言語処理における識別モデルの発展-- HMMからCRFまで --坪井祐太, 鹿島久嗣 （IBM Research）
工藤 拓 (Google)

Tokyo Research Laboratory

今日話した内容
HMMの話
復号(Viterbi)
内積で書けるよ
内積で書ける別のモデル CRF, HM Perceptron, HM SVM
違いはパラメータ推定法
Generative Model
HMM
HMM課題
Discriminative Modelのメリット：直接P(Y|X), 素性間の重なりを考慮できる
Conditional Model
CRF
Discriminative Model
HM Perceptron
メリット：
Generative Model vs Discriminative のまとめた表
形態素解析の例

Tokyo Research Laboratory

チュートリアルの流れ
構造のラベル付け問題の定義
２つのアプローチ： 生成モデル vs. 識別モデル– 生成モデル： 隠れマルコフモデル– 識別モデル： 条件付確率場

そのほかの識別モデル
計算機実験による性能比較

Tokyo Research Laboratory

構造ラベル付与問題とは？
観測されたデータ構造xに対応するラベル構造yへの写像を学習する問題
列構造
x1x2x3

観測変数x4x4x2x1x3

y2

y1y3y4

木構造

y4

ラベル変数

y2y1y3構造を持つ観測データの各ノードにラベルを付与する問題として捉えることが出来る応用が多く存在する。
– 例：自然言語処理、バイオインフォマティックス

Tokyo Research Laboratory

自然言語処理での構造ラベル付与問題の例（列構造）
品詞タグ付与タスク
単語列に対して品詞ラベルを付与するタスク
y 冠詞 名詞 動詞x

The man saw

冠詞名詞agirl

固有表現抽出タスク
人名・組織名等の固有表現をテキスト中から抽出
単語列に対して固有表現の始まり(B-XXX) と続く固有表
現(I-XXX) を示すラベルを付与するタスク（O は固有表現
y B-場所 O B-組織 I-組織OO以外）
x 日本で小泉内閣が発足しOた

Tokyo Research Laboratory

自然言語処理での構造ラベル付与問題の例（木構造）
係り受け木に対する固有表現抽出タスク– 係り受け解析によって生成された単語間の関係を表す係り受け木に対して、ラベルを付与。
– 主語と述語の関係など言語構造を考慮したラベル付与

で日本

たO

発足しOがO

内閣
小泉

B-場所 I-組織
B-組織O

Tokyo Research Laboratory

教師付き学習による構造ラベル付与問題
学習データ（ 正しいx,yペア）
パラメータ推定
（学習）

y(1)

モデル
(写像)

x(1)
y(2)

復号
（予測）

x(2)
y(3)

y

x(3)

x?

?

?

?

…

ラベル無しデータTokyo Research Laboratory

構造ラベル付与学習モデル

生成モデルに基づく手法–隠れマルコフモデル(HMM)

識別モデルに基づく手法–条件付確率場(CRF)Tokyo Research Laboratory

生成モデルによる構造ラベル付与学習

隠れマルコフモデル(HMM)
xとyの同時分布に基づくモデル

y

冠詞

動詞

冠詞名詞x

The man sawagirl

名詞

生成確率を出力確率と遷移確率に分解してモデル化

P( x, y )P( x | y ) P( y )T

P( xt|yt )P( yt | yt 1 )(Tは構造x, yのサイズ)

t 1

ytxt

出力確率
(各ノード間の独立性仮定)

yt-1

yt

遷移確率
(マルコフ性仮定)

Tokyo Research Laboratory

隠れマルコフモデル(HMM):

全部で|Y|T個

ラベル列の予測（復号問題)
predict

yargmaxP(x | y ) argmaxP( x, y )yyT→ありうるラベル列全て(|Y|T個)の列挙は非効率（ |Y| は目的ラベル集合のサイズ）

冠詞

冠詞冠詞)
The man saw

agirl

冠詞

名詞

…

t 1

あるxが与えられたときに、確率が最大になるラベル列yを見つけたい。

冠詞

