TOPNetwork > ベクトル類似性検索とは(後)

Network

ベクトル類似性検索とは(後)

2021/10/21

Martin Heller InfoWorld

 potifyなどのような音楽サービスには、自分の好きな曲と似た曲をレコメンドしてくれる機能がある。同じような機能を自分で実装するには、どうすればよいだろうか。方法の1つは、個々の楽曲が持つ特徴をいくつかの切り口で数値化し、それぞれの特徴値を組み合わせた「ベクトル」を作成して、データベースにインデックス化して保存しておくというものだ。そのデータベースを検索すれば、目的の曲を表すベクトルと「類似度」が高い曲を見つけ出すことができる。こうして、ベクトル類似性検索を実現できる。

前回から続く)

アルゴリズム

Credit: Thinkstock
Credit: Thinkstock

 一般にベクトル探索では、K近傍法(KNN)のアルゴリズムで優れた結果が得られることが多い。ただし、プロセッサとメモリーの両面で処理の負荷が大きいという課題がある。

 KNNに代わる選択肢としては、近似最近傍探索(ANN)の各種ライブラリがある。例えば、米Facebookが開発したFAISS(Facebook AI Similarity Search)や、米Microsoftが開発したSPTAG(Space Partition Tree and Graph)は、いずれもオープンソース化されている。こうしたANNのライブラリでは、インデックスの削減や処理の効率化のために、直積量子化などの手法が取り入れられている。

 FacebookのFAISSは、互いに類似するマルチメディアドキュメントを検索する目的で開発され、ベクトル数が10億に及ぶ大規模データベースの探索に対応するANNライブラリとして登場した。FAISSでは、ベクトルの前処理、データベースのパーティショニング、ベクトルのエンコーディング(直積量子化)をカスタマイズでき、利用可能なRAMにデータセットを収められる。FAISSの処理能力を評価するために、開発チームは、10億の画像で構成されるDeep1Bデータセットを利用し、CPUとGPUを使った実装でそれぞれテストを行った。すると、GPUでの処理は一般にCPUの5~10倍高速で、米NVIDIAのPascalクラスのGPUでは20倍以上高速という結果が得られた。

↑ページ先頭へ