(57)【特許請求の範囲】
【請求項１】
文ｘと前記文ｘの構文解析結果を表す構文木ｙとのペアの集合からなる学習データの構文木ｙの各々から文法規則ｒの集合Ｒを抽出する文法規則集合抽出部と、
前記学習データに基づいて、前記学習データの構文木ｙの各々について、単語を表すラベル及び品詞を表すラベルとは異なるラベルの各々を、仮想的なラベルに変換して、簡単化された構文木ｙ￣を生成する構文木簡単化部と、
前記学習データの構文木ｙの各々について簡単化された構文木ｙ￣から文法規則ｒ￣の集合Ｒ￣を抽出すると共に、前記仮想的なラベルを用いた変換前の文法規則ｒと、前記文法規則集合抽出部によって抽出された前記文法規則ｒの集合Ｒに含まれる、前記仮想的なラベルを用いて変換された文法規則ｒ￣との対応関係を求め、前記対応関係に基づいて、前記仮想的なラベルを用いて変換された文法規則ｒ￣を、前記仮想的なラベルを用いた変換前の文法規則ｒに変換するための変換関数を生成する簡単化文法規則集合抽出部と、
前記学習データの前記ペアの各々について、前記ペアの文ｘと前記簡単化された構文木ｙ￣とから抽出される特徴量のベクトルｆ￣（ｘ，ｙ￣）と、前記特徴量のベクトルｆ￣（ｘ，ｙ￣）に対応する重みベクトルｗ￣とに基づいてスコアを計算し、前記スコアに応じて前記重みベクトルｗ￣を更新する簡単化構文木用重みベクトル更新部と、
を含む文法規則フィルターモデル学習装置。
【請求項２】
前記学習データの前記ペアの各々について、前記ペアの文ｘと前記構文木ｙとから抽出される特徴量のベクトルｆ（ｘ，ｙ）と、前記特徴量のベクトルｆ（ｘ，ｙ）に対応する重みベクトルｗとに基づいてスコアを計算し、前記スコアに応じて前記重みベクトルｗを更新する学習部を更に含む請求項１記載の文法規則フィルターモデル学習装置。
【請求項３】
前記簡単化構文木用重みベクトル更新部は、前記学習データの前記ペアの各々について前記スコアを計算し、前記スコアに応じて前記重みベクトルｗ￣を更新することを、予め定められた繰り返し回数だけ繰り返す請求項１又は２記載の文法規則フィルターモデル学習装置。
【請求項４】
文の構文解析結果を表す構文木ｙに含まれる、単語を表すラベル及び品詞を表すラベルとは異なるラベルの各々を仮想的なラベルに変換して簡単化された構文木ｙ￣から抽出された文法規則ｒ￣の集合Ｒ￣と、文ｘ及び前記簡単化された構文木ｙ￣から抽出される特徴量のベクトルｆ￣（ｘ，ｙ￣）に対応する予め学習された重みベクトルｗ￣と、入力文ｘとに基づいて、基準スコアを計算するスコア計算部と、
前記文法規則ｒ￣の集合Ｒ￣に含まれる前記文法規則ｒ￣の各々について、前記重みベクトルｗ￣、前記入力文ｘ、及び前記入力文ｘの構文解析結果を表す、前記文法規則ｒ￣を含み、かつ、前記簡単化された構文木ｙ￣に基づいて計算されるスコアと、前記基準スコアとに応じて、前記仮想的なラベルを用いた変換前の文法規則ｒと、前記仮想的なラベルを用いて変換された文法規則ｒ￣との対応関係に基づいて予め生成された、前記仮想的なラベルを用いて変換された文法規則ｒ￣を、前記仮想的なラベルを用いた変換前の文法規則ｒに変換するための変換関数を用いて、前記文法規則ｒ￣を、前記仮想的なラベルを用いた変換前の文法規則ｒに変換して、前記仮想的なラベルを用いていない文法規則ｒの集合Ｒ´に追加する文法規則追加部と
を含む文法規則フィルター装置。
【請求項５】
請求項４記載の文法規則フィルター装置と、
前記文法規則フィルター装置によって得られた前記文法規則ｒの集合Ｒ´と、文ｘと前記文ｘの構文解析結果を表す構文木ｙから抽出される特徴量ベクトルｆ（ｘ，ｙ）に対応する予め学習された重みベクトルｗと、前記入力文ｘとに基づいて、前記文法規則ｒの集合Ｒ´に含まれる文法規則ｒを用いて前記入力文ｘの構文解析結果を表す構文木ｙと前記入力文ｘとから抽出される特徴量のベクトルｆ（ｘ，ｙ）と、前記重みベクトルｗとに基づいて計算されるスコアが最大となる、前記入力文ｘの構文解析結果を表す構文木ｙ＾を探索する解析部
を含む構文解析装置。
【請求項６】
コンピュータを、請求項１〜３の何れか１項記載の文法規則フィルターモデル学習装置の各部として機能させるためのプログラム。
【請求項７】
コンピュータを、請求項４記載の文法規則フィルター装置の各部として機能させるためのプログラム。
【請求項８】
コンピュータを、請求項５記載の構文解析装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文の構文解析を行うための文法規則フィルターモデル学習装置、文法規則フィルター装置、構文解析装置、及びプログラムに関するものである。
【背景技術】
【０００２】
従来より、モデル学習装置、及び、解析装置から構成される統計的構文解析装置が知られている（非特許文献１）。モデル学習装置は、文と構文木とのペアの集合から文法規則集合、及び、モデルの重みベクトルを出力する。解析装置は、モデル学習装置で出力した文法規則集合、及び、重みベクトルを受け取り、解析したい文に対して、最も高いスコアを持つ構文木を出力する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Jenny Rose Finkel, Alex Kleeman, and Christopher D Manning. Efficient, feature-based, conditional random field parsing. In ACL, volume 46, pages 959-967, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、上述した従来の統計的構文解析装置では、文法規則の組み合わせにより膨大な数の解候補が考えられるため、全ての解候補をスコア付けすることは大きな計算時間を要する。
【０００５】
本発明では、上記問題点を解決するために成されたものであり、文の構文解析を高速に行うために文法規則を減らすことができる文法規則フィルターモデル学習装置、文法規則フィルター装置、構文解析装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明に係る文法規則フィルターモデル学習装置は、文ｘと前記文ｘの構文解析結果を表す構文木ｙとのペアの集合からなる学習データに基づいて、前記学習データの構文木ｙの各々について、単語を表すラベル及び品詞を表すラベルとは異なるラベルの各々を、仮想的なラベルに変換して、簡単化された構文木ｙ￣を生成する構文木簡単化部と、前記学習データの構文木ｙの各々について簡単化された構文木ｙ￣から文法規則ｒ￣の集合Ｒ￣を抽出すると共に、前記仮想的なラベルを用いて変換された文法規則ｒ￣を、前記仮想的なラベルを用いた変換前の文法規則ｒに変換するための変換関数を生成する簡単化文法規則集合抽出部と、前記学習データの前記ペアの各々について、前記ペアの文ｘと前記簡単化された構文木ｙ￣とから抽出される特徴量のベクトルｆ￣（ｘ，ｙ￣）と、前記特徴量のベクトルｆ￣（ｘ，ｙ￣）に対応する重みベクトルｗ￣とに基づいてスコアを計算し、前記スコアに応じて前記重みベクトルｗ￣を更新する簡単化構文木用重みベクトル更新部と、を含んで構成されている。
【０００７】
本発明に係る文法規則フィルター装置は、文の構文解析結果を表す構文木ｙに含まれる、単語を表すラベル及び品詞を表すラベルとは異なるラベルの各々を仮想的なラベルに変換して簡単化された構文木ｙ￣から抽出された文法規則ｒ￣の集合Ｒ￣と、文ｘ及び前記簡単化された構文木ｙ￣から抽出される特徴量のベクトルｆ￣（ｘ，ｙ￣）に対応する予め学習された重みベクトルｗ￣と、入力文ｘとに基づいて、基準スコアを計算するスコア計算部と、前記文法規則ｒ￣の集合Ｒ￣に含まれる前記文法規則ｒ￣の各々について、前記重みベクトルｗ￣、前記入力文ｘ、及び前記入力文ｘの構文解析結果を表す、前記文法規則ｒ￣を含み、かつ、前記簡単化された構文木ｙ￣に基づいて計算されるスコアと、前記基準スコアとに応じて、前記文法規則ｒ￣を、前記仮想的なラベルを用いた変換前の文法規則ｒに変換して、前記仮想的なラベルを用いていない文法規則ｒの集合Ｒ´に追加する文法規則追加部とを含んで構成されている。
【０００８】
本発明に係る構文解析装置は、上記の文法規則フィルター装置によって得られた前記文法規則ｒの集合Ｒ´と、文ｘと前記文ｘの構文解析結果を表す構文木ｙから抽出される特徴量ベクトルｆ（ｘ，ｙ）に対応する予め学習された重みベクトルｗと、前記入力文ｘとに基づいて、前記文法規則ｒの集合Ｒ´に含まれる文法規則ｒを用いて前記入力文ｘの構文解析結果を表す構文木ｙと前記入力文ｘとから抽出される特徴量のベクトルｆ（ｘ，ｙ）と、前記重みベクトルｗとに基づいて計算されるスコアが最大となる、前記入力文ｘの構文解析結果を表す構文木ｙ＾を探索する解析部を含んで構成されている。
【０００９】
また、本発明のプログラムは、コンピュータを、上記の文法規則フィルターモデル学習装置、文法規則フィルター装置、又は構文解析装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１０】
以上説明したように、本発明の文法規則フィルターモデル学習装置及びプログラムによれば、学習データの構文木ｙの各々について、簡単化された構文木ｙ￣を生成して、文法規則ｒ￣の集合Ｒ￣を抽出し、学習データのペアの各々について、前記ペアの特徴量のベクトルｆ￣（ｘ，ｙ￣）と、重みベクトルｗ￣とに基づいてスコアを計算し、前記スコアに応じて前記重みベクトルｗ￣を更新することにより、文の構文解析を高速に行うために文法規則を減らすことができる文法規則フィルターを学習することができる。
【００１１】
本発明の文法規則フィルター装置及びプログラムによれば、簡単化された構文木ｙ￣から抽出された文法規則ｒ￣の集合Ｒ￣と、特徴量のベクトルｆ￣（ｘ，ｙ￣）に対応する予め学習された重みベクトルｗ￣と、入力文ｘとに基づいて、基準スコアを計算し、前記文法規則ｒ￣の各々について、前記入力文ｘの構文解析結果を表す、前記文法規則ｒ￣を含む構文木ｙ￣に基づいて計算されるスコアと、前記基準スコアとに応じて、前記文法規則ｒ￣を、変換前の文法規則ｒに変換して、文法規則ｒの集合Ｒ´に追加することにより、文の構文解析を高速に行うために文法規則を減らすことができる。
【００１２】
本発明の構文解析装置及びプログラムによれば、文の構文解析を高速に行うことができる。
【図面の簡単な説明】
【００１３】
【図１】入力となる文の一例を示す図である。
【図２】構文木の一例を示す図である。
【図３】本発明の実施形態に係る構文解析装置の機能的構成を示すブロック図である。
【図４】本発明の実施形態に係る構文解析装置の学習部の構成を示すブロック図である。
【図５】文法規則の集合の一例を示す図である。
【図６】本発明の実施形態に係る構文解析装置の規則フィルターモデル学習部の構成を示すブロック図である。
【図７】簡単化された構文木の一例を示す図である。
【図８】簡単化された構文木から抽出された文法規則の集合の一例を示す図である。
【図９】本発明の実施形態に係る構文解析装置の規則フィルター部の構成を示すブロック図である。
【図１０】本発明の実施形態に係る構文解析装置における規則フィルターモデル学習処理ルーチンのフローチャート図である。
【図１１】本発明の実施形態に係る構文解析装置における構文解析処理ルーチンのフローチャート図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００１５】
＜本実施の形態の概要＞
まず、本発明の実施の形態の概要について説明する。本実施の形態は、自然言語処理などの分野で使用される統計的構文解析装置に関するものである。構文解析装置とは入力として単語列を受け取り、その単語列の構文構造を表す木構造を出力する装置である。入力となる単語列(インデックス付き)とは図１に示すような文のことをいう。これに対する構文木とは図２のようなものをいう。構文木は、単語ラベル、単語ラベルのすぐ上にのみ現れる品詞ラベル(NN、V、DTなど)、及び句ラベル(S、VP、NPなど)を使って階層的に構成される。
【００１６】
統計的構文解析装置は、文とその正解構文木のペアから成る集合(学習データ)を使って、文法規則集合、及び文と構文木のペアをスコア付けする統計モデルを予め構築する。ここでいう文法規則とは、
【００１７】
NN→I
【００１８】
のように1つの単語を子供、１つの品詞ラベルを親とする規則、及び、
【００１９】
S→NP VP
VP→V NP
【００２０】
のように1つ以上の品詞または句ラベルを子供とし、1つの句ラベルを親とするような規
【００２１】
則をいう。そして、構文解析装置に文が入力されると、文法規則集合、及び、統計モデルを使って、最も高いスコアを持つ構文木を構築して出力する。出力された構文木は機械翻訳などの自然言語処理分野における応用タスクで利用される。
【００２２】
本実施の形態の構文解析装置は、文法規則フィルターモデル学習部、及び、文法規則フィルター部を備えて構成される。この装置は、従来技術の統計的構文解析装置に、文法規則フィルターモデル学習部、及び、文法規則フィルター部を結合した装置である。
【００２３】
規則フィルターモデル学習部は、文と構文木ペアの集合と、従来技術のモデル学習装置から出力された文法規則集合を受け取り、新たな文法規則集合、新たな文法規則を入力の文法規則集合の要素に変換する変換関数、重みベクトル、及び、超パラメータを出力する。
【００２４】
規則フィルター部は、規則フィルターモデル学習装置の出力である新たな文法規則集合、変換関数、重みベクトル、超パラメータを受け取り、入力文に対して、フィルターされた文法規則集合を出力する。
【００２５】
＜本発明の実施の形態に係る構文解析装置の構成＞
次に、本発明の実施の形態に係る構文解析装置の構成について説明する。図３に示すように、本実施の形態に係る構文解析装置１００は、ＣＰＵと、ＲＡＭと、後述する規則フィルターモデル学習処理ルーチン、及び構文解析処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この構文解析装置１００は、機能的には図３に示すように入力部１０と、演算部２０と、出力部９０とを含んで構成されている。
【００２６】
入力部１０は、学習データとして、文と構文木のペアの集合
【００２７】
【数１】
0006482084.tif 000002
【００２８】
を受け付ける。ただし、(x，y)は、文xとその正解構文木yとのペアである。
【００２９】
また、入力部１０は、構文解析の対象となる入力文ｘを受け付ける。
【００３０】
演算部２０は、学習部２２と、文法規則記憶部２４と、規則フィルターモデル学習部２６と、簡易文法規則記憶部２８と、規則フィルター部３０と、解析部３２を含んで構成されている。
【００３１】
学習部２２は、学習データに基づいて、チャート型構文解析を行うための文法規則の集合と、文xと文法規則rから抽出できる特徴量のベクトルに対応する重みベクトルとを学習する。
【００３２】
ここで、チャート型構文解析について説明する。
【００３３】
文xに対して、文法規則集合Rを用いて文ｘの構文木を構築する方法はチャート型構文解析と呼ばれる。統計的構文解析は、
【００３４】
【数２】
0006482084.tif 000003
（１）
【００３５】
で定式化され、チャート型構文解析はこれを遂行する。ここで
【００３６】
【数３】
0006482084.tif 000004
【００３７】
は文ｘに対して文法規則集合Ｒから構築できる構文木の候補集合、rは構文木yを構築するために使われた文法規則、f(x，r)は文xと規則rから抽出できる特徴量のベクトルを返す関数、ｗは各特徴量を重み付けする重みからなる重みベクトルを表す。また、ｆ（ｘ、ｙ）は、構文木ｙに含まれる各規則ｒと文xとから抽出できる特徴量のベクトルｆ（ｘ、ｒ）の総和である。ただし、rは通常の文法規則ではなく、
【００３８】
【数４】
0006482084.tif 000005
【００３９】
のように構文木上で規則がカバーするｘの部分単語列のインデックスが付与された規則になっている(上の例の規則は図２のa telescope をカバーする位置で使用されていることを示す)。以下、構文木yの構築に使われた文法規則rはこのような部分単語列のインデックスが付与されているとする。
【００４０】
学習部２２は、図４に示すように、文法規則集合抽出部２２０と、重みベクトル更新部２２２とを備えている。
【００４１】
文法規則集合抽出部２２０は、学習データＰの構文木ｙの各々から文法規則ｒの集合Ｒを抽出し、文法規則記憶部２４に格納する。
【００４２】
具体的には、学習データＰに含まれる全ての構文木yi (1≦I≦｜P｜) から文法規則ｒを抽出する。抽出された文法規則ｒの集合をＲと書く。例えば、図２で示した２つの構文木からは、図５に示す文法規則の集合が抽出される。
【００４３】
重みベクトル更新部２２２は、学習データＰのペア（ｘi，ｙi）の各々について、当該ペアの文ｘiと前記構文木ｙiとから抽出される特徴量のベクトルｆ（ｘi，ｙi）と、重みベクトルｗとに基づいてスコアを計算し、スコアに応じて重みベクトルｗを更新する。
【００４４】
具体的には、まず、重みベクトルｗの値を全て0にする。
【００４５】
そして、各ペア(xi，yi)∈Pに対して、以下の（２）式に従って、文ｘiの構文木＾ｙiを求める。
【００４６】
【数５】
0006482084.tif 000006
（２）
【００４７】
上記（２）式により構文木＾ｙiを求めた結果、＾ｙi≠ｙiのとき、文ｘi、構文木ｙi、及び上記（２）式で得られた構文木＾ｙiを用いて、以下の（３）式に従って、重みベクトルｗを更新する。
【００４８】
【数６】
0006482084.tif 000007
（３）
【００４９】
上記の手続きを有限回繰り返し、重みベクトル更新部２２２は、最終的に得られた重みベクトルｗを、文法規則記憶部２４に格納する。
【００５０】
規則フィルターモデル学習部２６は、学習データＰと、文法規則記憶部２４に格納された文法規則ｒの集合Ｒとに基づいて、新たな文法規則の集合Ｒ￣、新たな文法規則を入力の文法規則集合の要素に変換する変換関数、重みベクトルｗ￣、及び超パラメータγを学習する。
【００５１】
規則フィルターモデル学習部２６は、図６に示すように、構文木簡単化部２６０と、簡単化文法規則集合抽出部２６２と、簡単化構文木用重みベクトル更新部２６４とを備えている。
【００５２】
構文木簡単化部２６０は、学習データＰに基づいて、学習データＰの構文木ｙiの各々について、単語を表すラベル及び品詞を表すラベルとは異なるラベルの各々を、仮想的なラベルＸに変換して、簡単化された構文木ｙi￣を生成する。
【００５３】
具体的には、構文木ｙiに対して、単語と品詞を除く全てのラベルをＸという仮想的なラベルへと変換する。この変換を構文木の簡単化と呼ぶ。図２の左図の構文木を簡単化した例を図７に示す。全ての(xi，yi)∈Pにおける構文木yiに対して、簡単化を行った結果をyi￣とし、
【００５４】
【数７】
0006482084.tif 000008
【００５５】
とする。
【００５６】
簡単化文法規則集合抽出部２６２は、学習データＰの構文木ｙiの各々について簡単化された構文木ｙi￣から、文法規則ｒ￣の集合Ｒ￣を抽出すると共に、文法規則記憶部２４に記憶された文法規則ｒの集合Ｒを用いて、仮想的なラベルＸを用いて変換された文法規則ｒ￣を、仮想的なラベルＸを用いた変換前の文法規則ｒに変換するための変換関数ｃｏｎｖを生成し、文法規則ｒ￣の集合Ｒ￣と変換関数ｃｏｎｖとを簡易文法規則記憶部２８に格納する。
【００５７】
具体的には、学習データＰに含まれる全ての簡単化された構文木yi￣ (1≦I≦｜P｜) から文法規則ｒ￣を抽出する。図７の簡単化された構文木から抽出される文法規則ｒ￣を、図８に示す。
【００５８】
抽出した文法規則ｒ￣の集合はＲ￣とする。また、このように簡単化された構文木ｙ￣から抽出した文法規則ｒ￣は、
【００５９】
【数８】
0006482084.tif 000009
【００６０】
のように、学習部２２で抽出した文法規則ｒの集合Ｒの要素ｒと対応関係を持つ。関数conv は、仮想的なラベルＸを用いて簡単化された文法規則ｒ￣を引数にとり、それに対応する文法規則ｒの集合Ｒ中の文法規則ｒの集合を返す関数として生成される。
【００６１】
簡単化構文木用重みベクトル更新部２６４は、学習データＰのペア（ｘi，ｙi）の各々について、当該ペア（ｘi，ｙi）の文ｘiと構文木簡単化部２６０で簡単化された構文木ｙi￣とから抽出される特徴量のベクトルｆ￣（ｘ，ｙi￣）と、特徴量のベクトルｆ￣（ｘ，ｙ￣）に対応する重みベクトルｗ￣とに基づいてスコアを計算し、スコアに応じて重みベクトルｗ￣を更新する。
【００６２】
具体的には、
【００６３】
【数９】
0006482084.tif 000010
【００６４】
及び、文法規則ｒ￣の集合Ｒ￣を使って、枝狩りモデルの学習を行う。まず、重みベクトルｗ￣の全ての値を0にし、超パラメータγを0から1の任意の値とする。
【００６５】
そして、各ペア(xi，yi￣)∈Ｐに対して、以下の（４）式に従って、スコアtxi(γ)を計算する。
【００６６】
【数１０】
0006482084.tif 000011
（４）
ただし、
0006482084.tif 000012
【００６７】
ここで、ｆ￣(xi，r￣)は、文xiと簡単化された規則r￣から抽出できる特徴量のベクトルを返す関数とする。
【００６８】
上記（４）式を計算した結果、スコアtxi(γ)と、重みベクトルｗ￣及び特徴量のベクトルｆ￣(xi，ｙ￣)から計算されるスコアｗ￣・ｆ￣(xi，ｙ￣)とを比較して、
【００６９】
【数１１】
0006482084.tif 000013
【００７０】
のとき、文ｘi、構文木ｙi￣、上記（４）式で得られた構文木ｙi￣*を用いて、以下の（５）式に従って、重みベクトルｗ￣を更新する。
【００７１】
【数１２】
0006482084.tif 000014
（５）
【００７２】
ここで、
【００７３】
【数１３】
0006482084.tif 000015
【００７４】
であり、規則ｒ￣を含む構文木
【００７５】
【数１４】
0006482084.tif 000016
【００７６】
の中でスコアが最大のものを探索している。
【００７７】
上記の手続きを有限回繰り返し、簡単化構文木用重みベクトル更新部２６４は、学習された重みベクトルw￣を、簡易文法規則記憶部２８に格納する。また、任意の値が設定された超パラメータγが、簡易文法規則記憶部２８に格納される。
【００７８】
規則フィルター部３０は、入力部１０で受け付けた入力文ｘ、簡易文法規則記憶部２８に記憶されている文法規則ｒ￣の集合Ｒ￣、変換関数conv、重みベクトルｗ￣、及び超パラメータγを入力として、入力文ｘに対して、フィルターされた文法規則ｒの集合Ｒ´を求める。
【００７９】
規則フィルター部３０は、図９に示すように、スコア計算部３００と、文法規則追加部３０２とを備えている。
【００８０】
スコア計算部３００は、入力文ｘと、文法規則ｒ￣の集合Ｒ￣と、重みベクトルｗ￣と、超パラメータγとに基づいて、以下の（６）式に従って、入力文ｘに対する基準スコアｔx（γ）を計算する。
【００８１】
【数１５】
0006482084.tif 000017
（６）
【００８２】
文法規則追加部３０２は、文法規則ｒ￣の集合Ｒ￣に含まれる文法規則ｒ￣の各々について、重みベクトルｗ￣、入力文ｘ、及び入力文ｘの構文解析結果を表す、当該文法規則ｒ￣を含む構文木ｙ￣に基づいて計算されるビタビスコアと、基準スコアｔx（γ）とに応じて、当該文法規則ｒ￣を、仮想的なラベルＸを用いた変換前の文法規則ｒに変換して、仮想的なラベルＸを用いていない文法規則ｒの集合Ｒ´に追加する。
【００８３】
具体的には、まず、集合Ｒ´を空集合で初期化する。
【００８４】
そして、文法規則ｒ￣∈Ｒ￣の各々に対して、
【００８５】
【数１６】
0006482084.tif 000018
【００８６】
となるとき、
【００８７】
【数１７】
0006482084.tif 000019
【００８８】
とする。ここでｒ￣は、入力文ｘのインデックス付きの規則であり、変換関数ｃｏｎｖの返り値である集合に含まれる文法規則にもこのインデックスが継承されるとする。
【００８９】
そして、文法規則追加部３０２は、文法規則ｒの集合Ｒ´を、解析部３２へ出力する。
【００９０】
解析部３２は、入力文ｘ、文法規則ｒの集合Ｒ´、及び文法規則記憶部２４に記憶された重みベクトルｗを入力として、上記（１）式に従って、文法規則ｒの集合Ｒ´に含まれる文法規則ｒを用いて入力文ｘの構文解析結果を表す構文木ｙと入力文ｘとから抽出される特徴量のベクトルｆ（ｘ，ｙ）と、重みベクトルｗとに基づいて計算されるスコアが最大となる、入力文ｘの構文解析結果を表す構文木ｙ＾を探索し、出力部９０により出力する。
【００９１】
＜本発明の実施形態に係る構文解析装置の作用＞
次に、本発明の実施形態に係る構文解析装置１００の作用について説明する。構文解析装置１００は、入力部１０によって、文と構文木のペア(xi，yi)の集合である学習データＰを受け付けると、構文解析装置１００によって、図１０に示す規則フィルターモデル学習処理ルーチンが実行される。
【００９２】
まず、ステップＳ１００において、学習データＰを読み込む。ステップＳ１０２では、学習データＰに含まれる構文木ｙの各々から文法規則ｒの集合Ｒを抽出し、文法規則記憶部２４に格納する。
【００９３】
そして、ステップＳ１０４において、重みベクトルｗを初期化する。ステップＳ１０６では、上記ステップＳ１０２で抽出された文法規則ｒの集合Ｒ、及び初期化され又は更新された重みベクトルｗに基づいて、学習データＰに含まれるペア(xi，yi)の各々に対して、上記（２）式に従って、構文解析を行って、文ｘiの構文木＾ｙiを求め、＾ｙi≠ｙiのとき、文ｘi、構文木ｙi、及び上記（２）式で得られた構文木＾ｙiを用いて、上記（３）式に従って、重みベクトルｗを更新する。
【００９４】
ステップＳ１０８では、上記ステップＳ１０６の処理を、所定回数繰り返し実行したか否かを判定する。上記ステップＳ１０６の処理を、所定回数繰り返し実行していない場合には、上記ステップＳ１０６へ戻る。一方、上記ステップＳ１０６の処理を、所定回数繰り返し実行した場合には、ステップＳ１１０へ移動する。
【００９５】
ステップＳ１１０では、学習データＰに基づいて、学習データＰの構文木ｙiの各々について、単語を表すラベル及び品詞を表すラベルとは異なるラベルの各々を、仮想的なラベルＸに変換して、簡単化された構文木ｙi￣を生成する。
【００９６】
次のステップＳ１１２では、上記ステップＳ１１０で構文木ｙiの各々について簡単化された構文木ｙi￣から文法規則ｒ￣の集合Ｒ￣を抽出すると共に、文法規則記憶部２４に記憶された文法規則の集合Ｒを用いて、仮想的なラベルＸを用いて変換された文法規則ｒ￣を、仮想的なラベルＸを用いた変換前の文法規則ｒに変換するための変換関数ｃｏｎｖを生成し、文法規則ｒ￣の集合Ｒ￣と変換関数ｃｏｎｖとを簡易文法規則記憶部２８に格納する。
【００９７】
ステップＳ１１４では、重みベクトルｗ￣を初期化する。次のステップＳ１１６では、学習データＰのペア（ｘi，ｙi）の各々について、当該ペア（ｘi，ｙi）の文ｘiと簡単化された構文木ｙi￣とから抽出される特徴量のベクトルｆ￣（ｘ，ｙi￣）と、初期化され又は更新された重みベクトルｗ￣とに基づいて、上記（４）式に従って、スコアtxi(γ)を計算し、スコアtxi(γ)が、重みベクトルｗ￣及び特徴量のベクトルｆ￣(xi，ｙ￣)から計算されるスコアｗ￣・ｆ￣(xi，ｙ￣)より大きい場合、文ｘi、構文木ｙi￣、及び上記（４）式で得られた構文木ｙi￣*を用いて、上記（５）式に従って、重みベクトルｗ￣を更新する。
【００９８】
ステップＳ１１８では、上記ステップＳ１１６の処理を、所定回数繰り返し実行したか否かを判定する。上記ステップＳ１１６の処理を、所定回数繰り返し実行していない場合には、上記ステップＳ１１６へ戻る。一方、上記ステップＳ１１６の処理を、所定回数繰り返し実行した場合には、規則フィルターモデル学習処理ルーチンを終了し、学習された重みベクトルｗ￣が、簡易文法規則記憶部２８に格納される。
【００９９】
構文解析装置１００は、入力部１０によって、入力文ｘを受け付けると、構文解析装置１００によって、図１１に示す構文解析処理ルーチンが実行される。
【０１００】
ステップＳ１２０で、入力文ｘを読み込み、ステップＳ１２２では、入力文ｘと、簡易文法規則記憶部２８に記憶されている文法規則ｒ￣の集合Ｒ￣と、重みベクトルｗ￣と、超パラメータγとに基づいて、上記（６）式に従って、入力文ｘに対する基準スコアｔx（γ）を計算する。
【０１０１】
そして、ステップＳ１２４において、文法規則ｒ￣の集合Ｒ￣に含まれる文法規則ｒ￣の各々について、重みベクトルｗ￣、入力文ｘ、及び当該文法規則ｒ￣を含む構文木ｙ￣に基づいて計算されるビタビスコアが、基準スコアｔx（γ）以上となる場合、変換関数ｃｏｎｖにより、当該文法規則ｒ￣を、仮想的なラベルＸを用いた変換前の文法規則ｒの集合に変換して、仮想的なラベルＸを用いていない文法規則ｒの集合Ｒ´に追加する。
【０１０２】
次のステップＳ１２６では、入力文x、文法規則ｒの集合Ｒ´、及び文法規則記憶部２４に記憶された重みベクトルｗを入力として、上記（１）式に従って、文法規則ｒの集合Ｒ´に含まれる文法規則ｒを用いて入力文ｘの構文解析結果を表す構文木ｙから抽出される特徴量のベクトルｆ（ｘ，ｙ）と、重みベクトルｗとに基づいて計算されるスコアが最大となる、入力文ｘの構文木ｙ＾を探索する。そして、ステップＳ１２８において、上記ステップＳ１２６で得られた構文木ｙ＾を、構文解析結果として出力部９０により出力し、構文解析処理ルーチンを終了する。
【０１０３】
以上説明したように、本発明の実施の形態に係る構文解析装置によれば、学習データＰの構文木ｙの各々について、簡単化された構文木ｙ￣を生成して、文法規則ｒ￣の集合Ｒ￣を抽出し、学習データＰのペア（ｘ、ｙ）の各々について、当該ペアに対する特徴量のベクトルｆ￣（ｘ，ｙ￣）と、重みベクトルｗ￣とに基づいてスコアを計算し、スコアに応じて重みベクトルｗ￣を更新することにより、文の構文解析を高速に行うために文法規則を減らすことができる文法規則フィルターモデルを学習することができる。
【０１０４】
また、簡単化された構文木ｙ￣から抽出された文法規則ｒ￣の集合Ｒ￣と、学習された重みベクトルｗ￣と、入力文ｘとに基づいて、基準スコアを計算し、文法規則ｒ￣の各々について、入力文ｘの構文解析結果を表す、当該文法規則ｒ￣を含む構文木ｙ￣に基づいて計算されるスコアと、基準スコアとに応じて、文法規則ｒ￣を、変換前の文法規則ｒに変換して、文法規則ｒの集合Ｒ´に追加することにより、文の構文解析を高速に行うために文法規則を減らすことができ、入力文の構文解析を高速に行うことができる。
【０１０５】
また、規則フィルターにより構文解析に使われる、詳細な句ラベルを持つ文法規則を減らすことができるため、従来の統計的構文解析装置よりも高速に解析を行うことができる。構文解析速度が向上することによって、機械翻訳や文書要約などの応用システムを高速化することが可能になる。
【０１０６】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１０７】
例えば、上記の実施の形態では、文法規則フィルターモデル学習装置と構文解析装置とを、１つの構文解析装置で実現する場合を例に説明したが、これに限定されるものではなく、文法規則フィルターモデル学習装置と構文解析装置とを別々に設けてもよい。この場合には、文法規則フィルターモデル学習装置が、学習部２２及び規則フィルターモデル学習部２６を備えればよい。また、構文解析装置が、規則フィルター部３０及び解析部３２を備えればよい。
【０１０８】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【０１０９】
１０   入力部
２０   演算部
２２   学習部
２４   文法規則記憶部
２６   規則フィルターモデル学習部
２８   簡易文法規則記憶部
３０   規則フィルター部
３２   解析部
９０   出力部
１００ 構文解析装置
２２０ 文法規則集合抽出部
２２２ 重みベクトル更新部
２６０ 構文木簡単化部
２６２ 簡単化文法規則集合抽出部
２６４ 重みベクトル更新部
３００ スコア計算部
３０２ 文法規則追加部
【図１】
0006482084.tif 000020
【図２】
0006482084.tif 000021
【図３】
0006482084.tif 000022
【図４】
0006482084.tif 000023
【図５】
0006482084.tif 000024
【図６】
0006482084.tif 000025
【図７】
0006482084.tif 000026
【図８】
0006482084.tif 000027
【図９】
0006482084.tif 000028
【図１０】
0006482084.tif 000029
【図１１】
0006482084.tif 000030