Hierarchical Geographical Modeling of User Locations from Social Media Posts (WWW2013)を読んだ

論文のpdfはここ

概要

TwitterやFacebook，FoursquareやGoogle+などのソーシャルネットワークサービスによってロケーションセンサーやジオタグが安価に利用可能になっている．この論文は地理情報とメッセージ内容の生成モデルを提案する．

既往研究のように予め定義(たとえばメッシュなどで)することをせず，本研究のモデルは自動的にコンテンツ上の階層構造と地理的位置情報上のサイズと位置上の階層構造を推論する．これによりかなり精度が向上した（過去のベストな結果よりも40%以上エラーが減少した）

この結果は新しい統計モデル nested Chinese Restrant Franchise (nCRF)を提案することで達成した．多くの統計的構造はユーザー間でシェアされている．つまり，各ユーザーは興味と場所において自分自身の分布を持っている．nCRFを用いることによって，次のような影響を捉えることができる．

ツイートに対するトピックモデルを与える
場所固有のトピックを得る
場所の潜在的な分布を推論する
トピックと場所の階層モデルを与える
上記のモデル内のトピックとロケーションに関するパーソナライズドされた選好を推論する．

以上より，ユーザーのツイートから正確に位置を推測することができたり，地理的な言語モデルを詳細に推定することができる．

Key Contribution

ロケーションとコンテンツ，個人の選好の同時階層モデルをつくったこと．
ユーザーごとにロケーション固有生成モデルを作成する．
ノンパラベイズで階層モデルをつくる
nCRFによって次のような重要な問題を対処した
- 各ユーザーのツイートをnested Chinese Restrant過程かhierarchical Pachinko Allocation Modelと同種の階層構造モデルでモデル化したい
- 同時に，階層構造を共有することで異なるユーザー間で統計的検出力の共有を保証したい

Chinese Restrant Process

ノンパラベイズの典型的な構成要素はディリクレ過程 $DP (H, \gamma)$ である．
任意の測度 $H$ からドローされたobservationsの離散分布がつくれる．
$G_0 \sim DP(H, \gamma)$ はDPからのドローを表し， $\gamma$ はbase measure周辺でのドローの分散をコントロールしている．
$G_0$ はそれ自体が無限要素の分布である．
次に $\theta_i \sim G_0$ となるパラメータをドローする．
ディリクレ過程混合モデル(DPM)は観測データ点 $x_i$ を $\theta_i$ からドローする( $x_i \sim f(\theta_i)$ )ことによって前述の生成過程に拡張する．

ディリクレ過程のよくあるメタファーはChinese Restaurantである．各データ点は無限にテーブルがある中華料理店の客であり，最初はすべてのテーブルは空だが，人気に応じて客はテーブルを選択していく．その確率は

　　　　　　　　　　　　 $Pr \{ x_i = j \} = \left\{ \begin{array}{l} \frac{N_j}{\sum_k N_k + \alpha} \text{ for an existing table} \\ \frac{\alpha}{\sum_k N_k + \alpha} \text{ for a new table}\end{array} \right.$
ここで， $z_i$ は客 $i$ の選択， $N_j$ はテーブル $j$ に座っている現在の客の数， $\sum_k N_k$ は現時点でのすべての客の数．

Franchises and Hierarchies

階層モデルをつくるための重要な構成要素は階層ディリクレ分布(HDP)
$G \sim DP(H,\gamma) \text{we now have } G_i \sim DP(G_0, \gamma^') \text{and } G_0 \sim DP(H, \gamma)$
$\gamma, \gamma^'$ はパラメータ
これはまず， $H$ から $G_0$ をドローし，reference measureとして使うことで測度 $G_i$ を得る．
すべてのランダム測度を統合するために，Chinese Restaurant Franchise (CRF)
これは各レストランがテーブルの集合を持っているが，同じ混合集合をシェアしている
レストランkの客はテー部酢に座っている客の数に応じた確率で存在するテーブルに座ることもできるし，確率 $\alpha$ で新しいテーブルを始め，グローバルな分布から料理を選ぶこともできる．
このグローバルな分布において，料理(mixture)は全てのレストランで使われている割合に応じて選択されるが， $\gamma$ に比例した確率で新しいglobal dishが選ばれることもある．

The Nested Chinese Restaurant Process

CRPsやCRFsによって単一のmixture (topic)から文書のようなオブジェクトを生成できる
でも，トピック間の関連は与えられない
この問題に対して，nested Chinese Restaurant Process (nCRP)が提案
nCRPだとツリーの子のトピックをより一般化したものが親のトピックになるような木構造

The Nested Chinese Restaurant Franchise Processの基本的な考え

名前はCRFとnCRPから借りてきた
nCRFは個人ごとに同じ階層構造上での個人ごとの分布をもつ
ツリー構造上のノンパラメトリックモデル
- 各ユーザーは自分自身のツリーを持っているが，ツリー内のノード集合とその構造（親-子構造)はすべてのユーザー間でシェアしている
- nCRPを各ユーザー間で関連づける
図を引用していいのかわからんので引用しないがFigure 1がわかりやすい

user によるツイートによる経路を生成したいとする
- root nodeはその子ノード上でCRPを定義する
- 子ノードを選択するか新しい子ノードをつくる．つくる場合はglobal CRP
- global treeでの子の選択確率はglobalな利用によって決まる
- 全部の選択確率は基本的なCRFメカニズムに従う
- 子ノードが決まると，full pathが決まるまで再帰的に決める

数式で簡単に書く
- $i$ をツリー内のノード， $(i)$ をノード $i$ のツリー内でのレベル， $C(i)$ を子， $\pi(i)$ を親とする．
- $n_{ij}$ はノード $i$ で子 $j$ が選ばれた数， $n_i = \sum_j n_{ij}$

　　　　　　　 $Pr\{ \text{child } j \text{ at } i\} = \left\{ \begin{array}{l} \frac{n_{ij}^u}{n_i^u+ \alpha} + \frac{\alpha}{n_i^u + \alpha}\frac{n_{ij}}{n_i + \beta} &&\text{ if} j \in C^u(i)\\ \frac{\alpha}{n_i^u + \alpha}\frac{n_{ij}}{n_i + \beta} &&\text{ if} j \in C(i) \backslash C^u(i)\\ \frac{\alpha}{n_i^u + \alpha}\frac{\beta}{n_i + \beta} &&\text{ if} j \not \in C(i)\end{array} \right.$

Generating Microblogs

Tree distribution
- nCRF
Hierarchical location model
- $\mu_r \sim N(\mu_{\pi (r)} , \Sigma_{\pi (r)}) \text{ and } \Sigma_r = \frac{1}{level(r)} \Sigma_0$
Generic topics
- $\Pi_i \sim Dir (\eta)$
Location specific language model
- $\phi_0 \sim Dir (\eta)$ , $\phi_r \sim Dir (\omega \phi_{\pi (r)})$
Location specific mix of topics
- $\theta_0 \sim Dir (\beta)$ , $\theta_r \sim Dir (\lambda \theta_{\pi (r)})$
User specific tree distribution