知識ベース

ステミング

言語形態および情報検索において、 ステミングは、語尾変化した(または派生した)単語を単語の語幹、ベース、またはルート形式(通常は書き言葉形式)に減らすプロセスです。語幹は、単語の形態学的ルートと同一である必要はありません。通常、この語幹自体が有効なルートではない場合でも、関連語が同じ語幹にマップされれば十分です。ステミングのアルゴリズムは、1960年代からコンピューターサイエンスで研究されてきました。多くの検索エンジンは、同じ語幹を持つ語を類義語と同様に一種のクエリ拡張、つまり混同と呼ばれるプロセスとして扱います。

単語を茎コンピュータプログラムやサブルーチンは語幹アルゴリズム 、またはステマステミングプログラムと呼ばれることもあります。

stem catで動作する英語のステマーはcatscatlikecattyなどの文字列を識別する必要があります。語幹アルゴリズムはまた、幹に単語釣りを減らし、 釣り 、と漁師かもしれません。ステムが主張し 、例えばポーターアルゴリズムが減少し、単語である必要はないと主張主張主張 、および幹にargUARGUS。

歴史

最初に公開されたステマーは、1968年にジュリー・ベス・ロビンズによって書かれました。この論文は、その初期の日付で注目に値し、この分野の後の仕事に大きな影響を与えました。彼女の論文は、プリンストン大学のジョン・W・テューキー教授、ジェラルド・サルトン教授の指揮の下、マイケル・レスクによってハーバード大学で開発されたアルゴリズム、ジェームズ・L・ドルビーによって開発された第3のアルゴリズムによるアルゴリズムの3つの初期の主要な試みに言及していますカリフォルニア州ロスアルトスの研究開発コンサルタントの

後のステマーはMartin Porterによって書かれ、1980年7月号のジャーナルProgramに掲載されました。このステマーは非常に広く使用され、英語のステミングに使用される事実上の標準アルゴリズムになりました。ポーター博士は、ステミングと情報検索に関する研究で2000年にTony Kent Strix賞を受賞しました。

Porterステミングアルゴリズムの多くの実装が記述され、自由に配布されました。ただし、これらの実装の多くには微妙な欠陥が含まれていました。その結果、これらのステマーはその潜在能力と一致しませんでした。このエラーの原因を排除するために、Martin Porterは2000年頃に公式のフリーソフトウェア(ほとんどBSDライセンス)アルゴリズムの実装をリリースしました。彼は、ステミングアルゴリズムを記述するためのフレームワークSnowballを構築することで、今後数年間にわたってこの作業を拡張し、いくつかの他の言語のステマーとともに、改善された英語のステマーを実装しました。

Paice-Husk Stemmerは、1980年代後半にLancaster UniversityのChris D Paiceによって開発された、反復ステム機能であり、外部に保存された一連のステミングルールを備えています。ルールの標準セットは「強力な」ステマーを提供し、エンディングの削除または置換を指定できます。置換技術により、プロセスの別の段階で再コーディングまたは部分一致を提供する必要がなくなります。 Paiceは、オーバーステミングおよびアンダーステミングのエラーのカウントに基づいて、ステマーを比較するための直接測定も開発しました。

アルゴリズム

いくつかのタイプのステミングアルゴリズムがあり、パフォーマンスと精度、および特定のステミング障害の克服方法が異なります。

単純なステマーは、ルックアップテーブルで活用形を検索します。このアプローチの利点は、シンプルで高速、例外を簡単に処理できることです。欠点は、すべての活用形を表に明示的にリストする必要があることです。新しい単語や見慣れない単語は完全に規則的(例:cats〜cat)でも処理されず、テーブルが大きくなる場合があります。英語のような単純な形態の言語の場合、表のサイズは控えめですが、トルコ語のような高度に活用された言語には、ルートごとに数百の潜在的な活用された形式があります。

ルックアップアプローチでは、予備的な品詞タグを使用して、オーバーステミングを回避できます。

生産技術

ステマーで使用されるルックアップテーブルは、通常、半自動で作成されます。たとえば、単語が「run」の場合、逆アルゴリズムは「running」、「runs」、「runned」、「runly」という形式を自動的に生成します。最後の2つの形式は有効な構成ですが、可能性は低いです。

