【初心者】ベクトル検索について調べてみた

# 背景・目的
最近、AWSのWhat's new で下記の通りベクトル検索関連のリリースが立て続けに発表されていました。
詳細を整理したいと思います。

- [Vector engine for Amazon OpenSearch Serverless now generally available](https://aws.amazon.com/about-aws/whats-new/2023/11/amazon-opensearch-serverless-vector-engine/)
- [AWS announces vector search for Amazon MemoryDB for Redis (Preview)](https://aws.amazon.com/about-aws/whats-new/2023/11/vector-search-amazon-memorydb-redis-preview/)
- [AWS announces vector search for Amazon DocumentDB](https://aws.amazon.com/about-aws/whats-new/2023/11/vector-search-amazon-documentdb/)

# まとめ
- ベクトルは、数値の羅列
    - 数値の組み合わせにより、特定のトピックと類似性を定義する。
- ANN=近似最近傍探索
    - 検索時間を短縮可能
- VQ=ベクトル量子化
    - ベクトル空間を複数のグループに分割し、各グループを表す「コードワード」を定義し、検索する。
    - 検索速度を飛躍的に向上させる技術
    - ANNアルゴリズムに必要不可欠。
        - RDBや全文検索によりインデックスが必要と同等
- エンベディング=ベクトル表現
    - エンべディングは、多くはディープラーニングが使用される
    - 単語やテキスト以外でも使用されてる
- セマンティックマッチングシステム　の例
    - レコメンデーション エンジン
    - 検索エンジン
    - 広告ターゲティング システム
    - 画像分類または画像検索
    - テキスト分類
    - 質問への回答
    - チャットボット
- セマンティック マッチングのパラダイム
    - アイテムのエンベディング表現を生成する
    - エンベディングに対して最近傍探索を実行する


# 概要
## あらゆるデータの瞬時アクセスを実現する Google のベクトル検索技術
GCPのブログ記事「[あらゆるデータの瞬時アクセスを実現する Google のベクトル検索技術](https://cloud.google.com/blog/ja/topics/developers-practitioners/find-anything-blazingly-fast-googles-vector-search-technology)」で

Google Cloudのパートナー会社が[MatchIt Fast](https://matchit.magellanic-clouds.com/)を公開したとのこと。
[Wikimedia](https://commons.wikimedia.org/wiki/Category:Images) や [the GDELT project](https://www.gdeltproject.org/) などにある大規模公開データの中から、選択したサンプルに類似した画像やテキストを数ミリ秒で見つけ出すことが可能とのこと。


1. デモを試してみるため、MatchIt Fastに遷移し、「Start」をクリックします。
    <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/7b1f440e-6f1c-5b33-3be9-ac47bc701ebd.png" width=400/>

1. 「News Similarity Search」をクリックします。
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/65ebbfe8-2e78-a543-904a-9d5ad91f968b.png)

1. 「Who is Japan's current Prime Minister?」と入力し、「Query」をクリックします。
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/eec43646-06f5-cf3f-25b0-66509f744ef0.png)

1. 検索結果が表示されました。ハングル等はじめ他の言語のニュースなど表示されました。 菅首相の記事が多いようです。
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/5454f71d-5366-a053-2933-1a8c2800ece9.png)

### ベクトル検索：Google 検索、YouTube、 Google Play などを支える技術
> これほど速い検索をどのようにして実現しているのでしょうか？　その秘密は、Vertex AI Matching Engine のベクトル検索機能にあります。Vertex AI Matching Engine は、Google Image Search、YouTube、Google Play などで世界中の Google ユーザーに何十億ものレコメンデーションや情報検索を提供しているものと同じベクトル検索のバックエンドを利用しています。この技術は、Google のコアサービスの最も重要なコンポーネントの一つです。ディープニューラルネットワーク（DNN）の発展にともない、Google に限らずコンテンツ検索や情報検索に依存する多くの一般的なウェブサービスに不可欠なコンポーネントになりつつあります。

- ベクトル検索エンジンがポイント
- Googleのサービスでもベクトル検索を利用している

> では、従来のキーワードベースの検索とベクトル検索の違いは何でしょうか？　従来、ITシステムの情報検索基盤はリレーショナル データベースと全文検索エンジンでした。これらの技術では、例えばコンテンツ（画像やテキスト）の一部やエンティティ（商品、ユーザ、IoT デバイスなど）に対して”movie”、”music”、”actor”などのようなタグやカテゴリーキーワードを付与し、それらのレコードをデータベースに保存します。そうすることで、それらのタグやキーワードで検索できるようにしています。

> これに対し、ベクトル検索ではコンテンツの表現と検索にベクトル（数値の羅列）を使用します。数値の組み合わせによって、特定のトピックとの類似性を定義します。例えば、ある画像（またはその他のコンテンツ）に映画に関する内容が 10 %、音楽が 2 %、俳優が 30 %含まれていた時、シンプルにそれを表すと[0.1, 0.02, 0.3]というベクトルを定義できます（このあとで説明するように、実際のベクトルはもっと複雑なベクトル空間を持っています）。このように作られたベクトル同士の距離や類似性を比較することで、似たコンテンツを見つけることができます。Google のサービスは、このベクトル検索の技術を使用することで、世界中の多様なユーザにとって価値のあるコンテンツを数ミリ秒で見つけ出しているのです。


- キーワード検索と、ベクトル検索の違い
    - キーワード検索は、タグやカテゴリキーワードを付与して、それらのレコードをDBに保存する
    - ベクトル検索は、コンテンツの表現と検索にベクトルを使用する。
        - ベクトルは、数値の羅列
        - 数値の組合わせにより、特定のトピックと類似性を定義する。
- ベクトル検索技術を使用し、数ミリ秒で検索している

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/a63b6400-4cf1-9ee1-7c11-6f309e5ebc83.png" width=300 />
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/40dc8c32-de45-4895-913f-593cb6ee3a5d.png" width=333 />

キーワード検索では、各コンテンツに紐付けられる属性として、映画かどうか、音楽かどうかなど、イチゼロで指定することになります。これはコンテンツの実際の”意味”を表現しているわけではありません。そのため、例えば”films”というキーワードで検索した場合、同じ意味を持つ”movies”がタグ付けされたコンテンツも本来検索対象に含めて欲しいところですが、キーワード検索ではヒットしません。キーワード検索でこれを改善したい場合、”films”と”movies”の2つの用語を明示的に結びつける辞書をデータベースや検索エンジンで持つ必要があります。コンテンツの実際の”意味”を十分に表せる表現力がありません。

> ベクトル検索では、微妙なニュアンスや意味に基づき、コンテンツをより洗練された方法で見つけ出せます。キーワード検索のように各要素が独立しているわけではなく、ベクトル全体でコンテンツの意味が表現されるので、”films”、”movies”、”cinema”をまとめたコンテンツの意味を表現することができます。また、ベクトルはこれらの属性値の組み合わせに傾向や特徴が表れ、新しいカテゴリーとして捉えることもできます。つまり、これまでサービス提供者が知らなかった、あるいは定義されていなかったカテゴリーを表現する柔軟性を備えています。例えば、ASMR やスライムなど、おもに子供に人気のあるコンテンツの新しいカテゴリーは、大人やマーケティング担当者が事前に予測することは非常に難しくうえ、膨大なデータベースを遡って手動で新しいラベルに更新することは、非常に時間がかかりす。一方、ベクトルはこれまでにないカテゴリーをも瞬時に捉え表現できます。

- ベクトル検索では、微妙なニュアンスや意味で検索する。
- キーワード検索とは異なり、各要素が独立していないので、ベクトル全体で値の組み合わせで表現される。つまり新しいカテゴリとして捉える。柔軟であること。

### ベクトル検索がビジネスを変える
> ベクトル検索は画像やテキストといったコンテンツだけに利用可能な技術ではありません。ベクトル表現を定義できるあらゆるビジネスデータの情報検索に適用できます。いくつか例を挙げてみましょう。
> - 類似ユーザーの発見：ユーザのアクティビティや購買履歴、その他のユーザ属性を組み合わせてベクトルを定義することで、指定したユーザーに類似した傾向を持つユーザを見つけ出せます。例えば、似たような商品を購入しているユーザー、ボットと疑われるユーザー、デジタルマーケティングの対象としたい優良顧客ユーザーなどを見つけられます。
> - 類似した製品やアイテムを見つける：商品説明、価格、販売場所などの製品の特徴から生成されたベクトルを使うことで、特徴の類似した製品を見つけ、様々な顧客の質問に答えられます。例えば、「この製品に似ていて、同じユースケースで使える他の製品はありますか？」、「この地域で過去24時間に売れた製品は？」などの検索に有用なツールとなり得ます。
> - 欠陥のある IoT デバイスの発見：欠陥のある機器の特徴を信号から捉え、そのベクトルで検索することで、同じように欠陥の可能性がある機器を瞬時に見つけ出し、事前のメンテナンスを行えます。
> - 広告レコメンド：ここの広告とユーザーに対して適宜作成されたベクトルにより、ユーザーにとって最も関連性が高く適切な広告を数ミリ秒という速さで見つけることができます。
> - セキュリティの脅威を発見：Web サービスやネットワーク機器に対するコンピュータウイルスのバイナリやマルウェアの振る舞いパターンのシグネチャをベクトル化することで、セキュリティ上の脅威を発見できます。
> - ここまで紹介してきたもの以外にも、ベクトル検索は、今後数年のうちにあらゆる業界で何千もの多様な用途に適用され、リレーショナル データベースと同じくらい重要な技術になるでしょう。

- ベクトル検索であらゆるビジネスデータの情報検索に適用可能。下記に整理する。


|ユースケース | 概要| 例|
|:--|:--|:--|
|類似ユーザの発見：似たようなユーザを見つけることができる。|類似製品、アイテムの検索：商品説明、価格、販売場所などの製品の特徴から生成されたベクトルを使い、類似した製品を見つける。|似たような商品を購入しているユーザー、ボットと疑われるユーザー、デジタルマーケティングの対象としたい優良顧客ユーザーなどの検索|
| 類似した製品やアイテムの発見|商品説明、価格、販売場所などの製品の特徴から生成されたベクトルを使うことで、特徴の類似した製品を見つけ、様々な顧客の質問に回答する。|この製品に似ていて、同じユースケースで使える他の製品はありますか？などの検索|
|欠陥のある IoT デバイスの発見|欠陥のある機器の特徴を信号から捉え、そのベクトルで検索することで、同じように欠陥の可能性がある機器を瞬時に見つけ出し、事前のメンテナンスを行う||
|広告レコメンド|この広告とユーザーに対して適宜作成されたベクトルにより、ユーザーにとって最も関連性が高く適切な広告を数ミリ秒という速さで見つけることができる。|
| セキュリティの脅威を発見|Web サービスやネットワーク機器に対するコンピュータウイルスのバイナリやマルウェアの振る舞いパターンのシグネチャをベクトル化することで、セキュリティ上の脅威を発見する|

- 今後、RDBと同じくらい利用される。

> ここまで聞くと、ベクトル検索は非常に強力な技術に聞こえます。しかし、この技術を実際のビジネスのユースケースに適用する上での大きな課題は何でしょうか？　実は2つあります。

> - ビジネスのユースケースに適したベクトルの作成
> - 高速でスケーラブルなベクトル検索サービスの構築

課題は、ビジネスユースケースに適したベクトルの作成、高速でスケーラブルなベクトル検索サービスの構築

### Embeddings：ビジネスユースケースに適したベクトル
> 最初の課題は、ビジネス上のユースケースに適した、有用なベクトルを作ることです。この点では、深層学習の技術が威力を発揮します。Matchlt Fast のデモでは、画像からのベクトル抽出には事前学習された MobileNet v2 model を、テキストには Universal Sentence Encoder（USE）をそのまま使用しています。これらのモデルに生データを入力することで、データの「意味」の空間にマッピングされたベクトルである”embeddings（埋め込み表現）”を抽出できます。MobileNet ではパターンやテクスチャが似ている画像同士を embedding 空間の近くにマッピングし、USE ではトピックが似ているテキストを近くにマッピングします。

ビジネスユースケースに適したベクトル検索の課題に対する対応
- すでにあるモデルに生データを入力し、embeddingsを抽出可能

> 例えば、注意深く設計され、学習された機械学習モデルを使えば、映画を以下のような embedding 空間にマッピングできます。
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/bdeeb562-c5a6-7ebc-ad94-a1cae8ec1a66.png)

> ここで示した embedding 空間では、ユーザーは「その映画は子供向けか大人向けか」、「ブロックバスター映画かアート系映画か」という 2 つの次元に基づいて、おすすめの映画を見つけられます。もちろん、これは非常に単純な例ですが、他のケースでもビジネス要件にあった同様の embedding 空間があれば、モデルから抽出されたベクトルが表現するインサイトにより、推薦サービスや情報検索サービスでより優れたUXを提供できます。

- ビジネスユースケースにあったembedding空間を作れれば、モデルから抽出されたベクトルが表現された、レコメンデーションや検索サービスのUXを提供可能

> Embedding の作成方法については、Machine Learning Crash Course on Recommendation Systems が参考になります。また、ビジネスデータからより良い embedding を抽出する方法については、この記事の後半で紹介します。

### 高速でスケーラブルなベクトル検索サービスの構築
> ビジネスデータから有用なベクトル（embedding）を抽出できたなら、あとは類似するベクトルを検索するだけです。これは簡単そうに聞こえますが、実際にはそうではありません。ナイーブな手法によるベクトル検索を BigQuery で実装した場合の動作を見てみましょう。

> この動画から分かるとおり、100 万個のアイテムの中から類似したアイテムを見つけ出すのに約 20 秒かかっています。Matchlt Fast のデモと比較するとかなり見劣りします。BigQuery は業界で最も高速なデータウェアハウスサービスの一つですが、なぜベクトル検索にこれほどの時間がかかるのでしょうか？

> これは 2 つ目の課題である「高速でスケーラブルなベクトル検索エンジン」を構築することの難しさを示しています。ベクトル同士の類似性を計算する指標としては、L2 距離（ユークリッド距離）、コサイン類似度、内積が広く使われています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/4c5f14aa-01fe-ee2c-a7bc-df2e8301fcd8.png)


- 時間がかかるという課題。


> いずれの指標も一般的な方法で実装すると、ベクトルの総数を N、次元数を K とした時にO (NK)の計算量が必要になります。例えば、1024 次元のベクトルと検索対象のベクトル 1 M（100 万）個を比較した場合、計算回数は 1024 x 100 M = 1.02B（10億回）に比例したオーダーになります。これが 1 回の検索で全てのベクトルを調べるのに必要な計算量であり、上記 BigQuery のデモが時間がかかる理由でもあります。

- ベクトルの検索の計算量が多い。

> ベクトルを 1 つ 1 つ比較する代わりに、近似最近傍探索（ANN）を使うことで検索時間を短縮できます。多くの ANN アルゴリズムでは、ベクトル空間を複数のグループに分割し、各グループを表す「コードワード」を定義して、そのコードワードを使って検索するベクトル量子化（VQ）が用いられています。この VQ は、検索速度を飛躍的に向上させる技術であり、リレーショナル データベースや全文検索エンジンにインデックスが不可欠であるのと同様に、多くの ANN アルゴリズムに欠かせない技術となっています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206276/2f615de6-300e-4903-64fd-044f8df679cd.png)


