生成AI関連では、テキストや画像、音声といった大量の非構造化データを扱います。そして、これらのデータを効率的に格納し、検索するためにはベクトルDBが必要になります。 ベクトルDBで行われる検索は、ほとんどのケースにおいては類似度検索であり、ベクトルDB上の多数のベクトルと入力ベクトルとの間で、類似度の計算を行う形になります。
非常に多くのベクトルが格納されたベクトルDBにおいて、入力ベクトルに類似したベクトルを厳密に求めるのは非常にコストがかかります。そのため、アプローチとしては近似解を求める（Approximate Nearest Neighbor (ANN)）ことが一般的です。そして、それを効率的に行うデータ構造としてHierarchical Navigable Small World (HSNW) というものがあると聞き、少し調べてみました。
論文を含む、後述する参考文献を参考にしていますが、なにぶんこの分野に明るくないもので、間違っているところがあるかもしれません。その際は、お手数ですがコメントいただけると幸いです。
Hierarchical Navigable Small World (HSNW)
HSNWは、2013年に提案されたANNのためのデータ構造です。HSNWでは、レイヤー化されたグラフ構造の中でベクトルを扱い、高次元空間におけるANNを効率的に行えるようになっています。
検索の仕組みをざっくり理解する
ざっくりしたデータ構造は次の図のとおりです。各レイヤのノードはベクトルを表し、各レイヤのエッジはベクトルが類似していることを表します。全ノードがエッジで結ばれているわけではなく、基本的には各ノードごとに類似度が高いノード上位$M_{\text{max}}$個までがエッジで繋がれる構造です。また、レイヤが高いほどノード数が少なく、レイヤが低いほどノード数は多くなります。レイヤ0には全ノードが存在します。
検索アルゴリズムのアイディアはシンプルです。 入力ベクトル$q$の近似最近傍ベクトル$K$個を求める場合、まずは最も高いレイヤ上での最近傍ベクトルを求めます。そして、その最近傍ベクトルを起点として、次のレイヤ上での最近傍ベクトルを求めるという操作を繰り返します。このようにして、最終的にレイヤ0における最近傍ベクトルを求めることができます。
構築の仕組みをざっくり理解する
もちろん、ゼロコストでこの構造を作れるわけでもありません。HSNWを利用する場合は、グラフ構造を作るところにもコストがかかります。
まず、レイヤの数は確率的に決まります。これは、各ノードに対し、どのレイヤに存在すべきかを$l=\lfloor -\ln \left( \text{unif}(0..1)\right) m_{L} \rfloor$で決めることで実現されます1。ノードはレイヤ$l$以下の全てのレイヤに存在することになります。
グラフ構築時、レイヤにおける各ノードは、最大$M_{\text{max}}$個のエッジを持つことになります。各ノードに対して、類似度が高い同一レイヤ内ノードを探し、上位$M_{\text{max}}$個のノードとエッジを張ります。この操作を全ノードに対して繰り返すことで、HSNWの構築が完了します。
計算量
ノード数$N$に対して、検索の計算量は$O(\log N)$、構築の計算量は$O(N \log N)$となります。構築の計算量が検索計算量の$N$倍となるのは、各要素の挿入は基本的に検索操作と同等の処理を行うためです。
パラメータ
HSNWの構築にはいくつかのパラメータがあります。その中でも重要なものは次の通りです。
| パラメータ | 意味 | 影響 |
|---|---|---|
| $m_{L}$ | レイヤ数を操作するパラメータ。$0$に近いとレイヤ数は小さくなり、大きいとレイヤや数が大きくなる | $\frac{1}{\ln(M)}$あたりに設定することで良いクエリ時間になる |
| $M_{\text{max}0}$ | レイヤ0のノードが持てるエッジの最大数 | $2\cdot M$あたりで最適性能。$M$あたりにしてしまうと、recallが大きいときにクエリ時間が大きく悪化する |
| $M$ | 近傍検索で探索するノード数 | 5〜48が推奨。ただし、メモリ使用量は$M$に比例して増大する |
| $ef_{\text{construction}}$ | 構築時に接続するエッジの最大数 | 構築時間とクエリ時間がトレードオフとなる。大きくすると構築時間が伸びる |
まとめ
計算量の問題を解決するためのアイディアがとても興味深かったです。
- 階層構造の導入:
- グラフを複数のレイヤに分割し、上位層ほど疎となる構造を作成
- 各要素が属する最大レイヤー$l$を確率的に選択し、その確率分布を指数関数的に減衰させることにより、レイヤーの総数がデータセットサイズ$N$に対して対数的にスケールする
- 各レイヤーでの接続数の固定:
- 各要素が持つ接続数を一定に保つことで、1レイヤーあたりの探索コストを抑えています。
参考文献
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
- Hierarchical Navigable Small Worlds (HNSW)
- OpenSearch における 10 億規模のユースケースに適した k-NN アルゴリズムの選定
- $\text{unif}(0..1)$は0から1までの一様分布で、$m_{L}$は構築時のパラメータの1つです。↩
