murawaki の雑記

はてなグループから移転してきました

Adaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Models

NLP

Mark Johnson, Thomas L. Griffiths and Sharon Goldwater (2007) Adaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Models, NIPS 19.

最近雑記を書いていない。なぜか。全然新しことをやってないから。この論文も 2006/7 年の話で今更すぎる。以前の雑記で取り上げたこともあるし。とはいえ、細かい点を整理したいので書きだしてみる。

Adaptor Grammar は PCFG (確率的文脈自由文法) の拡張。まずは応用例から。いわゆる単語分割が CFG の規則で記述できる。例えば以下の規則。

Sentence → Word
Sentence → Word Sentence
Word → Phonemes
Phonemes → Phoneme
Phonemes → Phoneme Phonemes

ある文は単語の列からなっていて、ある単語は音素の列からなっていますという自然な話が自然に記述できている。これらの規則と生テキストをモデルに与えると、モデルが適当に分割してくれる。普通に生成モデルを考えるのと比べて何がうれしいかというと、モデルの拡張が容易なこと。単語の平板に並んでいるのではなく、コロケーションを考慮したいとか、音素が平板に並んでいるのではなく、音節構造を考慮したいとか。普通にモデルを書いていて、こういう拡張を入れようと思うと、モデルを書き換えまくらないといけない。Adaptor Grammar だと文法規則を書き換えるだけですむ。うまい抽象化。生成モデル業界は、自分でモデルを考えて、自分でゴリゴリ実装して当然みたいな雰囲気があるので、なおさらそう思う。

別の例。トピックモデル。LDA 相当のものが CFG で書ける。

  • \mathrm{Sentence} \rightarrow \mathrm{Doc}_j^{\prime}
  • \mathrm{Doc}_j^{\prime} \rightarrow {}_{-j}
  • \mathrm{Doc}_j^{\prime} \rightarrow \mathrm{Doc}_j^{\prime} \mathrm{Doc}_j
  • \mathrm{Doc}_j \rightarrow \mathrm{Topic}_i
  • \mathrm{Topic}_i \rightarrow w

文書jに対して、\mathrm{Doc}_jが1個の単語に相当する non-terminal。これからまずトピック i に相当する non-terminal \mathrm{Topic}_i を導出。次にトピックから具体的な単語 w を導出。つまり \mathrm{Doc}_j \rightarrow \mathrm{Topic}_i が、文書 j のトピック分布、\mathrm{Topic}_i \rightarrow w がトピック i の単語分布を表している。残りの部分は単語列を表現するための規則。

トピックモデルを CFG で表現して、何がうれしいかといえば、やはり拡張性。bag-of-words をやめて、単語の列が同じトピックになりやすいように HMM を入れるとか。ここまでは単なる Bayesian PCFG だが、さらに Adaptor Grammar にすると、コロケーションを考慮するトピックモデルも作れる。

PCFG なのだから、普通の文の parsing に使えないかと考えるのは自然な流れ。でもそれには問題がある。それを説明する前に、まずは中身の説明。

基本は普通の (Bayesian な) PCFG。ただし、あらかじめ指定したいくつかの non-terminal について、そこから導出される部分木をまる覚えする。いま、モデルから次々と木を生成することを考える。モデルは、それまでに生成した部分木をキャッシュする。次の木はその頻度に比例する確率で生成される。ある non-terminal をまる覚えの対象にすることを adapt すると呼ぶ。

とりあえず adapt する non-terminal を A とする。論文では G_A という見慣れない分布が定義されていて面食らう。PCFG では、通常は、個々の規則の生成確率の掛け合わせを考える。Adaptor Grammar では部分木をまる覚えしたいから、A から、non-terminal を全部展開してできた木の分布を考える。それが G_A。一般にそうした木の異なり数は不定。nonparametric Bayes の出番となる。

最後まで展開した木を分布を用意したら、次はそれをキャッシュ。adapt された分布を H_A とする。例によって Chinese restaurant process が出てくる。客が次々にテーブルに座って行く。テーブルに付与されるラベルは、ある部分木。当然、複数のテーブルに「同じ」木がラベル付けされることもある。新たなテーブルに座る場合は、基底測度からラベルを振る。その基底測度は構成的で再帰的。A \rightarrow B_1 \, B_2 について、これ自体の生成確率 \theta{A \rightarrow B_1 \, B_2} と、H_{B_1}、H_{B_2} からの生成確率を掛け合わせる。つまり、B_1, B_2 についてもレストランでテーブルに座るという操作が行われる。

この再帰性が実は厄介。普通の文の parsing に使うと問題が生じるのはこれが理由。adapt した non-terminal A を展開して行って、また A が出てきたらどうなるか。どのテーブルに座るか決める最中に、バックオフの客が同じレストランにやってきてどのテーブルに座るか決めることになる。Mark Johnson は「そういうことすると inference が複雑になるからやらないよ」(footnote 1) と言っている。どういう手続きなら (たとえ複雑でも) 理論的に問題ないのか教えて欲しいところ。Adaptor Grammar の変分推論を考案しましたという人たちは、子孫の客が同じテーブルに座らなければ大丈夫というようなことを言ってる (Sec 3.1)。正確には stick-breaking process で説明しているが、Chinese restaurant process に置き換えればそういう意味になるはず。変分推論なら、ill-defined な部分を 0 にして正規化しなおすという手続きを入れられるけど、積分消去する MCMC ならそんなことできないねと言われて、変分推論初級の私は涙目。

論文をぼーっと読んでいると再帰の議論についていけず混乱する。上述の単語分割の規則に

Sentence → Word Sentence

とあるのは再帰じゃないのか、これは駄目なんじゃないかと誤解する。実際には、Sentence は adapt しないので問題ない。adapt しないと単なる PCFG。単なる PCFG を Chinese restaurant process で解釈すると、客を常に新たなテーブルに座らせるという操作にあたる。子孫の客が同じテーブルに座ることは原理的にありえない。

単語分割の例で adapt するのは Word。音素列の生成確率をバックオフで考慮しつつ、単語という部分木をキャッシュする。これだけだとあまりありがたみがないので、コロケーションを導入。

  • \mathrm{Sentence} \rightarrow \mathrm{\underline{Colloc}}^{+}
  • \mathrm{\underline{Colloc}} \rightarrow \mathrm{\underline{Word}}^{+}
  • \mathrm{\underline{Word}} \rightarrow \mathrm{Phoneme}^{+}

{}^{+} は右再帰の略記、下線が adapt される non-terminal。この規則だと、Colloc をまる覚えしつつ、その構成要素の Word もまる覚えする。

推論は sampling による。文単位の block sampling。chart を下から上に確率質量で埋めていって、根まできたら top-down に sampling。何しろ部分木を覚えているので、途中のセルの確率は、下のセルの組み合わせ確率とキャッシュされた部分木の確率の和となる。

他の論文でよくあるのは、この文単位の block sampling で Gibbs sampling をするもの。Mark Johnson はそうではなく、component-wise Metropolis-Hastings とする。block sampling を提案分布からの draw として、まじめに受理確率を考える。だからたまに提案を棄却する。この補正を入れているのは、block sampling が近似だから。本来は、文を生成している途中にどんどんキャッシュのカウントを更新しないといけない。でもそんなことをしていたら動的計画法で解けない。だからカウントを固定して sampling をするけど、そのままだと気持ち悪いから補正を入れる。しかし、MCMC 自体が近似的な大域解探索なわけで、受理確率を計算する代わりに、その分だけ余計に block sampling をまわした方が実際上良さそうな気がする。