高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介

はじめに

検索技術の菅原です。

今回は以前にこのTech Blogで紹介された「NGT（Neighborhood Graph and Tree）」という高速な近傍探索を実現するソフトウエアについて紹介します。これまでNGTは商用利用不可なライセンスを採用していましたが、商用・非商用にかかわらず広く利用してもらいたいという考えから、よく知られたOSSラインセンスである「Apache License 2.0」で新たに提供します。なお、これに伴いNGTに関する特許の実施権を無償で提供します。

NGTは特定物体認識のために画像特徴量の類似検索する技術として研究開発されました。また、最近ではDeep Learning（深層学習）が注目され、Deep Learningブームの先駆けとなった画像処理分野で研究された技術がさまざまな分野で応用されています。そこで、私たちもNGTを自然言語処理の分野に適用し、NGTが有用な技術であることをACLというカンファレンスで論文発表しました［1］。今回はその発表内容に触れつつNGTの性能や使い方について簡単にご紹介します。

NGTに関する論文の紹介

NGTは任意の密ベクトルに対して事前に登録した（同次元の）ベクトルから最も距離が近いベクトルの上位数件（k件）を高速に近似k最近傍探索（k-Nearest Neighbor Search）するためのソフトウエアです。代表的なSIFTという画像特徴量により画像は128次元のベクトルで表現します。同様に自然言語処理でも代表的なword2vecというツールにより単語は数百次元のベクトルで表現します。word2vecで得られたベクトルの最近傍探索を行うと意味的に似た語を取り出せることが知られています。例えば「東京」のベクトルで最近傍探索した場合には「大阪」「名古屋」「新宿」の順に対応するベクトルが取り出せます。今回、私たちは単語のベクトルに焦点をあて、以下の条件を変化させながらNGTの性能を調べました。

1. 距離関数
   NGTは理論上、距離定義を満たすものであれば何でも適用できます。NGTのデフォルトではユークリッド距離が使われます。
2. データの次元数
   例えばword2vecのデフォルト値である200次元のベクトルを扱います。
3. データの件数
   例えばWikipediaの単語数である200万件のデータを扱います。
4. 検索時の取得件数
   NGTのデフォルトでは上位20件を取得します。
5. ベクトルを生成するための元データ
   例えばWikipediaのデータをコーパスとして使います。
6. ベクトルを生成するための手法
   例えばword2vecのツールでSkip-gramと階層型Softmaxという手法を使います。

まずは、「1.距離関数」について説明します。word2vecではデフォルトでコサイン類似度が使われますが、コサイン類似度は「距離」ではありません。類似度は高い（大きい）順に取り出したいですが、距離は近い（小さい）順に取り出したくなります。NGTは距離しか扱えないため、コサイン類似度と同じ検索結果を得るために事前にベクトルのノルムが1となるように正規化してユークリッド距離を使う方法か、またはコサイン角度（arccos）を距離とみなして使います。比較対象として正規化せずにユークリッド距離を使う場合も実験しています。この時のNGTの平均検索速度と精度を以下に示します。論文では検索時の探索範囲係数を変化させたより詳細なグラフを載せていますが、簡略化のためにNGTのデフォルトの探索範囲係数0.1の結果のみをお見せします。

ここで書いた精度についてもう少し補足します。NGTの検索結果にある各ベクトルとの距離は近似ではありません。検索結果が近似です。精度0.9は上位10件を取得した時に9件は正しく取得できたが1件は取得できなかったということで、極端な話では最も近いベクトルが検索できなくても、それ以外が検索できていれば精度は0.9です。この実験結果は、Wikipediaのデータからword2vecで200次元にベクトル化した200万件のデータに対し、上位10件のコサイン類似度での最近傍探索を約6ミリ秒で0.987という高い精度をNGTで実現できることを示しています。また、他の結果を比較すると事前にベクトルを正規化することで最も高速化できることが分かります。

同様に、「2.データの次元数」、「3.データの件数」、「4.検索時の取得件数」の結果です。次元数、データ件数、取得件数がそれぞれ小さいほど高速に動作します。また、取得件数を増やすほど精度が上昇することも分かります。

