1.自然言語解析システムの設計課題

自然言語文解析(NLA:Natural Language Analysis)システムは、入力文に対して言語知識を適用して最も適切な解釈を出力する。一般に、NLAシステムは、形態素、構文、意味、文脈などの多層の言語知識を扱う必要があり、各層の知識記述のベースとして、句構造木、依存木、述語論理式など様々な文解釈記述スキーマが提案されている。これらのスキーマは、知識記述の質や能力、すなわちシステムの性能を規定するため、どの様なスキーマを採用するかはNLAシステム設計上重要な課題の1つである。また、言語知識は、計算機処理の視点から見て、入力文に対して不可能な解釈を排除する「制約知識」と可能な解釈の優先順序付けを行う「選好知識」の2種類に分類される。制約知識は自然言語の各層で生じる解釈の組み合わせ爆発の抑制に有効であるが、その過度の適用は正解解釈の枝刈りによる性能劣化を引き起こしてしまう。一方、自然言語の各層の選好知識は、相異なる解釈を支持することもあり、全体として最適な解を得るためには各層の知識を統合評価する必要がある。このように、多層の知識、制約/選好知識の統合をいかに行うかがNLAシステム設計のもう1つの重要な課題である。

2.選好依存文法の概要と特徴

本論文は、上記NLAの課題に焦点をあてて設計された文解析の枠組みである選好依存文法(PDG:Preference Dependency Grammar)を提案する。PDGの文解析モデルとして、Meaning Text Theory(MTT)[Melcuk88,Kahane O3]の考え方をベースに多層の言語知識を扱う「多レベル圧縮共有データ結合(MPDC:Multilevel Packed Shared Data Connection)モデル)を提案する。MTTは、テキストから意味までを扱う言語理論体系であり、自然言語をテキストと意味の対応を規定するものと捕らえ、形態素、構文といった複数の解釈層のデータ構造を介してテキストと意味を対応付ける。MTTは、基本的に解析/生成の双方向モデルであるが、文生成に軸足をおいており、文解析に必要な解釈多義や選好知識の扱いが不十分である。この課題に対して、MPDCでは、各層の文解釈を圧縮共有データ構造で結合することにより組合せ爆発を抑制しながら解釈多義性をモデルに導入し、また、各層の選好知識を統合処理する仕組みも導入している。

PDGの実装モデル(図1)は形態素、構文、意味の各層の解釈記述スキーマとして語品詞系列2、句構造木、依存木、意味依存木の4種を用い、それぞれ、語品詞トレリス、統語森、(機能)依存森、意味依存森の4つの圧縮共有データ構造で接続している。各データ構造は、隣接するデータ構造との対応関係を持ち、意味構造とテキスト(文)のマッピングが規定される。PDGの開発では、構文レベルまでをカバーする構文解析版PDGと意味レベルまでをカバーする意味解析版PDGの2段階を想定しており、各層の選好知識のスコアは、前者では(機能)依存森、後者では意味依存森に集約され、依存森から文に対する最適解釈が探索される。

本稿で提案する「依存森」は、次のPDGの特長を実現するキーとなるデータ構造である。

(a)構文層において、句構造と依存構造の両者を解釈記述スキーマとして統合利用する

(b)構文層と意味層を依存構造に基づく圧縮共有構造で橋渡しする

(c)制約知識と選好知識を統合した最適解探索を実現する

句構造と依存構造は、文の構文構造をそれぞれ異なった側面から表現する代表的記述スキーマであり、その統合利用により両者の利点を活用できる。統合利用には、句構造と依存構造のマッピングが必要であるが、従来、これを目的とする研究はあまり例がない。構文グラフ【Seo&Simmons 89]は、両者のマッヒ。ング手法を提案しているが、対応関係が不完全であり、MPDCモデルに利用できない(後述)。依存森は、構文グラフの問題を解決することにより、従来手法では困難であった(a)を実現した[平川06a]。これにより、(b)の構文層と意味層の橋渡しが可能となり、図1の実装モデルを実現している。また、依存森は、制約知識と選好知識を記述するための制約/選好マトリックスを有し(後述)、各層の制約知識と選好知識がこの上で統合される。グラフ分枝法と呼ぶ新規提案のアルゴリズムにより、任意の依存関係間の制約条件を満足する最適な解を依存森から探索可能である。

3.圧縮共有データ構造

