Sharon Goldwater, Thomas L. Griffiths, and Mark Johnson: A Bayesian framework for word segmentation: Exploring the effects of context, Cognition, 112(1), pp. 21-54. 2009. (PDF)
unsupervised word segmentation の論文。unsupervised word segmentation とは、語彙知識を与えず、テキストだけを与えて、単語分割を得るタスク。それを nonparametric Bayes の生成モデルでやったという話。無茶なタスクだし、実用レベルかは疑問だが、ある程度うまくいくのが恐ろしい。
表題の論文はジャーナルのものだが、元は ACL2006 の論文で、表題は Contextual Dependencies in Unsupervised Word Segmentation。「contextual dependency って何だ。構文解析でもやるのか」と思うところだがさにあらず。unigram に対する bigram モデルを指していてる。unigram だと、単語が前の単語とは独立に生成されるけど、bigram だと前の単語に依存する。論文の主張は、bigram モデルを使って単語間の連接をモデルに組み込んだ方が性能が良いというもの。対する unigram モデルは、what's that のような高頻度のフレーズを1語とみなしがちである。当たり前じゃないかと直観的に思うところだが、従来研究の実験結果ではそうでなかった。おかげで、従来手法の分析にかなり紙面を割いている。
なぜこの論文かと言えば、nonparametric Bayes の word segmentation が、理論的にも実装的にも魑魅魍魎の世界へ突入しつつあるなか、まだ手の届くところにあるから。もっと具体的に言うと、持橋大地氏の一連の論文を前々からぼちぼち読んでいるものの挫折気味。もっと基本的な手法から攻めようと考えて、たどり着いたのがこの論文。
この論文の良いところは、(1) あれこれやらずに単純なモデルを使っていること。(2) 説明が丁寧なこと。論文の解読でつまづく類型の一つに、式変形が追えないというものがある。ACL-2006 版はいろいろ端折っているけど、ジャーナル版は細かく説明している。飛躍があるところでは「これ嫁」と論文を cite しているので、なぜそうなるかが分からなくても、少なくとも何をやっているかは分かる。(3) さらに、素晴らしいことに、第一著者のサイトで C++ による実装が公開されている。実際にプログラムを動かしてみると疑問も解消する。
ただし、モデルの説明は appendix に追いやられている。論文の内容の中心は、Cognition というジャーナルの名前から分かるように認知系となっていて、赤ちゃんがどうやって言語を獲得するかを延々議論している。実際、扱っているコーパスも、赤ちゃんに向けられた発話 (英語) を1音素1文字で記述したもの。*1この議論も面白いけど、工学の人間としては appendix の方が重要。
前置きはこのくらいにして本題。生成モデルなので、コーパスがそのモデルから生成されたと仮定し、与えられたコーパスから反対にモデルのパラメータを推定する。単語は音素列から、文は単語列から生成される。単語のモデルは unigram が Dirichlet Process、bigram が Hierarchical Dirichlet Process であり、各々 Chinese Restaurant Process によって説明される。大仰な名前に戸惑うが、N-gram とその smoothing に理論的説明を与えただけの代物と思えば怖くない。
普通の N-gram モデルでは、コーパス中の出現頻度で最尤推定をやると、コーパス中で観測されなかった単語の確率が0になるなど不都合がある。だから既知の単語に割り当てられた確率を少し削って、未知の単語に割り振るということをやる。これと同じようなことを生成モデルでやる。unigram なら音素モデル (zerogram)、bigram なら unigram のバックオフを用意する。
生成モデルでは、process (確率過程) なだけあって系列変化を考える。モデルは単語を前から順番に生成していくが、ある時点で次に生成する単語の確率は、既に生成した単語の割合に比例する。例えば、5単語生成した時点で the が 2 回出てきたら、次の単語が the である確率はおよそ 2/5。およそというのは、少し確率を削るからで、削られた確率は back off の確率分布に割り当てられる。これによって未知の単語にも確率を与える。ただし、back off の確率分布から draw した結果、既知の the が出てくることもある。
モデルを作ったら次は推定 (inference)。Gibbs sampling を使う。パラメータはコーパス中のすべての境界候補で、各々が区切るか区切らないかの2値を持つ。適当な初期値から始めて sampling を繰り返すと、モデルの事後分布に近づく。つまり、sampling を終えると、モデルに基づいて単語分割されたコーパスが得られる。
一つのパラメータをサンプリングするということは、ある位置で区切るか区切らないかを考えること。ここで Dirichlet Process の交換可能という性質を利用する。文は単語を順番に生成して作られるが、生成順序を交換しても文の生成確率は変わらない。いま、注目箇所を区切るか否かを考えるとき、注目個所以外がすべて生成済みと見なせる。つまり、コーパスの残りの部分で単語を数えれば、その割合にほぼ比例する確率で、注目箇所の単語が生成されることになる。これは簡単に計算できる。この Gibbs sampling の難点は、持橋氏の指摘する通り、収束がとても遅いこと。
以上は unigram モデルでも bigram モデルでも当てはまる話だが、もちろん違う部分もある。unigram モデルだと、Chinese Restaurant の table、つまり内部状態に依存しない。実際に生成した単語の数だけを数えれば、次の単語の生成確率が求まる。一方、bigram だと、table の状態に依存する。推定のときも table の状態を管理しないといけない。どうするかと言うと、まず生成する単語を決める。次にその単語が割り当てられた table がどれかという確率分布を考えて、実際に draw する。論文ではさらっと記述しているけど、実装を見るとそこそこ面倒な処理をしていた。
2009/08/10 追記: ACL2009 の short paper に 実装を間違っていたという論文が出ていた。上記の bigram の推論は、間違っていた ACL 版ではなく、一応訂正したもの。
