Improving recommendation for long-tail queries via templates
概要
グラフベースのクエリ推薦において，クエリごとにクエリ-ページの遷移を考えるのではなく，クエリ-テンプレート，テンプレート-テンプレートでの遷移を考える．
これにより，従来のクエリ推薦では対応できなかったロングテール（つまりは検索数が少ないクエリ）に対応する．
例えば，"Montezuma surf"というクエリについて，"
Query-Flow Graph
Boldiがこれまで何度か書いてきた手法．いくつか読んではいるがブログで書いた事は無かったのでいつかまとめて書く．
QUERY TEMPLATES AND THE QUERY TEMPLATE FLOW GRAPH
最大のキモであるクエリのテンプレート化．
なるクエリはタームの集合
であるとする．この時，連続したタームをまとめる作業をtokenizationと呼ぶ．例えば"chocolate cookie recipe"なるクエリに対するtokenizationは
- "(chocolate)(cookie)(recipe)"
- "(chocolate cookie)(recipe)"
- "(chocolate)(cookie recipe)"
- "(chocolate cookie recipe)"
となる．そしてこの時，あるtokenizationをと表現する．
このクエリログに加えgeneralization hierarchyなるデータも同時に用いる．これは要素Eについて，
なる汎化構造を含んでいる．これは，
が
の一般化である時，
として現される（ex. chocolate→food，chocolate→drink，food→substance...）．
その後，について
であるならばそれを置換し，
とする．先の"chocolate cookie recipe"に関するtokenizationについては
cookie recipe cookie recipe cookie recipe
- chocolate
recipe - chocolate
recipe
- chocolate
recipe recipe - chocolate cookie <instruction>
などがテンプレートとして得られる．chocolate→food→substanceといったように，階層構造を遡れる時は遡れる限り遡る．
またこの時，，
とする．
これらをn-gramについて取得していく．その際，メールアドレスであれば
Query-to-template edges
クエリ-テンプレート間にエッジを張る．この作業はクエリとテンプレート間のスコア計算に相当する．
クエリqとそのテンプレートtに対しスコアを次にように計算する．
- 要素eがgeneralization hierarchy Hにおいてより上位にあるならば，それは一般化しすぎていると考える．よって，置き換えた元の単語
とテンプレートの要素eとの階層構造での距離
について
とする．ちなみに
が良かったらしい．
- また，Query-Flow Graphにおけるクエリ⇔クエリ間のエッジについて
であれば
とする．
この上でと正規化してやる．
Template-to-Template edges
テンプレート-テンプレート間にエッジを張る．
二つのテンプレートに対し，次の条件を満たした場合有効エッジ
を張る．
- 同じ"単語"(placeholder)で置き換られている状態
かつ
の時，
であるクエリ
についてquery-flow graphにエッジが存在するならば，それを
に対するサポートエッジとし，
で表す．
あとはスコアを計算する．
感想
query-flow graphの論文も読み返してまとめたほうが理解が早いっぽい．