接尾辞除去アルゴリズム

接尾辞除去アルゴリズムは、活用形とルート形関係で構成されるルックアップテーブルに依存しません。代わりに、通常はより小さな「ルール」のリストが保存され、入力語形式が与えられた場合にそのルート形式を見つけるためのアルゴリズムのパスが提供されます。ルールの例を次に示します。

  • 単語が「ed」で終わる場合、「ed」を削除します
  • 単語が「ing」で終わる場合、「ing」を削除します
  • 単語が「ly」で終わる場合は、「ly」を削除します

サフィックスストリッピングアプローチは、保守者が言語学と形態学、およびエンコーディングサフィックスストリッピングルールの課題について十分に知識があると仮定すると、ブルートフォースアルゴリズムよりもメンテナンスがはるかに簡単であるという利点があります。接尾辞除去アルゴリズムは、例外的な関係(「実行」や「実行」など)を処理する際のパフォーマンスが低いため、粗雑なものと見なされる場合があります。接尾辞除去アルゴリズムによって生成されるソリューションは、ほとんど例外なく、よく知られている接尾辞を持つ語彙カテゴリに限定されます。しかし、これは問題です。すべての品詞がこのように適切に策定されたルールのセットを持っているわけではないからです。補題は、この課題を改善しようとします。

プレフィックス除去も実装できます。もちろん、すべての言語で接頭辞または接尾辞が使用されるわけではありません。

追加のアルゴリズム基準

サフィックス除去アルゴリズムは、さまざまな理由で結果が異なる場合があります。そのような理由の1つは、出力語が特定の言語の実際の語でなければならないかどうかをアルゴリズムが制約するかどうかです。一部のアプローチでは、単語が言語辞書(言語内のすべての単語のセット)に実際に存在する必要はありません。あるいは、一部の接尾辞除去アプローチは、実際の単語として存在するすべての既知の形態学的単語のルートのデータベース(大きなリスト)を維持します。これらのアプローチは、決定を行う前に用語の存在についてリストをチェックします。通常、この用語が存在しない場合、代替アクションが実行されます。この代替アクションには、いくつかの他の基準が含まれる場合があります。出力用語が存在しないと、アルゴリズムが代替接尾辞除去規則を試行するようになる場合があります。

2つ以上の接尾辞除去規則が同じ入力用語に適用される場合があり、適用する規則に関してあいまいさが生じます。アルゴリズムは、1つのルールまたは別のルールに(人間の手または確率的に)優先順位を割り当てることができます。または、アルゴリズムは1つのルール適用を拒否する場合があります。これは、存在しない用語を生成するのに対し、他の重複するルールは生成しないためです。例えば、英語の用語の親善与えられ、アルゴリズムはIESサフィックスを識別し、適切なルールを適用し、friendlの結果を達成することができます。 friendlは辞書にない可能性が高いため、ルールは拒否されます。

基本的な接尾辞除去の1つの改善点は、接尾辞置換の使用です。除去ルールと同様に、置換ルールは接尾辞を代替接尾辞に置き換えます。たとえば、 iesyに置き換えるルールが存在する可能性があります。これがアルゴリズムに与える影響は、アルゴリズムの設計によって異なります。説明のために、アルゴリズムは、 iesサフィックス除去ルールとサフィックス置換ルールの両方が適用されることを識別できます。除去ルールの結果、用語集に存在しない用語が存在しますが、置換ルールは存在しないため、代わりに置換ルールが適用されます。この例では、 friendliesfriendlではなくfriendlyになります。

さらに詳細に説明すると、一般的な手法は、ルールを周期的に適用することです(コンピューター科学者が言うように、再帰的に)。このシナリオ例でサフィックス置換ルールを適用した後、「 フレンドリー 」という用語で一致するルールを識別するために2回目のパスが行われます。この場合、 ly strippingルールが識別され、受け入れられます。要約すると、 フレンドリは(置換を介して) フレンドリーになり、 フレンドリは(ストリッピングを介して) フレンドになります。

