はじめに

単語やキーワードの類似度を計算したいシーンはよくあります。
最近では単語やキーワードをベクトルに変換して類似度を計算する方法が主流ですが, 一昔前にとてもユニークな類似度計算の手法が提案されていました。
それが本記事のテーマである Normalized Google Distance です。

Normalized Google Distance は $2007$ 年に The Google Similarity Distance として発表されました。

本手法の一番の特徴は単語やキーワードの類似度に Google 検索エンジンによるヒット数を用いていることです。¹

以下でちょっとした概説を行うとともに, 簡単な実行結果をお見せします。²

Normalized Google Distance

$w_1$, $w_2$ を単語もしくはキーワード, $G$ を検索システムとします。
また $G(w_1)$ を $w_1$ の $G$ によるヒット数, $G(w_1, w_2)$ を$w_1$ かつ $w_2$ の $G$ によるヒット数とし, $|G|$ を検索システム $G$ が持つ全ての検索結果数とします。
このとき,

$$
NGD(w_1, w_2) := \dfrac{\max\{\log G(w_1), \log G(w_2)\} - \log G(w_1, w_2)}{\log |G| - \min\{\log G(w_1), \log G(w_2)\}}
$$

を Normalized Google Distance (NGD) と呼びます。

$NGD(w_1, w_2)$ は一般的に $0 \leq NGD(w_1, w_2) \leq 1$ の値をとりますが, $NGD(w_1, w_2) < 0$ や $NGD(w_1, w_2) > 1$ となることもあります。

Normalized Google Distance では $NGD(w_1, w_2)$ の値が $0$ に近いほど $w_1$ と $w_2$ の類似度が高く, $1$ を超えると $w_1$ と $w_2$ に類似性はほとんどないと解釈します。

やってみた

josh-ashkinaze/Normalized-Google-Distance に実装が公開されているので試してみました。
$|G|$ の値を取得することはできないので, 上記のコードの中では Normalized Google distance (Wikipedia) を習って「the」の検索結果数を採用していることに注意してください。³

実行時に 'NoneType' object has no attribute 'text' が出る方はこちらの issue を確認してみてください。

実験では「太宰治」といくつかの単語の類似度を計算してみます。

コードは以下です :

ngd_sample.py

from ngd import *

if __name__ == '__main__' :
    w1 = '太宰治'
    w2_list = [
        '太宰治',
        '走れメロス',
        '人間失格',
        '芥川龍之介',
        '文豪',
        'ゼータ関数',
        '頂点作用素代数',
        'ブルーアイズホワイトドラゴン',
        'デスメタル',
        'モンゴリアン・チョップ・スクワッド'
    ]

    for w2 in w2_list :
        ngd = calculate_NGD(w1, w2)
        print(f'({w1}, {w2}) : {ngd}')

結果は以下のようになりました :

実行結果

(太宰治, 太宰治) : 0
(太宰治, 走れメロス) : 0.3835239827371587
(太宰治, 人間失格) : 0.28235421091148194
(太宰治, 芥川龍之介) : 0.22330888312055666
(太宰治, 文豪) : 0.3333057649058047
(太宰治, ゼータ関数) : 0.7095620960433643
(太宰治, 頂点作用素代数) : 0.7367494049492057
(太宰治, ブルーアイズホワイトドラゴン) : 0.33743545300524547
(太宰治, デスメタル) : 0.7290201345063949
(太宰治, モンゴリアン・チョップ・スクワッド) : 0.916910907640382

定義から明らかなように, 「太宰治」同士の類似度は $0$ になっていますね。

「太宰治」を除き最も類似度が高かったのは「芥川龍之介」の $0.22330888312055666$ でした。
他にも「走れメロス」や「人間失格」, 「文豪」といった「太宰治」と類似性があると感じられるものについてはスコアが $0.2 ～ 0.4$ のあたりに集中していますね。

一方で類似性が無さそうな「ゼータ関数」や「頂点作用素代数」, 「デスメタル」, 「モンゴリアン・チョップ・スクワッド」はスコアが $0.7～0.9$ あたりに集中していました。

個人的に面白いなーと思ったのは「太宰治」と「ブルーアイズホワイトドラゴン」の類似度が $0.33743545300524547$ となっているところです。
数値だけ見ると「走れメロス」よりも「ブルーアイズホワイトドラゴン」の方が「太宰治」と類似していることになります。
~~太宰治は海馬瀬人だった…？~~

おわりに

単語やキーワードの類似度計算に検索エンジンのヒット数を用いる手法 Normalized Google Distance を紹介しました。
精度面では現在主流になっている手法に敵わないと思いますが, 発想のユニークさが個人的にとても気に入っています。
分散表現がメインになる前だったからこそ生まれたアイデアなのでしょうか…？

本論文や適用事例まで深く調べられてないので, 今後もっと勉強して理解を深めようと思います！

参考

The Google Similarity Distance
Normalized Google distance (Wikipedia)
josh-ashkinaze/Normalized-Google-Distance

論文では Google 検索エンジンを使用していますが, 特段 Google 検索エンジンである必要はなく任意の検索エンジンで代替可能です。 ↩
筆者は情報工学出身ではないため, NGD の背景にある理論を何も知りません。ご存じの方がいらっしゃれば教えてください。また現時点では論文も深く読み込めていないため, 薄い理解となってしまっていることをご容赦ください。 ↩
「the」の検索結果がハードコードされているため, 今の結果とは少し異なるかもしれません。 ↩