統計数理（2016）
第 64 巻 第 2 号 179–200
c 2016 統計数理研究所


特集「統計的言語研究の現在」［原著論文］

条件付き確率場の理論と実践
岡崎 直観†（受付 2016 年 6 月 17 日；改訂 8 月 25 日；採択 9 月 14 日）

要旨

自然言語処理のタスクの多くは，入力から出力のラベルを予測する問題として定式化できる．
言語は構造を持つと考えられるので，入力や出力に単語列や木などの構造を持たせることで，さらに多くのタスクが予測問題として定式化できる．本稿では，系列ラベリング問題，すなわち入力と出力が系列データの場合の条件付き確率場を解説する．条件付き確率場は，多クラスロ
ジスティック回帰を系列データに適用するため，ラベル列のマルコフ性を仮定した素性関数を導入し，動的計画法でラベル列の予測とパラメータの学習を効率化している．そこで，ロジス
ティック回帰の素性関数，確率的勾配降下法による学習，正則化などの基礎理論を復習し，条件付き確率場の理論全体を説明する．また，能動学習，部分的に正解が付与された訓練データからの学習，深層ニューラルネットワークの適用など，条件付き確率場の最近の研究動向や実践について概観する．
キーワード：条件付き確率場，ロジスティック回帰，確率的勾配降下法．

1.

はじめに

自然言語処理は，言葉を操る賢いコンピュータを実現することを究極の目標としているが，その目標到達への道程は長い．一方で，自然言語処理は情報検索，機械翻訳，質問応答，自動要約，対話生成，評判分析，ソーシャルネットワーク分析など，幅広い応用を生み出している．
これらを支えているのは，品詞タグ付け（形態素解析），チャンキング，固有表現抽出，構文解
析，共参照解析，意味役割付与などの基盤解析技術である．
このように，自然言語処理は多種多様なタスクに取り組んでいるが，その多くのタスクは入力 x から出力 ŷ を予測する問題として定式化できる．入力 x に対する出力 y の「良さ」をスコア付けする関数を s(x, y) と書くと，与えられた入力に対して，可能な出力の集合 Y から最適な出力 ŷ を選ぶ問題は，次式で与えられる．
(1.1)

ŷ = argmax s(x, y)y∈Y

例えば，入力文を単語列 x で表し，その文がポジティブ（+1）な内容であるか，ネガティブ（−1），を判定する評判分析タスクは，次式で定式化される．
な内容であるか，どちらでもないか
（0 ）
(1.2)

ŷ =

argmax s(x, y)y∈{+1,0,−1}

関数 s(x, y) はナイーブベイズ，パーセプトロン，ロジスティック回帰，サポートベクトルマシ†

東北大学大学院 情報科学研究科：〒 980–8579 宮城県仙台市青葉区荒巻字青葉 6–6–05

統計数理

180

第 64 巻

第 2 号 2016

ン，ニューラルネットワークなどの手法を用い，訓練データから自動的に導出することが多い．
言語は構造を持つので，出力にも単語列や木などの構造を持たせることにすると，さらに多くのタスクが予測問題として定式化される．例えば，M 個の単語の列 x = (x1 , x2 , . . . , xM ) から M
個の品詞ラベルの列 y = (y1 , y2 , . . . , yM ) を予測すると，品詞タグ付け（part-of-speech tagging）
が実現する．予測するラベルの種類を B-NP, I-NP, B-VP などのチャンクタグに変更すると，浅をモデル化できる．このように，系列 x を入力として系列 ŷ をい句構造解析
（shallow parsing）
出力する問題は，系列ラベリング（sequential labeling）と呼ばれる．
ŷ = argmax s(x, y)

(1.3)

y∈Y M

ここで，出力されるラベルの集合を Y と書くと，予測されるラベル列 ŷ は Y M の中から選ぶ．
また，スコア付け関数 s(x, y) は，隠れマルコフモデル，構造化パーセプトロン，条件付き確率場などで学習する．
本稿では，系列データにおける条件付き確率場の理論と実践を解説する．条件付き確率場の本質は，多クラスロジスティック回帰を系列データに適用するため，ラベル列のマルコフ性を仮定した素性関数を導入し，動的計画法でラベル列の予測とパラメータの学習を効率化した点にある．そこで，本稿では条件付き確率場の導入として，ロジスティック回帰，および多クラ
スロジスティック回帰を復習する．これらの理論をベースに条件付き確率場を説明し，能動学
習や部分アノテーションなどの拡張や，最近の研究動向を概観する．
2.

線形二値分類器

は，入力 x に対してスコア s(x) ∈ R を計算し，その線形二値分類器（linear binary classiﬁer）
正負によって二値のラベル ŷ ∈ {+1, −1} を推定する．
(2.1)
(2.2)

s(x) = w φ(x)⎧⎨+1 (s(x) = w φ(x) ≥ 0)ŷ =⎩−1 (それ以外の場合)

ただし，φ(x) ∈ Rd は x を素性ベクトル（feature vector）で表現したものである（d は素性空間の次元数）．w ∈ Rd は重みベクトル（weight vector) と呼ばれ，訓練データに適合するように学習
は，入力の素性ベクトルと重みベクトルの内積値を計算し，その正負でラベで求める．式（2.2）
ルを推定するという，単純明快な分類ルールである．以降では，素性関数 φ(x) の設計と，重みベクトル w の学習について説明する．
2.1 素性空間式（2.2）からも明らかなように，分類器は入力 x を素性ベクトル φ(x) を通して観測し，そのラベルを予測する．したがって，高性能の分類器を開発するためには，入力の特徴をよく反映
し，ラベルの予測に効きそうな素性空間（feature space）を設計する必要がある．残念ながら，よい素性を設計するための汎用的な方法はないが，素性の作り方には一定の慣習がある．
（y = +1），そうでないか（y = −1）を推題材として，文章中の英単語 x が人名の一部であるか定するタスクを考える．単語の先頭が大文字から始まる場合，その単語は固有名詞である可能性が高くなる．例えば，素性ベクトルの 2 次元目として，次式で表現される素性関数 φ2 (x) を定義する．

条件付き確率場の理論と実践(2.3)

φ2 (x) =⎧⎨1(x が大文字で始まる場合)⎩0(それ以外の場合)

181

他にも，全ての文字が小文字か（人名の可能性は低い），全てが大文字の単語か（人名の可能性は低い），x が Mar という綴りで始まるか（Mary, Maria, Margaret のように女性の名前である可能（人名の可能性は高い）など，x の特徴を表す様々な事性が高い），文章中で直前の単語が Ms か（条件）
を考え，その条件の成立時
象を素性として定義する．このように，x の特徴を表す事象
のみ 1 を返すような素性関数をたくさん定義し，それぞれを特徴ベクトルの各次元に割り当てる．入力 x に対して素性関数 φk (x) が 0 以外の値を返すとき，入力 x に対して素性 φk が「発火」したと呼ぶ．
「単語が ie という綴り
先ほど，「単語が Mar という綴りで始まるか」という素性を説明したが，」や「単語が ard という綴りで終わるか（Richard や Edward）」
で終わるか（Stephanie, Marie, Julie）など，人名の推定に効きそうな特徴はたくさんある．また，人名ではない英単語を y = −1 と予測することも重要であるので，「人名らしくない単語の特徴」にも着目すべきである．しかしながら，これらの素性を人間が網羅的に発見し，定義することは困難である．
そこで，入力の特徴を学習データから掘り起こし，素性関数を定義するアプローチもよく採というルール
用される．例えば，学習データに含まれる単語から「長さ 3 の接頭辞を取り出す」
を設計し，抽出された全ての接尾辞に対して素性関数を定義することで，「単語が Mar という綴りで始まる」「単語が Ale という綴りで始まる」などの素性関数が自動的に導出される．素性関数を取り出すルールは，素性テンプレート（feature template）と呼ばれる．
単語 x の長さ 2, 3, 4 の接頭辞や接尾辞，単語 x の前後に出現する単語など，様々な素性テン
プレートを設計・適用することで，人名の予測に効きそうな素性を系統的に作成できる．一方，
素性テンプレートは機械的な処理なので，人名の予測に役に立たない素性も多く作り出されてしまう．しかし，線形二値分類器の学習では，それぞれの素性関数 φi (x) の有用性が重み wi で調整され，役に立たない素性の重みは 0 に近くなると期待できる．ゆえに，役に立たない素性を生成するリスクを気にせず，網羅性重視で素性テンプレートを設計することが多い．
ところで，どのような入力に対しても，常に 1 を返すような素性を導入しておくと，原点を通らない分離平面を表現することができる．例えば，入力 x によらず常に φ1 (x) = 1 を返すよ
うな素性を定義すると，y = +1 と予測する条件は次式で表される（説明のため，素性ベクトル．
の 1 次元目を用いたが，次元のインデックス番号は任意である）(2.4)

