技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

序文

ベクトル データベースは、今日の大規模モデルのナレッジ ベース検索実践の中核コンポーネントです。次の図は、ナレッジ ベース検索を構築するためのアーキテクチャ図です。

• まず、該当する文書データをベクトル化してベクトル化データベースに埋め込み、次にユーザーのクエリ文をベクトル化クエリに変換し、類似性の高いTOP Nデータをベクトルデータベースから呼び出します。
• 次に、上位 N を並べ替え、そのうちのいくつかを選択し、プロンプトを作成し、LLM を使用して対話的にクエリを実行します。

ベクトル クエリ データとクエリの類似性は、プロンプトの品質に直接影響します。この記事では、市場にある既存のベクトル データベースを簡単に紹介し、転置インデックス、KNN、近似 KNN、積量子化、などのインデックス作成方法について説明します。これらのアルゴリズムの設計思想や手法については、HSNWなどが解説する。

ベクターデータベースの紹介

現在、オープン ソースのベクトル データベースとして人気があるのは、Chroma、Milvus、Weaviate の 3 つです。興味があれば、この記事を読んでください。3 つの主要なオープンソース ベクトル データベース間の競争。
以下は、オープンソースのベクトル データベースの開発の歴史です。

彼らが使用するインデックス作成方法は次のとおりです。

インデックス方式

転置インデックス

10^12 のインデックス データを格納する転置インデックスを使用するデータベースがある場合、データベースにデータを格納するときに、データを分割し、分割された単語に対応する単語を記録します。インデックスとは何ですか。同じ単語が異なる文に出現する可能性があるため、各単語はインデックス セットに対応します。

• 大型モデル——>[…]
• アプリケーション——>[…]
• …

ここで、次のようなクエリがあるとします。 2024 年に大型モデルの応用はどのような進展をもたらすでしょうか?
データベースは、クエリ ステートメントを 3 つのキーワード (大規模モデル、2024 年、開発) に分割します。次に、各単語に対応するインデックスの組み合わせをクエリし、交差部分を見つけます。このクエリ プロセスが呼び出されます。想起。
この時点で、クエリに関連付けられたデータを取得できましたが、これらのデータとクエリ ステートメントの類似度は異なります。これらを並べ替えて TOP N を取得する必要があります。
ただし、テキスト データをインデックスに直接対応付けるこの種のクエリはあまり効率的ではありません。類似性の検索を高速化する方法はありますか?
このとき、データをベクトルに変換してからベクトルを計算するベクトル化検索が登場しました。類似性そして距離2 つの方法で検索します。

KNN検索

KNN 検索は K 最近傍検索と呼ばれ、クエリ文をベクトルに変換し、そのベクトルとデータベース内のベクトルを検索します。最も高い類似性と最も近い距離ベクトルを設定します。

時間計算量は O(N)*O(d) で、d は次元であり、次元データは通常固定されていると仮定します。データベースには 10,000 個のベクトル データが格納されており、次元はすべて 1024 です。 maxSim(q,v)(最も高い類似性)、minDist(q,v)(最も近い) ベクトルの時間計算量は O(10000)*O(1024) です。
この検索方法の利点は、検出されるデータの精度が高いことですが、欠点は時間がかかることです。

近似KNN検索

近似 KNN 探索は、探索空間を点からブロックに変更し、まず最も近いブロックを決定し、次に高速空間内で最も類似度の高い点を見つけることです。下図の左側が KNN 探索であり、エッジは です。 KNN 検索:

各ブロックには中心点が存在します。クエリ点とブロック間の距離を計算するには、クエリ点から各ブロックの中心点までの距離を計算します。

たとえば、上の図のクエリ手順は次のとおりです。

• クエリ点に最も近いブロックは C6 です (C6 の中心点に最も近い)
• 次に、C6 で最も近い距離と最も高い類似性を持つ点をクエリします。

ただし、赤とオレンジのブロックの中心点はクエリ点から遠く離れていますが、ブロック内の点はクエリ点に近いことが肉眼でわかります。このとき、範囲を拡大する必要があります。検索ブロックの:

以下は、最大類似度および最近接距離を求めるためのアルゴリズムの式です。最大類似度 (COS_SIM) は、コサインによって計算されます。最も近い距離には、ヨーロピアン アルゴリズムとマンハッタン アルゴリズムの 2 つのアルゴリズムがあります。ここでは説明しません。 :

積量子化(PQ)

PQ アルゴリズムでは、まずすべてのベクトルを複数の部分空間に分割します。近似 KNN と同様に、各部分空間には中心点 (重心) があります。
次に、元の高次元ベクトルが複数の低次元ベクトルのサブベクトルに分割され、サブベクトルに最も近い中心点がサブベクトルの PQ ID として使用されます。複数の PQ ID で構成され、スペースが大幅に圧縮されます。

たとえば、上図の 1024 次元のベクトルは 4 つの 256 次元のサブベクトルに分割されており、これら 4 つのサブベクトルの最も近い中心点は 50、118、29、47 です。したがって、1024次元のベクトルはV=(50,118,29,47)で表すことができ、そのPQコードも(50,118,29,47)となる。
したがって、PQ アルゴリズムを使用するベクトル データベースには、すべての高次元ベクトルのすべての中心点の情報と PQ コードが保存される必要があります。
ここで、ベクトル データベースから最も類似性の高いベクトルをクエリする必要があるクエリ ステートメントがあるとします。PQ アルゴリズムを使用してクエリを実行するにはどうすればよいでしょうか。

