ベクトルデータベースとは？

无事小狗仙
2024-10-16 13:51
オリジナル
閲覧 593 回

数据

一、大規模モデル事業の全工程

AIクラスターの構築：計算・通信・ストレージの整備
大規模モデルのデータ：大規模モデルのデータセット、データ処理、ベクトルデータベース
大規模モデルのアルゴリズム：従来のNLPから事前学習済みLLMへ
大規模モデルの学習：大規模モデル学習の一般的なアルゴリズム手法と安定性の分析
分散並列：モデル並列、データ並列、オプティマイザー並列など
大規模モデルのファインチューニング：全パラメーター調整、少数パラメーター調整、指示ファインチューニングのアルゴリズム
大規模モデルの推論：量子化による圧縮、長いシーケンスに対応する推論の拡張、キャッシュ手法
大規模モデルの評価：NLP下流タスク、CV下流タスク、評価方法
大規模モデルのエージェント：RLHF のプロセス、エージェント、生涯学習

二、ベクトル

犬に詳しい人は、すぐに犬種を見分けることができます。それができるのは、例えば体の大きさなど、さまざまな観点から特徴を観察しているからです。
座標軸を一つ使って体の大きさという特徴を表すと、これらの犬はそれぞれ異なる座標に位置します。しかし、体格という一つの特徴だけでは不十分で、体格が非常に近い犬もいます。
さらに毛の長さなどの特徴を観察し、もう一つ座標軸を作ると、大きさが同じという特徴を持つ犬の一部を区別できます
ただし、まだ一部は重なっているため、鼻の長さなど、さらに多くの観点から観察を続ける必要があります。
目の大きさなど、さらに多くの次元を加えることもできます。四次元空間に図を描くことはできませんが、座標点の数値として表すのは簡単で、後ろに追加していくだけです。
犬一匹の特徴は、より多くの観点、言い換えれば次元から観察できます。たとえば脚の太さ、毛の巻き具合、さらには従順さや作業への適性といった抽象的な観点もあります。使う次元が多いほど、犬を区別する能力は高まります。同時に、座標点が存在する空間の次元も高くなります。
犬だけでなく、実際にはほとんどあらゆるものをこのように表現できます。具体的なものでも、抽象的な喜怒哀楽や、悲しみと喜び、別れと出会いでも構いません。異なるものは、それぞれの特徴次元において異なる現れ方、つまり異なる数値を持つため、最終的には高次元の特徴空間内の1つの座標点に対応します。ただし、より広い範囲でものをうまく区別するには、さらに多くの特徴次元が必要になる場合があります。数百、数千、場合によっては1万以上になるかもしれません。
ただし、三次元を超える図は描けないため、二次元座標を使って説明する。
概念的に近い点ほど空間内で密集し、概念的に大きく異なる点ほど距離が遠くなることが分かります。さらに、座標の原点を始点とし、これらの座標点を終点とすれば、方向と大きさを持つベクトルになります。

画像をベクトル化し、類似するベクトルを検索することで、画像による画像検索機能を実現する
動画をベクトル化すれば、類似するベクトルを検索することで、類似動画の推薦を実現できます
商品をベクトル化すれば、類似するベクトルを検索することで、ユーザーが現在閲覧している商品に関連する商品を推薦できる
テキストをベクトル化すれば、インテリジェントな質問応答システムで、ユーザーの現在の質問に基づいて、すでに解決済みの類似した質問を見つけ、参考にできます

三、ベクトルデータベース

AI の到来とともに、ベクトルは重要なデータ形式になるだろう。従来のデータベースはベクトルデータの保存や検索に適していないため、これらの問題を扱う専用設計のデータベースが必要になる。これは将来、データ層のインフラになるかもしれない。データテーブルを保存し、クエリ文で正確に検索する従来のデータベースとは異なり、ベクトルデータベースはベクトルデータを保存する。検索では、クエリベクトルに最も類似したベクトルをデータベースからいくつか探し出すため、一定の曖昧さがある。

1、ベクトル検索

ベクトルデータの主な用途の一つは、クエリベクトルが与えられたときに、多数のベクトルの中から最もよく似たベクトルをいくつか見つけることです。これがいわゆる最近傍問題で、それを実現するものを最近傍アルゴリズムと呼びます。最も思いつきやすい方法の一つは総当たり探索でしょう。すべてのベクトルとクエリベクトルの類似度を順番に比較し、類似度が最も高いものをいくつか選びます。二つのベクトルの類似度を比較する具体的な方法は数多くあり、ユークリッド距離とコサイン類似度。

