JP6042264B2

JP6042264B2 - 文法規則学習装置、方法、及びプログラム

Info

Publication number: JP6042264B2
Application number: JP2013103557A
Authority: JP
Inventors: 裕之進藤; 永田　昌明; 昌明永田
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2013-05-15
Filing date: 2013-05-15
Publication date: 2016-12-14
Anticipated expiration: 2033-05-15
Also published as: JP2014225104A

Description

本発明は、文法規則学習装置、方法、及びプログラムに係り、特に、統語的な情報が付与された構文木のコーパスから、サンプリング法に基づいて文法規則を学習する文法規則学習装置、方法、及びプログラムに関する。

従来、自然言語処理分野では、統語的な情報が付与された構文木コーパスから、確率的文法モデルに基づいて、文法規則を学習することが行われている。ここで、図５に構文木の例を示す。図５の例では、木構造の末端ノードには単語が付与されており、それ以外のノードには統語情報を表すシンボルが付与されている。図５において、“ＮＰ”は名詞句、“ＤＴ”は前置詞、“Ｎ”は名詞、及び“ＪＪ”は形容詞を表すシンボルである。また、確率的文法モデルの例として、文脈自由文法、木置換文法、木接合文法などに基づくモデルがある。図６に、図５に示す構文木から木置換文法に従って得られる文法規則の例を示す。木置換文法における各文法規則は、構文木の部分構造（部分木）となっている。

また、構文木コーパスから文法規則を学習する方法として、ギブスサンプリング法を用いた方法が提案されている（例えば、非特許文献１参照）。ギブスサンプリング法では、構文木を一つずつ巡回し、対象となる構文木を構成する現在の部分木の割り当てを確率的に更新していく方法である。ギブスサンプリング法では、部分木の割り当てを更新する度に確率的文法モデルの尤度を計算し、最も尤度の高かった部分木の割り当てを最終的な文法規則として出力する。

Trevor Cohn, Sharon Goldwater, and Phil Blunsom, "Inducing compact but accurate tree-substitution grammars," In Proceedings of HLT-NAACL, pages 548-556, Boulder, Colorado, June. Association for Computational Linguistics, 2009.

しかしながら、非特許文献１に記載のギブスサンプリング法のように、部分木を一つずつ更新して文法規則を学習する手法では、構文木コーパスのデータ量が多い場合に、局所最適解へ留まってしまい、確率的文法モデルにおける尤度が高い文法規則を学習することができない、という問題がある。

本発明は、上記問題点を解決するために成されたものであり、確率的文法モデルにおける尤度が高い文法規則を学習することができる文法規則学習装置、方法、及びプログラムを提供することを目的とする。

上記目的を達成するために、本発明の文法規則学習装置は、複数種類の複数の部分木と所定のパラメータとで複数の構文木を表した確率的文法モデルにおける前記複数の部分木及び前記所定のパラメータの初期値を設定する初期設定部と、構文木を構成する部分木の割り当てを確率的に更新する手法により、前記初期設定部により設定された前記複数の部分木及び前記所定のパラメータ、または前回更新された複数の部分木及び所定のパラメータを更新する更新部と、前記更新部により更新された前記複数の部分木に含まれる第１の種類の部分木を分割して構成される部分木候補の各々から、前記所定のパラメータで表された前記確率的文法モデルにおける各部分木候補と該部分木候補を含む構文木集合との同時確率に応じて選択される部分木候補を第２の種類の部分木とし、前記複数の構文木に含まれる全ての前記第１の種類の部分木を、前記第２の種類の部分木に置換して、前記所定のパラメータを更新する置換更新部と、予め定めた終了条件を満たすまで、前記更新部による前記複数の部分木及び前記所定のパラメータの更新、並びに前記置換更新部による部分木の置換及び前記所定のパラメータの更新を繰り返し、前記終了条件を満たした際の前記複数の部分木の各々を文法規則として、前記終了条件を満たした際の所定のパラメータと共に出力する終了判定部と、を含んで構成されている。

