セマンティックサーチ(Semantic Search)をApache Luceneで検証 #ANN

はじめに

セマンティックサーチ(Semantic Search)が注目を浴びているようです。
全文検索ライブラリApache Luceneのデモモジュールを用いて、
近似最近傍探索(ANN)を使ったセマンティックサーチを行なってみました。

セマンティックサーチ(ベクトル検索)とは

セマンティックサーチとは

※ 引用元

ターム、クエリ、ドキュメントを表す、機械学習ベクトルの埋め込み(embeddings)に基づく検索
最新の検索エンジンにとって必須の機能になりつつある
その実現には、近似最近傍探索(ANN)を使用する

ベクトル検索とは

※ 引用元

機械学習 (ML) を活用して、テキストや画像などの非構造化データの意味とコンテキストを取得し、数値表現に変換
セマンティックサーチでよく使用されるベクトル検索は、近似最近傍探索(ANN)アルゴリズムを使用して類似データを検索
従来のキーワード検索と比較して、ベクトル検索はより関連性の高い結果をもたらし、より高速に実行される

近似最近傍探索(Approximate Nearest Neighbor, ANN)とは

最近傍探索(NNS)の派生
次元の呪いへの対策として最近特に人気がある

最近傍探索(Nearest neighbor search, NNS)とは

距離空間における最も近い点を探す最適化問題の一種、あるいはその解法
ドナルド・クヌースは、これを郵便局の問題で表した
- ある住所に最も近い郵便局を求める問題である
すなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題
多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される
低次元の場合と高次元の場合で異なるアルゴリズムがとられる

Apache Lucene でベクトル埋め込み(embeddings)の操作方法

`Apache Lucene`デモモジュールの説明

ベクトル埋め込み(embeddings)の操作

IndexFilesとSearchFilesは、テキストのインデックス作成と検索に加えて、「埋め込み」と呼ばれる、テキストから派生した数値ベクトルのインデックス作成と検索も行うことができる
このデモコードは、パブリックドメインにあるGloVeプロジェクトによって提供される事前計算された埋め込みを使用する
ここで使用する辞書は、完全なGloVeデータセットの小さなサブセット
- トイ・データセット(Toy dataset)に出現する単語のみが含まれており、本番環境で使用できない
- このコードを使用してより大きなドキュメントセットのベクトルインデックスを作成すると、インデクサーは例外をスロー
  - 完全な埋め込みセットが必要になるため

必要なパッケージ

org.apache.lucene.demo
- インデックス作成と検索のデモアプリケーション
org.apache.lucene.demo.facet
- ファーセットユーザガイドとデモ
org.apache.lucene.demo.knn
- KnnVectorのサンプルコード

セマンティックサーチの検証手順

検証環境

macOS 11.6 Big Sur
Apache Lucene: 9.5.0
Java SE Development Kit 19

`Java SE Development Kit 19`をインストール

以下イメージファイルをダウンロードしてから、インストールします。

`Apache Lucene`をインストール

Lucene 9.5.0 ディストリビューションをダウンロードしてから、作業ディレクトリに展開します。

curl -L https://dlcdn.apache.org/lucene/java/9.5.0/lucene-9.5.0.tgz --output lucene-9.5.0.tgz
tar xvf lucene-9.5.0.tgz

`CLASSPATH`環境変数の設定

Terminalを開き、下記コマンドを使って環境変数を設定します。

export LUCENE_HOME=/users/foo/lucene/lucene-9.5.0
export LUCENE_MODULES=$LUCENE_HOME/modules
export CLASSPATH=$LUCENE_MODULES/lucene-core-9.5.0.jar:$LUCENE_MODULES/lucene-queryparser-9.5.0.jar:$LUCENE_MODULES/lucene-analysis-common-9.5.0.jar:$LUCENE_MODULES/lucene-demo-9.5.0.jar

`GloVe`プロジェクトから事前学習済みの単語ベクトルを入手

以下zipファイルをダウンロードしてから、$LUCENE_HOME/knn_dictディレクトリに展開します。

cd $LUCENE_HOME/knn_dict
unzip /tmp/glove.6B.zip
ls glove*

