Hatena::Grouprekken

murawaki の雑記

2010-09-19

単語の zero-gram 確率

単語 w を生成する zero-gram 確率をどうやってモデル化しましょうかという話。

想定する用途は単語分割。単語分割では、長さの違う単語候補同士を比較して、どっちがそれらしいか推定する。一様分布を仮定するといかにも都合が悪そう。そこで、単語が構成要素から生成される確率を考える。構成要素は音素や文字。データに依存。では具体的にどう生成するか。

(Goldwater+ 2009) は w が c_1 \cdots c_k からなる確率を以下で与える。

p_{\%23}(1-p_{\%23})^{k-1} \prod_{i=1}^{k} P(c_i)

ここで、p_{\%23} は単語境界を生成する確率。データの言語は英語で c_i は音素 (普通の綴りではなく、1文字1音素で書き起こした特殊なデータ)。要するに、音素 unigram と、単語境界の二つを考慮している。

p_{\%23} はどれぐらいか。Goldwater+ は自動推定はしていない。手動で値を変化させて、教師なし単語分割の精度を調査している。(単語) unigram model で、type の精度 (F値) は 0.3 が一番、token の精度は単調増加で 0.9 が一番。他のモデルとの比較では 0.5 に固定。bigram model では 0.2 が良かったとのこと。ばらばら。

token の精度が良くて、type の精度が悪いということは、高頻度の語はあっていて、低頻度の語を間違う傾向にある。p_{\%23} を大きな値する、つまり短く区切ろうとするとそうなるという結果。この結果をどう説明するか。a や is などの高頻度語は短く、低頻度語は長いという傾向を反映している?

そもそもモデルがいまひとつではないかという疑惑。ひとまず P(c_i) のばらつきを無視して、分割する場合に対する分割しない場合の確率の比を取ると、p_{\%23} > 0.5 のとき、長さ k = 1 からひたすら減衰。ということは、もし単語 zero-gram をモデルとして教師なし単語分割を行うと、1 音素 1 単語に落ち着くはず。unigram model ではそうならない (ただし事前分布を考慮する Bayesian な設定で)。unigram が分割しない方向に作用することがあるから。いま、is という音素列を考えた時、バックオフの zero-gram は i . s と分割する側に傾く。unigram は is というコロケーションがコーパス中によく出現するのであれば、is と分割しないでおこうとする。適当なところで均衡。p_{\%23} < 0.5 だと逆。

別の方式。(Nagata 1996) は単語長 k を直接モデル化している。こちらは c は文字。

P_0(w) = P(k) P(c_1 \cdots c_k | k)

そして、P(k) に Poisson 分布を仮定。

P(k) = Po(k-1; \lambda -1) = \frac{(\lambda - 1)^{k - 1}}{(k-1)!}e^{-(\lambda - 1)}

1 を引いている理由に自信はない。k = 0 に確率質量を与えたくないからという理解であっているのだろうか。とにかく、k が λ から離れると、大きくても小さくでもペナルティがかかる。

文字列の生成は bigram で。

P(c_1 \cdots c_k|k) = P(c_1|\mathrm{BOW}) \prod_{i=2}^k P(c_i|c_{i-1}) P(\mathrm{EOW}|c_k)

BOW, EOW はそれぞれ単語の始まり、終わり。(Nagata 1999) では、さらに、日本語の字種を考慮するようにモデルが修正される。また、教師データがあるという設定で、各種のパラメータは教師データから推定される。

ここで、高頻度語は短く、低頻度語は長い傾向にあることを思い出す。この現象がモデルにどういう影響を与えるかというと、影響はない。実は上記のモデルは未知語モデル。パラメータは教師データ中の頻度 1 の単語から推定している。高頻度語は最初から除外されている。この設定で、(Nagata 1999) では λ = 4.8。結構長い。

(Mochihashi+ 2009) では、単語 unigram のバックオフが zero-gram で、その基底分布が以下。

\begin{eqnarray}G_0(w) &=& p(c_i \cdots c_k)\\ &=& \prod_{i=1}^k p(c_i|c_1 \cdots c_{i-1})\\ \end{eqnarray}