本発明の文法規則学習装置によれば、初期設定部が、複数種類の複数の部分木と所定のパラメータとで複数の構文木を表した確率的文法モデルにおける複数の部分木及び所定のパラメータの初期値を設定する。そして、更新部が、構文木を構成する部分木の割り当てを確率的に更新する手法により、初期設定部により設定された複数の部分木及び所定のパラメータ、または前回更新された複数の部分木及び所定のパラメータを更新する。更新部による複数の部分木及び所定のパラメータの更新は、例えば、ギブスサンプリング法等の従来手法を用いることができる。

そして、置換更新部が、更新部により更新された複数の部分木に含まれる第１の種類の部分木を分割して構成される部分木候補の各々から、所定のパラメータで表された確率的文法モデルにおける各部分木候補と部分木候補を含む構文木集合との同時確率に応じて選択される部分木候補を第２の種類の部分木とし、複数の構文木に含まれる全ての第１の種類の部分木を、第２の種類の部分木に置換して、所定のパラメータを更新する。そして、終了判定部が、予め定めた終了条件を満たすまで、更新部による複数の部分木及び所定のパラメータの更新、並びに置換更新部による部分木の置換及び所定のパラメータの更新を繰り返し、終了条件を満たした際の複数の部分木の各々を文法規則として、終了条件を満たした際の所定のパラメータと共に出力する。

このように、複数の構文木を構成する複数の部分木に含まれる第１の種類の部分木を、一度に第２の種類の部分木に置換して、複数の構文木を表す確率的文法モデルのパラメータを更新することにより、部分木の頻度分布を大幅に変更できるため、確率的文法モデルにおける尤度が高い文法規則を学習することができる。

また、前記置換更新部は、前記第１の種類の部分木を分割して構成される部分木候補の各々から、前記所定のパラメータで表された前記確率的文法モデルにおける各部分木候補と該部分木候補を含む構文木集合との同時確率に応じて選択された部分木候補を、前記第２の種類の部分木とすることができる。これにより、部分木の頻度分布を多様に変更することができるため、より尤度の高い文法規則を学習することができる。

また、本発明の文法規則学習方法は、初期設定部が、複数種類の複数の部分木と所定のパラメータとで複数の構文木を表した確率的文法モデルにおける前記複数の部分木及び前記所定のパラメータの初期値を設定するステップと、更新部が、前記初期設定部により設定された前記複数の部分木及び前記所定のパラメータ、または前回更新された複数の部分木及び所定のパラメータを更新するステップと、置換更新部が、前記更新部により更新された前記複数の部分木に含まれる第１の種類の部分木を、前記第１の種類とは異なる第２の種類の部分木に置換して、前記所定のパラメータを更新するステップと、終了判定部が、予め定めた終了条件を満たすまで、前記更新部による前記複数の部分木及び前記所定のパラメータの更新、並びに前記置換更新部による部分木の置換及び前記所定のパラメータの更新を繰り返し、前記終了条件を満たした際の前記複数の部分木の各々を文法規則として、前記終了条件を満たした際の所定のパラメータと共に出力するステップと、を含む方法である。

また、本発明の文法規則学習プログラムは、コンピュータを、上記の文法規則学習装置を構成する各部として機能させるためのプログラムである。

以上説明したように、本発明の文法規則学習装置、方法、及びプログラムによれば、複数の構文木を構成する複数の部分木に含まれる第１の種類の部分木を、一度に第２の種類の部分木に置換して、複数の構文木を表す確率的文法モデルのパラメータを更新することにより、部分木の頻度分布を大幅に変更できるため、確率的文法モデルにおける尤度が高い文法規則を学習することができる、という効果が得られる。

本実施の形態に係る文法規則学習装置の機能的構成を示すブロック図である。部分木の置換を説明するための概略図である。本実施の形態における文法規則学習処理ルーチンの内容を示すフローチャートである。本実施の形態における手法と従来手法との確率的文法モデルの尤度を比較した結果を示す図である。構文木の一例を示す図である。図５に示す構文木から木置換文法に従って得られる文法規則の一例を示す図である。

以下、図面を参照して本発明の実施の形態を詳細に説明する。

図１に示すように、本実施の形態に係る文法規則学習装置１０は、統語的な情報が付与された構文木ｔの集合である構文木コーパス｛ｔ｝を入力とし、確率的文法モデルの尤度を最大にする最適な文法規則、すなわち、部分木の集合を出力する。本実施の形態では、確率的文法モデルとして、木置換文法による確率的文法モデル（例えば、非特許文献１参照）を用いる場合を例に説明する。

