ScaNN:効率的なベクトル類似性検索(1/2)

１．ScaNN:効率的なベクトル類似性検索(1/2)まとめ

・「南北戦争の詩」などの抽象的な検索を実現したい場合、単語を使った類似性は使えない
・機械学習モデルは入力情報をベクトルに変換するのでベクトル間距離で類似性を測れる
・ただし、ベクトル間の距離を計算する事は簡単ではなく計算上の課題が残る

２．ScaNNとは？

以下、ai.googleblog.comより「Announcing ScaNN: Efficient Vector Similarity Search」の意訳です。元記事は2020年7月28日、Philip Sunさんによる投稿です。

Vectorの語源はラテン語の「運ぶ者」の意だそうで、そこからイメージしたアイキャッチ画像のクレジットはPhoto by Rebekah Blocker on Unsplash

文学作品の大規模なデータセットを検索したいとしましょう。

この場合、「タイトル」、「著者」、もしくは「管理番号」などの簡単に機械で索引付け可能な項目を完全一致させる事を必須条件とするのであれば、SQLなどの言語を使用するリレーショナルデータベースが適しています。

ただし、「南北戦争の詩」などのより抽象的な検索をサポートする場合、2つの語句で共通する単語の数を数える等の単純な類似性に頼る事は事はできなくなります。

例えば、「サイエンスフィクション(science fiction)」という検索は、「地球科学(earth science)」よりも「未来(future)」に関連しています。地球科学にはscienceという両者で使われている単語が1つあり、未来には一つもありませんが、未来の方が関連しています。

機械学習(ML:Machine learning)では、言語の持つ意味を理解できるため、従ってこれらの抽象的な検索に答えるコンピュータの能力が大幅に向上しています。最新の機械学習モデルは、文章や画像などの入力を「embedding(訳注：埋め込みと訳される事が多いです)」に変換できます。embeddingとは、入力情報を高次元ベクトルに変換したもので、より類似した入力同士がより近くに配置されるように設計されています。

従って、特定の検索語について、そのembeddingを計算し、検索語のembeddingに最も近いembeddingを持つ文学作品を見つける事で検索を達成できます。

このようにして、MLは、以前は特定することが困難であった抽象的なタスクを、厳密な数学的タスク、すなわちベクトル間の距離を計算する問題に変換しました。

ただし、計算上の課題は残ります。特定の検索語のembeddingについて、データセット内の最も近いembeddingをどのようにすばやく見つけるのでしょうか？embeddingのセットは、網羅的な検索を行うためには大きすぎることが多く、その高次元性により絞り込みが困難になります。

私達のICML 2020の論文「Accelerating Large-Scale Inference with Anisotropic Vector Quantization」では、データセットのベクトルを圧縮して高速に近似距離計算を可能にする手法に焦点を当ててこの問題に対処し、従来の研究と比較して精度を大幅に向上させる新しい圧縮技術を提案します。この手法は、最近オープンソース化されたベクター類似検索ライブラリ(ScaNN)で利用されており、ann-benchmarks.comで測定すると、他のベクター類似検索ライブラリよりも2倍優れています。

ベクトル類似性検索の重要性
embeddingベースの検索は、単純な索引付け可能な属性に頼らないため、意味の理解が必要となる検索に対応できる効果的な手法です。この手法では、機械学習モデルをトレーニングして、検索語とデータベース内の項目を共通のベクトルembedding空間に割り当てます。これにより、embedding同士の距離が項目同士の意味的類似性を表現するようになり、類似した項目同士はベクトル距離もより近くなります。

上図の２つのタワーニューラルネットワークモデルは、特定の種類のembeddingベースの検索であり、検索語とデータベース内の項目が2つのニューラルネットワークによってembedding空間にマッピングされます。この例では、モデルは架空の文学データベースに対する自然言語をつかった検索に応答しています。

この手法で検索に回答するには、システムはまず検索語をembedding空間に割り当てる必要があります。次に、データベース内の全項目のembeddingの中から、検索語のembeddingに最も近いものを見つける必要があります。これは最近傍探索問題(nearest neighbor search problem)と呼ばれます

検索用データベースのembeddingの類似性を定義する最も一般的な方法の1つは、その内積を計算する事です。このタイプの最近傍検索は、最大内積検索(MIPS:Maximum Inner-Product Search)と呼ばれます。

データベースのサイズは数百万または数十億にもなる可能性があるため、MIPSは推論速度の計算上のボトルネックになることが多く、全項目を徹底的に検索、つまり総当たり検索をする事は非現実的です。総当たり検索を実現し且つ大幅に高速化するためには、ある程度の精度を犠牲に近似MIPSアルゴリズムを使用する事が必要になります。