分散表現の類似度を高速に算出する

はじめに

みなさんこんにちは。
近年自然言語処理界隈では、word2vecをはじめELMoなど、分散表現が非常に人気を博しております。
分散表現とは、すごく雑にいうと、単語（もしくは文）をベクトル化したものを指します。
ただ、そのベクトル化にはいろいろ工夫をされており、似た表現は似たようなベクトルに変換されるといった特徴があります。
例えば、「日本」という単語のベクトルと「ギター」という単語のベクトルは遠く、「日本」という単語ベクトルと「中国」といった単語ベクトルは近くなります。（ベクトル間の「近い」「遠い」はコサイン類似度を用いて計算できます。）
最近は単語だけでなく、文書の分散表現を獲得しようとしている論文が多いです。文書の分散表現の獲得ができると、類似文書の検索ができたりします。

分散表現は便利な一方、高次元かつデータ数が大量にあり、単純に類似度をとるスクリプトを書くだけではものすごく時間がかかることがあります。
本記事では、高次元のベクトルの類似度計算を行う際のベストプラクティスを紹介しようと思います。

結論

ベクトルの計算には、NGTを使えばOK。

ベクトル計算について

ベクトルの類似度計算には、NGTを利用するのがベストだと思いました。
なんといっても、速い＋非常にわかりやすい。さらにApache License2ライセンス。
類似度の計算&探査は下記コードで計算できちゃいます。

from ngt import base as ngt 

# w2vという変数は200次元のベクトルが入っている二重リスト
w2v = ....
dim = 200

index = ngt.Index.create(b"tmp", dimension=dim, distance_type="Cosine")
index.insert(w2v)
index.save()

# queryには200次元のベクトルが入っている想定
query  = [0.5,2.0,1.0,.....]

result = index.search(query, 3)

for o in result :
    print("id is", str(o.id)) 
    print("distance is ", str(o.distance))

ここからは上記コードを解説していきます。
ますはここのコード。

from ngt import base as ngt 

# w2vという変数は200次元のベクトルが入っている二重リスト
w2v = ....
dim = 200

index = ngt.Index.create(b"tmp", dimension=dim, distance_type="Cosine")
index.insert(w2v)
index.save()

ここのコードは、w2vという変数に二重リストで200次元のベクトルが代入されていることとします（今回はベクトルを取得するところは本質ではないので省いています）。最後の3行で/tmpにindexを作成しています。indexを作成する際、distance_typeに引数を与えることで、どういった距離を使うかが選択できます。今回は分散表現なのでコサイン類似度で計算していますが、ユークリッド距離（L2 distance）に設定することも可能です。

そしてあとは検索をするだけです。

query  = [0.5,2.0,1.0,.....]

result = index.search(query, 3)

for o in result :
    print("id is", str(o.id)) 
    print("distance is ", str(o.distance))

index.searchに類似度を計算したいベクトルを入れればOKです。
これで、全ベクトルから類似度を計算し、近いものから3つをソートして算出してくれます。
実際に試してみたのですが、爆速でした。
AIを使って顔画像から「常連さん」を判定しよう！の記事で、人の顔画像を128次元にし、たくさんの顔画像から同一人物の計算をしようとしていますが、NGTを使うとこの計算が爆速でできます。
（画像の場合はユークリッド距離で類似度を算出することが多いので注意）

終わりに

今回はベクトルの類似度を爆速で計算する方法を紹介しました。
機械学習の実装をしていく上で、ベクトル計算の時間は意外と処理時間を占めます。
そんな時はNGTのような素晴らしいツールを利用することも検討してみてはいかがでしょうか。