NLP プログラミング勉強会 6 – 識別学習の発展版

自然言語処理プログラミング勉強会 6 識別学習の発展版

Graham Neubig
奈良先端科学技術大学院大学 (NAIST)1NLP プログラミング勉強会 6 – 識別学習の発展版

復習 : 識別学習とパーセプトロン

2

NLP プログラミング勉強会 6 – 識別学習の発展版

予測問題

x が与えられた時y を予測する
3

NLP プログラミング勉強会 6 – 識別学習の発展版

今回の例
●
●

Wikipedia 記事の最初の１文が与えられた時その記事が人物についての記事かどうかを予測与えられた情報●

予測

Gonso was a Sanron sect priest (754-827)
in the late Nara and early Heian periods.

Yes!

Shichikuzan Chigogataki Fudomyoo isa historical site located at Magura, Maizuru
City, Kyoto Prefecture.

No!

これはもちろん、２値予測4

NLP プログラミング勉強会 6 – 識別学習の発展版

数学的な定式化
y = sign (w⋅ϕ(x))
I= sign ( ∑i=1 w i⋅ϕi ( x))●x: 入力●φ(x): 素性関数のベクトル {φ1(x), φ2(x), …, φI(x)}●w: 重みベクトル {w1, w2, …, wI}●

y: 予測値、「 yes 」なら +1 、「 no 」なら -1●

sign(v) は「 v >= 0 」の場合 +1 、そうでない場合 -1

5

NLP プログラミング勉強会 6 – 識別学習の発展版

オンライン学習
create map w
for I iterations
for each labeled pair x, y in the dataphi = create_features(x)y' = predict_one(w, phi)
if y' != yupdate_weights(w, phi, y)●

つまり：各学習事例を分類してみる● 間違った答えを返す時に、重みを更新●●

様々なオンライン学習アルゴリズムが存在●

最もシンプルで実装しやすいのがパーセプトロン

6

NLP プログラミング勉強会 6 – 識別学習の発展版

パーセプトロンによる重み更新w ← w + y ϕ(x)
●

つまり：
●

y=1 の場合、 φ(x) の素性の重みを増やす–●「 yes 」の事例の素性により大きな重みを

y=-1 の場合、 φ(x) の素性の重みを減らす–「 no 」の事例により小さな重みを→ 更新のたびに、予測性能が向上！
update_weights(w, phi, y)
for name, value in phi:w[name] += value * y7

NLP プログラミング勉強会 6 – 識別学習の発展版

ロジスティック回帰8

NLP プログラミング勉強会 6 – 識別学習の発展版

パーセプトロンと確率●応用によって確率がほしい時も：予測の信頼性を表現● 他システムとの統合が容易にP( y∣x )●●しかし、単純なパーセプトロンは yes/no のみ

y =sign(w⋅ϕ( x))つまり：p(y|x)P( y =1∣x)=1 if w⋅ϕ ( x )≥0
P( y =1∣x)=0 if w⋅ϕ (x)< 0

10.5-10-500

w*phi(x)5109

NLP プログラミング勉強会 6 – 識別学習の発展版

シグモイド関数 ( ロジスティック関数 )●シグモイド関数はステップ関数を柔らかくしたものw⋅ϕ ( x)eP( y =1∣x)=w⋅ϕ (x)1+e
シグモイド関数

ステップ関数1p(y|x)p(y|x)

10.5-10-500w*phi(x)

●
●

510

不確実性（確率）を考慮
微分可能

0.5-10-500510w*phi(x)10NLP プログラミング勉強会 6 – 識別学習の発展版

ロジスティック回帰(logistic regression; LR)●●

条件付き尤度最大化基準で学習x が与えられたときの正解 y の条件付き尤度を最大化するパラメータ w を獲得

w=argmax^∏i P( yi∣x i ; w)
w

●

解き方は？

11

NLP プログラミング勉強会 6 – 識別学習の発展版

確率的勾配降下法(stochastic gradient descent; SGD)●●

ロジスティック回帰を含む確率モデルのための学習ア
ルゴリズム
w=0
for I iterations
for each labeled pair x, y in the data
w += α * dP(y|x)/dw
つまり各学習例に対して勾配を計算（ y の確率が上がる方向）●
その方向へ、学習率 α をかけた分だけ動かす●

12