w φ(x) = w1 +

K

k=2

wk φk (x) ≥ 0 ⇔K

wk φk (x) ≥ −w1

k=2

したがって，1 次元目の重み w1 は分類時の閾値を表しており，この閾値をも学習で自動的に調（bias term）と呼ばれ，素性の重みベクトルと分けて明示節することができる．w1 はバイアス項
的に記述されることもある．
式（2.3）は，ある条件を満たした場合は 1 を，それ以外は 0 を返す関数として設計されている．
ところが，線形二値分類器の枠組みでは，素性関数は 0 や 1 だけでなく，実数値を返してもよの素性関数が 1 の代わりに 2 や 0.1 の値を返しても問題ない．実際にい．したがって，式（2.3）
は，ある素性関数の値を常に定数倍しても，対応する重みがその定数倍を打ち消すように調整されることが多いので，1 以外の素性値を用いることは稀である．
ただし，ある特徴が出現した回数や，ある特徴に関連する事象が別のコーパス中で出現する
回数など，入力 x に応じて素性値を変化させたい場合は，実数値を返す素性を定義する．例えば，大規模なコーパスにおいて，単語 x の直前に Ms という語が出現した回数（出現頻度）の対

182

統計数理

第 64 巻

第 2 号 2016

図 1．シグモイド関数 σ(a)．

数を素性値として用いることで，単語 x の名前らしさを連続値で示唆する素性を設計できる．
(2.5)

φ(x) = log(x がコーパスにおいて Ms の後に出現する回数)

なお，素性値は線形二値分類器のスコアに線形の影響を与える．式（2.5）では，少数の高頻度語の影響を抑えるため，出現回数の対数をとっている．このような非線形の変換は，実数値を返す素性の側に盛り込んでおく必要がある．
2.2 ロジスティック回帰
は線形二値分類器の一種で，入力 x に対するラベル
ロジスティック回帰（logistic regression）
y ∈ {+1, −1} の条件付き確率 p(y|x) を，シグモイド関数 σ（sigmoid function）
でスコア s(x) を確率値に変換することにより計算する．
1
p(y|x) = σ(ys(x)) =(2.6)
1 + exp (−yw φ(x))
1
シグモイド関数 σ(a) = 1+exp(−a)
は，(−∞, +∞) → (0, 1) の単調増加関数で，図 1 のような形状をしている．p(+1|x) = σ(s(x)) であるから，入力の素性ベクトルと重みベクトルの内積値
s(x) を図 1 の横軸にとり，y = +1 と予測する確率 p(+1|x) を縦軸から求めていることに相当す
る．図 1 からも明らかなように，s(x) が大きければ p(+1|x) は 1 に近づき，s(x) が小さければ
p(+1|x) は 0 に近づく．また，
1 + e−a − 1e−aea e−a1(2.7)
1 − σ(a) === a= σ(−a)
=
−a
−a
1+e
1+e
e (1 + e−a )1 + eaであるから，(2.8)

p(−1|x) = σ(−s(x)) = 1 − σ(s(x)) = 1 − p(+1|x)が成り立つ．式（2.8）
より，y = +1 と予測する確率と，y = −1 と予測する確率の和が 1 になることが確認できる．
（2.2）と整合する
なお，入力 x を y = +1 と予測する確率が 0.5 を上回る条件を求めると，式ことが確認できる．
1(2.9)
p(+1|x) ≥ 0.5 ⇔≥ 0.5 ⇔ w φ(x) ≥ 0
1 + exp(−w φ(x))

条件付き確率場の理論と実践

183

2.3 ロジスティック回帰モデルの学習
入力 x(i) に対して正解の二値ラベル y (i) を付与した N 件の訓練事例 D = (x(i) , y (i) )N
i=1 がある．ロジスティック回帰モデルの学習とは，学習データの各訓練事例の入力 x(i) に対して，その正解ラベル y (i) を再現（正しく予測）できるように，重みベクトル w を調整することである．
ある訓練事例 (x(i) , y (i) ) に関して，ロジスティック回帰モデルの予測の正しさは p(y (i) |x(i) ) で見積もることができる．すなわち，p(y (i) |x(i) ) が 1 に近ければモデルの予測が正しく，0 に近ければモデルの予測が間違っていることになる．
そこで，全ての学習事例に対して p(y (i) |x(i) ) を計算し，その確率の積を求める．
N(2.10)p(y (i) |x(i) )i=1

式（2.10）は，学習データ D におけるモデルの尤もらしさを表すので，尤度（likelihood）と呼ばれを重みベクトル w の関数とみなし，式（2.10）を最大化するような重みる．したがって，式（2.10）
ベクトル w∗ を求めると，訓練事例を再現できる分類器を学習したことになる．このように，尤度関数を最大化することでモデルのパラメータを学習することを最尤推定（maximum likelihoodと呼ぶ．ただ，式（2.10）
は，小さい数（確率値）の積を計算するため，数値計算ではアンestimation）（log likelihood）
ダーフローなどの問題を引き起こす．そこで，式（2.10）の対数をとった対数尤度を最大化することが多い．
(2.11)

LLR = logNp(y (i) |x(i) ) =

i=1

N


log p(y (i) |x(i) )i=1

まとめると，ロジスティック回帰モデルの学習は，以下の目的関数 E LR (w) を最小化することに帰着する．
(2.12)E LR (w) = −LLR = −Nlog p(y (i) |x(i) )i=1

幸いなことに，この目的関数は凸関数であり，大域最適解 w∗ を持つ．式（2.12）を最小化する手法として，L-BFGS 法や確率的勾配降下法（stochastic gradient descent）が代表的である．ここでは，理論と実装が簡単な確率的勾配降下法を説明する．
確率的勾配降下法は勾配降下法（gradient descent）をベースにしている．勾配降下法は，次の（2.12）の解を求める．
漸化式を t = 1, 2, . . . , T に関して適用し，式(2.13)

w(t+1) = w(t) − η (t)LR∂E LR (w)(t)(t) ∂L
=
w
+
η
∂w(t)
∂w(t)

重みベクトルの初期値 w(1) は 0 など，適当な値に設定すればよい．η (t) は学習率と呼ばれ，1/t,√（t0 > 0 はハイパー・
1/ t, 1/(t0 + t) など，反復が進むにつれて減衰していくように設定するは，t 回目の反復において w(t) を LLR の最急方向（steepest direction）にパラメータ）．式（2.13）
向け，幅 η (t) だけ動かすという更新式を表している．反復を終了する回数 T は，ハイパー・パ
ラメータとして予め設定したり，収束判定などで漸化式の適用時に自動的に決定する．例えば，反復において重みベクトルの変化量の 2 - ノルムが初めて  > 0 を下回った時を収束と判定するには，次式を用いる．
(2.14)

w(T +1) − w(T ) 2 < 

ところで，訓練事例ごとの対数尤度

統計数理

184

(2.15)

第 64 巻

第 2 号 2016

l(x, y) = log p(y|x)

を定義すると，勾配はN
∂l(x(i) , y (i) )
∂LLR
=
∂w
∂w
i=1

(2.16)

LR∂Lのように，各訓練事例の勾配の和として書ける．したがって，式（2.13）の勾配 ∂w(t) を求める
(i)

(i)