文字列の確率は ∞-gram で、n-gram は n-1 gram でバックオフするという恐ろしいモデル。これだけではうまくいかないとして、Poisson 分布により補正を加えている。

P_0(w) = \frac{P(c_1 \cdots c_k,k|\mathrm{\Theta})}{P(k|\mathrm{\Theta})}Po(k|\lambda)

こちらは 1 を引いていない。細かいところが理解出来ていない。(Nagata 1996)P(k|\mathrm{\Theta}) = (1 - P(\%23))^{k-1} P(\%23) を仮定していると論文に書いてあるけど、なぜ?

Poisson 分布の共役分布がガンマ分布なので、これを事前分布としている。事後分布は以下に従う。

P(\lambda | W) \propto \mathrm{Ga}(a + \sum_{w \in W} t(w)|w|, \, b + \sum_{w \in W}t(w))

ただし、|w| は単語 w の長さ。ガンマ分布 Ga(a, b) は平均が a/b、分散が a/(b*b)。事前分布のパラメータはほぼ無視できて、事後分布は一点でバーストしているはず。つまり、

\lambda \approx \frac{\sum_{w \in W} t(w)|w|}{\sum_{w \in W}t(w)}

何のことはない、λ は単語の平均長に従う。

問題は平均に傾斜をかけている t(w)。t(w) は単語 unigram の t_{\epsilon w}。Pitman-Yor process の Chinese Restaurant 表現におけるテーブルの数。分子の discount にかける項。論文によれば、unigram count c_1(w) の対数のオーダーの数になるとのこと。短い高頻度語の影響は対数によって抑えられているはず。バックオフが効いてくるのは低頻度語だと考えると、よくできている。

余談。単語の打ち切り確率があるなら、文の打ち切り確率があってもよさそう。実際、(Goldwater+ 2009) は定義している。sampling においては、単語分割数を減らす方に作用する。値を変化させても精度に変化はないという報告。そもそもタスク設定として、文境界は最初から与えられている。文の長さ (単語数) は考慮せず、BOS と EOS を置くだけで良い気がする。もし文境界も推定するタスクならどうするか。文の長さについても Poisson 分布を仮定すると良いだろうか。

2010-09-12

Type-based MCMC

Percy Liang, Michael I. Jordan, Dan Klein: Type-based MCMC (PDF).

スライドが神。そっちを見ればやりたいことはわかる。

自分用のメモ。間違っていたら指摘してほしい。

3.3 Prior

いきなり事前分布として Dirichlet distribution ではなく Dirichlet process を設定するあたり、難易度が高い。Dirichlet distribution 版の p(z) を導出してみる。

本当はパラメータ θ は |R| 個あるけど、簡略化のために一つにする。複数のパラメータの場合は積を取ればいい。

論文の ascending factorial は表記が気持ち悪いので、普通にガンマ関数同士の割り算にしておく。

\begin{eqnarray}p(\mathbf{z})&=&\int_{\mathbf{\theta}} p(\mathbf{z}|\mathbf{\theta})p(\mathbf{\theta})d\mathbf{\theta}\\ &=& \int_{\mathbf{\theta}}\prod_{o} \theta_o^{n_o(\mathbf{z})} \,\times\, \frac{\Gamma(\alpha_{(\cdot)})}{\prod_{o} \Gamma(\alpha_{o})}\prod_o \theta_o^{\alpha_o - 1}\,d\mathbf{\theta}\\ &=& \frac{\Gamma(\alpha_{(\cdot)})}{\prod_{o} \Gamma(\alpha_{o})} \int_{\mathbf{\theta}} \prod_o \theta_o^{\alpha_o + n_o(\mathbf{z}) - 1}\,d\mathbf{\theta}\\ &=& \frac{\Gamma(\alpha_{(\cdot)})}{\prod_{o} \Gamma(\alpha_{o})} \frac{\prod_o \Gamma(\alpha_o + n_o(\mathbf{z}))}{\Gamma(\alpha_{(\cdot)} + n_{(\cdot)}(\mathbf{z}))}\\ &=& \frac{\Gamma(\alpha_{(\cdot)})}{\Gamma(\alpha_{(\cdot)} + n_{(\cdot)}(\mathbf{z}))} \prod_o \frac{\Gamma(\alpha_o + n_o(\mathbf{z}))}{\Gamma(\alpha_o)}  \end{eqnarray}

