CRF について（可変次数 CRF への前振り）

アルゴリズム

最大エントロピーモデルの続き。

今回は、CRF（Conditional Random Fields, 条件付き確率場とも） 一般*1について。

前向き・後ろ向きアルゴリズムについては書かない。

また、一般に関連が深いとされる MEMM というものについても、ここでは触れない。


CRF とはどういうものか。

一言でいうと、最大エントロピーモデルの考え方を系列ラベリングに応用したもの。


ここで、系列ラベリングというタスクについて簡単に説明しておく。

たとえば、品詞タグ付けのようなものがある。

英語のように単語が分かれている言語で、それぞれの単語に対して「名詞」「動詞」などの品詞タグをつけるというタスク。

古典的な "time flies like an arrow"*2 を例にとる。

これには複数の解釈があり、その中には

  • 時は矢のように過ぎ去る（光陰矢のごとし）
  • 時バエは矢を好む

のようなものがある*3。

それぞれの解釈において、品詞は

  • time(N) flies(V) like(P) an(A) arrow(N)
  • time(N) flies(N) like(V) an(A) arrow(N)

のようになる（N=名詞、V=動詞、P=前置詞、A=冠詞とおいている*4）。

どちらも可能な解釈ではあるが、自然な解釈は一番目のものなので、そちらのラベルをつけることが目的になる。


系列ラベリングが普通の分類タスクと違うのは、ある位置のラベルが何になるかの確率が、前後のラベルが何であるかと関係があるという点。

名詞の後は動詞が来やすい、など。

ところで、「前後」といっても、ある位置のラベルと後ろのラベルとの関係（「後ろのラベルが名詞である場合、ラベルは動詞になりやすい」など）は、後ろのラベルについて考えて、前のラベルとの関係に書き換えられる（「前のラベルが動詞である場合、ラベルは名詞になりやすい」など）。どちらの形でも、その形でパラメータを適切に学習すると、同じように判別ができる。

このラベル同士の関係というのは、隣接した二つのラベル同士とは限らず、三つやそれ以上の関係（「名詞-動詞-名詞という並びは起こりやすい」など）も考えられる。また、間をスキップしたもの（「名詞-○-名詞」という並びは起こりやすい）などもありうる。

これらはすべて、CRF のモデルとしては問題がないが、計算の都合上、考える依存関係はある程度限定することになる。前向き・後ろ向きアルゴリズムでは二つのラベル間の関係だけを考え、可変次数 CRF では長さを限定せずに連続したラベルの関係を考える。

CRF は一般の最大エントロピーモデルと同じく識別モデルなので、単語列が与えられた時のラベル列の確率をモデル化する。

つまり、単語列を x, ラベル列を y とすると、次のものを考えることになる。


上の例で言うと、P(N-V-P-A-N | "time flies like an arrow") や、P(N-N-V-A-N | "time flies like an arrow") ということになる。


CRF でも、最大エントロピーモデルと同じく素性関数を考える。

最大エントロピーモデルは、

  • 素性関数は、文脈に関する特徴とクラスを組み合わせたもの。
  • あるデータがあるクラスになる確率は、その場合に 1 になる素性関数の重みを掛け合わせたものに比例する。これをスコアとする*5。
  • あるデータがあるクラスになる確率は、その場合のスコアを、そのデータとすべてのクラスを組み合わせた各事象に対するスコアを合計したもので割ったものとする。

という設定だった。

それに対して CRF は、

  • 素性関数は、文脈に関する特徴と一つ以上のラベルを組み合わせたもの。
  • あるデータがあるラベル列を持つ確率は、その場合にそれぞれの位置で 1 になる素性関数の重みを掛け合わせたものに比例する。
  • あるデータがあるラベル列を持つ確率は、その場合のスコアを、そのデータとすべての可能なラベル列を組み合わせた各事象に対するスコアを合計したもので割ったものとする。

という設定。


つまり、CRF の素性関数には、文脈の他に

  • 位置
  • 一つ以上のラベル

が関わることになる。

そのため、素性関数の形は次のようになる。


これによって、

  • ある位置の単語が e で終わり、かつその位置のラベルが N である時に限り 1 になる
  • 前のラベルが V で、今の位置のラベルが N である時に限り 1 になる

といった素性関数が記述できる。

前者は、文脈に関する条件とラベル一つを組み合わせたもので、後者は文脈に関する条件なしで、ラベル 2 つだけに関する条件を設定したもの。

素性関数 fi には、それに対応する重み Wi があるというのは、最大エントロピーモデルの場合と同じ。


CRF では、あるラベル列の確率は、各位置で 1 になる素性関数の対応する重みを掛け合わせたものに比例するとする。これをスコアとする。


