Hatena::Grouprekken

murawaki の雑記

2012-11-20

Construction of Dependent Dirichlet Processes based on Poisson Processes

Dahua Lin, Eric Grimson, John Fisher. Construction of Dependent Dirichlet Processes based on Poisson Processes, NIPS 2010 (PDF, supplementary, videolectures, code).

NIPS 2010 の best student paper。理解度は 2 割ぐらい。videolectures にあがっている口頭発表は、動機を理解するには分かりやすい。

2014年3月31日追記: Yee Whye Teh のグループの ICML2013 論文supplementary に、このモデルのサンプリングは間違ってるという指摘がある。まじこわい。

要約。Dirichlet 過程*1同士に関係を持たせるために Poisson 過程を考える。Dirichlet 過程は Gamma 過程を正規化したもの。Dirichlet 過程には、足すと 1 になるという制約があって面倒だけど、Gamma 過程なら比較的柔軟な操作を行える。そのための理論的根拠として Poisson 過程が登場する。そもそも Gamma 過程は compound Poisson 過程のひとつであり、Poisson 過程の性質を満たす。つまり Poisson 過程のみが completely random な point process である。すなわち、completely random という性質を維持するように Poisson 過程に対する操作を定義すれば、その結果も Poisson 過程となる。具体的な操作として、superposition、subsampling、point transition の 3 種類を論文は導入する。これらは Gamma 過程に対する操作だが、正規化すれば Dirichlet 過程となる。Poisson 過程とか Gamma 過程が出てくるのは理論的正当化のためで、実装的には Dirichlet 過程だけを考えればよい。

何がうれしいか。Dirichlet 過程を 1 個使うだけでは、モデル化できるものは限られる。一般には複数の Dirichlet 過程を使いたい。別々にあるだけでは意味がないので、それらに関係を持たせたい。関係を持たせる具体的なやり方として、Dirichlet 過程の基底測度を別の Dirichlet 過程にして階層化する以外の方法を知らなかった。この方法では、親 Dirichlet 過程に対して複数の子供がいるような階層関係は作れるが、二つの Dirichlet 過程を直接混ぜ合わせて新たな Dirichlet 過程を作るといったことはできない*2。この論文手法ならこれが実現できる。

具体的には Dynamic Topic Models のようなことを Dirichlet 過程だけを使ってできる。Dynamic Topic Model の元論文では一度正規分布を考えて、次に正規化することで Dirichlet 分布を得ていた。もはや正規分布は必要ないはず。他には Sparse Additive Generative Models of Text が、指数関数の肩の上で好き放題操作して、後で正規化していたが、同じようなことが Dirichlet 過程だけでできるはず。まあ、additive generative model は負の「確率」を足す、つまり引き算ができていたけど、Gamma 過程を使う限りは非負でなければならない。

まあ、私が勉強不足なだけで、dependent Dirichlet process 自体は以前から研究されている。MacEachern の 1999 年の論文が走りで、これまでもいろいろ提案されてきたらしい。それぞれ一長一短だったけど、提案手法は満たしたい性質を全部満たしてますよとのこと。

特にうれしい性質は marginally DP であること。それは式 (19) に表されている*3

D'|\mathrm{\Phi} \sim \mathrm{DP}\left(\alpha_\nu p_\nu + \alpha_0 p_{q\mu} + \sum_{k=1}^{m} q_k c_k T(\phi_k, \cdot)\right)

記号が一度に出てきたが、ぼちぼち説明していく。今考えているのはD'というDirichlet 過程。D'|\mathrm{\Phi}は、ぼーっと眺めていると、サンプルを得た後の周辺事後確率を表しているように思ってしまいそうだが、そうではない。\mathrm{\Phi} \sim D であり、別の Dirichlet 過程Dからのサンプル集合。D'からのサンプルは考えていない。そもそもDを周辺化していないし。パラメータ内の長ったらしい数式は、これ全部で普通の Dirichlet 過程の基底測度に対応する。

パラメータの中身。まず\alpha_\nu p_\nuが普通の Dirichlet 過程のパラメータp_\nuを innovation distribution と呼んでいる。残りの部分がD'から引き継いだもの。つまり、前の分布を引き継ぎつつ、新しい分布を混ぜる。この混ぜる操作が superposition にあたる。残りの subsampling と point transition には、それぞれ q と T が関係している。

c_k\phi_k \in \mathrm{\Pi}\mathrm{\Phi}中で観測された回数。

p_{q \mu}qで subsampling された結果。qは項q_k c_k T(\phi_k, \cdot) にも出てくる。先に subsampling してから point transition T適用する。q_kは point \phi_k に対応する Bernoulli 分布のパラメータ関数形式だとわかりにくいので、定数、例えばq=0.6の場合を考えると、前の分布の\phi \in \mathrm{\Pi}は確率qで生き残る。qはT(\phi_k, \cdot)\phi_kが飛ばされた先全部に効果が及ぶ。

