はじめに

検索技術の菅原です。

以前にこのTech Blogで紹介されたNGT（Neighborhood Graph and Tree）という高速な近傍探索を実現するソフトウエアのpython用インターフェースが公開されました。pythonは機械学習のライブラリが多く公開されており、より手軽にNGTを組み合わせて使うことができるでしょう。

そこで今回はword2vecのベクトルを近傍探索する実践的な内容を紹介します。word2vecを扱うライブラリとしてgensimを使用します。word2vecやgensimの詳しい説明は省略しますが、分からなくてもpythonの文法を知っていれば理解できると思います。今回使用した環境はMacBook Pro（Sierra）です。後で紹介する実行時間も厳密ではないため参考情報としてお読みください。

インストール

事前準備

以下を利用可能な環境を準備ください。詳しい説明は割愛します。ただし、macOSの場合、System Integrity Protection （SIP）が有効になっていると環境変数（LD_LIBRARY_PATH）が有効にならないこともあるため、pythonはvenvなどのVirtual環境で実行環境を構築することを推奨します。また、コンパイラはclang++よりXcodeに含まれるg++を使ってください。brew install llvmによって入るclang++（5.0.1）でもコンパイルはできましたがライブラリのパスを気をつける必要があります。

• Unix Shell （macOS,CentOSなど）
• git
• cmake
• g++
• python
• pip

NGTのインストール

NGT pythonを使うためには事前にNGT本体のインストールが必要です。

$ git clone https://github.com/yahoojapan/NGT.git
$ mkdir NGT/build
$ cd NGT/build
$ cmake ..
（筆者実行時 $ cmake .. -DCMAKE_CXX_COMPILER=g++-7 ）
$ make
$ make install

NGTの動作確認

以下の様な結果が出力されれば正しくインストールされています。

$ ngt
Usage : ngt command database data
           command : create search remove append export import

NGT pythonライブラリのインストール

$ cd ../python
（$ cd NGT/python）
$ python setup.py sdist
$ pip install dist/ngt-*.tar.gz
$ python -c 'import ngt.base'
（エラーが出なければ正しくインストールされています）

サンプルで使うgensimのインストール

word2vecをpythonから扱えるライブラリをインストールします。

$ pip install gensim
$ python -c 'import gensim'
（エラーが出なければ正しくインストールされています）

word2vecモデルのダウンロード

今回のサンプルでは公開されている日本語のword2vecモデルを利用します。日本語 Wikipedia エンティティベクトルから20170201.tar.bz2というファイルをダウンロードし解凍してください。

word2vecのサンプルプログラム

pythonで以下のようなプログラムを作成し、実行します。全件検索を行った場合は約0.21秒で検索することができました。

from gensim.models.keyedvectors import KeyedVectors
# モデルを読み込みます
word_vectors = KeyedVectors.load_word2vec_format('entity_vector.model.bin', binary=True)

## コサイン類似度を効率的に求めるため正規化したベクトルをあらかじめ作成します
word_vectors.init_sims()
## or メモリが足りない場合は元のデータを置換します
## word_vectors.init_sims(replace=True)

import time

## 検索例 '[ヤマハ]'の単語ベクトルに近い単語を全件検索します
start = time.time()
result = word_vectors.similar_by_word(u'[ヤマハ]', topn=10)
print('search time: {:.2f}[sec]'.format(time.time() - start))
for (word, dist) in result:
    print('{}\t{:.6f}'.format(word, dist))

出力結果

search time: 0.2082[sec]
[ローランド]    0.826786
[コルグ]    0.810291
[河合楽器製作所]    0.803839
ヤマハ    0.800751
[電子オルガン]    0.760175
[イーエスピー]    0.754939
[フェンダー_(楽器メーカー)]    0.731193
[ギブソン_(楽器メーカー)]    0.730971
[電子ピアノ]    0.727939
[シンセサイザー]    0.724792

NGT pythonのインデックス作成サンプルプログラム

上記のプログラムから続いて以下のプログラムを追加します。約15分でインデックスの作成ができました。

from ngt import base as ngt
# numpyはgensimのインストールで使用できます
import numpy

# 空の200次元のインデックス（ディレクトリ名:w2vIndex）を作成します
index = ngt.Index.create(b'w2vIndex', dimension=300)

