HNSW（Hierarchical Navigable Small World）への序章

『HNSW（ヒエラルキカル・ナビゲーブル・スモール・ワールド）への序章』

イントロダクション

AIの革新は驚異的なスピードで進んでいます。その革新のひとつがベクトル検索エンジンです。では、これらの検索エンジンとは何でしょうか？簡単に言えば、大規模な言語モデル(LLM)を訓練するためのもので、大量のデータセットを徹底的に調査し、関連する情報を選び出します。さて、このインデックス付けは、ベクトルデータベース内でさまざまな方法で行われますが、その中でも階層的ナビゲーション可能な小世界(HNSW)はパフォーマンスと拡張性に優れています。主要なベクトルストアはすべて、HNSWをインデックスメソッドとして提供しています。HNSWは高速で効率的、堅牢かつ信頼性があります。今回の記事では、HNSWの内部機能を解説し、なぜそれほど速いのかについて学びます。

学習目標

埋め込みとベクトルデータベースの理解。
ベクトルデータベースにおけるインデックスの異なる方法について知る。
HNSWとは何か、その仕組みを学ぶ。
HNSWlib、ヘッダのみのHNSW実装を理解する。

この記事は、Data Science Blogathonの一部として公開されました。

埋め込みとは何ですか？

埋め込みとは、データ（テキスト、画像）のベクトル表現です。

意味的に関連するデータはベクトル空間で近接しており、異なるデータは離れています。言い換えれば、Messiやサッカーの埋め込みは埋め込み空間で近くに位置し、サッカーやJoe Bidenの埋め込みは埋め込み空間で遠くに位置しています。

ベクトルの長さは数百から数千以上に及ぶことがあります。そのため、格納、クエリ、検索が困難です。しかし、リトリーバル強化生成（RAG）ベースのアプリケーションでは、データの埋め込みの高速な検索とクエリが必要です。ここでベクトルデータベースが登場します。

ベクトルデータベースとは何ですか？

従来のデータベースが構造化および非構造化データを格納することを目指しているのと同様に、ベクトルデータベースは高次元ベクトルの埋め込みを格納し、検索およびクエリを行います。ユーザーフレンドリーなインターフェースを提供し、埋め込みと関連データを操作できるようにします。ベクトルデータベースは基本的には従来のデータベースとは異なりません。ベクトルデータベースはシリアライズされた埋め込みを格納するために従来のデータベースを使用します。例えば、Chromaはメモリ内ストレージとしてSQLiteを使用し、Pgvectorは埋め込みと関連するメタデータを格納するためにPostgresデータベースを使用します。従来のデータベースとベクトルデータベースの違いは、基礎となるインデックスアルゴリズムです。

ベクトルデータベースでのインデックス作成

インデックス作成とは、最も近い近傍ベクトルの効率的なクエリを提供するために、高次元ベクトルを組織化するプロセスを指します。

これは任意のベクトルデータベースの構築において最も重要な部分です。これらのインデックスは高次元埋め込みの高速かつ効率的なクエリを可能にします。ベクトルインデックスを作成するためには、次のような複数のインデックス作成方法があります。

線形検索アルゴリズム（フラットインデックス）：これは線形検索アルゴリズムであり、データベースに格納されているすべてのベクトルとクエリベクトルを比較します。これは最も単純な方法であり、小規模なデータセットではうまく動作します。
クラスタベースアルゴリズム（IVF）：反転ファイルはクラスタベースのインデックス技術です。k-meansクラスタリングを使用してすべてのベクトルをクラスタ化します。クエリベクトルが提供されると、クエリベクトルと各クラスタの重心の距離を計算します。そして、クエリベクトルに最も近い重心を持つクラスタで最近傍ベクトルを検索します。これにより、クエリ時間が大幅に短縮されます。
量子化（スカラーおよびプロダクト量子化）：量子化技術は、大規模な埋め込みのメモリフットプリントを削減するために、精度を低下させる方法です。
グラフベース（HNSW）：最も一般的なインデックス作成方法です。階層的なグラフアーキテクチャを使用してベクトルをインデックスします。そして、これについても探索します。