,y )
には，学習データ D に含まれている全ての訓練事例 (x(i) , y (i) ) に関する対数尤度 ∂l(x∂w(t)を計算し，その和を計算することになる．しかしながら，学習データの訓練事例数が多くなると，
式（2.16）の計算に時間がかかるだけでなく，重みベクトル w を更新する間隔が長くなり，収束が遅くなる．
∂LLRのように各事例の勾配の和で求められるとき，勾配 ∂w
確率的勾配降下法は，勾配が式（2.16）(t)(i)の代わりに各事例 (x(i) , y (i) ) の勾配 ∂l(x ∂w,y化式を用いる．

(i)w(t+1) = w(t) + η (t)(2.17))

を用いる．すなわち，式（2.13）の代わりに次の漸∂l(x(i) , y (i) ), i = t mod N∂w(t)なお，t mod N は t を訓練事例数 N で割ったときの余りである．
式（2.17）の更新式を得るため，訓練事例 (x, y) 毎の対数尤度 l(x, y) を重みベクトル w で微分する．l(x, y) を合成関数とみなすと，∂l(x, y)∂l(x, y) ∂p(y|x) ∂s(x, y)=.
∂w∂p(y|x) ∂s(x, y) ∂w(2.18)

式（2.15）より，(2.19)∂l(x, y)∂1=
log p(y|x) =.
∂p(y|x)∂p(y|x)p(y|x)

次に，p(y|x) を s(x, y) で微分する（簡略化のために s = s(x, y) と略記する）．最終行の変形では，
（2.7）
を用いる．
式（2.6）と式(2.20)∂p(y|x)∂=∂s(x, y)∂s

1
1 + e−ys1· e−ys · (−y)= (−1) ·(1 + e−ys )2
=y·

1
e−ys
·
= y · p(y|x) {1 − p(y|x)}
1 + e−ys 1 + e−ys

また，
(2.21)∂s(x, y)∂=(w φ(x)) = φ(x)
∂w
∂w

ゆえに，
(2.22)∂l(x, y)1=
· y · p(y|x) {1 − p(y|x)} · φ(x) = y {1 − p(y|x)} φ(x).
∂wp(y|x)

最終的に，式（2.17）の更新式は次式で表される．
(2.23)

w(t+1) = w(t) + η (t) y (i) {1 − p(y (i) |x(i) )}φ(x(i) ), i = t mod N

理論的な説明が長くなったが，確率的勾配降下法によるロジスティック回帰モデルの学習は

条件付き確率場の理論と実践

185

Algorithm 1 の擬似コードで表される．この擬似コードでは，学習データに対する反復回数をT 回と定めているが，式（2.14）を使って収束を判定してもよい．また，学習率 η の計算も，1/t,√
1/ t, 1/(t0 + t) などに変更してもよい．
Algorithm 1: 確率的勾配降下法によるロジスティック回帰モデルの学習

入力: 学習データ D = (x(i) , y (i) )N
i=1
出力: 重みベクトル w
t ← 1;
w = 0;
for epoch ← 1 to T do
for i ← 1 to N do
η ← 1/t（※他の計算方法でも可）;)w を用いて）;q ← 1 − p(y (i) |x(i)（※現在の重みベクトル(i)(i)
w ← w + ηy (1 − q)φ(x );t ← t + 1;
end
end

学習率 η を 1 に固定して考えると，Algorithm 1 は各訓練事例 (x(i) , y (i) ) ∈ D に対して，以下の処理を行うと解釈できる．
（事例（1）現在の重みベクトル w を使い，訓練事例の入力 x(i) からラベル y (i) を予測する確率q を計算する．
の尤度）（2）重みベクトル w を次式で更新する: wnew ← wold + y (i) (1 − q)φ(x(i) )．
y (i) = +1 のとき，更新後の重みベクトル wnew は次式で与えられる．
(2.24)

wnew = w + (1 − q)φ(x(i) )基本的に，重みベクトル w に訓練事例の素性ベクトルを φ(x(i) ) を足し込むことになり，その量は (1 − q) で調整される．ここで，(1 − q) は予測の外れ度合いを表すので，予測が大幅に外れているときは重みベクトルの更新幅が大きくなり，予測がそれほど外れていないときは，重みベクトルの更新幅が小さくなる．
更新後の重みベクトル wnew を使ってスコア snew (x(i) ) を再計算する．
(2.25)

snew (x(i) ) = (w + (1 − q)φ(x(i) )) φ(x(i) )= w φ(x(i) ) + (1 − q)(φ(x(i) )) φ(x(i) ) ≥ s(x(i) )したがって，訓練事例 (x(i) , y (i) ) に関して重みベクトルを更新することで，スコア s(x(i) ) が上昇するので，この事例のラベルを +1 と予測しやすくなることが分かる．
y (i) = −1 のときも同様に，(2.26)

snew (x(i) ) = (w − (1 − q)φ(x(i) )) φ(x(i) )= w φ(x(i) ) − (1 − q)(φ(x(i) )) φ(x(i) ) ≤ s(x(i) )であるから，スコア s(x(i) ) を減少させる作用があり，この事例のラベルを −1 と予測しやすく

統計数理

186

第 64 巻

第 2 号 2016

なる．
2.4 正則化の目的関数が最小となる条件について考えてみたい．これは，式（2.10）の尤
ここで，式（2.12）
度が最大となる時であるから，全ての学習事例の尤度が 1 となる場合である．しかし，式（2.6）
から明らかなように，ロジスティック回帰モデルで p(y|x) = 1 となるのは，s(x) → ±∞ の時だけである．素性ベクトル φ(x) の大きさを ∞ とすることはあり得ないので，s(x) → ±∞ を成立させるには，重みベクトル w の大きさが ∞ になる必要がある．
一般的に，重みベクトル w が大きくなると，素性ベクトル φ(x) の僅かな差でもスコア s(x)が大きく変動するため，学習データのノイズに対する耐性が低下する．また，重みベクトルの要素の分散が大きくなるため，それぞれの訓練事例のみで発火する素性に依存してスコア付けを行うようになり，過学習を引き起こす．そこで，実際にロジスティック回帰モデルを学習す
るときは，目的関数に正則化項（regularization term）を追加し，重みベクトル w が大きくなり過ぎないように制御する．例えば，L2 - 正則化（l2 -regularization）では重みベクトル w の 2 - ノル
ムをペナルティ項として目的関数に導入する．
(2.27)

E L2LR (w) = −LLR +N1
1
log p(y (i) |x(i) ) + Cw22
Cw22 = −2
2i=1

ただし，C > 0 は L2 - 正則化の強さを調整するハイパー・パラメータである．C を大きくすると，訓練事例への適合よりも w の 2 - ノルムの大きさを抑える作用が強くなる．C を小さくすると，訓練事例への適合を重視する傾向が強くなる．
式（2.27）の目的関数を w で微分し，確率的勾配降下法を適用すると，重みベクトル w の更新式は次式で表される．
(2.28)

w(t+1) = (1 − η (t) C)w(t) + η (t) y (i) {1 − p(y (i) |x(i) )}φ(x(i) ), i = t mod N

したがって，L2 - 正則化付きでロジスティック回帰モデルを学習するには，Algorithm 1 の重みに変更するだけでよい．正則化を行わなかった場合の更新式（2.23）
ベクトルの更新式を式（2.28）と比較すると，各反復で重みベクトル w を (1 − η (t) C) 倍するという処理が加わり，重みベクト
ルを縮小させようとする力が働く．
また，目的関数に重みベクトル w の 1 - ノルムをペナルティ項として加えた L1 - 正則化（l1 regularization）
もよく用いられる．
(2.29)

E L1LR (w) = −LLR + C|w| = −Nlog p(y (i) |x(i) ) + C|w|

i=1

ここで，C > 0 は L1 - 正則化の強さを調整するハイパー・パラメータである．L1 - 正則化は，素性の重みの値を 0 に落とそうとする作用があることが知られている．学習の結果，素性の重みが0 になったということは，その素性は無くてもよいと学習アルゴリズムが判断したことになるた
め，L1 - 正則化は学習と素性選択を同時に行う方法としても知られている．ただ，式（2.29）の目的
関数は wk = 0 において微分不可能であるため，そのままでは確率的勾配降下法を適用できない．
しかし，FOrward-Backward Splitting（FOBOS）などの手法を用いることにより，Algorithm 1 に近い流れの擬似コードで重みベクトルを学習できる（Duchi and Singer, 2009）．
3.

線形多クラス分類器

本節では，入力 x に対して，L 個のラベル Y = {1, 2, . . . , L} の中から 1 つのラベル y ∈ Y を条件付き確率場の理論と実践

187

推定する線形多クラス分類器（linear multi-class classiﬁer）を説明する．説明を簡単にするため，，y = 2 は「組織名」など，ラベルの番
ラベル y は正の整数を取ることにするが，y = 1 は「人名」
号に任意の分類カテゴリを割り当ててよい．線形二値分類器では単一の重みベクトル w ∈ Rdを用いたが，線形多クラス分類器では L 個のラベルに対応する重みベクトル w1 , . . . , wL を用いる．線形二値分類器と同様に，入力素性ベクトル φ(x) ∈ Rd と重みベクトル wy ∈ Rd との内積を，入力 x をラベル y に分類するスコア s(x, y) と定義する．
s(x, y) = wy φ(x)(3.1)

そして，入力 x に対するラベル ŷ を次式で推定する．
(3.2)

ŷ = argmax s(x, y) = argmax wy φ(x)
y∈Y

y∈Y

式（3.4）は，候補となる全てのラベル y ∈ Y に関してスコア s(x, y) を計算し，最も高いスコアを与えたラベル ŷ に分類するという，単純明快なルールである．素性関数 φ(x) の設計は，2.1 節
で説明した方針のままでよい．
と（3.2）で理解しておけばよいが，より一般的には次の線形多クラス分類器の原理は，式（3.1）
ように定式化される．
(3.3)

s(x, y) = λ f (x, y) =K

λk fk (x, y)

k=1

(3.4)

ŷ = argmax s(x, y) = argmax λ f (x, y)
y∈Y

y∈Y

この定式化での素性空間の次元数を K とすると，λ ∈ RK は重みベクトル，f (x, y) ∈ RK は入力 x とラベル y に関する素性ベクトルを表す．
式（3.1）と
（3.2）
よりも式
（3.3）
と（3.4）の定式化の方が一般性が高く，表現力も高いため，本稿（3.4）の定式化を採用する．しかし，式（3.3）と（3.4）の定式化では，素性空間が入では式（3.3）と
力 x だけでなくラベル y にも依存するため，最初は分かりづらい．イメージを掴んでもらうた
め，式（2.3）に示した線形二値分類器の素性関数を多クラス分類に拡張し，ラベル y = 1 の時のみに発火する素性関数の例を示す．
⎧⎨1 (x が大文字で始まる ∧ y = 1)
(3.5)
f2 (x, y) =⎩0 (それ以外の場合)
f2 は，x が大文字で始まり，かつラベルを y = 1 と予測する場合に発火する素性である．さらに，「x が大文字で始まる」という特徴に関して，予測するラベル y = 1, 2, . . . , L 毎に素性関数を
f2 , f3 , . . . , fL+1 などと定義する．すると，λ2 , λ3 , . . . , λL+1 は「x が大文字で始まる」という特徴
から，それぞれラベル y = 1, 2, . . . , L を予測するときの重みを表すようになる．
（3.4）の定式化は，f (x, y) と λ を次のように定義すると，式（3.1）と（3.2）の定式化と式（3.3）と等価になる．
(3.6)

f (x, y) = 0 ⊕ · · · ⊕ 0⊕ φ(x) ⊕0 ⊕ · · · ⊕ 0


y−1

(3.7)

L−y

λ = w 1 ⊕ w2 ⊕ · · · ⊕ wL

ただし，0 ∈ Rd ，⊕ はベクトルの連結を表す．すなわち，素性空間を d 次元ずつ L 個のグループに分け，素性空間の各グループをラベル y ∈ Y に対応付ける（K = dL）．重みベクトル λ は

統計数理

188

第 64 巻

第 2 号 2016

各ラベルに対応した重みベクトル w1 , . . . , wL を並べたものである．素性関数 f (x, y) は，ラベ
ル y に対応する素性空間グループで入力 x の素性ベクトル φ(x) を展開し，その他のグループでは 0 とする．したがって，s(x, y) = λ f (x, y) = wy φ(x) となり，式（3.1）と式（3.3）が一致する．
実際に多クラス分類器を構築するときは，素性関数 f (x, y) を直接設計することは稀である．
代わりに，入力 x に関する素性ベクトル φ(x) を定義し，式（3.6）の変換を用いて多クラス分類
用の素性関数 f (x, y) を自動的に導出することが多い．したがって，多クラス分類器のツールを使うだけであれば素性関数 f (x, y) を意識する必要はない．しかし，式（3.3）と（3.4）の定式化を用いると，次式のように複数のラベル（y = 1 or 2）で共通に発火する素性を定義できる（素性の．
次元の番号 2045 は適当である）⎧⎨1 (x が大文字で始まる ∧ (y = 1 ∨ y = 2))(3.8)
f2045 (x, y) =⎩0 (それ以外の場合)
例えば，y = 1 を人名，y = 2 を組織名であることにすると，これらの固有名詞で共通に発火す
る素性を定義したことになる．
3.1 多クラスロジスティック回帰（二値分類である）
ロジスティック回帰では，素性ベクトルと重みベクトルの内積で計算されるスコアを，シグモイド関数（sigmoid function）を使って確率値に変換していた．多クラスロジ
スティック回帰では，ラベル y 毎に計算されるスコア s(x, y) にソフトマックス関数（softmaxを適用し，入力 x に対してラベル y が予測される条件付き確率を求める．
function）(3.9)

p(y|x) = 

exp s(x, y)
exp (λ f (x, y))

=



y  ∈Y exp s(x, y )y  ∈Y exp (λ f (x, y ))式（3.9）の分母は，分配関数（partition function）と呼ばれる．

(3.10)
Z(x) =
exp λ f (x, y  )y  ∈Yなお，多クラスロジスティック回帰モデルは，最大エントロピー法（maximum entropy modeling）とも呼ばれる．
（Berger et al., 1996）
多クラスロジスティック回帰モデルの学習では，（二値分類の）ロジスティック回帰モデルの理論とアルゴリズムをそのまま流用できる．言い換えれば，各事例の対数尤度の勾配さえ求めることができれば，確率的勾配降下法による最尤推定や事後確率最大化（正則化）の手順は全く同じで(i)(i))
ある．ここでは，最尤推定について説明する．学習データ D = (x(i) , y (i) )N
i=1 の各事例 (x , y(i)(i)(i) (i)MLRの対数尤度を l(x , y ) = log p(y |x ) とすると，学習データ全体の対数尤度 L，最小化
すべき目的関数 E MLR (λ) は，(3.11)LMLR = log

N

i=1

(3.12)p(y (i) |x(i) ) =Nlog p(y (i) |x(i) ) =i=1

E MLR (λ) = −LMLR = −Nl(x(i) , y (i) )

i=1
N


l(x(i) , y (i) ).

i=1

確率的勾配降下法を適用するため，各事例の対数尤度 l(x, y) を展開する．

条件付き確率場の理論と実践(3.13)

l(x, y) = log p(y|x)= λ f (x, y) − log
exp λ f (x, y  )y  ∈Y=K

λk fk (x, y) − logexpy  ∈Y

k=1

189

K





λk fk (x, y )

k=1

そして，式
（3.13）を λk に関して偏微分する．第 1 項では k に関する部分のみを考えればよい．
第 2 項には合成関数，対数関数，指数関数の微分公式を適用する．
⎧
K
⎫
K
⎬
⎨


∂l(x, y)∂
(3.14)=
λk fk (x, y) − logexp
λk fk (x, y )
⎭
∂λk
∂λk ⎩
k=1
k=1
y  ∈Y




K



y  ∈Y exp
k=1 λk fk (x, y ) · fk (x, y )= fk (x, y) −Ky  ∈Y exp
k=1 λk fk (x, y )
(3.15)p(y  |x)fk (x, y  )= fk (x, y) −y  ∈Yゆえに，k 番目の素性に関する確率的勾配降下法の更新式は，
⎫
⎧
⎬
⎨

(t+1)
(t)
(t)
(i)
(i)
 (i)
(i)

(3.16)λk= λk + ηp(y |x )fk (x , y ) , i = t mod N
fk (x , y ) −
⎭
⎩

y ∈Y

式（3.15）および（3.16）の解釈を考えてみたい．簡単のため，素性 fk はどれか 1 つのラベル（0 を返す）こととに関してのみ発火し（1 を返す），それ以外のラベルに関しては発火しないする．もし，訓練事例 (x(i) , y (i) ) に関して素性 fk が発火する場合，fk (x(i) , y (i) ) = 1 かつ∀y  = y (i) : fk (x(i) , y  ) = 0 であるから，(3.17)∂l(x(i) , y (i) )= 1 − p(y (i) |x(i) ) ≥ 0.
∂λk

式（3.16）に当てはめて考えると，予測誤差に応じて素性 fk の重みが増加する．これは，fk が訓練事例に関して発火しているため，その信頼度を増やそうとしていると解釈できる．
一方，訓練事例 (x(i) , y (i) ) に関して素性 fk は発火しないものの，正解のラベル y (i) を別のラベ
ル ỹ に置き換えると発火する場合を考える．これは，素性 fk は入力 x(i) の特徴を捉えようとするが，正解とは異なるラベル ỹ = y (i) を予測しようとする状況である．このとき，fk (x(i) , ỹ) = 1
かつ ∀y  = ỹ : fk (x(i) , y  ) = 0，よって fk (x(i) , y (i) ) = 0 であるから，(3.18)∂l(x(i) , y (i) )= 0 − p(ỹ|x(i) ) ≤ 0∂λk

訓練事例 (x(i) , y (i) ) は，入力 x(i) に対してラベル ỹ を予測することは間違いであることを示唆（3.16）に当てはめて考えると，予測誤差に応じてしているため，p(ỹ|x(i) ) は予測誤差を表す．式
素性 fk の重みが減少する．これは，fk が訓練事例に関して発火せず，正解とは異なるラベルで発火してしまうため，その信頼度を下げようとしていると解釈できる．
なお，訓練事例 (x(i) , y (i) ) の入力 x(i) に対して，どのようなラベル y  ∈ Y に関しても素性 fkが発火しない場合，∀y  ∈ Y : fk (x(i) , y  ) = 0 であるから，(3.19)∂l(x(i) , y (i) )
= 0.
∂λk

統計数理

190

第 64 巻

第 2 号 2016

これは，訓練事例 (x(i) , y (i) ) の入力 x(i) とは全く関連がない素性 fk に関しては，その重み λkを更新しないことを表している．
Algorithm 2 に，確率的勾配降下法による多クラスロジスティック回帰モデルの学習の擬似コードを示す．
Algorithm 2: SGD による多クラスロジスティック回帰モデルの学習

入力: 学習データ D = (x(i) , y (i) )N
i=1
出力: 重みベクトル λ ∈ RKt ← 1;
λ = 0;
for epoch ← 1 to T do
for i ← 1 to N do
η ← 1/t（※他の計算方法でも可）;for k ← 1 to K doλk ← λk + η fk (x(i) , y (i) ) − y ∈Y p(y  |x(i) )fk (x(i) , y  ) ;endt ← t + 1;
end
end

4.

条件付き確率場

多クラスロジスティック回帰では，ラベル y は単一の確率変数であった．これに対し，条件（Laﬀerty et al., 2001）では，複数の確率変数を同時に予付き確率場（conditional random ﬁelds）
測する．予測される確率変数は入力 x に依存するだけでなく，系列や木構造などのグラフ構造
上でマルコフ性に従うと仮定する．入力 x も構造を持つと仮定してもよいが，入力と出力の構造は一致しなくてもよい．
自然言語の単語や文は無秩序に並んでいるのではなく，何らかの規則性を持っている．その規則性を分類モデルに取り込むことで，タスクの予測精度の向上が期待できる．例えば，英語では「文頭の単語は名詞になりやすい」「冠詞の後には名詞や形容詞が続きやすい」などの規則性があり，この規則性は単語列から品詞列を推定するのに役立つ．
本稿では，条件付き確率場の代表例として，系列 x = x1 , . . . , xM が与えられた時，ラベル
列 y = y1 , . . . , yM を予測する系列ラベリング（sequential labeling）問題を扱う（M は系列の要素
数）．先ほどの品詞タグ付けの例では，入力 x が単語列，ラベル列 y が品詞ラベル列となる．ここで，隣り合うラベル同士 ym , ym+1（m = 1, . . . , M − 1）の依存関係（線形連鎖一次マルコフ性）「直前の品詞の予測結を考慮し，ラベル列 y を予測することを考える．品詞タグ付けの例では，
果が冠詞ならば現在の単語の品詞は名詞や形容詞になりやすい」などの依存関係を考慮することになる．
条件付き確率場の予測モデルは，多クラス線形分類器の入力 x を系列 x に，ラベル y をラベ（式（3.3））と同様に，入力系列 x のラベル
ル列 y に置き換えたものになる．線形多クラス分類器
系列 y を予測するスコア s(x, y) を，素性ベクトル f (x, y) ∈ RK と重みベクトル λ ∈ RK の内積で計算する．素性関数 f (x, y) は，系列 x とラベル列 y の全体から素性ベクトルを取り出す関数である．

条件付き確率場の理論と実践

s(x, y) = λ f (x, y) =

(4.1)

K


191

λk fk (x, y)

k=1

式（3.2）と同様に，入力系列 x に対するラベル列 ŷ を次式で推定する．
ŷ = argmax s(x, y) = argmax λ f (x, y)

(4.2)

y∈Y

y∈Y

ここで，各ラベル ym ∈ y が取りうるラベルの集合を Y とすると，ラベル列の候補集合は Y = Y Mである．
式（3.2）で考慮すべきラベルの候補数は |Y| であったが，式（4.2）ではラベル列の候補は |Y|M
通りである．例えば，ラベルの種類数 |Y| = 9 とし，長さ M = |x| = 10 のラベル列を予測する
場合でも，ラベル列の候補数は 3, 486, 784, 401 に膨れ上がる．したがって，式（4.1）をラベル列の全候補 Y に関して計算し，最大のスコアを与えたラベル系列 ŷ を求めることは事実上不可能を効率よく求めるアルゴリズムは，4.2 節で紹介する．
である．式（4.2）
式（3.9）と同様に，ラベル列 y 毎に計算されるスコア s(x, y) にソフトマックス関数を適用し，入力系列 x に対してラベル列 y が予測される条件付き確率を求める．
(4.3)

p(y|x) = 

exp s(x, y)
exp (λ f (x, y))
= 



y  ∈Y exp s(x, y )y  ∈Y exp (λ f (x, y ))

ここで，式
（4.3）
の分母（分配関数）の計算には，ラベル列の全候補 y  ∈ Y に関する内積とその和が必要である．



(4.4)
Z(x) =
exp λ f (x, y  )y  ∈Y式（4.4）を愚直に計算すると，指数オーダー（|Y|M 回）の内積計算と加算演算が必要になり，分配関数の値を求めることも事実上不可能である．式（4.4）を効率よく計算する方法は，4.3 節で説明する．
条件付き確率場の学習では，（多クラス）
ロジスティック回帰モデルの学習の理論とアルゴリ
ズムをそのまま流用できる．すなわち，各訓練事例の対数尤度さえ求めることができれば，確率的勾配降下法による最尤推定や事後確率最大化（正則化）の手順は全く同じである．学習デー(i)(i)) の対数尤度を l(x(i) , y (i) ) = log p(y (i) |x(i) ) とすると，
タ D = (x(i) , y (i) )N
i=1 の各事例 (x , y
学習データ全体の対数尤度 LMLR は，(4.5)

LMLR = logNp(y (i) |x(i) ) =

i=1

N


log p(y (i) |x(i) ) =

i=1

N


l(x(i) , y (i) )i=1

確率勾配降下法による重みベクトル λ の更新式は，式（2.17）と同一である．
(4.6)

λ(t+1) = λ(t) + η (t)∂l(x(i) , y (i) ), i = t mod N∂λ(t)そこで，式（4.6）の更新式で必要な勾配を求める．多クラスロジスティック回帰から条件付き確率場に拡張する際に変更したのは，入力とラベルの型だけなので，式（3.15）の導出を再利用
すると，重み λk に関する偏微分は次式で与えられる．
∂l(x, y)(4.7)
= fk (x, y) −p(y  |x)fk (x, y  )
∂λk

y ∈Y



式（4.7）の第 2 項は，ラベル列の全候補 y ∈ Y において現在の確率モデルが素性関数 fk を発火

192

統計数理

第 64 巻

第 2 号 2016

させる期待値である．ラベル列の全候補 y  ∈ Y が必要であることに加えて，素性関数 fk が発
火するかどうかが y  に依存しているため，この値を求めることも容易ではない．
まとめると，条件付き確率場は多クラスロジスティック回帰の入力 x を入力系列 x に，ラベル y をラベル列 y に置換しただけのモデルであるが，計算上の困難が 3 つある．
（4.2）
（1）スコアを最大にするラベル列 ŷ の予測: 式（4.4）（2）分配関数 Z(x) の計算: 式（3）素性関数のモデルにおける発火の期待値: 式（4.7）
これらを効率よく計算するための鍵は，いずれも，ラベル列の一次マルコフ性に基づく素性関
数 f (x, y) の設計と，動的計画法である．以降では，これらについて説明していく．
4.1 線形連鎖 1 次マルコフ素性
本稿では，入力系列 x が与えられた時，ラベル列に関して一次マルコフ性を仮定する．すなわ
ち，位置 m のラベル ym の予測結果は，入力 xm ，隣接するラベル ym−1 ，および ym+1 に依存す
ると仮定する．この依存関係は，xm , ym−1 , ym を引き数とした素性関数で記述できる．例えば，（I-ORG）で，現在の単語も組織名（I-ORG）
現在の単語が “Ltd” で，直前の単語が組織名の途中である場合に発火する素性は，次式で表される．
⎧⎨1 (xm が “Ltd” ∧ ym−1 が I-ORG ∧ ym が I-ORG)
(xyy)
(4.8)
πk
(xm , ym−1 , ym ) =⎩0 (それ以外の場合)

なお，この素性関数は 1 つの入力 xm ，2 つのラベル ym−1 , ym に依存するので，(xyy) という印を付けてある．
また，xm ，ym ，ym−1 のどれかに依存しない素性を考えてもよい．例えば，直前のラベル ym−1に関わらず，現在の単語 “Ltd” と組織名
（I-ORG）の依存関係を表現する素性は，次式で表される．
⎧⎨1 (xm が “Ltd” ∧ ym が I-ORG)(xy)
πk (xm , ym ) =(4.9)⎩0 (それ以外の場合)
さらに，位置 m を任意とし，隣接するラベル間の事象のみを記述した素性は，次式で表される．
⎧⎨1 (ym−1 が B-PERSON ∧ ym が I-PERSON)(yy)(4.10)πk (ym−1 , ym ) =⎩0 (それ以外の場合)
線形連鎖一次マルコフ素性に基づく条件付き確率場では，式（4.8），式（4.9），式（4.10）のいず
れかの型を持つ素性関数を定義することになる．
ところで，線形多クラス分類器では，入力 x と予測ラベル y の両方で条件付けされた素性関
数 f (x, y) を直接設計することは稀で，入力 x に関する素性ベクトル φ(x) を定義し，素性関数
f (x, y) を自動的に導出することを説明した．条件付き確率場でも，入力 x に関する素性ベクトル φ(x) の設計に注力し，式（4.8），式（4.9），式（4.10）の形の素性関数を自動的に導出するのが一般的である．
の形は多クラス線形分類器のものと同一であり，（3）節で説明した方法で自動
例えば，式（4.9）の形の素性は，すべてのラベルの組み合わせ (ym−1 , ym ) ∈ Y 2
的に導出できる．また，式（4.10）に対して定義するか，訓練事例に出現する隣り合うラベルの組み合わせに対して定義すればよい．式（4.8）の形の素性は，以上の方法を組み合わせることによって導出できる．このように，
条件付き確率場のツールを使うだけであれば，素性関数を直接設計しなくてもよい．

条件付き確率場の理論と実践

193

さて，式
（4.8）
の形の素性関数を K1 個定義し，その全ての素性関数の値を K1 次元ベクトルで返す素性関数ベクトルを π (xyy) (xm , ym−1 , ym ) ∈ RK1 と書く．同様に，式（4.9）と式（4.10）の素性関数をそれぞれ，K2 個，K3 個定義し，素性関数ベクトルで表現したものを，それぞれ，π (xy) (xm , ym ) ∈ RK2 ，π (yy) (ym−1 , ym ) ∈ RK3 と書く（ただし，K = K1 + K2 + K3 ）．線形連鎖
，式
（4.9）
，式
（4.10）のいずれかで表されるので，時刻 m における一次マルコフ素性は，式（4.8）
素性関数ベクトル π(xm , ym−1 , ym ) ∈ RK は次式で表される．
(4.11)π(xm , ym−1 , ym ) = π (xyy) (xm , ym−1 , ym ) ⊕ π (xy) (xm , ym ) ⊕ π (yy) (ym−1 , ym )π(xm , ym−1 , ym ) は，位置 m における素性ベクトルを表すので，局所素性ベクトルと呼ぶ．この記法に基づくと，線形連鎖一次マルコフ素性による大域素性ベクトルは次式で表される．
(4.12)f (x, y) =Mπ(xm , ym−1 , ym )m=1

ただし，m = 1 のとき，y0 は系列の先頭を表す特殊なシンボル BOS とし，x1 と y1 のみに依存する素性とするか，系列の先頭のラベルを捉える素性としてもよい．同様に，系列の末尾のラベルを捉える素性を導入してもよい．
4.2 ラベル列の推定式（4.2）を効率よく求める方法を説明するため，以下の量を定義する．
(4.13)

rx (m, i, j) = λ π(xm , i, j)rx (m, i, j) は，入力系列 x が与えられた時，ym−1 = i かつ ym = j の時に発火する素性関数の重みの和である．
（4.12），式（4.13）
より，式（4.1）は次のように展開できる．
式（4.11），式(4.14)

s(x, y) = λ f (x, y) = λ

M

m=1

π(xm , ym−1 , ym ) =Mrx (m, ym−1 , ym )m=1

これは，系列全体の大域素性ベクトル f (x, y) を先に求めてから重み λ との内積を計算する代
わりに，先に各時刻 m = 1, 2, . . . , M において局所素性ベクトル π(xm , ym−1 , ym ) と重みベクト（4.14）の計算
ル λ の内積を求め，その和を計算しても結果が同じであることを示している．式は大変そうに見えるが，素性関数は式（4.8），式（4.9），式（4.10）のいずれかの形をしているため，
入力 x の時刻 m における特徴量に対応した素性や，ラベルのペアに関する素性の次元番号を列挙し，その次元番号に対応する重み取り出し，その和を計算するだけでよい．
の計算をラティスとして図示したものである．横軸は時刻 m = 1, 2, 3，縦図 2 は，式（4.14）
軸はラベル y を表し，図中の各ノード (m, j) は時刻 m のラベル ym = j である事象を表している．また，各点をつなぐ線（エッジ）
は，rx (m, ym−1 , ym ) の値を示している．この図を用いると，m = 1 から m = 3 に至る任意の経路がラベル列 y を表し，その経路上の重みの和がスコア
s(x, y) である．したがって，式（4.2）
を求める問題は，図 2 で m = 1 から m = 3 に至る経路の中で，スコアが最大となる経路を求める問題に帰着する．
この問題は，最短経路問題と同様に，以下の漸化式で求めることができる．
⎧⎨rx (1, EOS, j)(m = 1 のとき)
(4.15)
ψx (m, j) =⎩maxi∈Y {ψx (m − 1, i) + rx (m, i, j)} (m > 1 のとき)
ここで，ψx (m, j) は図 2 の左端からノード (m, j) に至る経路の中で，最大のスコアを記録した

194

統計数理

第 64 巻

第 2 号 2016

図 2．ラティスで表現した素性の重み．エッジの数字は rx (m, i, j) の値を表す．

図 3．ビタビ・アルゴリズムの動作例．ノードは各時点 m におけるラベル ym を表す．エッジの数字は rx (m, i, j) の値を表す．ノードの左上の青色の数字は ψx (m, j) を，赤色のエッジはその値がどこに由来するのかを示している．

ものである．式（4.15）
は，ノード (m − 1, i) を経由してノード (m, j) に至る経路のスコアの最大値は，ψx (m − 1, i) + rx (m, i, j) で与えられることを利用し，経路のスコアを最大にする経由地(m − 1, i) を選ぶことで，ノード (m, j) に至る経路のスコアの最大値を求めている．
式（4.15）の漸化式を使い，ψx (m, j) の値を m = 1 から m = M まで求めたとき，スコアが最大となる経路の終点 (M, ŷM ) は次式で表される．
(4.16)ŷM = argmax ψx (M, i)i∈Y

そして，この終点に至るまでの経路を逆向きに辿ることで，式（4.2）の解を求めることができる．
すなわち，m = M − 1 から m = 1 まで，以下の漸化式を適用していけばよい．
(4.17)ŷm = argmax {ψx (m, i) + rx (m + 1, i, ŷm+1 )}i∈Y

実際には，式（4.17）を計算しなくても，式（4.15）の漸化式を適用する際に選ばれた経由地への逆向きのリンクを保持しておけば，終点 (M, ŷM ) から逆向きのリンクを辿っていくだけでよい．
この計算過程を示したのが図 3 である．図中のノード (m, i) の上に ψx (m, i) の値を示し，その値がどのノードから来たのか，赤色の矢印で示してある．式（4.16）に従い，m = 3 のラベルを条件付き確率場の理論と実践

195

図 4．前向き・後ろ向きアルゴリズムの計算例．ノードは各時点 m におけるラベル ym を表す．
エッジの数字は řx (m, i, j) の値を表す．ノードの左上の青色の数字は αx (m, j) を，右（4.22）で求めた分配関数の値を BOS の右下に，下の緑色の数字は βx (m, i) を表す．式
式（4.24）で求めた分配関数の値を EOS の左上に示した．前向き・後ろ向きのどちらを使っても，分配関数の値が同じになることを確認できる．

NN と決定したら，そのノードに至る矢印を逆向きに辿ることで，式（4.2）の解，すなわち予測されるラベル列 ŷ を求めることができる．図 3 の場合は，NN VB NN が解となる．このアルゴ
リズムは，ビタビ・アルゴリズム（Viterbi algorithm）と呼ばれる．
4.3 分配関数の計算を効率よく求める方法を説明する．まず，rx (m, i, j) の指数を取っ
次に，分配関数（式（4.4））た関数 řx (m, i, j) を定義する．
(4.18)řx (m, i, j) = exp rx (m, i, j)

分配関数の定義を řx (m, i, j) の式として書き直す．
(4.19)
Z(x) =
exp s(x, y)
y1 ,...,yt ∈Y L

=



M


řx (m, ym−1 , ym )y1 ,...,yt ∈Y L m=1

式（4.19）を展開し，共通部分を m = 1 から括り出すと，次のようになる．
(4.20)

Z(x) =Lřx (1, BOS, y1 )

y1 =1

L

y2 =1

řx (2, y1 , y2 )

L

y3 =1

...

L


řx (M, yM −1 , yM )

yM =1

ここで，式
（4.20）の形に着目すると，右側（m = M ）から左側（m = 1）に向かって，řx (m, i, j) の和を求め，その値を左側に伝播させながら，和の計算を進めればよいことが分かる．
（m = M ）に至る
この計算過程を図示したのが図 4 である．あるノード (m, i) の右側から終端
経路上のエッジにある řx (m, i, j) の積を計算し，全ての経路で和を取ったものを βx (m, i) と定義すると，以下の漸化式が成り立つ．
⎧⎪(m = M のとき)⎪
⎨1
L
(4.21)βx (m, i) = ⎪řx (m, i, j)βx (m + 1, j) (m < M のとき)
⎪
⎩
j=1

統計数理

196

第 64 巻

第 2 号 2016

この漸化式で各ノードの βx (m, i) の値を求めたものを，ノードの下側に緑色で示した．式（4.20）との対比により，分配関数は次式で求まることが分かる．
Z(x) = βx (0, BOS)

(4.22)

一方，式（4.19）を展開するとき，m = M から括り出すと，次のようになる．
Z(x) =LLřx (M, yM −1 , yM )yM =1 yM −1 =1

LyM −2 =1...

Lřx (1, y0 , y1 )y1 =1

ここで，左端（m = 1）からノード (m, j) に至る経路上にあるエッジの řx (m, i, j) の積を計算し，全ての経路で和を取ったものを αx (m, j) と定義すると，以下の漸化式が得られる．
⎧⎪⎪(m = 1 のとき)
⎨řx (1, BOS, j)L
αx (m, j) = (4.23)⎪řx (m, i, j)αx (m − 1, i) (1 < m のとき)⎪⎩
i=1

この漸化式で各ノードの αx (m, i) の値を求めたものを，ノードの上側に青色で示した．式（4.20）との対比により，分配関数は次式で求めることもできる．
(4.24)

Z(x) =L

αx (M, i)i=1

分配関数の値を求めるだけであれば，αx (m, i) と βx (m, i) のどちらを用いてもよい．ただ，次節で説明する周辺確率の計算には，これらの両方の値が必要になる．このように，αx (m, i),βx (m, i) の値を求めるアルゴリズムのことを，前向き・後ろ向きアルゴリズムと呼ぶ．
4.4 素性関数のモデルにおける発火の期待値の計算方法を説明する．式（4.11）を用い，大域素性ベクトルを局所素性ベク
最後に，式（4.7）
は以下のように変形できる．
トルに変換すると，式（4.7）
∂l(x, y)= fk (x, y) −p(y  |x)fk (x, y  )
∂λk

y ∈Y


M


(4.25)p(i, j|x, m)πk (xm , i, j)=
πk (xm , ym−1 , ym ) −m=1i∈Y j∈Y

ここで，p(i, j|x, m) は，与えられた入力系列 x に対して，現在のモデルで出力の系列を予測したとき，時刻 m − 1 のラベルが i で，時刻 m のラベルが j と予測される確率（周辺確率）を表す．
したがって，任意の m, i, j に関して，p(i, j|x, m) が計算できればよい．
（m = 1）からノード (m, i) に至る経路のスコアの和，βx (m, i) がノー
ここで，αx (m, i) が左端（m = M ）に至るスコアの和であることを利用すると，p(i, j|x, m) を次式で求ド (m, i) から右端
めることができる．
(4.26)(m − 1, i)—(m, j) を通過する全経路のスコアの和Z(x)αx (m − 1, i)řx (m − 1, i, j)βx (m, j)=Z(x)p(i, j|x, m) =ゆえに，4.3 節で分配関数を計算する時に用いた αx (m, i) および βx (m, i) の値を保存しておけ
ば，周辺確率 p(i, j|x, m) の値を簡単に求めることができる．

条件付き確率場の理論と実践

197

4.5 その他の研究動向
2001 年の登場以降，条件付き確率場は様々な言語処理タスクに適用されてきた．典型例として，浅い句構造解析（Sha and Pereira, 2003），固有表現抽出（McCallum and Li, 2003），形態素解析（Kudo et al., 2004），情報抽出（Sarawagi and Cohen, 2005），構文解析（Finkel et al.,
，ゾーニング（Hirohata et al., 2008）などがある．条件付き確率場を実装したツールとし
2008）て，CRF++ 1) , CRFsuite 2) , Wapiti 3) などが有名である．
高性能の系列予測器を作るには，大量の訓練データを用意しなければならない．そこで，条件付き確率場の理論をうまく利用して，訓練データの構築を支援する研究もある．坪井ら（Tsuboi
et al., 2008）
は，入力系列の一部のみに正解ラベルを付与した訓練データや，正解を一つに絞り込むことができずに複数の正解ラベルが付与された訓練データから，重みベクトルを学習する手法を提案した．本手法は後に中国語の単語分割に適用され（Liu et al., 2014），CRFsuite のソースコードをベースにした実装が公開されている4) ．
Settles and Craven（2008）
は，少量の訓練データと正解が付与されていない大量の事例がある
とき，どの事例に正解を付与すべきかを示唆する能動学習（active learning）の戦略を比較・検討した．この研究では，少量の訓練データで学習したモデルを使い，正解が付与されていない事例の入力 x に対してラベル列 ŷ を予測し，予測されたラベル列の確率推定値 p(ŷ|x) が低い事例の正，ラベルの周辺確率から計算されるラベル列のエントロピーの解を付与したり（least conﬁdence）
高い事例に対して正解を付与する戦略（token entropy）などを検討している．CRFsuite では，予測されたラベル列の確率は-p, --probability オプションで，予測されたラベル列の周辺確率は-i, --marginal オプションで得ることができる．また，CRFsuite の API（Tagger::marginal）
を呼び出すことで，全てのラベルに関する周辺確率を計算できる．これらを活用することで，Settles らが比較・検討した能動学習の戦略を実装できる．
本稿では，ラベルに関する 1 次マルコフ性を仮定し，隣り合うラベルの依存関係を考慮した．
しかし，言語のデータを扱っていると，2 単語先や 3 単語先など，距離が離れたラベルの依存や関係をモデル化したくなることがある．最も単純な解決策は，2 次（連続する 3 個のラベル）
3次（連続する 4 個のラベル）など，2 次以上のマルコフ性を仮定した素性関数を導入することである．ただ，素性の次数を l とすると，ビタビ・アルゴリズムや前向き・後ろ向き・アルゴ
リズムの計算量は |Y|l+1 であるため，次数を上げると計算量が急増してしまう．代わりに，連続する複数のラベルをひと塊として扱うセミ・マルコフ条件付き確率場（Sarawagi and Cohen,が提案されている．また，入力列から出力列を予測するまでの間に，潜在変数のラベル列
2005）を導入することで，離れた距離の依存関係をモデル化しようとする研究もある（Morency et al.,（Sun et al., 2008）．なお，CRFsuite の実装を拡張して，高次のマルコフ性，セミ・マル
2007）
コフ性，木構造予測などを実現した実装5) も公開されている．
や Long Short-Term Memory（LSTM）などの深層
最近では，Recurrent Neural Network（RNN）
ニューラルネットワークに条件付き確率場のアイディアを導入し，品詞タグ付けや固有表現抽出を実現した研究も報告されている（Zhou and Xu, 2015）（Lample et al., 2016）．これらの研究は，潜在変数のラベル列の代わりに中間層の分散表現を用いるとともに，LSTM の記憶セルなどで離れた距離の依存関係をモデル化している．また，深層ニューラルネットワークに基づ
く条件付き確率場では，タスクに依存した素性関数を人間が設計しなくても，文字や単語の分散表現を学習することにより，特徴抽出を自動化できる．実際，Lample et al.（2016）は文字に関する素性や辞書などの外部知識を用いずに，深層ニューラルネットワークだけで獲得した素性を用いて，固有表現抽出の最高性能を達成できることを報告した．

