Vald(NGT)の検索チューニングのすゝめ
はじめに
背景
Hybrid Searchの検証の事前検証でVald単体での精度検証を行ったところ、検索精度が著しく低い現象が見られました。
精度の低い状態ですと、Hybrid Searchが検索精度にどの程度影響を与えているかどうかを正確に判断することが難しくなります。
そこで、正しい影響具合を観測するためにも、まずはVald単体で検索精度を改善するためのパラメータチューニングを行うことにしました。
チューニングにあたり、検索パフォーマンスに焦点を当てたTuning Guidelineを作成し、これに沿ってチューニングを行いました。
デフォルトパラメータの改善
以前よりValdで設定しているデフォルトパラメータを利用した場合、他のライブラリ・エンジンに比べて精度が出ないというユーザーからのフィードバックを受けていました。
利用するデータによって精度は変化するためチューニングが不要になるわけではありませんが、デフォルトパラメータを改善することは課題として捉えていました。
Valdをより使いやすく、様々なユースケースで利用してもらいたいため、デフォルトパラメータの改善にも今回の検証の中で取り組むことにしました。
検索パラメータチューニング
パラメータチューニングは以下のように進めました。
- Linear Search(全件探索/k-NN)での精度検証
- 検索精度を向上させるためのパラメータ調整
- 要求する検索速度を満たすためのパラメータ調整(
timeout=3sの条件で十分な精度が出たため、今回は未実施)
まず、Linear Searchによる精度検証を行ったところ検索精度に問題ないことが確認できました。
ここで、初めにLinear Searchの検証を行った理由ですが、Vald Agent(NGT)におけるLinear Searchは実質的にk-Nearest Neighbor(k-NN)であるためです。
k-NNの全てのindexデータとクエリとの距離を計算し、最も近いk個の点を予測するという特性から、Linear Searchを用いることで、ANNに対して実質的に最大精度を得ることができます。
そのため、ベクトル化などに問題がないか、きちんと精度が出る余地があるか等を確認する上でも、パラメータチューニングの初期段階として、Linear Searchを行うことをチームで推奨しています。
次に、ValdのANNの検索精度に影響を与えるパラメータを変化させながらチューニングを行っていきます。
精度検証
本検証では、Hybrid Searchの検証と同様にデータセットとしてMS MARCO passage(train: 8.84M, val: 6980)、ベクトル化するためのモデルとしてSentence-BERTを使用しました。
Vald Agent(NGT)の検索に影響を与えるパラメータは、radius, epsilon, timeout, create_edge_size, search_edge_sizeの5つになります。
各パラメータの簡単な説明は以下のとおりです:
- radius: 探索範囲を指定するパラメータです。この値により、indexグラフ上で、クエリから一定距離(radius)以内に存在し、その最近傍から昇順で指定された検索数k個分のデータを取得します。-1を指定した場合はfloatの最大値を指定したことと同値になります。
- epsilon: 探索精度を調整するパラメータです。indexグラフ上で、(radiusとは異なる)検索時の探索円の半径を(1+epsilon)倍する数値で、その探索円を用いてグラフを探索します。大きいほど探索精度が上がる可能性がある代わりに、探索時間が長くなります。検索数kが最大値になっている場合には探索円の半径はradiusと同値になります。
- k: 検索結果として返す数を指定するパラメータです。検索結果には指定されたradiusよりも大きい距離のデータは返却されないため、得られたデータの数が指定したkを下回る可能性があります。
- creation edge: indexグラフ作成時の各ノードの出力edge数を指定するパラメータです。大きいほど精度が上がる可能性がありますが、index構築時の処理時間が長くなります。
- search edge: 検索時に用いられるindexグラフのedge数です。大きいほど検索精度が向上する可能性がありますが、検索時の処理時間が長くなります。0を指定した場合には、各ノードに付与されている全てのedgeを利用して検索します。
パラメータに関してさらに詳しく知りたい方はNGT wikiを参照してください。
上記のうち、本検証ではVald(v1.7.8)を対象に、epsilon、creation edge、search edgeの3つパラメータを変化させチューニングを行っていきます。
今回のチューニングは2つの検証に分けて行いました。
まずは、creation edgeとsearch edgeのそれぞれを200/100/50/25と大まかに変化させたときの性能を確認しました(検証1)。
次に、検証1で選定した大まかなパラメータを更に細かい範囲で変化させたときの性能を検証しました(検証2)。
epsilonに関しては、両検証とも0.01/0.05/0.1の3パターンそれぞれの性能を検証しました。
検証1
検証1では、大まかにcreation edgeとsearch edgeを変化させそれぞれの検索結果について評価していきます。
検証を行った検索パラメータとエッジサイズペアはそれぞれ以下の表の通りになります。
| radius | epsilon | timeout | k |
|---|---|---|---|
| -1 | 0.01 | 3s | 1,000 |
| -1 | 0.05 | 3s | 1,000 |
| -1 | 0.1 | 3s | 1,000 |
| creation_edge size | search_edge size |
|---|---|
| 25 | 25 |
| 25 | 200 |
| 50 | 50 |
| 50 | 200 |
| 100 | 100 |
| 100 | 200 |
| 200 | 25 |
| 200 | 50 |
| 200 | 100 |
| 200 | 200 |
検証結果を以下のグラフに示します。
Time/Recallのグラフ
Time/NDCGのグラフ
Search Edge/Recallのグラフ
Search Edge/NDCGのグラフ
上記の結果から、エッジサイズは50から100の間で十分に検索精度を出すことが可能であることがわかりました。
検証2
検証2では、検証1の結果を元にエッジサイズの範囲を狭めながら更に細かく検証を行います。
パラメータセットは以下のとおりです。
| radius | epsilon | timeout | k |
|---|---|---|---|
| -1 | 0.01 | 3s | 1,000 |
| -1 | 0.05 | 3s | 1,000 |
| -1 | 0.1 | 3s | 1,000 |
| creation_edge size | search_edge size |
|---|---|
| 50 | 50 |
| 50 | 75 |
| 75 | 50 |
| 75 | 75 |
| 75 | 100 |
| 100 | 75 |
| 100 | 100 |
結果を以下のグラフに示します。
Time/Recallのグラフ
Time/NDCGのグラフ
Search Edge/Recallのグラフ
Search Edge/NDCGのグラフ
Search Edge/Timeのグラフ
Creation Edge/Recallのグラフ
Creation Edge/NDCGのグラフ
Creation Edge/Timeのグラフ
上記の結果から、creation edge sizeとsearch edge sizeのペアは{50, 75}, {75, 100}あたりが検索精度・検索速度の観点で優れていることが確認できました。
加えて、本検証の結果から検索精度・検索速度・必要とされるリソースを考慮した上で、どのようなデータセットでもある程度の精度を出すことが期待できるようepsilon=0.05、creation edge=50、search edge=50をそれぞれ新しいデフォルトパラメータとして設定しました。
考察
それぞれの実験から、全体的にcreation edge・search edgeを問わずedge数を増やすことで検索精度が向上する傾向にあることが分かります。
また、edge数の増加に伴い検索時に探索するノード数も増加するため、全体の検索時間も増加することも読み取ることができます。
しかし、c100s100（creation edge: 100, search edge: 100）より、c50s75やc75s100の結果が検索精度・検索時間で優れていることから、単純にedge数を増やせば良い結果が得られるわけでもないことも分かりました。
search edgeを固定してcreation edgeを増減する視点から見た時間・精度について
Search Edge/Timeのグラフから、同一search edge上では多くの部分でグラフが被っています。
このことから、creation edgeサイズによる検索時間の差は、ほとんどないことが分かります。
つまり、creation edgeが検索時間の増減に影響を与えることは比較的少なく、search edgeが支配的であると考えられます。
Search Edge/Recall(NDCG)のグラフからは、search edge数が大きいほど検索精度が高く、epsilonの変化による精度の差も小さいことが分かります。
そのため、十分大きいsearch edge上では、epsilonを小さくして検索を行うことで、精度と時間両方の面で良い結果となるようValdを運用することが可能だと考えられます。
creation edgeを固定してsearch edgeを増減する視点から見た時間・精度について
前述とは逆に、Creation Edge/Timeのグラフでは、グラフとして被っている部分は比較的少なく、差分も大きいことが分かります。
このことから、同一creation edge上ではsearch edgeの大きさに応じて時間変化が大きいものと考えることができます
つまり、creation edgeは検索時間に対して支配的なパラメータではないと考えられます。
Search Edge/Recall(NDCG)のグラフからは、creation edge数が増加するほど検索精度の下限は増加していることが分かります。
検索精度の大きな影響を与えるのはSearch edgeではあるものの、Creation Edgeもある程度大きい値に設定することで検索精度の下限を高めることができる可能性があると考えられます。
c50s75・c75s100の性能が良い
creation edge・search edgeの増減に伴う考察は以上の通りではありますが、本実験ではc50s75・c75s100が単純なedge数の増加に伴う精度向上とは異なる形で、時間的にも精度的のもより良い結果を示しています。
中でも、c50s75が驚くほど良い性能を示していることが分かります。
これは、creation edge・search edgeがともに「ある程度の閾値」で上限に達していると考えられます。
閾値の上限以上にedge数を増やすと、検索時の探索ノード数が増加による検索時間の増加と検索結果へのノイズの混入による検索精度の悪化が起きていると考えられます。
ここで述べた「ある程度の閾値」は、それぞれのデータセットやモデルなどのベクトル化手法によって異なるため、一概に決定することはできません。
本実験では、creation edgeが50程度を最低値として、creation edgeとsearch edgeを2:3の比率での設定が最も性能を引き出せるパラメータであったと考えられます。
c200s50がNDCGで一部Linear Searchの性能を上回っている件
Time/NGCGのグラフにおいて、c200s50の性能がLinear Searchの性能を一部上回っていることが確認できました。
他の性能はLinear Searchを上限として精度が推移しているのに対し、この結果がだけが異質なものとなっています。
これは、ベクトルと距離関数での正の結果と、データセット的に正しいと関連付けられた正の結果が乖離している場合があるために起こった可能性が考えられます。
今回の実験では、c200s50の設定で得られた検索結果がたまたまLinear SearchよりもNDCGの指標に関して望ましい結果となるような検索順位の変動があったため、このようなグラフになったと考えられます。
また、s100c50のグラフと比較しても同じ傾きのまま精度が向上しており、この設定にはまだまだ秘密が隠れているのかもしれません。
おわりに
本記事ではVald(NGT)での検索性能向上のためのチューニング方法について実際に行った例を上げながら解説しました。
検証結果として、edge数に比例して検索精度が向上し、search edgeとepsilonに関しては更に検索時間が増加することが分かりました。
また、search edge数が検索精度・検索時間両面で一番支配的であることも確認できました。
上記に加えて、課題であったデフォルトパラメータについても言及しました。
各種精度(Recall/NDCG)や検索時間・利用者のコンピュートリソースや最初の使用感などをチーム内で議論し、コストパフォーマンスが良さそうなeplison 0.5、creation edge 50、search edge 50を新たなデフォルトパラメータとして選定しました。
これらを踏まえ、Valdのepsilonとcreation edge・search edgeの関係性について簡単に考察を述べました。
あくまで一つの例ではありますが、チューニングの際の参考になれば幸いです。
チューニングに関しては本記事とTuning Guidelineを参考に是非とも挑戦してみてください。
この記事が参考になったという方はぜひリアクションをお願いします。
（GitHub Starもお待ちしています😄）
Documents
Valdの更に詳しい内容については、下記ドキュメントを参考にしてください。
Slack
質問等がありましたら、下記Slack WSに投稿してください。
また、ValdへのContributionもいつでもお待ちしています。
Medium
Mediumでblog(英語)を公開しているので、こちらも是非ご覧ください。
X
公式Xアカウントはこちら
Discussion