次に、単語ベクトルそのものについて説明します。「5.ベクトルを生成するための元データ」、「6.ベクトルを生成するための手法」を調べるために、さらに3つの単語ベクトルと比較しました。一つ目はword2vecのサイトで公開されているGoogle News datasetの元データから作られた単語ベクトル、二つ目めは比較的に初期の2008年に考案されたDeep Neural Network（DNN）ベースの手法で作られた単語ベクトル、三つ目は比較的によく知られたGloVeという手法で作られた単語ベクトルです。

この結果を見て単語ベクトルが変わるとNGTの性能が変わってしまうように感じた方がいるかもしれません。しかし、実はこれらの単語ベクトルはデータの次元数や件数が違っているため、それぞれの条件をあわせてみる必要があります。興味がある方は論文を読んで見比べて欲しいと思いますが、ここで重要なことは、NGTが高い精度にも関わらず、せいぜい100ミリ秒程度で検索できるという規模感であるということです。その規模感を感じてもらうために、これらの実験結果をご紹介しました。この実験以外にも論文の中では単語ベクトルの応用としてアナロジーと呼ばれる合成ベクトルでの実験やその他の比較手法の比較、実験結果の考察などもありますが今回は割愛します。

これまで紹介した内容と同じような実験はLinux系のサーバーであれば公開しているExperimental softwareという実験プログラムを使うと簡単に試すことができます。実験プログラムではデモのため比較的に小さなデータを使っています。実験プログラムを解凍し、解凍したフォルダーに移動してから以下のコマンドを実行します。

$ make
（NGTや比較手法、データセットの環境構築を行います）
$ ./demo.sh
（各手法のインデックスの作成、検索評価を行うログが出力されます）
+ /usr/local/bin/ngt create -d 50 ./output/ngt_index ./data/train.txt
（NGTのインデックスを作成するコマンドの実行）
+ /usr/local/bin/ngt search -n 10 -e 0.0:0.2:0.025 -o e ./output/ngt_index ./data/test.txt
（NGTのインデックスから検索を行うコマンドの実行）
（NGTの実験結果が出力されます）
NGT evaluation below:
Ground Truth=./output/ground_truth.txt
Target=./output/ngt_result.txt
Epsilon # of Queries    Accuracy    Time(msec)
0   1000    0.914299999999997   0.0276459999999999
0.025   1000    0.941399999999998   0.030872
0.05    1000    0.963599999999998   0.0369539999999999
0.075   1000    0.978899999999998   0.046123
0.1 1000    0.989199999999999   0.0588769999999999
0.125   1000    0.994199999999999   0.075368
0.15    1000    0.9973  0.0966030000000002
0.175   1000    0.9986  0.12478
0.2 1000    0.9992  0.161459

（比較手法の実験結果も出力されます）

上記の場合、探索範囲係数0.1で精度0.989、平均検索速度0.0589ミリ秒でNGTが検索できることを示しています。さらにNGTを使いたい人はNGTのソフトウエア内にあるngtコマンドのcreateやsearchについての説明をお読みください。

おわりに

今回は単語ベクトルに焦点をあて紹介しましたが、最近のDeep Learning界隈（かいわい）では、このようなベクトルを分散表現と呼び、例えば機械翻訳、文書要約、ニュース記事や商品のレコメンド、画像QA、音声認識などで利用できるさまざまな分散表現が作られています。このようなベクトルデータを検索したいといった場合には、ぜひNGTの利用を検討してください。
NGTのダウンロードは以下のURLから行えます。また、GitHubでもコードを公開しているため、積極的なフォーク・プルリクエストをお待ちしています。

https://randd.yahoo.co.jp/jp/softwaredata

参考文献

1. Kohei Sugawara, Hayato Kobayashi, and Masajiro Iwasaki, “On Approximately Searching for Similar Word Embeddings”, In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics （ACL 2016）, pages 2265-2275. Association for Computational Linguistics, 2016.

検索技術 菅原 晃平