自然言語の分析におけるテキストのプレゼンテーションの現代的側面：古典的および代替アプローチ

はじめに

コンピュータサイエンスでは、自然言語処理のトピックが年々人気を集めています。 そのような分析が必要とされる膨大な数のタスクのために、テキスト文書の自動処理の必要性を過大評価することは困難です。

この記事では、コンピューター処理用のテキスト文書のプレゼンテーションに対する最も人気のある最新のアプローチを簡単に説明します。 そして、まだ広く配布されていないものの1つについては、可能性がありますが、 コンテキスト広告ターゲティングなどのアルゴリズムを開発する際にSlickJumpでこのメソッドを使用するため、さらに詳しく説明します。

引用されたアプローチは、テキストだけでなく、一般に、たとえば遺伝学からのいくつかの高分子（DNA、RNA、タンパク質）などの記号配列として表現できるオブジェクトにも適用できることに注意してください。 合計で、4つの方法を検討します。

1. 特性の説明。
2. テキストのペアごとのオーバーレイ（配置）。
3. プロファイルと隠れマルコフモデルの形成。
4. フラグメントによるプレゼンテーション。

それでは始めましょう。

機能の説明

特性記述は、自然言語の分析で古典と呼ぶことができるアプローチです。 これは、特定の数の機能、たとえば、単語、または連続した単語のペア（いわゆるバイグラム）が分析されたテキストドキュメントと区別されることを意味します。 属性は、たとえば、一連のドキュメント内の出現頻度でフィルタリングしたり、リストから興味のないもの、たとえば前置詞や接続詞（「ストップワード」）をリストから削除したりできます。 さらに、各ドキュメントは、その中のこれらの属性の出現回数、または、たとえば、各要素が特定の属性に対応するベクトルとして表すのに便利なそれらの存在/不在によって特徴付けられます。 もちろん、その順序は事前に修正する必要があります。 重要なタスクは、異なる形で同じ兆候を識別することです。たとえば、「Katya」と「Katya」は同一の症状であると考えると便利です。 このため、語の基本のみが考慮されるステミングのプロセスが使用されます（ほとんどの場合、語根、接頭辞、接尾辞、語尾は破棄されます）。単数形の場合。 ほとんどの場合、2番目のプロセスはより複雑です。多くの場合、単語形式のベースが必要です（たとえば、単語 "people"の場合、通常の形式 "man"を取得できません）。一方、多くの言語の最初のプロセスでは、単語を変換するための規則のリストで十分です

たとえば、N。グミリョフの美しい詩「Giraffe」から抜粋したテキストを考えてみましょう。

聞く：遠く、遠く、チャド湖で
絶妙なキリンが歩き回ります。

ここからサインを選び出し（個々の単語のみを使用します）、それらを整理し、次のセットを取得します。

（聞く、遠く、湖、チャド、絶妙、さまよう、キリン）

前置詞「on」はストップワードとして使用されません。 上記のリストに基づいて、指定されたテキストの最初の行をベクター形式で表示すると、次のベクターが取得されます。

（1、2、1、1、0、0、0）

結果のベクトルをマトリックスに結合し、それらの間のさまざまな距離を測定し、その距離を測定し、周波数変換技術を適用します（たとえば、TF-IDF-ただし、この場合、適切な作業のために、標識と文書の数は十分でなければなりません）。

シーケンスのオーバーレイ、プロファイルの形成

一部のタスクは、シンボリックシーケンスのペアごとのオーバーラップ（アライメント）で構成されるアプローチを使用します。 この方法の本質は、一致するシーケンス文字が配置される位置の数を最大化することですが、シーケンス自体は「破損」する可能性があります。 このアプローチは、たとえばDNAなどの高分子がシンボルシーケンスの役割を果たすバイオインフォマティクスの問題で積極的に使用されており、通常、それらの一部は歴史的変更など、他の変更の結果です。 多くの場合、比較されるすべてのシーケンスには共通の祖先があると想定されます。 このアプローチのために、距離行列を生成するいくつかの近接度測定法が開発されており、さらなる作業が進行中です。

さらに、テキスト文書のプロファイルと隠れマルコフモデルの形成を含む方法があります。 このアプローチも、重複するシーケンスに基づいていますが、ペアワイズではなく複数です。 すべてのシーケンスが関与する位置は個別に強調表示されます。 隠れマルコフモデルはこのアプローチを発展させたもので、状態間の遷移によってシーケンスが生成されることを示唆しています。 特定の確率を持つ遷移ごとに、そのシンボルが形成されます。 この方法は広く普及していないため、このような簡単な説明について説明します。

フラグメントビュー