P(P( xt|yt )P( yt | yt 1 )argmaxy

冠詞

冠詞

名詞動詞P()The man sawagirl

動詞

動詞

…
動詞

動詞

動詞

P()
The man sawagirl

Tokyo Research Laboratory

隠れマルコフモデル(HMM):

Viterbi 復号法による最適ラベル列の求め方
位置tまでのラベル列の確率が最大になる値を記憶するテーブルδ
を使い再計算を避けることで、最適なラベル列を効率的に計算( y)P( x1 | y )t ( y)~~max(y)P(x|y)
P(y|y)
t 1t~

1yx

冠詞
名詞
動詞y YtheP( the | 冠詞)P( the | 名詞)
P( the | 動詞)

英語品詞タグ付けタスクでのδmansaw…

~max(y)1~y Y~max(y)2~…

P(man | 冠詞) P(冠詞 | ~y)max ( ~y)P(saw | 冠詞) P(冠詞 | ~y)max ( ~y)…

P(man | 名詞) P(名詞 | ~y)~max
1( y )~P(saw | 名詞) P(名詞 | ~y)
~max
2(y)
…
~y Y
P(saw | 動詞) P(動詞 | ~y)

~y Y

1y Y

P(man | 動詞) P(動詞 | ~y)y Y~y Y2

Tokyo Research Laboratory

隠れマルコフモデル(HMM):

Viterbi 復号法によるσｔの計算例
δｔを最大にするyt-1からytへの遷移（矢印）が決まった時のδの例（英語品詞タグ付け）
xthemansaw…

y
冠詞

P ( the | 冠詞)P( the | 動詞)

P( the | 名詞)

P(man | 冠詞) P(冠詞 | 動詞)

P(man | 動詞) P(動詞 | 名詞)…

P(saw | 冠詞) P(冠詞 | 動詞)

名詞

P( the | 名詞)

P( the | 冠詞)P(man | 名詞) P(名詞 | 冠詞)P( the | 名詞)
P(man | 動詞) P(動詞 | 名詞)P(saw | 名詞) P(名詞 | 動詞)
P( the | 冠詞)

動詞
P( the | 動詞)…

P( the | 名詞)

P(man | 名詞) P(名詞 | 冠詞)P(man | 動詞) P(動詞 | 名詞)P(saw | 動詞) P(動詞 | 名詞)…

Tokyo Research Laboratory

隠れマルコフモデル(HMM):

テーブルπを用いた最適ラベル列の求め方（Viterbi 復号法)
位置tまでのラベル列の確率が最大になる位置t-1のラベルを記憶する
テーブルπ も同時に計算
末端(T)において確率(δT(y))が最大になるyのπT(ｙ)からバックトラッ
クすることで、確率が最大になるラベル列を得ることができる。

~~(y)argmax(y)P(x|y)
P(y|y)
tt 1
t~yy xtheymansaw…

冠詞π2(冠詞)=動詞π3(冠詞)=動詞…

名詞

π2(名詞)=冠詞

π3(名詞)=動詞…

動詞

π2(動詞)=名詞

π3(動詞)=名詞…

Tokyo Research Laboratory

隠れマルコフモデルのパラメタ推定（学習）パラメータθ
– 出力確率 P(xt|yt)– 遷移確率 P(yt|yt-1)

最尤推定θˆ argmaxθPθ ( x ( i ) , y ( i ) )iT (i )

argmaxθ（iは学習データの索引）

i(i )P ( xt | yt( i ) ) P ( yt( i ) | yt( i )1 )t

最尤なパラメータは共起頻度のカウントで計算可能

Tokyo Research Laboratory

生成モデルの課題点同時分布の推定をすることで、間接的に分類問題を解いている。(P(x)を余分に推定している)
predict

yargmaxP( y | x) argmaxP( x, y )yy

同時分布を推定する十分なデータを得るのは難しいため、変数間の独立性を仮定することが多い。
predictyTargmaxyP( xt|yt )P( yt | yt 1 )t 1→相互作用のある観測変数（素性）をうまく扱えない(HMM)

Tokyo Research Laboratory

相互作用のある素性の例
自然言語処理では単語それ自身以外に、単語の部分文字列等が素性に使われることが多い
品詞タグ付け– P(beautiful|形容詞),
P(fulで終わる単語|形容詞)