ここで、木置換文法では、具体的な確率的文法モデルの式は、例えば下記（１）式のように与えられる。

ただし、ｅ_ｔは、一つの構文木ｔを構成する部分木ｅの集合、｛ｅ_ｔ｝は、構文木コーパス｛ｔ｝全体での部分木ｅの集合、Ｐ（｛ｅ_ｔ｝，｛ｔ｝｜θ）は、パラメータをθとする確率的文法モデルにおける部分木の集合｛ｅ_ｔ｝と構文木コーパス｛ｔ｝との同時確率である。また、ｉは、構文木コーパス中の構文木を指すインデックス、ｊは、構文木ｔを構成する部分木を指すインデックス、Ｉは、構文木コーパスに含まれる構文木の総数、Ｊは、構文木ｔを構成する部分木ｅの総数である。また、Ｘは、部分木ｅの根ノードのシンボルを表し、ｎ_ｅは、部分木ｅが構文木コーパス中に何回出現したかを表す回数である。また、θ_Ｘは、木置換文法のパラメータであり、根ノードのシンボルＸ毎に定義されている。従って、確率的文法モデルのパラメータは、θ_Ｘの集合、すなわち、θ＝｛θ_Ｘ｝となる。ｎ_．，Ｘは、根ノードがＸである部分木が、構文木コーパス中に何回出現したかを表す回数である。Ｐ_０（ｅ｜Ｘ）は、部分木ｅの基底確率と呼ばれる確率で、例えば一様分布に基づいて計算される。

文法規則学習装置１０は、構文木コーパス｛ｔ｝を入力とし、（１）式に示すような確率的文法モデルの尤度Ｐ（｛ｅ_ｔ｝，｛ｔ｝｜θ）を最大にする文法規則｛＾ｅ_ｔ｝及びパラメータ＾θを出力する。

文法規則学習装置１０は、ＣＰＵと、ＲＡＭと、後述する文法規則学習処理ルーチンを実行するための文法規則学習プログラムを記憶したＲＯＭと、を備えたコンピュータで構成されている。すなわち、ＲＯＭに記憶された文法規則学習プログラムをＣＰＵが実行することにより、コンピュータが文法規則学習装置１０として機能する。また、コンピュータを、記憶手段としてのＨＤＤを含んで構成するようにしてもよい。

このコンピュータは、機能的には、図１に示すように、初期設定部１１、ギブスサンプリング部１２、置換更新部１３、及び終了判定部１４を含んだ構成で表すことができる。なお、初期設定部１１及びギブスサンプリング部１２は、本発明の設定部の一例である。

初期設定部１１は、構文木コーパス｛ｔ｝を入力として受け付け、初期部分木｛ｅ_ｔ｝^（０）及び初期パラメータθ^（０）を設定する。初期部分木｛ｅ_ｔ｝^（０）は、例えば、末端ノード及び根ノードを除く構文木の各ノードに対して、ランダムに０または１の変数を割り当て、１の変数が割り当てられたノードを部分木の根ノードに設定し、０の変数が割り当てられたノードを部分木の内部ノード（部分木の根ノード以外のノード）に設定することができる。初期パラメータθ^（０）についても、ランダムに設定することができる。初期設定部１１は、設定した初期部分木｛ｅ_ｔ｝^（０）及び初期パラメータθ^（０）を、ギブスサンプリング部１２へ出力する。

ギブスサンプリング部１２は、初期部分木｛ｅ_ｔ｝^（０）及び初期パラメータθ^（０）、または後述する終了判定部１４から出力された部分木｛ｅ_ｔ｝^{（ｕ＋１）}及びパラメータθ^{（ｕ＋１）}を入力として受け付ける。なお、ｕは、更新処理の繰り返し回数を表す変数である。ギブスサンプリング部１２は、例えば、非特許文献１に開示されているように、構文木の各ノードをランダムな順番で巡回しながら各ノードを処理対象の対象ノードとする。そして、ギブスサンプリング部１２は、対象ノードが部分木の根ノードか内部ノードかを確率的に決定し、対象ノードに対する現在の設定を更新する。