HNSWの理解

大規模な言語モデル（LLMs）はますます人気が高まっており、多くの組織が製品スタックに実装したいと考えています。しかし、その際には課題があります。LLMsには限られたコンテキストウィンドウがあります。コンテキストウィンドウとは、AIモデルが受け入れることのできるトークンの数です。例えば、AIモデルのコンテキスト長は4096です。ここでベクトル検索データベースが輝くのです。LLMに全ての情報を与えるのではなく、最も関連性の高い部分を見つけ出して正確な結果を得るのです。

今、ベクトルデータベースでインデックス化するためのさまざまな方法の中で、HNSWが最も堅牢でスケーラブルです。これにより、最も広く使用されているインデックス化方法となっています。HNSWは、スキップリストとナビゲーション可能な小世界という2つのアルゴリズムを組み合わせて形成されます。HNSWを理解するためには、これらのアルゴリズムを知る必要があります。では、さっそく見ていきましょう。

スキップリスト

その名前からもわかるように、スキップリストはリンクリストデータ構造を基にしており、リンクリストデータ構造の高速な代替手段として1990年にDavid Pughによって発明されました。

なぜスキップリストが必要なのでしょうか？リンクリストはO(n)の検索時間の複雑さを持っています。これは、実世界の使用例では実行速度が重要な場合には理想的ではありません。そのため、より効率的なリンクリストアルゴリズムが必要な場合があるのです。

スキップリストの期待される時間の複雑性はO(log n)です。リンクリストよりもランダムアクセスでのパフォーマンスが優れています。各層に複数のノードを持つ階層構造を持つため、最悪の場合の空間の複雑性はO(n log n)となります。ここで、nは最下層のノードの数です。

スキップリストはどのように動作するのでしょうか？

スキップリストは、トップレベルに最も長いリンクを持つ階層化されたリンクアーキテクチャを維持します。これは、下の層に移動するにつれて指数的に減少していきます。

上記の図で、最下層は完全なリンクリストです。上に向かって移動すると、各層でノードの数は半減していきます。この構造はスキップリストと呼ばれており、上位の層ではトラバーサル中にノードをスキップすることができます。

以下の例を考えてみましょう。

kを検索する場合:

k = ターゲット要素であれば
k >= 右に移動
k < 移動して下に移動

左上の角から始めて、kを見つけるか、kより小さい数値を見つけるまで右に移動します。下の層に降りて、kにたどり着くまでプロセスを続けます。各レベルでアイテムの半分をスキップするため、検索の複雑性はO(log n)です。

ランダムアクセスは速いですが、挿入と削除は遅くなります。複数の層での更新と削除のために追加のオーバーヘッドが発生するからです。

挿入時には、ボトムリストから開始し、ノードを適切な位置に追加します。スキップリストは階層的な構造を維持しているため、ノードが上位レベルに表示されるかどうかを確認する必要があります。このプロセスはコイントスのようなランダム性があります。ノードが直ちに上位レベルに表示される確率は0.5です。理想的なスキップリストでは、レベル1のノード数は約n/2、レベル2ではn/4となります。ここで、nは最下層または完全なリンクリストのノード数です。

以下の例を考えてみましょう。

挿入のための適切な場所を見つけ、ノードをボトムレベルに挿入します。次に、ノードが上位レベルに表示されるかどうかをランダムなバイナリの結果（表または裏）に基づいて決定します。理想的なスキップリストでは、各レベルにノードがバランスよく分布するでしょう。

削除も同様に行われます。対象の数値を見つけてノードを削除します。要素が上位のレベルにある場合は、削除し、リンクリストを更新します。

ナビゲーション可能な小世界（NSW）

ナビゲーション可能な小世界は、近似最近傍探索のためのグラフベースのアルゴリズムです。グラフ内のデータポイントはノードと呼ばれます。各ノードは、互いに近い固定された接続にリンクされています。

これは貪欲アルゴリズムです。グラフ内の事前定義されたポイントから始まり、ターゲットノードに近いノードを選択します。ノード間の距離は、ユークリッド距離またはコサイン類似度で測定することができます。このプロセスは、ターゲットノードの最近傍ノードに到達するまで繰り返されます。