are

IBM Google– P(beで始まる単語|形容詞)

ask

New

– P(immediately|副詞),
P(lyで終わる単語|副詞)

York

固有表現抽出– P(3文字の単語 | B-組織), P(最初が大文字の単語 |B-組織)– P(小泉|B-人名), P(漢字だけからなる単語| B-人名)

足して1にならないといけないのになってないTokyo Research Laboratory

識別モデル
xからyを直接推定するモデル
識別モデルの利点– 直接分類問題を解くことが出来る– 素性間の重なりを考慮して重みを学習
多クラスのロジスティック回帰モデル（最大エントロピーモデル)– 確率分布の形をした識別モデル– 条件付分布を直接モデル化

P( y | x)
内積だよexp( θ, Φ(x, y ) )exp( θ, Φ(x, ~y) )~y Y(Φはx,yの素性、θは素性に対する重み)Tokyo Research Laboratory

復号は一緒Tokyo Research Laboratory

識別モデルのパラメータ推定（学習）最尤推定θˆ arg max
θPθ ( y (i ) | x ( i ) )i trainingdata

arg max
θi trainingdata

exp( θ, Φ(x (i ) , y (i ) ) )exp( θ, Φ(x ( i ) , ~y) )~y Yパラメータの計算– 素性間の相互作用を考慮してパラメータ推定をする必要があり、計算手順が複雑– 損失関数の偏微分を用いて損失最小化問題を解く。

Tokyo Research Laboratory

識別モデルによる構造ラベル付与学習：

条件付確率場 (Conditional Random Fields: CRF)
ロジスティック回帰モデルを基に、ローカルな変数間の関係を素性(遷移素性)で表現したモデル

exp θ, (x, y )exp θ, (x, ~y)P( y | x)~yT

θ , (x, yexp).y 11Tθ , ( x, ~y 1)

exp
~y1

1

( y , y 1)

(Φはx,yの素性、θは素性に対する重み)Tokyo Research Laboratory

条件付確率場の素性
素性ベクトルの各要素は、素性が構造中に出現した頻度– 観測素性:観測変数とラベル変数のペア– 遷移素性：ラベル変数のペア

冠詞#( The )=1x

冠詞

名詞

動詞

The man saw

冠詞a名詞girl)…