[問題設定]1図1のPDG実装モデル実現のための圧縮共有データ構造を設定する。語品詞系列と句構造木に対しては、それぞれ既存のデータ構造、即ち、語品詞トレリスと統語森が利用できるが、依存木、意味依存木に対する適切なデータ構造が必要である。

[従来技術・課題]構文解析を行い圧縮共有型の依存構造を生成する手法として、意味依存グラフ[平川 02]、構文グラフが提案されているが、前者は日本語を前提とし汎用性に欠け、後者は句構造木と依存木の完全で健全な対応がとれないという問題3があり、MPDCモデルに利用できない。

[新手法の提案]これらを解決するデータ構造として依存森を提案する(図2)。依存森は、ノードとスコア付きアークからなる依存グラフとアークの共起関係を規定する制約マトリックスから構成される圧縮共有データ構造であり4、書き換え規則と部分依存構造よりなる拡張文脈自由文法規則を用いて、(a)チャート法に基づく構文解析によるヘッド付き統語森の生成、(b)ヘッド付き統語森からの依存森の生成、(c)依存森の縮退処理(コンパクト化)の3つの処理により構築される。統語森と依存森の間には、完全性と健全性が成立し5、MPDCモデルに利用可能である。また、依存森は、任意のアーク間の共起関係を記述可能であり、非交差制約を満たさない依存構造(Non-projective dependency)なども扱えるという柔軟性を持つ。

4.最適解探索

[問題設定]依存森から最適な解釈(依存木)を探索するタスクは、「スコア付き依存グラフから依存木の整合性を規定する制約条件を満足する最大のスコアを持つ木の探索」として形式化される(図3)。この枠組みのもとで従来様々な依存グラフに対する探索法が提案されている。

[従来技術・課題]言語非依存の基本的な依存木整合制約条件には、

(a)被覆制約:入力文中の全ての語に対応するノードが依存木に存在する

(b)単一役割制約:依存木中のノードは1つの単語に対応する

(c)非交差制約:依存関係の交差が存在しない

(d)多重格禁止制約:述語の格スロットは1つの要素のみが占有する

などが存在する。(a),(b)を満足するChu-Liu-Edmonds法は高速である[McDonald O5]が、語品詞からなる依存グラフ(依存森など)に適用できないという問題がある。Dynamic Programmingをべ一スとするアルゴリズムで(a)~(c)を満足する手法が広く提案・利用されているが、(d)や依存森の制約マトリックスの任意の共起制約を扱えないという問題がある。

[新手法の提案]依存森は、高い制約記述能力を持つため従来手法では最適解の探索が困難である。このため、PDGでは、分枝限定法6に基づき依存森から制約マトリックスを満足する最適解を計算する「グラフ分枝アルゴリズム」を提案する[平川 06b]。

更に、PDGでは、選好スコアの記述の枠組についても従来型(図3)のアークスコアのみのモデル(単項選好モデル)からアーク共起の選好スコアも加えたモデル(二項選好モデル)に拡張し、記述力を強化した。二項選好モデルの依存森は、依存グラフ、制約マトリックス、選好マトリックスより構成される。グラフ分枝アルゴリズムは、二項選好モデルに適応可能である。

[評価実験]グラフ分枝アルゴリズムの計算量は、指数関数オーダーであるが、分枝限定法の上界値関数や許容解関数を最適化することにより、早期の段階で最適解に到達する(平均問題展開数が1.43/文)ことが実験より示され(図4)、性能的見通しが得られた。また、「部分問題展開数を10に限定する」という戦略を採用した場合に、実験では、99.8%の文において1つ以上の最適解が得られた。

5.スコアリング

スコアリングは、各レベルの選好知識を依存森の選好マトリックスのスコア(単項モデルの場合はアークスコア)に統合する処理である。現状のスコアリング方式では、各レベルの選好知識を単項ノード、単項アーク、二項ノード、二項アークの4種類の選好スコアにヒューリスティック関数を用いて変換し、統合する。

6.実験評価

英語技術文12.5万文をクローズドデータとオープンデータに分割し、既存の文解析システムを用いて前者より選好知識データ(語品詞頻度、依存アーク頻度、語品詞BIGRAM頻度、依存アーク共起頻度)を、後者より正解依存木データを抽出した。また、構文解析版PDGを実装し、英語基本文法(907CFG規則)を用いて、選好知識統合による解析精度の向上実験、選好知識による解の絞込み能力測定実験などを実施した。選好知識統合実験(図5)では、単項ノードと単項アークならびに単項アークと二項ノードの2つの組合せが最高のアーク正解率788.3%を示した。これは、べースライン(選考知識無し)に対して10.9%の改善となり、選好知識統合利用の効果が確認された。

