800件から1,000万件へ、Voronoi分割の研究を続けています

ブログを再開するにあたって、3月に公開したPloneサイト実データでのベクトル検索アルゴリズム比較を読み返しました。

当時は約800件のデータを使った実験でした。それから研究を続け、現在は最大1,000万件、5種類以上のEmbeddingモデルを使った検証まで進んでいます。

3月の実験から続いている

3月の記事では、全件に対するコサイン類似度計算を基準として、ITQ-LSHとVoronoi分割による候補の絞り込みを比較しました。その結果、当時のデータではVoronoi分割が有力でした。

もちろん、約800件で得られた結果が、そのまま大規模なデータにも当てはまるとは限りません。データが増えれば、検索精度だけでなく、候補数、計算量、メモリ使用量、前処理の時間など、考えるべき条件も増えていきます。

そこで、Embeddingモデルとデータ規模を変えながら実験を重ねてきました。その過程で、3月に選んだVoronoi分割という方向性には、引き続き研究する価値があると感じています。

この一連の取り組みは、ベクトル検索 ANNプロジェクトとして整理し、LSH Cascade PoCの後継として進めていきます。

当時の実験では、一つのベクトルを一つのVoronoiセルだけに固定せず、二つのセルへ割り当てる A=2 を採用していました。

セルを一つに決めれば、インデックスは単純になります。一方で、セルの境界付近にあるベクトルは、わずかな違いで別の領域に分かれてしまいます。複数のセルとの関係を残しておくことで、その境界をどのように扱えるかが重要になります。

A=2 は小規模な実験のためだけに置いた設定ではなく、その後の研究にもつながる興味深い設計でした。ただし、どのような条件で効果があり、どこに限界があるのかは、引き続き慎重に検証しています。

研究の対象は、Voronoi分割そのものから、IVF系の探索全体へと広がりました。

1,000万件規模になると、候補をどう選ぶかだけでなく、ベクトルをどのような形式で保持し、CPU上でどう計算するかも重要になります。そのため、SQ8をはじめとする量子化方法についても探究を続けています。

さらに、ベクトル同士の距離だけを見るのではなく、ベクトル集合がどのような幾何学的な特徴を持つのかという観点からも検証しています。このテーマの一部は特許出願中の内容とも関係するため、現時点で詳しく説明することはできません。

関連論文を調べると、同じ方向を支持するものだけでなく、異なる結果や慎重な見方もあります。

研究では、都合のよい結果だけを見るわけにはいきません。論文が置いている前提、使用しているデータ、Embeddingモデル、評価方法などを確認し、自分たちの実験条件との違いを考える必要があります。

そうしたさまざまな研究を参照しながら、複数のEmbeddingモデルと大規模なデータを使った検証を続けています。

3月の記事を書いた時点では、その実験がここまで続く研究の入口になるとは、まだ見えていませんでした。

約800件の実データで確かめたことを出発点に、1,000万件規模の検証、IVF系の探索、量子化、ベクトルの幾何学的な特徴へと関心がつながっています。

詳細を公開できる段階にはまだありませんが、小さな実験で得た手応えを次の問いへつなげながら、研究を続けています。