この例は、ルールベースのアプローチとブルートフォースアプローチの違いを説明するのにも役立ちます。ブルートフォースアプローチでは、アルゴリズムは数十万の語形変化形の友好を検索し、理想的には対応するルート形friendを見つけます。ルールベースのアプローチでは、上記の3つのルールが連続して適用され、同じソリューションに収束します。ルックアップアルゴリズムはソリューションに直接アクセスできるため、ブルートフォースアプローチが遅くなる可能性がありますが、ルールベースではいくつかのオプションとそれらの組み合わせを試してから、最適な結果を選択する必要があります。

補題アルゴリズム

単語の語幹を決定する問題に対するより複雑なアプローチは、見出し語化です。このプロセスでは、最初に単語の品詞を決定し、品詞ごとに異なる正規化ルールを適用します。一部の言語では、語幹の規則は単語の品詞に応じて変化するため、品詞は最初にルートを見つける前に検出されます。

このアプローチは、正しい語彙カテゴリ(品詞)を取得することを条件としています。特定のカテゴリの正規化ルールには重複がありますが、間違ったカテゴリを特定したり、適切なカテゴリを作成できないため、サフィックスストリッピングアルゴリズムに対するこのアプローチの利点が制限されます。基本的な考え方は、ステマーがステミングされている単語についてより多くの情報を把握できる場合、より正確な正規化ルールを適用できることです(サフィックスストリッピングルールとは異なり、ステムも変更できます)。

確率的アルゴリズム

確率的アルゴリズムでは、確率を使用して単語のルート形式を識別します。確率論的アルゴリズムは、ルートモデルのテーブルでトレーニングされ(確率論的モデルを開発するために、屈折したフォームの関係になります)。このモデルは、通常、接尾辞の除去または見出し語化と本質的に類似した複雑な言語規則の形式で表現されます。ステミングは、学習済みモデルに屈折形を入力し、モデルにその内部ルールセットに従ってルート形を生成させることにより実行されます。これは、サフィックスの除去と補題に似ていますが、最も適切なルールの適用に関する決定、または単語をステミングして同じ単語を返すかどうか、または2つの異なるルールを順番に適用するかどうかは、出力単語が正しい確率が最も高い(つまり、正しくありません。これが通常の測定方法です)。

一部の補題アルゴリズムは、複数の品詞に属する可能性のある単語が与えられると、確率が各可能な部分に割り当てられるという点で確率的です。これは、コンテキストと呼ばれる周囲の単語を考慮するかどうかを考慮します。文脈自由文法では、追加情報は考慮されません。いずれの場合も、可能性のある各音声部分に確率を割り当てた後、音声の最も可能性の高い部分が選択され、そこから適切な正規化規則が入力単語に適用され、正規化(ルート)形式が生成されます。

nグラム分析

一部のステミング手法では、単語のn-gramコンテキストを使用して、単語の正しい語幹を選択します。

ハイブリッドアプローチ

ハイブリッドアプローチでは、上記の2つ以上のアプローチを同時に使用します。簡単な例は、最初にブルートフォースを使用してルックアップテーブルを参照するサフィックスツリーアルゴリズムです。ただし、特定の言語の単語間の関係のセット全体を保存しようとする代わりに、ルックアップテーブルは小さく保持され、「ran => run」などの「頻繁な例外」のわずかな量の保存にのみ使用されます。単語が例外リストにない場合、接尾辞の除去または見出し語化を適用し、結果を出力します。

ステマーの付加

言語学では、接辞という用語は接頭辞または接尾辞のいずれかを指します。接尾辞の処理に加えて、いくつかのアプローチは一般的な接頭辞の削除を試みます。たとえば、単語を無期限に指定すると、先頭の「in」が削除可能なプレフィックスであることを識別します。前述の同じアプローチの多くが適用されますが、 affix strippingという名前で行きます。いくつかのヨーロッパ言語の接辞のステミングの研究は、ここにあります。

マッチングアルゴリズム

そのようなアルゴリズムは、語幹データベース(たとえば語幹を含むドキュメントのセット)を使用します。上記のように、これらの語幹は必ずしも有効な単語そのものではありません(ただし、「参照」および「参照」の「参照」などの一般的なサブストリング)。単語をステミングするために、アルゴリズムはそれをデータベースのステムと一致させ、単語内の候補ステムの相対的な長さなどのさまざまな制約を適用しようとします(たとえば、短いプレフィックス「be」、 「be」、「been」、「being」などの単語の語幹であり、「beside」という語の語幹とは見なされません)。

