学習
ベクターデータベース入門：知っておくべきことすべて

ベクトル類似検索入門

Nov 03, 20231 分で読めます

ベクトル検索とは何か、オブジェクト間の距離（または類似性）を決定するための適切なメトリクスを学ぶ。

シリーズ全体を読む

前回のチュートリアルでは、非構造化データ、ベクトルデータベース、そして世界で最も人気のあるオープンソースベクトルデータベースであるMilvusについて見てきました。非構造化データ](https://zilliz.com/glossary/unstructured-data)の素晴らしい意味論的表現として機能する高次元ベクトルであるembeddingsのアイデアについても簡単に触れました。エンベッディングとベクトル表現が互いに「近い」ことは、意味的に類似したデータの断片を表していることを意味します。

このベクトル検索入門では、ベクトル検索とは何かを定義し、ベクトル検索に関する基本的な疑問に答えます。その後、単語の埋め込みを例に、意味的に類似した非構造化データが互いに「近く」、非構造化データが互いに「遠い」ことを見ていきます。これは、最近傍探索のハイレベルな概要につながります。これは、統一された距離メトリックに基づいて、クエリベクトルに最も近いベクトルを見つけることを含む計算問題です。一般的に使用される距離メトリックに加えて、最近傍探索のためのいくつかの有名な方法（私のお気に入り - ANNOYを含む）について説明します。

さっそく始めましょう。

ベクトル探索、ベクトル類似探索とは?

ベクトル検索は、ベクトル類似検索、最近傍検索、またはセマンティック検索とも呼ばれ、データ検索や情報検索システムにおいて、与えられたクエリベクトルに類似または密接に関連するアイテムやデータポイントを見つけるために使用されるテクニックです。正確な単語やフレーズにマッチする従来のキーワード検索とは異なり、セマンティック検索はクエリの背後にある意図や文脈的な意味を理解するため、コンテンツに正確なキーワードが存在しない場合でも、より関連性の高い結果を返すことができる。ベクトル検索では、画像、テキスト、音声などのデータ点を高次元空間のベクトルとして表現する。ベクトル検索の目的は、クエリ・ベクトルに類似または最も近い、最も関連性の高いベクトルを効率的に検索・取得することである。

通常、ユークリッド距離や余弦類似度のような距離メトリックは、ベクトル間の類似性を測定します。ベクトル空間におけるベクトルの近さは、そのベクトルの類似度を決定する。ベクトルの検索結果を効率的に整理して表示するために、ベクトル検索アルゴリズムは、ツリーベースの構造やハッシュ技術などのインデックス構造を使用します。

ベクトル検索は、推薦システム、画像・動画検索、自然言語処理、異常検知、質疑応答チャットボットなど、様々な応用がある。セマンティック検索を使用することで、高次元データの中から関連する項目やパターン、関係性を見つけることが可能になり、より正確で効率的な情報検索が可能になる。

なぜベクトル検索が重要なのか？

ベクトル検索は、高次元空間から情報を分析・検索するための強力な手法である。ユーザーが与えられたクエリに対して、類似または密接に関連するアイテムを見つけることを可能にし、様々なドメインで重要な役割を果たす。以下にベクトル検索の利点を挙げる：

セマンティック検索は類似性ベースの検索を可能にし、ユーザーが与えられたクエリに類似または密接に関連するアイテムを見つけることを可能にする。類似性ベースの検索は、ユーザーが自分の好みや他のユーザーとの類似性に基づいてパーソナライズされた推薦を期待する推薦システムなど、様々なドメインで非常に重要である。
高次元データ分析** - 画像、音声、テキストデータなど、高次元データの利用可能性が高まるにつれ、従来の検索手法は有効ではなくなってきています。ベクトル検索は、高次元空間から情報を分析・検索する強力な方法を提供し、より正確で効率的なデータ探索を可能にします。
近傍探索** - 効率的な近傍探索アルゴリズムは、与えられたクエリベクトルに最も近い近傍を見つけます。最近傍検索は、画像やドキュメントの類似検索、コンテンツベースの検索、または最も近い一致や類似のアイテムを見つける必要がある異常検出などの重要なタスクに便利です。
セマンティック検索を活用することで、アプリケーションはユーザーにより適切でパーソナライズされた結果を提供することができます。ベクトル検索は、関連性の高い推奨情報の提供、視覚的に類似した画像の検索、類似したコンテンツを持つドキュメントの検索など、より的を絞った意味のある結果を提供することで、全体的なユーザー体験を向上させます。
スケーラビリティ** - ベクトル検索アルゴリズムとインデックス構造は、大規模なデータセットと高次元空間を効率的に処理します。これらは高速な検索と取得操作を可能にし、巨大なデータセット上でも、類似性に基づくクエリをリアルタイムで実行することを可能にします。

ベクター検索エンジンはどのように機能するのか？

AIやLLMの普及に伴い、あらゆる開発者ツール、検索エンジン、データベースは、その機能セットにベクトル検索機能を追加しています。このため、ベクトルエンジンやベクトル検索エンジンという用語は、しばしばベクトルデータベースと同じ意味で使用されます。ベクトル検索エンジンは、ベクトルセマンティック検索を行います（ベクトル検索と呼ばれることもあります）。ベクトル検索とは、高次元空間におけるベクトル表現に基づいて、データセット内の類似項目やデータ点を見つける技術である。各項目はこの空間内の点にマッピングされ、各ベクトル次元は特定の特徴を表す。ベクトル検索のプロセスには、インデックス作成、クエリ、ランキング、検索が含まれる。

ベクトル検索を行うには、まず、Word2VecやTF-IDFのようなテクニックを使って、データ項目をベクトルとして表現します。インデックス・データ構造は、KDツリーやハッシュ・テーブルのような手法を用いて、これらのベクトルを効率的に格納し、素早く検索できるようにする。ユーザがクエリーアイテムを送信すると、それはベクトル表現に変換され、余弦類似度やユークリッド距離のような類似度メトリクスを用いてインデックス化されたベクトルと比較され、最も類似したアイテムが検索され、ランク付けされる。

ベクトル検索の使用例

画像、動画、音声の類似検索
AI創薬
意味検索エンジン
DNA配列分類
質問応答システム
推薦システム
異常検知
検索拡張世代 (RAG)

さて、ベクトル検索の基本を説明したところで、単語の埋め込み例を見て、より技術的な詳細を調べ、最後に最近傍探索のハイレベルな概要を説明しよう。

埋め込みの比較

ユーザがソリューションにベクトル検索を組み込むことを決めたら、次によく聞かれる質問は、"どの機械学習モデルを使ってベクトル埋め込みを作成すべきか "です。モデルを選択する前に、いくつかの例を比較することで、ベクトル埋め込みを理解することが重要です。いくつかの単語埋め込み例を見てみましょう。ここでは簡単のため、skipgramsに基づいた学習方法を使用する古いモデルであるword2vecを使用します。BERTや他の最新の変換器ベースのモデルは、より文脈に基づいた単語埋め込みを提供することができますが、ここでは簡単のためにword2vec*にこだわります。Jay Alammarは、word2vecに関する素晴らしいチュートリアルを提供しています。

準備作業

始める前に、gensim ライブラリをインストールして word2vec モデルをロードする必要がある。

シェル pip install gensim --disable-pip-version-check wget https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz % gunzip GoogleNews-vectors-negative300.bin


    すでに満たされている要件: gensim in /Users/fzliu/.pyenv/lib/python3.8/site-packages (4.1.2)
    既に満たしている要件: smart-open>=1.8.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (from gensim) (5.2.1)
    すでに満たされている要件: numpy>=1.17.0 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (gensim から) (1.19.5)
    必要条件をすでに満たしています: scipy>=0.18.1 in /Users/fzliu/.pyenv/lib/python3.8/site-packages (gensim) (1.7.3)
    --2022-02-22 00:30:34-- https://s3.amazonaws.com/dl4j-distribution/GoogleNews-vectors-negative300.bin.gz
    s3.amazonaws.com (s3.amazonaws.com)を解決しています...52.216.20.165
    s3.amazonaws.com (s3.amazonaws.com)|52.216.20.165|:443...に接続しています。
    HTTP リクエストが送信されました。
    長さ: 1647046227 (1.5G) [application/x-gzip］
    保存先GoogleNews-vectors-negative300.bin.gz

    GoogleNews-vectors- 100%[=====================] 1.53G 2.66MB/s in 11m 23s

    2022-02-22 00:41:57 (2.30 MB/s) - GoogleNews-vectors-negative300.bin.gz saved [1647046227/1647046227].

    gunzip：GoogleNews-vectors-negative300.bin: サフィックスが不明 -- 無視されました。


word-to-vectorエンベッディングを生成するために必要な準備作業が終わったので、学習済みの`word2vec`モデルをロードしてみよう。


python
>> from gensim.models import KeyedVectors
>> model = KeyedVectors.load_word2vec_format('GoogleNews-vectors-negative300.bin', binary=True)

例0：マーロン・ブランド

word2vec` が有名な俳優 Marlon Brando をどのように解釈するか見てみよう。

python

print(model.most_similar(positive=['Marlon_Brando']))


    [('Brando', 0.757453978061676), ('Humphrey_Bogart', 0.6143958568572998), ('actor_Marlon_Brando', 0.6016287207603455), ('Al_Pacino', 0.5675410032272339), ('Elia_Kazan', 0.5594002604484558), ('Steve_McQueen', 0.5539456605911255）、（'Marilyn_Monroe'、0.5512186884880066）、（'Jack_Nicholson'、0.5440199375152588）、（'Shelley_Winters'、0.5432392954826355）、（'Apocalypse_Now'、0.5306933522224426）] 。


マーロン・ブランドは『ゴッドファーザー』でアル・パチーノと、『欲望という名の電車』でエリア・カザンと共演。アポカリプス・ナウ』にも出演。

### 例1：もしすべての王が王妃を玉座に座らせたとしたら

ベクトル同士を足したり引いたりすることで、根本的な意味の変化を示すことができる。


``python
>> print(model.most_similar(positive=['king', 'woman'], negative=['man'], topn=1)))

[('queen', 0.7118193507194519)]

エンジニアがたまにはダンスポップを楽しんではいけないと誰が言った？

例2：アップル、会社、果物、...それとも両方？

apple」という単語は、会社だけでなく、おいしそうな赤い果物も指すことができます。この例では、Word2Vecが両方の意味を保持していることがわかる。

パイソン

print(model.most_similar(positive=['samsung', 'iphone'], negative=['apple'], topn=1)) print(model.most_similar(positive=['fruit'], topn=10))[9:])


    [('droid_x', 0.6324754953384399)]
    [('apple', 0.6410146951675415)]


「ドロイド」はサムスン初の4G LTEスマートフォン（「サムスン」＋「iPhone」-「アップル」＝「ドロイド」）を指し、「アップル」は「フルーツ」に10番目に近い単語である。

## ベクトル検索戦略

ベクトル埋込みの威力を理解したところで、最近傍探索を行うためのいくつかの方法を簡単に見てみましょう。これは包括的なリストではありません。ベクトル検索がどのように大規模に行われるかのハイレベルな概要を提供するために、いくつかの一般的な方法について簡単に説明します。例えば、量子化と空間分割を併用することも可能です。

(今後のチュートリアルでは、これらの各手法について詳しく解説していきますので、ご期待ください)

### 線形探索

最も単純だが最もナイーブな最近傍探索アルゴリズムは、古き良き線形探索です：クエリベクトルから[ベクトルデータベース](https://zilliz.com/learn/beginner-guide-to-implementing-vector-databases)内の他のすべてのベクトルまでの距離を計算します。

明らかな理由により、ナイーブ検索はベクトルデータベースを数千万、数億のベクトルに拡張しようとするときには機能しません。しかし、データベースの総要素数が少ない場合は、インデックスのための独立したデータ構造が必要なく、挿入や削除が非常に簡単に実装できるため、ナイーブサーチはベクトル検索を実行する最も効率的な方法となります。

ナイーブ検索に伴う空間の複雑さや一定の空間オーバーヘッドがないため、この方法は、中程度の数のベクトルに対してクエリを実行する場合でも、空間分割を上回ることがよくあります。

### 空間分割

スペース・パーティショニングは単一のアルゴリズムではなく、すべて同じ概念を使用するアルゴリズムのファミリーです。

K次元木(kd-trees)は、おそらくこのファミリーの中で最もよく知られており、2進探索木に似た方法で探索空間を連続的に2等分する(ベクトルを「左」と「右」のバケットに分割する)ことで機能する。

IVFも空間分割の一種であり、各ベクトルを最も近い重心に割り当てることで機能する。検索は、まずクエリーベクトルに最も近い重心を決定し、そこを中心に検索を行うことで、検索が必要なベクトルの総数を大幅に減らす。IVFはかなり一般的なインデックス作成戦略であり、性能を向上させるために他のインデックス作成アルゴリズムと組み合わせるのが一般的である。

### 量子化

量子化は、ベクトルの精度を下げることでデータベースの総サイズを縮小する手法です。

例えばスカラー量子化 (SQ) は、高精度の浮動小数点ベクトルにスカラー値を乗算し、その結果のベクトルの要素を最も近い整数にキャストすることで機能します。これはデータベース全体の実効サイズを小さくするだけでなく（例えば**float64_t**から**int8_t**への変換では8分の1）、ベクトル間の[ベクトル距離](https://zilliz.com/glossary/vector-distance)の計算を高速化するという良い副作用もあります。

積量子化(PQ)は、辞書圧縮と似た働きをするもう1つの量子化手法です。PQでは、すべてのベクトルは等しい大きさの部分ベクトルに分割され、それぞれの部分ベクトルは重心に置き換えられます。

### 階層移動可能な小世界（HNSW）

Hierarchical Navigable Small Worldsは、グラフベースの索引付けおよび検索アルゴリズムである。

HNSWは、有効サイズを小さくすることでデータベースの検索性を向上させる代わりに、元のデータから多層グラフを作成する。上層には「長い接続」のみが含まれ、下層にはデータベース内のベクトル間の「短い接続」のみが含まれる（ベクトル距離メトリクスの概要については次のセクションを参照）。個々のグラフ接続は、スキップリストのように作成される。

このアーキテクチャーにより、検索は非常に簡単になります。クエリベクトルに最も近いベクトルを探すために、一番上のグラフ（最も長いベクトル間接続を持つグラフ）を貪欲に走査します。次に、第1層の検索結果を出発点として、第2層でも同じことを行う。これは一番下の層で検索が完了するまで続けられ、その結果がクエリーベクトルの最近傍となる。

HNSW、可視化。画像ソース：https://arxiv.org/abs/1603.09320](https://assets.zilliz.com/hnsw_visualized_9bd0417e4d.png)


### 近似最近傍Oh Yeah](https://zilliz.com/learn/approximate-nearest-neighbor-oh-yeah-ANNOY)

これは、その遊び心のある直感的でない名前のため、おそらく私のお気に入りのANNアルゴリズムです。[Approximate Nearest Neighbors Oh Yeah](https://github.com/spotify/annoy) (ANNOY)は、Spotifyによって普及したツリーベースのアルゴリズムである（彼らの音楽推薦システムで使用されている）。その奇妙な名前とは裏腹に、ANNOYの根底にあるコンセプトは実にシンプルだ。

ANNOYは、まずデータベース内の2つのベクトルをランダムに選択し、その2つのベクトルを隔てる超平面に沿って探索空間を2等分することで機能する。これは、ノードごとにあらかじめ定義されたパラメータ**NUM_MAX_ELEMS**より少なくなるまで繰り返し行われる。結果として得られるインデックスは基本的にバイナリーツリーであるため、O(log n)の複雑さで検索を行うことができる。


ANNOY、可視化。画像ソース：https://github.com/spotify/annoy](https://assets.zilliz.com/annoy_visualized_1adb042e7e.png)


## よく使われる類似度メトリクス

非常に優れたベクトルデータベース](https://zilliz.com/)は、2つのベクトル間の距離を計算する方法である類似性メトリクスなしでは役に立ちません。数多くのメトリクスが存在するので、ここでは最もよく使われるサブセットについてのみ説明します。

### 浮動小数点ベクトルの類似度メトリクス

最も一般的な浮動小数点ベクトルの類似度メトリクスは、順不同ですが、_L1 distance_、_L2 distance_、_cosine similarity_です。最初の2つの値は_距離メトリック（値が小さいほど類似度が高く、値が大きいほど類似度が低いことを意味する）であり、コサイン類似度は_類似度メトリック（値が大きいほど類似度が高いことを意味する）です。

1. $$d_{l1}(\mathbf{a},\mathbf{b})=\sum_{i=1}^{N}|\mathbf{a}_i-\mathbf{b}_i|$$
2. $$d_{l2}(\mathbf{a},\mathbf{b})=\sqrt{\sum_{i=1}^{N}(\mathbf{a}_i-\mathbf{b}_i)^2}$$
3. $$d_{cos}(\mathbf{a},\mathbf{b})=\frac{\mathbf{a}\cdot\mathbf{b}}{|\mathbf{a}||\mathbf{b}|}$$

L1距離は一般にマンハッタン距離とも呼ばれ、マンハッタンで点Aから点Bに行くには、2つの垂直方向のどちらかに沿って移動する必要があるという事実にちなんで名付けられた。2番目の式、L2距離は、ユークリッド空間における2つのベクトル間の距離である。最後の3番目の式は余弦距離で、2つのベクトル間の角度の余弦に相当する。余弦類似度の式は、入力ベクトル__a__と__b__の正規化されたバージョン間のドット積であることに注意してください。

ちょっとした計算で、単位ノルムベクトルの類似度ランキングに関しては、L2距離と余弦類似度が実質的に等価であることを示すこともできます：

$$d_{l2}(\mathbf{a},\mathbf{b})=(\mathbf{a}-\mathbf{b})^T(\mathbf{a}-\mathbf{b})$$
$$=\mathbf{a}^T\mathbf{a}-2\mathbf{a}^T\mathbf{b}+\mathbf{b}^T\mathbf{b}$$

単位ノルムベクトルは大きさが1であることを思い出してください：

mathbf{a}^Tmathbf{a}=1$。

これを使うと

$$\mathbf{a}^T\mathbf{a}-2\mathbf{a}^T\mathbf{b}+\mathbf{b}^T\mathbf{b}$$
$$=2-2\mathbf{a}^T\mathbf{b}$$

単位ノルムのベクトルを持っているので、余弦距離は__a__と__b__の間のドット積になる（上の式3の分母は1になる）：

$$2-2\mathbf{a}^T\mathbf{b}$$
$$=2(1-d_{cos}(\mathbf{a},\mathbf{b}))$$

基本的に、単位ノルムベクトルに対して、L2距離と余弦類似度は関数的に等価です！埋め込みを正規化することを常に忘れないでください。

### バイナリ・ベクトルの類似度メトリクス

バイナリ・ベクトルは、その名前が示すように、浮動小数点ベクトルのような算術に基づくメトリックスを持ちません。2進ベクトルの類似度メトリクスは、代わりに集合数学、ビット操作、またはその両方の組み合わせに依存します（大丈夫です、私も離散数学は嫌いです）。以下は、よく使われる2つの2進ベクトルの類似度メトリクスの公式です：

1. $$d_J(\mathbf{a},\mathbf{b})=1-\frac{\mathbf{a}\cdot\mathbf{b}}{|a|^2+|b|^2-\mathbf{a}\cdot\mathbf{b}}$$
2. $$d_J(\mathbf{a},\mathbf{b})=\sum_{i=1}^{N}\mathbf{a}_i\oplus\mathbf{b}_i$$

最初の式はTanimoto/Jaccard距離と呼ばれ、本質的に2つの2値ベクトル間の重なり量の尺度である。2番目の式はハミング距離で、aとbのベクトル要素のうち、互いに異なるものの数を数えるものである。

ほとんどのアプリケーションでは、浮動小数点埋め込みよりもコサイン類似度を使用するため、これらの類似度メトリクスは無視しても問題ないでしょう。

## まとめ

このチュートリアルでは、一般的なベクトル探索アルゴリズムと距離メトリクスとともに、ベクトル探索について見てきました。以下は重要な要点です：

* 埋め込みベクトルは、ベクトル間の距離においても、ベクトル算術においても、強力な表現です。埋め込みベクトルにベクトル代数を自由に適用することで、基本的な数学的演算子だけでスケーラブルな意味解析を行うことができる。

* セマンティック・ベクトル検索](https://zilliz.com/vector-database-use-cases/semantic-search)は、クエリの意味に基づいて検索できるようにすることで、キーワード検索の限界を克服します。ベクトル検索を行うことで、答えを素早く検索することができる。

* 近似最近傍探索アルゴリズムやインデックスの種類は多種多様です。現在最も一般的に使用されているのはHNSWですが、個々のベクトルの長さだけでなく、埋め込むベクトルの総数によっては、別のインデックス作成アルゴリズムの方が特定のアプリケーションに適している場合があります。

* 今日使われている2つの主要な距離メトリクスは、L2/ユークリッド距離と余弦距離です。正規化された埋め込みで使用される場合、これら2つのメトリクスは機能的に等価です。

このチュートリアルにご参加いただきありがとうございます！ベクトル探索は[Milvus](https://zilliz.com/what-is-milvus)の核心部分であり、これからもそうあり続けます。今後のチュートリアルでは、最も一般的に使用されるANNSアルゴリズムであるHNSWとScaNNをより深く掘り下げていきます。

## ベクターデータベース101コースをもう一度見てみよう

1.[非構造化データ入門](https://zilliz.com/learn/introduction-to-unstructured-data)
2.[ベクターデータベースとは](https://zilliz.com/learn/what-is-vector-database)
3.[ベクトルデータベース、ベクトル検索ライブラリ、ベクトル検索プラグインの比較](https://zilliz.com/learn/comparing-vector-database-vector-search-library-and-vector-search-plugin)
4.[Milvusの紹介](https://zilliz.com/learn/introduction-to-milvus-vector-database)
5.[Milvusクイックスタート](https://zilliz.com/learn/milvus-vector-database-quickstart)
6.[ベクトル類似検索入門](https://zilliz.com/learn/vector-similarity-search)
7.[ベクトルインデックスの基本と反転ファイルインデックス](https://zilliz.com/learn/vector-index)
8.[スカラー量子化と積量子化](https://zilliz.com/learn/scalar-quantization-and-product-quantization)
9.[階層的航行可能小世界(HNSW)](https://zilliz.com/learn/hierarchical-navigable-small-worlds-HNSW)
10.[近似最近傍オーイェー(ANNOY)](https://zilliz.com/learn/approximate-nearest-neighbor-oh-yeah-ANNOY)
11.[プロジェクトに適したベクトルインデックスの選択](https://zilliz.com/learn/choosing-right-vector-index-for-your-project)
12.[DiskANNとVamanaアルゴリズム](https://zilliz.com/learn/DiskANN-and-the-Vamana-Algorithm)