CRF の前向き・後ろ向きアルゴリズム

今回は、CRF の前向き・後ろ向きアルゴリズムについて。

可変次数 CRF のアルゴリズムとの対比のために書いておく。


前向き・後ろ向きアルゴリズムは、1 次の CRF で使われる*1

高次に応用する方法も考えられないこともないが、計算量が次数に対して指数的に増加するため、あまり現実的ではない。


1 次の CRF で使う素性関数は、文脈に関する特徴と 長さ 1 または 2 のラベル列を組み合わせたもの。長さ 1 のものは状態素性、2 のものは遷移素性と呼ぶこともある。


例として前回と同じものを使う。

文は "time flies like" という三つの単語で、可能なラベルは N, V, A の 3 つ。

素性関数は、次の 5 つ。

  • 文脈にかかわらず、今の位置でラベルが "N" の時に 1 になるもの。重みは 2。
  • 文脈にかかわらず、今の位置でラベルが "V" の時に 1 になるもの。重みは 3。
  • 文脈にかかわらず、今の位置でラベルが "A" の時に 1 になるもの。重みは 5。
  • ある位置の単語が "es" で終わり、その前の位置のラベルが "N" で、今の位置のラベルも "V" である時に 1 になるもの。重みは 2。
  • ある位置の単語が "like" であり、その前の位置のラベルが "V" で、今の位置のラベルが "A" である時に 1 になるもの。重みは 3。

前向き・後ろ向きアルゴリズムについても、実際に流れを追いながら説明する。

まず、前向き・後ろ向きアルゴリズムでは、「ノード」と「エッジ」という概念を使う。

この例では、次のような図になる。

このそれぞれのエッジには、長さ 2 のラベル列を持つ素性関数の重みを掛け合わせたものを割り当てる。ないところでは、重みは 1 になる。

ここでの礼では、1 以外の重みになるのは 1 列目の N から 2 列目の V と、2 列目の V から 3 列目の A だけ。

そして、それぞれのノードには、長さ 1 のラベル列を持つ素性関数の重みを掛け合わせたものを割り当てる。

ここの例では、N はすべて 2、 V はすべて 3、A はすべて 5 になる。

ここで、前向きスコアは「先頭からそのノードまでのスコアの合計に、そのノードの重みを掛けたもの」とし、後ろ向きスコアは「最後尾からそのノードまでのスコアの合計」とする。

つまり、後ろ向きスコアにはそのノードの重みを掛けない。


まず、前向きスコアから計算する。

1 列目のそれぞれのノードでは、それぞれ 1 とする。

それにそれぞれのノードの重みを掛ける。すると、次のようになる。

これを1 列目の前向きスコアとする。


次は 2 列目。

N のノードには、1 列目の N, V, A のそれぞれから、エッジの重みを掛けたものが入る。

この場合、エッジの重みはすべて 1 なので、2+3+5=10 が 2 列目の N に入り、それが前向きスコアになる。

V のノードにも、1 列目の N, V, A のそれぞれから、エッジの重みを掛けたものが入る。

N-V のエッジの重みは 2 なので、2*2+3+5=12 が 2 列目の N に入る。

A のノードには、そのまま 2, 3, 5 が入る。

1 列目と同じく、それぞれのノードの重みを掛ける。

これが、2 列目の前向きスコアになる。


次は 3 列目。

N のノードに入るエッジは重みがすべて 1 なので、これらがそのまま入る。

V のノードも同じ。

A のノードだけ、V-A のエッジの重みが 3 なので、V の 36 が 3 倍になって入る。

最後に、それぞれのノードの重みを掛ける。

これが 3 列目の前向きスコア。

合計すると、全パターンの合計スコアである 1420 になる。


次は、後ろ向きスコア。

まず、最初はすべて 1。

3 列目はこれだけ。

ノードの重みを掛けないものを後ろ向きスコアとする(前向きスコアをノードの重みを掛けるものとしている都合上)。


次は 2 列目。

まず、3 列目の後ろ向きスコアにそれぞれのノードの重みを掛ける。

N のノードに入るエッジは重みがすべて 1 なので、スコアがそのまま入ってくる。

V のノードは、V-A のエッジの重みが 3 なので、A の 5 は 3 倍になる。

A のノードはそのまま。

これで 2 列目の後ろ向きスコアは終わり。


次は 1 列目。

まず、2 列目の後ろ向きスコアにノードの重みを掛ける。

N のノードは、N-V の重みが 2 なので、V のスコアだけ 2 倍になって入ってくる。

V のノードは、全部そのまま。

A のノードも同じ。

これで、前向き・後ろ向きのスコアがすべて揃った。

まず、ノードのスコアから。

それぞれの前向き・後ろ向きスコアをそのまま掛け合わせたものになる。

長さ 1 のラベル列を持つ素性関数のスコアは、次のようになる。

  • 文脈にかかわらず、今の位置でラベルが "N" の時に 1 になるもの: 380+200+212=792
  • 文脈にかかわらず、今の位置でラベルが "V" の時に 1 になるもの: 390+720+318=1428
  • 文脈にかかわらず、今の位置でラベルが "A" の時に 1 になるもの: 650+500+890=2040

次は、エッジのスコア。

エッジのスコアを求めるには、

  • 左ノードの前向きスコア
  • 右ノードの後ろ向きスコア
  • 右ノードの重み
  • エッジの重み

を掛け合わせる。

ここで、「右ノードの重み」を掛けるのは、ノードの後ろ向きスコアをそのノードの重みを掛けないものとしているから。

実際にはすべてのエッジについて計算する必要があるが、この例ではエッジにかかる素性関数は次の 2 つしかないので、それらについてだけ計算する。

  • ある位置の単語が "es" で終わり、その前の位置のラベルが "N" で、今の位置のラベルも "V" である時に 1 になるもの。重みは 2。
  • ある位置の単語が "like" であり、その前の位置のラベルが "V" で、今の位置のラベルが "A" である時に 1 になるもの。重みは 3。


それぞれ計算すると、

  • 1 列目の N から 2 列目の V のエッジのスコア: 1*20*2*6=240
  • 2 列目の V から 3 列目の A のエッジのスコア: 36*1*5*3=540

となる。

この計算方法でも、系列の長さが 2 倍になっても計算量は 2 倍になるだけなので、組み合わせ爆発を起こさないですむ。


このように、前向き・後ろ向きアルゴリズムは、比較的単純なアルゴリズムになっている。

しかし、この方法では高い次数の素性関数に対応できない。2 つ以上のラベルを持ったノードを考えればできないことはないが、計算量が次数に対して指数的に増えてしまう。

それに比べて、合計・差分アルゴリズムは(見た目は複雑だけど)素性関数があるところだけ計算すればいいし、高い次数の素性関数が少しあるという時には役に立つと思うのですが、どうでしょう。

*1:元は、隠れマルコフモデル(HMM)というもののために考案されたアルゴリズム