系列ラベリングのための Forward-Backward アルゴリズムの一般化

これも、頑張れば、breakthroughになりそうな研究。前向き後ろ向きアルゴリズムというと、隠れマルコフモデル(HMM)のBaum-Welchアルゴリズムが有名だけど、実は、HMMに限らず、前向き後ろ向きアルゴリズムで行っている計算は、系列ラベリングを行う時に本質的に必要になってくる。
結局、入力系列\mathbf{x}と出力系列(ラベルの系列)\mathbf{y}があるとき、パラメータ\mathbf{w}と、パラメータの良さ評価する関数f(\mathbf{y},\mathbf{x};\mathbf{w})を作ってやって、これを最大化するようにしてやるわけだ。今、ある入出力ペア\mathbf{x}_0,\mathbf{y}_0とパラメータ\mathbf{w}_0があるときに、さぁ、このパラメータ\mathbf{w}_0がどれだけ良いパラメータなのですか?ということを測りたい。測るのに使えるデータは、出力系列(正解のラベル系列)\mathbf{y_0}だけ。

まっとうな方法は、その入力\mathbf{x}_0とパラメータ\mathbf{w}_0を与えた時の全ての出力系列のパターンと比較して、\mathbf{y}_0がどれだけ寄与するか(確率で考えれば、出やすいか)を計算することだろう。つまり、\frac{f(\mathbf{y}_0,\mathbf{x}_0;\mathbf{w}_0)}{\sum_{\mathbf{y} \in \mathbf{Y}} f(\mathbf{y},\mathbf{x}_0;\mathbf{w}_0)}を計算してやる。

条件付確率場(Conditional Random Field, CRF)は、この関数fが、f(\mathbf{y}_0,\mathbf{x}_0;\mathbf{w}_0)=exp(\mathbf{\phi}(\mathbf{y}_0,\mathbf{x}_0)^T \mathbf{w}_0)の形をとる時の話なわけだ。fの形が複雑だと、\sum_{\mathbf{y} \in \mathbf{Y}}が出力系列長|\mathbf{y}|に対して指数関数的になるので、長い系列が事実上計算できなくなる。この論文は、このfとしてどんな関数が取れるかを考えて、その関数の幅を広げましたよ、という話。さらに、fをテイラー展開で近似するのでよければ、fとして大抵の関数は持ってきてよさそうだ、ということも書いてある。

恥ずかしながら、HMMのBaum-Welchと、CRFのZ項の計算が本質的に同じものだって、この記事書いてて初めて理解しました。もっと勉強しなければ・・・