Φ(y観測素性#(冠詞名詞)=2

遷移素性

…
冠詞

名詞が出現した頻度

Tokyo Research Laboratory

その他の識別モデル： 分類手法に基づくアプローチ
CRFのパラメタ推定の別アプローチ– 分類手法（パーセプトロン, SVM, …）にもとづいたアプローチ

何がうれしいか？→ 通常のアプローチでは解けない問題に適用できる

Tokyo Research Laboratory

そのほかの識別モデル： 隠れマルコフパーセプトロン(i )y
CRFの推定は、訓練データのが出力される確率を「最大にする」ように学習される

θˆ arg maxθPθ ( y (i ) | x ( i ) )i trainingdata

別の考え方： 訓練データの y が出力される確率が、(i )(i )~yy「ほかのの出力確率よりも大きければよい」(i )log Pθ ( y (i ) | x ( i ) ) log Pθ ( ~y (i ) | x ( i ) )θ, Φ ( x ( i ) , y ( i ) )θ, Φ(x (i ) , ~y (i ) )0Tokyo Research Laboratory

隠れマルコフパーセプトロンのアルゴリズム
1. i 番目の訓練データに対して予測してみる
predict(i )yargmax P( y | x ( i ) )ypredict(i )

2. 当たっていれば（ yy (i ) ）何もしない

3. 外れていたら、パラメータを修正θ newθ old

4. 1.に戻って繰り返すΦ( x ( i ) , y ( i ) ) Φ( x ( i ) , ~y (i ) )Tokyo Research Laboratory

最尤推定と隠れマルコフパーセプトロンの違いは、argmax操作のみで実現できるところ
隠れマルコフパーセプトロンは訓練と予測が両方argmax操作
CRF

隠れマルコフパーセプトロン

訓練ΣΠargmax予測

argmaxargmax

通常、argmaxもΣΠも動的計画法で実現できるのであまり変わりはない…しかし…

Tokyo Research Laboratory

隠れマルコフパーセプトロンは、最尤推定では解けない問題が解ける？
問題によっては、argmax操作は、動的計画法以外の多項式時間アルゴリズムで実現できる動的計画法で多項式時間で解けない問題は、最尤推定では解けない– たとえば、異なる言語の文章間での単語のマッチング• argmax操作が線形計画法（多項式時間）で解ける

図引用：
Dan Klein and Ben
Tasker, “Max-Margin
Methods for NLP:
Estimation, Structure,and Applications”,
ACL 2005 Tutorial より

Tokyo Research Laboratory

End of the Presentation

Tokyo Research Laboratory

Reference
Dan Klein and Ben Tasker. Max-Margin Methods
for NLP: Estimation, Structure, and Applications.
ACL-05 Tutorial.
Dan Klein and Chris Manning. Maxent Models,Conditional Estimation, and Optimization, without
the Magic. ACL-03 Tutorial.

Tokyo Research Laboratory

Gradient of Point-wise Log-Loss
LT (i )

θi trainingdatat) )y yt yt( i )

) (i)
(i) )
P(y | x )Φ(x , y )) )y yt yt( i )))P(y | x (i) )Φ(x (i) , y ))P(y | x (i) )) )y yt yt( i )(y( (i)P(y | x )(y Y((P(y | x (i) )Φ(x, y ))Φ( x , y )
(i)

yt-1’

yt’

yt+1’

yt-1(i)yt(i)yt+1(i)yt-t’’yt’’’

yt+t’’

Tokyo Research Laboratory

Classification of Structured Output (e.g. HMMs, CRFs)
Viterbi Decoding
Finding the most probable label sequence.
Avoids re-calculation

Tokyo Research Laboratory

Parameter Estimation of Structured Output (CRFs)
logP(Y | X)
iexp( θ, φ( X, Y ) )log~exp( θ, φ( X, Y ) )i~
Y Yθ, φ( X, Y )i~exp( θ, φ( X, Y ) )log~Y Y

Tokyo Research Laboratory

Structured Output Learning (e.g. POS tagging, NER, Parsing)
X 1 , Y1
X 2 , Y1...
X 1 , Y2
X 2 , Y2...
X m , Yl

Vector input

X 1 , Y1
X 2 , Y1...
X 1 , Y2
X 2 , Y2

Vector input

Multi label output
Classifier

yLabel Sequence output
Classifier

y1y2y3y4...
X m , Yl

Sequence input
X1X2X3X4Label Tree output
Classifiery4y2y1y3

Tokyo Research Laboratory

Structured Output Learning
In general, structured output problem is one ofmulti label problems.
In practice, all the labels are not enumerable andsparse in training data.
POS tag Sequence
Word Sequence

DT DT DT DT DT
DT DT DT DT CC

The man saw a girl…
DT NN VBD DT NN…
RB RB RB RB RB# of possiblelabel assignmentis large (|Y|T)

Tokyo Research Laboratory

冠詞

冠詞

冠詞

冠詞

冠詞

名詞

名詞

名詞

名詞

名詞

動詞

動詞

動詞

動詞

動詞

Themansawagirl

Tokyo Research Laboratory

条件付確率場(CRF)：識別モデルによる構造ラベル付与学習
Dynamic Programming (Belief Propagation) algorithm– solves graphical inference problems via a series of local messagepassing operations.
– a label depends only its neighborhood labels (Markov assumption)– reuses previous calculation to avoid re-calculation
y1

y2

y3

y4

When we decide y4, we only see the decision of y3.
Transition features– represent structural label consistency

Tokyo Research Laboratory

Machine Learning on Structured dataP(y | x)exp( θ, Φ(x, y ) ),~exp( θ, Φ(x, y ) )~y YTokyo Research Laboratory

Dynamic Programming

P(Y | X)

exp( θ, Φ( X, Y ) )~exp( θ, Φ( X, Y ) )~Y Y

reuses previous calculation to avoid re-calculation
計算したい値– 存在しうる全てのLabel Pathのスコアの和– あるポジションtにある素性が出てくるLabel Pathのスコアの和
DT

DT

DT

DT

DT

NN

NN

NN

NN

NN

…

…

…

…

…

RB

RB

RB

RB

RB

sawagirl

The man~exp( θ, Φ( X, Y ) )~Y YTokyo Research Laboratory

分類問題で使われる生成モデル (例： Naïve Bayes)
ベイズの法則ベイズ分類器predictyargmaxP( y | x) argmaxP( x | y ) P( y )yy(xは観測変数ベクトル、yはラベル変数)– 結合分布

P( x | y )yP( x1 , x2 ,..., xm | y )x1,x2,...,xm– ナイーブ分布(結合条件付分布を緩め、観測変数間の独立性を仮定)

y| x|

P( x | y )P( x j | y )j(|x|はベクトルのサイズ)

x1x2… xm

Tokyo Research Laboratory

テーブルπを用いた最適ラベル列の求め方（Viterbi 復号法)
位置tまでのラベル列の確率が最大になる位置t-1のラベルを記憶する
テーブルπ も同時に計算
末端(T)において確率(σT(y))が最大になるyのπT(ｙ)からバックトラッ
クすることで、確率が最大になるラベル列を得ることができる。

~~(y)argmax(y)P(x|y)
P(y|y)
tt 1t~yy xtheymansaw…

冠詞

π2(冠詞)=動詞π3(冠詞)=動詞…

名詞

π2(名詞)=冠詞π3(名詞)=動詞…

動詞π2(動詞)=名詞

π3(動詞)=名詞…

Tokyo Research Laboratory

Another interpretation of HMM–Log likelihood can be written as
the inner product of weight vector w & feature vectorDT

NN VBD NN

log Pr ()the man saw glassesDT

log Pr (weight vector(model parameters)DT)#(feature vector(labeled sequence)theNN

log Pr (theNN)#(man
VBD NNlog Pr ()#()
Number of times

NNman
VBD NN…

…

VBD)

appearing)Tokyo Research Laboratory

識別モデルによる構造ラベル付与学習：

条件付確率場 (Conditional Random Fields: CRF)
Sequence input
x1x2x3

最大エントロピーモデルで素性はこんなx4

ローカルな変数間の関係を素性で表現

Feature Vector
xtaytya

xtxa

yty1X

xm Yyl

Yt

ya

Ya

tt...
t

Yt 1t...
Yttyl

Yt 1 Yl}}y

