2010-05-30
Bayesian Inference for PCFGs via Markov chain Monte Carlo
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 で決める。よくこんな方法を思いつくものだ。
2010-05-19
The Infinite Tree
The Infinite Tree (ACL 2007).
依存木が与えられたとき、その木構造をうまく説明する品詞を Gibbs sampling により求める。簡潔で的確な解説が既にある。そっちを読んだほうが良い。
sampling 系の話題。私がこれまで読んだ論文は系列データを扱ってきた。今回は tree を扱う。一般に tree の話は難しい。候補が爆発するので計算を工夫する必要があるから。でもこの論文は簡単。tree そのものはいじらないで品詞だけをいじる。
標題が misleading。infinite tree の素直な解釈は、木の幅や深さが無限という状態。実際の意図は、ノードについている状態の数が無限ということ。
依存木の親子関係を考えた時、兄弟同士を独立と仮定する。生成モデルなので、親の品詞が与えられた時、子の品詞の確率を考える。モデルとして多項分布、事前分布として Dirichlet 分布を仮定するのが自然。数を数えて事前分布の擬似カウントを足すだけの簡単なお仕事で事後分布が求まる。
ひとまず品詞の数を C に固定する。親が C 種類、子が C 種類で C x C の matrix を管理することになる。同様に、品詞が与えられたときに単語が生成される。語彙数を N とすると、C x N の matrix。
これに品詞数 C を事前に与えないという拡張を行う。Dirichlet process の出番。宣言的には品詞数は無限。手続き的には、既に観測されている品詞の集合と、まだ観測していない品詞の集合に分離できる。管理する品詞の数は常に有限。遅延評価。今観測した品詞数を C' とすると、C' x C'、C' * N の matrix。実装には hash を使うだろうが。
最終的なモデルでは Dirichlet process がさらに階層化されて 2 段階になっている。上に β という変数が乗っていて、親子関係の Dirichlet process の基底分布になっている。人に説明したら、この部分がわかりにくいと言われた。β がないと事前分布が情報を持たない。親が与えられたときの子の品詞の分布がバラバラに決まることになる。β を用意して、sampling により適切な値が設定されることで、品詞の一般の分布が基底分布になる。N-gram の back-off のような役割。
今まで読んできた sampling 系の論文はおもちゃ感があった。この論文もおもちゃだけど、問題設定が実用的。実際に係り受け解析の精度が上がる。人間が設定した品詞体系なんて駄目で、データに語らせたらもっとよい体系が出てくるというお話だけではない。
inference。各単語に対応する品詞を一つ一つ sampling していく。inside-outside とか、ややこしい話は出てこない。その分効率は良くないと思われる。品詞の数が1,000とかになってくると、1回の sampling だけでも大変そう。β を sampling する部分がわからない。Teh との p.c. とあるのみで、それ以上の説明がない。
以下疑問。count を一回の sampling の途中で update する必要はないのか。Goldwater の論文は CRP で説明していた。stick-breaking process による説明だと勝手が違うのだろうか。もっとも、update が必要になるとしたら、一つは3世代すべて同じ品詞の場合だが、英語でそんなことはなさそう。もうひとつは自分と子の組がかぶる場合だが、実際のモデルでは、係り先が左か右かで分けているので、こちらもあまりなさそう。いろいろ理解できていない予感。
sampling の途中で、品詞を一度作って (観測して)、その後 count が 0 になったらどうするのか? Goldwater は空になった table を消していたが、この論文にはその手の記述がない。また、実験結果で報告されている品詞数に空のものが含まれているかどうかで話が変わってくる。
2010-05-12
cron on cygwin
cygwin で cron を動かそうとしてはまったのでメモ。
はまった点は三つ。複合的なので症状と原因の整理はできていない。
- cron が起動時にエラーを吐く。
- crontab がすぐに反映されない。
- 通常と環境が違う。ssh-agent を反映させるのが面倒。
サービスの登録には普通は cygrunsrv を使う。sshd はこの方法でうまく行った。ただし、Windows 7 では「管理者として実行」する必要がある。
以下のコマンドの場合、エラーメッセージが返ってくる。
cygrunsrv --install cron --path /usr/sbin/cron --args -D cygrunsrv --start cron
いろいろ調べたところから推測すると、利用者 SYSTEM として実行しようとすると不都合な環境であるらしい。
解決策。/usr/bin/cron_diagnose.sh という便利なスクリプトを実行。run as yourself という質問に対して yes と答える。これで cron が私の権限で実行されるようになった。ここでも「管理者として実行」が必要。
二つ目の問題は、Wikipedia に「よくあるミス」として載っていた。デバッグのために cron の実行時刻として 40 秒先とかを指定して crontab で登録すると、すぐには実行されない。実行時刻を少し先にすると解決。
最後の問題。cron の実行は環境設定が異なる。そのため、ssh を使う処理は、ssh-agent の chain が切れているので失敗する。keychain という utility を使えばいいらしいことを知ったが、いつものように環境変数 SSH_AUTH_SOCK を自力で設定することによって解決。