正規化されたGoogle距離

正規化Google距離（NGD）は、特定のキーワードセットに対してGoogle検索エンジンが返すヒット数から導き出される意味的類似度尺度です。^[¹^]自然言語の意味において同じまたは類似の意味を持つキーワードは、正規化Google距離の単位で「近い」傾向があり、意味が異なる単語は離れている傾向があります。

具体的には、2つの検索語xとyの間のNGDは

\operatorname {NGD} (x,y)={\frac {\max\{\log f(x),\log f(y)\}-\log f(x,y)}{\log N-\min\{\log f(x),\log f(y)\}}}

ここで、Nは Google が検索したウェブページの総数に、ページ上に出現する単一の検索語の平均数を掛けたものです。f ( x )とf ( y ) はそれぞれ検索語xとyのヒット数です。f ( x , y ) はxとy の両方が出現するウェブページの数です。

もし $NGD(x,y)=0$ そして、xとyは可能な限り似ていると見なされるが、もし $NGD(x,y)\geq 1$ つまり、xとyは大きく異なるということです。検索語xとyが同じウェブページ上で同時に出現することがなく、別々に出現する場合、両者のNGDは無限大になります。両方の語が常に同時に出現する場合は、NGDはゼロになります。

例：2013年4月9日、「シェイクスピア」でGoogle検索すると1億3000万件、「マクベス」で2600万件、「シェイクスピアマクベス」で2080万件のヒットがありました。Googleがインデックスしたページ数は、「the」という検索語のヒット数（252億7000万件）から推定されました。平均的なページに約1000個の検索語があると仮定すると、 $N=25,270,000,000,000$ したがって

NGD(シェイクスピア,マクベス)=(26.95-24.31)/(44.52-24.63)=0.13

。

Googleが提供する相対的な意味論によれば、「シェイクスピア」と「マクベス」は非常によく似ている。

導入

正規化された Google 距離は、以前の正規化された圧縮距離から導出されます。^{[ 2 ]}^{[ 3 ]}つまり、マウスの 4 文字のゲノムやシェイクスピアのマクベス のテキストのように、オブジェクトを文字通りに与えることができます。これらのオブジェクトの類似性は NCD によって与えられます。簡単にするために、オブジェクトのすべての意味は、オブジェクト自体によって表されるとします。オブジェクトは、「マウスの 4 文字のゲノム」や「シェイクスピアのマクベスのテキスト」のように、名前で与えることもできます。また、文字通りに与えることができず、名前でしか与えられず、人類の背景にある共通知識の文脈から意味を得るオブジェクトもあります。「家」や「赤」などです。オブジェクトの名前間の類似性は NGD によって与えられます。

Googleの配布とGoogleコード

Google検索語の確率は、Googleが返すページ数の頻度を、Googleがインデックス化したページ数（かつそれらのページにおける検索語の平均数）で割った値として定義され、社会で実際に使用されている検索語の実際の相対頻度を近似的に表します。この前提に基づき、正規化されたGoogle距離によって表される関係は、検索語を支配する真の意味関係を近似的に捉えています。NGDでは、ワールドワイドウェブとGoogleが使用されます。その他のテキストコーパスには、Wikipedia、キングジェームズ版聖書、オックスフォード英語辞典、および適切な検索エンジンが含まれます。

不動産

以下の性質は^{[ 1 ]で証明されています。}

NGDはおおよそ0から $\infty$ わずかにマイナスになる場合もあります。たとえば、「red red」は「red」よりもGoogleのワールドワイドウェブでのヒット数が約20%多くなります。（2013年半ばには「red」のヒット数は42億6000万件、「red red」のヒット数は55億件でした。現在では、「red red」は「red」よりもはるかに少ない結果しか返しません。） $NGD(x,y)\geq 1$ すると、xとyは非常に異なるものとみなされます。
NGDはメトリックではありません。xとyが等しくない場合、NGDはゼロになります。ただし、xとyは常に同じウェブページ上に同時に出現します。NGDの式から、対称であることがわかります。NGDは三角形の性質を満たしていません。ただし、これらの結果は理論上のものです。Googleを使用したワールドワイドウェブで三角形の性質に違反する実際的な例を挙げるのは困難です。

アプリケーション

