研究に関係して, Mark Johnson, Tom Griffiths, Sharon Goldwaterの "Bayesian Inference for PCFGs via Markov Chain Monte Carlo" (NAACL-HLT 2007) を読んだ。面白い。

PCFGはS->VP NP, NP->DT NN, DT->"the", N->"cat" のような生成規則と, S->NP, S->VP, S->VP NPのように非終端記号を展開する複数の可能性があった時に, それぞれが使われる θ=[0.05, 0.2, 0.75]のような確率分布からなる。PCFGのベイズモデルは, この確率分布がディリクレ分布から生成されたとするもの。
ディリクレ分布のハイパーパラメータαを小さくすることで, θが偏った分布である という仮定を置くことができ, 関係するデータ量が少ない場合でも最尤推定に比べて 安定した推定が可能になる。
PCFGをベイズ化するという話自体は 栗原君 が変分ベイズで 前にやっている のですが(この論文でどうして引用されていないのか謎ですが..), 今回はMCMCなので, 各規則に対するパラメータの最適化が独立ではない, という利点があるのだと思う。

具体的には,

• Gibbsの場合
  　(文法規則は所与なので)確率分布θと, それに従った各文の構文木t をそれぞれ具体的にサンプリングする.
• Metropolis-Hastingsの場合
  　θを積分消去して, 構文解析tだけを直接, 次々とサンプリングする.

という2つのパターンになる。 後者の場合, 内部ではθとして事後分布の期待値を使ったものをproposalとして, 前の構文解析の尤度と比べて, 新しい構文解析をacceptするかどうかを 決めるらしい。
結果的には, 性能は普通の文に関しては *1 Inside-outsideを使った通常の最尤推定と同様にあまり良くない(与えられたPCFGが 自然言語を記述するのに充分でない)そうですが, 面白かったのは, 文wに対して, 構文木tを「サンプリングする」というところ。
これは, 先に文に対してinsideテーブルを動的計画法で計算しておいて,

(j,A,B) = Mult(X,w)

のようなサンプリングをトップダウンに, 再帰的に適用することで 構文木をサンプリングする方法。
Mult(X,w) は, 非終端記号Xとみた文字列wに対して, これを位置jで切って左側をA,右側をBに展開するペア(j,A,B)を確率的に返す関数。 Mult(S,w) から始めると, S->NP VP のような可能性と, 切る位置 j が 返され, 今度は左側と右側の部分文字列に対して, それぞれNPとVPなので, NP->DT N や NP->N のような展開の可能性に対して同様に再帰的にサンプリングを 行って, 最終的な単語列を得ることができる。
上の(j,A,B)はp(j,A,B|X)の意味なので,

p(j,A,B|X) ∝ θ(X->A B)p_A(w(i,j)|θ)p_B(w(j,k)|θ)

として確率が計算できる。ここでp_X(s|θ)はパラメータθの下で, 非終端記号Xが 文字列sになる確率で, inside確率を計算しておくと求まる。

さて, Mark Johnsonのページ を見ると, C++の実装 gibbs-pcfg.tgz が置いてあったので, ちょっと試してみました。

wave:/tmp/gibbs-pcfg% ./gibbs-pcfg -n 5000 -a 0.01 -A result -G grammar testengger.lt < testeng.yld   
wave:/tmp/gibbs-pcfg% v grammar 
1               ROOT --> S
1               S --> NP VP
1               NP --> Det N
7.84215e-34     VP --> V
0.651455        VP --> V NP
2.6057e-61      VP --> NP V
0.348545        VP --> V NP NP
3.9252e-13      VP --> NP NP V
0.39633         Det --> the
1.58667e-15     N --> the
3.2873e-06      V --> the
0.600561        Det --> a
4.70053e-09     N --> a
1.61862e-10     V --> a
2.81297e-35     Det --> dog
0.264735        N --> dog
7.40429e-45     V --> dog
3.32051e-47     Det --> man
0.465411        N --> man
5.02489e-19     V --> man
1.27336e-08     Det --> bone
0.269448        N --> bone
2.87335e-27     V --> bone
5.31171e-77     Det --> bites
0.000406084     N --> bites
0.49108         V --> bites
0.00310949      Det --> gives
6.50102e-09     N --> gives
0.508917        V --> gives
wave:/tmp/gibbs-pcfg% v result 
(ROOT (S (NP (Det the) (N dog)) (VP (V bites) (NP (Det a) (N man)))))
(ROOT (S (NP (Det the) (N man)) (VP (V bites) (NP (Det a) (N dog)))))
(ROOT (S (NP (Det a) (N man)) (VP (V gives) (NP (Det the) (N dog)) (NP (Det a) (N bone)))))
(ROOT (S (NP (Det the) (N dog)) (VP (V gives) (NP (Det a) (N man)) (NP (Det the) (N bone)))))
(ROOT (S (NP (Det a) (N dog)) (VP (V bites) (NP (Det a) (N bone)))))

かなり妥当な結果になっているのが面白い。 データが少ないのでこの解析は5秒くらいですが, Gibbsのiterationを少なくすると, 正しくない解が出ることもあるのがMCMCっぽい。 *2

これまで, 構文解析は自分にはあまり必要がなかったのと, 動的計画法で効率的に 計算するというのは離散数学の常なので, ふーん, よかったね, という感じだった のですが, こうやって具体的に構文木をサンプリングできるというと, がぜん 面白いような気がします。 いわゆる構文解析のN-bestはビタビの拡張でビームサーチをしているのでは ないかと予想するのですが(多分), バラエティを増やして安定した推定を 得るためには, こうやって確率的に正しい構文解析結果をサンプリングする, というのも興味深い感じです。

なお, この論文ではPCFGの規則を人手で与えていますが, これは The Infinite Tree のような形で, 係り受け解析結果からノンパラメトリック ベイズで学習することができそうです。 ので, ありそうな方向としては, 係り受け解析済み(係り受け解析なので文法的なタグ はない)に対して, The Infinite Tree でPCFGを教師なし学習して, この論文のような 形で構文木をサンプリングするのは面白そうです。 *3

---