• まず、クエリ ステートメントがクエリ ベクトルに変換されます。
• 次に、クエリ ベクトルは、次の図に示すように、各ベクトルの PQ コードで計算された距離になります。実際には、PQ コードの各中心点で計算された距離が加算されます。

• 次に、上記の方法に従って、各サブベクトルの PQ コードを使用して計算し、最も近いベクトルを計算します。ただし、中心点を使用して計算するこのアルゴリズムには、次の図に示すようにエラーが発生します。

左側は誤差が非常に小さい場合、右側は誤差が比較的大きい場合です。通常、多少の誤差は発生しますが、ほとんどの誤差は比較的小さいです。

キャッシュを使用して計算を高速化する
元のクエリ ベクトルと各サブベクトルの PQ コードが距離計算を必要とする場合、空間計算量は近似 KNN アルゴリズムと大きな違いはありません。このことは意味します。アルゴリズムとは何ですか？圧縮してストレージ容量を減らすためだけですか?
すべてのベクトルが K 個の部分空間に分割され、各部分空間に n 個の点があると仮定します。各部分空間の点から中心点までの距離を事前に計算し、それを 2 次元行列に代入して、ベクトルをクエリします。次の図に示すように、各サブベクトルから中心点までの距離を行列から直接クエリできます。

最後に、各サブベクトルの距離の平方根を加算するだけです。

PQ アルゴリズムと組み合わせた近似 KNN
これら 2 つのアルゴリズムは競合しません。まず近似 KNN を使用してすべてのベクトルを複数の部分空間に分割し、次に対応する部分空間内でクエリ ベクトルを見つけます。
このように、部分空間では PQ アルゴリズムが使用され、計算が高速化されます。

NSWアルゴリズム検索

与えられたベクトル データセット内で、クエリ ベクトルに近い K 個のベクトル (K-Nearest Neighbor、KNN) が特定の測定方法に従って検索されます。ただし、KNN の計算は過剰であるため、通常は近似値のみに注目します。最近隣 (近似最近傍、ANN) 問題。
写真を構成するとき、NSW はランダムに点を選択し、それらを写真に追加します。ポイントが追加されるたびに、m 個のポイントがその最も近い近傍を検索してエッジを追加します。最終的な構造は、次の図に示すように形成されます。

ニューサウスウェールズ州の地図を検索するときは、事前に定義されたエントリ ポイントから開始します。このエントリ ポイントは、近くのいくつかの頂点に接続されています。これらの頂点のどれがクエリ ベクトルに最も近いかを判断し、そこに移動します。

たとえば、A から開始して、A の隣接点 C が P に近づくように更新されます。次に、C の隣接点 D は P に近づきますが、D の隣接点 B と F は近くなくなり、プログラムは停止します (点 D)。

HNSW

グラフの構築は最上位レベルから始まります。グラフに入ると、アルゴリズムはエッジを貪欲に走査して、挿入したベクトル q に最も近い ef 近傍を見つけます (この時点では ef = 1)。
極小値が見つかると、(検索中に行われたのと同じように) 次のレベルに移動します。選択した挿入レイヤーに到達するまで、このプロセスを繰り返します。ここから第二期工事が始まります。
ef 値は、設定した efConstruction パラメーターまで増加します。これは、より多くの最近傍が返されることを意味します。第 2 段階では、これらの最近傍要素が新しく挿入された要素 q へのリンクの候補となり、次の層へのエントリ ポイントとして機能します。
何度も繰り返した結果、リンクを追加するときに考慮すべきパラメーターがさらに 2 つあります。 M_max は頂点が持つことができるリンクの最大数を定義し、M_max0 はレイヤー 0 の頂点の最大接続数を定義します。

HNSW は Hierarchical Navigable Small World の略で、多層グラフです。データベース内のすべてのオブジェクトは、最下位レベル (図ではレベル 0) でキャプチャされます。これらのデータ オブジェクトは非常にうまく接続されています。最下層より上の各層では、より少ないデータ ポイントが表現されます。これらのデータ ポイントは下位レイヤーと一致しますが、各上位レイヤーのポイントは指数関数的に少なくなります。検索クエリがある場合、最も近いデータ ポイントが最上位で見つかります。以下の例では、これはもう 1 つのデータ ポイントにすぎません。次に、さらに 1 レベル深く進み、最上位レベルで見つかった最初のデータ ポイントから最も近いデータ ポイントを見つけ、そこから最も近いデータ ポイントを検索します。最も深いレベルでは、検索クエリに最も近い実際のデータ オブジェクトが見つかります。
HNSW は、最下層のすべてのデータ ポイントではなく、最上位層 (最上位層) のみがキャッシュに保存されるため、非常に高速でメモリ効率の高い類似性検索方法です。上位層によって要求された後、検索クエリに最も近いデータ ポイントのみがロードされるため、少量のメモリのみを予約する必要があります。