この記事は何か
Cai, Fei, and Maarten De Rijke. Query auto completion in information retrieval. Universiteit van Amsterdam [Host], 2016.の簡単なまとめとそれを読んで考えたことを書いたものです。
アムステルダム大学でQuery Auto Completion を専攻した方の博士論文でした。
検索入力フォームのQuery Auto Completion(以降、QACと略します) をこれから作る人の参考になれば、と思いQiitaに残します。検索窓に「あ」と入力すると「明日の天気」などの検索キーワード（クエリ）がサジェストされるやつのことです。
なぜ読もうと思ったか
以下の理由からなります。
- 博士論文であるため、背景や前提の記述が手厚いだろうと想像できたため（教科書になるほどメジャーなテーマではなさそう or 枯れてなさそうな場合、初学者はレビュー論文や博士論文をまず目を通します）
- 博士論文であるため、かなり厳しくチェックの目が入っていると想像できたため（偏見ですが）
- 被引用数が100件以上あったため（100件が多いかは分野によるため、一概に言えませんが少なくても「少なすぎる」ということはなさそうでした）
- 2016年のものなので、少し古いかもしれないが、まずは基本的なベースラインとその考え方をちゃんと理解したかったため
なにが書いてあったか
元論文は162ページもある大作なので、ここでは簡単に私が学びたかった（初学者にとって特に有益であろう内容）ことを軸にまとめます。公開データセットの詳細や著者の提案手法の詳細などは元論文を参照してください。
ここでは、下記の4つにわけてまとめます
- QACの問題設定
- QACの評価実験について
- QACの標準的なアルゴリズム（いわゆる先行研究のレビュー）
- 著者のQACの改良方法とその改善幅
画像はすべて元論文からの引用です。
QACの問題設定
prefix (接頭語、userが入力したい検索キーワードの部分文字列。だいたいの場合は先頭文字列)が与えられた時に、膨大なquery log により作られたindex に検索をかけて、完全な検索キーワードの集合（query completions）を獲得し、online ranking behavior (検索時刻や場所、その他サイト内行動やuserに関連する属性情報などなど)を特徴量にしたランキングアルゴリズムによる並び替えを実施し、そのtop k件（執筆時点でのGoogle検索ではk=9）をuserに返す、というのがQACの要件です。
queryが与えられ、documentsのindexに検索をかけ、諸々の情報による並び替えをし、そのtop k件をuserに返却する、いわゆる検索一覧画面(Search Engine Result Page;SERP)を取得する問題設定と非常に似通っていることがよくわかります。本論文ではこれをDocument Retrieval(DRと称する)とよんでいます。
両者ともに、入力に合致する集合を獲得し（本記事ではこの働きをfilterとよぶ）その集合を並び替える（本記事ではこの働きをsortと呼ぶ）点で一致しています。
対比するとこのようになります。
QACのMajor Metricsに見慣れない指標が並んでいますが、DRのそれと大きくは変わらない思想で作られています（後述）
本論文ではfiletr機能ではなく、sort機能に焦点が当てられています。
QACの評価実験について
論文では公開データセットが使われることがほとんどです（非公開のindustory dataでは先行研究とフェアな比較ができないため）
本論文ではMSN検索からのログであるAOLとNetherlands Institute for Sound and Vision(SnVと称されていた)の2つを利用していました。
また、基本的に評価指標はMRRが用いられ、これはRR〜QACで返したquery completions のうち使われたqueryのランク位置の逆数、ランク位置が小さい程大きな数字を返し（一番上だったら１を返す）、どれも用いられなかったら0を返す〜を全てのprefixで平均をとったものです。
QACの結果が用いられたか否か、を最重視し、top k件に正解が含まれる割合を計算するSR@kも使用されています。
また、結果の多様性を考慮した評価実験も本論文では一部実施しており、それにはα-nDCG@Nが用いられています。
これは nDCG@k を $A_p$ (アスペクト、DRではdocuments, QACではqueryをカテゴリに分類したもの)ごとに計算する形で拡張したもので、仮にアスペクトが偏った結果になった場合は一番右の $(1-α)$ が指数的に減少するため(αは0から1の範囲)結果が悪化するようになっています。(nDCG@kは有名な指標なので別文献〜例えばApache Solr入門第３版の９章〜をご参照ください(ダイマ))
QACの標準的なアルゴリズム（いわゆる先行研究のレビュー）
おおざっぱに、timeに焦点をあてたものと、userに焦点をあてたものの2種類に分かれる、と書かれてあります。
この論文の執筆当時は両者のアルゴリズムは別々に作られていたため、この2つの統合しオフラインテストでの成績を改善させたことが本論文の成果の１つとされています。
time に焦点をあてたもの
もっとも単純なranking algorithmは「prefixに前方一致したqueryのうち、出現頻度が多い順に返す」となります（Bar-Yossef and Kraus, 2011）
このアルゴリズムが本論文でもBaseline（いわゆるベンチマーク）に使われています。
ただし、この方法だと
1. 人気急上昇キーワード
1. 季節性（周期性）キーワード
が過小評価されるため、いくつか改良が考えられています
人気急上昇キーワードの対策は非常にシンプルで、直近のログだけで集計すれば多少は改善されます。本論文のベンチマークにもそれが使われています。下記の表はMPR（後述）でAOLとSnVという２つの公開データセットで、「どのくらい直近のログを使用するか」の違いを評価したものです。
MPRは1が最高のスコアで、#pはprefixが何文字与えられた状態なのか（これが増えるとMPRは向上する）で、MPC-ALLが全期間のログを集計したverで、MPC-R-xdays が直近x日のログを集計したver で、O-MPC-Rがxの部分をデータから最適化したver です。
ここから下記の2点がわかります
1. データセットによって最適な時間幅が違う
1. 全期間使うよりも直近で絞った方が良さそう
季節性（周期性）キーワードは、週間（平日や休日など）月間（月初や月末など）年間（盆や正月など）によって検索キーワードのトレンドが変わる場合に考慮するものです。
私の経験上、サービスのドメインに大きく依存しますが、検索キーワードの出現回数のトレンドになんらかしらの周期性はかなりみられます。
こんな感じで、yをあるキーワードの出現頻度数とし、周期性をTと置いた場合に、Fで急上昇人気ワード、Sで季節性キーワードを考慮するといったtime series analysis 的な方法も提唱されています。
userに焦点を当てたもの
ユーザーの過去の検索行動などの行動ログやデバイス情報などからcontext を推定し、そのcontext に近い結果を返します。たとえばcontext をベクトル表現にしたのならクエリの方もベクトル化し、下記のように内積が大きいものを最終結果にします。
どんな特徴量を使うの？とか、どんなモデルを使うの？とかは様々みたいです。
Learning to Rank の枠組みでの研究では、userに焦点を当てたモデルが中心になっているそうです
著者のQACの改良方法とその改善幅
時間ベースとパーソナライズのアルゴリズムを統合した
過去では、バラバラに研究されていたtimeに焦点を当てたアルゴリズム（ここでは時間ベースと称します）とuserに焦点を当てたそれ（ここではパーソナライズと称します）を統合したアルゴリズムを提唱しました。非常にシンプルにそれぞれの結果を正規化し、重み付け線形和にしたものです。
TSとあるのが時間ベースで、Pがパーソナライズ、γはハイパーパラメータです
これを導入した結果、ベンチマークのO-MPC-Rと比べてMRRで0.03~0.07くらいの改善を示しました。
また、ハイパーパラメータγも最適化した結果、0.04~0.09くらいの改善になりました。
クエリの意味的類似度を考慮したもの
Queryの言語的特徴をranking algorithmの特徴量（素性とも）にした場合に、当時の最先端のQACモデルと比べてSR@kで9%も改善しました。
言語的特徴はWordNetやPOSデータを駆使したラベリング、クエリ内での共起、クエリ出現頻度の時間的類似性、クエリログやGoogleNewsからのw2vなど様々なものが用いられてました。
改善にもっとも寄与したものはクエリログからのw2vでした。
研究はもう２つほどありますが、上記２つほど改善幅が大きくない上に仮定とアプローチが複雑なため割愛します。興味ある方はぜひ元の論文をご参照ください。
読んで考えたこと
QACのアカデミアでの王道（？）の考え方を踏まえた上で、「こうしたらいいんじゃね？」を書きます
まずは集計ベースで十分そう
確かに改善はしていますが、非常に単純なBaseline(適当な時間窓でのログ集計)と比較しても劇的とは言えない改善幅なので、実装や分析の手間暇を考えると、適当な時間窓でのクエリの出現頻度を集計をするだけでも良さそうな印象をうけました。
ただし、サービスや利用者の特性によっては
- エリアや商品ジャンルなどによってクエリの出現頻度が全然違う（エリアはレジャー施設の検索、ジャンルはECサイトなど）
- 急上昇キーワードが重要（在庫が限られているフリマアプリなど）
- 季節性キーワードが重要（年間イベントに左右されやすい贈呈品の検索など）
が重要な場合があるので、その場合は
- エリアや商品ジャンルによって集計を分ける
- 出現頻度の前日までとの差分をスコアに反映させる
- 昨年同日（同週？同月？）の出現頻度をスコアに反映させる
といったアドホックな対応が良さそうです。（あくまで経験論です）
どう集計をわけるかは実際にログ集計結果が変わるかで判断する、スコアへの反映は先行研究通りの線形和（いわゆるバギング）にし重みのハイパーパラメータはある程度探索する、くらいで十分な印象があります。
なぜ、このような印象を受けたかは、次に述べる「QACのオフライン性能評価とユーザー体験の向上やビジネス上の実利の関係に距離がありそう」からです。
QACのオフライン性能評価とユーザー体験の向上やビジネス上の実利の関係に距離がありそう
本論文ではQACの性能を「QACの結果のQuery completionsで実際に選ばれるか、選ばれた場合に上位に位置していたか」で評価していましたが、この部分がユーザー体験の向上に寄与するためには一般的に
1. 知りたい情報を見つけられたか
1. ゴールにたどりつくための知見が得られたか
のどちらかを満たす体験にならなければなりません。（参考 検索体験を向上する Query Understanding とは）
知りたい情報を見つけられたか、の観点で言えば、QACではDRのSERP到達までを支援しているだけで、DR側でその目標を達成しなければなりません（QACとDRの連携については後述）
ゴールにたどりつくための知見が得られたか、は確かにQACによって解決できる可能性がある課題ですが、MRRやSR@kでは単に入力を省略できた場合と知見が得られた場合とが区別できません。
また、QACはあくまで工学なので、その技術選定にはビジネス上の実利との関係性も無視できません。SERPに到達することで広告が表示され、それが企業の利益になる検索エンジンサービスならば、かなり直接的な関係になります。一方で、ECサイトや予約サイトの場合はSERPから購入や予約完了のコンバージョンにまでならず、「知りたい情報を見つけられたか」と同じくDRやクレジットカードの入力フォームといった後続の機能や画面でQACの性能の結果が希釈されます。
これらのことからQACのオフライン性能の10%未満の改善が、その労力に見合うものかの考慮は必要そうです。
ただし、QACだけの性能評価だけでなく、DRとの連動させたアルゴリズム改善の場合は、より大きな価値がある可能性があります。
QACとDRの連携が重要そう
まずDRのsort機能が極めて重要なのは自明とします (Googleが天下をとった大きな要因でもあります)
その上で、DRのsort機能を補完するためにQACが活用できるのはないか？についていくつかのアイデアを書きます。参照した文献が2016年のもののため、すでにあちこちで言われている内容かもしれません。私のサーベイ不足が悪いのですが、もし良い文献を知っている方はコメント等で教えていただけると大変ありがたいです
QACのranking algorithm をクエリ出現頻度ではなく、そのクエリからの実利に基づいて作る
先行研究の時間ベースの手法はクエリ出現頻度に基づいていましたが、これは評価指標がMRRやSR@kであるためだと思われます。仮に実利（ECサイトだとクエリごとの購入金額など）を目標にした場合は、それをranking algorithmの主要な特徴量にするのは自然な発想かと思われます。
するとDRでのSERPがユーザーにとってもより良いものになるクエリがQACで優先されるようになるはずです。
QACとDRで特徴量を連携する
本論文でのQACに特に有益な特徴量はユーザーのcontextとクエリの言語情報（クエリログからのw2vなど)でした。これはDRにとっても同じく有益であると考えられます。
特にクエリの言語情報は、DR側で同義語扱いされているクエリ群をQACで別々に提示する、といったナンセンスな事態をさけるためにもQACとDRで共有した方が明らかに良いです。
DRのSERPをユーザーのcontextによって変えて良いかは（１）公平性（２）SERPのシェア可能性の2点から疑問がありますが、SERP内の広告やリコメンド結果がユーザーのcontextによって変わることは許容される傾向にあるので可能かもしれません。また、プライバシー意識の高まりから、ブラウザやスマホアプリでのユーザーのトラッキングが年々厳しくなっているためユーザーのcontext推定の可能性や重要度は低下傾向にあるように思われます。
と、色々と書きましたが、この辺は全部机上の空論なので、A/Bテストでもして見ない限りは確かなことは言えません。A/Bテストのやり方ですが、A/Bテスト実践ガイドのメトリクスの考え方や分析方法を参照することをオススメします(2回目のダイマ)。QACに特化した内容ではありませんが、これで十分かと思われます。
A/Bテストに頼るだけではなく、統計的因果推論の方法論による介入効果の推定が有益な予感もあり調査中です。良い文献あったらコメント等で教えていただけると本当にありがたいです。
前方一致検索+シンプルなranking algorithmなら実装のコアはluceneベースの全文検索エンジンで良さそう
全文検索エンジンのSolrやElasticsearchにはEdge-Ngramというtokenizerが用意されており(Solr ver ,Elasticsearch ver )、前方一致検索を高速で実現するための転置インデックスを簡単に利用することができます。
また、エリアやジャンルごとの集計結果をindexに格納するだけでなく、前日比較結果や前年同日の結果をindexにもち、それをfunction score queryで参照し、ハイパーパラメータの部分をクエリで表現すれば、ハイパーパラメータの探索を変更範囲を局所化した形で実施できます。prefixの種類やuser contextによってハイパーパラメータを変えてみるのも有益かもしれません。これも全文検索エンジンのクエリに変更を局所化できれば実現は容易になります。
終わりに
本論文のようながっつりとした調査・研究があり、それが公開されているおかげで「何が役立ちそうか」についてかなり具体的に思いを馳せることができました。
最後の方で色々と好き勝手なことを言っていますが、これはアカデミアの研究として成立させるためには過去のベンチマークとの評価指標を揃える必要があったり、総合的にどうこうではなく要素に着目して性能をしっかりと確認することこそが重要だったりと、実際に産業応用する場合と重視するポイントが違うためかと思います。
非常に勉強になりました、著者の方には大感謝です。