本記事でやること

私が最近読んだQuery Auto-Completion(以下QAC)をテーマにしたテックブログを列挙し、簡易的なまとめを記載します。

対象読者

検索窓に入力されたクエリの続きを提示する機能(Query Auto-Completion)の改善事例や文献を探している方

概要

タイトル	企業名	執筆年	簡単なまとめ
Autosuggestion services in web search	Microsoft	2022	QACの一般的な改善手法がまとまっています。さらに、改善を評価するための指標がいくつか紹介されています。
AutoSuggest Retrieval & Ranking(Part2)	OLX Group	2022	OLX Groupで実践された、入力クエリと提案するクエリのマッチングアルゴリズムやランキングアルゴリズムの改善方法を紹介しています。
How Instacart Uses Machine Learning-Driven Autocomplete to Help People Fill Their Carts	tech-at-instacart	2022	instacartで実践された、QAC機能の改善事例がいくつか紹介されています。ランキングアルゴリズムの改善以外に、スペルミスの吸収や意味が重複するキーワードの削除などが紹介されています。
A better way to search for music through query suggestion	Deezer	2020	Deezerで採用されていたインスタント検索をQACに置き換えた話が紹介されています。また、ランキングアルゴリズムを改善した上でABテストを実践し、その際採用した評価指標も紹介されています。

Autosuggestion services in web search

入力されたクエリとサジェスト候補キーワードの関連性の改善

QACは、ユーザーの検索クエリのログから人気があるキーワードを提案するだけではない

パーソナライズ

使用言語によるパーソナライズ
- ユーザーが使用している言語の種類によって、提案するクエリを出し分ける
- 文字の種類が異なる言語間では自動翻訳を行う

時系列イベントによるパーソナライズ
- スポーツや政治などのイベントは周期性を持つので、この周期性を利用し提案するクエリを予測し生成する
ユーザーの検索履歴に基づくパーソナライズ
- 例えば、「アベンジャーズ」や「キャプテン・アメリカ」を過去に検索したユーザーが検索窓に「マーク」と入力した時は、「マークザッカーバーグ」ではなく「マーク・ラファロ」を一番上に表示すべき
- ユーザーの過去の検索履歴を通じて、各ユーザーを表現するようなエンドツーエンドの自然言語モデルを利用する

多様性

同じ意味を持つ冗長なクエリを減らし、QACの多様化を目指す

新規性

急速に人気を集めているトレンドワードをピックアップしQACにより提案することでユーザーが最新情報を把握できるようにする

カバレッジの向上

スペルミスによってキーワードが表示されない問題を解決するために、検索クエリとのプレフィックスマッチによってマッチしたキーワードではなく、スペル修正メカニズムを持った非プレフィックスマッチによるキーワードを提案する方が良いかもしれない

その他機能

質問に対する回答の表示
- 計算式などを入力すると解答が得られる
ゴースティング
- ユーザーが検索窓にクエリを入力中にクリックする確率が高いと判断したキーワードを自動的に入力する

未入力時の提案
- 検索窓に何も入力されていない時に検索履歴やトレンドワードなどを提案する

評価指標

Mean Reciprocal Rank (MRR)
- Q: 評価セット内の全てのユーザークエリ (q)
- rank_q: クエリqがQACに表示された際のランキング

評価セット内のユーザークエリがQACにてより上位に表示されたことを重視する評価指標

Success Rate at TopK (SR@K)
- ユーザーの検索意図を満たすキーワードが上位K位以内にある平均比率
α-nDCG
- QACがより多様なワードを提示できているかを評価するために使用するnDCGを拡張した指標。
- 詳細は「Diversifying Query Auto-Completion」を参照

AutoSuggest Retrieval & Ranking(Part2)

改善前のアルゴリズム

当社が保有しているマスタデータのようなもの(商品カテゴリーなど)から提案するクエリを生成していた

問題点

ユーザーがどのように検索しているのかが考慮されていない
どのサジェスト候補がよりクリックに繋がるのか考慮されていない

改善後

提案するクエリはユーザーの過去の検索クエリを利用する
検索クエリの出現頻度を加味したランキングアルゴリズムを利用する

マッチングアルゴリズム