言語の課題

この分野の初期の学術研究の多くは英語に焦点を当てていましたが(ポーターステマーアルゴリズムを大幅に使用)、他の多くの言語が調査されてきました。

ヘブライ語とアラビア語は依然として語幹解析が難しい研究言語と見なされています。英語のステマーはかなり些細なものです(「ドライ」が動詞「dry」​​の三人称単数形である、「軸」が「軸」および「軸」の複数形であるなど、たまにしか問題がありません)。しかし、ターゲット言語の形態、正字法、および文字エンコードがより複雑になると、ステマーの設計が難しくなります。たとえば、イタリア語のステマーは英語のものよりも複雑で(動詞の屈折の数が多いため)、ロシア語のステマーはより複雑(名詞の変形)が多く、ヘブライ語のステマーはさらに複雑です(非連結形態により、母音のない書記体系、および接頭辞除去の要件:ヘブライ語の語幹は2、3、または4文字にすることができますが、それ以上ではありません)。

多言語ステミング

多言語ステミングは、検索クエリを解釈するときに、単一の言語のみの規則ではなく、2つ以上の言語の形態学的規則を同時に適用します。多言語ステミングを使用する商用システムが存在します。

エラーメトリック

ステミングアルゴリズムには、オーバーステミングとアンダーステミングの2つのエラー測定値があります。オーバーステミングとは、2つの異なる語形変化した語が同じ語根に由来するエラーですが、そうでないはずの誤検知です。アンダーステミングとは、2つの異なる語形変化した語が同じ語根に由来するはずのエラーですが、そうではない-偽陰性です。ステミングアルゴリズムは、各タイプのエラーを最小化しようとしますが、一方のタイプを減らすと、もう一方のタイプを増やすことができます。

たとえば、広く使用されているPorterステマーは、「universal」、「university」、および「universe」を「univers」にステム処理します。これはオーバーステミングの場合です。これらの3つの単語は語源的に関連していますが、それらの現代の意味は大きく異なるドメインにあるため、検索エンジンで同義語として扱うと検索結果の関連性が低下する可能性があります。

ポーターステマーのアンダーステミングの例は、「alumnus」→「alumnu」、「alumni」→「alumni」、「alumna」/「alumnae」→「alumna」です。この英語の単語はラテン語の形態を保持するため、これらの同義語は混同されません。

用途

ステミングは、類似した基本的な意味を持つ単語をグループ化するための近似方法として使用されます。たとえば、「水仙」に言及するテキストは、「水仙」に言及するテキスト(sなし)とおそらく密接に関連しています。しかし、場合によっては、同じ形態の語幹を持つ単語は密接に関連していない慣用的な意味を持ちます。「マーケティング」を検索するユーザーは、「マーケティング」ではなく「マーケティング」に言及するほとんどの文書で満足しません。

情報検索

ステマーは、Web検索エンジンなどのクエリシステムの一般的な要素です。しかし、英語のクエリシステムに対するステミングの有効性はすぐにかなり制限されることがわかりました。そのため、初期の情報検索研究者は、一般にステミングを無関係とみなすようになりました。代わりに、ステムではなくn-gramの検索に基づく代替アプローチを使用できます。また、ステマーは、英語以外の言語でも大きな利点を提供する場合があります。

ドメイン分析

ステミングは、ドメイン分析でドメイン語彙を決定するために使用されます。

商用製品での使用

多くの商業企業は、少なくとも1980年代からステミングを使用しており、多くの言語でアルゴリズムおよび語彙のステマーを作成しています。

Snowballステマーと市販の語彙ステマーを比較して、さまざまな結果が得られています。

Google検索は2003年に語幹を採用しました。以前は「魚」を検索しても「釣り」は返されませんでした。他のソフトウェア検索アルゴリズムでは、語幹処理の使用方法が異なります。部分文字列を単純に検索するプログラムは、明らかに「fishing」で「fish」を見つけますが、「fishes」を検索すると「fish」という単語の出現は見つかりません。