ナビゲーション可能な小世界アルゴリズムは非常に効率的で簡単に展開できます。数百から数千のデータセットに適しています。それ以上の大きなデータセットでは、性能が低下する傾向があります。最近傍のノードを見つけるためにローカル情報だけを使用するため、事前終了することがあります。

挿入時には、最も近い隣接ノードを見つけ、それらをノードxに接続するためにグラフをトラバースします。

ベクトルデータベースでは、数百万個以上の埋め込みデータを扱う必要があります。そのため、スケーラビリティが優れ、検索性能が向上するより優れたアルゴリズムが必要です。NSWは小さなデータセットでは十分なパフォーマンスを発揮しますが、数億または数十億のデータポイントを処理するためにさらに良いアルゴリズムが必要です。これがHNSWが登場する場所です。

ヒエラルキカルナビタブルスモールワールド（HNSW）

HNSWはSkip Listsの階層アーキテクチャを組み込むことにより、NSWの拡張です。これにより、NSWのスケーラビリティのボトルネックが解消されます。Skip Listsと同様に、HNSWは連結リストの代わりにNSWの多層構造を作成します。Skip Listsと同様に、最上位の層は最も長い接続を持つデータポイントが少なくなります。要素の数は階層を下に移動するにつれて増加します。最も下のレベルでは、すべてのデータポイントを持っています。Skip Listsと同様に、階層を上に移動するにつれて要素の存在確率が指数的に低くなります。

では、HNSWではどのように検索するのでしょうか？

HNSWでの検索

まず、Skip ListとNSWを思い出してください。Skip Listでは、最上位のレイヤーから始めますが、NSWでは事前に定義されたポイントから始めます。HNSWでは、階層の最上位から事前に定義されたポイントから始め、グラフを貪欲にトラバースしてそのレイヤーのターゲットデータポイントに最も近い要素を見つけます。最も近いノードに到達したら、下のレイヤーに降りてプロセスを繰り返し、ターゲットノードの「K」個の最近傍ノードが見つかるまで続けます。以下の画像を参照してください。

HNSWでの挿入と削除

HNSWでの挿入はSkip Listsと同じ原則に従います。レイヤーをトラバースして、要素の最近傍ノードを見つけます。その後、下に移動して同じプロセスを繰り返し、ボトムレイヤーの最近傍ノードを見つけます。

次のタスクは、挿入された要素への双方向リンクを決定することです。通常、あらかじめ定義されたパラメータmによって決定されます。m個の最近傍ノードを挿入されたノードに接続します。これは、挿入されたノードへの接続を決定する方法の1つです。他のヒューリスティックも使用できます。たとえば、同じ領域の最近傍ノードに接続するだけでなく、挿入されたノードを最近の領域の最も近いノードにも接続して、よりよく接続されたグラフを形成します。

スキップリストと同様に、ノードが上位のレイヤーに表示される確率はランダムに決定されます。その関数はfloor(-ln(rand(0, 1)))です。ここで、rand(0, 1)は(0, 1]の一様分布からサンプリングされたランダムな数値です。

削除は類似のアプローチを取ります。トップレイヤーから始めて、ボトムレイヤーまでターゲットが表示されるたびに削除します。

HNSWでの複雑さ

HNSWでの検索、挿入、削除の時間複雑度は、アーキテクチャの高さ、ノードごとの近隣ノードの数、および距離指標など、複数の要素に依存します。しかし、平均的には、検索、挿入、削除にはO(log n)の時間複雑度があります。HNSWの構築は費用がかかる場合があります。O(log n)の複雑さでn個のノードを挿入する必要があります。したがって、グラフの構築全体の時間複雑度はO(n log n)となります。

ベクトルデータベースは数億の埋め込みを処理できるように構築されます。そのような量のデータをインデックス付けするには、非常に効率的で堅牢かつスケーラブルなアルゴリズムが必要です。HNSWはすべての要件を満たします。

HNSWのデメリット