また、ギブスサンプリング部１２は、構文木の全てのノードを対象ノードとして設定を更新する処理が終了すると、（１）式に基づいてパラメータθを更新する。パラメータθの更新方法として、例えば、非特許文献１に開示されているサンプリング法に基づく方法を用いることができる。この方法では、パラメータθの確率分布Ｐ（θ）がガンマ分布Ｇａｍｍａ（１．０，１．０）に従うと仮定して、Ｐ（｛ｅ_ｔ-｝，｛ｔ｝，θ）＝Ｐ（｛ｅ_ｔ-｝，｛ｔ｝｜θ）×Ｐ（θ）を計算する。そして、｛ｅ_ｔ-｝を全て固定した上で、下記（２）式に示す更新後のθ’を、マルコフ連鎖モンテカルロ法で探索し、パラメータθをθ’に更新する。

ギブスサンプリング部１２は、更新した部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を出力する。

置換更新部１３は、ギブスサンプリング部１２により更新された部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を入力として受け付ける。置換更新部１３は、構文木の各ノードを巡回するのではなく、部分木｛ｅ_ｔ｝^（ｕ）を一種類ずつランダムな順番で巡回しながら各部分木を処理対象の対象部分木とし、対象部分木ｅを、別の部分木ｅ’へ、Ｐ（ｅ’，｛ｔ｝｜θ）の確率に応じて置換する。ただし、｛ｔ｝は、別の部分木ｅ’を含む構文木ｔの集合である。Ｐ（ｅ’，｛ｔ｝｜θ）の確率は、下記（３）式のように計算される。

ただし、ｋは｛ｔ｝に含まれる構文木を指すインデックスであり、Ｋは｛ｔ｝に含まれる構文木の総数である。また、Ｐ（ｅ’，ｔ_ｋ｜θ）は、（１）式下段に示す、パラメータをθとする確率的文法モデルにおける部分木ｅ’と構文木ｔとの同時確率である。
このとき、部分木ｅ’の候補として、対象部分木ｅを分割して構成される全ての部分木の組み合わせを考慮する。図２に示すような部分木ｅが対象部分木の場合、対象部分木ｅを分割して構成できる全ての部分木の組み合わせ（図２中のｅ’_（１）〜ｅ’_（４））を部分木ｅ’の候補とする。ただし、部分木ｅと部分木ｅ’とが同じ部分木になる場合もある。図２の例では、部分木ｅ’_（４）が対象部分木ｅと同じ部分木である。置換更新部１３は、各部分木の候補ｅ’の確率Ｐ（ｅ’，｛ｔ｝｜θ）に応じて、１つの候補を選択し、構文木コーパス｛ｔ｝に含まれる全ての部分木ｅを、選択した部分木ｅ’へ置換する。

置換更新部１３は、部分木の置換が完了したら、ギブスサンプリング部１２と同様に、パラメータθを更新する。置換更新部１３では、構文木コーパス｛ｔ｝に含まれる複数の同じ種類の部分木を一度に更新するため、ギブスサンプリング部１２による更新よりも、部分木の頻度分布を大幅に変更できる可能性がある。従って、単にギブスサンプリングを何度も繰り返すよりも、尤度の高い部分木の割り当てを発見できる可能性が高まり、確率的文法モデルが局所最適解に留まってしまう問題を解消することができる。置換更新部１３は、更新した部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を出力する。

終了判定部１４は、置換更新部１３により更新された部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を入力として受け付ける。終了判定部１４は、終了条件を満たしたか否かを判定し、終了条件を満たすまで、ギブスサンプリング部１２及び置換更新部１３の処理を繰り返す。終了判定は、例えば、現在の繰り返し回数ｕが、予め指定された回数（例えば３０００回）となったときに終了と判定し、それ未満であれば未終了と判定することができる。終了判定部１４は、終了条件を満たしたと判定した場合には、現在の部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を、それぞれ確率的文法モデルの尤度を最大にする文法規則｛＾ｅ_ｔ｝及びパラメータ＾θとして出力する。