一般的に、あるラベル列に対するスコアは、次のように表せる。


これは、二値変数 aiが 1 になるところだけについて、それに対応する値 bi を掛け合わせたい時に、と表すという、例のパターン。

これが求められたら、すべての可能なラベル列に対するスコアを合計したもので割って正規化すると、今のパラメータによるそのラベル列の確率が求められる。

一般的には、上の式の対数をとったものを使う。

まず、重みの対数をとって wi = log Wi とおくと、次のように書き換えられる。

すべての可能なラベル列に対するスコアの合計は、次のように表せる。

あるラベル列に対する正規化したスコアは次のようになる。

ある単語列に対して、すべての可能なラベル列にわたって各素性関数の値を合計すると、素性関数の期待値が求められる。

また、現在のパラメータによる訓練データに対する各素性関数の期待値が求められると、それと実際の各素性関数の合計値との差分をとることで、最大エントロピーモデルの場合と同じく、訓練データの尤度をより大きくするようなパラメータに更新することができる。

最初に各素性関数に対する重みの対数（wi）を適当に設定して、この手順を繰り返してパラメータを更新していくことで、訓練データの尤度を最大化するようなものに限りなく近づけることができる。この場合も、尤度（実際に使うのは対数尤度）の変化が小さくなったところで更新を打ち切ればよい。


ここまでの説明はちょっと抽象的なので、実際の例で見てみる。

可能なラベルが N, V, A の 3 つで、"time/N flies/V like/A" という訓練データがある場合を考える。

素性関数は、次の 5 つだけだとする*6。

  • f1: 文脈にかかわらず、今の位置でラベルが "N" の時に 1 になる。
  • f2: 文脈にかかわらず、今の位置でラベルが "V" の時に 1 になる。
  • f3: 文脈にかかわらず、今の位置でラベルが "A" の時に 1 になる。
  • f4: 今の位置の単語が "es" で終わり、前の位置のラベルが "N" で、今の位置のラベルが "V" である時に 1 になる。
  • f5: 今の位置の単語が "like" であり、前の位置のラベルが "V" で、今の位置のラベルが "A" である時に 1 になる。

こうすると、それぞれの位置で 1 となる素性関数は次のようになる。

  • 位置 1: f1
  • 位置 2: f2, f4
  • 位置 3: f3, f5

つまり、訓練データの中での合計値はすべて 1 ということになる。

これは、後で期待値との差分をとるために使う。


ここで、素性関数の期待値を求める。

まず、3 単語に対する可能なラベル列は次の 27 通り。

N-N-N
N-N-V
N-N-A
N-V-N
N-V-V
N-V-A
N-A-N
N-A-V
N-A-A
V-N-N
V-N-V
V-N-A
V-V-N
V-V-V
V-V-A
V-A-N
V-A-V
V-A-A
A-N-N
A-N-V
A-N-A
A-V-N
A-V-V
A-V-A
A-A-N
A-A-V
A-A-A

これらそれぞれについてスコアを計算する。

スコアを計算するには、それぞれの位置で 1 になる素性関数を列挙し、それらの重みを掛け合わせる。


例として、"time flies like" に対する N-V-V というラベル列のスコアを考える。

この場合、位置 1 では

  • f1: 文脈にかかわらず、今の位置でラベルが "N" の時に 1 になる。

が 1 になる。

位置 2 では、

  • f2: 文脈にかかわらず、今の位置でラベルが "V" の時に 1 になる。
  • f4: 今の位置の単語が "es" で終わり、前の位置のラベルが "N" で、今の位置のラベルが "V" である時に 1 になる。

の 2 つが 1 になる。

位置 3 では、

  • f2: 文脈にかかわらず、今の位置でラベルが "V" の時に 1 になる。

が 1 になる。

この場合のスコアを、次の式に当てはめる。

1 になる素性関数の重みを掛け合わせたものなので、 W1*W2*W4*W2 となる。

ここで、f1..f5 に対応する重み W1..W5 が次のようになっているとする。

W1=2
W2=3
W3=5
W4=2
W5=3

すると、スコアは W1*W2*W4*W2=2*3*2*3=36 となる。

この重みの設定を使って、同じようにそれぞれのラベル列に対応するスコアを計算すると、次のようになる。

N-N-N:  8
N-N-V: 12
N-N-A: 20
N-V-N: 24
N-V-V: 36
N-V-A:180
N-A-N: 20
N-A-V: 30
N-A-A: 50
V-N-N: 12
V-N-V: 18
V-N-A: 30
V-V-N: 18
V-V-V: 27
V-V-A:135
V-A-N: 30
V-A-V: 45
V-A-A: 75
A-N-N: 20
A-N-V: 30
A-N-A: 50
A-V-N: 30
A-V-V: 45
A-V-A:225
A-A-N: 50
A-A-V: 75
A-A-A:125
合計:1420

