The Google Similarity Distance (Rudi L. Cilibrasi, Paul M. B. Vitanyi著)

The Google Similarity Distance

Rudi L. Cilibrasi,　Paul M. B. Vitanyi著

検索エンジン「グーグル」を用いて、２つのものの関係性を表すという主旨の論文。

Information Distance とKolmogorov Complexity に基づいた、二つのオブジェクト、とりわけ語句の関係性を表す指標であるNormalized Information Distanceが定義されたが、これはコルモゴロフ複雑性を内包しているため、コンピュータで計算できない。そこでNormalized Compression Distanceというものが提唱された。これはコルモゴロフ複雑性K(x)を圧縮関数C(x)で近似したものである。コンピュータ上で関数を圧縮関数を指定すればNCDは計算できる。

そして本論文はその圧縮関数C(x)をグーグルサーチエンジンを用いてさらにG(x)として近似する物である。圧縮＝グーグルの接頭コードという発想である。

以下NGD。f(x)はxのグーグルサーチエンジンが返すxを含むページ数である。

さらにSVMと組み合わせるなどして、精度の向上にも努めている。

また、検証実験としてWordNetとの比較も行っており、erectrical termsについては100％の精度でwordnetと一致するなどといった結果もでている。

Wikipediaと同様に外部ソースを使った語句相関指標として使ってみたい。