機械学習・自然言語処理の勉強メモ

学んだことのメモやまとめ

CRFについて

はじめに



CRFはConditional Random Fieldsの略。

識別モデル(xからyを直接推定するモデル)の一種。

HMMを識別モデル(最大エントロピーモデル)に適用したものと考えると分かりやすい。
それぞれは下記でまとめた。

参考文献はHMMの時と同じで

後、下記のSlideShareも参考とさせていただいた。

www.slideshare.net

導入



対数線形モデルの条件付き確率は、
\begin{eqnarray}
P(y|x)=\frac{1}{Z}\exp (w\cdot \phi(x,y))\cdots(1)
\end{eqnarray}
\begin{eqnarray}
(Z =\sum_{y}\exp (w \cdot \phi(x,y)))
\end{eqnarray}
と書けた。

また、HMMで導入した素性は、
\phi_{x,y}:観測素性(xにラベルyにがついている回数)
\phi_{y,y'}:遷移素性(y'の後にyが現れた回数)
であった。

CRFでは、素性関数を観測素性と遷移素性で表現する。

つまり、
\begin{eqnarray}w\cdot \phi(x,y)=\sum_{t}w\cdot \phi(x_t,y_t,y_{t-1})\end{eqnarray}
という仮定をおく。
(系列の素性は系列位置毎の素性の総和で表現できるとする)

すると(1)は、
\begin{eqnarray}
P(y|x)=\frac{1}{Z}\exp (\sum_{t}w\cdot \phi(x_t,y_t,y_{t-1}))\cdots(2) 
\end{eqnarray}
と書き換えられる。
対数を取った
\begin{eqnarray}
\log P(y|x)=\log \exp \sum_{t}w\cdot \phi(x_t,y_t,y_{t-1})- Z
\end{eqnarray}
\begin{eqnarray}
\hspace{2.05cm}=\sum_{t}w\cdot \phi(x_t,y_t,y_{t-1})- \log \sum_{y}\exp (\sum_{t}w \cdot \phi(x_t,y_t,y_{t-1}))
\end{eqnarray}
wを最尤法により求める。

パラメータ推定(学習)



CRFは識別モデルなので、対数線形モデルと同様の方法で学習可能。
最急勾配法なら
w^{new}=w^{old}+\epsilon  \nabla _wL(w^{old})
の更新式を収束するまで繰り返す。
注意すべき点は、
\begin{eqnarray}\nabla _wL(w)=\sum_{(x^{(i)},y^{(i)})}{(\phi (x^{(i)},y^{(i)})- \sum_{y}P(y|x^{(i)}) \cdot \phi(x^{(i)},y))}\end{eqnarray}
において、訓練データに含まれるx^{i}に対して、あらゆるラベルyについてのP(y|x^{i})を計算する必要がある。
識別問題とは異なり、系列ラベリングの場合は計算すべきyの数が非常に大きいので、高速に計算する工夫が必要となる。

まず、
\begin{eqnarray}\sum_{y}{P(y|x)\phi (x,y)}=\sum_{y}{P(y|x)\sum_{t}{\phi (x,y_t,y_{t-1})}}\end{eqnarray}
\begin{eqnarray}\hspace{3.4cm}=\sum_{t}{\sum_{y_t,y_{t-1}}{P(y_t,y_{t-1}|x)\phi (x,y_t,y_{t-1})}}\end{eqnarray}
のように変形する。
\begin{eqnarray}\sum_{y_t,y_{t-1}}{P(y_t,y_{t-1}|x)\phi (x,y_t,y_{t-1})}\end{eqnarray} であるが、これはラベルの遷移確率×素性関数の周辺化。
(位置t,t-1の取り得るラベルの組み合わせの総和)
例えば、t=0 の位置の場合、y_0は常にダミーラベルBなので、

  • B - NER
  • B - O

の各遷移確率×素性関数の総和となる。
t=1 の位置の場合は、

  • NER - NER
  • NER - O
  • O - NER
  • O - O

