The query-flow graph: model and applications - todo314 @ ウィキ

The query-flow graph: model and applications

• Paolo Boldi, Francesco Bonchi, Carlos Castillo, Debora Donato, Aristides Gionis, Sebastiano Vigna
• CIKM 2008

概要

• query-flow graph
• q_i→q_j: 同セッションで計算されやすいよ！w(q_i,q_j)はその確率
• 問題
  • でかい、ノイズ、定式化、あいまい、疎、などつらぽよ
• 応用
  1. logical session
     • intertwined query chainsを見つける
  2. query recommendation
• Random walk with restartを使う

概念

• クエリログとは
  • L = {<q_i, u_i, t_i, V_i, C_i>}
    • q_i: クエリ
    • u_i: ユーザID
    • t_i: タイムスタンプ
    • V_i: 得られたドキュメント
    • C_i: クリックされたドキュメント
  • 全部使う、ともーじゃん？…と思わせて
  • L = {<q_i, u_i, t_i} しか使わない
• セッションとは
  • 時間制限を設けてクエリログを区切る
  • 隣り合うクエリ間の時間がt=30min以下
• スーパーセッション
  • 全部
• チェイン（ミッション、ロジカルセッション）
  • ユーザが欲している情報に着目してクエリを繋げる
• The query-flow graph
  • G_qf = (V, E, w)
    • V = Q∪{s, t}
    • w:E→(0,1]
    • w(q,q'): qとq'が同チェインに含まれる確率

構築

• I(L) = {S_1, …, S_m}
  • time stampでソートしてしきい値tで区切っただけ
• T = {(q,q') | ∃s_i s.t. q=q_i, q'=q_{i+1}∈S_j}
• 訓練データ
  • (q,q')をランダムに選択してラベル付
• 特徴
  • 18個：Textual, Session, Time-related

チェインを見つける

• 評価関数を定義するよ
• S = <q_1, q_2, …, q_k>
  • とりあえずquery-flow graphには↑が入っている
• chain cover
  • {1, …, k}をC_1, …, C_kに分割
  • 各C_iをchainと考えて発生確率を決定
• maximize P(C_1)…P(C_k)
• TSPでやるには？
  • ω(q_i, q_j)=max{-log P(q_i, q_j), -log P(q_i, t)P(s, q_j)}
  • 後者は分割に相当
• どうやって解くの？
  • 無理？！
  • Greedy！！しょうがないね
• timeout-basedな分割とも比較しちゃう
• 実験結果
  • ATSPの方がちょっと良い
  • ※ATSPはタイムスタンプ使わない、timeout-basedは使っている
  • イイ感じに分割できる！！！

Query Recommendation

• w'(q,q')をw(q,q')がでかいもの限定に
• 最大重みでレコメンド
  • う～ん…
• Random walkでレコメンド
  • personalized PR
  • そのまんまだとうまくいかないのでちょっと変える、正規化っぽい
• Historyでレコメンド
  • 何か頑張る

CIKM kk query-flow graph recommendation

2013-12-12 00:24:10 (Thu)