Hierarchical Dirichlet Processに関するメモ

自分用メモ。例によってすげー基本っぽいことを書いていく。HDPの前のDP関係は昔ちょっとメモ書きを書いている。
www.yasuhisay.info

全体的なこと

  • 客はdocument levelでCRPしていく
  • 料理はcorpus levelでCRPしていく(!)
  • HDPはこの2段階(というか2つ)のCRPで構成される
    • document levelだけではコーパス間の情報を共有できないが、料理はcorpus levelなのでこれを使って共有できる
    • もちろんdocument levelのものもあるので「このdocumentではこういう単語が出やすい」という風なLDA風のこともやっている
  • document内のクラスタリングとdocument横断でのクラスタリングを同時に走らせているようなイメージ(あまり自信はない)

生成過程

こんなイメージ。HDPの元論文にある通り(P13の3つ目のやり方)、TとLを無限大に飛ばしたもの、と考えたほうが分かりやすいかな。

  1. \beta \sim \mbox{Dir}(\gamma) => どの料理を配るかのパラメータ。次元はCRPで伸びていく
  2. For each topic k = 1, ..., \infty:
    1. \theta_k \sim \mbox{Dir}(\alpha_0) => 各トピック毎の単語の多項分布のパラメータ。\theta_kは単語次元のベクトル
  3. For each document j = 1, ..., J:
    1. \pi_j \sim \mbox{Dir}(\lambda) => どのtableに着席するかのパラメータ。次元はCRPで伸びていく
    2. For each class t = 1, ..., \infty:
      1. k_{jt} \sim \mbox{Multi}(\beta)
    3. For each word i = 1, ..., N_j:
      1. t_{ji} \sim \mbox{Multi}(\pi_j)
      2. x_{ji} \sim \mbox{Multi}(\theta_{k_{jt}})

最後のx_{ji} \sim \mbox{Multi}(\theta_{k_{jt}})のところとLDAを拡張したという雰囲気がぴんときていないので後でまとめる。

x_{ji} \sim \mbox{Multi}(\theta_{k_{jt}})のところ

ようやく意味が分かった。

  1. まずtable tに料理kが一つ運ばれてくる(tableに置かれる料理は一つだけである。それとこの料理はglobalなメニューの中から選ばれる料理である)
  2. 単語xはtable tに着席する
  3. 着席したところには料理kが置いてあるので、そのindexの\theta_kをパラメータとする多項分布を考えればよい

ということのようだ。そういうわけでクラスタはtableのほうで作っておいて、トピックは料理kのほうで作るということらしい。文書内レベルでのクラスタリングと文書横断のクラスタリングを同時に走らせているようなイメージ。合ってるかな。

学習

ここの図1(b)のグラフィカルモデルをベースにしながら考えていく(他のだとテキストによらず色々な形で使えるように(Base Measureを使って)一般化して書いてあるが、最初はこっちのほうが分かりやすい。元のHDPとのつながりを書いておくとHのようなBase Measureは具体的なディリクレ分布に置き変わり、そのハイパーパラメータの部分がグラフィカルモデルに残った、と考えると分かりやすいかも)。アルゴリズムのところで\alphaをアップデートしているからこの\alphaが(ハイパーパラメータではなく)パラメータのように勘違いしてしまったが、グラフィカルモデルにある\alpha_0はハイパーパラメータでおk、ということにちょっと注意が必要。図1(b)では\alpha_0はベクトルになっているけど、まあsymmetricとしてscalarでもそんなには問題ないでしょう。さて、整理すると

  • 隠れ変数 => tとk
  • パラメータ => \pi\beta\theta
  • ハイパーパラメータ => \lambda\beta\alpha_0

という関係のモデルになっているということが分かる。こうして書いてみるとそんなに恐しくないような気もしてくる...はず。HDPの元論文では3種類のsamplingの方法が書かれているが、最初なので一番ベーシックなGibbsでやっていくことにしよう。上で書いたように隠れ変数はtとkなので、いつものようにfull conditionalな分布を書いてやることを考えよう。Gibbs Samplingに必要なのは以下の2つの式。

  • p(t_{j, i} = t | \mathbf{t}_{- (j, i)}, \mathbf{k}, \mathbf{x}, \lambda, \beta, \alpha_0)
  • p(k_{j, t} = k | \mathbf{k}_{- (j, t)}, \mathbf{t}, \mathbf{x}, \lambda, \beta, \alpha_0)

まず、最初の式についてだが、LDA Gibbsのときのように2つの項に分解する。
p(t_{j, i} = t | \mathbf{t}_{- (j, i)}, \mathbf{k}, \mathbf{x}, \lambda, \beta, \alpha_0) \propto p(t_{j, i} = t, x_{i, j}| \mathbf{t}_{- (j, i)}, \mathbf{k}, \mathbf{x}_{- (j, i)}, \lambda, \beta, \alpha_0) = p(t_{j, i} = t | \mathbf{t}_{- (j, i)},  \lambda) p(x_{i, j} | t_{j, i} = t, \mathbf{t}_{- (j, i)}, \mathbf{x}_{- (j, i)}, \alpha_0)
次の項についても同様に2つの項に分解する。\mathbf{x}_kは今いるdocumentのトピックと同じトピックにいる単語の集合(コーパスレベルであることに注意)。
p(k_{j, t} = k | \mathbf{k}_{- (j, t)}, \mathbf{t}, \mathbf{x}, \lambda, \beta, \alpha_0) \propto p(k_{j, t} = k, \mathbf{x}_{k}| \mathbf{k}_{- (j, t)}, \mathbf{t}, \mathbf{x}_{- k}, \lambda, \beta, \alpha_0) = p(k_{j, t} = k | \mathbf{k}_{- (j, t)},  \gamma) p(\mathbf{x}_k | k_{j, t} = k, \mathbf{k}_{- (j, t)}, \mathbf{x}_{k}, \alpha_0)

p(t_{j, i} = t | \mathbf{t}_{- (j, i)},  \lambda)p(k_{j, t} = k | \mathbf{k}_{- (j, t)},  \gamma)のところはCRPの式(document levelかcorpus levelかは異なるが)になるが、ここはいつもの通り。P(\mathbf{X}_{jt} | \mathbf{X}_k)のような確率が必要になってくるが、こやつは多項分布とディリクレ分布のパラメータを積分消去したいつものポリヤ分布が出てくる形を見ればいつものようにできるんだなと分かってくる。

参考リンク

実装とかを中心に。

続・わかりやすいパターン認識―教師なし学習入門―

続・わかりやすいパターン認識―教師なし学習入門―