NLP プログラミング勉強会 6 – 識別学習の発展版●

確率の微分w⋅ϕ ( x)dP ( y=1∣x ) =dw

d ed w 1+e w⋅ϕ (x)w⋅ϕ (x)e= ϕ (x )w⋅ϕ (x) 2(1+e)
dP ( y=−1∣x ) =dw

dp(y|x)/dw*phi(x)シグモイド関数の勾配
0.4
0.3
0.2
0.1
-10-500510

w*phi(x)w⋅ϕ (x)de(1−)w⋅ϕ (x)dw1+ ew⋅ϕ (x)e= −ϕ (x )w⋅ϕ (x) 2(1+ e)

13

NLP プログラミング勉強会 6 – 識別学習の発展版

例：最初の更新●

α=1 を設定、 w=0 と初期化

y = -1x = A site , located in Maizuru , Kyoto0deP ( y=−1∣x ) = −ϕ (x )w⋅ϕ(x)=00 2dw(1+e )=−0.25 ϕ (x)w← w +−0.25 ϕ ( x )wunigram “Maizuru” = -0.25
wunigram “,”= -0.5wunigram “in”
= -0.25
wunigram “Kyoto” = -0.25

wunigram “A”
wunigram “site”
wunigram “located”= -0.25= -0.25= -0.25

14

NLP プログラミング勉強会 6 – 識別学習の発展版

例： 2 回目の更新

y=1x = Shoken , monk born in Kyoto-0.5w⋅ϕ (x )=−1-0.25 -0.25

dP ( y=1∣x ) =dw=1eϕ (x)1 2(1+ e )0.196 ϕ (x )w← w +0.196 ϕ( x)wunigram “Maizuru” = -0.25
wunigram “,”= -0.304
wunigram “in”
= -0.054
wunigram “Kyoto” = -0.054

wunigram “A”
wunigram “site”
wunigram “located”= -0.25= -0.25= -0.25

wunigram “Shoken” = 0.196
wunigram “monk” = 0.196
wunigram “born” = 0.196 15

NLP プログラミング勉強会 6 – 識別学習の発展版

学習率の決定●●学習率 α をどうやって設定？

徐々に減らしていくのが基本（収束が保証）

1α=C+ tパラメータ
●

サンプル数

または：学習データに含まれない開発データを用意し、開発データの尤度が下がったら学習率を減らす
16

NLP プログラミング勉強会 6 – 識別学習の発展版

マージンを考慮した識別17

NLP プログラミング勉強会 6 – 識別学習の発展版

精度が同一の識別平面の選択方法●

どの線が良い？直線か点線か？
OX

O
X

O
X

18

NLP プログラミング勉強会 6 – 識別学習の発展版

精度が同一の識別平面の選択方法●

どの線が良い？直線か点線か？
OX

O
X

OX

●
●

答え：おそらく点線

理由：マージンがより大きいから

19

NLP プログラミング勉強会 6 – 識別学習の発展版

マージンとは？
●識別平面と事例の間の最短距離

O
X

O
X

O
X

20

NLP プログラミング勉強会 6 – 識別学習の発展版

サポートベクトルマシン(Support Vector Machine: SVM)●

最も有名な分類器

ハードマージン：マージンを直接最大化● ソフトマージン：誤りを少々許す●●

多くの場合はバッチ学習を利用

バッチ学習：全ての例で統計を計算してから更新→精度が少々高い、より安定した学習● オンライン学習：事例ごとに更新
シンプル、省メモリ、収束が速い●●

SVM のバッチ学習についての資料

http://disi.unitn.it/moschitti/material/Interspeech2010-Tutorial.Moschitti.pdf●

バッチ学習ライブラリ :LIBSVM, LIBLINEAR, SVMLite

21

NLP プログラミング勉強会 6 – 識別学習の発展版

マージンを用いたオンライン学習●

誤りだけでなく、一定のマージン以内の場合でも更新

create map w
for I iterations
for each labeled pair x, y in the dataphi = create_features(x)val = w * phi * y★
if val <= margin
update_weights(w, phi, y)( 正しい分類結果は常に w * phi * y > 0)
margin = 0 の場合はパーセプトロンと等しい
22

NLP プログラミング勉強会 6 – 識別学習の発展版

正則化23

NLP プログラミング勉強会 6 – 識別学習の発展版

大きい分類器と小さい分類器●