Dirichlet process 版の \alpha\alpha_o の和を取った \alpha_{(\cdot)} に、\alpha_{o} \mu_{o}\alpha_o に代わる。あれっ、Dirichlet process 版は \alpha \mu_{o} のような気がする。\alphaスカラー\alpha_o なんてないように思うのだが。

ascending factorial を見ると面喰うが、少し考えて見れば、当たり前の結果。すでにいくつかのデータを観測した状態で、次の一個が入ってきたときの更新を考える。データの値に対応するカウント n_o(\mathbf{z}) が1増えて、\alpha_o + n_o(\mathbf{z}) がかけられる。同時に、総数 n_{(\cdot)}(\mathbf{z})) も1増えて、1 / (\alpha_{(\cdot)} + n_{(\cdot)}(\mathbf{z})) がかけられる。これを繰り返すわけだから、階乗が出てくるのは当然。

論文を普通に前から読み始めると、いきなり2節の式 (1) が導出できなくて涙目になったりするのだが、上の式に Dirichlet(1, 1, 1), Multi(m, m, n-1) を入れるとすぐに出てくる。

4.1 Binary Representation

\mathbf{z}^{s:0}\mathbf{z}^{s:1} は基本的には z 全体を表していて、ただし s が b = 0 あるいは b = 1 に対応する状態になっている。最初勘違いして、z の中から s に関係する部分を抜き出したものだと思い込んだ。そうすると、

\mathbf{z}^{-s} \stackrel{\mathrm{def}}{=} \mathbf{z}^{s:0} \cap \mathbf{z}^{s:1}

が意味を成さないので気付いた。

4.2 Sampling One Site

式(4)の導出。ここで p(\mathbf{z}^{s:b})=p(b_s=b,\mathbf{b}\setminus\mathbf{b}_s)

\begin{eqnarray}p(b_s=b|\mathbf{b}\setminus\mathbf{b}_s) &=& \frac{p(b_s=b,\mathbf{b}\setminus\mathbf{b}_s)}{p(\mathbf{b}\setminus\mathbf{b}_s)} \\ &\propto& p(b_s=b,\mathbf{b}\setminus\mathbf{b}_s) \\ &=& \prod_{r \in R}\frac{\prod_o (\alpha_{r}\mu_{ro})^{(n_{ro}^{-s}+\triangle n_{r\cdot}^{s:b})}}{\alpha_r^{(n_{r\cdot}^{-s}+\triangle n_{r\cdot}^{s:b})}} \\ &=& \prod_{r \in R}\frac{\prod_o (\alpha_{r}\mu_{ro})^{(n_{ro}^{-s})} (\alpha_{r}\mu_{ro} + n_{ro}^{-s})^{(\triangle n_{r\cdot}^{s:b})}}{\alpha_r^{(n_{r\cdot}^{-s})} (\alpha_r + n_{r\cdot}^{-s})^{(\triangle n_{r\cdot}^{s:b})}} \\ &\propto& \prod_{r \in R}\frac{(\alpha_{r}\mu_{ro} + n_{ro}^{-s})^{(\triangle n_{r\cdot}^{s:b})}}{(\alpha_r + n_{r\cdot}^{-s})^{(\triangle n_{r\cdot}^{s:b})}} \\ \end{eqnarray}

4.3 Sampling Multiple Sites

式 (9) の ascending factorial の scope が変。内側の分母は (\alpha_r + n_{r \cdot}(\mathbf{z}^{-S}))^{(\triangle n_{r o}^{S:m})} が正しいはず。

その他

普通の多項分布で、事前分布に Dirichlet distribution を設定しているものなら、式 (7),(9) を使えば sampling の計算ができる。もっと複雑なモデルになるとよくわからない。要は多項分布の θ が残っていたら不都合で、消去してあればよさそう。例えば LDA の Griffiths の Gibbs sampling に適用できる? この場合、同じ type というのは、同一文書中の同じ単語?