最後に、焦点を当てる最後のアプローチは、テキストの断片的な説明です。 このアプローチでは、いわゆる注釈付きサフィックスツリーを使用します。 注釈付きサフィックスツリー（ASD）は、すべてのテキストフラグメントをその頻度とともに計算して保存するために使用されるデータ構造です。 ルートツリー（つまり、その中の1つの頂点が強調表示され、ルートと呼ばれます）として定義されます。各ノードは1文字に対応し、ルートからこのノードへのパスをエンコードするテキストの頻度によってマークされます。
ASDを使用する場合、すべてのテキストは行-文字のチェーンに分割されます。 原則として、1行は2〜4個の連続した単語で構成されます。 短い文字列のSDAの例 下の図に示されています。



長さの接尾辞 ひも 長さ （ ）文字で構成 部分文字列と呼ばれる 。 たとえば、文字列の場合 長さ2の接尾辞は部分文字列になります 。 与えられた行でASDを構築するためのアルゴリズムの非公式な説明を提供します 。

1. ADAを格納するための空の構造を初期化します- 。 この構造は、ノードにシンボルと番号（その頻度）を持つツリーを格納できる必要があります。
2. すべての行サフィックスを検索します。 。
3. 各サフィックスについて 探している 接尾辞の先頭との一致が最大になるルートからのパス- 。 一致するすべての文字 、対応するノードの頻度を1増やします。
4. 偶然の場合 長さが短い 、その後、接尾辞は最後まで走査されません。 それから 頻度1を割り当てて新しいノードを作成する必要があります。
   

2行以上のASDを作成する場合、すべての行のサフィックスが共通ツリーに順番に重ねられます。 したがって、ドキュメントを複数行の形式で提示すると、対応するASDを作成できます。
ドキュメント用に構築されたASDを使用すると、行とドキュメントの近接性を見つけるなどの問題を正常に解決できます。 このタスクは、ツリー内の部分文字列の出現度を決定するタスクと呼ばれます。 その解決策を提示します（[3]で提案および詳細に説明）。

ノードの条件付き確率の概念を紹介します ASDで ルートトップ付き 。 ノード周波数 によって示す 。 その場合、ノードの条件付き確率は次と等しくなります。



どこで -ノードの祖先 木の中で 。 ルート頂点が祖先である頂点の場合 公式 次の形式を取ります。



多くの ツリーの最初のレベルにあるすべてのノードのセットのみです。

各サフィックスについて ひも ツリー内でのその発生の程度の推定値は、最大一致に属するノードの条件付き確率の合計として表されます 長さ 。



次に、ツリー内の行の出現度は次のように推定されます。



2つ以上のASDの文字列の出現度を比較する場合、式 見つかったオカレンスの長さで除算して変更する必要があります。



この式に従って、上の図に示されているツリーのいくつかの行のADSでの発生の度合いを練習して計算すると、次のプレートが得られます。

ひも	ツリー内の文字列の出現度
ジャバスクリプト	0.083
ジープ	0.125
スリックジャンプ	0.111
Jk	0.291
ジューク	0.125

上記のASDを構築するアルゴリズムは最適ではありません。 現在、古典的な文字列メソッドに基づくアルゴリズム、たとえば、文字列内の部分文字列を検索するためのUkkonenアルゴリズム（[4]で読むことができます）は、ASDを構築するためにより多く使用されます。 これにより、ASDの構築とASDでの行の発生の推定値の計算の両方に費やされる時間を短縮できます。 もう1つの領域は、必要なメモリリソースの削減です。 これは、特殊な配列など、ツリーを格納するためのさまざまなデータ構造を使用することで実現できます。

フラグメンテーションの利点

特徴的な方法と比較したこのアプローチの利点に注目します。 文字のアプローチは、バイグラムを記号として使用する場合（または、さらに長い単語のシーケンス-トライグラムなど、場合によってはベクトルの次元を大幅に増加させる場合）でも、テキストの深い「構造」を非常に悪く感じます。 さらに、フラグメントアプローチでは、単語を通常の形式に縮小する必要はありません（もちろん、変換規則のみを使用し、単語形式のベースを使用しない場合）-単語がASDに含まれている場合、そのベースは明らかにいくつかの場所に配置されますいくつかの枝。 しかし、最も重要なことは、断片化されたアプローチは、テキストの軽微なエラーを許容することです。 もちろん、これと属性のアプローチを学ぶことができる特別な方法がありますが、これはしばしばアルゴリズムを複雑にします。 当社の具体的な例を使用して、より詳細に説明します。

