系列ラベリングのための Forward-Backward アルゴリズムの一般化
これも、頑張れば、breakthroughになりそうな研究。前向き後ろ向きアルゴリズムというと、隠れマルコフモデル(HMM)のBaum-Welchアルゴリズムが有名だけど、実は、HMMに限らず、前向き後ろ向きアルゴリズムで行っている計算は、系列ラベリングを行う時に本質的に必要になってくる。
結局、入力系列と出力系列(ラベルの系列)があるとき、パラメータと、パラメータの良さ評価する関数を作ってやって、これを最大化するようにしてやるわけだ。今、ある入出力ペアとパラメータがあるときに、さぁ、このパラメータがどれだけ良いパラメータなのですか?ということを測りたい。測るのに使えるデータは、出力系列(正解のラベル系列)だけ。
まっとうな方法は、その入力とパラメータを与えた時の全ての出力系列のパターンと比較して、がどれだけ寄与するか(確率で考えれば、出やすいか)を計算することだろう。つまり、を計算してやる。
条件付確率場(Conditional Random Field, CRF)は、この関数fが、の形をとる時の話なわけだ。fの形が複雑だと、が出力系列長に対して指数関数的になるので、長い系列が事実上計算できなくなる。この論文は、このfとしてどんな関数が取れるかを考えて、その関数の幅を広げましたよ、という話。さらに、fをテイラー展開で近似するのでよければ、fとして大抵の関数は持ってきてよさそうだ、ということも書いてある。
恥ずかしながら、HMMのBaum-Welchと、CRFのZ項の計算が本質的に同じものだって、この記事書いてて初めて理解しました。もっと勉強しなければ・・・