Search shortcuts using click-through data
目的
Query suggestionはこれまで散々紹介しているので割愛．この論文では「似ているクエリ」を推薦するのではなく，ユーザの需要を満たしたクエリ(Successful)を推薦する．
類似度尺度
ユーザの一連のクエリ入力の課程をセッションとし，
と書く．またこれ以降
は省略して
と書く．セッションのi番目の要素を
と書く．セッションの集合を
とする．
続いて，なる関数を考える．これは，セッション
のi番目のクエリにおいてユーザが1つでも検索結果から何かページを開いていた場合1とする．
であるならば，セッション
をsatisfactoryであるとし，そうでなければunsatisfactoryとする．言い換えれば，セッションの最後のクエリでページを開いているかどうかである．
なる関数を考える．これはセッションを受け取り要素数k以下のクエリ集合を返す関数であり，k-way shortcutと呼ぶ．shortcut functionの集合を
とする．
次にheadとtailを定義する．headはセッション
の頭からt個のクエリ
であり，tail
はt+1個目から最後までのクエリ
である．
また，がsatisfactory sessionである時，k-way shortcut
と
の類似度は
である．つまりはセッションのクエリを先頭からt個受け取って，残りのクエリをhで予測したときの類似度というか正解数のスコア．
はマッチした位置mに対して重みをつけるのでこれを色々変えると結果が変わる．例えば
なクエリがあって，
，
だったとする．
なら，
となる．しかし
とすると
，
になる．この違いは，元のセッションで
が後半に配置されているので，後ろに着ているクエリがマッチするほど類似度が高い，といった意図が反映されたためこのようになっている．
手法
手法としては古典的な協調フィルタリングとアドホックな手法を提案している．
協調フィルタリング
通常の協調フィルタリングではユーザ - アイテムで行列を作る．今回の問題に適用するため，セッションをユーザ，クエリをアイテムとして行列を構築する．その際，クエリ列の最後のクエリのみに注目し，
- successfulだったら(検索結果からどっかのページを開いていたら)クエリにポジティブな値を振り
- unsuccessfulだったらネガティブな値を振り
- それ以外には値を振らない
として行列を構築．その後は通常の協調フィルタリングにおける諸々の手法を試す．
アドホックな手法
今度はもっと簡単な手法を考える．
まず，クエリを，そのクエリによる検索結果のドキュメントでクラスタリングしておく．
次に，successfulなセッションについて（と論文には書いてあるが，successfulになるのはセッションではなくセッションにおけるクエリ単体である．よっておそらくこれはsatisfactoryなセッションについての作業だと考えられる），セッションごとに最後のクエリについてクエリのリストを作る．
- Session1: apple, banana, coffee, cake, tea
- Session2: apple. orange, spaghetti, raspberry
- Session3: orange, raspberry, pie, coffee
これらのセッションに対し，最後のクエリに向けて
- query_list[apple] #=> [tea, raspberry]
- query_list[banana] #=> [tea]
- query_list[coffee] #=> [tea]
- query_list[cake] #=> [tea]
- query_list[orange] #=> [raspberry, coffee]
- query_list[spaghetti] #=> [raspberry]
- query_list[raspberry] #=> [coffee]
- query_list[pie] #=> [coffee]
こんな感じのを作る．
で，あとは新しいクエリが来たら
- 新しいクエリが所属するクラスタのクエリをすべて持ってくる
- 持ってきたクエリすべてについて，query_listからクエリ集合を取得
- それの積集合を取り，k個ランダムに返す
実験
色々しました
感想
ページを踏んだか踏んでないかでsuccessfulかどうか，というのは面白いと思った．あとは類似度の話とか．