SlickJumpのアフィリエイトストアの商品のコンテキストターゲティングの技術は、兆候で動作する確率論的テーマモデルLDA（ディリクレの隠れた配置）に基づいています。 一般に、確率論的テーマモデリングは、独立した広大で興味深いトピックです。このトピックを取り上げるのであれば、この記事では取り上げません。 このアプローチにより、ドキュメントの近さを見つける問題（つまり、コンテキストと提供された商品）を解決し、膨大な数のドキュメントを解決することができます-そして、当社の拠点には200万を超えるパートナーストアの商品があります。

ただし、バナーのコンテキストターゲットでは、その数がパートナーのオンラインストアの製品の数と比較して少ないため、ASDメソッドに基づいて特別に開発されたモデルを使用します。 これにより、たとえばフォーラムなど、人々が鶏の足のように書く場合でも、高品質のコンテンツターゲットを提供できます。 例を考えてみましょう。

スマートフォン用のファッションアクセサリーを割引価格で提供する電器店のバナーがあるとします。 そして、広告プラットフォームとしてのモバイル技術に関するフォーラム。 広告主は、バナーのキーワードのリストを示すか、それを提供します（バナーの数が数千の場合に便利です。対応する機能があります）。 コンテキストに関連するバナー（通常はWebページ、フォーラムの投稿など）を選択する必要があります。 2つのコンテキストターゲットモデル：LDA（属性に基づく）とADAに基づくモデルを比較し、関連するバナーが2つの異なる状況で見つかるかどうかを確認します：人々が正しく書くときと間違えるとき。
すべての人がエラーなしで書いた場合、コンテンツターゲットの問題は発生しなかったでしょう。 キーワード「充電器」があり、メッセージテキストのどこかに「充電中」と表示されている場合、標識を正規化するプロセスにより、ターゲティングに問題は発生しません。 以下のスクリーンショットは、両方のモデルが関連するバナーを見つけたことを示しています。



しかし、人がhtcではなくhtsを書いた場合（原始的な例ですが、ジャンルの古典）、すべてがはるかに興味深いです。 この単語に関連するバナーを見つけてみましょう。 LDAモデルは、特別なデバイスを使用しない機能ベースのアプローチに基づいているため、何も見つかりません（または適切なものも見つかりませんが、これも悪いことです）。 また、ASDに基づいた方法は、3文字しか単語に誤りがない場合でも、優れた結果をもたらします。 これは下のスクリーンショットに示されており、リクエストに応じて対応する製品名が表示されています。

おわりに

もちろん、ASDを使用したアプローチでは、自然言語にとって非常に複雑な同義語と同音異義語の問題は解決されないため、すべての万能薬ではありません。 さらに、関連性の計算に必要なツリー内の行の出現度は、この行の長さに依存する時間で計算されます。行が長いほど時間がかかります。 そして、原始的なアプローチでは、すべてのドキュメントに対してADAでこのようなチェックを行う必要があります。 しかし、SlickJumpでは、特別な高次データ構造を使用して、すべての文書に関連する文書の候補リストを決定し、品質の損失なしにそれらの包含の程度を確認し、明らかに何もないところを検索しないようにします。 私たちはこの方向に積極的に取り組んでいますが、改善できることは他にもたくさんあります。

今後数年間でテキストを提示するためのフラグメント法が積極的に開発され、多くの方向に開発されることは間違いありません。 そして、次の記事では、注釈付き接尾辞ツリーを構築および表現するための最新のアルゴリズムを検討します。

トピックを読むためのリファレンス

1. Manning K. D.、Raghavan P.、SchützeH.情報検索の紹介。 M。：ウィリアムズ、2011
2. Mirkin、B. G.意思決定支援のためのクラスター分析方法：レビュー。 M .:国立研究大学経済学部出版会、2011年
3. Mirkin B.G.、Chernyak E.L.、Chugunova O.N.テキスト文書内の行の出現度を評価するための注釈付き接尾辞ツリー法。 ビジネス情報学。 2012.Vol。3. No. 21. S. 31-41。
4. Dubov M.S.、Chernyak E.L.注釈付きサフィックスツリー：実装機能。 In：全ロシア科学会議AIST-2013 / Otvのレポート。 エド：E. L.チェルニャック; 科学的 Ed .: D.I. Ignatov、M。Yu。Khachai、O。Barinova。 M。：国立公開大学「INTUIT」、2013年。S。49-57。
5. Mirkin BG、データ分析のコアコンセプト。 スプリンガー、2012
6. Korshunov A、Gomzin A.自然言語のテキストの主題モデリング。 ISP RASの議事録。 2012年。 S.215-244。
7. Steven Bird、Ewan Klein、Edward Loper。 Pythonによる自然言語処理。 OReilly Media、2009