条件付き確率場 - Island Babies

あらまし

卒論でソフトウェアマイニングみたいなことをやるという方針がとりあえず定まって、色々論文読んでみな〜と言われて教えてもらった論文の一つで、 Predicting Program Properties from “Big Code” こういうのがありました。 Javascriptでコードのサイズを小さくするために色々な処理が行われるのだが、その一環で変数名をtとかmとか短いものに変換することでサイズを小さくするという処理が行われるそうで、その変換後の変数名から元の変数名を推測する、という研究です。
その中で条件付き確率場(Conditional Random Field) という考えが出てきていて、なんじゃそりゃという感じだったので一度勉強しておこうと思います。
自分でさっとメモ書き程度にまとめてみようかと思います。
ちなみに条件付き確率場を前もって知らなくても一応読めるには読める。が明らかに知っていて読んだ方がわかりやすかっただろうなと思いました。
https://www.ism.ac.jp/editsec/toukei/pdf/64-2-179.pdf この資料で勉強しました。

確率付き条件場

概要

入力系列 $\bf x \it = x_1x_2x_3x_4...x_m$ に対して、出力系列 $\bf y \it = y_1y_2y_3y_4...y_m$ を推定することを考えます。
多クラスのロジスティック回帰と同じような定式化をすると動的計画法なんかを使うとうまく計算ができるよーということが述べられています。
実際に書いてみると確かに式の表現としては多クラスのロジスティック回帰と同じよう形で定式化できています。
ここで問題になるのが、愚直に計算してしまうと候補となるラベルの数、分配関数の値、各ラベルに対するスコアの値が現実的に計算できないくらいの計算量になってしまうという点。
一般の素性関数についてはおそらく計算することは事実上難しいのではないかと思いますが、ラベル列に対して一次マルコフ性 を仮定して、素性関数の形を制限することによってうまく計算することができるようになります。
一次マルコフ性とは、各時点において、一つ前の状態が決まれば今の状態に対する制約が定まるという性質です。
例えば前置詞の後は名詞がきやすい、文の初めは(文の始まりをあるトークンだと思えばよくて)名詞がきやすい、などなど一つ前の状況によって今の状況に関する制約が得られることはままあり、それに対するモデル化であるそうです。このマルコフ性のおかげでかなりスコアの計算が楽になり、動的計画法により現実的な計算時間でスコアを計算することができるようになります。

ラベル列の推定

途中までのラベル列 $y_1y_2y_3...y_k$ に対して、ある $y_k$ を固定したとき、 $y _ {1} ... y _ {k-1}$ については、 $y_1y_2y_3...y_k$ のスコアが最大になるように $y _ 1 ... y _ {k-1}$ を計算しておきます。
そうすれば、先ほど述べたマルコフ性から、 $y _ {k+1}$ を考えるときにスコアの変化量に関係があるのは $y _ k$ のみなので、 $y _ 1 ... y _ {k-1}$ を変更する必要がなく、 $y _ {k}$ の選び方のみを考えれば最適な $y _ 1 y _ 2 ... y _ {k+1}$ を計算することができます。
これを、 $y _ 1$ から順番に計算していくことで、求めるべき $y_1y_2...y _ m$ を計算することができます！

感想

なんかマルコフ過程みたいな感じだなーと思いました。ビタビ・アルゴリズム(Viterbi algorithm)というらしく、まさしく前に聞いたことのあるアルゴリズムでした(笑) しかし、どこでやったんだろうなー。。。明らかにどこかで見たことのあるアルゴリズムであることは間違い無いんですけどね。そこそこ昔からあるアルゴリズムのようですが、単純に用いるだけでもそれなりに精度が出そうなアルゴリズムだなーと思いますた。

最近はニューラルネットが流行りがちですが、こういう昔のアルゴリズムを学んでモデル化とかのアイデアを知るのも大切なのかなと思ったり思わなかってりしています。