IBIS-2008
2008年10月29日

機械学習による自然言語処理の諸問題
松本裕治
奈良先端科学技術大学院大学
情報科学研究科
matsu@is.naist.jp

1

自然言語処理の主な研究項目
分類問題


文書分類，語義曖昧性解消

構造解析


形態素解析，統語解析，固有表現解析

複合処理
述語項構造解析，共参照解析（照応解析）
 質問応答，機械翻訳，評判・意見情報抽出，知識獲得2典型的な言語処理の流れ
1. 形態素解析

分かち書き，品詞付与



文節まとめ上げ，固有表現解析



句構造解析，または，係り受け解析

述語（動詞，形容詞，動作名詞など）の項（意味的に必須な役割：主語，目的語など）の同定
省略された項の補完（照応解析）

2. Chunking
3. 統語解析4. 項構造解析
3

述語項構造の解析係り受け解析

が格項構造（意味役割）付与

timeと格村山富市首相は八日社会党の新民主連合会長と会談し、今春の統一地方選後に党全体での新党移行を目指す考えを強調、離党など性急な行動への自重を求めた。
が格に格の省略

照応関係の付与が格の省略省略された格の同定

応用例：Webからの意見・評判情報の抽出と分類
意見
文書をお勧めかそうでないかによって分類
recommended
recommendedWeb
documents
特定の対象に関する文 意見表明となる表現を分類
書群

notnotrecommended
recommended

製品

観点

値

A

価格

高い

A

シート

快適

B

内装

安っぽい

理由

レストランの評判抽出システム

意見・評判マイニング

応用

意味解析
文脈解析

照応表現の解析

関係
抽出

述語項構造
解析
機械学習に基づく
基盤的言語解析システム

文節係り受け
固有表現解析
品詞タグ付け
分かち書き言語処理における２つの大きな問題
曖昧性
言語処理のあらゆる段階に曖昧性があり，ただ一つの正しい解析にいたることが難しい
曖昧性解消のためにどのような知識が必要かを特定することが難しい
主な曖昧性の原因

