CRFについて
はじめに
CRFはConditional Random Fieldsの略。
識別モデル(からを直接推定するモデル)の一種。
HMMを識別モデル(最大エントロピーモデル)に適用したものと考えると分かりやすい。
それぞれは下記でまとめた。
参考文献はHMMの時と同じで
後、下記のSlideShareも参考とさせていただいた。
導入
対数線形モデルの条件付き確率は、
と書けた。
また、HMMで導入した素性は、
:観測素性(にラベルにがついている回数)
:遷移素性(の後にが現れた回数)
であった。
CRFでは、素性関数を観測素性と遷移素性で表現する。
つまり、
という仮定をおく。
(系列の素性は系列位置毎の素性の総和で表現できるとする)
すると(1)は、
と書き換えられる。
対数を取った
のを最尤法により求める。
パラメータ推定(学習)
CRFは識別モデルなので、対数線形モデルと同様の方法で学習可能。
最急勾配法なら
の更新式を収束するまで繰り返す。
注意すべき点は、
において、訓練データに含まれるに対して、あらゆるラベルについてのを計算する必要がある。
識別問題とは異なり、系列ラベリングの場合は計算すべきの数が非常に大きいので、高速に計算する工夫が必要となる。
まず、
のように変形する。
であるが、これはラベルの遷移確率×素性関数の周辺化。
(位置の取り得るラベルの組み合わせの総和)
例えば、 の位置の場合、は常にダミーラベルBなので、
- B - NER
- B - O
の各遷移確率×素性関数の総和となる。
の位置の場合は、
- NER - NER
- NER - O
- O - NER
- O - O
の各遷移確率×素性関数の総和となる。
また、系列全体のラベルの条件付き確率は、
とおけるので、
(分類時の計算で用いる系列全体の素性ベクトルは、各位置での素性ベクトルの総和である)
と より後で式を分けると、
と表せる。
とおくと、
と表せる。
※
の関係式より、動的計画法により高速計算が可能となる。
実際の例文と遷移図で確認してみる。
例文
Mark visited Mars
HMMと同様のラベリング(NかO)を考える。
①前向きアルゴリズム
1)Mark=N
2)visited=O
※は時点の計算結果を利用
3)Mars=NER
※は時点の計算結果を利用
②後ろ向きアルゴリズム
計算方法は前向きアルゴリズムと同様
1)Mars=NER
以降、前向きアルゴリズムと同じ計算を行う。
前向き・後ろ向きアルゴリズムを用いると、
時点の つまり、 は、
のように前の情報を利用して高速計算できる。
また、 については、
であることを利用して計算可能である。
とおくと、
分かりにくいので、式変形すると、
となることが分かる。
これは、全ての経路(8通り)のスコアの総和に相当することが分かる。
スコアを求める
損失関数
を解いてスコアを求めてみる。
下記の訓練データで考える。
Mark | visited | Mars |
N | O | N |
尚、 は下記のように与えられるものとする。
- 出力素性
N | O | |
Mark | ||
visited | ||
Mars |
(重み)
3.2 | 0.4 | 0.6 | 2.1 | 1.1 | 2.5 |
- 遷移素性
N | O | <BOS> | <EOS> | |
N | ||||
O | ||||
<BOS> | ||||
<EOS> |
(重み)
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 |
全経路のパスは下記の組み合わせなので、
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 |
素性関数について
素性関数とは、引数がその素性関数の条件を満たす場合に 1、そうでない場合に 0 を返す関数。
CRFでは素性関数は、
- unigram feature:現在の単語にのみ依存する素性
- bigram feature:現在と 1 つ前の単語に依存する素性
に大別される。
(クックパッドさんのブログより引用)
unigram feature
例文で考える。
Mark visited Mars
の単語情報からunigram featureの素性関数を作ると(ラベルはNかOのみ)、
が作られる。
次に、例文に下記のように品詞が付与されていたとする。
Mark | visited | Mars |
Noun | Verb | Noun |
固有表現抽出では、品詞も重要な情報となるため、この情報も素性として含めたい。
品詞情報も加えると、素性候補は下記のようになる。
先頭文字が大文字かどうかも素性に含めたい場合、下記の素性関数を加える。
unigram featureは好きなだけ拡張できるので、有効と思われる素性を自由に作ることが出来る。
bigram feature
これはHMMの遷移素性と同じ。
ラベルがNかOの場合の素性関数は、
となる。
※入力系列には依存しない。
重みベクトルの要素数は素性関数の数になるので、21となる。
最後に素性ベクトルの例を確認する。
1)Mark=Nのパスでの素性ベクトルは、
1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2)Mark=Oのパスでの素性ベクトルは、
0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
となる。