NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

自然言語処理プログラミング勉強会 3 パーセプトロンアルゴリズム

Graham Neubig
奈良先端科学技術大学院大学 (NAIST)1NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

予測問題

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

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

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

本のレビュー「良い」評価なのか？２値予測( 選択肢が２つ )Oh, man I love this book!
yesThis book is so boring...
noツイートOn the way to the park!
公園に行くなう！

書かれた言語EnglishJapanese

文

構文木

S

構造化予測
( 選択肢が膨大 )VP

I read a bookNPN

VBD DET

多クラス予測( 選択肢が数個 )NN

I read a book

3

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

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

予測

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

Yes!

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

No!

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

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

予測方法

5

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

どうやって予測するか

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

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

6

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

どうやって予測するか「 priest 」を含む→
人物の可能性が高い「 (<#>-<#>) 」を含む →人物の可能性が高い

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

「 site 」を含む →人物の可能性が低い

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

「 Kyoto Prefecture 」を含む →人物の可能性が低い

7

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

様々な情報を組み合わせる●予測に利用する情報は「素性」と呼ぶ「 priest 」を含む
「 (<#>-<#>) 」を含む
「 site 」を含む
「 Kyoto Prefecture 」を含む●

書く素性に重みが振られており、「 yes 」の可能性が高ければ高いほど重みが正の値になる
wcontains “priest” = 2
wcontains “site” = -3●

wcontains “(<#>-<#>)” = 1
wcontains “Kyoto Prefecture” = -1

新しい事例が入ってきたら、重みの和で答えを予測
Kuya (903-972) was a priest
born in Kyoto Prefecture.

●

2 + -1 + 1 = 2

重み付き和が 0 以上であれば「 yes 」そうでなければ8「 no 」

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

数学で言うと
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

9

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

素性関数の例： 1-gram 素性●「事例において、ある単語が何回現れるか？」

x = A site , located in Maizuru , Kyoto
φunigram “A”(x) = 1

φunigram “site”(x) = 1

φunigram “,”(x) = 2

φunigram “located”(x) = 1 φunigram “in”(x) = 1
φunigram “Maizuru”(x) = 1 φunigram “Kyoto”(x) = 1
φunigram “the”(x) = 0 φunigram “temple”(x) = 0…
●

残りはすべて 0

便宜のため、素性 ID(φ1) の代わりに、素性の名前(φunigram “A”) を利用

10

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

重み付き和の計算
x = A site , located in Maizuru , Kyoto
φunigram “A”(x)φunigram “site”(x)φunigram “located”(x)

=1
=1
=1

φunigram “Maizuru”(x)φunigram “,”(x)φunigram “in”(x)φunigram “Kyoto”(x)φunigram “priest”(x)φunigram “black”(x)

=1
=2
=1
=1
=0
=0

wunigram “a”
wunigram “site”

*…

=0
= -3

wunigram “located” = 0wunigram “Maizuru” = 0
wunigram “,”=0wunigram “in”
=0wunigram “Kyoto” = 0
wunigram “priest” = 2
wunigram “black” = 0=0+-3+0 +0+00 ++0+0+0+…
=-3 → No!

11

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

予測の擬似コード

predict_all(model_file, input_file):load w from model_file # w[name] = wname となるように
for each x in input_filephi = create_features (x) # phi[name] = φname(x) となるように
y' = predict_one(w, phi)print y'# sign(w*φ(x)) を計算

12

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

1 つの事例に対する予測の擬似コード
predict_one(w, phi)score = 0
for each name, value in phi
if name exists in w
score += value * w[name]if score >= 0
return 1else
return -1# score = w*φ(x)13

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

素性作成の擬似コード( 例： 1-gram 素性 )CREATE_FEATURES (x):create map phi
split x into words
for word in words
phi[“UNI:”+word] += 1
すreturn phi●# 「 UNI: 」を追加して 1-gram を表

この関数を変更し、他の素性を簡単に導入できる
2-gram ？
● その他の素性？
●

14

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

重みの学習：
パーセプトロンアルゴリズム15

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

重みの学習
●

人手で重みを付与するのが困難
有用な素性の数は膨大● 重みをむやみに変更すると予期しない影響●●

その代わり、ラベル付きデータから学習yx

1

FUJIWARA no Chikamori ( year of birth and death unknown ) was asamurai and poet who lived at the end of the Heian period .

1Ryonen ( 1646 - October 29 , 1711 ) was a Buddhist nun of the Obaku
Sect who lived from the early Edo period to the mid-Edo period .

-1-1

A moat settlement is a village surrounded by a moat .
Fushimi Momoyama Athletic Park is located in Momoyama-cho , Kyoto
City , Kyoto Prefecture .
16

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

オンライン学習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)●

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

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

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

17

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

パーセプトロンによる重み更新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 * y18

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

例：最初の更新●

w=0 として初期化

x = A site , located in Maizuru , Kyotow⋅ϕ(x)=0y = -1y ' =sign( w⋅ϕ( x))=1y '≠ yw ← w + y ϕ( x)wunigram “Maizuru” = -1 w
= -1
unigram “A”
wunigram “,”= -2 w= -1
unigram “site”
wunigram “in”
= -1 w= -1
unigram “located”
wunigram “Kyoto” = -1

19

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

例：２回目の更新
x = Shoken , monk born in Kyoto-2-1w⋅ϕ( x)=−4

y=1-1

y ' =sign( w⋅ϕ( x))=−1y '≠ yw ← w + y ϕ( x)wunigram “Maizuru” = -1 w
= -1
unigram “A”
wunigram “,”= -1 w= -1
unigram “site”
wunigram “in”
=0 w
= -1
unigram “located”
wunigram “Kyoto” = 0

wunigram “Shoken” = 1
wunigram “monk” = 1
wunigram “born” = 1

20

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

演習問題

21

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

演習問題●

２つのプログラムを作成
train-perceptron: パーセプトロンを用いた分類器学習● test-perceptron: 重みを読み込み、予測を１行ずつ出力●●

テスト： train-perceptron
入力： test/03-train-input.txt● 正解： test/03-train-answer.txt●

22

NLP プログラミング勉強会 3 – パーセプトロンアルゴリズム

演習問題●

data-en/titles-en-train.labeled でモデルを学習●

data-en/titles-en-test.word のラベルを予測●

評価スクリプトで分類器の精度を計算●●

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

上級編：
モデルが間違えた箇所を見て、間違えた理由について考察する● 新しい素性を導入し、精度への影響を計る●

23