の各遷移確率×素性関数の総和となる。
また、系列全体のラベルの条件付き確率は、
\begin{eqnarray}P(y|x)=\prod_t \exp (w\cdot \phi (x,y_t,y_{t-1}))\end{eqnarray}
とおけるので、
(分類時の計算で用いる系列全体の素性ベクトルは、各位置での素性ベクトルの総和である)
\begin{eqnarray}P(y_t,y_{t-1}|x)=\frac{1}{Z}\sum_{y_0,...,y_{t-2}}\sum_{y_{t+1},...,y_{T+1}}\prod_{t'} \exp (w\cdot \phi (x,y_{t'},y_{t'-1}))\end{eqnarray}
\begin{eqnarray}\hspace{2.5cm}=\frac{\exp (w\cdot \phi (x,y_{t},y_{t-1}))}{Z}\sum_{y_0,...,y_{t-2}}\sum_{y_{t+1},...,y_{T+1}}\prod_{t'\neq t} \exp (w\cdot \phi (x,y_{t'},y_{t'-1}))\end{eqnarray}
t-1t より後で式を分けると、
\begin{eqnarray}\sum_{y_0,...,y_{t-2}}\sum_{y_{t+1},...,y_{T+1}}\prod_{t'\neq t} \exp (w\cdot \phi (x,y_{t'},y_{t'-1}))\end{eqnarray}
\begin{eqnarray}=(\sum_{y_0,...,y_{t-2}}\prod_{t'= 1}^{t-1} \exp (w\cdot \phi (x,y_{t'},y_{t'-1})))(\sum_{y_{t+1},...,y_{T+1}}\prod_{t'=t+1}^{T+1} \exp (w\cdot \phi (x,y_{t'},y_{t'-1})))\end{eqnarray}
と表せる。
\begin{eqnarray}\alpha (y_t,t)=\sum_{y_0,...,y_{t-1}}\prod_{t'= 1}^{t} \exp (w\cdot \phi (x,y_{t'},y_{t'-1}))\end{eqnarray}
\begin{eqnarray}\beta (y_t,t)=\sum_{y_{t+1},...,y_{T+1}}\prod_{t'=t+1}^{T+1} \exp (w\cdot \phi (x,y_{t'},y_{t'-1}))\end{eqnarray}
とおくと、
\begin{eqnarray}P(y_t,y_{t-1}|x)=\frac{1}{Z}\exp (w\cdot \phi (x,y_{t},y_{t-1}))\alpha (y_{t-1},t-1)\beta (y_t,t)\end{eqnarray}
と表せる。
\begin{eqnarray}\alpha (y_t,t)=\sum_{y_{t-1}}{\exp (w\cdot \phi (x,y_{t},y_{t-1}))}\sum_{y_0,...,y_{t-2}}\prod_{t'= 1}^{t-1} \exp (w\cdot \phi (x,y_{t'},y_{t'-1}))\end{eqnarray}
\begin{eqnarray}\hspace{1.5cm}=\sum_{y_{t-1}}{\exp (w\cdot \phi (x,y_{t},y_{t-1}))}\alpha (y_{t-1},t-1)\end{eqnarray}
\alpha(y_0,0)=1, \beta(y_{T+1},t-1)=1
の関係式より、動的計画法により高速計算が可能となる。

実際の例文と遷移図で確認してみる。
例文

Mark visited Mars

HMMと同様のラベリング(NかO)を考える。
前向きアルゴリズム
1)Mark=N
\begin{eqnarray}\alpha(N,1)=\sum_{y_0}\exp (w\cdot \phi(x,N,y_0))\alpha(y_0,0)\end{eqnarray}
\begin{eqnarray}\hspace{1.6cm}=\exp (w\cdot \phi(x,N,B))\end{eqnarray}
f:id:kento1109:20171218111557p:plain:w200
2)visited=O
\begin{eqnarray}\alpha(O,2)=\sum_{y_1}\exp (w\cdot \phi(x,O,y_1))\alpha(y_1,1)\end{eqnarray}
\begin{eqnarray}\hspace{1.6cm}=\exp (w\cdot \phi(x,O,N))\alpha(N,1)+\exp (w\cdot \phi(x,O,O))\alpha(O,1)\end{eqnarray}
\alpha(N,1),\alpha(O,1)t-1時点の計算結果を利用

f:id:kento1109:20171218113719p:plain:w350
3)Mars=NER
\begin{eqnarray}\alpha(N,3)=\sum_{y_2}\exp (w\cdot \phi(x,N,y_2))\alpha(y_2,2)\end{eqnarray}
\begin{eqnarray}\hspace{1.6cm}=\exp (w\cdot \phi(x,N,N))\alpha(N,2)+\exp (w\cdot \phi(x,N,O))\alpha(O,2)\end{eqnarray}
\alpha(N,2),\alpha(O,2)t-2時点の計算結果を利用

f:id:kento1109:20171218113415p:plain:w500

後ろ向きアルゴリズム
計算方法は前向きアルゴリズムと同様
1)Mars=NER
\begin{eqnarray}\beta(N,3)=\sum_{y_4}\exp (w\cdot \phi(x,y_4,N))\beta(y_4,4)\end{eqnarray}
\begin{eqnarray}\hspace{1.6cm}=\exp (w\cdot \phi(x,E,N))\end{eqnarray}

f:id:kento1109:20171218112152p:plain:w200

以降、前向きアルゴリズムと同じ計算を行う。

前向き・後ろ向きアルゴリズムを用いると、
t=3 時点の P(y_t,y_{t-1}|x) つまり、 P(N,O|x) は、
\begin{eqnarray}P(y_t,y_{t-1}|x)=\frac{1}{Z}\exp (w\cdot \phi (x,y_{t},y_{t-1}))\alpha (y_{t-1},t-1)\beta (y_t,t)\end{eqnarray}
\begin{eqnarray}P(N,O|x)=\frac{1}{Z}\exp (w\cdot \phi (x,N,O))\alpha (O,2)\beta (N,3)\end{eqnarray}
\begin{eqnarray}\hspace{2.1cm}=\frac{1}{Z}\exp (w\cdot \phi (x,N,O))(\sum_{y_1}\exp (w\cdot \phi(x,O,y_1))\alpha(y_1,1))(\sum_{y_4}\exp (w\cdot \phi(x,y_4,N))\beta(y_4,4))\end{eqnarray}
\begin{eqnarray}\hspace{2.1cm}=\frac{1}{Z}\exp (w\cdot \phi (x,N,O))(\exp (w\cdot \phi(x,O,N))\alpha(N,1)+\exp (w\cdot \phi(x,O,O))\alpha(O,1))(\exp (w\cdot \phi(x,E,N)))\end{eqnarray}
\begin{eqnarray}\hspace{2.1cm}=\frac{1}{Z}\exp (w\cdot \phi (x,N,O))(\exp (w\cdot \phi(x,O,N))(\exp (w\cdot \phi(x,N,B)))+\exp (w\cdot \phi(x,O,O))\alpha(O,1))(\exp (w\cdot \phi(x,E,N)))\end{eqnarray}
のように前の情報を利用して高速計算できる。

f:id:kento1109:20171218115407p:plain

また、 Z については、
Z=\sum_{y_T}\alpha(y_T,T)
であることを利用して計算可能である。
\psi_t(y_t,y_{t-1})=\exp(w\cdot \phi(x,y_t, y_{t-1})とおくと、
\hspace{2.25cm} =\psi_4(E,N)\alpha(N,3)+\psi_4(E,O)\alpha(O,3)
\hspace{2.25cm}=\psi_4(E,N)\left\{\psi_3(N,N)\alpha(N,2)+\psi_3(N,O)\alpha(O,2)\right\} +\psi_4(E,O)\left\{\psi_3(O,N)\alpha(N,2)+\psi_3(O,O)\alpha(O,2)\right\}
\hspace{2.25cm}=\psi_4(E,N)\left\{\psi_3(N,N)\left[\psi_2(N,N)\alpha(N,1)+\psi_2(N,O)\alpha(O,1)\right]  +\psi_3(N,O)\left[\psi_2(O,N)\alpha(N,1)+\psi_2(O,O)\alpha(O,1)\right]\right\} +\\ \hspace{2.25cm} \psi_4(E,O)\left\{\psi_3(O,N)\left[(\psi_2(N,N)\alpha(N,1)+(\psi_2(N,O)\alpha(O,1)\right]+\psi_3(O,O)\left[(\psi_2(O,N)\alpha(N,1)+(\psi_2(O,O)\alpha(O,1)\right]\right\}
\hspace{2.25cm}=\psi_4(E,N)\left\{\psi_3(N,N)\left[\psi_2(N,N)\psi_1(N,B)+\psi_2(N,O)\psi_1(O,B) \right]  +\\ \hspace{4.25cm} \psi_3(N,O)\left[\psi_2(O,N)\psi_1(N,B)+\psi_2(O,O)\psi_1(O,B)\right]\right\} +\\ \hspace{2.25cm} \psi_4(E,O)\left\{\psi_3(O,N)\left[\psi_2(N,N)\psi_1(N,B)+\psi_2(N,O)\psi_1(O,B)\right]+\\ \hspace{4.25cm} \psi_3(O,O)\left[\psi_2(O,N)\psi_1(N,B)+\psi_2(O,O)\psi_1(O,B)\right]\right\}
分かりにくいので、式変形すると、
Z=\psi_1(N,B)\psi_2(N,N)\psi_3(N,N)\psi_4(E,N)+
\hspace{0.9cm}\psi_1(N,B)\psi_2(N,N)\psi_3(O,N)\psi_4(E,O)+
\hspace{0.9cm}\psi_1(N,B)\psi_2(O,N)\psi_3(O,O)\psi_4(E,O)+
\hspace{0.9cm}\psi_1(N,B)\psi_2(O,N)\psi_3(N,O)\psi_4(E,N)+
\hspace{0.9cm}\psi_1(O,B)\psi_2(N,O)\psi_3(N,N)\psi_4(E,N)+
\hspace{0.9cm}\psi_1(O,B)\psi_2(N,O)\psi_3(O,N)\psi_4(E,O)+
\hspace{0.9cm}\psi_1(O,B)\psi_2(O,O)\psi_3(O,O)\psi_4(E,O)+
\hspace{0.9cm}\psi_1(O,B)\psi_2(O,O)\psi_3(N,O)\psi_4(E,N)

となることが分かる。
これは、全ての経路(8通り)のスコアの総和に相当することが分かる。

スコアを求める



損失関数
\begin{eqnarray}
\sum_{t}w\cdot \phi(x_t,y_t,y_{t-1})- \log \sum_{y}\exp (\sum_{t}w \cdot \phi(x_t,y_t,y_{t-1}))
\end{eqnarray}
を解いてスコアを求めてみる。
下記の訓練データで考える。

Mark visited Mars
N O N

尚、 w は下記のように与えられるものとする。

  • 出力素性
N O
Mark w_0 w_1
visited w_2 w_3
Mars w_4 w_5

(重み)

w_0 w_1 w_2 w_3 w_4 w_5
3.2 0.4 0.6 2.1 1.1 2.5
  • 遷移素性
N O <BOS> <EOS>
N w_6 w_7 w_8 w_9
O w_{10} w_{11} w_{12} w_{13}
<BOS> w_{14} w_{15} w_{16} w_{17}
<EOS> w_{18} w_{19} w_{20} w_{21}

(重み)

w_6 w_7 w_8 w_9 w_{10} w_{11} w_{12} w_{13} w_{14} w_{15} w_{16} w_{17} w_{18} w_{19} w_{20} w_{21}
0.8 1.4 0.0 1.8 0.6 1.1 0.0 1.2 1.1 0.5 0.0 0.0 0.0 0.0 0.0 0.0

\sum_{t}w\cdot \phi(x_t,y_t,y_{t-1})=
w_0+w_3+w_4+w_{14}+w_{7}+w_{10}+w_{13}\\
\hspace{3.9cm}=3.2+2.1+1.1+1.1+1.4+0.6+1.2\\\hspace{3.9cm}=10.7

全経路のパスは下記の組み合わせなので、

Mark visited Mars
N N N
N N O
N O O
N O N
N N N
N N O
N O O
N O N


\log \sum_{y}\exp (\sum_{t}w \cdot \phi(x_t,y_t,y_{t-1}))=
\{\hspace{0.1cm}\exp(w_0+w_2+w_4+w_{14}+w_{6}+w_{6}+w_{9})+\\
\hspace{7.12cm}\exp(w_0+w_2+w_5+w_{14}+w_{6}+w_{7}+w_{13})+\\\hspace{7.12cm}\exp(w_0+w_3+w_5+w_{14}+w_{7}+w_{11}+w_{13})+\\\hspace{7.12cm}\exp(w_0+w_3+w_4+w_{14}+w_{7}+w_{10}+w_{9})+\\\hspace{7.12cm}\exp(w_1+w_2+w_4+w_{15}+w_{10}+w_{6}+w_{9})+\\\hspace{7.12cm}\exp(w_1+w_2+w_5+w_{15}+w_{10}+w_{7}+w_{13})+\\\hspace{7.12cm}\exp(w_1+w_3+w_5+w_{15}+w_{11}+w_{11}+w_{13})+\\\hspace{7.12cm}\exp(w_1+w_3+w_4+w_{15}+w_{11}+w_{10}+w_{9})
\hspace{0.1cm}\}\\
\hspace{6.3cm}=\{\hspace{0.1cm}\exp(3.2+0.6+1.1+1.1+0.8+0.8+1.8)+
\\\hspace{7.12cm}\exp (3.2+0.6+2.5+1.1+0.8+1.4+1.2)+\\\hspace{7.12cm}\exp(3.2+2.1+2.5+1.1+1.4+1.1+1.2)+\\\hspace{7.12cm}\exp(3.2+2.1+1.1+1.1+1.4+0.6+1.8)+\\\hspace{7.12cm}\exp(0.4+0.6+1.1+0.5+0.6+0.8+1.8)+
\\\hspace{7.12cm}\exp (0.4+0.6+2.5+0.5+0.6+1.4+1.2)+\\\hspace{7.12cm}\exp(0.4+2.1+2.5+0.5+1.1+1.1+1.2)+\\\hspace{7.12cm}\exp(0.4+2.1+1.1+0.5+1.1+0.6+1.8)\hspace{0.1cm}\}\\
\hspace{6.3cm}=13.015

\sum_{t}w\cdot \phi(x_t,y_t,y_{t-1})- \log \sum_{y}\exp (\sum_{t}w \cdot \phi(x_t,y_t,y_{t-1}))=-2.315

素性関数について



素性関数とは、引数がその素性関数の条件を満たす場合に 1、そうでない場合に 0 を返す関数。
\phi(x,y) =\begin{cases}1 & x = \hat x \hspace{3pt}and \hspace{3pt} y = \hat y \\0 & otherwise\end{cases}
CRFでは素性関数は、

  • unigram feature:現在の単語にのみ依存する素性
  • bigram feature:現在と 1 つ前の単語に依存する素性

に大別される。
クックパッドさんのブログより引用)

unigram feature

例文で考える。

Mark visited Mars

の単語情報からunigram featureの素性関数を作ると(ラベルはNかOのみ)、

  • \phi_0(Mark, N)
  • \phi_1(Mark, O)
  • \phi_2(visited, N)
  • \phi_3(visited, O)
  • \phi_4(Mars, N)
  • \phi_5(Mars, O)

が作られる。

次に、例文に下記のように品詞が付与されていたとする。

Mark visited Mars
Noun Verb Noun

固有表現抽出では、品詞も重要な情報となるため、この情報も素性として含めたい。
品詞情報も加えると、素性候補は下記のようになる。

  • \phi_0(Mark, N)
  • \phi_1(Mark, O)
  • \phi_2(visited, N)
  • \phi_3(visited, O)
  • \phi_4(Mars, N)
  • \phi_5(Mars, O)
  • \phi_6(Noun, N)
  • \phi_7(Noun, O)
  • \phi_8(Verb, N)
  • \phi_9(Verb, O)

先頭文字が大文字かどうかも素性に含めたい場合、下記の素性関数を加える。

  • \phi_{10}(Caps, N)
  • \phi_{11}(Caps, O)

unigram featureは好きなだけ拡張できるので、有効と思われる素性を自由に作ることが出来る。

bigram feature

これはHMMの遷移素性と同じ。
ラベルがNかOの場合の素性関数は、

  • \phi_{12}(N, B)
  • \phi_{13}(O, B)
  • \phi_{14}(N, N)
  • \phi_{15}(O, N)
  • \phi_{17}(N, O)
  • \phi_{18}(O, O)
  • \phi_{19}(E, N)
  • \phi_{20}(E, O)

となる。
※入力系列には依存しない。

重みベクトルの要素数は素性関数の数になるので、21となる。

最後に素性ベクトルの例を確認する。
1)Mark=Nのパスでの素性ベクトルは、

\phi_{0} \phi_{1} \phi_{2} \phi_{3} \phi_{4} \phi_{5} \phi_{6} \phi_{7} \phi_{8} \phi_{9} \phi_{10} \phi_{11} \phi_{12} \phi_{13} \phi_{14} \phi_{15} \phi_{16} \phi_{17} \phi_{18} \phi_{19} \phi_{20}
1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0

2)Mark=Oのパスでの素性ベクトルは、

\phi_{0} \phi_{1} \phi_{2} \phi_{3} \phi_{4} \phi_{5} \phi_{6} \phi_{7} \phi_{8} \phi_{9} \phi_{10} \phi_{11} \phi_{12} \phi_{13} \phi_{14} \phi_{15} \phi_{16} \phi_{17} \phi_{18} \phi_{19} \phi_{20}
0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0

となる。