Attachment: 係り先（修飾先）の曖昧性
並列構造(and, or, で結ばれる等位句の範囲の曖昧性）

頑健性 (システムのカバレージ)


どのような自然言語処理システムについても，開発者が想定していなかったような言語現象が存在する
個々の現象に対して規則を書き並べても完全な解析システムにならない
9構文的曖昧性の例(attachment)

I saw a girl with a telescope.



I saw a girl with a scarf.



彼は よく 本を 読む

彼は よく 本を 読む 人が 好きだ10

構文的曖昧性の例(並列句)

私は 大阪と 京都へ 行きました

私は 友人と 京都へ 行きました11

係り受けに基づく統語解析
単語(あるいは、文節/基本句)の間の統語的依存関係の解析
統語木は、単語だけからなり、句のような中間レベルがない
言語に依存しない統語解析が可能
明示的な文法規則を過程しない（係り受け関係のラベルを設定することはある）ので，文法の頑健さ（カバレージ）に関する問題が少ない
効率的な解析手法が多く提案されている
12

文節まとめ上げと係り受け解析
文節まとめ上げ私は新しく建っ

た

名詞 助詞

形容詞
連用形

動詞 自動詞連用形 基本形

図書館 へ
名詞助詞

行った

動詞 助動詞連用形 基本形

係り受け解析
13

日本語係り受け解析システム「南瓜」（Cascaded Chunking Model）[工藤，松本 02]

各文節が右側の文節に係ることができるかどうかを決定的に決めながら、文節のまとめあげを行う
文節間の係り受けの可否の判定をSVMを用いて学習する
用いているアルゴリズムは，局所最適化の繰り返し

14

南瓜による文解析例
入力文

係り受け木
文節区切り
BIOタグによる固有表現同定

係り受け情報3D: 3という文節にかかっているという意味
15機械学習に基づく構造学習 代表的な学習モデルと用いられる素性

形態素解析

隠れマルコフモデル，CRFs(Conditional Random Fields)
 1次または2次のマルコフ仮説


浅い統語解析(基本句解析，固有表現認識)
Maximum Entropy modelによる線形chunking, CRFs
 前後±２単語前後の文脈情報

統語解析
確率文法，係り受け解析（決定性解析，最大全域木）
 部分木，または，局所的な係り受け関係

典型的な目標関数

arg max θ ⋅ f ( x, y )y∈Y ( x )arg max p( y | x)y∈Y ( x )16

機械学習に基づく構造解析の問題点
局所素性 vs 全域最適化のtrade-off

構造全体にわたる最適化問題であっても，用いている素性は局所的
 Window sizeの限られた素性の利用

決定性局所処理のcascadingは解析の履歴(history)が使えるので，より広い素性を用いることができるが，未解析の部分は構造情報を用いることができない 途中の解析エラーの伝播異なるレベルの処理がパイプライン的に処理されることが多い(e.g. 形態素→文節→統語→．．．)


同時解析：異なるレベルの解析の同時処理
 組み合わせ爆発を防ぐ必要がある
17

局所確率しか用いないことの問題点

この局所的な文脈で確率が最大の木

彼はよく本を読む
18

局所確率しか用いないことの問題点
この文脈では、この木の確率が高い

彼はよく本を読む

人が好きだ19統計的学習による句構造解析
確率文脈自由文法

各句構造規則への確率割り当て

語彙情報も用いた決定木学習による確率値計算
Magerman 1995

最大エントロピー法による決定的解析
Ratnaparkhi 1997

単語の共起確率と文法規則マルコフ化の導入
Collins 1996, 1997

確率文脈自由文法によるN-best解析＋より広い範囲の情報を用いた最大エントロピー法による確率値再推定
Charniak 2000

Collins ModelによるN-best解析＋reranking(Tree Kernelを用いた統語木の部分木を素性とする識別学習)Collins 2002
20

より広い文脈情報を考慮するにはどうすればよいか
すべての可能な句構造木を生成して比較するのは非現実的

可能な句構造木の数は文長の指数オーダー

局所素性＋history:限定された前後文脈を見せる
ことによって評価値(確率値)を推定できるようにする
簡単なモデルによるN-best解＋全域比較：大域素性を用いることができる．N-bestに正解がなければ，正しい解析が付加．効率性に難．
21

N-best解析との組み合わせ
Maximum Entropy-inspired Parser[Charniak 00]
確率文脈自由文法によるN-best解析＋
 親の親や兄弟の情報を使った最大エントロピー法による確率推定Reranking with Tree Kernel and Voted Percepton[Collins &Duffy 02]
Collinsの共起確率モデルによるN-best解析
 Tree Kernel(句構造木のすべての部分木を要素とする内積)を用いた識別学習Coarse-to-fine n-best and MaxEnt Reranking[Charniak &Johnson 05]

Charniak00 parserによるn-best parse(2段階) 句構造木全域を対象とする素性を用いた最大エントロピー法による確率推定 並列句のラベルや長さの情報，他の構造情報による性能向上
22

係り受け解析における曖昧性の問題
係り先（attachment）の曖昧性?

彼は本を読まない ．．．

彼は本を読まない

人を好まないこのように同じような単語列が異なる解析結果をもつ
場合、学習法を工夫しなければ、学習が破綻する
 広い文脈を考慮する必要があるが、その決定は困難Statistical dependency parsers
Eisner (1996)


確率モデル＋CKY法(動的計画法)に基づく解析

Kudo & Matsumoto (VLC 00, CoNLL 02):日本語
SVM出力の擬似確率値利用＋CKY法
 SVMによるcascade chunking
Yamada & Matsumoto (IWPT03)


SVMによるcascade chunking

Nivre (IWPT03, COLING04, …)
決定性Shift-reduce parsing

McDonald-Crammer-Pereira (ACL05)

最大全域木アルゴリズム

Reidel & Clarke (EMNLP06)

整数(線形)計画法による全域最適化

最大全域木による係り受けのイメージ“John saw Mary”
に対するすべての単語対のコスト(rootはダミーの根ノード)

最大コストをもつ全域木
Chu-Liu-Edmonds algorithm:O(n2)25Notation and definition
Τ = {( xt , yt )}Tt=1

訓練データ

xt

t番目の文

yt = {(i, j )}in=1

ｔ番目の文の依存構造木(枝の集合)

f (i, j )素性関数

dt ( x )xに対する可能な依存木の集合基本アイデア
依存木に対するスコア関数s ( x , y ) = ∑ s (i, j ) = ∑ w ⋅ f (i, j )( i , j )∈ y( i , j )∈ y

最適化の目標関数min ws.t. s ( x , y ) − s ( x , y' ) ≥ L( y, y' )∀( x , y ) ∈ T , y' ∈ dt ( x )L(y,y’)は，正しい木 y に対する y’ のloss．
loss = 親が間違っている単語の数と定義する

weight vectorのupdate
min w (i +1) − w (i )s.t. s ( x , y ) − s ( x , y' ) ≥ L( y, y' )∀y' ∈ dt ( xt )しかし，これでは，すべての可能な依存木を求める必要があるため，次のようにk-bestだけを対象とする

min w (i +1) − w (i )s.t. s ( x , y ) − s ( x , y' ) ≥ L( y, y' )∀y' ∈ best k ( xt ; w (i ) )(k=5〜20)

学習に用いられる素性
Unigram素性：親の単語，品詞，子の単語，品詞(５文字以上の語の単語素性は5文字prefix)
Bigram素性：親の品詞・単語と子の品詞・単語の組
合せ
Trigram素性：親子の品詞とその間に存在する語の品詞の３つ組
文脈素性：親子の品詞と前後に現れる語の品詞．４
種類の4-gram素性を構成(trigramでbackoff)… , wi, ……………………… , wj, ……
単語… pi-1, pi, pi+1, …, pk, …, pj-1, pj, pj+1, … 品詞
親子

機械学習に基づく英語(多言語)の依存構造解析(代表的な手法)
上昇型決定性解析
SVMによる決定性動作学習[Yamada, Matsumoto 03]
 解析の動作をSVMによって学習

決定性Shift-reduce parsing[Nivre 03]

 解析の動作をmemory-based modelにより学習、後にSVMを使用

全体最適化


最大全域木(MST)に基づく手法[McDonald, et al 05]
 単語間の依存関係を素性の重みとしてパーセプトロンにより学習、全体の依存関係の和を最大化するspanning treeを求める



広い範囲の素性を利用した最適化[Nakagawa 07]

 文全体を対象とする素性(global feature)を用いる確率学習(sampling法を利用)と最大全域木を利用

混合モデル
Nivre法とMST法のそれぞれの結果を素性として，相手の入力として利用[Nivre & McDonald 08]
 MST法+整数計画法による大域的な制約[Reidel & Clarke 06]
30

日本語係り受け解析手法の変遷(1)
人手による係り受け規則の記述
文節係り受け確率の学習
単語の共起確率[Fujio, Matsumoto 97]
 最大エントロピー法による確率推定[Uchimoto etal 99]
 Support Vector Machinesによる擬似確率推定[Kudo, Matsumoto 00]


上昇型決定性解析
SVMによる決定性動作学習[Kudo, Matsumoto02]
 決定性Shift-reduce parsing[Sassano 04]
31

日本語係り受け解析手法の変遷(2)競合する係り受け関係の比較を考慮した解析

文法制約により係り先を絞った上で選択[金山他 00] 文法を用いた解析で係り先候補を絞る
 候補が2つの場合と3つの場合の選択モデルを学習

相対的な係りやすさを考慮した確率推定[工藤、松本05]
 係り受け確率の学習時に、正しい係り受けの確率が正しくないどの係り受け確率より大きな値をもつように学習
 解析時は、通常の解析(ビーム幅を考慮、しかし、決定性解析で充分な精度)


トーナメントモデルを利用した最適な係り先選択[Iwatate, Asahara, Matsumoto 08]
 係り先候補を２つずつ比較し、最適なものを選択
32

言語解析における曖昧性の問題
可能な係り先をいかに選択するか

彼は本を読まない

人を好まないトーナメントモデルを用いた日本語[Iwatate 08]
係り受け解析
係り受け解析を文末から解析する
各文節の係り先の最適な候補をトーナメントによって選択する

chunk

chunk1chunk2…

chunkn-1

係り先の候補文節

chunknトーナメントモデルを用いた日本語[Iwatate 08]
係り受け解析
係り受け解析を文末から解析する
各文節の係り先の最適な候補をトーナメントによって選択する

chunk

chunk1chunk2…

chunkn-1

係り先の候補文節

chunknトーナメントモデルを用いた日本語[Iwatate 08]
係り受け解析
係り受け解析を文末から解析する
各文節の係り先の最適な候補をトーナメントによって選択する(係り先候補を２つずつ比較し、より適切なものを選択、chunk2
これを繰り返す)chunk

chunk1chunk2…

chunkn-1係り先の候補文節

chunknトーナメントモデルを用いた日本語[Iwatate 08]
係り受け解析
係り受け解析を文末から解析する
各文節の係り先の最適な候補をトーナメントによって選択する

chunkchunk1

chunk2…

chunkn-1

係り先の候補文節

chunkn言語解析における曖昧性の問題
係り先の曖昧性に対応する解析法


トーナメントモデル

彼は本を読まない

人を好まない言語解析における曖昧性の問題
係り先の曖昧性に対応する解析法
トーナメントモデル

彼は本を読まない

人を好まない言語解析における曖昧性の問題
係り先の曖昧性に対応する解析法


トーナメントモデル

彼は本を読まない

人を好まない日本語係り受け解析性能の比較
南瓜 [Kudo & Matsumoto 02]
Cascaded chunking model 隣り合う文節間のまとめ上げの繰り返し

tournament model [Iwatate, Asahara, Matsumoto 08]
 係り先候補を2つずつ比較しながら，最適の候補を選択
test1

test2

test3

89.22/47.90 89.80/47.94 89.53/49.79
CaboChaTournament 90.09/47.79 90.11/49.02 90.35/52.59(約1万文による実験の数値，数字は「係り受け精度/文解析の精度)」

統語解析に関するこれまでの考え方の変遷
局所的かつ文脈非依存の尺度による大域的最適化
(HMM), PCFG, MST

限定された文脈を用いた決定性解析
Cascaded chunking, Shift-reduce parsing

他候補との比較全体比較：N-best解析＋reranking
 局所的な比較：Tournament model

42曖昧性解消のためのその他の手法
制約との融合言語に関する文法的知識を制約として同時にモデル化
 制約を確率的にモデル化
 e.g., probabilistic inductive logic programming,
Markov logic networks

同時推定(joint inference) vs pipeline
異なるレベル（e.g.,形態素解析と統語解析）を同時にモデル化し学習する これまでの多くの手法は，個々のレベルを独立にモデル化し，pipeline的につなげていた

43

制約との融合の例
形態素解析における種々の文法的制約
文には少なくとも一つ述語（動詞，形容詞など）が存在しなければならない （英語）：助動詞の後には数単語以内に必ず動詞の原形が存在しなければならない このような制約を確率論理プログラムで実装[]


並列句解析における整合性に関する制約
文中に複数の並列構造が出現する場合，それらの開始・終了位置が交差していてはならない これを系列アラインメントと文法制約により融合[原，他 08]44

係り受け解析における並列句の問題
単純な並列句の場合
並列句
私は大阪と京都へ行きました

私は友人と京都へ行きました係り受け解析における並列句の問題


並列句にまつわる係り受けの表現の問題
並列表現
高い

水温の山と低い

高い

潮と山に登る低い?
「水温の」が「高い」と「低い」の両方に係ることをどう表現すればよいか

潮が混じり合う並列句は、既存の統語解析法では正しく解析するのが困難“Median times to progression and median survival times
were 6.1 months and 8.9 months in group Aand 7.2 months and 9.5 months in group B” の、下線部分に対する、
正しい構文木and 8.9
and 7.2 and 9.5
in
6.1
in
monthsmonths group A
monthsmonths group B

誤りの構文木 [Charniak and Johnson, 2005] による出力結果
andand 8.9
in
6.1
monthsmonths group Ain
7.2 and 9.5
monthsmonths group B

並列句構成要素対のアラインメント
相同する部分に対応を付ける。
“the standard arm and the dose densearm”
thestandard arm
the dosedensearm48

アラインメントは編集グラフ上の経路に対応
the dose dense arm
thestandardarm

thestandard arm

the dosedensearm49

入れ子を伴う複雑な並列構造
系列アラインメントによる手法では入れ子になった並列構造を解析するのが困難
複数の並列句が１文に存在する場合，それらが交差しないことを保証するのも困難“( (Median times to progression) and (median survivaltimes) ) were( ( ( (6.1 months) and (8.9 months) ) in group A) and( ( (7.2 months) and (9.5 months) ) in group B) )”50

並列句範囲同定へのアラインメントと文法制
約の融合 [原，新保，大熊, 松本 08]

1. 並列句構成要素対にスコアを定義する


アラインメント素性の重みに基づく

2. 並列句に特化した文法により，通常の句構造解析を行う（並列句構造の整合性制約）

それぞれの構文木は、並列句範囲の異なる決め方に対応する

3. 訓練データを用い、素性の重みを最適化する


ＣＫＹ統語解析アルゴリズムとパーセプトロンを組み合わせたアルゴリズム
51

Cc（完全な並列句）の生成規則
Cc → {N, Cc} CEp {N, Cc}
Cc → {N, Cc} CEs Ci
Cc

Cc

Ci

N

CEp N

W

W

“A” “and” “B”

N CEs N
W

W

CEp N
W

“A” “,” “B” “and” “C”
52

Ci（不完全な並列句）の生成規則
Ci → {N, Cc} CEp {N, Cc}
Ci → {N, Cc} CEs Ci
Cc

CiCi

N CEs N CEs NWW

W

CEp N
W

“A” “,” “B” “,” “C” “and” “D”
53

文とその並列句の範囲が与えられたとき、これを一意の構文木に表現できる“( (Median times to progression) and (median survivaltimes) ) were ( ( ( (6.1 months) and (8.9 months) ) ingroup A) and ( ( (7.2 months) and (9.5 months) ) ingroup B) )”N

NCc
Cc

NNNNN

NN

N

N
N

Cc

N
N

NNN
NN
N

Cc

NN

NN

N
W WW WCEpW W W WW WCEpW W WW WCEpWWCEpW WW WW

54

構文木全体のスコアは、並列句のアラインメントスコ
アの総和として制約を保証しつつ最適化“( (Median times to progression) and (median survivaltimes) ) were ( ( ( (6.1 months) and (8.9 months) ) ingroup A) and ( ( (7.2 months) and (9.5 months) ) ingroup B) )”N

N

Cc
Cc

NN

NNN

N
N

N

N
N

Cc

N
NN
NN
NN
N

Cc

NN

N
N

N
W WW WCEpW W W WW WCEpW W WW WCEpWWCEpW WW WW

55

評価実験
GENIA コーパスを使用する“and”を接続詞としてもつ並列句 2,948 個を解析対象とする


GENIA コーパスの COOD タグ（4,129個）の約7割

このうちの、名詞並列句（1,976個）の並列範囲を同定するタスクに対し、提案手法を評価する
56

実験結果手法

適合率

再現率

Ｆ値

提案手法

56.8%

54.5%

55.6

Charniak andJohnson, 2005

45.6%

42.9%

44.2Bikel, 2004

43.9%

44.4%

44.1
57

同時処理の例
品詞タグ付けと固有表現の同時処理

Factorial CRFによる同時処理[Sutton,Rohanimanesh, McCallum 04]

形態素解析と統語解析の同時処理
両者が生成モデルとして確率値計算するなら統合は容易：形態素lattice入力のparsing
 CRFによるヘブライ語の形態素と確率文法による句構造解析の融合[Cohen & Smith 07]
 下位のモデルから得られる素性の確率値を上位モデルで利用[Bunescu 08]
58

同時モデルの事例“Learning with Probabilistic Features forImproved Pipeline Models,” Razvan
Bunescu (EMNLP 08)
ヘブライ語の形態素解析と係り受け解析の同時処理
 英語の品詞タグ付け，係り受け解析，固有表現認識の同時処理59２つの階層的なモデルの融合
Pipeline inference modelz(下位のモデル)の最適解のみを上位で利用yˆ ( x) = arg max w ⋅ φ ( x, y, zˆ ( x))y∈Y ( x )zˆ ( x) = arg max p ( z | x)z∈Z ( x )Joint inference model

下位モデルの全解を考慮した素性の確率値を利用
yˆ ( x) = arg max w ⋅ ϕ ( x, y )y∈Y ( x )ϕ ( x, y ) = ∑ p ( z | x ) ⋅ φ ( x, y , z )z∈Z ( x )

２つの階層的なモデルの融合
中間的なモデルz(下位のモデル)の最適解の確率だけを利用yˆ ( x) = arg max w ⋅ ϕ ( x, y )y∈Y ( x )ϕ ( x, y ) = ∑ p ( z | x ) ⋅ φ ( x, y , z )z∈zˆ ( x )Bunescu (EMNLP 08)より引用

まとめ
構造学習の諸問題を統語解析を例として次のような話題を説明
局所素性のみによる大域的最適化
 大域素性の利用 N-best解の利用による木全体の比較
 競合対象の直接比較異なるレベルの情報の利用
 上位の制約の利用 同時学習（異なるレベルの）62

言わなかったこと
未解析データの利用

半教師あり学習(semi-supervised learning)
新領域への適用(domain adaptation)
クラス数推定：語義曖昧性解消（語義数）
Bootstrapping

素性選択



特に，素性の組み合わせ構造をもつ素性（系列，木構造）のマイニング

制約との融合

語彙知識の活用
素性としての制約の学習(素性マイニングと同義)

耐規模性，あるいは，そのための近似手法
部分アノテーションデータの構築と利用

アノテーション作業の動的な選択・指定
部分情報をもったデータの解析
63