基本木獲得装置、構文解析装置、方法、及びプログラム
【課題】メモリの消費量を抑制しつつ、あらゆる言語の構文木コーパスに対応する。
【解決手段】ラベル付与部１５で、基本木ｅ（ｕ）の情報に基づいて、接合操作に関する内容を含む木接合文法に従った非終端ノードの内容を示すラベルを、構文木各々の各非終端ノードに付与し、構文木分解部１６で、ラベルが付与された構文木を、深さ１の部分木に分解すると共に、ラベルの内容及び推定する確率モデルに基づいて各部分木の生成確率を計算する。内側確率計算部１８で、部分木の生成確率に基づいて、非終端ノード毎に内側確率を計算し、基本木サンプリング部２０で、非終端ノード毎の内側確率に基づいて、新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで新たな基本木の生成を繰り返し、構文木が観測された下での基本木の事後確率が最大となるときの基本木、及び確率モデルのパラメータを獲得する。
【解決手段】ラベル付与部１５で、基本木ｅ（ｕ）の情報に基づいて、接合操作に関する内容を含む木接合文法に従った非終端ノードの内容を示すラベルを、構文木各々の各非終端ノードに付与し、構文木分解部１６で、ラベルが付与された構文木を、深さ１の部分木に分解すると共に、ラベルの内容及び推定する確率モデルに基づいて各部分木の生成確率を計算する。内側確率計算部１８で、部分木の生成確率に基づいて、非終端ノード毎に内側確率を計算し、基本木サンプリング部２０で、非終端ノード毎の内側確率に基づいて、新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで新たな基本木の生成を繰り返し、構文木が観測された下での基本木の事後確率が最大となるときの基本木、及び確率モデルのパラメータを獲得する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基本木獲得装置、構文解析装置、方法、及びプログラムに係り、特に、統語的な情報が付与された構文木のコーパスから、木接合文法に基づく基本木を自動獲得する基本木獲得装置、方法、及びプログラム、並びに、獲得された基本木を用いて構文解析を行う構文解析装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
文法獲得とは、データから文法的枠組みに基づいた生成規則を獲得することをいう。従来より、統語的な情報が付与された構文木コーパスから、その構文木を構成する生成規則を確率的に獲得する方法が提案されている。文法の枠組みには、例えば、文脈自由文法、木接合文法や文脈依存文法などがある。
【０００３】
木接合文法とは、後述する基本木を生成規則とし、これらを組み合わせることにより構文木を生成する文法の枠組みである。構文木の例を図１に、基本木の例を図２に示す。以降、各基本木について、木構造の根に相当するノードをルートノード、末端に位置するノードを葉ノード、それ以外のノードを中間ノードと呼ぶ。また、各ノードに付与されたタグをシンボルと表現する。さらに、“ｔｈｅ”、“ｐｒｅｔｔｙ”などの単語を終端記号、それ以外の“ＮＰ”、“ＶＰ”などの文法的な情報を表すタグを非終端記号と表現し、終端記号が付与されたノードを終端ノード、非終端記号が付与されたノードを非終端ノードと表現する。
【０００４】
基本木は、初期木及び補助木の二種類に分類される。初期木は、例えば図３に示すように、置換操作と呼ばれるシンボルの書き換えによって他の木と結合する。また、補助木は、例えば図４に示すように、接合操作と呼ばれる木の割り込みによって他の木と結合する。補助木は、必ずルートノードと同じシンボルである葉ノードを持つ。
【０００５】
従来の木接合文法の獲得方法には、大きく分けると二種類ある。一つは、基本木の型（パターン）を予め定義しておき、ＥＭアルゴリズムなどの方法で構文木から基本木の確率を推定するものである（例えば、非特許文献１参照）。二つ目の方法は、言語学的な知識に基づいて、発見的な方法により基本木を直接獲得した後に、それらの確率を最尤推定によって求める方法である（例えば、非特許文献２参照）。また、近年の自動文法獲得方法には、木置換文法に基づいた方法がある（例えば、非特許文献３参照）。木置換文法は、初期木による置換操作のみで構文木を生成する方法である。非特許文献３に開示されている木置換文法の自動獲得方法は、どのような言語のコーパスにも適用できるという利点がある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Fei Xia (1999) Extracting tree adjoining grammars from bracketed corpora, In Proceedings of the 5th Natural Language Processing Pacific Rim Symposium (NLPRS), pages 398-403.
【非特許文献２】David Chiang, (2003) Statistical Parsing with an Automatically Extracted Tree Adjoining Grammar, pages 299-316. CSLI Publications.
【非特許文献３】Trevor Cohn, Sharon Goldwater, and Phil Blunsom (2009) Inducing compact but accurate treesubstitution grammars, In Proceedings of HLT-NAACL, pages 548-556, Boulder, Colorado, June. Association for Computational Linguistics.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１のような方法では、予め定義された型に当てはまる基本木しか獲得することができないため、言語毎に基本木の型を定義する必要があり、汎用性に欠ける、という問題がある。また、非特許文献２のような発見的な方法による基本木の獲得の場合も、言語学的な知見に基づいているため、対象言語が変わると同じ獲得方法を適用できない可能性がある、という問題がある。英語や中国語などのよく知られた言語以外でも、同じ方法で基本木を自動獲得できることが望ましい。
【０００８】
また、非特許文献３に開示されている木置換文法の自動獲得方法は、言語の種類に依存しない汎用的な方法であるが、木置換文法では置換操作だけで構文木を構成するため、多くの初期木を獲得してしまい、メモリを多く消費してしまう、という問題がある。
【０００９】
本発明は、上記問題点を解決するために成されたものであり、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる基本木獲得装置、構文解析装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明の基本木獲得装置は、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与する付与手段と、各部分木の深さが１となるように前記構文木を部分木に分解する分解手段と、前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出する算出手段と、前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返す生成手段と、前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する獲得手段と、を含んで構成されている。
【００１１】
本発明の基本木獲得装置によれば、付与手段が、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを各非終端ノードに付与し、分解手段が、各部分木の深さが１となるように構文木を部分木に分解する。
【００１２】
そして、算出手段が、構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、非終端ノード毎に内側確率を算出し、生成手段が、非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで新たな基本木の生成を繰り返す。獲得手段は、事後確率が最大となるときの生成手段により生成された基本木、及び確率モデルの所定のパラメータを獲得する。
【００１３】
このように、構文木の各非終端ノードに、接合操作も導入した木接合文法に基づく内容を示すラベルを付与し、このラベルに基づいて構文木を深さ１の部分木に分解し、各部分木の生成確率に基づくノード毎の内側確率を用いて新たな基本木を生成し、構文木が観測された下での基本木の事後確率が最大となる基本木を獲得するため、言語に依存しない基本木の獲得を行うことができ、また、接合操作の導入により、獲得される基本木の数を削減することができるため、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる。
【００１４】
また、前記確率モデルは、前記保持した基本木の情報に基づいて基本木を生成する第１確率、及び前記基底分布に基づいて基本木を生成する第２確率を用いて表され、前記第１ラベルが付与された非終端ノードは、前記第２確率に従って生成された非終端ノードであり、前記第２ラベルが付与された非終端ノードは、前記第１確率に従って生成され非終端ノードであり、前記第３ラベルが付与された非終端ノードは、前記第１確率で前記第２ラベルが示す内容の非終端ノードを生成し、前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成し、前記第４ラベルが付与された非終端ノードは、所定の接合確率及び前記第１確率に従って前記第２ラベルが示す内容の非終端ノードを生成し、前記所定の接合確率及び前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成する。
【００１５】
また、前記獲得手段は、メトロポリス・ヘイスティングス法により、前記生成手段により生成された新たな基本木を受理または棄却すると共に、前記確率モデルのパラメータを更新し、前記パラメータの更新を所定回数以上行った場合には、現在の基本木及び更新されたパラメータを獲得し、前記パラメータの更新を所定回数以上行っていない場合には、前記現在の基本木を前記分解手段に入力すると共に、前記更新されたパラメータを前記確率モデルに設定することができる。
【００１６】
また、本発明の構文解析装置は、上記の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータを記憶する記憶手段と、前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する解析手段と、を含んで構成されている。また、本発明の構文解析装置は、上記の基本木獲得装置を含んで構成してもよい。
【００１７】
また、本発明の基本木獲得方法は、付与手段と、分解手段と、算出手段と、生成手段と、獲得手段とを含む基本木獲得装置における基本木獲得方法であって、前記付与手段は、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、構文木を構成する複数の基本木各々の各非終端ノードにラベルが付与されていない場合には、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与し、前記分解手段は、各部分木の深さが１となるように前記構文木を部分木に分解し、前記算出手段は、前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出し、前記生成手段は、前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返し、前記獲得手段は、前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する方法である。
【００１８】
また、本発明の構文解析方法は、記憶手段、及び解析手段を含む構文解析装置における構文解析方法であって、前記記憶手段には、上記の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータが記憶され、前記解析手段は、前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する方法である。
【００１９】
また、本発明の基本木獲得プログラムは、コンピュータを、上記の基本木獲得装置を構成する各手段として機能させるためのプログラムである。
【００２０】
また、本発明の構文解析プログラムは、コンピュータを、上記の構文解析装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００２１】
以上説明したように、本発明の基本木獲得装置、構文解析装置、方法、及びプログラムによれば、構文木の各非終端ノードに、接合操作も導入した木接合文法に基づく内容を示すラベルを付与し、このラベルに基づいて構文木を深さ１の部分木に分解し、各部分木の生成確率に基づくノード毎の内側確率を用いて新たな基本木を生成し、構文木が観測された下での基本木の事後確率が最大となる基本木を獲得するため、言語に依存しない基本木の獲得を行うことができ、また、接合操作の導入により、獲得される基本木の数を削減することができるため、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】構文木の一例示す図である。
【図２】基本木の一例を示す図である。
【図３】置換操作を説明するための図である。
【図４】接合操作を説明するための図である。
【図５】各非終端ノードにラベルが付与された構文木の一例を示す図である。
【図６】深さ１に分解された部分木及びその部分木の生成確率の一例を示す図である。
【図７】第１の実施の形態の基本木獲得装置の機能構成を示すブロック図である。
【図８】内側確率テーブルを示す図である。
【図９】第１の実施の形態の基本木獲得装置における基本木獲得処理ルーチンの内容を示すフローチャートである。
【図１０】第２の実施の形態の構文解析装置の機能構成を示すブロック図である。
【図１１】第２の実施の形態の構文解析装置における構文解析処理ルーチンの内容を示すフローチャートである。
【図１２】効果確認結果を示す表である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２４】
＜本実施の形態の確率モデル＞
文法獲得（基本木の獲得）の問題は、与えられた構文木ｔから、ｔを構成する基本木の集合ｅを獲得することである。構文木が与えられたとき、基本木の事後確率ｐ（ｅ｜ｔ；Φ）は、ベイズの定理を用いて、下記（１）式のように計算できる。
【００２５】
【数１】
【００２６】
木接合文法では、初期木または補助木を一つずつ生成し、全ての葉ノードが終端記号、すなわち単語になったときに生成を停止する。全ての葉ノードが終端記号になったとき、これらの終端記号列が構文木ｔと一致するとき、ｐ（ｔ｜ｅ）＝１となり、そうでない場合はｐ（ｔ｜ｅ）＝０となる。一つずつ生成される基本木ｅを、インデックスｉを用いてｅｉ（ｉ＝１，２，・・・）とする。
【００２７】
本実施の形態では、非特許文献４（Y.W. Teh(2006) A Bayesian Interpretation of Interpolated Kneser-Ney. Technical Report TRA2/06, School of Computing, NUS.）に開示されているベイズモデルを用いて、ｐ（ｅ）をモデル化する。このモデルは、基本木ｅｉが、今までに生成された基本木ｅ１，・・・，ｅｉ−１ に依存するモデルであり、下記（２）式のように定義される。
【００２８】
【数２】
【００２９】
ただし、ｅ−ｉ＝ｅ１，・・・，ｅｉ−１は、１回目から（ｉ−１）回目までに生成された基本木の集合である。Ｘは基本木ｅｉのルートシンボルを表す。また、αｅｉ，Ｘ及びβＸは、下記（３）式で表される。
【００３０】
【数３】
【００３１】
ｎ−ｉｅｉ，Ｘは、ｅ−ｉのうちｅｉと同じ基本木が何回生成されたかを表す。また、この確率モデルは、内部で各基本木が何回生成されたかという情報を、いくつかのクラスタに分けて保存する。例えば、ある基本木がこれまでに１０回生成されたとすると、この確率モデルの内部では、（３回，７回）という２つのクラスタになって保持している場合もあれば、（２回，３回，５回）のように３つのクラスタになっている場合もある。このとき、ｔｅｉ，Ｘは、基本木ｅｉがモデル内部でいくつのクラスタに分割されているかを表す。また、ｎ−ｉ・，Ｘ及びｔ・，Ｘは、下記（４）式で表される。
【００３２】
【数４】
【００３３】
この確率モデルは、Ｐｉｔｍａｎ−Ｙｏｒ過程と呼ばれ、非特許文献４に詳細が開示されている。
【００３４】
本実施の形態では、初期木及び補助木の確率分布をそれぞれ独立に（２）式で定義する。以降、初期木の確率モデルのパラメータを｛ｄＸ，θＸ｝、補助木の確率モデルのパラメータを｛ｄ’Ｘ，θ’Ｘ｝と区別する。同様に、（２）式の変数をそれぞれ｛αｅｉ，Ｘ，βＸ｝、｛α’ｅｉ，Ｘ，β’Ｘ｝と区別する。初期木による置換操作は、葉ノードが非終端記号であれば確率１で必ず実行される。一方で、補助木の接合操作は中間ノードに対して実行される場合と実行されない場合とがある。そこで、接合確率ａＸを新たに導入すると、補助木ｅｉが中間ノードＸに対して接合される確率は、下記（５）式となる。
【００３５】
【数５】
【００３６】
また、（２）式中のＰ０（ｅｉ｜Ｘ）は、基底分布と呼ばれ、基本木ｅｉの基底となる確率分布である。したがって、ΣｅｉＰ０（ｅｉ｜Ｘ）＝１を満たす必要がある。基底分布の実現例として、例えば、下記（６）式のように定義することができる。
【００３７】
【数６】
【００３８】
ただし、ＣＦＧ（ｅｉ）は、ｅｉを深さが１の部分木に分解した生成規則の集合を表す。例えば、ｒが二分木の場合、Ａ→ＢＣという形式をとる。ここで、Ａはルートノード、Ｂ及びＣはＡの子ノードである。ＰＭＬＥ（ｒ）は、生成規則ｒの最尤推定値であり、例えば、ｒ＝Ａ→ＢＣとき、下記（７）式のように計算することができる。
【００３９】
【数７】
【００４０】
ただし、ｃｏｕｎｔ（Ａ）はコーパス中にシンボルＡが何回出現したかを表し、ｃｏｕｎｔ（Ａ→ＢＣ）はコーパス中に生成規則Ａ→ＢＣが何回出現したかを表す。ＬＥＡＦ（ｅｉ）、ＩＮＴＥＲＮＡＬ（ｅｉ）はそれぞれ、ｅｉの葉ノード及び中間ノードの集合を表す。例えば、ｅｉを図２（ｃ）とすると、ＣＦＧ（ｅｉ）＝｛ＮＰ→ＤＴ Ｎ，Ｎ→ｇｉｒｌ｝、ＬＥＡＦ（ｅｉ）＝｛ＤＴ，ｇｉｒｌ｝、ＩＮＴＥＲＮＡＬ（ｅｉ）＝｛Ｎ｝となる。ｓＸは、停止確率と呼ばれ、初期木または補助木の生成がノードＸで停止する確率を表す。
【００４１】
本実施の形態の基本木獲得装置では、事後確率ｐ（ｅ｜ｔ；Φ）を最大にする基本木ｅ及びパラメータセットΦ＝｛ｄＸ，θＸ，ｓＸ，ａＸ｝を学習する。
【００４２】
＜本実施の形態における構文木の分解＞
（２）式に基づいて構文木を生成するために、本実施の形態では、構文木中の各非終端ノードを、そのノードの内容に従って、以下のように４つのタイプ（Ｘ（ｂａｓｅ）、Ｘ（ｅ）、Ｘｓｕｂ、Ｘａｄｊ（ｔｙｐｅ））に分類し（下記［タイプ１］〜［タイプ４］）、タイプに応じたラベルを付与する。なお、Ｘは非終端ノードに付与されたシンボルである。また、基本木を生成する際に、それが（２）式の第１項目（αｅｉ，Ｘ）からの生成なのか、第２項目（βＸＰ０（ｅｉ｜Ｘ））からの生成なのかを区別する。第１項目からの生成は、以前生成した基本木ｅ−ｉの中から、確率的にいずれかを選択することに相当する。一方で、第２項目からの生成は、基底分布Ｐ０（ｅｉ｜Ｘ）に従って新たに基本木を生成する。基底分布から新たに生成された基本木は、以前生成された基本木のいずれかと一致する場合もあれば、今までに生成したことのない基本木であることもある。
【００４３】
ここで、タイプ別のラベル毎に、各非終端ノードの内容を示す。
【００４４】
［タイプ１］Ｘ（ｂａｓｅ）：基底分布、すなわち（２）式の第２項目から生成された基本木のルートノードまたは中間ノードを表す。このノードは、基底分布Ｐ０に従って基本木を生成するノードである。
【００４５】
［タイプ２］Ｘ（ｅ＊）：（２）式の第１項目から生成された基本木のルートノードまたは中間ノードを表す。ｅ＊は基本木の情報を格納した変数であり、例えば、図２（ｃ）の場合、ｅ＊＝ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ）と表され、Ｘ＝ＮＰとなる。この場合、ＮＰ（ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ））は、基本木の情報ｅ＊＝ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ）に従って、ＮＰ（ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ））→（ＤＴ）（Ｎ ｇｉｒｌ）という規則を生成する。同様に、Ｎ（Ｎ ｇｉｒｌ）は、Ｎ（Ｎ ｇｉｒｌ）→ｇｉｒｌという規則を生成する。これにより、図２（ｃ）の基本木を、Ａ→ＢＣという深さが１の部分木の組み合わせで生成することが可能となる。
【００４６】
［タイプ３］Ｘｓｕｂ：置換操作が起こったノードを表す。このノードは、確率αｅｉ，ＸでＸ（ｅ） を生成し、確率βＸでＸ（ｂａｓｅ）を生成する。
【００４７】
［タイプ４］Ｘａｄｊ（ｔｙｐｅ＊）：接合操作が起こったノードを表す。ｔｙｐｅ＊は、上記のｂａｓｅまたはｅ＊のいずれかが入る変数であり、接合操作によって割り込まれる前のノードがＸ（ｔｙｐｅ＊）であったことを意味する。このノードは、確率α’ｅｉ，ＸでＸａｄｊ（ｔｙｐｅ＊）（ｅ＊）を生成し、確率β’ＸでＸａｄｊ（ｔｙｐｅ＊）（ｂａｓｅ）を生成する。例えば、Ｘａｄｊ（ｔｙｐｅ＊）（ｅ＊）は、ノードＸ（ｔｙｐｅ＊）に対して、（２）式の第１項目から生成された補助木ｅが接合されたことを意味する。図４に示すように、接合操作によって割り込まれたノード及びその子ノードは、補助木の葉ノードと結合されるため、Ｘａｄｊ（ｔｙｐｅ＊）（ｅ＊）、Ｘａｄｊ（ｔｙｐｅ＊）（ｂａｓｅ）はどちらもＸ（ｔｙｐｅ＊）を葉ノードとして生成する。
【００４８】
構文木データの各非終端ノードを、上記の４つのいずれかのタイプに分類すれば、構文木を構成する基本木の集合が確定される。ただし、観測データとして得られる構文木コーパスには、これらのタイプはラベル付けされていないため、学習によってこれらのタイプを推定する。一例として、図４に示すように１つの初期木（ＮＰ（ＤＴ ｔｈｅ）（Ｎ ｇｉｒｌ））と、１つの補助木（Ｎ（ＪＪ ｐｒｅｔｔｙ）（Ｎ））とで構成される構文木を考える。この構文木の各非終端ノードシンボルを上記の４つのタイプに分類した例を図５に示す。そして、このラベルが付与された構文木を深さが１の部分木に分解する。深さが１の部分木とは、その部分木が示す生成規則がＡ→ＢＣのように表せる（親ノード及び子ノードのみで表せる）部分木をいう。各部分木が表す生成規則に対して生成確率を図６のように定義すると、（２）式に従って基本木を生成することと等しくなる。例えば、［タイプ３］のラベルが付与されたノードＸｓｕｂは置換操作が起こったノードなので、確率αｅｉ，ＸでＸ（ｅ＊）を生成し、確率βＸでＸ（ｂａｓｅ）を生成するように設定する。これは、（２）式の第１項目から基本木を生成するのか、または第２項目から生成するのかを確率的に選ぶことに相当する。このように、全ての構文木を深さが１の部分木に分解し、部分木毎に適切な生成確率を割り当てる操作が構文木の分解である。
【００４９】
＜基本木獲得装置の構成＞
次に、構文木コーパスを訓練データとして、基本木を獲得する基本木獲得装置に本発明を適用した場合を例にして、第１の実施の形態を説明する。
【００５０】
第１の実施の形態の基本木獲得装置は、ＣＰＵと、ＲＡＭと、後述する基本木獲得処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このコンピュータは、機能的には、図７に示すように、木接合文法学習部１２を構成している。木接合文法学習部１２は、構文木ｔが観測された下での基本木の集合ｅの事後確率を示す確率モデルｐ（ｅ｜ｔ；Φ）のパラメータΦを指定回数だけ逐次更新することで、最適な基本木の集合＾ｅ及び最適なパラメータ＾Φを求めるものである。以下、基本木の集合及びパラメータの初期値をｅ（０）及びΦ（０）とし、ｕ回目の更新後の基本木の集合及びパラメータをとｅ（ｕ）及びΦ（ｕ）と表記する。
【００５１】
木接合文法学習部１２は、初期基本木及び初期パラメータを設定する基準基本木設定部１４と、基本木の情報に基づいて構文木にラベル付与を行うラベル付与部１５と、ラベルが付与された構文木を部分木に分解する構文木分解部１６と、各部分木の生成確率に基づいて各ノードの内側確率を計算する内側確率計算部１８と、各ノードの内側確率に基づいて、新たな基本木を生成する基本木サンプリング部２０と、新たな基本木を受理するか棄却するかを判定する受理棄却判定部２２と、確率モデルのパラメータを更新するパラメータ更新部２４と、学習処理を終了するか否かを判定する終了判定部２６と、を含んだ構成で表すことができる。
【００５２】
基準基本木設定部１４は、構文木コーパス｛ｔ｝のデータを読み込む。構文木コーパスとは、文にＮＰやＶＰなどの文法的な役割が付与された木構造（構文木）で構成されるコーパスである。なお、ここで読み込む構文木コーパス｛ｔ｝の各非終端ノードには、上述の［タイプ１］〜［タイプ４］のどのタイプに該当するかのラベルは付与されていない。構文木コーパス｛ｔ｝は、基本木獲得装置１０の訓練データ記憶部（図示省略）に予め記憶しておくことができる。また、外部装置に記憶された構文木コーパス｛ｔ｝を、ネットワーク等を介して読み込むようにしてもよい。基準基本木設定部１４は、読み込んだ構文木コーパス｛ｔ｝に対して、初期基本木ｅ（０）及び初期パラメータΦ（０）を設定する。
【００５３】
ラベル付与部１５は、基準基本木設定部１４により設定された基本木の集合ｅ（０）、または後述の終了判定部２６から出力された基本木の集合ｅ（ｕ）の情報に基づいて、構文木コーパスに含まれる全ての構文木ｔの各非終端ノードに対して、上述の［タイプ１］〜［タイプ４］のいずれかのラベルを付与する。ラベルの情報は基本木の情報と１対１に対応しているため、ラベル付与は確定的に行うことができる。
【００５４】
構文木分解部１６は、各構文木を、深さが１の単純な部分木に分解し、各部分木が表す生成規則に対して、例えば図６に示すような生成確率を計算する。各部分木の生成確率は、各部分木を構成するルートノード及び子ノードに付与されたラベルのタイプが示すノードの内容に基づいて計算することができる。また、図６に示した生成確率内のαｅｉ，Ｘやα’ｅｉ，Ｘは、上記（３）式により求めることができる。
【００５５】
内側確率計算部１８は、構文木分解部１６で分解された部分木を用いて、構文木の内側確率を計算する。内側確率ｐＸ，ｉ，ｋとは、非終端ノードＸ（Ｘはこの非終端ノードに付されたシンボル）からあらゆる規則を使って単語列のｉ番目からｋ番目までの連続する領域を出力する確率を指す。なお、内側確率の定義は非特許文献５（K. Lari and S.J. Young (1991) Applications of stochastic context-free grammars using the inside-outside algorithm, Computer Speech & Language, 5(3):237-257.）に開示されている。内側確率は、基本木が深さ１であれば下記（８）式に示すように、再帰的に計算することができる。
【００５６】
【数８】
【００５７】
ただし、ＰＣＦＧ（ｒ：Ｘ→ＹＺ）は、構文木分解部１６で分解された深さが１の部分木Ｘ→ＹＺの生成確率である。また、Ｘ、Ｙ及びＺの各シンボルが付された非終端ノードは、各々上記の４タイプのいずれかに分類された非終端ノードである。各非終端ノードについて内側確率を計算し、計算された内側確率は、例えば、図８に示すようなテーブル形式で保持する。
【００５８】
基本木サンプリング部２０は、内側確率計算部１８により計算された内側確率テーブルに基づいて、トップダウン的に新たな基本木ｅ’を生成する。例えば、ルートノードがＶＰ、単語数がＬの構文木の場合を考える。構文木のルートノードでは必ず初期木による置換が起こるため、ＶＰｓｕｂから基本木の生成を開始する。まず、ＶＰｓｕｂをルートノードとする考え得る全ての基本木ｒ∈ＣＦＧ（ＶＰｓｕｂ）に対して、確率ＰＣＦＧ（ｒ：ＶＰｓｕｂ→ＹＺ）×ｐＹ，０，ｊ×ｐＺ，ｊ＋１，Ｌを計算し、その確率に基づいてランダムに１つの生成規則＾ｒを生成する。なお、ｐＹ，０，ｊやｐＺ，ｊ＋１，Ｌは、内側確率計算部１８で作成した内側確率テーブルを参照することにより値が得られる。次に、生成規則＾ｒに含まれる全ての子ノードについて、同様にランダムに１つの生成規則を生成する。以上の処理を繰り返していき、全ての子ノードが終端記号、すなわち単語となったときに生成を停止する。このようにして得られた生成規則の集合を新たな基本木の集合ｅ’とする。
【００５９】
受理棄却判定部２２では、基本木サンプリング部２０で新たに生成された基本木の集合ｅ’を受理するか、または棄却するかを、メトロポリス・ヘイスティングス法を用いて確率的に決定する。メトロポリス・ヘイスティングス法は、非特許文献６（Mark Johnson, Thomas L. Griffiths and Sharon Goldwater (2007) Bayesian Inference for PCFGs via Markov Chain Monte Carlo, The Conference of the NAACL; Proceedings of the Main Conference, pages139-146.）に詳細が開示されている。基本木の集合ｅ’が受理された場合には、現在の基本木ｅ（ｕ）を、新たに生成された基本木ｅ’に置き換える。棄却された場合には、基本木サンプリング部２０で新たに生成された基本木ｅ’は棄却され、現在の基本木ｅ（ｕ）をそのまま保持する。新たな基本木ｅ’を受理する確率は、下記（９）式により計算する。
【００６０】
【数９】
【００６１】
ただし、基本木サンプリング部２０で現在扱っている文をｌとし、ｅ−ｌはｌ以外の全ての文の構文木を構成する基本木の集合を表す。ｗｌは、現在扱っている文ｌの単語列である。
【００６２】
パラメータ更新部２４は、非特許文献５に開示されている方法を用いて、以下のようにハイパーパラメータ（ｄＸ，θＸ，ｄ’Ｘ，θ’Ｘ，ｓＸ，ａＸ）を更新する。
【００６３】
【数１０】
【００６４】
また、（〜ｄ１，〜ｄ２，〜θ１，〜θ２，〜ｓ１，〜ｓ２，〜ａ１，〜ａ２）は、予め設定された値である。
【００６５】
終了判定部２６は、現在の学習ステップｕが事前に設定された値ｕｔｈと一致するか否かを判定することにより、学習過程を終了するか否かを判定する。ｕｔｈには予め学習過程の所定の更新回数を定めておく。ｕがｕｔｈと一致する場合には、更新されたパラメータΦ（ｕ）を最適なパラメータ＾Φとし（＾Φ←Φ（ｕ））、現在の基本木の集合ｅ（ｕ）を最適な基本木の集合＾ｅとして（＾ｅ←ｅ（ｕ））、学習過程を停止する。ｕ＜ｕｔｈの場合、すなわち、予め定めた所定の更新回数分の学習過程をまだ終了していない場合には、学習ステップｕを１インクリメントして（ｕ←ｕ＋１）、更新されたパラメータΦ（ｕ）及び基本木ｅ（ｕ）を再度、ラベル付与部１５へ出力する。
【００６６】
＜基本木獲得装置の作用＞
次に、第１の実施の形態に係る基本木獲得装置１０の作用について説明する。基本木獲得装置１０のＲＯＭに記憶された基本木獲得プログラムを、ＣＰＵが実行することにより、図９に示す基本木獲得処理ルーチンが実行される。
【００６７】
ステップ１００で、予め訓練データ記憶部に記憶された構文木コーパス｛ｔ｝のデータを読み込み、次に、ステップ１０２で、初期基本木ｅ（０）及び初期パラメータΦ（０）を設定する。
【００６８】
次に、ステップ１０４で、上記ステップ１００で読み込んだ構文木コーパス｛ｔ｝の構文木各々の各非終端ノードに対して、上記ステップ１０２で設定した基本木の集合ｅ（０｝の情報に基づいて、基本木の情報と１対１に対応するラベルの情報に従って、上述の［タイプ１］〜［タイプ４］のいずれかのラベルを付与する。
【００６９】
次に、ステップ１０６で、各構文木を、深さが１の単純な部分木に分解し、各部分木が表す生成規則毎に、各部分木を構成するルートノード及び子ノードに付与されたラベルのタイプが示すノードの内容、及び上記（３）式に基づいて、例えば図６に示すような生成確率を計算する。
【００７０】
次に、ステップ１０８で、上記ステップ１０６で分解された部分木を用いて、非終端ノード毎の内側確率を、上記（８）式に従って計算する。計算された内側確率は、例えば、図８に示すようなテーブル形式で保持する。
【００７１】
次に、ステップ１１０で、構文木のルートノードＸ及び単語数Ｌに基づいて、Ｘｓｕｂをルートノードとする考え得る全ての基本木ｒ∈ＣＦＧ（Ｘｓｕｂ）に対して、確率ＰＣＦＧ（ｒ：Ｘｓｕｂ→ＹＺ）×ｐＹ，０，ｊ×ｐＺ，ｊ＋１，Ｌを計算し、その確率に基づいてランダムに１つの生成規則＾ｒを生成する。この際、ｐＹ，０，ｊやｐＺ，ｊ＋１，Ｌは、上記ステップ１０８で計算された内側確率テーブルを参照することにより値を得る。そして、生成規則＾ｒに含まれる全ての子ノードについて、同様にランダムに１つの生成規則を生成し、全ての子ノードが終端記号となるまで、以上の処理を繰り返す。全ての子ノードが終端記号となった場合には処理を停止し、得られた生成規則の集合を新たな基本木の集合ｅ’とする。
【００７２】
次に、ステップ１１２で、上記ステップ１１０で生成された新たに基本木の集合ｅ’を受理するか、または棄却するかを、メトロポリス・ヘイスティングス法を用いて、例えば（９）式に従って確率的に決定する。基本木が受理された場合には、ステップ１１４へ移行し、現在の基本木ｅ（ｕ）（初回はｅ（０））を、新たに生成された基本木ｅ’に置き換えて、ステップ１１６へ移行する。棄却された場合には、ステップ１１４をスキップして、ステップ１１６へ移行する。
【００７３】
ステップ１１６では、ハイパーパラメータ（ｄＸ，θＸ，ｄ’Ｘ，θ’Ｘ，ｓＸ，ａＸ）を更新する。
【００７４】
次に、ステップ１１８で、現在の学習ステップｕが事前に設定された値ｕｔｈと一致するか否かを判定することにより、学習過程を終了するか否かを判定する。ｕ＜ｕｔｈの場合には、ステップ１２０へ移行して、学習ステップｕを１インクリメントして、ステップ１０４へ戻り、更新されたパラメータΦ（ｕ）及び基本木ｅ（ｕ）を用いて処理を繰り返す。一方、ｕ＝ｕｔｈの場合には、更新されたパラメータΦ（ｕ）を最適なパラメータ＾Φとし、現在の基本木の集合ｅ（ｕ）を最適な基本木の集合＾ｅとして獲得し、獲得結果（＾ｅ，＾Φ）を出力して、処理を終了する。
【００７５】
以上説明したように、第１の実施の形態の基本木獲得装置によれば、構文木の各非終端ノードに、接合操作も導入した木接合文法に基づく内容を示すラベルを付与し、このラベルに基づいて深さ１の部分木に分解し、各部分木の生成確率に基づくノード毎の内側確率を用いて新たな基本木を生成し、構文木が観測された下での基本木の事後確率が最大となる基本木を獲得するため、言語特有の規則などを利用した発見的手法に頼ることなく、言語に依存しない基本木の獲得を行うことができ、また、接合操作の導入により、獲得される基本木の数を削減することができるため、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる。
【００７６】
次に、第２の実施の形態について説明する。第２の実施の形態では、入力された構文解析対象文について構文解析を行う構文解析装置に本発明を適用した場合を例に説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【００７７】
＜構文解析装置の構成＞
第２の実施の形態の構文解析装置２１０は、ＣＰＵと、ＲＡＭと、後述する構文解析処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このコンピュータは、機能的には、図１０に示すように、木接合文法学習部１２と、基本木パラメータ記憶部３０と、構文解析部３２と、を含んだ構成で表すことができる。木接合文法学習部１２は、第１の実施の形態と同様に、基準基本木設定部１４と、ラベル付与部１５と、構文木分解部１６と、内側確率計算部１８と、基本木サンプリング部２０と、受理棄却判定部２２と、パラメータ更新部２４と、終了判定部２６と、を含んだ構成で表すことができる。
【００７８】
基本木パラメータ記憶部３０は、木接合文法学習部１２で獲得された基本木の集合＾ｅ及び確率モデルのパラメータセット＾Φが記憶される。
【００７９】
構文解析部３２は、基本木パラメータ記憶部３０に記憶された基本木＾ｅ及びパラメータ＾Φを用いて、構文木が未知の構文解析対象文Ｓから構文木を推定する。具体的には、パラメータ＾Φを確率モデルに設定し、基本木＾ｅを、構文木分解部１６と同様の処理により深さ１の部分木に分解すると共に、各部分木が表す生成規則の生成確率を計算する。次に、内側確率計算部１８と同様の処理により、非終端ノード毎の内側確率を計算する。そして、基本木サンプリング部２０でトップダウン的に基本木を生成し、生成された基本木の集合で構成される構文木を出力する。構文木が観測されている学習時は、構文木の各ノードにラベルを付与し、それを分解した深さ１の部分木のみを用いて内側確率を計算し、基本木をサンプリングするが、構文解析時は、構文木が不明のため、木接合文法学習部１２で獲得した全ての基本木＾ｅを深さ１の部分木に分解し、その部分木を用いて内側確率を計算し、基本木をサンプリングする。その結果、あらゆる構文木の可能性を考慮することができる。
【００８０】
＜構文解析装置の作用＞
次に、第２の実施の形態に係る構文解析装置２１０の作用について説明する。構文解析装置２１０のＲＯＭに記憶された構文解析プログラムを、ＣＰＵが実行することにより、図１１に示す基本木獲得処理ルーチンが実行される。
【００８１】
ステップ２００で、第１の実施の形態の基本木獲得処理（図９）と同様の処理を実行し、読み込んだ構文木コーパス｛ｔ｝から基本木の集合＾ｅ及び確率モデルのパラメータセット＾Φを獲得し、次に、ステップ２０２で、獲得した基本木の集合＾ｅ及びパラメータセット＾Φを、基本木パラメータ記憶部３０に記憶する。
【００８２】
次に、ステップ２０４で、構文解析対象文Ｓを読み込む。次に、ステップ２０６で、基本木パラメータ記憶部３０から基本木の集合＾ｅ及びパラメータセット＾Φを読み出す。
【００８３】
次に、ステップ２０８で、上記ステップ２０６で読み出したパラメータ＾Φを確率モデルに設定し、基本木＾ｅを深さ１の部分木に分解すると共に、各部分木が表す生成規則の生成確率を計算し、その生成確率に基づいて、非終端ノード毎の内側確率をボトムアップ的に計算する。そして、上記ステップ２０４で読み込んだ構文解析対象文Ｓに対してトップダウン的に基本木を生成して、生成された基本木の集合で構成される構文木を出力する。
【００８４】
以上説明したように、第２の実施の形態の構文解析装置によれば、第１の実施の形態の基本木獲得装置により獲得された基本木及びパラメータを用いて構文を解析するため、メモリの消費量を抑制しつつ、言語に依存しない構文解析を行うことができる。
＜効果確認実験＞
本発明の効果を検証するため、構文解析の実験で広く使われている英語のペンツリーバンクデータを構文木コーパスとして使用し、実際に木接合文法を自動獲得する実験を行った。また、獲得された基本木を用いて構文解析を行い、精度の評価を行った。
【００８５】
予め設定するパラメータ値はそれぞれ、（〜ｄ１，〜ｄ２）＝（１，１），（〜θ１，〜θ２）＝（０．１，１０），（〜ｓ１，〜ｓ２）＝（１，１），（〜ａ１，〜ａ２）＝（１００，１００）とした。
【００８６】
構文木コーパスは、非特許文献４に示されている実験設定と同様に、セクション２から２１までを学習用データとして用いた。評価用データは、セクション２３の構文木情報を取り除いた文を用いた。構文解析の結果は、ＥＶＡＬＢ（ｈｔｔｐ：／／ｎｌｐ．ｃｓ．ｎｙｕ．ｅｄｕ／ｅｖａｌｂ／）を用いてブラケティングＦ値を計算し、評価指標として用いた。この結果を図１２に示す。本実施の形態の基本木獲得装置で獲得された木接合文法の基本木を用いて、本実施の形態の構文解析装置により行った構文解析の評価値Ｆは、文脈自由文法の評価値Ｆを大きく上回った。また、木置換文法よりも約１９％少ない基本木の数で、木置換文法とほぼ同等の精度を得た。従って、本実施の形態が少量の基本木を獲得しつつ、高い精度で構文解析を実行できる効果を確認した。
【００８７】
なお、上記第２の実施の形態では、基本木獲得装置（木接合文法学習部）を備えた構文解析装置について説明したが、基本木獲得装置と、木接合文法学習部を備えない構文解析装置とを別々に構成してもよい。この場合、基本木獲得装置で獲得された基本木及びパラメータを、ネットワーク等を介して、構文解析装置の基本木パラメータ記憶部に記憶するようにするとよい。また、基本木獲得装置に基本木パラメータ記憶部を設けて、獲得した基本木及びパラメータを記憶しておき、構文解析装置から、ネットワーク等を介して、基本木獲得装置の基本木パラメータ記憶部に記憶された基本木及びパラメータを読み出すようにしてもよい。
【００８８】
また、上述の基本木獲得装置及び構文解析装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００８９】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００９０】
１０ 基本木獲得装置
１２ 木接合文法学習部
１４ 基準基本木設定部
１５ ラベル付与部１５
１６ 構文木分解部
１８ 内側確率計算部
２０ 基本木サンプリング部
２２ 受理棄却判定部
２４ パラメータ更新部
２６ 終了判定部
３０ 基本木パラメータ記憶部
３２ 構文解析部
２１０ 構文解析装置
【技術分野】
【０００１】
本発明は、基本木獲得装置、構文解析装置、方法、及びプログラムに係り、特に、統語的な情報が付与された構文木のコーパスから、木接合文法に基づく基本木を自動獲得する基本木獲得装置、方法、及びプログラム、並びに、獲得された基本木を用いて構文解析を行う構文解析装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
文法獲得とは、データから文法的枠組みに基づいた生成規則を獲得することをいう。従来より、統語的な情報が付与された構文木コーパスから、その構文木を構成する生成規則を確率的に獲得する方法が提案されている。文法の枠組みには、例えば、文脈自由文法、木接合文法や文脈依存文法などがある。
【０００３】
木接合文法とは、後述する基本木を生成規則とし、これらを組み合わせることにより構文木を生成する文法の枠組みである。構文木の例を図１に、基本木の例を図２に示す。以降、各基本木について、木構造の根に相当するノードをルートノード、末端に位置するノードを葉ノード、それ以外のノードを中間ノードと呼ぶ。また、各ノードに付与されたタグをシンボルと表現する。さらに、“ｔｈｅ”、“ｐｒｅｔｔｙ”などの単語を終端記号、それ以外の“ＮＰ”、“ＶＰ”などの文法的な情報を表すタグを非終端記号と表現し、終端記号が付与されたノードを終端ノード、非終端記号が付与されたノードを非終端ノードと表現する。
【０００４】
基本木は、初期木及び補助木の二種類に分類される。初期木は、例えば図３に示すように、置換操作と呼ばれるシンボルの書き換えによって他の木と結合する。また、補助木は、例えば図４に示すように、接合操作と呼ばれる木の割り込みによって他の木と結合する。補助木は、必ずルートノードと同じシンボルである葉ノードを持つ。
【０００５】
従来の木接合文法の獲得方法には、大きく分けると二種類ある。一つは、基本木の型（パターン）を予め定義しておき、ＥＭアルゴリズムなどの方法で構文木から基本木の確率を推定するものである（例えば、非特許文献１参照）。二つ目の方法は、言語学的な知識に基づいて、発見的な方法により基本木を直接獲得した後に、それらの確率を最尤推定によって求める方法である（例えば、非特許文献２参照）。また、近年の自動文法獲得方法には、木置換文法に基づいた方法がある（例えば、非特許文献３参照）。木置換文法は、初期木による置換操作のみで構文木を生成する方法である。非特許文献３に開示されている木置換文法の自動獲得方法は、どのような言語のコーパスにも適用できるという利点がある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Fei Xia (1999) Extracting tree adjoining grammars from bracketed corpora, In Proceedings of the 5th Natural Language Processing Pacific Rim Symposium (NLPRS), pages 398-403.
【非特許文献２】David Chiang, (2003) Statistical Parsing with an Automatically Extracted Tree Adjoining Grammar, pages 299-316. CSLI Publications.
【非特許文献３】Trevor Cohn, Sharon Goldwater, and Phil Blunsom (2009) Inducing compact but accurate treesubstitution grammars, In Proceedings of HLT-NAACL, pages 548-556, Boulder, Colorado, June. Association for Computational Linguistics.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１のような方法では、予め定義された型に当てはまる基本木しか獲得することができないため、言語毎に基本木の型を定義する必要があり、汎用性に欠ける、という問題がある。また、非特許文献２のような発見的な方法による基本木の獲得の場合も、言語学的な知見に基づいているため、対象言語が変わると同じ獲得方法を適用できない可能性がある、という問題がある。英語や中国語などのよく知られた言語以外でも、同じ方法で基本木を自動獲得できることが望ましい。
【０００８】
また、非特許文献３に開示されている木置換文法の自動獲得方法は、言語の種類に依存しない汎用的な方法であるが、木置換文法では置換操作だけで構文木を構成するため、多くの初期木を獲得してしまい、メモリを多く消費してしまう、という問題がある。
【０００９】
本発明は、上記問題点を解決するために成されたものであり、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる基本木獲得装置、構文解析装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明の基本木獲得装置は、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与する付与手段と、各部分木の深さが１となるように前記構文木を部分木に分解する分解手段と、前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出する算出手段と、前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返す生成手段と、前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する獲得手段と、を含んで構成されている。
【００１１】
本発明の基本木獲得装置によれば、付与手段が、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを各非終端ノードに付与し、分解手段が、各部分木の深さが１となるように構文木を部分木に分解する。
【００１２】
そして、算出手段が、構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、非終端ノード毎に内側確率を算出し、生成手段が、非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで新たな基本木の生成を繰り返す。獲得手段は、事後確率が最大となるときの生成手段により生成された基本木、及び確率モデルの所定のパラメータを獲得する。
【００１３】
このように、構文木の各非終端ノードに、接合操作も導入した木接合文法に基づく内容を示すラベルを付与し、このラベルに基づいて構文木を深さ１の部分木に分解し、各部分木の生成確率に基づくノード毎の内側確率を用いて新たな基本木を生成し、構文木が観測された下での基本木の事後確率が最大となる基本木を獲得するため、言語に依存しない基本木の獲得を行うことができ、また、接合操作の導入により、獲得される基本木の数を削減することができるため、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる。
【００１４】
また、前記確率モデルは、前記保持した基本木の情報に基づいて基本木を生成する第１確率、及び前記基底分布に基づいて基本木を生成する第２確率を用いて表され、前記第１ラベルが付与された非終端ノードは、前記第２確率に従って生成された非終端ノードであり、前記第２ラベルが付与された非終端ノードは、前記第１確率に従って生成され非終端ノードであり、前記第３ラベルが付与された非終端ノードは、前記第１確率で前記第２ラベルが示す内容の非終端ノードを生成し、前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成し、前記第４ラベルが付与された非終端ノードは、所定の接合確率及び前記第１確率に従って前記第２ラベルが示す内容の非終端ノードを生成し、前記所定の接合確率及び前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成する。
【００１５】
また、前記獲得手段は、メトロポリス・ヘイスティングス法により、前記生成手段により生成された新たな基本木を受理または棄却すると共に、前記確率モデルのパラメータを更新し、前記パラメータの更新を所定回数以上行った場合には、現在の基本木及び更新されたパラメータを獲得し、前記パラメータの更新を所定回数以上行っていない場合には、前記現在の基本木を前記分解手段に入力すると共に、前記更新されたパラメータを前記確率モデルに設定することができる。
【００１６】
また、本発明の構文解析装置は、上記の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータを記憶する記憶手段と、前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する解析手段と、を含んで構成されている。また、本発明の構文解析装置は、上記の基本木獲得装置を含んで構成してもよい。
【００１７】
また、本発明の基本木獲得方法は、付与手段と、分解手段と、算出手段と、生成手段と、獲得手段とを含む基本木獲得装置における基本木獲得方法であって、前記付与手段は、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、構文木を構成する複数の基本木各々の各非終端ノードにラベルが付与されていない場合には、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与し、前記分解手段は、各部分木の深さが１となるように前記構文木を部分木に分解し、前記算出手段は、前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出し、前記生成手段は、前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返し、前記獲得手段は、前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する方法である。
【００１８】
また、本発明の構文解析方法は、記憶手段、及び解析手段を含む構文解析装置における構文解析方法であって、前記記憶手段には、上記の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータが記憶され、前記解析手段は、前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する方法である。
【００１９】
また、本発明の基本木獲得プログラムは、コンピュータを、上記の基本木獲得装置を構成する各手段として機能させるためのプログラムである。
【００２０】
また、本発明の構文解析プログラムは、コンピュータを、上記の構文解析装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００２１】
以上説明したように、本発明の基本木獲得装置、構文解析装置、方法、及びプログラムによれば、構文木の各非終端ノードに、接合操作も導入した木接合文法に基づく内容を示すラベルを付与し、このラベルに基づいて構文木を深さ１の部分木に分解し、各部分木の生成確率に基づくノード毎の内側確率を用いて新たな基本木を生成し、構文木が観測された下での基本木の事後確率が最大となる基本木を獲得するため、言語に依存しない基本木の獲得を行うことができ、また、接合操作の導入により、獲得される基本木の数を削減することができるため、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】構文木の一例示す図である。
【図２】基本木の一例を示す図である。
【図３】置換操作を説明するための図である。
【図４】接合操作を説明するための図である。
【図５】各非終端ノードにラベルが付与された構文木の一例を示す図である。
【図６】深さ１に分解された部分木及びその部分木の生成確率の一例を示す図である。
【図７】第１の実施の形態の基本木獲得装置の機能構成を示すブロック図である。
【図８】内側確率テーブルを示す図である。
【図９】第１の実施の形態の基本木獲得装置における基本木獲得処理ルーチンの内容を示すフローチャートである。
【図１０】第２の実施の形態の構文解析装置の機能構成を示すブロック図である。
【図１１】第２の実施の形態の構文解析装置における構文解析処理ルーチンの内容を示すフローチャートである。
【図１２】効果確認結果を示す表である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２４】
＜本実施の形態の確率モデル＞
文法獲得（基本木の獲得）の問題は、与えられた構文木ｔから、ｔを構成する基本木の集合ｅを獲得することである。構文木が与えられたとき、基本木の事後確率ｐ（ｅ｜ｔ；Φ）は、ベイズの定理を用いて、下記（１）式のように計算できる。
【００２５】
【数１】
【００２６】
木接合文法では、初期木または補助木を一つずつ生成し、全ての葉ノードが終端記号、すなわち単語になったときに生成を停止する。全ての葉ノードが終端記号になったとき、これらの終端記号列が構文木ｔと一致するとき、ｐ（ｔ｜ｅ）＝１となり、そうでない場合はｐ（ｔ｜ｅ）＝０となる。一つずつ生成される基本木ｅを、インデックスｉを用いてｅｉ（ｉ＝１，２，・・・）とする。
【００２７】
本実施の形態では、非特許文献４（Y.W. Teh(2006) A Bayesian Interpretation of Interpolated Kneser-Ney. Technical Report TRA2/06, School of Computing, NUS.）に開示されているベイズモデルを用いて、ｐ（ｅ）をモデル化する。このモデルは、基本木ｅｉが、今までに生成された基本木ｅ１，・・・，ｅｉ−１ に依存するモデルであり、下記（２）式のように定義される。
【００２８】
【数２】
【００２９】
ただし、ｅ−ｉ＝ｅ１，・・・，ｅｉ−１は、１回目から（ｉ−１）回目までに生成された基本木の集合である。Ｘは基本木ｅｉのルートシンボルを表す。また、αｅｉ，Ｘ及びβＸは、下記（３）式で表される。
【００３０】
【数３】
【００３１】
ｎ−ｉｅｉ，Ｘは、ｅ−ｉのうちｅｉと同じ基本木が何回生成されたかを表す。また、この確率モデルは、内部で各基本木が何回生成されたかという情報を、いくつかのクラスタに分けて保存する。例えば、ある基本木がこれまでに１０回生成されたとすると、この確率モデルの内部では、（３回，７回）という２つのクラスタになって保持している場合もあれば、（２回，３回，５回）のように３つのクラスタになっている場合もある。このとき、ｔｅｉ，Ｘは、基本木ｅｉがモデル内部でいくつのクラスタに分割されているかを表す。また、ｎ−ｉ・，Ｘ及びｔ・，Ｘは、下記（４）式で表される。
【００３２】
【数４】
【００３３】
この確率モデルは、Ｐｉｔｍａｎ−Ｙｏｒ過程と呼ばれ、非特許文献４に詳細が開示されている。
【００３４】
本実施の形態では、初期木及び補助木の確率分布をそれぞれ独立に（２）式で定義する。以降、初期木の確率モデルのパラメータを｛ｄＸ，θＸ｝、補助木の確率モデルのパラメータを｛ｄ’Ｘ，θ’Ｘ｝と区別する。同様に、（２）式の変数をそれぞれ｛αｅｉ，Ｘ，βＸ｝、｛α’ｅｉ，Ｘ，β’Ｘ｝と区別する。初期木による置換操作は、葉ノードが非終端記号であれば確率１で必ず実行される。一方で、補助木の接合操作は中間ノードに対して実行される場合と実行されない場合とがある。そこで、接合確率ａＸを新たに導入すると、補助木ｅｉが中間ノードＸに対して接合される確率は、下記（５）式となる。
【００３５】
【数５】
【００３６】
また、（２）式中のＰ０（ｅｉ｜Ｘ）は、基底分布と呼ばれ、基本木ｅｉの基底となる確率分布である。したがって、ΣｅｉＰ０（ｅｉ｜Ｘ）＝１を満たす必要がある。基底分布の実現例として、例えば、下記（６）式のように定義することができる。
【００３７】
【数６】
【００３８】
ただし、ＣＦＧ（ｅｉ）は、ｅｉを深さが１の部分木に分解した生成規則の集合を表す。例えば、ｒが二分木の場合、Ａ→ＢＣという形式をとる。ここで、Ａはルートノード、Ｂ及びＣはＡの子ノードである。ＰＭＬＥ（ｒ）は、生成規則ｒの最尤推定値であり、例えば、ｒ＝Ａ→ＢＣとき、下記（７）式のように計算することができる。
【００３９】
【数７】
【００４０】
ただし、ｃｏｕｎｔ（Ａ）はコーパス中にシンボルＡが何回出現したかを表し、ｃｏｕｎｔ（Ａ→ＢＣ）はコーパス中に生成規則Ａ→ＢＣが何回出現したかを表す。ＬＥＡＦ（ｅｉ）、ＩＮＴＥＲＮＡＬ（ｅｉ）はそれぞれ、ｅｉの葉ノード及び中間ノードの集合を表す。例えば、ｅｉを図２（ｃ）とすると、ＣＦＧ（ｅｉ）＝｛ＮＰ→ＤＴ Ｎ，Ｎ→ｇｉｒｌ｝、ＬＥＡＦ（ｅｉ）＝｛ＤＴ，ｇｉｒｌ｝、ＩＮＴＥＲＮＡＬ（ｅｉ）＝｛Ｎ｝となる。ｓＸは、停止確率と呼ばれ、初期木または補助木の生成がノードＸで停止する確率を表す。
【００４１】
本実施の形態の基本木獲得装置では、事後確率ｐ（ｅ｜ｔ；Φ）を最大にする基本木ｅ及びパラメータセットΦ＝｛ｄＸ，θＸ，ｓＸ，ａＸ｝を学習する。
【００４２】
＜本実施の形態における構文木の分解＞
（２）式に基づいて構文木を生成するために、本実施の形態では、構文木中の各非終端ノードを、そのノードの内容に従って、以下のように４つのタイプ（Ｘ（ｂａｓｅ）、Ｘ（ｅ）、Ｘｓｕｂ、Ｘａｄｊ（ｔｙｐｅ））に分類し（下記［タイプ１］〜［タイプ４］）、タイプに応じたラベルを付与する。なお、Ｘは非終端ノードに付与されたシンボルである。また、基本木を生成する際に、それが（２）式の第１項目（αｅｉ，Ｘ）からの生成なのか、第２項目（βＸＰ０（ｅｉ｜Ｘ））からの生成なのかを区別する。第１項目からの生成は、以前生成した基本木ｅ−ｉの中から、確率的にいずれかを選択することに相当する。一方で、第２項目からの生成は、基底分布Ｐ０（ｅｉ｜Ｘ）に従って新たに基本木を生成する。基底分布から新たに生成された基本木は、以前生成された基本木のいずれかと一致する場合もあれば、今までに生成したことのない基本木であることもある。
【００４３】
ここで、タイプ別のラベル毎に、各非終端ノードの内容を示す。
【００４４】
［タイプ１］Ｘ（ｂａｓｅ）：基底分布、すなわち（２）式の第２項目から生成された基本木のルートノードまたは中間ノードを表す。このノードは、基底分布Ｐ０に従って基本木を生成するノードである。
【００４５】
［タイプ２］Ｘ（ｅ＊）：（２）式の第１項目から生成された基本木のルートノードまたは中間ノードを表す。ｅ＊は基本木の情報を格納した変数であり、例えば、図２（ｃ）の場合、ｅ＊＝ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ）と表され、Ｘ＝ＮＰとなる。この場合、ＮＰ（ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ））は、基本木の情報ｅ＊＝ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ）に従って、ＮＰ（ＮＰ（ＤＴ）（Ｎ ｇｉｒｌ））→（ＤＴ）（Ｎ ｇｉｒｌ）という規則を生成する。同様に、Ｎ（Ｎ ｇｉｒｌ）は、Ｎ（Ｎ ｇｉｒｌ）→ｇｉｒｌという規則を生成する。これにより、図２（ｃ）の基本木を、Ａ→ＢＣという深さが１の部分木の組み合わせで生成することが可能となる。
【００４６】
［タイプ３］Ｘｓｕｂ：置換操作が起こったノードを表す。このノードは、確率αｅｉ，ＸでＸ（ｅ） を生成し、確率βＸでＸ（ｂａｓｅ）を生成する。
【００４７】
［タイプ４］Ｘａｄｊ（ｔｙｐｅ＊）：接合操作が起こったノードを表す。ｔｙｐｅ＊は、上記のｂａｓｅまたはｅ＊のいずれかが入る変数であり、接合操作によって割り込まれる前のノードがＸ（ｔｙｐｅ＊）であったことを意味する。このノードは、確率α’ｅｉ，ＸでＸａｄｊ（ｔｙｐｅ＊）（ｅ＊）を生成し、確率β’ＸでＸａｄｊ（ｔｙｐｅ＊）（ｂａｓｅ）を生成する。例えば、Ｘａｄｊ（ｔｙｐｅ＊）（ｅ＊）は、ノードＸ（ｔｙｐｅ＊）に対して、（２）式の第１項目から生成された補助木ｅが接合されたことを意味する。図４に示すように、接合操作によって割り込まれたノード及びその子ノードは、補助木の葉ノードと結合されるため、Ｘａｄｊ（ｔｙｐｅ＊）（ｅ＊）、Ｘａｄｊ（ｔｙｐｅ＊）（ｂａｓｅ）はどちらもＸ（ｔｙｐｅ＊）を葉ノードとして生成する。
【００４８】
構文木データの各非終端ノードを、上記の４つのいずれかのタイプに分類すれば、構文木を構成する基本木の集合が確定される。ただし、観測データとして得られる構文木コーパスには、これらのタイプはラベル付けされていないため、学習によってこれらのタイプを推定する。一例として、図４に示すように１つの初期木（ＮＰ（ＤＴ ｔｈｅ）（Ｎ ｇｉｒｌ））と、１つの補助木（Ｎ（ＪＪ ｐｒｅｔｔｙ）（Ｎ））とで構成される構文木を考える。この構文木の各非終端ノードシンボルを上記の４つのタイプに分類した例を図５に示す。そして、このラベルが付与された構文木を深さが１の部分木に分解する。深さが１の部分木とは、その部分木が示す生成規則がＡ→ＢＣのように表せる（親ノード及び子ノードのみで表せる）部分木をいう。各部分木が表す生成規則に対して生成確率を図６のように定義すると、（２）式に従って基本木を生成することと等しくなる。例えば、［タイプ３］のラベルが付与されたノードＸｓｕｂは置換操作が起こったノードなので、確率αｅｉ，ＸでＸ（ｅ＊）を生成し、確率βＸでＸ（ｂａｓｅ）を生成するように設定する。これは、（２）式の第１項目から基本木を生成するのか、または第２項目から生成するのかを確率的に選ぶことに相当する。このように、全ての構文木を深さが１の部分木に分解し、部分木毎に適切な生成確率を割り当てる操作が構文木の分解である。
【００４９】
＜基本木獲得装置の構成＞
次に、構文木コーパスを訓練データとして、基本木を獲得する基本木獲得装置に本発明を適用した場合を例にして、第１の実施の形態を説明する。
【００５０】
第１の実施の形態の基本木獲得装置は、ＣＰＵと、ＲＡＭと、後述する基本木獲得処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このコンピュータは、機能的には、図７に示すように、木接合文法学習部１２を構成している。木接合文法学習部１２は、構文木ｔが観測された下での基本木の集合ｅの事後確率を示す確率モデルｐ（ｅ｜ｔ；Φ）のパラメータΦを指定回数だけ逐次更新することで、最適な基本木の集合＾ｅ及び最適なパラメータ＾Φを求めるものである。以下、基本木の集合及びパラメータの初期値をｅ（０）及びΦ（０）とし、ｕ回目の更新後の基本木の集合及びパラメータをとｅ（ｕ）及びΦ（ｕ）と表記する。
【００５１】
木接合文法学習部１２は、初期基本木及び初期パラメータを設定する基準基本木設定部１４と、基本木の情報に基づいて構文木にラベル付与を行うラベル付与部１５と、ラベルが付与された構文木を部分木に分解する構文木分解部１６と、各部分木の生成確率に基づいて各ノードの内側確率を計算する内側確率計算部１８と、各ノードの内側確率に基づいて、新たな基本木を生成する基本木サンプリング部２０と、新たな基本木を受理するか棄却するかを判定する受理棄却判定部２２と、確率モデルのパラメータを更新するパラメータ更新部２４と、学習処理を終了するか否かを判定する終了判定部２６と、を含んだ構成で表すことができる。
【００５２】
基準基本木設定部１４は、構文木コーパス｛ｔ｝のデータを読み込む。構文木コーパスとは、文にＮＰやＶＰなどの文法的な役割が付与された木構造（構文木）で構成されるコーパスである。なお、ここで読み込む構文木コーパス｛ｔ｝の各非終端ノードには、上述の［タイプ１］〜［タイプ４］のどのタイプに該当するかのラベルは付与されていない。構文木コーパス｛ｔ｝は、基本木獲得装置１０の訓練データ記憶部（図示省略）に予め記憶しておくことができる。また、外部装置に記憶された構文木コーパス｛ｔ｝を、ネットワーク等を介して読み込むようにしてもよい。基準基本木設定部１４は、読み込んだ構文木コーパス｛ｔ｝に対して、初期基本木ｅ（０）及び初期パラメータΦ（０）を設定する。
【００５３】
ラベル付与部１５は、基準基本木設定部１４により設定された基本木の集合ｅ（０）、または後述の終了判定部２６から出力された基本木の集合ｅ（ｕ）の情報に基づいて、構文木コーパスに含まれる全ての構文木ｔの各非終端ノードに対して、上述の［タイプ１］〜［タイプ４］のいずれかのラベルを付与する。ラベルの情報は基本木の情報と１対１に対応しているため、ラベル付与は確定的に行うことができる。
【００５４】
構文木分解部１６は、各構文木を、深さが１の単純な部分木に分解し、各部分木が表す生成規則に対して、例えば図６に示すような生成確率を計算する。各部分木の生成確率は、各部分木を構成するルートノード及び子ノードに付与されたラベルのタイプが示すノードの内容に基づいて計算することができる。また、図６に示した生成確率内のαｅｉ，Ｘやα’ｅｉ，Ｘは、上記（３）式により求めることができる。
【００５５】
内側確率計算部１８は、構文木分解部１６で分解された部分木を用いて、構文木の内側確率を計算する。内側確率ｐＸ，ｉ，ｋとは、非終端ノードＸ（Ｘはこの非終端ノードに付されたシンボル）からあらゆる規則を使って単語列のｉ番目からｋ番目までの連続する領域を出力する確率を指す。なお、内側確率の定義は非特許文献５（K. Lari and S.J. Young (1991) Applications of stochastic context-free grammars using the inside-outside algorithm, Computer Speech & Language, 5(3):237-257.）に開示されている。内側確率は、基本木が深さ１であれば下記（８）式に示すように、再帰的に計算することができる。
【００５６】
【数８】
【００５７】
ただし、ＰＣＦＧ（ｒ：Ｘ→ＹＺ）は、構文木分解部１６で分解された深さが１の部分木Ｘ→ＹＺの生成確率である。また、Ｘ、Ｙ及びＺの各シンボルが付された非終端ノードは、各々上記の４タイプのいずれかに分類された非終端ノードである。各非終端ノードについて内側確率を計算し、計算された内側確率は、例えば、図８に示すようなテーブル形式で保持する。
【００５８】
基本木サンプリング部２０は、内側確率計算部１８により計算された内側確率テーブルに基づいて、トップダウン的に新たな基本木ｅ’を生成する。例えば、ルートノードがＶＰ、単語数がＬの構文木の場合を考える。構文木のルートノードでは必ず初期木による置換が起こるため、ＶＰｓｕｂから基本木の生成を開始する。まず、ＶＰｓｕｂをルートノードとする考え得る全ての基本木ｒ∈ＣＦＧ（ＶＰｓｕｂ）に対して、確率ＰＣＦＧ（ｒ：ＶＰｓｕｂ→ＹＺ）×ｐＹ，０，ｊ×ｐＺ，ｊ＋１，Ｌを計算し、その確率に基づいてランダムに１つの生成規則＾ｒを生成する。なお、ｐＹ，０，ｊやｐＺ，ｊ＋１，Ｌは、内側確率計算部１８で作成した内側確率テーブルを参照することにより値が得られる。次に、生成規則＾ｒに含まれる全ての子ノードについて、同様にランダムに１つの生成規則を生成する。以上の処理を繰り返していき、全ての子ノードが終端記号、すなわち単語となったときに生成を停止する。このようにして得られた生成規則の集合を新たな基本木の集合ｅ’とする。
【００５９】
受理棄却判定部２２では、基本木サンプリング部２０で新たに生成された基本木の集合ｅ’を受理するか、または棄却するかを、メトロポリス・ヘイスティングス法を用いて確率的に決定する。メトロポリス・ヘイスティングス法は、非特許文献６（Mark Johnson, Thomas L. Griffiths and Sharon Goldwater (2007) Bayesian Inference for PCFGs via Markov Chain Monte Carlo, The Conference of the NAACL; Proceedings of the Main Conference, pages139-146.）に詳細が開示されている。基本木の集合ｅ’が受理された場合には、現在の基本木ｅ（ｕ）を、新たに生成された基本木ｅ’に置き換える。棄却された場合には、基本木サンプリング部２０で新たに生成された基本木ｅ’は棄却され、現在の基本木ｅ（ｕ）をそのまま保持する。新たな基本木ｅ’を受理する確率は、下記（９）式により計算する。
【００６０】
【数９】
【００６１】
ただし、基本木サンプリング部２０で現在扱っている文をｌとし、ｅ−ｌはｌ以外の全ての文の構文木を構成する基本木の集合を表す。ｗｌは、現在扱っている文ｌの単語列である。
【００６２】
パラメータ更新部２４は、非特許文献５に開示されている方法を用いて、以下のようにハイパーパラメータ（ｄＸ，θＸ，ｄ’Ｘ，θ’Ｘ，ｓＸ，ａＸ）を更新する。
【００６３】
【数１０】
【００６４】
また、（〜ｄ１，〜ｄ２，〜θ１，〜θ２，〜ｓ１，〜ｓ２，〜ａ１，〜ａ２）は、予め設定された値である。
【００６５】
終了判定部２６は、現在の学習ステップｕが事前に設定された値ｕｔｈと一致するか否かを判定することにより、学習過程を終了するか否かを判定する。ｕｔｈには予め学習過程の所定の更新回数を定めておく。ｕがｕｔｈと一致する場合には、更新されたパラメータΦ（ｕ）を最適なパラメータ＾Φとし（＾Φ←Φ（ｕ））、現在の基本木の集合ｅ（ｕ）を最適な基本木の集合＾ｅとして（＾ｅ←ｅ（ｕ））、学習過程を停止する。ｕ＜ｕｔｈの場合、すなわち、予め定めた所定の更新回数分の学習過程をまだ終了していない場合には、学習ステップｕを１インクリメントして（ｕ←ｕ＋１）、更新されたパラメータΦ（ｕ）及び基本木ｅ（ｕ）を再度、ラベル付与部１５へ出力する。
【００６６】
＜基本木獲得装置の作用＞
次に、第１の実施の形態に係る基本木獲得装置１０の作用について説明する。基本木獲得装置１０のＲＯＭに記憶された基本木獲得プログラムを、ＣＰＵが実行することにより、図９に示す基本木獲得処理ルーチンが実行される。
【００６７】
ステップ１００で、予め訓練データ記憶部に記憶された構文木コーパス｛ｔ｝のデータを読み込み、次に、ステップ１０２で、初期基本木ｅ（０）及び初期パラメータΦ（０）を設定する。
【００６８】
次に、ステップ１０４で、上記ステップ１００で読み込んだ構文木コーパス｛ｔ｝の構文木各々の各非終端ノードに対して、上記ステップ１０２で設定した基本木の集合ｅ（０｝の情報に基づいて、基本木の情報と１対１に対応するラベルの情報に従って、上述の［タイプ１］〜［タイプ４］のいずれかのラベルを付与する。
【００６９】
次に、ステップ１０６で、各構文木を、深さが１の単純な部分木に分解し、各部分木が表す生成規則毎に、各部分木を構成するルートノード及び子ノードに付与されたラベルのタイプが示すノードの内容、及び上記（３）式に基づいて、例えば図６に示すような生成確率を計算する。
【００７０】
次に、ステップ１０８で、上記ステップ１０６で分解された部分木を用いて、非終端ノード毎の内側確率を、上記（８）式に従って計算する。計算された内側確率は、例えば、図８に示すようなテーブル形式で保持する。
【００７１】
次に、ステップ１１０で、構文木のルートノードＸ及び単語数Ｌに基づいて、Ｘｓｕｂをルートノードとする考え得る全ての基本木ｒ∈ＣＦＧ（Ｘｓｕｂ）に対して、確率ＰＣＦＧ（ｒ：Ｘｓｕｂ→ＹＺ）×ｐＹ，０，ｊ×ｐＺ，ｊ＋１，Ｌを計算し、その確率に基づいてランダムに１つの生成規則＾ｒを生成する。この際、ｐＹ，０，ｊやｐＺ，ｊ＋１，Ｌは、上記ステップ１０８で計算された内側確率テーブルを参照することにより値を得る。そして、生成規則＾ｒに含まれる全ての子ノードについて、同様にランダムに１つの生成規則を生成し、全ての子ノードが終端記号となるまで、以上の処理を繰り返す。全ての子ノードが終端記号となった場合には処理を停止し、得られた生成規則の集合を新たな基本木の集合ｅ’とする。
【００７２】
次に、ステップ１１２で、上記ステップ１１０で生成された新たに基本木の集合ｅ’を受理するか、または棄却するかを、メトロポリス・ヘイスティングス法を用いて、例えば（９）式に従って確率的に決定する。基本木が受理された場合には、ステップ１１４へ移行し、現在の基本木ｅ（ｕ）（初回はｅ（０））を、新たに生成された基本木ｅ’に置き換えて、ステップ１１６へ移行する。棄却された場合には、ステップ１１４をスキップして、ステップ１１６へ移行する。
【００７３】
ステップ１１６では、ハイパーパラメータ（ｄＸ，θＸ，ｄ’Ｘ，θ’Ｘ，ｓＸ，ａＸ）を更新する。
【００７４】
次に、ステップ１１８で、現在の学習ステップｕが事前に設定された値ｕｔｈと一致するか否かを判定することにより、学習過程を終了するか否かを判定する。ｕ＜ｕｔｈの場合には、ステップ１２０へ移行して、学習ステップｕを１インクリメントして、ステップ１０４へ戻り、更新されたパラメータΦ（ｕ）及び基本木ｅ（ｕ）を用いて処理を繰り返す。一方、ｕ＝ｕｔｈの場合には、更新されたパラメータΦ（ｕ）を最適なパラメータ＾Φとし、現在の基本木の集合ｅ（ｕ）を最適な基本木の集合＾ｅとして獲得し、獲得結果（＾ｅ，＾Φ）を出力して、処理を終了する。
【００７５】
以上説明したように、第１の実施の形態の基本木獲得装置によれば、構文木の各非終端ノードに、接合操作も導入した木接合文法に基づく内容を示すラベルを付与し、このラベルに基づいて深さ１の部分木に分解し、各部分木の生成確率に基づくノード毎の内側確率を用いて新たな基本木を生成し、構文木が観測された下での基本木の事後確率が最大となる基本木を獲得するため、言語特有の規則などを利用した発見的手法に頼ることなく、言語に依存しない基本木の獲得を行うことができ、また、接合操作の導入により、獲得される基本木の数を削減することができるため、メモリの消費量を抑制しつつ、あらゆる言語に対応することができる。
【００７６】
次に、第２の実施の形態について説明する。第２の実施の形態では、入力された構文解析対象文について構文解析を行う構文解析装置に本発明を適用した場合を例に説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【００７７】
＜構文解析装置の構成＞
第２の実施の形態の構文解析装置２１０は、ＣＰＵと、ＲＡＭと、後述する構文解析処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このコンピュータは、機能的には、図１０に示すように、木接合文法学習部１２と、基本木パラメータ記憶部３０と、構文解析部３２と、を含んだ構成で表すことができる。木接合文法学習部１２は、第１の実施の形態と同様に、基準基本木設定部１４と、ラベル付与部１５と、構文木分解部１６と、内側確率計算部１８と、基本木サンプリング部２０と、受理棄却判定部２２と、パラメータ更新部２４と、終了判定部２６と、を含んだ構成で表すことができる。
【００７８】
基本木パラメータ記憶部３０は、木接合文法学習部１２で獲得された基本木の集合＾ｅ及び確率モデルのパラメータセット＾Φが記憶される。
【００７９】
構文解析部３２は、基本木パラメータ記憶部３０に記憶された基本木＾ｅ及びパラメータ＾Φを用いて、構文木が未知の構文解析対象文Ｓから構文木を推定する。具体的には、パラメータ＾Φを確率モデルに設定し、基本木＾ｅを、構文木分解部１６と同様の処理により深さ１の部分木に分解すると共に、各部分木が表す生成規則の生成確率を計算する。次に、内側確率計算部１８と同様の処理により、非終端ノード毎の内側確率を計算する。そして、基本木サンプリング部２０でトップダウン的に基本木を生成し、生成された基本木の集合で構成される構文木を出力する。構文木が観測されている学習時は、構文木の各ノードにラベルを付与し、それを分解した深さ１の部分木のみを用いて内側確率を計算し、基本木をサンプリングするが、構文解析時は、構文木が不明のため、木接合文法学習部１２で獲得した全ての基本木＾ｅを深さ１の部分木に分解し、その部分木を用いて内側確率を計算し、基本木をサンプリングする。その結果、あらゆる構文木の可能性を考慮することができる。
【００８０】
＜構文解析装置の作用＞
次に、第２の実施の形態に係る構文解析装置２１０の作用について説明する。構文解析装置２１０のＲＯＭに記憶された構文解析プログラムを、ＣＰＵが実行することにより、図１１に示す基本木獲得処理ルーチンが実行される。
【００８１】
ステップ２００で、第１の実施の形態の基本木獲得処理（図９）と同様の処理を実行し、読み込んだ構文木コーパス｛ｔ｝から基本木の集合＾ｅ及び確率モデルのパラメータセット＾Φを獲得し、次に、ステップ２０２で、獲得した基本木の集合＾ｅ及びパラメータセット＾Φを、基本木パラメータ記憶部３０に記憶する。
【００８２】
次に、ステップ２０４で、構文解析対象文Ｓを読み込む。次に、ステップ２０６で、基本木パラメータ記憶部３０から基本木の集合＾ｅ及びパラメータセット＾Φを読み出す。
【００８３】
次に、ステップ２０８で、上記ステップ２０６で読み出したパラメータ＾Φを確率モデルに設定し、基本木＾ｅを深さ１の部分木に分解すると共に、各部分木が表す生成規則の生成確率を計算し、その生成確率に基づいて、非終端ノード毎の内側確率をボトムアップ的に計算する。そして、上記ステップ２０４で読み込んだ構文解析対象文Ｓに対してトップダウン的に基本木を生成して、生成された基本木の集合で構成される構文木を出力する。
【００８４】
以上説明したように、第２の実施の形態の構文解析装置によれば、第１の実施の形態の基本木獲得装置により獲得された基本木及びパラメータを用いて構文を解析するため、メモリの消費量を抑制しつつ、言語に依存しない構文解析を行うことができる。
＜効果確認実験＞
本発明の効果を検証するため、構文解析の実験で広く使われている英語のペンツリーバンクデータを構文木コーパスとして使用し、実際に木接合文法を自動獲得する実験を行った。また、獲得された基本木を用いて構文解析を行い、精度の評価を行った。
【００８５】
予め設定するパラメータ値はそれぞれ、（〜ｄ１，〜ｄ２）＝（１，１），（〜θ１，〜θ２）＝（０．１，１０），（〜ｓ１，〜ｓ２）＝（１，１），（〜ａ１，〜ａ２）＝（１００，１００）とした。
【００８６】
構文木コーパスは、非特許文献４に示されている実験設定と同様に、セクション２から２１までを学習用データとして用いた。評価用データは、セクション２３の構文木情報を取り除いた文を用いた。構文解析の結果は、ＥＶＡＬＢ（ｈｔｔｐ：／／ｎｌｐ．ｃｓ．ｎｙｕ．ｅｄｕ／ｅｖａｌｂ／）を用いてブラケティングＦ値を計算し、評価指標として用いた。この結果を図１２に示す。本実施の形態の基本木獲得装置で獲得された木接合文法の基本木を用いて、本実施の形態の構文解析装置により行った構文解析の評価値Ｆは、文脈自由文法の評価値Ｆを大きく上回った。また、木置換文法よりも約１９％少ない基本木の数で、木置換文法とほぼ同等の精度を得た。従って、本実施の形態が少量の基本木を獲得しつつ、高い精度で構文解析を実行できる効果を確認した。
【００８７】
なお、上記第２の実施の形態では、基本木獲得装置（木接合文法学習部）を備えた構文解析装置について説明したが、基本木獲得装置と、木接合文法学習部を備えない構文解析装置とを別々に構成してもよい。この場合、基本木獲得装置で獲得された基本木及びパラメータを、ネットワーク等を介して、構文解析装置の基本木パラメータ記憶部に記憶するようにするとよい。また、基本木獲得装置に基本木パラメータ記憶部を設けて、獲得した基本木及びパラメータを記憶しておき、構文解析装置から、ネットワーク等を介して、基本木獲得装置の基本木パラメータ記憶部に記憶された基本木及びパラメータを読み出すようにしてもよい。
【００８８】
また、上述の基本木獲得装置及び構文解析装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００８９】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００９０】
１０ 基本木獲得装置
１２ 木接合文法学習部
１４ 基準基本木設定部
１５ ラベル付与部１５
１６ 構文木分解部
１８ 内側確率計算部
２０ 基本木サンプリング部
２２ 受理棄却判定部
２４ パラメータ更新部
２６ 終了判定部
３０ 基本木パラメータ記憶部
３２ 構文解析部
２１０ 構文解析装置
【特許請求の範囲】
【請求項１】
構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与する付与手段と、
各部分木の深さが１となるように前記構文木を部分木に分解する分解手段と、
前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出する算出手段と、
前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返す生成手段と、
前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する獲得手段と、
を含む基本木獲得装置。
【請求項２】
前記確率モデルは、前記保持した基本木の情報に基づいて基本木を生成する第１確率、及び前記基底分布に基づいて基本木を生成する第２確率を用いて表され、
前記第１ラベルが付与された非終端ノードは、前記第２確率に従って生成された非終端ノードであり、前記第２ラベルが付与された非終端ノードは、前記第１確率に従って生成され非終端ノードであり、前記第３ラベルが付与された非終端ノードは、前記第１確率で前記第２ラベルが示す内容の非終端ノードを生成し、前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成し、前記第４ラベルが付与された非終端ノードは、所定の接合確率及び前記第１確率に従って前記第２ラベルが示す内容の非終端ノードを生成し、前記所定の接合確率及び前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成する
請求項１記載の基本木獲得装置。
【請求項３】
前記獲得手段は、メトロポリス・ヘイスティングス法により、前記生成手段により生成された新たな基本木を受理または棄却すると共に、前記確率モデルのパラメータを更新し、前記パラメータの更新を所定回数以上行った場合には、現在の基本木及び更新されたパラメータを獲得し、前記パラメータの更新を所定回数以上行っていない場合には、前記現在の基本木及び前記更新されたパラメータを、前記分解手段に入力する請求項１または請求項２記載の基本木獲得装置。
【請求項４】
請求項１〜請求項３のいずれか１項記載の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータを記憶する記憶手段と、
前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する解析手段と、
を含む構文解析装置。
【請求項５】
請求項１〜請求項３のいずれか１項記載の基本木獲得装置を含む請求項４記載の構文解析装置。
【請求項６】
付与手段と、分解手段と、算出手段と、生成手段と、獲得手段とを含む基本木獲得装置における基本木獲得方法であって、
前記付与手段は、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、構文木を構成する複数の基本木各々の各非終端ノードにラベルが付与されていない場合には、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与し、
前記分解手段は、各部分木の深さが１となるように前記構文木を部分木に分解し、
前記算出手段は、前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出し、
前記生成手段は、前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返し、
前記獲得手段は、前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する
基本木獲得方法。
【請求項７】
記憶手段、及び解析手段を含む構文解析装置における構文解析方法であって、
前記記憶手段には、請求項１〜請求項３のいずれか１項記載の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータが記憶され、
前記解析手段は、前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する
構文解析方法。
【請求項８】
コンピュータを、請求項１〜請求項３のいずれか１項記載の基本木獲得装置を構成する各手段として機能させるための基本木獲得プログラム。
【請求項９】
コンピュータを、請求項４または請求項５記載の構文解析装置を構成する各手段として機能させるための構文解析プログラム。
【請求項１】
構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与する付与手段と、
各部分木の深さが１となるように前記構文木を部分木に分解する分解手段と、
前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出する算出手段と、
前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返す生成手段と、
前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する獲得手段と、
を含む基本木獲得装置。
【請求項２】
前記確率モデルは、前記保持した基本木の情報に基づいて基本木を生成する第１確率、及び前記基底分布に基づいて基本木を生成する第２確率を用いて表され、
前記第１ラベルが付与された非終端ノードは、前記第２確率に従って生成された非終端ノードであり、前記第２ラベルが付与された非終端ノードは、前記第１確率に従って生成され非終端ノードであり、前記第３ラベルが付与された非終端ノードは、前記第１確率で前記第２ラベルが示す内容の非終端ノードを生成し、前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成し、前記第４ラベルが付与された非終端ノードは、所定の接合確率及び前記第１確率に従って前記第２ラベルが示す内容の非終端ノードを生成し、前記所定の接合確率及び前記第２確率で前記第１ラベルが示す内容の非終端ノードを生成する
請求項１記載の基本木獲得装置。
【請求項３】
前記獲得手段は、メトロポリス・ヘイスティングス法により、前記生成手段により生成された新たな基本木を受理または棄却すると共に、前記確率モデルのパラメータを更新し、前記パラメータの更新を所定回数以上行った場合には、現在の基本木及び更新されたパラメータを獲得し、前記パラメータの更新を所定回数以上行っていない場合には、前記現在の基本木及び前記更新されたパラメータを、前記分解手段に入力する請求項１または請求項２記載の基本木獲得装置。
【請求項４】
請求項１〜請求項３のいずれか１項記載の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータを記憶する記憶手段と、
前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する解析手段と、
を含む構文解析装置。
【請求項５】
請求項１〜請求項３のいずれか１項記載の基本木獲得装置を含む請求項４記載の構文解析装置。
【請求項６】
付与手段と、分解手段と、算出手段と、生成手段と、獲得手段とを含む基本木獲得装置における基本木獲得方法であって、
前記付与手段は、構文木を構成する複数の基本木各々の情報に基づいて、構文木の各ノードに対して、構文木を構成する複数の基本木各々の各非終端ノードにラベルが付与されていない場合には、基底分布に基づいて基本木を生成する非終端ノードであることを示す第１ラベル、保持した基本木の情報に基づいて基本木を生成する非終端ノードであることを示す第２ラベル、置換操作が起こった非終端ノードであることを示す第３ラベル、及び接合操作によって割り込まれた非終端ノードであることを示す第４ラベルを含むラベル群のいずれかのラベルを前記各非終端ノードに付与し、
前記分解手段は、各部分木の深さが１となるように前記構文木を部分木に分解し、
前記算出手段は、前記構文木が観測された下での基本木の事後確率を示し、かつ所定のパラメータが設定された確率モデル、及び前記各部分木の非終端ノードに付与されたラベルが示す内容に基づいて定まる該部分木の生成確率に基づいて、前記非終端ノード毎に内側確率を算出し、
前記生成手段は、前記非終端ノード毎の内側確率に基づいて、所定の非終端ノードをルートノードとする新たな基本木を生成し、全ての葉ノードが終端ノードとなるまで前記新たな基本木の生成を繰り返し、
前記獲得手段は、前記事後確率が最大となるときの前記生成手段により生成された基本木、及び前記確率モデルの前記所定のパラメータを獲得する
基本木獲得方法。
【請求項７】
記憶手段、及び解析手段を含む構文解析装置における構文解析方法であって、
前記記憶手段には、請求項１〜請求項３のいずれか１項記載の基本木獲得装置によって獲得された前記基本木及び前記確率モデルのパラメータが記憶され、
前記解析手段は、前記記憶手段に記憶された前記基本木、及び前記パラメータを設定した前記確率モデルに基づいて、解析対象の構文の構文木構造を解析する
構文解析方法。
【請求項８】
コンピュータを、請求項１〜請求項３のいずれか１項記載の基本木獲得装置を構成する各手段として機能させるための基本木獲得プログラム。
【請求項９】
コンピュータを、請求項４または請求項５記載の構文解析装置を構成する各手段として機能させるための構文解析プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−１８１６７６（Ｐ２０１２−１８１６７６Ａ）
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願番号】特願２０１１−４４１６０（Ｐ２０１１−４４１６０）
【出願日】平成２３年３月１日（２０１１．３．１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年９月２０日（２０１２．９．２０）
【国際特許分類】
【出願日】平成２３年３月１日（２０１１．３．１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]