スコアをすべての可能なラベル列のスコアの合計で割ると、ラベル列に対する確率が求められる。

たとえば N-N-N であれば 8/1420 ということになる。


これを使って、それぞれの素性関数の期待値を求める。

たとえば、N-N-N というラベル列の確率は 8/1420 で、またそのラベル列では「文脈にかかわらず、今の位置でラベルが "N" の時に 1 になる」という素性関数が位置 1、位置 2、位置 3 の 3 つで 1 になるため、その期待値は 8/1420 * 3 = 24/1420 となる。

ここで、1420 で割る（合計スコアで割って正規化する）のは後回しにしてもよい。

その場合、ある素性関数に関して、それぞれのラベル列のスコアとそのラベル列で 1 になる回数を掛けたものを先に合計する。

それを正規化すると、その素性関数の期待値になる。


この考え方で、まずそれぞれの素性関数の合計スコアを求める。

すると、次のようになる。

  • 文脈にかかわらず、今の位置でラベルが "N" の時に 1 になるもの: 792
  • 文脈にかかわらず、今の位置でラベルが "V" の時に 1 になるもの: 1428
  • 文脈にかかわらず、今の位置でラベルが "A" の時に 1 になるもの: 2040
  • ある位置の単語が "es" で終わり、その前の位置のラベルが "N" で、今の位置のラベルが "V" である時に 1 になるもの: 240
  • ある位置の単語が "like" であり、その前の位置のラベルが "V" で、今の位置のラベルが "A" である時に 1 になるもの: 540

そして、全ラベル列の合計スコアである 1420 で割ると、各素性関数の期待値が求められる。

E[f1] = 792/1420
E[f2] = 1428/1420
E[f3] = 2040/1420
E[f4] = 240/1420
E[f5] = 540/1420

訓練データ中での合計値はそれぞれ 1 なので、それから今のパラメータによる期待値を引いた差分を求めると、次のようになる。

(1 - 792/1420, 1 - 1428/1420, 1 - 2040/1420, 1 - 240/1420, 1 - 540/1420)

これを使って、パラメータを最適解により近いものに更新することができる。


ここまででわかるように、CRF というのは最大エントロピーモデルのやり方をそのまま系列に当てはめたもので、最大エントロピーモデルですべての可能なクラスにわたって計算するものを、CRF ではすべての可能なラベル列にわたって行うというのが違うところ。

すべての可能なラベル列というのは、ラベル列の長さに対して指数的に増える。ラベル数が 4 個でも、長さが 20 だとパターンが 1 兆通りにもなってしまう。

もし計算機の速さが無限であれば、ここでやったようにすべての系列のスコアを計算して、それぞれの期待値を求め、それによって素性関数の期待値を求めてパラメータを更新する、という手順でパラメータを求めることができる。

しかし、計算機の速度は有限であるため、一般的には計算に工夫をする必要がある。


普通の CRF（1 次 CRF）で使われる前向き・後ろ向きアルゴリズムでは、素性関数のタイプを以下のようなものに絞ることで、動的計画法による効率的な計算を実現している。

  • ある位置での文脈に関する特徴と、その位置のラベルとを組み合わせたもの
  • 前の位置のラベルと、今の位置のラベルを組み合わせたもの

これらはそれぞれ状態素性・遷移素性と呼ばれることもある。

ぼくが提案する合計・差分アルゴリズムは可変次数 CRF のための計算方法で、素性関数は以下のようなものとする。

  • ある位置での文脈に関する特徴と、その位置までの 1 つ以上のラベル列を組み合わせたもの

この形で、文脈に関する特徴に条件をつけない（文脈によらず 1 となる）ようにすると状態素性を表すことができ、またラベル列の長さを 1 とすると遷移素性を表すことができるので、この形は前向き・後ろ向きアルゴリズムを使う場合の形の上位互換になっている。


次の記事では、合計・差分アルゴリズムについて書く。

前向き・後ろ向きアルゴリズムに関しては、その次に。

どちらも CRF のスコア計算のためのもので、足し算・掛け算と引き算（これは合計・差分アルゴリズムだけ）以外は出てこない。

*1:といっても Linear-Chain CRFs に限る。

*2:すべて小文字とする。句読点は省略。

*3:他にもある

*4:A は普通形容詞だと思うけれど、まあ便宜的に。

*5:「スコア」という用語は正式なものではないが、計算をする時にはこのような概念が必要になる

*6:普通は素性関数をもっと密に設定する。