統計数理

198

5.

第 64 巻

第 2 号 2016

おわりに

本稿では，系列データにおける条件付き確率場の理論と実践を解説した．条件付き確率場は，
多クラスロジスティック回帰に基づいているため，これらの理論や学習方法を復習した．また，
ラベル列のマルコフ性を仮定した素性関数と，ビタビ・アルゴリズムや前向き・後ろ向き・アル
ゴリズムなどの動的計画法でラベル列の予測とパラメータの学習を効率化する方法を詳説した．
注．
1)

https://taku910.github.io/crfpp/
http://www.chokkan.org/software/crfsuite/3)
https://wapiti.limsi.fr/
4)
https://github.com/ExpResults/partial-crfsuite
5)
https://github.com/WladimirSidorenko/CRFSuite
2)

参

考

文

献

Berger, A., Pietra, S. D. and Pietra, V. D. (1996). A maximum entropy approach to natural language
processing, Computational Linguestics, 22(1), 39–71.
Duchi, J. and Singer, Y. (2009). Eﬃcient online and batch learning using forward backward splitting,
Journal of Machine Learning Research, 10, 2899–2934.
Finkel, J. R., Kleeman, A. and Manning, C. D. (2008). Eﬃcient, feature-based, conditional random
ﬁeld parsing, Proceedings of ACL-08 : HLT, 959–967.
Hirohata, K., Okazaki, N., Ananiadou, S. and Ishizuka, M. (2008). Identifying sections in scientiﬁc abstracts using conditional random ﬁelds, Proceedings of the Third International Joint Conference
on Natural Language Processing (IJCNLP 2008 ): Volume-I, 381–388.
Kudo, T., Yamamoto, K. and Matsumoto, Y. (2004). Applying conditional random ﬁelds to Japanesemorphological analysis, Proceedings of EMNLP 2004, 230–237.
Laﬀerty, J. D., McCallum, A. and Pereira, F. C. N. (2001). Conditional random ﬁelds: Probabilistic
models for segmenting and labeling sequence data, Proceedings of the Eighteenth International
Conference on Machine Learning (ICML 2001 ), 282–289.
Lample, G., Ballesteros, M., Subramanian, S., Kawakami, K. and Dyer, C. (2016). Neural architectures for named entity recognition, Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies(NAACL-HLT 2016 ), 260–270.
Liu, Y., Zhang, Y., Che, W., Liu, T. and Wu, F. (2014). Domain adaptation for CRF-based Chinese
word segmentation using free annotations, Proceedings of the 2014 Conference on Empirical
Methods in Natural Language Processing (EMNLP ), 864–874.
McCallum, A. and Li, W. (2003). Early results for named entity recognition with conditional randomﬁelds, feature induction and web-enhanced lexicons, Proceedings of the Seventh Conference on
Natural Language Learning at HLT-NAACL 2003, 188–191.
Morency, L.-P., Quattoni, A. and Darrell, T. (2007). Latent-dynamic discriminative models for continuous gesture recognition, Proceedings of the 2007 IEEE Conference on Computer Vision and
Pattern Recognition (CVPR ’07 ), 1–8.
Sarawagi, S. and Cohen, W. W. (2005). Semi-markov conditional random ﬁelds for information extraction, Advances in Neural Information Processing Systems 17 (NIPS 2005 ), 1185–1192.
Settles, B. and Craven, M. (2008). An analysis of active learning strategies for sequence labeling tasks,条件付き確率場の理論と実践

