はじめに
自然言語処理において意味を扱う際に、ある表現の意味と別の表現の意味がどれだけ関わりがあるのかということが分かると有用であることが多い。以下に紹介する文献では、検索エンジンGoogleでのヒット数を用いて、意味の関わりの強さを測る手法が提唱されている。
- Cilibrasi, R. L. & Vitanyi, P. M. B. (2007). The Google Similarity Distance. IEEE Transactions on Knowledge and Data Engineering, 19(3), 370-383. （このページからPDFがダウンロード可。）
今回は、この論文の内容について紹介したい。正直言って、この辺の議論は自分の専門外で、論文もしっかりと読み込めていない。なので、以下の記述は不正確な点もあるかもしれないが、ご容赦願いたい。なお、「かしわ進化論。」というブログにもこの論文について紹介した記事があるので参照されてはいかがだろうか。
意味の関わりの強さ
今回紹介する論文が目的としているのは、表現と表現の間の意味の関わりの強さがどれほどであるかを測ることである。
普通の社会生活を行っている人間なら、ある表現と別の表現を比べて、意味的に関係があると判断することができるだろう。例えば、「風邪」という表現は「うがい」という表現と関わりが深いが、「風邪」と「冥王星」はあまり関わりがなさそうだと判断することができる。
なお、意味の関わりというのは、色々なパターンがある。例えば、「自動車」と「ハンドル」は全体と部分の関係になるし、「親戚」と「親類」は同義という関係になる。もっとも、今日紹介する論文では、意味の関わりにさまざまなものがあることについては特に気にしていないので、このことは放っておく。
さて、人間なら意味の関わりの強さが割合とすぐに分かるのだが、計算機はそうはいかない。計算機は何も教えなければ、何も分からないのである。このため、計算機に意味に関する作業を行わせる際には、意味の関わりの強さを教える必要が出てくる。
正規化Google距離の定義と性質
今回紹介する論文では、意味の関わりの強さを測る尺度として、正規化Google距離 (Normalized Google Distance) というものを提唱している。略称は、Normalized Google Distance の頭文字をとって、NGD である。
ある表現 x と ある表現 y の間の正規化Google距離は、以下のようにして求められる。
\[ NGD(x, y) = \frac{\max\{\log f(x), \log f(y)\} – \log f(x, y)}{\log N – \min\{\log f(x), \log f(y)\}} \]ここで、f(x) は表現 x をGoogleで検索した際のヒット数であり、f(y) は表現 y をGoogleで検索した際のヒット数である。また、f(x, y) は x かつ y をGoogleで検索した際のヒット数である。また、N はGoogle にインデクスされたページの数である [1] 。すなわち、N はGoogle が検索の対象としているページの数と言って良い。
なお、ここでは検索エンジンとしてGoogleが用いたが、別にGoogleを用いる必然性はなく、他の検索エンジンを用いても構わない。
基本的には、正規化Google距離は、0から1までの値をとる。0 ならば意味が一致し、1ならば意味に関わりがまったくない [2] ということになる [3] 。
今回紹介している論文に載っている具体例として、“horse”（馬）と “rider”（乗り手） の間の正規化Google距離を求める例を紹介しよう。検索が行われた時点で、“horse”は46,700,000ページだけヒットし、“rider”は12,200,000ページだけヒットしたという。また、“horse” かつ “rider” を検索すると、2,630,000ページだけヒットしたという。この検索が行われたときは、Google は、8,058,044,651ページをインデクスしていたとのことである。先に挙げた式で言うと、f(x) = 46,700,000, f(y) = 12,200,000, f(x, y) = 2,630,000, N= 8,058,044,651 ということになる [4] 。これに基づいて、正規化Google距離を計算すると、およそ 0.44 となる。
正規化Google距離の理論的背景
理論的に言えば、正規化Google距離は、正規化情報距離 (Normalized Information Distance) を近似したものであり、正規化情報距離の定義の中に含まれているコルモゴロフ複雑性がGoogleでのヒット数で近似されている。
こう書いてもなにがなにやら分からないかもしれないが、順を追ってみていこう。コルモゴロフ複雑性 (Kolmogorov complexity) は、データの複雑性を示す指標で、そのデータを記述するためにはどれだけの長さの記述が必要かということを示している。詳しいことは、Wikipedia の「コルモゴロフ複雑性」のページを見て欲しい。
そして、ある表現 x と ある表現 y の間の距離を示す指標として、正規化情報距離 (Normalized Information Distance) というものがある。この正規化情報距離の定義の中に、コルモゴロフ複雑性が含まれている。しかし、実はコルモゴロフ複雑性を計算することは原理的に不可能である。このため、正規化情報距離を求めることも不可能ということになる。
このままではどうしようもないので、コルモゴロフ複雑性の代わりにGoogleでのヒット数を使おうというのが、正規化Google距離の考え方である。
正規化Google距離の応用
正規化Google距離は、自然言語処理のさまざまな側面に応用できるようである。今回紹介した論文の中で挙げられている例を順に挙げていこう。
まず、階層的クラスタリングに応用した例がある。17世紀のオランダの画家の絵の名前の、Googleでのヒット数を調べることで、どの絵とどの絵が近いかを調べている。結果としては、同じ画家の絵が1つの部分に固まることになる。つまり、Googleでのヒット数を見るだけで、ある種の作者の判別ができたのである。
また、SVM [5] と組み合わせた例も出ているし、機械翻訳に応用した例もある。
この他、WordNet [6] の意味記述と、正規化Google距離の分析結果との比較を行っている。
- 元論文では、Nをこのように定義しているわけではないのだが、実質的にはN はGoogle にインデクスされたページの数を示しているので、このように書いた。 [↩]
- 意味に関わりがまったくないということと、対義語であるということは違う。対義語である場合は、少なくとも反対の意味であるという関わりが存在している。 [↩]
- 厳密に言うと、負数になったり、1よりおおきくなって無限大になることもある。 [↩]
- f(x) と f(y)は逆になっても同じ。 [↩]
- SVM とは、Support Vector Machine の略で、自然言語処理の分野では良く用いられる手法の1つである。なんらかのデータを元に訓練を行い、その訓練の成果をもって、判別を行うのが仕事。 [↩]
- WordNet は、英語の語彙のデータベースで、階層的な意味記述が行われている。 [↩]