また、終了判定部１４は、終了条件を満たしていないと判定した場合には、繰り返し回数ｕを１つ増やし、現在の部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を、｛ｅ_ｔ｝^{（ｕ＋１）}及びθ^{（ｕ＋１）}としてギブスサンプリング部１２へ出力する。

なお、終了判定部１４による終了条件の判定は、繰り返し回数が指定された回数となったか否かを判定する場合に限定されない。例えば、置換更新部１３により更新された｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）に基づいて今回算出された確率的文法モデルの尤度と、前回算出された尤度との差が所定値以下となった場合に、終了条件を満たすと判定してもよい。

次に、本実施の形態に係る文法規則学習装置１０の作用について説明する。文法規則学習装置１０に、構文木コーパス｛ｔ｝が入力されると、文法規則学習装置１０において、図３に示す文法規則学習処理ルーチンが実行される。なお、文法規則学習装置１０への構文木コーパス｛ｔ｝の入力は、外部装置や外部記憶媒体等に記憶された構文木コーパス｛ｔ｝を、ネットワーク等を介して文法規則学習装置１０内の記憶装置へ読み込むことにより行われる。また、予め文法規則学習装置１０内の記憶装置に記憶された構文木コーパス｛ｔ｝を読み出して、図３に示す文法規則学習処理ルーチンを開始するようにしてもよい。

図３に示す文法規則学習処理ルーチンのステップ１００で、初期設定部１１が、構文木コーパス｛ｔ｝を入力として受け付け、初期部分木｛ｅ_ｔ｝^（０）及び初期パラメータθ^（０）を設定する。次に、ステップ１０２で、終了判定部１４が、繰り返し回数を示す変数ｕを０に設定する。

次に、ステップ１０４で、ギブスサンプリング部１２が、例えば非特許文献１に開示されているように、構文木の各ノードをランダムな順番で巡回しながら各ノードを対象ノードとし、対象ノードが部分木の根ノードか内部ノードかを確率的に決定し、対象ノードに対する現在の設定を更新し、（１）式に基づいてパラメータθを更新する。

次に、ステップ１０６で、置換更新部１３が、部分木｛ｅ_ｔ｝^（ｕ）を一種類ずつランダムな順番で巡回しながら各部分木を対象部分木とし、対象部分木ｅを分割して構成される全ての部分木の組み合わせを部分木ｅ’の候補とする。そして、置換更新部１３は、各部分木の候補ｅ’の確率Ｐ（ｅ’，｛ｔ｝｜θ）に応じて、１つの候補を選択し、構文木コーパス｛ｔ｝に含まれる全ての部分木ｅを、選択した部分木ｅ’へ置換する。さらに、置換更新部１３は、ギブスサンプリング部１２と同様に、パラメータθを更新する。

次に、ステップ１０８で、終了判定部１４が、現在の繰り返し回数ｕが、予め指定された回数（例えば３０００回）となったか否かを判定することにより、終了条件を満たすか否かを判定する。終了判定部１４は、終了条件を満たしていないと判定した場合には、ステップ１１０へ移行して、繰り返し回数ｕを１つ増やし、現在の部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を、｛ｅ_ｔ｝^{（ｕ＋１）}及びθ^{（ｕ＋１）}としてギブスサンプリング部１２へ出力し、ステップ１０４へ戻る。繰り返し処理におけるステップ１０４では、ギブスサンプリング部１２が、更新された｛ｅ_ｔ｝^{（ｕ＋１）}及びθ^{（ｕ＋１）}を用いて、対象ノードの設定の更新及びパラメータθの更新を繰り返す。また、繰り返し処理におけるステップ１０６では、置換更新部１３が、ギブスサンプリング部１２により更新された｛ｅ_ｔ｝^{（ｕ＋１）}及びθ^{（ｕ＋１）}を用いて、部分木の置換及びパラメータθの更新を繰り返す。

一方、終了判定部１４は、終了条件を満たしたと判定した場合には、ステップ１１２へ移行し、現在の部分木｛ｅ_ｔ｝^（ｕ）及びパラメータθ^（ｕ）を、それぞれ確率的文法モデルの尤度を最大にする文法規則｛＾ｅ_ｔ｝及びパラメータ＾θとして出力し、文法規則学習処理ルーチンを終了する。