ユークリッド距離とは、二つのベクトル間の直線距離を計算したものです。二次元座標系で二つのベクトルpとqがあるとすると、ユークリッド距離はpとqを結ぶ直線の長さを計算したものです。三次元座標系では、各ベクトルがx、y、zの三つの座標を持ち、公式に従って任意の二点間の距離を計算します。n次元座標系では、100個の座標があり、公式に従って任意の二点間の距離を計算します。距離が短いほど、この二つのベクトルはある次元での類似性が高いことを示します
もう一つの方法がコサイン類似度です。距離のほかに、ベクトル間の角度によって、それらの関係を表すこともできます。二次元座標系では、角度が小さいほど、二つのベクトルの関連性が高いことを示します。数式を使えば、任意の二つのベクトル間のコサイン類似度を計算できます。三次元座標系でも、同じ原理で任意の二つのベクトル間の角度とコサイン類似度を計算できます。

一方、ベクトルデータが多すぎると、このような何の工夫もない総当たりの方法では、検索に非常に長い時間がかかる。ただし、実際にすべてのベクトルを比較しているため、検索の品質は確かに完璧だ。したがって、データベース内のデータ規模が比較的小さく、全ベクトルを走査する時間を許容できるなら、これもよい方法の一つと言える。しかし、実際の用途ではデータ規模があまり小さくないことが多いため、最適化する方法を見つける必要がある。

2、ベクトルインデックス

先ほどベクトルデータベースの検索原理について説明しましたが、実際にベクトルデータベースで類似度を照合する際は、すべてを数式どおりに計算するわけにはいきません。通常、ベクトルデータベースはデータ量が多く、次元数も高いからです。数式を使って二つの1000次元ベクトル間の類似度を計算すると、計算量が比較的大きく、CPUに非常に高い計算負荷がかかります。では、一億個のベクトルがあり、そのすべてについて計算するとしたら、時間も計算コストもさらに増大します。そこで、ここではベクトルインデックスという概念を導入します。
ベクトルインデックスはリレーショナルデータベースのインデックスと似ていますが、一つ違いがあります。ベクトルデータベースでベクトルインデックスから得られるのは近似結果であり、100%正確な結果ではありません。ベクトルインデックスが表すのは、類似度の高低です。そのため、これを近似最近傍探索（ANS）と呼びます。 ベクトルインデックスがなければ、あるベクトルとの類似度を調べる処理は、リレーショナルデータベースの全表走査に似ています。ただし、全表走査に加えてさらに計算が必要になるため、コストはリレーショナルデータベースの全表走査よりもはるかに高くなります。
実装方式に応じて、ANNSベクトルインデックスは大きく4つに分類できます：

木構造に基づくインデックス
グラフに基づくインデックス
ハッシュベースのインデックス
量子化に基づくインデックス

1、木に基づく手法

木構造に基づく手法の主な考え方は、二分探索木のようにデータを分割し、探索時の探索空間を狭めることで高速な検索を実現することである。ただし、この手法は高次元空間には適していない。木構造に基づく主な手法には、KDTree（K-Dimensional Tree）とAnnoy（Approximate Nearest Neighbors Oh Yeah）がある。
1.1 KDTree
KDTree の構築も、再帰的に分割する考え方に基づいています。まず分散が最大の次元を選び、その次元における全データの中央値を分割点として、超直方体の領域を二つの部分領域に分割します。中央値より小さいものを左側に、中央値より小さいものを右側に分け、すべてのデータの分割が完了するまで、左右の部分木を再帰的に構築します。

KDTreeに基づく検索の流れ：
1、検索データpと現在のノードの分割次元dについて、次元dにおけるデータpの座標値とノードの値の大小を判定し、大きければ左の子ノードへ、小さければ右の子ノードへ進みます；
2、葉ノードに到達するまで走査し、訪問済みとマークして、葉ノードまでの距離を最短距離として算出する；
3、葉ノードでバックトラックを行い、そのたびにpと、親ノードの未訪問の分岐との距離を判定します。
a)その分岐ノードとpの距離が現在の最短距離より大きければ、根ノードに至るまで上へバックトラックを続けます；
b)その分岐ノードとpとの距離が現在の最短距離より小さい場合、その分岐を使い、ステップ1とステップ2を葉ノードまで繰り返し、葉とQとの最短距離を更新します。