3つのアルゴリズムによってマッチするワードを探す(ex: 入力クエリ("scoote")
1. Infix match: クエリと前方一致 (ex: scooter)
2. Blended Infix match: クエリ内の任意のタームと前方一致(ex: electric scooter)
3. Fuzzy match: クエリのk番目の文字列と前方一致(ex: scooty)

ランキングアルゴリズム

上記3つのマッチングアルゴリズムによってマッチしたワードの出現回数に対してそれぞれ減衰係数を掛けスコアを計算する

Query=scoote	match word	Frequency	Decayed Frequency
Infix match	scooter	1800	1800
Blended Infix match	elactric scooter	1200	1200/2
Fuzzy match	scooty	600	600/3

上記の結果からソート順は (scooter, 1800), (electric scooter, 600), (scooty, 200)となる

A/Bテスト

いくつかの国毎にA/Bテストを実施し0件ヒット率が減少したこと、QACが提案したクエリの採用率、コンバージョン率が上昇した

How Instacart Uses Machine Learning-Driven Autocomplete to Help People Fill Their Carts

提案するクエリの生成方法

ユーザーの過去の検索ログを利用している
以下のようなフィルタリングをクエリに適用している
1. 不適切な単語の除外
2. 当社特有の語彙などの除外
3. 長すぎるキーワードの除外
4. 重複するキーワードの除外
  1. "egg", "eggs"があった場合、人気なワードを残す

スペルミスの処理

Fuzzy matchingを利用しユーザーのスペルミスを吸収し適切なクエリを提案している
Fuzzy matchを利用することで、QACのエンゲージメント向上、コンバージョンを発生させたクエリ割合の向上を実現した

重複削除

意味的に同じキーワードが表示されることがある
- "fresh bananas", "bananas fresh"など
重複を削除することで多様なワードを表示することができる
Search Embeddingモデルを用いて重複削除に取り組んだ
- クエリと商品の関連性を利用し予め訓練されたクエリのembeddingを利用しクエリ間の類似度を計算する

ランキングアルゴリズム

元々は人気なクエリを上位に表示するようにしていた

Autocomplete Engagement Model

機械学習モデルを利用したランキングアルゴリズムを作成した
- QACのログを訓練データとし、提案されたクエリへのクリックを正例、その他を負例と定義
- 二値分類問題として解く
- 特徴量
  - ac_conversion_rate: 該当のクエリがクリックされた割合
  - ac_skip_rate: 該当のクエリが上位に表示されたがエンゲージ(クリック)されていない割合
  - is_start_match: 該当のクエリがprefix matchでヒットしたかどうか
  - is_fuzzy_match: 該当のクエリがfuzzy matchでヒットしたかどうか
  - has_thumbnail: 該当のクエリが表示される際にサムネイルを持っているかどうか
  - normalized_popurarity: 該当のクエリの（正規化済み）人気度

Multi-objective Ranking

QACに対するユーザーのエンゲージメントを最適化するモデルとカート追加を最適化するモデルを併せたモデルを作成した
- QACが提案したクエリがクリックされ、その検索クエリからカート追加が発生した時にユーザーの検索意図を理解したと定義する
ユーザーのエンゲージメントを最適化するモデルは前項で説明した"Autocomplete Engagement Model"を利用する
カート追加最適化モデルはQACから検索されたクエリによって商品がカートに追加されたかどうかの二値分類問題として扱う

カート追加を最適化するモデル(Add to Cart model)は、検索窓に入力されたクエリ(prefix)に依存しないという仮定を置いている
- QACの検索ログだけではなく全検索ログの特徴量を利用することができる
カート追加モデルの特徴量
- Search Conversion Rate: 該当ワードの過去N日間のコンバージョン率(=コンバージョン数 / 検索された回数)
- Add to Cart Rate: 該当ワードの過去N日間のカート追加率(=カート追加数/検索された回数)
- Zero Result Rate / Low Result Rate: 該当ワードの過去N日間の０件ヒット率もしくは検索結果数が少数であった割合

A better way to search for music through query suggestion

改善前

検索窓にクエリを入力するたびに検索結果を表示するインスタント検索を提供していた
検索体験を阻害しているという理由でインスタント検索をやめることにした
- Google検索が2010年にインスタント検索を削除した際の調査結果を参考にした

新しい検索体験

以下の要素を備えたQACを開発した
1. 実際の検索クエリや音楽のメタデータから提案するクエリを生成する
2. ユーザーの国に応じて提案するクエリをローカライズする
3. ユーザーの好みに応じて提案するクエリをパーソナライズする
4. ユーザーの検索履歴を表示する
5. 関連するクエリを提案する
以下のようなデザインパターンに従った
1. 提案するクエリは最大10個までにする
2. 入力されたクエリと提案するクエリの差分はハイライトする
3. ユーザーがカーソルを合わせたクエリをハイライトする
4. 検索履歴を表示する
5. 境界線は多用しすぎないようにする

入力クエリとドキュメントとのマッチングアルゴリズムはprefix matchよりもexact matchを重視するようなアルゴリズムを開発した
検索順位を決めるランキングアルゴリズムは、BM25と視聴回数から算出される人気度を組み合わせた

A/Bテスト

新しいUX, 新しいランキングアルゴリズムにてABテストを行った
A/Bテストの評価指標は以下3つ
1. Ranked Half-Life(RHL) indicator
  1. 関連するアイテムがどの程度の頻度で検索結果の上位に表示されたかを示す指標
2. Success indicator
  2. セッションの最後にクエリをクリックした検索セッション
3. Effort indicator
  3. ユーザーがクエリを入力する時間、クエリを入力してからクリックするまでの時間

おわりに

QACに関する日本語の文献は数が少なく他社事例を収集するのが大変な中、今回扱ったテックブログは具体的かつ応用できそうな内容が多くとても勉強になりました。著者の方々には感謝です。
また、QACを評価する指標に関しても学びが多く、引用されている論文などを時間があるときに読もうと思います。
この記事が自分のようにQACの文献を探している方の参考になれば幸いです。