start = time.time()
# 全件(約100万件)の単語ベクトルを登録します
for vector in word_vectors.syn0:
    # コサイン類似度と同じ結果を得るためにノルム1に正規化したベクトルを挿入します
    normalized_vector = vector / numpy.linalg.norm(vector)
    # NGTはnumpy arrayでなくlist形式を受け付けます
    index.insert_object(normalized_vector.tolist())
print('insert data time:{:.2f}[sec]'.format(time.time() - start))
start = time.time()
# 挿入されたベクトルのインデックスを作成します。1回の挿入毎に呼ぶのは効率が悪いメソッドです
index.build_index()
print('build index time:{:.2f}[sec]'.format(time.time() - start))

start = time.time()
# インデックスをディレクトリに書き込みます
index.save()
print("write index time:{:.2f}[sec]".format(time.time() - start))

# インデックスをクローズします
del index

出力結果

insert data time:71.84[sec]
Processed 100000 time= 6.89426 (sec)
Processed 200000 time= 10.4501 (sec)
Processed 300000 time= 17.0059 (sec)
Processed 400000 time= 25.45 (sec)
Processed 500000 time= 39.4599 (sec)
Processed 600000 time= 58.5939 (sec)
Processed 700000 time= 89.3171 (sec)
Processed 800000 time= 121.726 (sec)
Processed 900000 time= 155.626 (sec)
Processed 1000000 time= 203.595 (sec)
build index time:760.94[sec]
write index time:3.54[sec]

NGT pythonの検索サンプルプログラム

新たにpythonで以下のプログラムを作成してください。約0.01秒で約25倍高速に検索できました。注意点としてNGTのidが1から始まること、登録済みの検索かは区別しないため1番目の結果には自身が含まれる可能性があること、検索のスコアはコサイン類似度（-1から1）でなくユークリッド距離（0から2）であること、検索結果は近似であるため全件検索の結果と一致しないことがあります。今回はデータサイズも小さく全件検索でも問題にならないことが多いですが、件数が大きくなるほど速度の差が顕著になります。

from gensim.models.keyedvectors import KeyedVectors
from ngt import base as ngt
import time
import numpy

# 文字列とベクトル、データのIDを変換するためにモデルを読み込みます
word_vectors = KeyedVectors.load_word2vec_format('entity_vector.model.bin', binary=True)

# 作成済みNGTのインデックスを読み込みます
index = NGT(b'w2vIndex')

# 検索例 '[ヤマハ]'の単語ベクトルに近い単語をNGTで近似検索します
start = time.time()
vector = word_vectors[u'[ヤマハ]']
normalized_vector = vector / numpy.linalg.norm(vector)
# kは最大検索件数です。自身が含まれるため10件取得するために11件を指定します
result = index.search(norm_vec.tolist(), k=11)
print('search time: {:.4f}[sec]'.format(time.time() - start))
for data in result:
    # NGTのIDは1から、gensimは0から始まるため-1をします
    # distanceはコサイン類似度でなくユークリッド距離です
    print('{}\t{:.6f}'.format(word_vectors.index2word[data.id-1], data.distance))

del index

出力結果

search time: 0.0082[sec]
[ヤマハ]    0.000000
[ローランド]    0.588581
[コルグ]    0.615969
[河合楽器製作所]    0.626356
ヤマハ    0.631267
[電子オルガン]    0.692567
[イーエスピー]    0.700087
[フェンダー_(楽器メーカー)]    0.733222
[ギブソン_(楽器メーカー)]    0.733525
[電子ピアノ]    0.737646
[シンセサイザー]    0.741900

おわりに

pythonでNGTが簡単に利用できることを感じられましたでしょうか。具体的な利用方法としては今回の様なアプリケーション以外にも機械学習の学習時のバリデーションやさらに言えばRNNで作成された中間表現の分析などにも活用ができそうです。また、機械学習も含めインデックスを作るところまではpythonで実装して、インデックスを配布しサーバーを作成、アプリケーションからはサーバー経由で検索するといった応用的な使い方もできます。密ベクトルの検索に時間がかかっている場合はぜひNGTの利用を検討してください。

参考情報

1. 高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開
2. 高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介

検索技術 菅原 晃平

Yahoo! JAPANでは情報技術を駆使して人々や社会の課題を一緒に解決していける方を募集しています。詳しくは採用情報をご覧ください。