色と数字、素数と非素数などへの応用は、^{[ 1 ]}に示されており、 WordNetカテゴリを使用したランダム化された大規模実験も示されています。素数と非素数の場合と WordNet 実験では、NGD 法はサポートベクターマシン分類器で拡張されています。実験は、25 個の正例と 25 個の負例で構成されています。WordNet 実験は、100 個のランダムな WordNet カテゴリで構成されています。NGD 法の成功率は 87.25% でした。平均は 0.8725、標準偏差は 0.1169 でした。これらの率は、WordNet カテゴリとの一致についてであり、これは、それらに入力した博士号を持つ研究者の知識を表しています。一致率が 75% 未満になることはまれです。

参考文献

1 2 3 R.L. Cilibrasi; PMB Vitanyi (2007). "Google 類似度距離". IEEE Transactions on Knowledge and Data Engineering . 19 (3): 370–383 . arXiv : cs/0412098 . Bibcode : 2007ITKDE..19..370C . doi : 10.1109/TKDE.2007.48 . S2CID 59777 .
↑ RL Cilibrasi; PMB Vitanyi (2005). "Clustering by Compression" . IEEE Transactions on Knowledge and Data Engineering . 51 (3): 12. arXiv : cs.CV/0312044 . Bibcode : 2007ITKDE..19..370C . doi : 10.1109/TKDE.2007.48 . S2CID 59777 .
↑ M. Li; X. Chen; X. Li; B. Ma; PMB Vitanyi (2004 年 12 月). "類似度メトリック". IEEE Transactions on Information Theory . 50 (12). IEEE : 3250– 3264. Bibcode : 2004ITIT...50.3250L . doi : 10.1109/TIT.2004.838101 . S2CID 221927 .

さらに読む

R. Allen & Y. Wu (2005). "コレクションの範囲の指標" . JASIST . 55 (10): 1243–1249 . doi : 10.1002/asi.20202 .
M. Li & PMB Vitanyi (2019).コルモゴロフ複雑性とその応用入門（第4 版）. Springer.
ダンカン・グラハム＝ロウ（2005年1月28日）「グーグルの意味探求」ニュー・サイエンティスト。 2005年2月5日時点のオリジナルよりアーカイブ。
J. Poland & Th. Zeugmann (2006).固有ベクトルと半正定値計画法による Google 距離のクラスタリング(PDF) . Knowledge Media Technologies、第 1 回国際コア間ワークショップ。ドイツ、ダグシュトゥール。pp. 61–69。
A. Gupta & T. Oates (2007).オントロジーとウェブを用いた語彙意味論の学習(PDF) . IJCAI'07: 第20回国際人工知能合同会議議事録. pp. 1618–1623 . 2009年2月19日にオリジナル(PDF)からアーカイブ済み。（NGDと他のアルゴリズムとの比較を含む。）
Wong, W. 、 Liu, W.、Bennamoun, M. ( 2007)「特徴のない類似性に基づく用語クラスタリングのためのツリー走査アリアルゴリズム」データマイニングと知識発見。15 (3): 349–381。doi : 10.1007/s10618-007-0073- y。S2CID 14924678。（用語クラスタリングにおけるNGDの使用）

[CV07-1] 1 2 3 R.L. Cilibrasi; PMB Vitanyi (2007). "Google 類似度距離". IEEE Transactions on Knowledge and Data Engineering . 19 (3): 370–383 . arXiv : cs/0412098 . Bibcode : 2007ITKDE..19..370C . doi : 10.1109/TKDE.2007.48 . S2CID 59777 .

[CV04-2] RL Cilibrasi; PMB Vitanyi (2005). "Clustering by Compression" . IEEE Transactions on Knowledge and Data Engineering . 51 (3): 12. arXiv : cs.CV/0312044 . Bibcode : 2007ITKDE..19..370C . doi : 10.1109/TKDE.2007.48 . S2CID 59777 .

[Li04-3] M. Li; X. Chen; X. Li; B. Ma; PMB Vitanyi (2004 年 12 月). "類似度メトリック". IEEE Transactions on Information Theory . 50 (12). IEEE : 3250– 3264. Bibcode : 2004ITIT...50.3250L . doi : 10.1109/TIT.2004.838101 . S2CID 221927 .

[

[ 2 ]

[ 3 ]