mots quotidiens. | |
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
|||||||||||||||||||||||||||||||||||||||||||||||
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なので,
各規則に対するパラメータの最適化が独立ではない, という利点があるのだと思う。
具体的には,
(j,A,B) = Mult(X,w)のようなサンプリングをトップダウンに, 再帰的に適用することで 構文木をサンプリングする方法。
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
タイトル一覧 |