隠れマルコフモデル（HMM）と条件付き確率場（CRF）
ブログやTwitterではある製品や番組、映画、書籍などについての個人の意見が公開されている。これらの情報を適切に抽出し、市場トレンドや購買行動を把握するために、条件付き確率場（CRF）という考え方が用いられている。
少し前置きが長くなるが、このような識別モデルについてご紹介したい。
隠れマルコフモデル（HMM）
まず、伝統的に用いられてきた隠れマルコフモデルである。前回、ある一定範囲の履歴に限定して出現確率への影響を判断する、マルコフモデルを紹介した。
例えば、天気予報の1階マルコフモデルは、下記のような遷移図で表現できる。
曇りの次に晴れが出現する確率は0.2、雨の次に晴れが出現する確率は0.5、というように理解できる。
これに対して、HMMとは、観測されない状態があり、その隠れた状態間である確率の遷移が起こって、遷移した各状態からさらにある確率で記号が出力されると考えるモデルである。言葉だけの説明では難しいため、具体例を示してみよう。
HMMによる品詞タグ付け
英語の品詞タグ付けの問題を考えてみる。よくある問題として、
Time flies like an arrow.という文が、
①Time flies like an arrow.（名詞／動詞／前置詞／冠詞／名詞：光陰矢のごとし）
②Time flies like an arrow.（名詞／名詞／動詞／冠詞／名詞：時蠅は矢をこのむ）
という2種類に解釈できるという話がある。
このような品詞タグ付けをモデル化してみよう。品詞として、N（名詞）、V（動詞）、DET（冠詞）、PREP（前置詞）の4種類を考える。
品詞から品詞への遷移確率と、品詞からの単語出力確率は、品詞付与コーパスがあれば最尤推定によって、次のように計算可能だ。
P(V|N) = C(N, V) / C(N) = 0.31
P(time|N) = C(time, N) / C(N) = 0.0037
C(N)、C(N, V)はそれぞれ品詞付与コーパス中の品詞Nの頻度、品詞bigram N, Vの頻度であり、C(time, N)はNとタグ付けされた単語timeの頻度である。このように考えると、入力文に対する品詞タグ付けの問題は、その文を出力する最も確率が高い品詞列（状態遷移）を求めることと同じである。つまり、上述の
Time flies like an arrow.
という文章は、確率の積が最大になるようなパスを選んでいくと、「光陰矢の如し」という意味に相当する品詞列が正しく求められる、ということになる。
このモデル化は下記のような式で表すことができる。
y = arg max P (y|x)
= arg max P (x | y)P(y) / P (x)
= arg max P (x | y)P(y)
= arg max Π P (xi | yi)P (yi | yi-1)
つまり、入力する単語列をx = x1 x2 x3....xn、品詞列をy = y1 y2 y3.....ynとして、xが与えられた条件で最も確率が高いyを求めるという意味である。
ここでは、①品詞列のマルコフ性の仮定（つまり、過去のデータに依存して品詞が決まってくる）と、②単語出力がその品詞だけに依存する（前後の品詞列からは独立している）という大胆な近似が行われている。
①P(y) = Π P (yi | yi-1)
②P(x|y) = Π P (xi | yi)
機械学習による系列ラベリング
上記、品詞タグ付けのような、データ系列に対してラベル付けを行う処理を、一般的に系列ラベリングといい、様々な機械学習の手法が提案されている。
どのような手がかりを利用するのか
HMMによる品詞タグ付けは注釈付与コーパス上の情報を活用するという意味では改良の余地がある。
例えば、HMMではxiの品詞yiを決定する上で関係するのはyi-1と単語としてのxiだけである。しかし、例えばxiが大文字ではじまるのかどうか、ing、ed、ly、ionなどの単語末尾が特徴的な文字列であるかどうか、また直前直後の単語が有効な手がかりになるかもしれない。
このような、様々な手がかりを素性として表現し、素性の束に対する分類器を、注釈付与コーパスを教師データとして機械学習によって学習することを考える。その手法としては、ナイーブベイズや、SVM（support vector machine）、対数線形モデル（log linear model）などがある。
これらの品詞タグ付けモデルは、一般にHMMによるモデルよりは性能が高く、特に未知語の品詞推定に強い。しかし、局所的な対応になるため、文全体の品詞列としては必ずしも妥当でない場合もある。
条件付き確率場（CRF）による品詞タグ付け
CRFは対数線形モデルの一種であり、様々な系列ラベリングに利用できるが、ここでは品詞タグ付けを具体例とする。CRFでは入力文（単語列）xが与えられたときに、それが品詞列yを持つ条件付き確率を次のように計算する。
P (y|x) = 1/Z exp Σ Σ (λj × fj (x, yi-1, yi, i))
ここで、Zは、Σ P (y|x) = 1、つまりすべての品詞列の確率の和を1にするための正規化項である。また、fj (x, yi-1, yi, i)は素性関数とよばれるもので、入力文xと品詞bigram yi-1, yiから素性を抽出する働きをするものであり、例えば次のような関数が考えられる。
fj (x, yi-1, yi, i) = 1 ：単語xiの末尾がlyで、yiが副詞
fj (x, yi-1, yi, i) = 0 ：それ以外
λjは各素性関数に対する重みで、注釈付与コーパスを用いて反復計算によって求めることができる（が、ここでは省略）。expに乗せて0以上の値にしてから全ての和で割ることで確率分布に変換していると理解すればよいだろう。
求める品詞列yは、この条件付き確率を最大にするものと考える。argmaxに関係ないZを除去し、expを外すことで最終的に以下のような計算を行うことになる。
y = arg max P (y|x)
= arg max 1/Z exp Σ Σ (λj × fj (x, yi-1, yi, i))
= arg max Σ Σ (λj × fj (x, yi-1, yi, i))
この中のΣ (λj × fj (x, yi-1, yi, i))は、yi-1、yiだけに依存しており、これをiについて、すなわち各語について足し合わせれば良いので、これまでと同様に効率的に最大値を与えるyを求めることができる。
このモデルが優れているといわれるのは、計算の効率化のために素数関数の引数を品詞bigram yi-1、yiに制限しつつ、P (y|x)という全体の最適化を行っている点にある。したがって、HMMでは同時確率P(y|x)を考えたが、CRFではxが与えられた時のyの条件付き確率を求める点で異なっている。
参考：自然言語処理（黒崎禎夫）
