Bayesian Inference for PCFGs via Markov chain Monte Carlo (PDF).
The Infinite Tree は、木を扱うものの依存木自体は与えていた。今回は木構造自体を教師なしで求める。気が狂いそうな論文。
移動中に読んだ論文。着いてから調べると、案の定的確な解説があった。おまけに著者がプログラムを公開している。
入力。コーパスと CFG の規則。出力は CFG に確率のついた PCFG、それにコーパスの構文木。入力コーパスの状態がはっきりしない。木構造の教師データは不要だが、少なくとも単語分割されている必要があるはず。POS タグ (preterminal) も勝手に推定するので不要。現実的には付けておいたほうがまともな結果がでそうだけど。
あまり現実的でない問題設定。最終的には、単語分割もされていないただのテキストから木構造を一気に推論してほしいところ。まだまだおもちゃで研究途上。
木構造を教師なしで学習する話をあまり聞かない。一つは私の勉強不足。もう一つはうまくいっていないから。頑張って EM を回しても結果が悲惨。事前分布を与える今回のモデルでも結果は悲惨。仕方がないのでおもちゃの設定で結果を報告している。文ではなく、ソト語の動詞の構造を推定。この実験のどこが excellent test-bed なのかわからない。うまくいかない原因の一つとして、PCFG のモデル自体が糞なんじゃないかと言っている。著者は実際にその手の調査をしていたはず。
モデル。CFG の生成規則 A → β を考える。A が与えられたとき、β に何を取るか。多項分布とする。事前分布は Dirichlet 分布。そのパラメータを sampling により推定。普通の Gibbs sampling は隠れ状態を一つずつ sampling していく。しかし木構造の候補は複数あって、個々の隠れ状態は固定じゃない。どうやって一つずつ sampling すればいいのか分からない。この論文では木をブロック単位として sampling する。
木の sampling。文をなす単語列と現在のパラメータが与えられたとき、構文木を sampling する。素直にすべての木の候補を列挙していたら終わらない。同じ計算をまとめて効率化する。結局やることは普通の木のパラメータ推定で出てくる inside-outside の変形。bottom-up に木の断片の確率を計算しておいて、top-down に確率的に断片を選択していく。いきなりこんな複雑な説明を聞いても分からないところだが、より簡単な系列データに対する forward-backward による sampling 手法を先に読んでいたので感じはわかった。ここまでが Gibbs sampling。
Gibbs sampling は EM のように並列化できると言う。そんなことをいきなり言われても戸惑う。コーパス全体をブロックとする、一応は Markov chain なのだろうが、一個ずつちびちび更新していく Gibbs sampling のイメージからかけ離れている。
後半は Hastings sampling。深くは理解できていない。PCFG のパラメータを積分消去して、木の状態のみを Markov chain で変化させていく。とはいえパラメータがないとまともに生成確率が計算できない。パラメータとして、sampling 対象の木を除いたコーパスから得られる期待値を使う。このパラメータのもとで次の木の候補を inside-outside で sampling し、これを採択するかを Hastings で決める。よくこんな方法を思いつくものだ。