最後は point transition。T(\phi_k, \phi_l)が元の分布上の\phi_kが新しい分布上の\phi_lに飛ばされる確率を表す。単語の分布とかを考えていると、この操作を導入してうれしい気分がわからない*4。雑踏中の人の流れなどをモデル化する場合には、前の分布上の点が、次の分布で同じ場所にいても仕方がない。T としてブラウン運動などを突っ込めばいいのだろう。おそらく。

お約束通りD'積分消去して、最初のサンプル\theta_1の分布を考える。

\theta_1|\mathrm{\Phi} \sim \frac{\alpha_\nu}{\alpha'_1} p_{\nu} + \frac{\alpha_0}{\alpha'_1} p_{q \mu} + \sum_{k=1}^{m}\frac{q_k c_k}{\alpha'_1}T(\phi_k,\cdot)

ここで\alpha'_1 = \alpha_\nu + \alpha_0 + \sum_{k=1}^{m} q_k c_k。この長ったらしい数式全部で普通の Dirichlet 過程の基底測度に対応する。\alpha'_1が「後で正規化」の役割を果たしている。

サンプリングの実装的には、3種類、2 + m 個ある項のいずれから出てくるかをまず考える。確率はそれぞれ\alpha_\nu, \alpha_0, q_i c_i ( 1 \leq i \leq m) に比例する。論文では補助変数を用意してu_1 = -1, u_1=0, u_1 = l > 0switch する。-1 になれば p_\nu からサンプルを得る。0 なら p_{q \nu} から。l > 0ならT(\phi_k, \cdot)から。

u_1 \in \{ -1, 0 \}なら\theta_1に質量を置く普通の更新。

D'|\mathrm{\Phi},\theta_1 \sim \mathrm{DP}\left(\alpha_\nu p_\nu + \alpha_0 p_{q \mu} + \sum_{k=1}^{m} q_k c_k T(\phi_k, \cdot) + \delta_{\theta_1}\right)

u_1 = l > 0だと不思議な更新。

D'|\mathrm{\Phi},\theta_1 \sim \mathrm{DP}\left(\alpha_\nu p_\nu + \alpha_0 p_{q \mu} + \sum_{k=1}^{m} q_k c_k T(\phi_k, \cdot) + (c_l + 1)\delta_{\theta_1}\right)

ここで\theta_1\theta_lの point transition で得られたとする。\theta_lのカウントが効くのはわかるとしても、なぜc_l+1なのか理解していない。更新後のパラメータを使って次のサンプルも生成できる。普通の階層化、つまり基底測度を別の Dirichlet 過程にし、Chinese restaurant process で説明する場合と違って、新たなテーブルを作っても基底測度側を更新しない。同じ感じで、観測データを所与とすれば、サンプリングの初期値を決められる。

ここで疑問が生じる。time-dependent な model を考えているので、Dirichlet 過程の Markov chain が用意される。現在の Dirichlet 過程は一つ前の Dirichlet 過程に依存する。現在の Dirichlet 過程のサンプルを更新しても過去は影響を受けない。一方で未来には影響を与える。それも広範囲に。一体どうやってサンプリングしているのか? 実はやっていない。6.1 の実験設定を見ると、Markov chain の各段階で、5,000 iterations を実行する。その最後のサンプルを使って次の段階のサンプリングをする。各段階の中の潜在変数は exchangeable なので好きな順番でサンプリングできるけど、ひとたび次の段階に進んだらもう変更しない。Markov chain 全体に対しては one pass だけ。戻る場合は最初から全部作りなおす。そんなので良いのだろうか。

Dirichlet 過程に対する柔軟な操作が導入されたわけで、時系列に限らず、様々な応用ができそうな気がしていた。しかし、もしサンプリングの実現方法に制限があるのなら、実際にはそれほど柔軟に依存関係を導入できないかもしれない。

なお、ICML 2012 で dependent hierarchical normalized random measure (supplement?) というのが提案されている。どうやら Dirichlet でモデルが提案されたら、discount factor を入れたモデルを出すのが業界のお約束らしい。しかし、こっちは math 濃度が高すぎて微塵も理解できない。

その他。

  • 3ページ目 point transition の\theta \in \mathcal{F}_\Omega\theta \in \Omegaの間違い?
  • Supplement の定義 1 のN_\pi(A) = \mathrm{num. of} \{\Omega \cap \pi\}*5N_\pi(A) = \mathrm{num. of} \{A \cap \pi\}の間違い?

*1:ここでは気分で\mathrm{DP}(\alpha \mu)自体を Dirichlet 過程と呼んだり、D \sim \mathrm{DP}(\alpha \mu)を Dirichlet 過程と呼んだりする。かなりいい加減。

*2基底測度を 2 段階で生成することで、二つの Dirichlet 過程の mixture を基底測度にするといったことならできる。サンプリング時にはどちらから生成されたかを track する。

*3D'|\mathrm{\Phi}と書かれると、\mathrm{\Phi}だけが所与みたいに見えるが、諸々のハイパーパラメータは省略されいる。

*4:Dependent Hierarchical Normalized Random Measure の論文は dynamic topic model に対しても point transition を適用しているみたいだが、私は中身を理解していない

*5はてなtex math mode で # を表示する方法がわからない。