199

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing,1070–1079.
Sha, F. and Pereira, F. (2003). Shallow parsing with conditional random ﬁelds, Proceedings of the 2003
Human Language Technology Conference of the North American Chapter of the Association
for Computational Linguistics, 134–141.
Sun, X., Morency, L.-P., Okanohara, D., Tsuruoka, Y. and Tsujii, J. (2008). Modeling latent-dynamic
in shallow parsing: A latent conditional model with improved inference, Proceedings of the 22ndInternational Conference on Computational Linguistics (Coling 2008 ), 841–848.
Tsuboi, Y., Kashima, H., Mori, S., Oda, H. and Matsumoto, Y. (2008). Training conditional randomﬁelds using incomplete annotations, Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008 ), 897–904.
Zhou, J. and Xu, W. (2015). End-to-end learning of semantic role labeling using recurrent neuralnetworks, Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (ACLIJCNLP 2015 ) (Volume 1 : Long Papers), 1127–1137.

200

Proceedings of the Institute of Statistical Mathematics Vol. 64, No. 2, 179–200 (2016)

Theory and Practice of Conditional Random Fields
Naoaki Okazaki
Graduate School of Information Sciences, Tohoku University

Most tasks of Natural Language Processing are formalized as a prediction problem ofan output for a given input. Assuming that an input and output have a structure such asa sequence and tree, which is a natural assumption for a language, we can formalize moretasks as the prediction problem. This paper explains Conditional Random Fields (CRF)
where an input and output are in the form of a sequence. In order to apply the multi-classlogistic regression to the sequential labeling problem, CRF introduces feature functions
that assume the Markov property for a label sequence and facilitates an eﬃcient inference
and parameter estimation by using dynamic programming. Therefore, this paper reviews
the fundamental theories of logistic regression, feature functions, training with stochastic
gradient descent, regularization, etc., and describes the overall theory of CRF. In addition,
it covers recent research topics and practices including active learning for CRF, learningfrom partially-annotated supervision data, and models with deep neural networks.

Key words: Conditional Random Fields, logistic regression, stochastic gradient descent.