Burr Settles and Mark Craven
In EMNLP 2008, pages 1069-1078
読み手: 岡崎直観(東大・辻井研)

系列ラベリングとして定式化されるタスクに,種々の
能動学習(active learning)戦略を適用
◦ 試した能動学習戦略は全部で15種類
 Expected Gradient Length (EGL) と Information Density (ID)
は著者らの提案手法
 能動学習を概観するカタログとしても有用
◦ 評価に用いたコーパスは全部で8種類
 Information Density (ID) とSequence Vote Entropy (SVE) の
性能が良さそうだが,突出して優れている手法は無かった

論文の著者はバイオNLPの研究者
◦ A Biomedical Named Entity Recognizer (ABNER) は有名
◦ EGLは2007年のNIPSで発表している

能動学習
◦ データ中のどのサンプルから学習を行うか,学習器自体がコント
ロールできる枠組み
◦ 本研究では,学習器は少ない訓練例L を基に,ラベル付けされて
いないサンプル集合U から,ある戦略(基準)に基づいて,学習
に有用と思われる事例(クエリ事例)を選ぶ
ラベル付け
学習
選択
スパムメール
の学習データ
分類器
大量のメール
(スパムかどう
かは不明)

系列ラベリングに能動学習を適用する先行研究
◦ Uncertainty sampling (Scheffer et al., CAIDA-2001;
Culotta and McCallum, AAAI-2005; Kim et al., HLTNAACL-2006)
◦ Query-by-committee (Dagan and Engelson, ICML-1995)

これらの従来研究は,外れ値(outliers)に弱いと言
われている (Roy and McCallum, ICML-2001; Zhu
et al., ICML-2003WS)
◦ 本論文は,ラベル付けされていないサンプル集合の分布を考
慮した能動学習戦略を提案する

種々のコーパスを用い,能動学習の先行研究や提案手
法を比較・解析する

Uncertainty sampling
◦ Least Confidence (LC); Margin (M)
◦ Token Entropy (TE); Total Token Entropy (TTE)
◦ Sequence Entropy (SE); N-best Sequence Entropy (NSE)

Query-by-committee (QBC)
◦
◦
◦
◦

Vote Entropy (VE); Total Vote Entropy (TVE)
Kullback-Leibler (KL); Total Kullback-Leibler (TKL)
Sequence Vote Entropy (SVE)
Sequence Kullback-Leibler (SKL)
その他
◦ Expected Gradient Length (EGL)
◦ Information Density (ID)
◦ Fisher Information Ratio (FIR)

定式化 (Lafferty et al., ICML-2001)
◦ x = x1, …, xT: 入力トークン系列
◦ y = y1, …, yT: 出力ラベル系列
P ( y | x) 
1


exp  k f k ( yt 1 , yt , xt ) 
Z ( x)
 t 1 k 1

T
素性の重み
K
素性関数
◦ 本研究では線形連鎖CRFを例に取り上げる

事後確率最大化によるパラメータ推定
 k2
l (L )   log P ( y | x )   2
l 1
k 1 2
L
K
(l )
(l )
Brown
promises
0.4
0.4
0.3
.2000
NN
NN
.1500
JJ
0.2
0.5
0.2
0.1
t=0
t=1
NN
0.6
JJ
0.2
0.1
0.1
0.1
.0030
.0200
VB
.0080
0.2
0.4
0.1
0.5
BOS
0.3
.0360
0.4
0.3
0.4
0.6
0.5
1
change
0.2
0.5
0.5
.0008
JJ
0.1
t=2
0.1
.0016
EOS
0.2
0.1
.0400
VB
0.1
0.2
0.5
.0072
0.1
VB
max operation
t=3
t=4
Brown
promises
0.4
0.4
0.3
.2000
NN
.0188
NN
.0070
.1500
JJ
0.1
0.2
0.6
0.2
0.1
.0054
JJ
0.2
0.1
.0200
VB
.0168
t=0
t=1
0.1
0.1
0.2
0.2
JJ
0.1
.0520
t=2
.0070
EOS
1
0.2
0.1
.0485
VB
0.1
.1000
0.5
0.5
(= Z)
0.1
.0017
.0600
0.5
NN
0.4
.0194
(= Z)
.0187
.2000
0.6
0.5
BOS
0.3
.0640
0.4
0.3
0.4
.0650
0.5
1
change
0.2
0.5
.0155
0.1
VB
.2000
t=3
t=4
P ( yt  i ) 
 t (i )  t (i )
