Identifying and Labeling Search Tasks via Query-based Hawkes Processes (KDD 2014) 読んだ

http://labs.yahoo.com/publication/identifying-and-labeling-search-tasks-via-query-based-hawkes-processes/

概要

タイムスタンプ付の検索クエリ集合から search task (同じ information need を満たすために入力されたクエリ集合) を特定する．
その際，点過程で用いられる Hawkes process と LDA を組み合わせることによってタスクを推定する．

手法

search task を推定するのは意外と厄介．以降 Figure 1を参照．

連続している2クエリが常に同 task であるとは限らない
むしろ連続していなくても同 task であることもある
ユーザごとにクエリを入れる頻度や間隔も異なる

まずはLDAをベースに手法を考えるが，既存のLDAベースの手法ではユーザごとに topic を学習するため，全ユーザでの傾向が反映できない．
提案手法では， influence という，あるクエリが別のクエリの入力を引き起こすような現象を考慮する．
具体的には，influence とクエリ-トピックの関係を潜在変数で表現する．

Query Co-occurrence and LDA

クエリ集合にLDAを適用してK個のトピックを抽出しようとすると，ユーザmに対するK次元ベクトル $\pi_m$ と，mのn回目のクエリに対するトピックを表すベクトル $Y_{m,n}=<y_{m,n,1},\cdots,y_{m,n,T}>^T$ を推定するタスクになる．
しかし，このままYを(通常のLDAの枠組みのまま，つまりは時間情報を抜きにして)推定するのは困難．なぜならば，2つのクエリが同一トピックに属するかどうかは時間的な距離(間隔)に大きく依存するためである．
そうなると次に問題なのは，時間情報をどう扱うか，言い換えれば，LDAでの入力(「文書」と呼ばれる単位)の構築にどう利用するか，ということである．一番シンプルな方法はある時間幅でクエリ集合を分割することだけど，

異なる時間幅でセッションを分割する最適解は大抵存在しない
- 時間幅の重複を許すと，余分な情報が入ってしまうか，もしくは，短い時間間隔で存在する2クエリが別タスクに分割されてしまう
ユーザ固有のパターンを無視してしまうか，誤解してしまう

という問題がある．
提案手法では，クエリのペアにどのような influence の関係があるかを推定することによってこのような問題を解決する．influenceを用いる事によって，各ユーザの通常のパターンからtaskにもとづくパターンを抽出することが可能になる．

Hawkes Process

Hawkes process は点過程の中でも self-exciting と呼ばれる現象を表現するモデル．これは，過去のイベントによってその発生確率が増加するモデルで地震などの分析に用いられている(一度地震が起こるとその後余震が引き起こされやすい)．
Hawkes processではN(s)を過去に起こったイベントの回数とすると，あるinfinitesimal(無限に小さい)tにおけるイベントの rate function は $\lambda(t) = \mu_t(t) + \int_{-\infty}^{t} \kappa(t-s)dN(s)$ で表現できる． $\kappa$ はself-excitingを表現するカーネル．
このままシンプルにモデル化すると，全クエリペアで self-exciting が起こるモデルになるので，ユーザmのn番目とn'番目のクエリに influence が存在するかどうかを示す変数 $R_{m, n, n'}$ を導入して rate function を
$\lambda_{m}(t) = \mu_m + \sum_{t_{m,l} < t} R_{m,l,n}\beta_m\kappa(t-t_{m,l})$
とする．あとは $\mu_m,R_{m,n,n'},\beta_m,\kappa$ を推定すればいい．

LDA-Hawkes

ここでLDAとHawkes processをつなげる．influenceを表現する $R_{m,n,n'}$ を
$R_{m,n,n'} = Y^T_{m,n} * Y_{m,n'}$
とする．いってしまえば，二つのクエリが同じトピックを持っていれば influence が存在するとする．
こうするとLDAとHawkes process両方にメリットがある．

LDAにとっては，2つのクエリの関係性を考慮した上でトピックを表現することができる
Hawkes Process にとっては，通常 influence を考える場合には，時間情報を用いるだけでは全クエリ対についての influence を考えなければならない．これは非常に高コスト．LDAのトピックという概念を用いて推定することでこの候補を狭めることができる．

生成過程は以下のとおり．

トピック k について， V 次元のベクトル $\sigma_k$ を Dirichlet から引く
ユーザ m について，K 次元のベクトル $\pi_m$ を Dirichlet から引く
ユーザ m の n 番目のクエリについて
- トピック $Y_{m,n}$ を多項分布 $\pi_m$ から引く
- ユーザ m の n 番目のクエリに含まれる i 番目の単語 $w_{m,n,i}$ を多項分布 $Y_{m,n}, \sigma$ から引く
ユーザ m のクエリのタイムスタンプについて
- $\mu_m$ と $\beta_m$ を引く(どの分布から?)
- $R_m$ を $Y_{m,n}$ から求める
- $N_m$ を Hawkes Process から求める