HNSWでは検索、挿入、削除が速くなりますが、HNSWを選択する前に知っておく必要があるいくつかのトレードオフがあります。以下に、HNSWを実装する前に心に留めておくべきいくつかのことを挙げます。

高いメモリフットプリント：HNSWは埋め込みの階層構造を維持するため、NSWなどのアルゴリズムと比較してメモリ消費量が大幅に増加します。これはリソース制約のあるデバイスにとって問題となる場合があります。
パラメータのチューニング：HNSWには異なる調整可能なパラメータがあります。パフォーマンスを向上させるためには慎重なパラメータのチューニングが必要です。
難易度：HNSWをゼロから実装するのは難しいことです。ほとんどのベクトルデータベースは、FAISSやHNSWlibなど、信頼できるプレビルドソリューションを使用します。

HNSWlib：ヘッダーのみのHNSW実装

HNSWlibは、Pythonバインディングを備えたHNSWアルゴリズムのヘッダーのみのC++実装です。これはHNSWの著者であるYury Malkovによって書かれました。これはアルゴリズムの基本的な実装です。

それでは、始めましょう。

あなたはPythonのパッケージマネージャーを使ってHNSWlibをインストールすることができます。

pip install hnswlib

HNSW indexを宣言して初期化します。

import hnswlib
import numpy as np
import pickle

dim = 16
num_elements = 100
hnsw_index = hnswlib.Index(space='l2', dim=dim) # Indexの宣言
hnsw_index.init_index(max_elements=num_elements, ef_construction=200, M=16)

spaceパラメーターはノード間の距離を計算するために使用される距離尺度です。Pythonの実装では、平方L2、Cosine、および内積をサポートしています。
dimパラメーターは埋め込みベクトルの次元です。
init_indexメソッドはインデックスを初期化します。
ef_constructionは作成時間と精度のトレードオフを定義します。
Mはノードの挿入中に作成される双方向リンクの数です。

インデックスを作成したので、いくつかのベクトルを追加しましょう。

data1 = np.float32(np.random.random((num_elements, dim)))
ids1 = np.arange(num_elements)
data2 = np.float32(np.random.random((100, dim)))
ids2 = np.arange(100)
data3 = np.float32(np.random.random((100, dim)))
ids3 = np.arange(100)

hnsw_index.add_items(data1, ids1)
hnsw_index.add_items(data2, ids2)
hnsw_index.set_ef(50) # 問い合わせ時間の速度/精度のトレードオフを設定
hnsw_index.set_num_threads(4) # バッチ構築時のスレッド数を設定

それでは、kの近似最近傍をクエリする方法を見てみましょう。

labels, distances = p.knn_query(data, k=1)

pickleを使用してインデックスオブジェクトをシリアライズします。

p_cp = pickle.loads(pickle.dumps(hnsw_index))

要素の削除。

for id in ids2:
    hnsw_index.mark_deleted(id)

これにより、インデックスから最後の100の要素が解放されます。必要な場合、削除された要素のメモリを再利用することもできます。

hnsw_index.add_items(data3, labels3, replace_deleted=True)

結論

HNSWは、ベクトル検索方法の開発において現在最も重要なアルゴリズムの一つです。主要なベクトルデータベース全体で使用されている主要なインデックスアルゴリズムです。この記事を通じてHNSWの動作を理解していただければ幸いです。AIの進化とともに、より大きく複雑な学習モデルの開発が進むため、HNSWの使用とその応用の重要性は増していくでしょう。

重要ポイント

ベクトルデータベースは高次元ベクトル埋め込みを保存するための専用のデータストアです。
埋め込みのインデックス作成により、ベクトルストアは埋め込みのクエリ、挿入、削除を処理することができます。
IVF、Annoy、Quantization、HNSWなど、ベクトルをインデックスするためのさまざまな方法があります。
HNSWは2つのアルゴリズムの組み合わせです。スキップリストとNavigable Small World（NSW）です。

よくある質問

この記事に掲載されているメディアはAnalytics Vidhyaの所有ではありません。著者の裁量により使用されています。

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!

AlgorithmblogathondatabasesembeddingsGuideHNSWIndexingLarge Language Models

Was this article helpful?

93 out of 132 found this helpful