Hoifung Poon, Colin Cherry, and Kristina Toutanova: Unsupervised Morphological Segmentation with Log-Linear Models, NAACL2009. (PDF)
NAACL2009 の best paper。また unsupervised word segmentation の論文。表題にあるように、log-linear models を用いる。log-linear model といえば CRF が有名だが、何しろ unsupervised なので訓練用の正解データがない。そこで疑似負例を作って観測データとの識別を試みる。パラメータを厳密に求めるのが困難という問題に対しては、Gibbs sampling で対処。その結果、従来研究よりも高い性能が得られたという。
unsupervised word segmentation の従来研究と比べると異質。従来研究は生成モデルを仮定していた。HMM とか Dirichlet Process とか。log-linear model は同タスクでは類例がなく、直接的な関連研究は POS tagging とか coreference resolution とかになる。こういう、一般的な手法を武器にいろんなタスクを解いていく人って怖い。
その一般的なモデル。log-linear model なので、確率は、e の指数に重み付きの素性列をぶちこみ、正規化項 Z で割ったもの。この Z がミソで、Z に入っている状態同士が 1 の確率質量を奪い合う形になっている。だから、正解データがある場合には、重みを調整して正例の確率を最大化すればよい。そうすると、相対的に負例から確率質量が奪われる。つまり、条件付き確率 P(y|x) を log-linear model で定義。Z としては x に対する y の候補すべてを考える。正例 y* について log P(y*|x) を最大化。普通に偏微分して山登り。
しかし、正解データがない。つまり、x の観測データ x* はあるけど、y のデータがない。そこで、条件付き確率のかわりに同時確率 P(x,y) を log-linear model で定義する。問題は Z をどうするか。まず観測データ x* と、それに対する y の候補のペア、(x*, y_{x*,1}), (x*, y_{x*,2}), ... を Z につっこむ。さらに、観測データ x* から x の疑似負例 x1, x2, ... をいくつか作り、(x1, y_{x1,1}), (x1, y_{x1,2}), ... (x2, y_{x2,1}), (x2, y_{x2,2}), ... を Z につっこむ。そして log P(x*) を最大化する。P(x) は、P(x,y) を y で周辺化して得る。つまり、疑似負例から観測データに確率質量が移るようにパラメータが調整される。
これだけでは実感がわかないので、具体的なデータを考える。segmentation タスクでは、入力は単語のリスト W、出力は W の各単語を形態素に分解した S。P(W,S) を log-linear model で定義する。分解したい単語リスト W* は与えられるけど、S のデータはない。P(W) は、P(W,S) を S で周辺化して得る。つまり、W に対して考えられる分割 S をすべて計算すると求められる。
入力、出力とも巨大。形態素解析などのタスクでは、独立性を仮定して、入力、出力を bigram などの細かい単位に分割するけど、このタスクでは、お化けみたいなデータをそのまま扱う。具体的には、素性列として形態素素性と文脈素性を考える。入力は P(W,S) であり、とりあえず分割 S が与えられているので、各形態素の出現数が数えられる。これが形態素素性。各形態素の前後 N 文字 (N=2 なら (c_-1, c_-2, c_1, c_2) という文字の列) を数える。これが文脈素性。文脈素性をこういう設計にした理由は述べられていない。多分、実験データがアラビア語とヘブライ語だから。語構成として (接頭辞)? 語幹 (接尾辞)? を想定している。語幹に対する文脈素性は、語幹を挟む接辞 (の一部または全部) のペアとなる。こうしたペアの数は限られているから、語幹の同定に役立つ素性となるのだろう。接辞に対する文脈素性は使い物になりそうにないけど。
W* から W の疑似負例を作る。具体的には、W の各単語の隣り合う文字を入れ替える。Alrb に対して lArb とか Arlb とか。この操作により、ほとんどの場合嘘の単語ができる。W に対してはすべての S を考えるので、W がまともなデータでも S がおかしければおかしな素性が出てくるけど、W がおかしなデータならもっとおかしな素性になるはず。これを疑似負例とすることで、正しい素性に大きな重みがつくようになるはず。いかにも効率悪そうだけど。
実際には、素性としてさらに lexicon prior と corpus prior をつっこむ。lexicon prior は under-segmentation に、corpus prior は over-segmentation にペナルティをかけるようになっている。このうち、lexicon prior がパラメータ推定をするときに障害になる。お化けみたいなデータから一気にパラメータを推定できないから、局所的な分割操作を繰り返して推定するのだけど、lexicon prior のせいで、局所データ同士が相互依存になっていて、ある場所の分割を変えると別の局所的な確率も変わってしまう。そこで Gibbs sampling を行う。
sampling で推定したいのは、尤度の偏微分の計算に必要な f_i の期待値。2種類あって、P(S|W*) における期待値と P(W,S) における期待値。Gibbs sampling なので、1箇所のみに注目して、他のパラメータは固定する。この場合、S のうち、残りの単語の分割を固定した状態で 1単語の分割を考える。このあたりの説明を論文は端折りすぎ。明記されていないけど、ここでは多分 P(s|w,h) を考えている。ただし、h は固定されているパラメータ。w が Alrb とすると、s として Alrb, A-lrb, ... A-l-r-b と 8 通りが考えられる。それぞれの確率は、現在のパラメータ λ から計算できる。その確率に従って s を draw する。こうして新たな S が得られる。こうして S を m 個 sampling し、各々の場合の f_i の平均をその期待値とする。こうして f_i の期待値が得られると偏微分の値が決まり、山登りすれば log P(W*) を最大化できる。*1
実際の計算では、どれだけのデータを track すれば期待値が計算できるのか。頭が整理できていない。まず、f_i(S) の計算はどうやるのか。私の理解が正しければ、現在の f_i(S) の値を持っていれば、期待値は、1単語の分割を変化させたときの素性値の差分だけを考えればよい。次に、疑似負例はどうやって処理するのか。多分、疑似負例のリスト W は track しておらず、1単語に注目するたびに嘘単語を作っている。そもそも疑似負例 W の数は不定のはず。w が "Alrb" とすると、w の疑似負例は 3 通り、"lAlrb" には 4 通り考えられる。
*1:最大値か極大値か自信がない。lexicon prior があるから。
