渕一博記念コロキウム
2007年10月20日
制約に基づく言語処理から
制約なしの言語処理へ
松本裕治
奈良先端科学技術大学院大学
情報科学研究科
1
簡単な自己紹介
1979.4: 電子技術総合研究所入所

推論機構研究室(渕一博室長,翌年より田中穂積室
長)
1984.9-1985.7: 英国Imperial College滞在研究
員(渕さんにKowalski教授への推薦書を書いていただく)
1985.9-1987.11

ICOT第一研究室(古川康一室長)
1988.10: 京都大学
1993.4: 奈良先端科学技術大学院大学
2
ICOTでの言語処理研究
並列構文解析


DCG (Definite Clause Grammars)に基づく構
文解析の並列処理
PrologおよびGHCによる実装(SAX, PAX)
層状ストリームによる並列プログラミング


動的計画法(Dynamic Programming)の並列
実装法
Prologによる副作用なし・後戻りなしの構文解
析(SAX),形態素解析(LAX)の実装
3
80年代の言語解析
単一化文法(制約に基づく文法)

論理文法(Logic Grammars)
 DCG (Definite Clause Grammars):文脈自由文法
規則(補強項(制約)付き)をPrologの節として直接
実行
 Extraposition Grammars, Gapping Grammars:
関係節などの痕跡(trace)を伴う文法現象等の記
述のための拡張

HPSG (Head-driven Phrase Structure
Grammar)
 ほとんどの文法情報を語彙に記述(radical
lexicalism)
 個別の文法規則は存在せず,句の形成を記述す
る少数のスキーマが存在するだけ
4
単一化文法(HPSG)の利点・欠点
利点


普遍的な演算:2つの句が組み合わさって1つの句を
作り上げる際に,単一化演算により一方が他方の関
数として機能する
文法の記述(語彙情報+原則)と処理の独立性
欠点


曖昧性の問題
曖昧性爆発:1つの文に対して,文法的に正しい解析
結果が多数得られる
脆弱性:文法誤りを持つ文(あるいは,想定外の文法
現象)に対して,処理が破綻する
頑健性の問題
5
統語的曖昧性の例
sentence
np
vp
I
vp
pp
verb
np
prep
det
det noun
saw
a
girl
np
with
a
noun
telescope
6
統語的曖昧性の例
sentence
vp
np
I
verb
np
pp
np
saw
det noun
a
prep
girl
with
np
det
noun
a
scarf
7
90年代前半の言語解析
コーパス(大規模言語データ)の出現



統計的機械翻訳(Statistical Machine
Translation)– IBMグループ:英仏翻訳
隠れマルコフモデルによる品詞タグ付けプロ
グラム(形態素解析)
確率文脈自由文法(Probabilistic Contextfree Grammar)
 各文法規則(VP→V NP, VP→V NP PP など)に確
率値を与え,文を構成する文法規則の積が最大に
なる構文木を求める
 Inside-Outsideアルゴリズム(Expectation
Maxmization法の一種)により,自動推定可能 8
統語的曖昧性の例
sentence
vp
np
pp
I
verb
np
prep
det noun
saw
a
girl
with
np
det
noun
a
scarf
9
初期の統計モデルの問題点
品詞や句を確率事象の単位とした条件付確率を用いる:
単語の情報を考慮しにくい
同じ品詞列や句の組み合わせを持つ文でも異なる形で
解析すべき例(telescopeの例)がある

次の例は同じ品詞列(名詞,助詞,動詞,名詞,助詞,動詞)を持
つが,異なる構造を持つ
 双眼鏡で泳ぐ子供を監視した
 海で泳ぐ子供を監視した
(双眼鏡で→監視した)
(海で→泳ぐ)
細かい粒度の情報(単語や単語の接頭・末尾の文字列
など)を取り込むことのできる統計モデルへ:


Exponential models (最大エントロピー法,Conditional Random
Fieldsなど)
Maximum margin methods (Support Vector Machines,
Boosting など)
10
統計学習と言語処理タスクの分類
学習タスクの分類 言語処理タスクの例
予測
言語モデル,語の類似度
分類
文書分類,語義曖昧性解消(WSD),用語の意
味分類,照応解析(代名詞の指示物の同定)
系列タグ付け
分かち書き,品詞タグ付け,基本句チャンキン
グ,固有表現抽出,統語解析(句構造解析,係
り受け解析)
変換
統計的機械翻訳,機械翻訳規則獲得,
対訳文アラインメント,
マイニング
コロケーション,クラスタリング,語彙知識獲得,
素性選択
11
語彙情報を利用した統計的統語解析
句構造解析



決定木の利用(Magerman 95)
句の主辞の共起確率を用いた句構造解析(Collins
96)
最大エントロピー法の利用 (Ratnaparkhi 97,
Charniak 00)
係り受け解析