7.今後の課題

各処理の最適化やC言語実装などによるPDG実システムの開発、意味構造への展開、双方向モデルの検討などが今後の主な研究課題である。

自然言語文解析システムにおいては、入力文に対して既知の言語知識を適用して最も適切な解釈を出力することが目的となる。一般に、自然言語文解析システムは、形態素、構文、意味、文脈の各層において有効となる言語知識を扱う必要があり、各層の知識記述の方法として、句構造木、依存木、述語論理式など様々な文解釈記述枠組みが提案されている。これらの枠組みは、知識記述の質や能力、すなわちシステムの性能を規定する。したがって、どのような枠組みを採用するかは自然言語文解析システム設計上重要な課題の1つである。また、言語知識は、計算機処理の視点から見て、入力文に対して不可能な解釈を排除する「制約知識」と可能な解釈の優先順序付けを行う「選好知識」の2種類に分類される。制約知識は自然言語の各層で生じる解釈の組み合わせ爆発の抑制に有効であるが、その過度の適用は正解解釈の枝刈りによる性能劣化を引き起こしてしまう。一方、自然言語の各層の選好知識は、相異なる解釈を支持することもあり、全体として最適な解を得るためには各層の知識を統合評価する必要がある。このように、多層の知識、制約/選好知識の統合をいかに行うかは、実用的な自然言語文解析システム設計において解決すべき重要な課題である。

本論文は「Preference Dependency Grammar(PDG): Sentence Analysis Method Based on Integrated Multilevel Preference and Constraint (邦訳:選好依存文法:多層の選好/制約知識を統合した文解析方式)」と題し、英文で書かれ、上記の自然言語文解析システム設計における課題を解決する方法に関して論じたものであり、下記に示す8章からなる。

第1章(Introduction)では、自然言語文解析システム研究における背景、特に句構造文法と依存構造文法、ならびに、その解析手法(句構造解析と依存構造解析)について概観し、問題点を指摘し、さらに本論文で展開する解決策の方針を示している。

第2章(Sentence Analysis Model and the PDG design)では、上記の問題点を解決するための多レベルの言語知識を統合する文解析モデルについて検討し、PDGのシステムの概要について述べている。

第3章(Packed Shared Data Structures )は、PDGの圧縮共有データ構造とその構成法、特に、構文層の2つのデータ構造である句構造森と依存森について述べている。依存森は、依存木の集合を表す新たなデータ構造であり、依存グラフ、制約マトリックス、選好マトリックスから構成される。その最大の特徴は、本章で証明した句構造森とのマッピングにおける完全性と健全性、すなわち句構造木と依存木が相互に対応を持つことである。これによって、句構造と依存構造レベルを持つ多レベル圧縮共有データ結合モデルを実現可能となった。

第4章(Optimum Solution Search )では、依存森として統一的に表現された構文構造の集合から最適な依存構造を探索すること、すなわちスコア付き依存グラフから依存木の整合性を規定する制約条件を満足する最大のスコアを持つ木の探索を行う探索アルゴリズムを提案している。具体的には、分枝限定法に基づくグラフ分枝アルゴリズムを提案し、被覆制約、単一役割制約、非交差制約、多重格禁止制約などの制約を充足する最適依存木を99.8%の文で得ることを実証するとともに、組み合わせ爆発に対応する枝刈り手法の性能も優れていることを実験的に示した。

第5章(Scoring)では、多層の選好知識を依存森の選好知識表現に統合する方法を提案した。

第6章(Evaluation)では、ここまでで提案してきたアルゴリズムを英語技術文 12.5万文を用いて実験的に評価している。まず、907個の規則からなる英語基本文法による構文解析器を実装し、選好知識を統合することによって、選好知識のない場合に比べて、構文構造のアークの正解率で10.9%を改善した88.3%の正解率を達成した。

第7章(Future Work)では、今後の課題として、実システムの開発、意味処理への展開、解析・生成の双方向モデルの検討の3点をあげている。

第8章(Conclusion)は、本論文のまとめである。

以上を要するに、本論文は多層の選好/制約知識を統合した自然言語文の処理に関して、依存森と統語森の対応付けを証明し、その両者における選好/制約を活用する効率の良い解析アルゴリズムを提案するとともに、実際のシステムを構築し性能の改善を評価実験によって示したもので、計算機科学の発展に寄与するところが大きい。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。