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 を消していたが、この論文にはその手の記述がない。また、実験結果で報告されている品詞数に空のものが含まれているかどうかで話が変わってくる。