観測素性

Label Sequence output

xCRF
遷移素性
yt

yt+1

y1y2

y3y4

Tokyo Research Laboratory

生成モデルと識別モデルの素性の重みの違い
学習データ
Ay BB

B

BB

B

AB

B

xβββββγββ

1/2 0/2 1/20/88/80/8βα

パラメータ推定HMMの重み(1/2以上を青、1/2未満を赤）

0/2A2/2A-2.2

A2/8
B

2.3

B

6/8
A

1.9

B-2.1A

A

A

B

B

B

αβγαβγB

6.0 -13.4 6.0 -6.0 13.4 -6.0

CRFの重み(プラスを青、マイナスを赤） → 識別に影響が少ない B

Bの重みが低いTokyo Research Laboratory

Tokyo Research Laboratory

生成モデルと識別モデル
B

A

B

B

B

B

B

bba

B

babba

B

B

A

B

B

9/10*6/8*9/10*6/8*1/10？

？

=2916/64000？

=0.4556

bbcbbbba
B

B

Abba

HMM
A

A0/2AA

B

B

A

B

2/2B

B

6/8B

A

2/8 1/2 1/2 1/10 9/109/10*6/8*9/10*2/8*1/2=972/12800

acab=0.0759

Tokyo Research Laboratory# weights for observation
A-a:5.96

A-b:-13.41

A-c:5.96

B-a:-5.96

B-b:13.41

B-c:-5.96# weights for transition
A-A:-2.14 A-B:2.28
B-A:1.91

B-B:-2.05

Tokyo Research Laboratory

Y-X– A-a:6.09 A-b:-20.67– B-a:-6.09 B-b:20.67

Y-Y– A-A:-3.69 A-B:10.08– B-A:-2.45 B-B:-3.93