次の事例に対して：-1 he saw a bird in the park
+1 he saw a robbery in the park●

どの分類器が良い？
分類器１he +3
saw -5a +0.5bird -1
robbery +1
in +5
the -3
park -2

分類器２
bird -1
robbery +1

24

NLP プログラミング勉強会 6 – 識別学習の発展版

大きい分類器と小さい分類器●

次の事例に対して：-1 he saw a bird in the park
+1 he saw a robbery in the park●

どの分類器が良い？
分類器１he +3
saw -5a +0.5bird -1
robbery +1
in +5
the -3
park -2

分類器２
bird -1
robbery +1

たぶん分類器２！
無関係な情報を使用しないから
25

NLP プログラミング勉強会 6 – 識別学習の発展版

正則化
●
●

モデルに重みを追加することに対する罰則
L2 正則化：

5

大きな重みに対して大きな罰則
小さな重みに対して小さな罰則● 精度が少々高い●●

43L1 正則化 :大小に関わらず同等の罰則● 多くの重みが０になるため小さなモデルが学習可能

L2L121●-2-1001

226

NLP プログラミング勉強会 6 – 識別学習の発展版

オンライン学習で L1 正則化●

更新のたびに、重みから定数 c を引く

update_weights(w, phi, y, c)★ for name, value in w:
if abs(value) < c:★
w[name] = 0
★
else:
★
w[name] -= sign(value) * c★
for name, value in phi:w[name] += value * y

絶対値 < c,→0 に設定
値 > 0,c を引く
値 < 0,c を足す

27

NLP プログラミング勉強会 6 – 識別学習の発展版

例●

順番に正則化 (R) 更新 (U) 正則化 (R) 更新 (U)

正則化係数 :
更新 :c=0.1
1 回と 5 回に {1, 0}
３回に {0, -1}

R1

U1

R2

U2

R3

U3

変更 :

{0, 0}{1, 0}{-0.1, 0}{0, 0}{-0.1, 0}{0, -1}w:{0, 0}{1, 0}{0.9, 0}{0.9, 0}{0.8, 0} {0.8, -1}

R4

U4

R5U5R6U6

変更 :{-0.1, 0.1} {0, 0} {-0.1, 0.1}w:{0.7, -0.9} {0.7, -0.9} {0.6, -0.8} {1.6, -0.8} {1.5, -0.7}{1.5, -0.7}{1, 0} {-0.1, 0.1} {0, 0}
28

NLP プログラミング勉強会 6 – 識別学習の発展版●素性の数 :

効率の問題

各文 (phi): 10~1000● 全体 (w): 1,000,000~100,000,000●

update_weights(w, phi, y, c)
for name, value in w:
if abs(value) <= c:w[name] = 0else:w[name] -= sign(value) * c
for name, value in phi:w[name] += value * y

このループは非常に遅い！

29

NLP プログラミング勉強会 6 – 識別学習の発展版

効率化のトリック●●

正則化は重みの使用時に行う！
getw(w, name, c, iter, last)
if iter != last[name]:# 重みが古くなっている
c_size = c * (iter - last[name])
if abs(w[name]) <= c_size:
w[name] = 0else:w[name] -= sign(w[name]) * c_size
last[name] = iter
return w[name]
これは「遅延評価」というやり方

30

NLP プログラミング勉強会 6 – 識別学習の発展版

正則化係数の選び方●●

正則化係数 c は大きな影響を及ぼす大きい

モデルサイズ：小● 学習データ精度：低● 過学習：少●●小さい

モデルサイズ：大● 学習データ精度：高● 過学習：多●●交差検定などで様々な値を試して決定：●

例： 0.0001, 0.001, 0.01, 0.1, 1.031NLP プログラミング勉強会 6 – 識別学習の発展版

演習課題

32

NLP プログラミング勉強会 6 – 識別学習の発展版

演習課題●

実装： L1 正則化とマージンで学習を行う train-svm●

学習 data-en/titles-en-train.labeled●

テスト data-en/titles-en-test.word●

比較 c=0.0001 で精度を測り、パーセプトロンと比較●●

script/grade-prediction.py data-en/titles-en-test.labeled your_answer

チャレンジ：

様々な正則化係数を試す● 効率化を実装●

33

NLP プログラミング勉強会 6 – 識別学習の発展版

Thank You!

34