- ANN=近似最近傍探索
    - 検索時間を短縮可能
- VQ=ベクトル量子化
    - ベクトル空間を複数のグループに分割し、各グループを表す「コードワード」を定義し、検索する。
    - 検索速度を飛躍的に向上させる技術
    - ANNアルゴリズムに必要不可欠。
        - RDBや全文検索によりインデックスが必要と同等

> 上図から分かるように、空間内のグループの数が増えると検索速度が低下し、精度が向上します。このトレードオフを改善すること、つまり、より短い遅延でより高い精度を得ることが、ANN アルゴリズムの重要な課題でした。


# 考察
今回は、ベクトル検索とはなにか？ベクトル検索のユースケース、構成要素の初歩の初歩を整理してみました。
まだまだ、理解ができてないので今後も継続して学習したいと思います。



# 参考

https://cloud.google.com/blog/ja/topics/developers-practitioners/find-anything-blazingly-fast-googles-vector-search-technology

https://matchit.magellanic-clouds.com/

https://github.com/groovenauts/MatchItFast/

https://commons.wikimedia.org/wiki/Category:Images

https://www.gdeltproject.org/

https://cloud.google.com/vertex-ai/docs/matching-engine/overview?hl=ja

https://www.kaggle.com/models/google/mobilenet-v2/frameworks/tensorFlow2/variations/100-224-feature-vector/versions/2?tfhub-redirect=true

https://www.kaggle.com/models?tfhub-redirect=true

https://developers.google.com/machine-learning/recommendation?hl=ja