1.2Annoy
Annoyは超平面を使って空間を分割します。KMeans(k=2)を利用して2つのクラスタ中心を求め、その中心を結ぶ線に垂直な平面を分割用の超平面とします。各部分空間のデータ数が指定されたしきい値を下回るまで、反復を続けます。

この空間内の任意の点を検索するには、根から二分木をたどります。各中間ノード（上の木にある小さな四角）は超平面を定義しているため、その超平面に基づいて、次に左の子ノードと右の子ノードのどちらへ進むかを判断できます。一つの点の検索は、木の高さに相当する対数時間で完了できます。

長所：低次元データの精度が比較的高い短所：データの複雑さを十分に捉えられず、高次元データの精度が低い

2、グラフに基づく手法

グラフに基づく手法は、主にグラフというデータ構造を使い、隣接ノード間の接続性を利用して高速な経路を構築し、問題をグラフの走査に置き換えるものです。探索範囲をすばやく絞り込み、検索を高速化できます。ただし、グラフは比較的複雑なデータ構造であり、検索速度を極限まで高めるため、通常はグラフ全体をメモリに読み込みます。そのためメモリ使用量は非常に大きくなりますが、検索が速く、再現率も高いという特徴があります。

現在よく使われているグラフ探索アルゴリズムは主にHNSW（Hierarchical Navigating Small World）で、NSW（Navigating Small World）はその先行アルゴリズムに当たるため、こちらも理解しておく必要があります。
2.1 NSW
NSWは単純なグラフ構築法を基礎に、次の規則を追加しています。すべてのノードに隣接ノードが存在すること、隣接ノード間に辺があること、近傍ノードの数をユーザーが指定するハイパーパラメーターとすることです。主に、単純なグラフ構築法のいくつかの制約を解消するために用いられます。
NSW のグラフ構築過程：
新しいノードを挿入する際は、まず新しいノードに最も近いm個のノードを探し、新しいノードをそのm個のノードに接続する。
NSWの検索過程：
クエリデータqについて、グラフからランダムにentry pointノードとその隣接ノードを探し、entry pointおよび隣接ノードとpとの距離を計算します。pとの距離がpとentry pointとの距離より短い隣接ノードがあれば、最短距離の点を設定します。これを、すべての隣接ノードとqueryとの距離が、そのpointとqueryとの距離より長くなるpointが見つかるまで繰り返します。
上の図のように、構築済みの近傍グラフから緑色のノードqueryに最も近いノードを検索するには、ランダムに選んだentry pointsから開始する。まず赤色のlong-linkを通ってqueryの近くのノードにすばやく到達し、その後、黒色のshort-linkを通って条件を満たす点を見つける。
NSWも近似計算の一種であり、真の最近傍であることは保証できません。先に挿入された点は冗長な辺が多く、高速道路を形成する可能性が高くなります。後から挿入された点ほど、高速道路を持つ可能性は低くなります。
2.1 HNSW
HNSW は NSW に基づく改良方式で、主にスキップリストの考え方を利用し、階層化によって実現します。各層がそれぞれ一つの NSW になっているため、階層型 NSW 方式とも呼べます。上の層ほどノードはまばらで、ノード間の距離は遠くなります。下の層に進むほどノードが増え、接続も増加し、平均距離は近くなります。

長所：高次元データから類似する近傍点を見つけ、検索性能を向上できます。短所：グラフの構築方法が複雑で、メモリ効率に影響します。

3、ハッシュに基づく方法

ハッシュに基づく手法は主に、類似度の高いデータはハッシュ値も似るというハッシュ関数の特性を利用します。ハッシュ関数は高次元データを低次元データに変換でき、構築効率を大幅に向上させます。ただし、ハッシュ関数には別の制約もあります。ハッシュ値が似ているデータが必ずしも似ているとは限らないため、この手法の再現率はそれほど高くありません。ハッシュに基づく手法の代表は LSH（Locality-Sensitive Hashing、局所性鋭敏型ハッシュ）です。2つのベクトルが似ているなら、そのハッシュ値も似ていると仮定します。ハッシュ関数を使い、似たベクトルを同じバケットにマッピングします。検索時には、まずクエリベクトルに最も似たバケットを見つけ、次にそのバケット内のデータを検索・計算して、最も似た topk 件を求めます。
LSH（局所性鋭敏型 hash）も空間分割に基づく方式の一つです。その実現方法は下図のとおりで、ランダムに一本の直線を生成し、その線の両側を正側と負側に分けます。あるベクトルがこの線の正側にあれば1、負側にあれば0とします。続いてもう一本の直線をランダムに生成し、同様に正側を1、負側を0とします；このような直線を複数生成することで、各ベクトルについて4個の0または1が計算され、それぞれ4ビットの二進符号が得られます。では、この4個の二進符号がどの程度似ているかを見てみましょう。

