Towards Context-Aware Search by Learning A Very Large Variable Length Hidden ... - todo314 @ ウィキ

Towards Context-Aware Search by Learning A Very Large Variable Length Hidden Markov Model from Search Logs

• Huanhuan Cao, Daxin Jiang, Jian Pei, Enhong Chen, Hang Li
  • MSRAとUniversity of Science and Technology of China
• WWW 2009

概要

• たった今調べたクエリからURLを正しくレコメンドするのは無理
• 例: ホントは車のレビューサイトを見たい
  • 検索クエリ: Ford new cars → Toyota new cars
  • 個々のクエリに着目するとautohome.comは出てこない
• クエリ全体を見ると分かる→context-aware!!

• 汎用的なフレームワークを作りたい！！
  • document re-ranking
  • query suggestion
  • URL recommendation

• variable length Hidden Markov Model(vlHMM)によるクエリコンテキストモデルを提案
  • 事後確率 $$ P(s_t | q_t, O_{1 \cdots t-1}) $$
    • s_t: ユーザーの思考、検索意向
    • q_t: 今のクエリ
    • O_{1…t-1}: q_tのコンテキスト（今までのクエリ+クリック）
  • さらに予測 $$ P(s_{t+1} | q_t, O_{1 \cdots t-1}) $$
• HMMの学習
  • セッションが多すぎる
  • パラメータが爆発

    　 　　(⌒⌒)
    　　　　 ii!i!i 　　ﾄﾞｶｰﾝ
    　 　　ﾉ~~~＼
    ,,,,,,,／´･ω･` ＼,,,,,,,,,,
    

  • 解決法
    • パラメータ初期化法
    • Map-Reduce

3. vlHMM

• 1-HMMs
  • s_tはs_1,…,s_{t-2}とは独立
  • 今回のに適用するにはやばめ
• vlHMM
  • s_1,…,s_N_s: 隠れ状態の集合
  • q_1,…,q_N_q: クエリの集合
  • u_1,…,u_N_u: URLの集合
  • T_max: 状態列の最大長
• 遷移確率分布: $$ \Delta = \{ P(s_i | S_i) \} $$
• 初期状態分布: $$ \Psi = \{ P(s_i) \} $$
• 放出確率: $$ \Lambda = \{ P(q,U | S_j) \} $$
  • T_{j-1}ステップ後に状態$$ s_{j,T_j} $$からクエリqを出してUをクリックする
  • $$ P(q,U | S_j) \equiv P(q,U | s_{j,T_j}) $$
    • 最後の状態だけにしちゃう
  • $$ P(q,U | s_{j,T_j}) \equiv P(q | s_{j,T_j})\prod_{u \in U}P(u | s_{j,T_j}) $$
    • 条件付き独立にしちゃう
  • ☆結局考えるべきは$$ (\Lambda_q, \Lambda_u) \equiv (\{P(q | s_i)\}, \{P(u | s_i)\}) $$
• Q. 何をtrainするのか？？？
• A. $$ \Theta = (\Psi, \Delta, \Lambda_q, \Lambda_u) $$

• セッションを30分ごとに区切る
  • $$ \chi = \{ O_1, \cdots, O_N \} $$: 訓練データ
  • $$ O_n = \langle (q_{n,1}, u_{n,1}), \cdots, (q_{n,T_n}, u_{n,T_n}) \rangle $$

• 最大尤度なΘを求めた
  • ↑訓練データを最もよく表現する
  • $$ \Theta^* = \arg \max_{\Theta} \ln P(\chi | \Theta) = \arg \max_{\Theta} \sum_{n}\ln P(O_n | \Theta) $$
  • あとは色々頑張る
  • 最終的にEM(Expectation Maximization) algorithmに落ち着く

4. Training

• EMアルゴリズムを適用したいけどやばお

1. 隠れ状態の数
   • よく分からん
   • 二部グラフ（？）作ってクラスタリング
   • クラスタ(Q,U)が隠れ状態
2. ログ大杉
   • MapReduce!!!
3. そもそもユニークなクエリ・URL大杉
   • パラメータ数10^30
   • うま～く減らすし、理論的に抑えるよ！

5. Application

• O: q_1, …, q_t, U_1, …, U_tの列
• Γ_O: 候補状態
• P(S_m | O, Θ): 事後確率を推論できる
• で？っていう
• P(s_t | O, Θ)もP(s_{t+1} | O, Θ)も↑から計算できる
• Context-Aware actionsの数々

1. Document re-ranking
   • $$ P(u | O) = \sum_{s_t \in S_t}P(u | s_t)\cdot P(s_t | O) $$の順にre-rank
     • $$ S_t = \{s_t | P(s_t | O) \neq 0\} $$
     • U: q_tに対して検索エンジンが返すURLリスト
2. Query suggestion
   • $$ P(q | O) = \sum_{s_{t+1} \in S_{t+1}}P(q | s_{t+1})\cdot P(s_{t+1} | O) $$
     • $$ S_{t+1} = \{ s_{t+1} | P(s_{t+1} | O) \neq 0 \} $$
     • $$ q \in Q_{t+1} = \{ q | s_{t+1} \in S_{t+1}, P(q | s_{t+1}) \neq 0 \} $$
3. URL recommendation
   • $$ P(u | O) = \sum_{s_{t+1} \in S_{t+1}} P(u | s_{t+1})\cdot P(s_{t+1} | O) $$
   • ↑と大体同じ

• オンラインでの応用
  1. 知らないクエリ or URLが来たら？
  2. 速度は？

6. 実験

• データセット

  1.8B queries	151M unique queries
  2.6B clicks	114M unique URLs
  840M sessions

• 前処理
  • あんまり適当だと消しすぎる
  • 出現回数5未満は消す（ジャンクだ！！！
    • 48%消えた
  • 結局
  • ユニーククエリ・URLは相当減った
  • クエリ、クリック、セッションの数は半分程度
• Efficiency
  • 隠れ状態（クラスタ）数 10^6位
  • パラメータ #P(s_i), #P(q|s_i), #P(u|s_i), #P(s_i|S_j)
  • 時間、パラメータ数は訓練データの量に比例するよ！！
• Effectiveness
  • 応用としてあげたのと比較

まとめ

• 超でかいデータにスケールするようなフレームワークを考え動かしたのが全て

Hidden Markov Model WWW context-aware search kk

2013-12-10 01:08:02 (Tue)