Z
P ( yt  j | yt 1  i ) 
Brown
 t 1 (i )et 1 ( j | i )vt ( j )  t ( j )
Z
promises
0.4
0.4
0.3
.2000
NN
.0188
NN
.0070
.1500
JJ
NN
0.6
0.2
0.4
0.1
0.2
0.1
0.1
.0054
JJ
.0194
0.2
0.2
JJ
0.5
.0520
t=2
.0070
EOS
1
0.2
0.1
.0485
VB
0.1
.1000
0.5
0.2
0.1
0.0640 0.0650
0.1
P( y1  NN) 
 0.5943
.0200
0.0070
VB
0.1
.0168
0.0485 0.0520
P( y1  VB ) 
 0.3603
0.0070
t=0
t=1
0.1500 0.6  0.4  0.0650
P( y2  NN | y1  JJ ) 
 0.3343
0.0070
0.2000 0.4  0.5  0.0520
P( y2  VB | y1  NN) 
 0.2971
0.0070
0.1
.0017
.0600
0.5
.0187
.2000
0.6
0.5
BOS
0.3
.0640
0.4
0.3
0.4
.0650
0.5
1
change
0.2
0.5
.0155
0.1
VB
.2000
t=3
t=4
ラベル付けをすべき
事例に高いスコアを
与える評価関数
人手でラベル付け
ラベル付けの確信度が
低い事例を選ぶ

現在のモデルが事例 x ∈U をビタビ・アルゴリズ
ムでラベル付けするとき,その確信度(確率推定
値)が低いものを選ぶ (Culotta and McCallum,
AAAI-2005)
 LC ( x)  1  P ( y* | x)
推定された確率
◦ CRFでは,条件付き確率は前向き・後ろ向きアルゴリズ
ムと,ビタビ・アルゴリズムで計算される

現在のモデルが事例 x ∈U をラベル付けするとき,
第1位と第2位のラベルの確信度の差が小さいも
のを選ぶ (Scheffer et al., CAIDA-2001)
 M ( x)  P ( y1* | x)  P ( y2* | x)
第1位の確率
第2位の確率
◦ 第2位の確率は,ビームサーチを用いたn-bestアルゴリ
ズムで求める (Schwartz and Chow, 1990)

現在のモデルが事例 x ∈U をラベル付けするとき,
各位置 t におけるラベル付け yt の曖昧さを,エン
トロピーで計る
x の長さ
ラベルの数
T M
1
 TE ( x )    P ( yt  m) log P ( yt  m)
T t 1 m1
位置 t のラベル y が m
トークンあたりのエ
ントロピーを求める
t
である確率(周辺確率)
◦ 周辺確率は前向き・後ろ向きアルゴリズムから求まる

Token entropy (TE) では,長い事例が過度に選
ばれないように,T に関して平均を取ったが,長
い事例は,そもそもラベル付けが難しい
(Baldridge and Osborne, EMNLP-2004; Hwa,
CL-2004)
 TTE ( x)  T  TE ( x)
平均を打ち消す
(平均を取らない)

Token entropy (TE) はトークンに関するエント
ロピーを計っているが,系列に関するエントロ
ピーを計った方がよいのではないか?
 ( x)   P ( y | x) log P ( y | x)  H x ( y)
SE
y
H x ( y)  H x ( y1...yT )
(前向き・後ろ向きアルゴ
リズムの適用後は,x に
依存しないと考えて良い)
(連鎖律)
 H x ( y1 )  H x ( y2 | y1 )  H x ( y3 | y1 y2 )  ... H x ( yT | y1...yT 1 )
(マルコフ性)
 H x ( y1 )  H x ( y2 | y1 )  H x ( y3 | y2 )  ...  H x ( yT | yT 1 )
◦ エッジの周辺確率が計算されていれば,系列全体の和を
取ることなく,条件付きエントロピーの和で計算できる

N-bestラベル付け系列に関するエントロピーを計
る (Kim et al., HLT-NAACL-2006)
 NSE ( x)    P ( y | x) log P ( y | x)
yYN*
*
N
Y
 y ,..., y 
*
1
*
N
◦ こちらは,単純にn-best系列に基づいてエントロピーを
計算する
複数の分類器を作り,ラベル付け
が一致するかどうか調べる