以上説明したように、本実施の形態に係る文法規則学習装置によれば、構文木コーパスに含まれる複数の同じ種類の部分木を一度に別の部分木に置換して、確率的文法モデルのパラメータを更新する。これにより、従来手法のように、部分木を局所的に更新する場合に比べ、部分木の頻度分布を大幅に変更できるため、尤度の高い部分木の割り当て、すなわち尤度の高い文法規則を発見できる可能性が高まり、確率的文法モデルが局所最適解に留まってしまう問題を解消することができる。また、部分木を別の部分木に置換する際に、元の部分木を分割して構成される全ての部分木の組み合わせを候補として考慮するため、部分木の頻度分布を多様に変更することができる。

ここで、本実施の形態に係る文法規則学習装置の効果を検証するため、置換更新部がある場合（本実施の形態）と、置換更新部がない場合（単純なギブスサンプリング法による従来手法）との尤度を比較した実験結果を図４に示す。本実験では、構文木コーパスは約４万文の構文木で構成されており、繰り返し回数ｕは１０００回とした。図４に示すように、本実施の形態に係る文法規則学習装置は、置換更新部の効果により、従来手法よりも尤度の高い文法規則を発見できることを確認した。

本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。

また、上述の文法規則学習装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。

また、本願明細書中において、プログラムが予めインストールされている実施の形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。

１０文法規則学習装置
１１初期設定部
１２ギブスサンプリング部
１３置換更新部
１４終了判定部

Claims

複数種類の複数の部分木と所定のパラメータとで複数の構文木を表した確率的文法モデルにおける前記複数の部分木及び前記所定のパラメータの初期値を設定する初期設定部と、
構文木を構成する部分木の割り当てを確率的に更新する手法により、前記初期設定部により設定された前記複数の部分木及び前記所定のパラメータ、または前回更新された複数の部分木及び所定のパラメータを更新する更新部と、
前記更新部により更新された前記複数の部分木に含まれる第１の種類の部分木を分割して構成される部分木候補の各々から、前記所定のパラメータで表された前記確率的文法モデルにおける各部分木候補と該部分木候補を含む構文木集合との同時確率に応じて選択される部分木候補を第２の種類の部分木とし、前記複数の構文木に含まれる全ての前記第１の種類の部分木を、前記第２の種類の部分木に置換して、前記所定のパラメータを更新する置換更新部と、
予め定めた終了条件を満たすまで、前記更新部による前記複数の部分木及び前記所定のパラメータの更新、並びに前記置換更新部による部分木の置換及び前記所定のパラメータの更新を繰り返し、前記終了条件を満たした際の前記複数の部分木の各々を文法規則として、前記終了条件を満たした際の所定のパラメータと共に出力する終了判定部と、
を含む文法規則学習装置。
初期設定部が、複数種類の複数の部分木と所定のパラメータとで複数の構文木を表した確率的文法モデルにおける前記複数の部分木及び前記所定のパラメータの初期値を設定するステップと、
更新部が、構文木を構成する部分木の割り当てを確率的に更新する手法により、前記初期設定部により設定された前記複数の部分木及び前記所定のパラメータ、または前回更新された複数の部分木及び所定のパラメータを更新するステップと、
置換更新部が、前記更新部により更新された前記複数の部分木に含まれる第１の種類の部分木を分割して構成される部分木候補の各々から、前記所定のパラメータで表された前記確率的文法モデルにおける各部分木候補と該部分木候補を含む構文木集合との同時確率に応じて選択される部分木候補を第２の種類の部分木とし、前記複数の構文木に含まれる全ての前記第１の種類の部分木を、前記第２の種類の部分木に置換して、前記所定のパラメータを更新するステップと、
終了判定部が、予め定めた終了条件を満たすまで、前記更新部による前記複数の部分木及び前記所定のパラメータの更新、並びに前記置換更新部による部分木の置換及び前記所定のパラメータの更新を繰り返し、前記終了条件を満たした際の前記複数の部分木の各々を文法規則として、前記終了条件を満たした際の所定のパラメータと共に出力するステップと、
を含む文法規則学習方法。
コンピュータを、請求項１の文法規則学習装置を構成する各部として機能させるための文法規則学習プログラム。