SVMの利用したchunking cascade (Kudo &
Matsumoto 02, Yamada & Matsumoto 03)
Memory-based Reasoningを利用したShift-Reduce法
(Nivre 03)
Maximum Spanning Tree algorithmとマージン最大
化の利用 (McDonald 05)
その他:re-ranking手法など
12
Japanese Dependency Parsing by CaboCha
input sentence
dependency tree
文節まとめ
上げ
固有表現の
タグ付け
13
英語に対する決定性の単語係り受け解析
[Yamada & Matsumoto 03]
各状況で3つのアクションを考える:



Right: 2つの連接する単語の間に,左から右への係り受け関係
がある.左の語を右の語へ掛けて,消去する
Left: 2つの連接する単語の間に,右から左への係り受け関係が
ある.右の語を左の語へ掛けて,消去する
Shift: 現在の2つの単語の間には,係り受け関係を決めずに,
対象を一つ右へずらす
 この状況では,実は2つの可能性がある:
 1.2つの単語の間に依存関係がない
 2.2つの単語の間に本当は依存関係があるかも知れないが,この
場で決めることを避けて,処理対象を右へ移す.(次のラウンドで決
定する)
この場合を,上の場合と区別して “Wait” というアクションをたてるこ
ともできる
この処理を文頭から順に右へ向かって適用し,文末まで
来れば,文頭へ向かって処理を繰り返す.文全体が一つ
の依存構造木になれば終了
14
Right action
15
Left action
16
Shift action
17
学習に用いられる素性(属性)
3 class問題 (right, left, shift) または
4 class問題 (right, left, shift, wait)を解くために
SVM(Support Vector Machines)を用いる
18
Yamada法による英語の係り受け解析の例
right
the
boy
hits
the
dog
with
a
rod
処理すべき単語対
参照文脈
19
Yamada法による英語の係り受け解析の例
right
boy
hits
the
dog
with
a
rod
the
処理すべき単語対
参照文脈
20
Yamada法による英語の係り受け解析の例
shift
hits
the
dog
with
a
rod
boy
the
処理すべき単語対
参照文脈
21
Yamada法による英語の係り受け解析の例
right
hits
the
dog
with
a
rod
boy
the
処理すべき単語対
参照文脈
22
Yamada法による英語の係り受け解析の例
shift
hits
dog
boy
the
with
a
rod
the
処理すべき単語対
参照文脈
23
Yamada法による英語の係り受け解析の例
shift
hits
dog
boy
the
with
a
rod
the
処理すべき単語対
参照文脈
24
Yamada法による英語の係り受け解析の例
right
hits
dog
boy
the
with
a
rod
the
処理すべき単語対
参照文脈
25
Yamada法による英語の係り受け解析の例
left
hits
boy
dog
with
the
rod
a
the
処理すべき単語対
参照文脈
26
Yamada法による英語の係り受け解析の例
shift
hits
boy
dog
the
the
with
rod
a
処理すべき単語対
参照文脈
27
Yamada法による英語の係り受け解析の例
left
hits
boy
dog
the
the
with
rod
a
処理すべき単語対
参照文脈
28
Yamada法による英語の係り受け解析の例
left
hits
with
boy
dog
rod
the
the
a
処理すべき単語対
参照文脈
29
Yamada法による英語の係り受け解析の例
処理の終了
hits
boy
dog
with
the
the
rod
a
30
統計的言語解析の貢献
曖昧性の解消

入力文に対して,単一(あるいは,順序付き)
の解を返してくれる
頑健性の問題

特に,依存構造(係り受け)解析は,どんな入
力に対しても,ともかく解を返す
31
制約に基づく文法の語彙化の流れ
個別の文法規則を持たず,ほとんどの文
法情報を語がもつ