Query-by-committee (Seung et al., CoNLL-1992)
◦ C 個のモデル C = {θ(1), …, θ(C)} があるとき,これらのモデルが異
なるラベル付けを行う事例をアノテートする

Query-by-bagging (Abe and Mamitsuka, ICML1998)
L 回サン
プリング
L
ラベル付き
データ
L
L (2)
θ(1)
(1)
…
L (C)
(サンプリングするときに重複
する事例を選んでも構わない)
θ(2)
学習
…
θ(C)
ラベル
付け
x ∈U
ラベル無し
データ
このラベル付けが
揺れるものを選ぶ

C 個のモデルが事例 x ∈U をラベル付けするとき,
各位置 t におけるラベル付け yt のばらつき具合を,
エントロピーで計る
ラベルの数
x の長さ
T M
V ( yt , m)
V ( yt , m)
1
VE
 (x )   
log
T t 1 m1 C
C
トークンあたりのエ
ントロピーを求める
位置 t のラ
ベル yt を m
と予測した
モデルの数
各モデルが位置 t のラベル yt
を m であると投票した確率
◦ 各モデルはビタビ・アルゴリズムでラベル付けを行う
 TVE ( x)  T  VE ( x)

C 個のモデルが事例 x ∈U をラベル付けするとき,各位
置 t におけるラベル付け yt のばらつき具合を,平均的
なラベル付けからのKLダイバージェンスで計る
T
C
1
1
KL
(c)
 ( x )    Dt ( || C )
T t 1 C c 1
Dt (
(c)
M
P ( c ) ( yt  m)
m 1
PC ( yt  m)
|| C )   P ( c ) ( yt  m) log
yt のラベル付けに関する
全モデルC と θ(c) の距離
1 C
PC ( yt  m)   P ( c ) ( yt  m)
C c 1
全モデルC が y を m と
t
ラベル付けする確率
位置 t におけるラベル付
けの,平均からのばらつ
き具合
 TKL ( x)  T  KL ( x)

C 個のモデルがそれぞれ,事例 x ∈U をn-best解
でラベル付けするとき,得られたラベル系列 y の
確率分布のばらつき具合(エントロピー)
 SVE ( x )    PC ( y | x ) log PC ( y | x )
yYNC
1 C
PC ( y | x )   P ( c ) ( y | x )
C c 1
C
YN   Y
C
c*
N
c 1
各モデルにn-best系列を
出力させ,その和集合を
とったもの
全モデルを使ったとき,
事例 x が y とラベル付
けされる確率

C 個のモデルがそれぞれ,事例 x ∈U をn-best解
でラベル付けするとき,得られたラベル系列 y の
確率分布のばらつき具合(KLダイバージェンス)
C
P ( c ) ( y | x )
1
SKL
 ( x )    P ( c ) ( y | x ) log
C c 1 yYNC
PC ( y | x )
1 C
PC ( y | x )   P ( c ) ( y | x )
C c 1
C
YN   Y
C
c*
N
c 1
各モデルにn-best系列を
出力させ,その和集合を
とったもの
全モデルを使ったとき,
事例 x が y とラベル付
けされる確率

現在のモデルが事例 x ∈U のラベル y を知ったとき,モ
デルを大きく修正する必要があるものを選ぶ (Settles
et al., NIPS-2008)
◦ 実際にはラベル y は未知なので,n-best解による期待値で近似

EGL
( x) 
 P ( y | x) l (L
 x, y
)
対数尤度の勾配
yYN*
l (L
 x, y
)  l (L )  l  x , y   l  x , y
尤度は対数尤度で,
各事例は独立
学習データに対す
る対数尤度は0に
なっているはず
◦ 勾配の計算には,CRFの学習の実装を再利用すればよい

○: ラベル無しサンプル
□: 正例
▲: 負例

ラベル無しサンプルAは分離境界面上にある
◦ ラベル付けの確信度が最も低いと考えられる

他のラベル無しサンプルの分布を見ると,Aより
もBをアノテートすべき
◦ Bの周辺にはラベル付けされた事例や,ラベル無しサン
プルがたくさん分布している

Sequence entropyを,中心性尺度で重み付け
1
 ( x)   ( x)  
U
ID
SE
sim( x , x ) 
(u )
xx

sim( x , x ) 

u 1

U
(u )
| x |  | x (u ) |

重み付けの重要度
(u )
x のU における中心性
KL距離やユークリッド距離
も試したが,コサイン距離
とほとんど変わらなかった
T
T

