Word Mover's Distance(1)fastWMD ー 高速化の試み

Word Mover's Distance(1) fastWMD


2021/04/29
藤田昭人


本稿では、論文 "Speeding up Word Mover’s Distance and its variants via properties of distances between embeddings" を眺めながら Word Mover's Distance (WMD) の高速化の試みをザックリと紹介したいと思います。


Word2Vec に思うこと

まずは Word2Vec について… 2013年に論文発表されたWord2Vec。 正直に告白すると当時は 「これ、いったい何に使えるんや?」 と思ったものです*1。 冒頭の論文では、Word2Vec の価値(そして意義)について次のように語られています。

数年前までは、意味的な関係(semantic relations)を取得する適切な方法がなかったので、 意味的な関係はほとんど利用されていませんでした。 それ故、研究者たちはこの問題を軽減する方法として、オントロジーを使用する決心をしましたが、 これはアプリケーションが外部の知識ベースに依存することを意味していました。 このシナリオが変わったのは,Word2Vec とその亜種が登場してからです。

この Word2Vec で分析できるとされる 「意味的な関係」が、 人工知能研究が始まって以来の命題である 「知能」に対する理解を 大きく変えつつあると僕は実感しています。

文章の類似性を測る WMD にとって その文章を構成する単語の類似性を測る Word2Vec は 必須のアルゴリズムですが、 同時に WMD は Word2Vec の有用性を 具体的に提示する重要なアプリケーション (のひとつ)でもあるように思います。


WMDの高速化の試み

実際「よく似た内容の文章を見つける」という 類似文書検索は日常的に役立つ アプリケーションでしょう。 その機能的な核となる文章間の類似度を 高い精度で計測できるWMDアルゴリズムは 需要が高い。それ故に登場した当初から 指摘されていた「分析に時間がかかる」という 課題には多くの研究者がチャレンジして来ました。 昨年(2020年)発表された冒頭の論文は、 WMD の Earth Mover's Distance (EMD) の部分、 すなわち以前紹介した最適輸送問題の解法に着目した高速化手法を扱っています。 参考文献には次の4本の先行研究も掲載されていて、 高速化はWMDが登場した2015年以来 毎年のように成果が発表される、 今もホットな研究領域のように見えます。

年号 論文
2015 From word embeddings to document distances
2017 Linear-complexity relaxed word mover’s distance with gpu acceleration
2018 Word mover’s embedding: From word2vec to document embedding
2019 Linear-complexity data-parallel earth movers distance approximations
2020 'Speeding up Word Mover’s Distance and its variants via properties of distances between embeddings'

そもそも高速化問題とは、 最適輸送問題の解法 が輸送元と輸送先の組み合わせを総あたりで計算することに起因します。 WMDに適用した場合には、その計算量は扱う語数の3乗に比例するそうで、 対象とする文書が大きい過ぎると「いつまで経っても終わらない」計算になります。

この問題は2015年のオリジナルのWMD論文でも指摘されていて、 WMDと同じ精度でもっと高速に計算する手法が提案されました。 冒頭の論文は2015年以来の先行研究を網羅した上で、 独自の手法を提案しています。


fastWMD ー C++ による WMD 実装

僕が、冒頭の論文に注目するもうひとつの理由は、 提案の評価に使われた(先行研究も含む) C++ による WMD 実装が Github で公開されていることです。

github.com

もちろん「実装コードがある」というのはありがたいことですが、 特に fastWMD では先行研究の成果であるアルゴリズムも実装されているので コードレベルで直接比較できることは大変ありがたいです。 ザッと調べてみたところ fastWMD に実装されているアルゴリズムは オリジナルの Word Mover ’s Distance (WMD) に加えて次の3つです。

  • Relaxed Word Mover ’s Distance (RWMD)
  • Linear-Complexity Relaxed Word Mover’s Distance (LC-RWMD)
  • Related Relaxed Word Mover ’s Distance (Rel-RWMD)

RWMD はオリジナルの論文で言及されていた高速化手法で、 最適輸送問題の制約条件をカットすることにより計算量を削減するアイデアです。 LC-RWMD は前処理を追加して計算量が語数に比例するように組み替えた高速化手法で、 並列化が容易になるよう配慮されている(?)反面、計算精度が低下するらしい。 Rel-RWMD は与えられた単語に対して 関連性がある単語グループと関連性がない単語グループに分ける 閾値を決めて計算の枝刈りをする高速化手法で、 Word2Vec では対象となるデータセット内での単語埋め込み間の意味的距離は 次のようなグラフを描く特性を活用しているそうです。

f:id:Akito_Fujita:20210429220216p:plain
Amazonのデータセットに含まれる全ての単語埋め込みから、単語 “cat” までの距離

Word2Vecを説明した記事 では distance コマンドを紹介しましたが、 その表示でグラフを描くとこのようなカーブを描くようですね。 Rel-RWMD の弱点は閾値は単語ごとに異なる可能性があることでしょうか?


まとめ

本稿では冒頭の論文を軸に fastWMD がサポートする WMDの高速化手法についてザックリと紹介しました。 この他にもWMDの高速化手法はたくさん提案されているようですが、 やはり実装がある fastWMD から手を付けるべきでしょう。

僕は対話システムへの応用を考えているので、 必ずしも大規模な文書が想定される訳ではないように思います。 いずれの手法が有効なのか?は対話システムの設計次第でしょう。 個々の高速化手法の詳細が気になるところですが、 以後、まずは fastWMD のビルド方法から説明することにします。

以上



*1:その僕がまさか 記事 を書くとはね。