ベクトル検索へのイントロダクション

# はじめに
本記事は、2025年2月6日に公開されたElastic 社の公式ブログ 「[A quick introduction to vector search](https://www.elastic.co/search-labs/blog/introduction-to-vector-search)」 を元にした日本語訳です。
元記事の著者: [Valentin Crettaz](https://www.elastic.co/search-labs/author/valentin-crettaz)

基礎からわかりやすく解説されており、ベクトル検索をこれから学ぶ方y復習したい方にもおすすめです！

# ベクトル検索へのイントロダクション

この記事は全3部構成の第一部で、セマンティック検索とも呼ばれるベクトル検索の仕組みと、そのElasticsearchでの実装方法について掘り下げていきます。

この記事では、埋め込みベクトルの基本と、ベクトル検索が内部でどのように動作しているのかについて、概観を提供します。

第一部で学んだ知識をもとに、[第二部](https://www.elastic.co/search-labs/blog/vector-search-set-up-elasticsearch) \([日本語訳](https://qiita.com/nobuhikosekiya/items/dbc86009f7a49a08843e)\) では、Elasticsearchにおけるベクトル検索のセットアップ方法を詳しく解説します。

第三部では、前の2部で得た知識を応用し、強力なハイブリッド検索クエリをElasticsearchで構築する方法について深堀りしていきます。

この記事の本題に入る前に、セマンティック検索の要となる概念であるベクトルの歴史をさかのぼって振り返ってみましょう。

## ベクトルは新しい概念ではない

おそらく、2022年11月にChatGPTが登場して以来、「ベクトル検索」という言葉を耳にしない日はないと思います。あまりにも至るところに現れ、最新の最先端技術のように感じられがちですが、実はこの技術は60年以上前から存在しているのです。1960年代半ばから研究が始まり、1978年に情報検索の第一人者であったGerard Saltonと彼のCornell Universityでの同僚たちによって最初の論文が発表されました。Saltonの密なベクトルモデルと疎なベクトルモデルに関する研究は、現代のベクトル検索技術の根幹を成しています。

過去20年間で、彼の研究に基づいたさまざまな[ベクトルDBMS](https://db-engines.com/en/ranking/vector+dbms/all)が開発され、市場に投入されてきました。その中には、Apache LuceneプロジェクトをベースにしているElasticsearchも含まれ、2019年から[ベクトル検索の開発](https://issues.apache.org/jira/browse/LUCENE-9004)に着手しています。

ベクトルはあらゆるところにあり、その基礎理論と内部動作をしっかりと把握することが、実際に触れる前に重要となります。ここで、まず従来のレキシカル検索とベクトル検索の違いを簡単に振り返り、その違いや相互補完性について理解を深めていきましょう。

## ベクトル検索とレキシカル検索

ベクトル検索（セマンティック検索とも呼ばれます）と、これまでなじみのあったレキシカル検索は、根本的に異なる仕組みで動作します。レキシカル検索は、Elasticsearchで長年利用されてきた検索手法です。簡単にまとめると、インデックスやクエリの対象となるデータの真の意味を理解しようとはせず、ユーザーが入力したクエリ中の単語やその変形（ステミングや同義語など）のリテラル値を、類似度アルゴリズム（TF-IDFなど）を用いてインデックス済みのリテラル値と**レキシカル**にマッチさせることに注力します。

![レキシカル検索の例](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Fa4f3eba19599e5330e9b0d29ecdbbeac211cdab0-1600x583.png&w=3840&q=75)

_図1: レキシカル検索の簡単な例_

図から分かるように、左上の3つのドキュメントはトークン化と解析が行われ、解析後の用語が転置インデックスに登録されます。転置インデックスは、解析された用語とそれを含むドキュメントIDを単純にマッピングします。なお、各用語は一度だけ現れ、どのドキュメント間でも共有されません。たとえば「nice german teacher」で検索すると、クエリの真の意味を正確に捉えてはいないものの、スコアの異なる3つのドキュメントがヒットします。

図2に示すように、多義語や同形異義語、つまり綴りは同じでも**意味が異なる**単語（right, palm, bat, meanなど）を扱う場合、さらに複雑になります。例として「right」という単語は3つの異なる意味を持ちますが、これがどのように処理されるかを見てみましょう。

![同形異義語の検索](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Febb9cc1be03475bbf68269a8dcea5f08bcda0b64-1594x754.png&w=3840&q=75)

_図2: 同形異義語の検索_

例えば _「I’m not right」_ で検索すると、最初の結果とは正反対の意味を持つドキュメントが返されます。同じ単語でも、順序を変えて意味が変わる _「turn right」_ と _「right turn」_ では、同じ結果（例：3番目のドキュメント「Take a right turn」）が返されます。ここでのクエリは単純化されていますが、フレーズマッチングなどの高度なクエリを使えば違いは出てきます。しかし、この例はレキシカル検索が、インデックスされたものや検索対象の真意を理解していないことを示しています。この点は第三部で、ベクトル検索がどのように役立つかを詳しく見ていきます。

構造化データをどのようにインデックスするか（例えばマッピング、テキスト解析、インジェストパイプラインなどを使って）、またクエリをどのように設計するか（巧妙に作成されたDSLクエリ、クエリ用語の解析などを使って）について自由度があれば、もちろん、レキシカル検索でも非常に優れた結果を得ることができます。Elasticsearchのレキシカル検索機能がこれまでに達成してきた成果は驚異的です。

しかし、ユーザーが自由形式の質問を行う必要がある[**非構造化データ**](https://www.elastic.co/what-is/unstructured-data)（画像、動画、音声、テキストなど）に対して検索機能を提供する場合、レキシカル検索はその限界を露呈します。さらに、クエリがテキスト以外の場合、たとえば画像の場合もあります。そのようなケースでレキシカル検索が不十分な理由は、非構造化データが構造化データと同じ方法でインデックスや検索ができないためです。非構造化データを扱う際は、**セマンティクス**が重要になるのです。セマンティクスとは、非常にシンプルに言えば「意味」のことです。

たとえば、画像検索エンジン（Google画像検索やLensなど）では、画像をドラッグ＆ドロップすると、その画像に最も類似する画像が返されます。図3では、左側にジャーマン・シェパードの写真があり、右側に似た画像が並んでいます。最初の結果は、提供された画像そのもの、つまり最も類似している画像となっています。

![セマンティック検索の例: 画像検索](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Fc0dff24d4379141abd1038c9c4b5577fd2dca802-1600x657.png&w=3840&q=75)

_図3: 画像検索の例_

出してみれば人間には直感的なものですが、コンピューターにとっては全く異なる問題です。これが、ベクトル検索が可能にし、実現する力です。近年、ベクトル検索が解放するパワーは非常に大きいと実感されています。では、内部の仕組みを詳しく見ていきましょう。

## 埋め込みベクトル

前述のように、レキシカル検索エンジンではテキストのような構造化データは簡単にトークン化され、検索時に用語がマッチしますが、非構造化データは画像、動画、音声、原文など多様な形式を取り、同じトークン化プロセスに適していません。また、セマンティック検索の本質は、データが持つ「意味」に基づいて検索できるようにデータをインデックス化することにあります。では、どうすれば実現できるのでしょうか？その答えは、**機械学習**、より正確には**ディープラーニング**にあります。

**ディープラーニング**は、複数の処理層からなる人工ニューラルネットワークを用いて、データの真の意味を段階的に抽出する機械学習の一分野です。これらのニューラルネットワークモデルの動作は、人間の脳から多くのインスピレーションを受けています。下図の図4は、入力層、出力層、複数の隠れ層を持つニューラルネットワークの概念図です。

![ニューラルネットワークの層](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Faeea3bab3c29e1c591a9c9082f2e73e7d3990ef1-1600x1116.png&w=3840&q=75)

_図4: ニューラルネットワークの層_

（出典: IBM, <https://www.ibm.com/topics/neural-networks>）

ニューラルネットワークの真骨頂は、非構造化データの単一の入力を、**埋め込みベクトル**、つまり一連の浮動小数点数に変換できる点にあります。私たち人間は、ベクトルを2次元または3次元空間で視覚化することでその概念を理解できますが、ニューラルネットワークが扱う埋め込みベクトルは、何百、何千もの次元を持ち、多次元空間内の一点を表現しています。各次元は、非構造化データの**特徴**や性質を示しています。例として、2048次元の埋め込みベクトルに画像を変換するディープラーニングモデルを考えてみましょう。このモデルは、図3で使用したジャーマン・シェパードの画像を、下表のような埋め込みベクトルに変換します。表では最初の3要素と最後の3要素のみを示していますが、実際には残り2042の次元があります。

|  | is_red | is_dog | blue_sky | … | no_gras | german_shepherd | is_tree |
| --- | --- | --- | --- | --- | --- | --- | --- |
| German shepherd embeddings | 0.0121 | 0.9572 | 0.8735 | … | 0.1198 | 0.9712 | 0.0512 |

各列はモデルの次元であり、ニューラルネットワークが捉えようとする非構造化データの特徴を表現しています。モデルに入力される各データは、2048次元それぞれとの類似度によって特徴づけられ、その値が各次元における**類似度**を示します。この例では、モデルが犬とジャーマン・シェパードとの高い類似度、そして青空の存在を検出していることが分かります。

レキシカル検索では、用語が単に一致するか否かだけですが、ベクトル検索では、非構造化データが各次元に対してどれだけ**類似**しているかを数値で示すことができます。したがって、埋め込みベクトルは、非構造化データのセマンティックな表現として非常に有用です。

## その秘密のソース

ディープラーニングのニューラルネットワークモデルが、非構造化データを高次元の埋め込みベクトルに変換し、その各次元がデータとの類似度を示す仕組みを理解したところで、次はこれらのベクトルがどのようにマッチングされるのかを理解する必要があります。答えは非常にシンプルです。互いに「近い」埋め込みベクトルは、**セマンティックに似通った**データを表しています。したがって、ベクトルデータベースにクエリが投げられる際、まずクエリ（画像、テキストなど）は、インデックス時に使用したのと同じモデルによって埋め込みベクトルに変換され、その後、クエリベクトルに最も近い**近傍ベクトル**を探し出すのです。つまり、必要なのはクエリベクトルとデータベース内の各ベクトルとの「距離」または「類似度」を測る方法を見つけることだけなのです。

### 距離と類似度

幸いにも、ベクトル同士の距離を測定するのは、ベクトル演算のおかげで容易な問題です。ここでは、Elasticsearchのような最新のベクトル検索データベースでサポートされる、最も一般的な距離および類似度の関数について見ていきます。※以下、数学の話が続きます。

#### L1距離

L1距離（マンハッタン距離とも呼ばれる）は、2つのベクトル x と y の各要素間の絶対差をすべて足し合わせたものです。距離 d が小さいほど、2つのベクトルは近いと判断されます。以下の式で表されます。

![L1 distance formula](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F2b17bcedfbedde61117a3e7970af55bc62318c6c-312x102.png&w=3840&q=75)

図5は、2つのベクトル間のL1距離を視覚的に表現したものです。

![Visualizing the L1 distance between two vectors](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F52075441892151536ed216081817a8e852566daa-474x464.png&w=3840&q=75)

_図5: 2つのベクトル間のL1距離の視覚化_

例えば、x = (1, 2) と y = (4, 3) の場合、L1距離は |1 − 4| + |2 − 3| = 3 + 1 = 4 となります。

#### L2距離

L2距離（ユークリッド距離とも呼ばれる）は、各要素間の差の二乗和の平方根として計算され、2点間の最短距離（斜辺）を表します。L1と同様、距離 d が小さいほど、2つのベクトルは近いと判断されます。

![](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Fb7675aa41f4f381e954c21dacd23a51a2dde6780-384x112.png&w=3840&q=75)

図6は、L2距離を視覚的に示しています。

![Visualizing the L2 distance between two vectors](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Fbac99d08d6cf8a3a387a8acdc2e8f67357dad235-448x456.png&w=3840&q=75)

_図6: 2つのベクトル間のL2距離の視覚化_

同じサンプルベクトル x と y を用いると、L2距離は  
\( (1-4)^2 + (2-3)^2 = 9 + 1 = 10 \)  
となり、その平方根は約3.16になります。

#### Linf距離

Linf距離（L∞距離、チェビシェフ距離またはチェス盤距離とも呼ばれる）は、2つのベクトル x と y の各要素間の差のうち、最大のものを取ったものです。式は以下の通りです。

![](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F179ea6c6520a59acd97638313a2fb1b105e2ffed-436x82.png&w=3840&q=75)

図7は、Linf距離の視覚的な表現です。

![Linf distance between two vectors](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Fb75540d793cdc0645244d77dc36da9d5734ccbac-548x560.png&w=3840&q=75)

_図7: 2つのベクトル間のLinf距離の視覚化_

サンプルの x と y では、Linf距離は  
max(|1 − 4|, |2 − 3|) = max(3, 1) = 3  
となります。

#### コサイン類似度

L1、L2、Linfが2つのベクトル間の距離を測るのに対し、コサイン類似度は2つのベクトル x と y の相対的な角度、つまり同じ方向を向いているかどうかを評価します。類似度 s が高いほど、2つのベクトルは「近い」と判断されます。式は以下の通りです。

![](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F931b6b90f0ee83e63a66496d06d6b4cef3affddd-304x72.png&w=3840&q=75)

図8は、2つのベクトル間のコサイン類似度の視覚化です。

![cosine similarity between two vectors](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F52092e8b5d366178e50a35f8c954ee8eaca76965-582x586.png&w=3840&q=75)

_図8: 2つのベクトル間のコサイン類似度の視覚化_

コサイン値は常に[-1, 1]の範囲にあり、-1は全く逆の方向（180°）、0は無関係（90°）、1は完全に一致（0°）を意味します。図9にそのスペクトルが示されています。

![The cosine similarity spectrum](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Ffd2690a845b89b69ff202bd04192893638538aec-1600x456.png&w=3840&q=75)

_図9: コサイン類似度のスペクトル_

たとえば、先ほどの x と y のサンプルベクトルでコサイン類似度を計算すると、まず内積は (1 * 4) + (2 * 3) = 10  となります。次に、それぞれのベクトルの大きさ（ノルム）を求め、  
\(1^2 + 2^2\)^1/2 + (4^2+3^2)^1/2 = 11.18034  となり、内積を、掛け合わせた大きさで割ると、10/11.18034 = 0.894427 (約26°の角度に相当)となります。これは、1に近いため両方のベクトル値は高い類似度と言えます。

#### 内積 (Dot product)による類似度

コサイン類似度の欠点は、角度のみを考慮し、ベクトルの大きさ（長さ）を無視してしまう点です。つまり、同じ方向を向いていても、片方のベクトルが非常に大きい場合でも高い類似度と判断されてしまいます。内積（スカラー積、または内積）は、角度と大きさの両方を考慮することで、より正確な類似度を提供します。

内積による類似度を計算する方法は2通りあります。1つ目は先ほどのコサイン類似度の分子と同じ計算、すなわち

![](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F52e2723926ab27cd96b688e805fae15f607073c8-482x104.png&w=3840&q=75)

です。2つ目は、各ベクトルの大きさに、両者の間のコサイン値を掛け合わせる方法です。

![](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Fdc9b11fc67dd748d9f1f29b735f4726138cb7d39-452x70.png&w=3840&q=75)

図10は、内積による類似度の視覚化です。

![dot product similarity between two vectors](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F1bda38cf82a1e1037f44b6e9657602c9efe1c0a6-558x574.png&w=3840&q=75)

_図10: 2つのベクトル間の内積類似度の視覚化_

再び、サンプルベクトル x と y で内積類似度を計算すると、先ほどと同様に (1 * 4) + (2 * 3) = 10 となります。2つ目の方法では、各ベクトルの大きさを掛け合わせ（先述の約11.18034）、その値にコサイン値（約0.894427）を掛けると、同じく約10となります。

なお、全てのベクトルを**正規化**（長さを1にする）すれば、内積類似度はコサイン類似度と全く同じ値（すなわち、両者の角度のコサイン値）となります。正規化は、ベクトルの大きさを無視し、角度に基づいた類似度に集中できるため、インデックス作成時や検索時の計算速度向上にも寄与します。

### 簡単なおさらい

ここまで非常に多くの情報を見てきました。改めて、以下の点を整理しましょう。

- セマンティック検索は、非構造化データを高次元の埋め込みベクトルに変換するディープラーニングのニューラルネットワークモデルに基づいている。
- モデルの各次元は、非構造化データの特徴や性質を表している。
- 埋め込みベクトルは、各次元における類似度（特徴とのマッチング度）を数値で表現したものである。
- 2つのベクトルが近ければ近いほど、セマンティックに類似した概念を表している。
- 距離関数（L1, L2, Linf）により、2つのベクトル間の近さを測定できる。
- 類似度関数（コサイン類似度および内積）は、2つのベクトルがどれだけ同じ方向を向いているか、またはどれだけ類似しているかを測定できる。

さて、ここまでで残る最後のパートは、ベクトル検索エンジン自体の解説です。クエリが送られると、まずクエリがベクトル化され、その後、データベース内の近傍ベクトルが検索されます。全てのベクトルとクエリベクトルとの距離や類似度を逐一計算する全探索（ブルートフォース）では、小規模データセットでは動作するものの、ベクトル数が増加すると性能が大幅に低下してしまいます。つまり、数百万、数十億、あるいは数兆ものベクトルを合理的な時間内に処理するには、いかに効率的にインデックス化するかが重要なのです。

### ベクトル検索アルゴリズムと技法

これまで、多くの研究チームが非常に巧妙なベクトル検索アルゴリズムの開発に取り組んできました。ここでは、用途に応じて適した主要な手法について簡単に紹介します。

#### リニアサーチ

前述したように、リニアサーチ（フラットインデックス）は、クエリベクトルとデータベース内の全ベクトルとの比較を行うブルートフォース的なアプローチです。小規模データセットではうまく機能しますが、ベクトルの数や次元が増えるにつれて性能が急激に低下します（計算量はO(n)）。

そのため、**近似最近傍探索（ANN: Approximate Nearest Neighbor）**と呼ばれる、あらかじめベクトル間の距離を計算し、類似したベクトル同士をクラスタ、木、ハッシュ、グラフなどを用いて近くにまとめておく効率的な手法が用いられます。これらの手法は、必ずしも100%の精度を保証するわけではありませんが、検索範囲をできるだけ絞り込むか、もしくはベクトルの次元を削減することで、効率的に近傍ベクトルを探索することを目指しています。

#### k-d木（KD-Tree）

k-d木は、k次元空間内の点を格納するための二分探索木の一般化で、検索空間を左と右の部分木に連続的に分割していきます。検索時には、クエリベクトル（図11の赤い点）の周辺のいくつかの枝だけを訪問し、最も近い近傍（図11の緑の点）を見つけます。もしk個以上の近傍が要求される場合は、黄色の領域を拡大して探索します。

![KD tree algorithm](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2Fe21af2d613112279089b6fa2166359233b10019d-829x860.png&w=3840&q=75)

_図11: KD-Treeアルゴリズム_  
（出典: <https://salzi.blog/2014/06/28/kd-tree-and-nearest-neighbor-nn-search-2d-case/>）

KD-Treeの最大の利点は、局所的な部分木だけに絞り込むことで、ほとんどのベクトルを探索対象から除外できる点にあります。しかし、次元数が増加すると、訪問すべき枝が増え、効率が低下するという問題があります。

#### 転置ファイルインデックス（Inverted File Index, IVF）

転置ファイルインデックス（IVF）も空間分割アルゴリズムの一種で、近いベクトル同士を共通のセントロイドに割り当てます。2次元空間では、図12のようなボロノイ図で表現できます。

![Voronoi representation of an inverted file index in the 2D space](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F33ddaaa818ab2f2a5fc87982c82c2a34cb849e33-640x640.png&w=3840&q=75)

_図12: 2次元空間における逆ファイルインデックスのボロノイ図_  
（出典: <https://docs.zilliz.com/docs/vector-index-basics-and-the-inverted-file-index>）

上記の図では、2次元空間が20のクラスタに分割され、各クラスタの中心が黒い点で示されています。空間内のすべての埋め込みベクトルは、最も近いセントロイドを持つクラスタに割り当てられます。検索時には、まずクエリベクトルに最も近いセントロイドを特定し、そのクラスタや周辺のクラスタを対象にして近傍を探索します。

しかし、この手法もKD-Treeと同様に、高次元空間では「次元の呪い」と呼ばれる問題に直面します。空間の体積が爆発的に増大するため、データが希薄になり、より精度の高い結果を得るには指数関数的に多くのデータが必要となります。データが希薄な場合、空間分割アルゴリズムはクラスタリングが難しくなります。

#### 量子化（Quantization）

量子化は、埋め込みベクトルの精度を下げることで、データベース全体のサイズを圧縮する手法です。**スカラー量子化（SQ）**を用い、浮動小数点数の値を整数に変換することで、データベースのサイズを8分の1に削減でき、メモリ消費量も減少し、検索時の距離計算が高速化されます。

また、**プロダクト量子化（PQ）**と呼ばれる手法では、まず空間を低次元の部分空間に分割し、各部分空間で近いベクトルをクラスタリング（k-meansなど）する方法が用いられます。

なお、量子化は、ベクトルの次元数を削減する**次元削減**とは異なります。

#### Hierarchical Navigable Small Worlds（HNSW）

名前が複雑に見えるかもしれませんが、実際はそれほど難しいものではありません。HNSWは、グラフベースのマルチレイヤーアルゴリズムで、多くのベクトルデータベース（Apache Luceneなど）で採用され、高い効率を発揮しています。概念的なHNSWの構成は、図13に示されています。

![Hierarchical Navigable Small Worlds ](https://www.elastic.co/search-labs/_next/image?url=https%3A%2F%2Fcdn.sanity.io%2Fimages%2Fme0ej585%2Fsearch-labs-import-testing%2F189ef9a8bec476e379222c454644ba4c1f952085-1400x840.png&w=3840&q=75)

_図13: Hierarchical Navigable Small Worlds_  
（出典: <https://towardsdatascience.com/similarity-search-part-4-hierarchical-navigable-small-world-hnsw-2aad4fe87d37>）

最上層では、非常に少数のベクトルが、最も離れたリンク（類似度が低いもの）を介して接続されています。下位層に進むにつれて、より多くのベクトルが現れ、グラフは密になり、類似したベクトルが互いに近接して配置されます。最下層では、すべてのベクトルが配置され、最も類似したものが互いに近くに存在します。

検索時、アルゴリズムは任意のエントリーポイントから最上層でクエリベクトルに最も近いベクトル（図中の灰色の点）を見つけ、次にそのベクトルを起点に下位層へ移り、同様の探索を繰り返して、最下層で最も近い近傍を見つけ出します。

#### ローカリティセンシティブハッシング（LSH）

これまでの手法と同様、LSHも検索空間を大幅に削減し、検索速度を向上させる手法です。LSHでは、埋め込みベクトルを、類似度情報を保持したままハッシュ値に変換し、結果的にグラフや木を横断する代わりに、単純なハッシュテーブルのルックアップにより探索を行います。ハッシュ法の主な利点は、任意の次元数のベクトルを固定サイズのハッシュに変換できるため、精度を大きく損なうことなく検索時間を短縮できる点にあります。

一般的にデータのハッシュ化にはさまざまな手法があり、特に埋め込みベクトルを扱う際にも多様な方法が存在しますが、本記事ではそれぞれの詳細には深く踏み込みません。通常のハッシュ手法は、非常に類似したデータであってもまったく違うハッシュ値を生成してしまうのが普通です。埋め込みベクトルは float 値で構成されているので、たとえばベクトル演算上きわめて近い 0.73 と 0.74 という2つの float 値を例に、一般的なハッシュ関数に通した結果を見てみると、下表のように入力同士の類似度をまったく保持していないことが明らかです。

| ハッシュ関数 | 0.73                                        | 0.74                                        |
|:-----------:|:-------------------------------------------:|:-------------------------------------------:|
| MD5         | 1342129d04cd2924dd06cead4cf0a3ca            | 0aec1b15371bd979cfa66b0a50ebecc5            |
| SHA1        | 49d2c3e0e44bff838e1db571a121be5ea874e8d9     | a534e76482ade9d9fe4bff3035a7f31f2f363d77     |
| SHA256      | 99d03fc3771fe6848d675339fc49eeb1cb8d99a12e6358173336b99a2ec530ea | 5ecbc825ba5c16856edfdaf0abc5c6c41d0d8a9c508e34188239521dc7645663 |

従来のハッシュ法が類似データ間のハッシュの衝突を極力避けようとするのに対し、ローカリティセンシティブハッシュ（LSH）の主目的は正反対で、類似データが高い確率で同じバケットに格納されるよう、衝突をむしろ増やそうとします。こうすることで、多次元空間上で近い位置にある埋め込みベクトルが、同じバケットに収まる固定サイズのハッシュ値として表されます。LSHではこのようにハッシュ化されたベクトルでも互いの近さを保てるため、データのクラスタリングや近傍探索（nearest neighbor searches）に非常に便利な手法です。

ハッシュ計算の大部分は、インデックス作成時（ドキュメント登録時）に行われます。検索時にはクエリベクトルをハッシュ化して、同じバケットに入っている最も近い埋め込みベクトルをまず探すだけでよいのです。候補となるバケットが見つかったら、通常はそこからさらに2段階目の処理を行い、クエリベクトルに対して真に近いベクトルを特定します。

## 結論

ここまで、ベクトル検索を紹介するために多くの領域をカバーしてきました。レキシカル検索とベクトル検索の違いを比較し、ディープラーニングのニューラルネットワークがどのように非構造化データの意味を捉え、高次元の埋め込みベクトルに変換するかを学びました。また、埋め込みベクトルは各次元における類似度のシーケンスとして、データの意味を表現していること、そして、2つのベクトルが近ければ近いほど、セマンティックに類似した概念を表すことを理解しました。

さらに、ベクトル間の距離や類似度（L1, L2, Linf、コサイン類似度、内積）を計算する方法を紹介し、最後に、木、グラフ、クラスタ、ハッシュなどに基づく様々なベクトル検索アルゴリズムや技法を概観しました。これらの手法は、全探索のように全てのベクトルを対象とするのではなく、近傍に絞り込むことで、効率的な検索を実現するものです。

もしこの記事が気に入ったなら、以下のシリーズの他のパートもぜひチェックしてください：

- [パート2: Elasticsearchでのベクトル検索のセットアップ方法](https://www.elastic.co/search-labs/blog/vector-search-set-up-elasticsearch)  \([日本語訳](https://qiita.com/nobuhikosekiya/items/dbc86009f7a49a08843e)\)
- パート3: Elasticsearchを用いたハイブリッド検索（近日公開！）

実際にベクトル検索を体験してみたい方は、こちらの[セルフペース型ハンズオン](https://www.elastic.co/demo-gallery/vector-search)でSearch AIを試してみるか、[無料クラウドトライアル](https://cloud.elastic.co/registration?onboarding_token=search&cta=cloudregistration&tech=trial&plcmt=cross%20module&pg=search-labs)または[ローカル環境](https://github.com/elastic/start-local?cta=local-machine&tech=github&plcmt=cross%20module&pg=search-labs)で試してみることができます。