長所：大規模データに拡張してもデータ処理が非常に高速、短所：正確性は並程度

5、量子化(Quantized)に基づくインデックス

5.1、クラスタリング
クエリベクトルに対して大まかな検索範囲を定め、その範囲内で検索できれば、検索速度を大幅に向上できます。まず、分類したい数を決めます。例えば下図のように4個に分類するなら、4個の中心点をランダムに生成し、各ベクトルを最も近い中心点に割り当てます。次に、現在同じクラスに割り当てられているベクトルから平均ベクトル点を計算し、中心点をその位置に移します。そして、各ベクトル点に最も近い中心点を再び判定し、分類し直します。この繰り返しの過程を学習と呼び、最終的に中心点は安定、つまり収束に向かいます。検索時には、クエリベクトルに最も近いクラスタ中心を見つけ、そのクラスタに属するベクトルを検索するだけで済みます。これにより、検索範囲を絞り込む目的を達成できます

5.2、量子化（Quantization）
しかし、大量のベクトルデータでは、検索速度に加えて、メモリ消費も大きな課題となります。実際の利用場面では、数千次元のベクトルや数億件のベクトルデータも珍しくないため、メモリ消費は非常に大きくなります。

上のクラスタリングで中心点について学びましたが、これは実は重心と呼ばれます。この重心でクラスタ内の点を代表させることはできるでしょうか。できるはずです。実は、この方法こそ典型的な非可逆圧縮 、画像を例にすると以下のようになります：

この方法ではベクトルの値の一部が失われますが、クラスタの重心と、そのクラスタに属するベクトルとの関連の強さを考えると、元の情報の一部はかなりの程度保たれています。そして、この非可逆圧縮によって細部の一部が失われることに比べ、得られる利点は非常に大きいものです。下図のように保存すれば、あるベクトルを使うとき、その符号値からコードブック内の対応する重心を見つけ、重心に対応する具体的な値を復元できます。ベクトルを重心の符号で表すこと、これがいわゆるベクトル量子化（Quantization)です

5.3、積量子化 PQ（Product Quantization）
ベクトルを量子化すると、コードブックが一つ増えます。ベクトル自体のメモリ使用量は確かに減りますが、このコードブックによって新たなメモリ使用量が生じ、しかもそれはかなりの大きさになります。低次元では目立ちませんが、実際の場面で使われる数百、数千次元のベクトルでは、このコードブックは恐ろしいほど大きくなります。ベクトルの数が一定の場合、量子化の品質を保つには、分布がまばらなベクトルほど多くのクラスタ代表ベクトルが必要です。

実際の用途で使われる数百から数千次元のベクトルでは、データは非常に疎になります。そのため、高次元空間で量子化の品質を確保するには、非常に多くのクラスタが必要になる場合があります。典型的な例を次の図に示します：128次元のベクトルには、2の64乗個のクラスタ中心が必要になる可能性があります。これにより、重心の符号を記録するコードブックが非常に巨大になります。そして、そのコードブックを保存するために消費するメモリは、量子化そのものによって節約できるメモリをはるかに上回ってしまいます
この問題を解決するには、まず高次元ベクトルを複数の低次元部分ベクトルに分割し、それらの低次元部分ベクトルごとに独立して量子化します。例えば、128次元の高次元ベクトルを8個の16ビットの部分ベクトルに分割し、次に8個の16次元の部分ベクトルで、それぞれ独立してクラスタリングの学習を行います。

こうして各ベクトルは、8個の部分空間の学習結果を使って、対応する8個の部分ベクトルを量子化できる。各部分ベクトルの次元数は16とそれほど高くないため、各16次元の部分空間では、クラスタ数が256個あれば十分に良好な量子化効果が得られる。そのため各部分ベクトルの符号値は0-255の範囲となり、8個の部分ベクトルの量子化符号をまとめることで、元のベクトルの最終的な量子化符号値が得られる。つまり、今や一つのベクトルが8個の符号値に量子化されたことになる。同様に、各部分空間も独自の部分コードブックを構築する。使用時には、8個の符号値を使って部分コードブックからそれぞれ検索した8個の16次元の部分ベクトルを結合し、一つの128次元ベクトルを復元する