Word Mover's Distance（WMD）
2021/04/27
藤田昭人
藤田昭人
僕は一度気が削がれると
なかなか元の状態に戻れないヤツなのですが…
とある
キッカケ
を掴んでブログ執筆を再開することができました。
ここからの数回は Word Mover's Distance (WMD) について取り上げます。
BookBot の紹介をして以来、 Word2Vec、 Earth Mover's Distance と対話機能の説明からドンドン離れて行くので 「迷走している」 と感じている方もいらっしゃるかもしれませんが、 この WMD の説明で「なるほど」と納得してもらえる…つもりです（笑）
WMD って何？
WMDは、類似文書検索（あるいは 概念検索 ともいう）、つまり 「文書検索で任意の文を与えると、 その文と意味的に近い文を検索する」 ためのアルゴリズムなんだそうです。
言い換えれば 「２つの文の意味的な距離を測る」 アルゴリズムなんですが…
- 文を単語単位に分解し、
- Word2Vec を使って、各々の単語毎に「単語の意味的な距離」を測り、
- EMD を使って、単語間の意味的距離を合算する
…のがWMD、つまり直感的には WMD = Word2Vec + EMD と説明すると分かり易いでしょう。
実は、コーパスに書籍を使うBookBotでは、応答する場合に 「質問文と意味的に近い文を書籍の中から探す」 必要があるため、このアルゴリズムに着目しました。
WMDに関する「論文」的な話
WMD は２０１５年に発表された論文 "From Word Embeddings To Document Distances" が初出なようで、ごく最近登場したアルゴリズムのようです。
この論文を読むには類似文書検索などの 統計的自然言語処理の基礎知識」 が必要で、特に「テキストを行列に変換する」 ベクトル空間モデル、 単語埋め込み、 単語分散表現など （これ全部同じことを意味する用語のようなんですが） が基礎になっています。
WMDをザッと理解したい場合には 前述の論文の日本語による概要説明が役に立ちます。
この概要説明でも次の定番のオバマ元大統領に関する例文が登場します。
| Sym | Sentance |
|---|---|
| D0 | 'The President greets the press in Chicago.' |
| D1 | 'Obama speaks to the media in Illinois.' |
| D2 | 'The band gave a concert in Japan.' |
この３つの例文の間の意味的距離の計算方法を図示したのが次の図です。
この図を見ると Word2Vecで求めた単語どうしの意味的距離 を 輸送問題の解法で集約して 文の間の意味的距離を計算していることが直感的に理解できます。
WMDをちょっと試してみる
WMD を手軽に試してみるには Python を使うのが一番楽です。
次のブログ記事では Python を対話的に使って WMD を計算する手順を説明しています。
Python3 を使ってこの手順どおりにWMDを計算してみました。
$ python3 Python 3.9.1 (v3.9.1:1e5d33e9b9, Dec 7 2020, 12:10:52) [Clang 6.0 (clang-600.0.57)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> from gensim.models.keyedvectors import KeyedVectors from gensim.models.keyedvectors import KeyedVectors >>> model = KeyedVectors.load_word2vec_format('./GoogleNews-vectors-negative300.bin', binary=True) model = KeyedVectors.load_word2vec_format('./GoogleNews-vectors-negative300.bin', binary=True) >>> model.most_similar(positive=['japanese']) model.most_similar(positive=['japanese']) [('japan', 0.6607722043991089), ('chinese', 0.6502295732498169), ('Japanese', 0.6149078607559204), ('korean', 0.6051568984985352), ('german', 0.5999272465705872), ('american', 0.5906798243522644), ('asian', 0.5839767456054688), ('san', 0.5834755897521973), ('jap', 0.5764404535293579), ('swedish', 0.5720360279083252)] >>> sent1 = 'But other sources close to the sale said Vivendi was keeping the door open to further bids and hoped to see bidders interested in individual assets team up.'.split() sent1 = 'But other sources close to the sale said Vivendi was keeping the door open to further bids and hoped to see bidders interested in individual assets team up.'.split() >>> sent2 = 'But other sources close to the sale said Vivendi was keeping the door open for further bids in the next day or two.'.split() sent2 = 'But other sources close to the sale said Vivendi was keeping the door open for further bids in the next day or two.'.split() >>> distance = model.wmdistance(sent1, sent2) distance = model.wmdistance(sent1, sent2) >>> print(distance) print(distance) 0.8738126733213613 >>> d0 = 'The President greets the press in Chicago.'.split() d0 = 'The President greets the press in Chicago.'.split() >>> d1 = 'Obama speaks to the media in Illinois.'.split() d1 = 'Obama speaks to the media in Illinois.'.split() >>> d2 = 'The band gave a concert in Japan.'.split() d2 = 'The band gave a concert in Japan.'.split() >>> dist01 = model.wmdistance(d0, d1) dist01 = model.wmdistance(d0, d1) >>> dist02 = model.wmdistance(d0, d2) dist02 = model.wmdistance(d0, d2) >>> print(dist01) print(dist01) 1.968269276774589 >>> print(dist02) print(dist02) 2.2929445610887638 >>> quit() quit() $
ここではブログ記事と同じ手順で、 前述の３つの例文の意味的距離も計算しています。 D0-D1 間の距離が 1.968269276774589 に対し、 D0-D2 間の距離は 2.2929445610887638 となりました。 Word2Vecの学習済みデータが異なるので、 前述の図とは値が異なりますが、 D0-D1 間の距離の方が D0-D2 間の距離よりも近いことがわかります。
まとめ
やはり Python は Gensim などパッケージが充実しているので、 今どきの統計的自然言語処理のちょっとした実験には大変便利な言語です。 日本語による解説記事もたくさんありますしね。
でも、さまざまなパッケージが高度にインテグレートされているので、 アルゴリズムの中身を調べようとすると骨が折れると言うのが僕の印象です。 とにかく覚えなければならないことが多いので、正直ウザい（笑） そもそも "Simple is Beautiful" の世代の僕には、 Ｃ言語のような「必要最小限」アプローチがフィットしているようです。
以降の解説では敢えて Python を使わないアプローチで WMD に迫ってみたいと考えてます。
以上