Lexicalized TAGでは,規則は2種類
HPSGでは,規則は4~5種類
Lexicalized TAG
HPSG
(それぞれgiveの記述例)
32
制約文法の利点
詳細な文法現象の記述
健が本を読み直した (Ken re-reads the book.)
本が健に読み直された (The book is re-read by Ken)
健が本を読みそびれた (Ken fails to read the book.)
*本が健に読みそびれられた (*The books fails to be read
by Ken.)
HPSG による説明
「直す」 は語彙的複合をつくる動詞
「そびれる」 は統語的複合をつくる動詞
これらを各語の内部構造の記述によって区別できる
33
「直す」:語彙的複合動詞
V
V
N
健が
Ken-ga
N
V
N
本を
book-wo
V
読み
read
「直す」は単語(動詞)
を引数として取る
本が
book-ga
V
V
直す
re-
V
N
健に
Ken-ni
V
V
V
V
V
読み
read
直さ
re-
他動詞としての「読み直す」
が受動態を取り得る
れる
passive
34
「そびれる」 統語的複合動詞
V
N
V
V
健が
Ken-ga
V
N
V
本を
book-wo
読み
read
そびれる
fails
「読みそびれる」は受動態
不可
「そびれる」 が
目的語を既にもつ動詞句を
引数として取るため
35
「そびれる」 を含むかき混ぜ構文
??
V
V
V
N
N
本を
健が
book-wo Ken-ga
V
V
読み
read
この文は文法的に
正しいが,句構造に
よって表現することが
できない
そびれる
fails
依存構造(係り受け)木
を利用することで,この
現象を回避できる
36
Use of Dependency as Control Information
Non-projectivity (caused by scrambling is easily handled
健が 本を 読み直した
健が 本を 読みそびれた
本を 健が 読み直した
本を 健が 読みそびれた
book-wo
read
健
本
健
本
が
を
が
を
読み
読み
直した
そびれた
37
近年の語彙意味論の進展の例
Generative Lexicon [Pustejovsky 95]



語の統語・意味構造を素性構造によって記述
文法的不適格な文に対して,制約を緩和する3つの
演算を定義 (強制:coersion, 共構成:cocomposition, 選択束縛:selective binding)
強制は:関数の引数のタイプを変更.共構成:関数の
タイプを変更.選択束縛:引数の部分構造を選択的に
引数とする
 “He began the book.” は “begin” が事象を表す目的語を
予測しているため,不適格
 強制(Coersion)により “book” の意味構造が「事象」に変更
される. 語の中にその語にまつわる事象に関する情報が記
述されているためにこれが可能になる.

語が持つQualia構造:構成役割,形式役割,目的役割,主体
役割をもち,目的・主体役割がその語が目的語・主語としてど
のような事象と関係するかを記述
38
GL representation of “begin”
Qualia structure of a “book”
39
共構成の例
bake と cakeの記述
から,
I bake a cake は正
しい文ではないこ
とになる.
bakeは「材料」を目
的語に予測して
おり,cakeは人
工物のため,材
料ではない,
(bake a potato
ならOK)
共構成によりbake
が単なるprocess
動詞ではなく,結
果をもつcreation
動詞に変更され
ることで,この文
が解釈できる
40
処理および文法記述における語彙化の流れ
統計的言語解析


単語の情報を素性として用いることにより,精
度の高い言語解析が可能になってきた
依存構造については,ハードな制約は存在し
ない
生成語彙


意味表現と統語の干渉:統語制約を意味情報
によりoverwrite
動的な制約緩和を実現
41
Overview of the Integrated System
HPSG+LCS
(grammar/lexicon)
Input
sentence
Control Information
of Syntactic Parsing
Expansion into
Grammar rules
Grammar
rules
Word Dependency
Parser
Chart Parser
with Dependency
Constraint
Unification Engine
Generalized
interpretation
Violation of
constraints
Generative/
constructive
operations
42
我々の研究グループの最近の活動:
言語処理ツールとコーパス管理システム
大規模テキストデータ
(新聞記事,Webテキスト)
言語処理ツール
言語処理ツール
茶筌・南瓜
固有表現タガー
機
械
学
習
共参照解析
項構造解析
未知語抽出
管理ツール
タグ付きコーパス
管理:茶器
aTagrin
辞書管理ツール
Cradle
言語資源
タグ付きコーパス
辞書
43
我々のグループで構築し公開している
言語処理ツール
NLP Tools Based on Machine Learning

Japanese Morphological Analyser:
 ChaSen [Asahara 00] – variable memory length HMM

Multi-lingual version: Japanese, Chinese, English
 MeCab [Kudo 04] – Conditional Random Fields



Japanese Dependency Parser: CaboCha [Kudo 02]
English and Chinese Word Dependency Parsers
[Yamada 03, Chen 04]
General Purpose Chunker: YamCha [Kudo 01]
 Named Entity Recognition [Asahara 03] [Watanabe 07]
 Unknown Word Identifier: bar [Asahara 04]

Anaphora Resolution and Co-reference Analysis
 Japanese zero-pronoun and co-reference [Iida 03, 05, 06]
Management Tools for Linguistic Data



Annotated Corpus Management Tool: ChaKi [Matsumoto 06]
Dictionary Management Tool: Cradle
44
General Purpose Annotation Tool: aTagrin
まとめ
制約に基づく文法


曖昧性の問題:唯一解の選択,順序付け
頑健性の問題:例外事象への対応
語彙情報を中心にした言語解析



統計的言語解析:単語(文節)係り受け
語彙意味と生成的演算に基づく制約の動的緩和
これらの融合
応用および今後



Webからの評判・意見情報マイニング
日本語国家コーパスプロジェクト
言語解析手法の精緻化
 全域情報を用いた全域最適化
45
ダウンロード

形態素解析のための辞書の構成