x   f1 ( x1 ),..., f K ( x1 )
t 1
 t 1

素性数 K を次元とするベクトル
系列中の各点の素性値の
和を x のベクトルとする

事例 x ∈U を学習データに加えたとき,対数尤
度の期待値ができるだけ大きくなる事例を選ぶ
(Zhang and Oles, ICML-2000)
◦ Cramer-Raoの不等式により,これはモデルのパラメー
タの分散をできるだけ下げることと等価


1
対数尤度の期待値
 ( x )   tr x ( ) 1 U ( )
2 Fisher information matrix
1 U
U ( )   x (u ) ( )
U u 1
FIR
2
( )ij   P( x ) P ( y | x )
log P ( y | x )
 i  j
x
y
2
x ( )ij    P ( y | x )
log P ( y | x )
 i  j
y
2
x ( )ii    P ( y | x ) 2 log P ( y | x )
 i
y
 


  P ( y | x )
log P ( y | x ) 
  i

y
対角要素のみで近似
(Nyffenegger et al.,
2006)
確率として正規化されてい
ることから導かれる定理
2
 

  P ( y | x )
log P ( y | x ) 
yYN*
  i

x に関するFisher
Information matrix
y をn-best解で近似
2

以下の式を最小化する
trx ( )1 U ( )
◦ x をn-best解でラベル付けしたとき,モデルの対数尤度
の θi に関する勾配は大きい方がよい
 モデルを大きく変更する可能性がある
◦ x をn-best解でラベル付けしたとき,モデルの対数尤度
の勾配は,すべてのラベル無しサンプルをn-best解でラ
ベル付けしたときの勾配に近い方がよい
 外れ値のラベル付けはしないほうがよい

CoNLL-03 (Sang and DeMeulder, 2003)

NLPBA (Kim et al., 2004)

BioCreative (Yeh et al., 2005)

FlySlip (Vlachos, 2007)

CORA (Peng and McCallum, 2004)

Sig+Reply (Carvalho and Cohen, 2004)

SigIE
◦ Newswire記事の固有表現抽出(PER, ORG, LOC, MISC)
◦ 生命・医学文献の固有表現抽出(protein, RNA, cell-type)
◦ 生命・医学文献の固有表現抽出(gene mention)
◦ 生命・医学文献の固有表現抽出(gene mention)
◦ 論文のヘッダーからタイトル,著者名,所属情報を抽出
◦ 論文の参考文献から,BibTeXのフィールドを抽出
◦ メールからシグニチャと引用を認識
◦ メールからアドレス帳の情報(名前,メール,電話番号)を抽出
※ラベルはすべてIOB表記

CRFの素性は平均的なもの
◦ 単語素性,綴り素性(文字種など),品詞,…

能動学習のベースライン
◦ ランダムにサンプルを選択する (Random)
◦ 系列が長いサンプルから選択する (Long)

実験設定
◦
◦
◦
◦
◦
N-best近似は N = 15
QBC手法におけるデータ分割数 C = 3
Information densityにおける重み付け β = 1
教師有りデータはランダムに選んだ5事例からスタート
1回の能動学習ループにおける追加事例数 B = 5

明確な勝者はなし

◦ Information density (ID) が良い
 Sequence entropy (SE) をほぼ改善
 大きいコーパスでは効果あり
◦ Sequence vote entropy (SVE) も
良さそう
◦ Uncertainty samplingでは,least
confidence (LC) と sequence
entropy (SE) が良さそう

トークンベースよりも系列
ベースの戦略のほうが良い
系列長の平均は要らない
◦ 長い系列は難しいと考えるべき

EGLやFIRは,理論的にはしっ
かりしているが,近似(Nbestや対角化)のためか,性
能があまり良くない

Uncertainty sampling戦略が一番速い
◦ トークンベースの戦略が系列ベースの戦略よりも若干速い

Query-by-committee (QBC) 戦略は,複数のモデル
を訓練しなければならないので,時間がかかる
◦ 5個のクエリを見つけるのに3~4分

EGLとFIRがもっとも遅い
◦ 1個のクエリを見つけるのに8~10分
◦ 素性の数 K に関して,処理時間が線形に増加してしまう

Information density (ID) ← 著者らのお薦め
◦ サンプルの中心性を事前に計算すれば,実行時間はSEと同じ
 中心性の計算を行うのに,30分から2時間くらいかかる
ダウンロード

Document