事前学習済みのファイルが四つ存在します。

glove.6B.100d.txt	glove.6B.200d.txt	glove.6B.300d.txt	glove.6B.50d.txt

インデックス作成

インデックス作成コマンドを実行します。

java org.apache.lucene.demo.IndexFiles -docs $LUCENE_HOME/docs -knn_dict $LUCENE_HOME/knn_dict/glove.6B.50d.txt

以下のようにインデックス作成が行われます。

INFO: Using MemorySegmentIndexInput with Java 19; to disable start with -Dorg.apache.lucene.store.MMapDirectory.enableMemorySegments=false
adding /users/foo/lucene/lucene-9.5.0/docs/benchmark/constant-values.html
adding /users/foo/lucene/lucene-9.5.0/docs/benchmark/overview-tree.html
adding /users/foo/lucene/lucene-9.5.0/docs/benchmark/index.html
... 中略 ...
adding /users/foo/lucene/lucene-9.5.0/docs/facet/help-doc.html
adding /users/foo/lucene/lucene-9.5.0/docs/facet/element-list
Indexed 7421 documents in 11589 ms

indexディレクトリにknn-dict.fst,knn-dict.binが生成されます。

ls -lrt index/
total 217128
-rw-r--r--  1 root  staff   5256747 Apr  3 08:14 knn-dict.fst
-rw-r--r--  1 root  staff  80000204 Apr  3 08:14 knn-dict.bin
-rw-r--r--  1 root  staff         0 Apr  3 08:14 write.lock
-rw-r--r--  1 root  staff       626 Apr  3 08:14 _0.cfe
-rw-r--r--  1 root  staff  10351317 Apr  3 08:14 _0.cfs
-rw-r--r--  1 root  staff       322 Apr  3 08:14 _0.si
-rw-r--r--  1 root  staff       626 Apr  3 08:14 _1.cfe
-rw-r--r--  1 root  staff  10113434 Apr  3 08:14 _1.cfs
-rw-r--r--  1 root  staff       322 Apr  3 08:14 _1.si
-rw-r--r--  1 root  staff       236 Apr  3 08:14 segments_1

検索

試しに、キーワードbookでセマンティックサーチを行なってみます。
knn_vectorオプションでknnHits値を1に指定します。

java org.apache.lucene.demo.SearchFiles -knn_vector 1

Enter query:に、bookと入力します。
KnnFloatVectorQueryによる検索が行われ、ドキュメントが8件ヒットします。

Apr 03, 2023 8:37:47 AM org.apache.lucene.store.MemorySegmentIndexInputProvider <init>
INFO: Using MemorySegmentIndexInput with Java 19; to disable start with -Dorg.apache.lucene.store.MMapDirectory.enableMemorySegments=false
Enter query:
book
Searching for: book KnnFloatVectorQuery:contents-vector[0.0,...][1]
8 total matching documents
1. /users/foo/lucene/lucene-9.5.0/docs/grouping/org/apache/lucene/search/grouping/package-summary.html
2. /users/foo/lucene/lucene-9.5.0/docs/memory/org/apache/lucene/index/memory/MemoryIndex.html
3. /users/foo/lucene/lucene-9.5.0/docs/facet/org/apache/lucene/facet/taxonomy/package-summary.html
4. /users/foo/lucene/lucene-9.5.0/docs/demo/org/apache/lucene/demo/facet/package-summary.html
5. /users/foo/lucene/lucene-9.5.0/docs/queryparser/org/apache/lucene/queryparser/flexible/core/nodes/OpaqueQueryNode.html
6. /users/foo/lucene/lucene-9.5.0/docs/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html
7. /users/foo/lucene/lucene-9.5.0/docs/benchmark/constant-values.html
8. /users/foo/lucene/lucene-9.5.0/docs/changes/Changes.html
Press (q)uit or enter number to jump to a page.

おわりに

全文検索ライブラリApache Luceneを使って、セマンティックサーチを行なってみました。
デモはテキストベースですので、画像検索なども試してみようと思います。

セマンティックサーチ(Semantic Search)をApache Luceneで検証