ブラウザにおけるセマンティック/ハイブリッド検索
Semantic/Hybrid Search in the Browser (bart.degoe.de)
要約
この記事では、ブラウザ上で動作する軽量なセマンティック検索の実装方法について解説しています。従来のキーワード検索と、サーバーサイドで動作する重厚なセマンティック検索エンジンのギャップを埋めるため、モデルサイズを大幅に削減したlookupテーブル方式のモデル(model2vec)を活用します。これにより、クライアントサイドでAPIサーバーなしに高度な検索機能を提供する方法を探求しています。
全文翻訳
クライアントサイドのセマンティック検索を静的サイトに
この記事を音声で聞く
0:00 / 0:00
[音声: Your browser does not support the audio element]
8年前、私はこのブログにLunr.jsでクライアントサイド検索を追加しました。これはビルド時に逆インデックスを作成し、JSONとして配信し、ブラウザ内で文字列を照合します。サーバーサイドのエンジンは不要です。投稿に実際に含まれる単語を入力すれば投稿が見つかる、という意味では、それ以来問題なく動作していました。
今年の初めに、私はPythonで約250行のセマンティック検索エンジンを開発しました(「ロンドンのビール洪水」を「イングランドでのアルコール飲料災害」と検索しても見つけられるような、ビールがアルコール飲料であり、洪水が災害であることを理解するタイプのもの)。それはsentence-transformersと数百MBのPyTorchをインストールしたマシンを必要とします。そのようなものを本番サーバーで提供するには、高価なRAMを搭載した高性能なマシンが必要です。ブラウザのタブで実行できるものではありません。
そのため、このブログにはどこでも動作するが何も理解しないキーワード検索はありましたが、物事を理解するが静的サイトの近くではどこでも実行できないセマンティック検索はありませんでした。この記事は、そのギャップを埋めることについてです:サーバーもAPIも一切不要で、モデル全体が基本的に4MBのルックアップテーブルである、完全にブラウザで動作するセマンティック検索です。私がベンチマークした3つのモデルすべてを、さらに下で、あなたのハードウェア上でライブ実行できます(私はGPUクラスターを所有できません)。
これを行うことで、いくつかのことが明らかになりました。最も重要なのは、キーワード検索に数年間バグがあったことです。適切な評価を行うことが重要であることが判明しました。
明らかなアプローチは23メガバイトかかる
Pythonの記事を支えるモデル(all-MiniLM-L6-v2のようなsentence-transformers)は、事実上ブラウザで実行できます。Transformers.jsは、そのONNXビルドをダウンロードし、WebAssembly上で実行します。私はそれをベンチマークしましたが、私のラップトップでは、量子化されたモデルとそのランタイムは、ワイヤー上で23.45MBで、ロードされて利用可能になるまで約2秒かかり、その後クエリを約18ミリ秒で埋め込みます。
14個の投稿しかないブログに検索ボックスのクエリを埋め込むには、23メガバイトは少し多いです。これは、派手な検索のためにダウンロードする必要があるバイト数で、高解像度の写真の約ダース分に相当します。動作はしますが、一部のアプリケーションでは完全に価値があります。しかし、ブルームフィルターについて読もうとした人に、特にモバイル接続で、それを押し付けるようなものではありません。
重要なのは、検索クエリを埋め込むためにトランスフォーマーは必要ないということです。十分な性能を持つベクトルが必要なだけで、それを得るにははるかに安価な方法があります。
静的埋め込みモデルはルックアップテーブルである
トリックは、model2vecと呼ばれるモデルファミリー(特定のモデルは「potion」と呼ばれます)です。これらは実際のsentence-transformerから蒸留されていますが、結果はニューラルネットワークではありません。それはテーブルです。
これがモデルの完全なフォワードパスです。簡略化ではありません――ライブラリのソースから、すべてです:
ids = tokenize(text) # サブワードトークンIDに分割
rows = embedding[ids] # トークンごとに1つのベクトルをルックアップ
vector = rows.mean(axis=0) # 平均を取る
vector = vector / norm(vector) # 単位長に正規化
これだけです。トークン化、トークンごとの行のルックアップ、平均化、正規化。アテンションも、レイヤーも、推論もありません。「モデルの実行」は、数回の配列ルックアップと平均化です。potion-base-8Mの場合、テーブルは29,528トークン×256次元のfloat32(約30MB)で、MiniLMの検索品質の81%に達しますが、定義上は辞書ルックアップです。
30メガバイトはまだ多すぎますが、テーブルはトランスフォーマーよりも縮小しやすいものです。
インデックスの構築:チャンキングと、決して元を取れないキャッシュ
埋め込みはビルド時に生成されます。私のラップトップでは、hugoを実行するたびに、Pythonスクリプトが投稿をウォークスルーし、フロントマターとコードブロックを削除し、各投稿を重複する600文字程度のチャンクに分割し、各チャンクを埋め込み、ユーザーが検索入力ボックスをクリックしたときにダウンロードされるファイルにベクトルを書き込みます。
チャンキングは予想以上に重要です。なぜなら、平均化ステップがあるからです。静的埋め込みは、トークンベクトルの平均であり、15,000文字の投稿全体を1つのベクトルに平均化すると、「ソフトウェアに関する一般的な英語の文章」を指すものになり、それ以上のものにはなりません。まれで特徴的な単語(pydubやmmh3のような用語)は、それらを囲む何百もの普通の単語に埋もれてしまいます。投稿をより小さなチャンクに分割すると、これらの信号をシャープに保つのに役立ちます。これは後で戻ってきます。なぜ一部のモデルが他のモデルを上回るかの鍵であることが判明するからです。
また、各チャンクのテキストのハッシュをキーとする埋め込みキャッシュも構築しました。これにより、再埋め込みは変更されたチャンクのみに触れます。これは時間とトークンの無駄であることが判明しました。このブログのすべてのチャンクを埋め込むのは、数百回のルックアップと平均化です。約10ミリ秒かかります。私は、すでにほぼ瞬時の操作を高速化するためにキャッシュを構築しました(14個のブログ投稿はそれほど多くのデータではないことが判明しました)。MiniLMモデルでは、埋め込みが実際のニューラルネットワークフォワードパスであるため、これはより重要になりますが、私はそれを配信していません。そのため、キャッシュはそこにあり、正しく、無意味ですが、過剰設計は簡単であるというリマインダーとして残しておきました。
テーブルの縮小:モデルのストップワードリストは目の前に隠されている
テーブルが30MBなのはfloat32だからです。それをint8に量子化すると、サイズは4分の1になります。ただし、すべてを同じスケールにクリップするだけではうまくいかず、なぜうまくいかないのかを理解することは、これを構築する上で私が最も気に入ったことの1つでした。
行の大きさ(magnitude)が実際にはどうなっているかを見てみましょう。potion-base-8Mのすべてのトークンをベクトルの長さでソートすると、最も短いベクトル(つまり、ゼロに近いもの)は次のようになります:
a . , - ) the to and of in
そして最も長いのは次のとおりです:
turkmenistan seychelles guantanamo hemingway vanuatu
これは偶然でもノイズでもありません。モデルのストップワードリストは、その行の大きさです。 トークンベクトルを平均化すると、小さなベクトルを持つ単語は結果をほとんど動かさず、大きなベクトルを持つ単語はそれを支配します。モデルは、ストップワードリストや特別な処理なしに、「the」のような単語はほとんど貢献せず、「guantanamo」のような単語は大きく貢献すべきだと学習しました。それはかなり美しいことで、その幾何学の中にあります。
だからこそ、量子化には行ごとのスケールが必要です。各トークンは独自のfloat32乗数を受け取るため、相対的な大きさがint8に押しつぶされても生き残ります。しかし、実際にはそれほど重要ではないことが判明しました。
私はそれを測定しました。実際のテーブルを単一のグローバルスケールで量子化し、クエリベクトルがどれだけ劣化するかをチェックしました。答えは次のとおりです:ほとんどありません。元のベクトルに対する集計コサイン類似度は0.9998のままでした。グローバルスケールは、29,528トークンの語彙全体で2つの行(.とa)をゼロにします。これらは、モデルがすでにほとんど貢献しないと判断した2つのトークンです。メカニズムは本物ですが、この特定のモデルでは重要ではありません。
行ごとのスケールは保持しました。なぜなら、4MBのうち118KBしかかからず、正しいからです。しかし、「負荷を支える」というよりは「安価な保険」のようなものです。int8テーブル全体、行ごとのスケールを含めても、元のfloat32モデルをコサインで0.999958まで再現します。モデルではなくルックアップテーブルをブラウザに出荷するには十分です。
WordPieceを80行で、そしてその3つの落とし穴
ブラウザにはトークンテーブルがありますが、Pythonでやったのと同じように、入力されたクエリをトークンIDに変換する必要があります。そうすれば、正しい行をルックアップできます。つまり、BERT WordPieceトークナイザーをJavaScriptで再実装する必要があります。約80行で、それぞれがクエリベクトルを静かに汚染する可能性のある3つの落とし穴があります:
[CLS]/[SEP]なし。 BERTトークナイザーは通常、テキストを特別なマーカートークンでラップします。tokenizer.jsonの設定にも、その説明セクションがあります。model2vecはそれを使用しませんが、代わりにadd_special_tokens=Falseでトークナイザーを呼び出します。マーカーを追加すると、存在しない2つのベクトルを平均化することになります。- 未知のトークンは削除され、埋め込まれません。 単語が語彙にない場合、
model2vecは[UNK]ベクトルに置き換えるのではなく、シーケンスから完全に削除します。したがって、完全に意味不明な単語で構成されたクエリは、空のトークンリストとゼロベクトルを生成し、ゼロ除算の代わりにそれを処理する必要があります。(実際にはこれはほとんど到達不能です。29,528トークンの語彙では、すべての文字が語彙に含まれているため、それをトリガーする唯一の方法は100文字を超える単語です。) "strip_accents": nullは、アクセントがストリップされることを意味します。 これは少し厄介です。設定ではstrip_accentsはnullであり、「オフ」のように読めます。しかし、HuggingFaceのトークナイザーライブラリでは、null値はlowercase設定から継承され、これはオンです。したがって、caféはcafeになります。設定を文字通りコピーした場合、アクセント付きのすべてのクエリがずれます。
いくつかのフラストレーションと、Claudeによって生成された多くのテスト文字列(pydub、café naïve、C++ vs C#、日本語のみ)の後、私はJSトークナイザーがBERT WordPieceトークナイザーと一致すると reasonably confident です。
検索は数百回のドット積である
クエリが埋め込まれると、検索はほぼあっけなく終わります。数百個のチャンクベクトル(すべての投稿の各チャンクに1つ)があります。それらすべてに対するコサイン類似度を計算することは、それぞれ128個の数値の数百回のドット積、数万回の乗算・加算であり、比較的モダンなマシンのブラウザはミリ秒の数分の一で実行します。その後、チャンクを投稿ごとにグループ化し、各投稿の最もスコアの高いチャンクを取得し、ソートします。私のマシン(M1 MacBook Air)では、クエリ全体(トークン化、埋め込み、すべてのチャンクのスコアリング、ランキング)は約0.4ミリ秒かかります。
本番環境では、ここで近似最近傍インデックス(HNSWなど)を使用します。数兆個のドキュメントがある場合は、それを使用すべきです。数百個の場合、ANNインデックスはブルートフォースループよりも遅く、ディスク上ではるかに大きくなります。「ベクトル検索」が複雑なデータベースシステムではなく、単なるforループであると明言する価値があります。
これらを構築する際に知っておくと役立つことが1つあります。ドキュメントベクトルはint8として保存されます。コサイン類似度は正のスケールに対して不変であり、ドキュメント行列はグローバルスケールを使用するため、ブラウザはfloat32クエリを生のint8バイトに対して直接ドット積して、アン量子化することなく正しいランキングを取得できます。しかし、JavaScriptでのint8 × int8はサイレントにオーバーフローします。真の値が300万であるドット積が、エラーや警告なしに-64として返されます。そのため、通常のfloatに累積する方が良いです。これはデバッグするのが楽しかったので言及します1。
それぞれが異なる方法で盲目な2つの検索エンジン
セマンティック検索を追加する前に、責任あることをしようと思い、既存のキーワード検索が実際にどれほど悪いかを測定し、それを上回るベースラインを得ようと思いました。Claudeに30個のテストクエリのセットを作成させ、3種類に分けました:
- 正確なトークン:
pydub、lunr、mmh3、papermod。投稿に文字通り現れる単語。 - 言い換え:「投稿が使用する単語ではなく、意味によってドキュメントを見つける」。投稿が使用する単語とは異なる言葉での概念。
- ナビゲーション:「静的サイトに検索を追加するにはどうすればよいか」。広範な意図。
キーワード検索は、正確なトークンでは間違いなく成功し、言い換えでは失敗するでしょう。それから実行しましたが、pydubで失敗しました。
pydubは、私が以前の投稿で使用したPythonライブラリです。その単語は、テキスト読み上げの投稿にそのまま含まれています。そして、このブログが使用しているあいまい検索ライブラリであるFuse.jsは、何も返しませんでした。設定でFuseがフィールドの開始付近の照合のみをスコアリングするように指示していたことが判明しました。これはlocationと呼ばれる設定で、distanceウィンドウは1000文字でした。pydubは、その投稿の約3,700文字の地点で最初に現れ、ウィンドウの外にあったため、検索ボックスにとっては存在しないも同然でした。mmh3も同様で、長い投稿の奥深くに偶然現れた特徴的な単語も同様でした。機能した単語は、タイトルに含まれていたため機能しただけでした。
私のキーワード検索は長年静かに壊れていましたが、それをベンチマークしようとしていたときに初めて気づきました。ドジです。
そして、2つのエンジンは、まさに補完的な方法で盲目であることが判明しました:
| キーワードで見つかる | セマンティックで見つかる | |
|---|---|---|
pydub (正確なトークン、語彙外) | ✅ | ❌ |
| 「意味でドキュメントを見つける」 (言い換え) | ❌ | ✅ |
キーワード検索は正確なトークンでは完璧で、言い換えについては何も返しません。悪い結果ではなく、結果がゼロです。セマンティック検索は鏡像です。言い換えは完璧にこなし、固有名詞でつまずきます。なぜなら、pydubは語彙になく、無意味なサブワードフラグメントに粉砕されるからです。どちらも優れていません。それらは互いに異なるセットで失敗します。
Reciprocal Rank Fusion、または:異なる検索結果セットをマージする方法
各エンジンが相手の見落としを捉えるなら、両方が欲しいでしょう。問題はそれらを組み合わせることです。キーワード検索はあいまい一致の距離を返し、ベクトル検索はコサイン類似度を返します。これらは異なるスケールにあり、意味が異なります。それらを平均化することは無意味です。温度と重さを足すようなものです。
ここでの答えはReciprocal Rank Fusionです。両方のインデックスに対してクエリを実行し、スコアを完全に破棄して、ランクのみを保持します。各ドキュメントの「融合スコア」は、両方のエンジンにわたる1 / (k + rank)の合計です。ここでkは慣習的に60です。一方のエンジンで1位にランク付けされ、もう一方ではランク付けされなかったドキュメントは1/61のスコアになります。両方のエンジンで3位にランク付けされたドキュメントは1/63 + 1/63となり、より大きくなります。kは、曲線の上部を平坦化するため、「両方のエンジンがこれをかなり気に入った」が「一方のエンジンはそれを愛した」を上回ります。これは、一方のエンジンが言い換えに盲目で、もう一方が固有名詞に盲目である場合にまさに望むことです。コードは10行程度で、単一のパラメータがあり、 sensible なデフォルト値があり、比較できない2つのスコアを比較する必要はありません。このブログを検索すると、キーワードとセマンティックがランクで融合されたものが実行されます。これは、ランク付けされたリストの多くのソースに簡単に拡張できます。
ベンチマーク:あなたのハードウェアで実行する必要があります
私は3つのクエリエンコーダーをベンチマークしました:私が説明してきたmodel2vecルックアップテーブル、transformers.js経由のMiniLM q8、そしてternlightです。これは巧妙なBitNetスタイルの三項モデルで、WebAssemblyにコンパイルされており、当初はこの道を歩むきっかけとなりました。
下のウィジェットは、これら3つすべてをあなたのブラウザで、あなたのハードウェア上で実行します。なぜなら、結局のところ、それが重要なことだからです。それぞれに独自の実行ボタンがあります。なぜなら、そのうちの1つは23MBをダウンロードし、接続でそれを支払うかどうかはあなたが決めるべきだからです。ダウンロードサイズは私が測定した定数です(ブラウザは、正しいヘッダーを送信しないクロスオリジンダウンロードのサイズを見ることができません)。タイミングはあなたのデバイス上でライブです。
私のラップトップでは、話はかなり明確です:ルックアップテーブルは4.2MBで、クエリを3分の1ミリ秒で埋め込みます。MiniLMは23.5MBで18ミリ秒です。ternlightはその間に位置します。そして、30個のラベル付きクエリ全体で測定された検索品質では、ルックアップテーブルはMiniLMと同じくらい良好なスコアです。同じくらい良好です。5分の1のサイズと約50倍の速度で。
ただし、その主張には注意が必要です。30個のクエリは小さなサンプルであり、私はそれに2回騙されそうになりました。
メトリックは何も見ることができなかった
当初、ヘッドラインメトリックはrecall@3でした:関連する投稿がトップ3に入ったか?13投稿のコーパスでは、「13個中のトップ3」はそれほど高いハードルではありません(ランダム推測で約4分の1の確率でクリアできます)。そして、ほとんどすべてのモデルがほとんどすべてのクエリでそれをクリアしたことが判明しました。5つの異なる構成が正確に0.978でタイしました。Recall@3は、4MBのルックアップテーブルと23MBのトランスフォーマーを区別できませんでした。
さらに悪いことに、それは自信に満ちたナンセンスを生み出しました。純粋なセマンティック検索は、正確なトークンクエリで完璧な1.000をスコアリングしました。それは毎回pydubを見つけたようです。しかし、実際にはそうではありませんでした:
pydub → 1. Free SSL on GitHub Pages (間違い)
2. Let's Encrypt on GitHub Pages (間違い)
3. Text-to-Speech with pydub (正しい)
正しい投稿は3番目にあり、完全に無関係な2つの投稿の後ろにあります。そしてrecall@3はそれをヒットとしてスコアリングしました。メトリックは、モデルが正しい回答を、それがそこに着地したことがほとんど意味をなさなかったほど広いバケットに着地させたことを評価していました。recall@1(「最初の結果は正しいか?」)に切り替えることで、モデルをより明確に分離し、異なるストーリーを語りました。学んだ教訓:メトリックがあなたが気にしているものを見ることができないなら、メトリックは無価値です。結果が良すぎたので、私はそれに気づきました。
何が出荷され、それを盗む方法
ホームページの検索ボックスは現在、キーワード、セマンティック、ハイブリッド検索を実行しており、トグルで比較して、それらがどのように意見が異なるかを見ることができます。pydubと入力し、セマンティックモードに切り替えて、それが間違った答えを得るのを見てください。ハイブリッドに切り替えて、それが再び正しくなるのを見てください。すべては4MBのルックアップテーブル、小さなドキュメントインデックス、そして約300行の依存関係のないJavaScriptで構成されており、検索ボックスにフォーカスしたときにのみ遅延ロードされるため、ページ自体は何も負担しません。
ビルドパイプライン(チャンキング、量子化、評価ハーネスなど)は、独自のサイトを指すことができるPythonパッケージです:
pip install static-site-search-eval
sss-eval build --corpus content/post --outdir static/search \
--model minishlab/potion-base-8M --dims 128 --chunk-size 600
コードはGitHubにあります。30個の評価クエリもそこに含まれているので、自分で試すことができます。携帯電話でセルラー経由で上記のベンチマークを実行すると、おそらく23MBを感じ、ルックアップテーブルが手間をかける価値があった理由を理解するでしょう。
- All time classic https://www.destroyallsoftware.com/talks/wat ↩︎