(57)【要約】【課題】より多くの文について漸進的に構文解析可能な有限状態変換器の作成装置、プログラム、記録媒体、作成方法、及び漸進的構文解析装置を提供する。【解決手段】有限状態変換器作成装置１は、再帰遷移ネットワークを作成する再帰遷移ネットワーク作成部２と、有限状態変換器の弧をその入力ラベルに対応した再帰遷移ネットワーク中のネットワークで置き換える操作を再帰的に繰り返す弧置き換え部３と、文法規則の適用頻度に関する統計情報に基づいて弧の置き換え優先度を計算する優先度計算部４とを備え、弧置き換え部３は、弧の置き換え優先度が高い弧から順に置き換え操作を適用するので、限られた大きさで、より多くの文を構文解析可能な有限状態変換器を、確実に作成することができる。【選択図】        図１
2004271764.tif 000002
【特許請求の範囲】
【請求項１】
漸進的構文解析に用いる有限状態変換器を作成する装置であって、
文脈自由文法に基づく文法規則の集合を表すネットワークの集合であると共に、前記各ネットワークにおける非終端記号による遷移が他のネットワークによって定義される再帰的構造を有する再帰遷移ネットワークを作成する再帰遷移ネットワーク作成手段と、
開始記号を入力ラベルとする弧を持つ有限状態変換器を初期の有限状態変換器とし、前記有限状態変換器の弧をその入力ラベルに対応した前記再帰遷移ネットワーク中のネットワークで置き換え、さらに、その置き換えによって新たに作成された弧を、前記再帰遷移ネットワーク中の別のネットワークに置き換える操作を再帰的に繰り返す弧置き換え手段と、
文法規則の適用頻度に関する統計情報に基づいて、前記有限状態変換器における入力ラベルが非終端記号である全ての弧について各々に対応する構文木の節点の導出確率を計算し、得られた導出確率を弧の置き換え優先度とする優先度計算手段と、
を備え、
前記弧置き換え手段は、前記弧の置き換え優先度が高い弧から順に置き換え操作を適用すると共に、前記置き換え操作が繰り返し適用されることによって前記有限状態変換器が所定の大きさに達したときに前記弧の置き換え操作の適用を終了することを特徴とする有限状態変換器作成装置。
【請求項２】
前記弧置き換え手段による前記弧の置き換え操作の適用が終了した後、非終端記号を入力ラベルに持つ弧を除去しつつ、弧の置き換え操作の適用をさらに実行する弧除去手段、を備えたことを特徴とする請求項１に記載の有限状態変換器作成装置。
【請求項３】
前記節点の導出確率は、構文木における開始記号から対象の節点までのパス上の各節点について順に文法規則が適用される確率であることを特徴とする請求項１又は２に記載の有限状態変換器作成装置。
【請求項４】
漸進的構文解析に用いる有限状態変換器を作成するためにコンピュータを、
文脈自由文法に基づく文法規則の集合を表すネットワークの集合であると共に、前記各ネットワークにおける非終端記号による遷移が他のネットワークによって定義される再帰的構造を有する再帰遷移ネットワークを作成する再帰遷移ネットワーク作成手段、
開始記号を入力ラベルとする弧を持つ有限状態変換器を初期の有限状態変換器とし、前記有限状態変換器の弧をその入力ラベルに対応した前記再帰遷移ネットワーク中のネットワークで置き換え、さらに、その置き換えによって新たに作成された弧を、前記再帰遷移ネットワーク中の別のネットワークに置き換える操作を再帰的に繰り返す弧置き換え手段、及び
文法規則の適用頻度に関する統計情報に基づいて、前記有限状態変換器における入力ラベルが非終端記号である全ての弧について各々に対応する構文木の節点の導出確率を計算し、得られた導出確率を弧の置き換え優先度とする優先度計算手段として機能させるための有限状態変換器作成プログラムであって、
前記弧置き換え手段は、前記弧の置き換え優先度が高い弧から順に置き換え操作を適用すると共に、前記置き換え操作が繰り返し適用されることによって前記有限状態変換器が所定の大きさに達したときに前記弧の置き換え操作の適用を終了することを特徴とする有限状態変換器作成プログラム。
【請求項５】
請求項４に記載の有限状態変換器作成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項６】
漸進的構文解析に用いる有限状態変換器を作成する方法であって、
文脈自由文法に基づく文法規則の集合を表すネットワークの集合であると共に、前記各ネットワークにおける非終端記号による遷移が他のネットワークによって定義される再帰的構造を有する再帰遷移ネットワークを作成する再帰遷移ネットワーク作成ステップと、
開始記号を入力ラベルとする弧を持つ有限状態変換器を初期の有限状態変換器とし、前記有限状態変換器の弧をその入力ラベルに対応した前記再帰遷移ネットワーク中のネットワークで置き換え、さらに、その置き換えによって新たに作成された弧を、前記再帰遷移ネットワーク中の別のネットワークに置き換える操作を再帰的に繰り返す弧置き換えステップと、
文法規則の適用頻度に関する統計情報に基づいて、前記有限状態変換器における入力ラベルが非終端記号である全ての弧について各々に対応する構文木の節点の導出確率を計算し、得られた導出確率を弧の置き換え優先度とする優先度計算ステップと、
を備え、
前記弧置き換えステップにおいて、前記弧の置き換え優先度が高い弧から順に置き換え操作を適用すると共に、前記置き換え操作が繰り返し適用されることによって前記有限状態変換器が所定の大きさに達したときに前記弧の置き換え操作の適用を終了することを特徴とする有限状態変換器作成方法。
【請求項７】
前記弧置き換えステップにおける前記弧の置き換え操作の適用が終了した後、非終端記号を入力ラベルに持つ弧を除去しつつ、弧の置き換え操作の適用をさらに実行する弧除去ステップ、を備えたことを特徴とする請求項６に記載の有限状態変換器作成方法。
【請求項８】
前記節点の導出確率は、構文木における開始記号から対象の節点までのパス上の各節点について順に文法規則が適用される確率であることを特徴とする請求項６又は７に記載の有限状態変換器作成方法。
【請求項９】
漸進的に構文解析を行うように構成された構文解析装置であって、
請求項６乃至８のいずれかに記載の方法によって作成された有限状態変換器と、
その有限状態変換器へ単語を入力する度に状態遷移に伴って出力される構文木を順次連接する連接処理手段と、
を備えたことを特徴とする漸進的構文解析装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、実時間音声言語処理システム等における漸進的構文解析に用いる有限状態変換器作成装置、プログラム、記録媒体、作成方法及び漸進的構文解析装置に関する。
【０００２】
【従来の技術】
同時通訳システムなどの実時間音声言語処理システムでは、ユーザの発話に対して同時的にその内容を理解し、応答する必要がある。そのような処理を実現するためには、文全体が入力されるまで待ってから解析処理を行うのではなく、発話の断片が入力されるごとに、順次、解析処理を実行するという文の漸進的な解釈が重要となる。
文の構文的関係を漸進的に理解する枠組みとして、これまでに、漸進的構文解析が研究されている。漸進的構文解析では、発話の途中段階においても、それまでに入力された文の断片に対する構文木を生成する。そのため、文全体が入力されていなくとも、その時点での構文構造を理解することができる。漸進的構文解析手法として、これまでにＭａｔｓｕｂａｒａらは、漸進的チャート解析手法を提案している（非特許文献１参照。）。この手法では、単語が入力されるごとに、入力された単語に対して文脈自由文法の文法規則を適用する操作を繰り返して、単語に対する構文木を生成し、これを文の断片に対する構文木と結合することにより、漸進的な解析処理を実現している。しかしながら、漸進的チャート解析手法では、実時間言語処理システムにおいて要求される実時間性について十分な性能が得られないという問題があった。
そこで、発明者らは、漸進的チャート解析手法における上述した問題点に鑑みて、有限状態変換器を用いた漸進的構文解析手法を提案している（非特許文献２参照）。この解析手法によれば、文脈自由文法を近似変換した有限状態変換器を用いて構文解析を実行するため、高速な構文解析処理を実現可能である。
【０００３】
【非特許文献１】
Ｓ．Ｍａｔｓｕｂａｒａ，  ｅｔ  ａｌ．，  ”Ｃｈａｒｔ−ｂａｓｅｄ  Ｐａｒｓｉｎｇ  ａｎｄ  Ｔｒａｎｓｆｅｒ  ｉｎ  Ｉｎｃｒｅｍｅｎｔａｌ  Ｓｐｏｋｅｎ  Ｌａｎｇｕａｇｅ  Ｔｒａｎｓｌａｔｉｏｎ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＮＬＰＲＳ’９７，  ｐｐ．５２１−５２４（１９９７）
【非特許文献２】
湊  他、”有限状態変換器を用いた漸進的構文解析”、平成１３年度電気関係学会東海支部連合大会論文集、Ｐ．２７９（２００１）
【０００４】
【発明が解決しようとする課題】
しかしながら、上述した従来の文脈自由文法を近似変換した有限状態変換器を用いた漸進的構文解析手法では、近似変換の結果、もとの文脈自由文法では解析できる文が、有限状態変換器では解析できない場合があるという問題があった。すなわち、漸進的構文解析に用いる有限状態変換器は、文法規則を表現するネットワークにより弧を再帰的に置き換えることにより作成されるが、実際上、有限状態変換器を実現するために使用されるコンピュータの記憶領域の大きさに制限があるために文解析に十分な回数の弧の置き換えができない場合があり、このため、もとの文脈自由文法では解析可能であった文が有限状態変換器では解析不能となる場合が生じていたのである。
本発明は、かかる課題に鑑みてなされたものであり、その目的は、より多くの文について漸進的に構文解析可能な有限状態変換器の作成装置、プログラム、記録媒体、作成方法、及び漸進的構文解析装置を提供することである。
【０００５】
【課題を解決するための手段】
この目的を達成するために、請求項１に記載の有限状態変換器作成装置は、漸進的構文解析に用いる有限状態変換器を作成する装置であって、文脈自由文法に基づく文法規則の集合を表すネットワークの集合であると共に、前記各ネットワークにおける非終端記号による遷移が他のネットワークによって定義される再帰的構造を有する再帰遷移ネットワークを作成する再帰遷移ネットワーク作成手段と、開始記号を入力ラベルとする弧を持つ有限状態変換器を初期の有限状態変換器とし、前記有限状態変換器の弧をその入力ラベルに対応した前記再帰遷移ネットワーク中のネットワークで置き換え、さらに、その置き換えによって新たに作成された弧を、前記再帰遷移ネットワーク中の別のネットワークに置き換える操作を再帰的に繰り返す弧置き換え手段と、文法規則の適用頻度に関する統計情報に基づいて、前記有限状態変換器における入力ラベルが非終端記号である全ての弧について各々に対応する構文木の節点の導出確率を計算し、得られた導出確率を弧の置き換え優先度とする優先度計算手段と、を備え、前記弧置き換え手段は、前記弧の置き換え優先度が高い弧から順に置き換え操作を適用すると共に、前記置き換え操作が繰り返し適用されることによって前記有限状態変換器が所定の大きさに達したときに前記弧の置き換え操作の適用を終了することを特徴とする。
従って、請求項１に記載の有限状態変換器作成装置によれば、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用されるので、限られた大きさで、より多くの文を解析可能な有限状態変換器を、確実に作成することができる。
【０００６】
また、請求項２に記載の有限状態変換器作成装置は、前記弧置き換え手段による前記弧の置き換え操作の適用が終了した後、非終端記号を入力ラベルに持つ弧を除去しつつ、弧の置き換え操作の適用をさらに実行する弧除去手段、を備えたことを特徴とする。
従って、請求項２に記載の有限状態変換器作成装置によれば、構文解析時に使用されない非終端記号を入力ラベルに持つ弧を除去しつつ、さらに弧の置き換えを行うので、より一層多くの文を解析可能な有限状態変換器を確実に作成することができる。
【０００７】
また、請求項３に記載の有限状態変換器作成装置は、前記節点の導出確率が、構文木における開始記号から対象の節点までのパス上の各節点について順に文法規則が適用される確率であることを特徴とする。
従って、請求項３に記載の有限状態変換器作成装置によれば、構文木における開始記号から対象の節点までのパス上の各節点について順に文法規則が適用される確率を弧の置き換え優先度として用いて弧の置き換え操作を行うことによって、より多くの文を解析可能な有限状態変換器を確実に作成することができる。
【０００８】
また、請求項４に記載の有限状態変換器作成プログラムは、漸進的構文解析に用いる有限状態変換器を作成するためにコンピュータを、文脈自由文法に基づく文法規則の集合を表すネットワークの集合であると共に、前記各ネットワークにおける非終端記号による遷移が他のネットワークによって定義される再帰的構造を有する再帰遷移ネットワークを作成する再帰遷移ネットワーク作成手段、開始記号を入力ラベルとする弧を持つ有限状態変換器を初期の有限状態変換器とし、前記有限状態変換器の弧をその入力ラベルに対応した前記再帰遷移ネットワーク中のネットワークで置き換え、さらに、その置き換えによって新たに作成された弧を、前記再帰遷移ネットワーク中の別のネットワークに置き換える操作を再帰的に繰り返す弧置き換え手段、及び文法規則の適用頻度に関する統計情報に基づいて、前記有限状態変換器における入力ラベルが非終端記号である全ての弧について各々に対応する構文木の節点の導出確率を計算し、得られた導出確率を弧の置き換え優先度とする優先度計算手段として機能させるための有限状態変換器作成プログラムであって、前記弧置き換え手段は、前記弧の置き換え優先度が高い弧から順に置き換え操作を適用すると共に、前記置き換え操作が繰り返し適用されることによって前記有限状態変換器が所定の大きさに達したときに前記弧の置き換え操作の適用を終了することを特徴とする。
従って、コンピュータによって、請求項４に記載の有限状態変換器作成プログラムを実行することにより、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用されるので、限られた大きさで、より多くの文を解析可能な有限状態変換器を、確実に作成することができる。
【０００９】
また、請求項５に記載のコンピュータ読み取り可能な記録媒体は、請求項４に記載の有限状態変換器作成プログラムを記録している。
従って、コンピュータによって、請求項５に記載のコンピュータ読み取り可能な記録媒体から請求項４に記載の有限状態変換器作成プログラムを読み取って実行することにより、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用されるので、限られた大きさで、より多くの文を解析可能な有限状態変換器を、確実に作成することができる。
【００１０】
また、請求項６に記載の有限状態変換器作成方法は、漸進的構文解析に用いる有限状態変換器を作成する方法であって、文脈自由文法に基づく文法規則の集合を表すネットワークの集合であると共に、前記各ネットワークにおける非終端記号による遷移が他のネットワークによって定義される再帰的構造を有する再帰遷移ネットワークを作成する再帰遷移ネットワーク作成ステップと、開始記号を入力ラベルとする弧を持つ有限状態変換器を初期の有限状態変換器とし、前記有限状態変換器の弧をその入力ラベルに対応した前記再帰遷移ネットワーク中のネットワークで置き換え、さらに、その置き換えによって新たに作成された弧を、前記再帰遷移ネットワーク中の別のネットワークに置き換える操作を再帰的に繰り返す弧置き換えステップと、文法規則の適用頻度に関する統計情報に基づいて、前記有限状態変換器における入力ラベルが非終端記号である全ての弧について各々に対応する構文木の節点の導出確率を計算し、得られた導出確率を弧の置き換え優先度とする優先度計算ステップと、を備え、前記弧置き換えステップにおいて、前記弧の置き換え優先度が高い弧から順に置き換え操作を適用すると共に、前記置き換え操作が繰り返し適用されることによって前記有限状態変換器が所定の大きさに達したときに前記弧の置き換え操作の適用を終了することを特徴とする。
従って、請求項６に記載の有限状態変換器作成方法によれば、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用されるので、限られた大きさで、より多くの文を解析可能な有限状態変換器を、確実に作成することができる。
【００１１】
また、請求項７に記載の有限状態変換器作成方法は、前記弧置き換えステップにおける前記弧の置き換え操作の適用が終了した後、非終端記号を入力ラベルに持つ弧を除去しつつ、弧の置き換え操作の適用をさらに実行する弧除去ステップ、を備えたことを特徴とする。
従って、請求項７に記載の有限状態変換器作成方法によれば、構文解析時に使用されない非終端記号を入力ラベルに持つ弧を除去しつつ、さらに弧の置き換えを行うので、より一層多くの文を解析可能な有限状態変換器を確実に作成することができる。
【００１２】
また、請求項８に記載の有限状態変換器作成方法は、前記節点の導出確率が、構文木における開始記号から対象の節点までのパス上の各節点について順に文法規則が適用される確率であることを特徴とする。
従って、請求項８に記載の有限状態変換器作成装置によれば、構文木における開始記号から対象の節点までのパス上の各節点について順に文法規則が適用される確率を弧の置き換え優先度として用いて弧の置き換え操作を行うことによって、より多くの文を解析可能な有限状態変換器を確実に作成することができる。
【００１３】
また、請求項９に記載の漸進的構文解析装置は、漸進的に構文解析を行うように構成された構文解析装置であって、請求項６乃至８のいずれかに記載の方法によって作成された有限状態変換器と、その有限状態変換器へ単語を入力する度に状態遷移に伴って出力される構文木を順次連接する連接処理手段と、を備えたことを特徴とする。
従って、請求項９に記載の漸進的構文解析装置によれば、請求項６乃至８のいずれかに記載の方法によって作成された有限状態変換器、すなわち、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用された有限状態変換器を備え、連接処理手段が、その有限状態変換器へ単語を入力する度に状態遷移に伴って出力される構文木を順次連接するように構成されているので、文脈自由文法を近似変換した限られた大きさの有限状態変換器を用いて、より多くの文について漸進的に構文解析を行うことができる。
【００１４】
【発明の実施の形態】
以下、本発明を具体化した有限状態変換器作成装置、プログラム、記録媒体、作成方法、及び漸進的構文解析装置の一実施形態について図面を参照しつつ説明する。
まず、本実施形態の有限状態変換器作成装置１の全体構成について、図１を参照しつつ説明する。
有限状態変換器作成装置１は、図１に示すように、再帰遷移ネットワーク作成部２と、弧置き換え部３と、優先度計算部４と、弧除去部５とから構成され、文法規則の適用頻度に関する統計情報を記憶する統計情報記憶装置１１が接続されている。但し、後述する弧の除去処理を行わない場合は、弧除去部５を省略して構成することも可能である。
【００１５】
有限状態変換器作成装置１は、具体的には、ＣＰＵ，ＲＯＭ，ＲＡＭ，ハードディスク装置，ＣＤ−ＲＯＭ装置等を備えたコンピュータによって実現され、例えば、コンピュータを再帰遷移ネットワーク作成部２、弧置き換え部３、優先度計算部４、及び弧除去部５として機能させるための有限状態変換器作成プログラムをハードディスク装置に記憶させ、ＣＰＵがハードディスク装置から有限状態変換器作成プログラムを読み出して実行するように構成される。また、ＣＤ−ＲＯＭ等に記録された文法規則の適用頻度に関する統計情報が予めＣＤ−ＲＯＭ装置等を介して予めコンピュータに読み込まれてハードディスク装置に記憶されている場合は、ハードディスク装置が統計情報記憶装置１１として機能する。尚、文法規則の適用頻度に関する統計情報としては、例えば、構文木付きＡＴＲ音声言語データベース（日本語対話）を用いることができる。
尚、再帰遷移ネットワーク作成部２が本発明の再帰遷移ネットワーク作成手段を、弧置き換え部３が弧置き換え手段を、優先度計算部４が優先度計算手段を、弧除去部５が弧除去手段をそれぞれ構成するものである。また、再帰遷移ネットワーク作成部２における処理内容が本発明の再帰遷移ネットワーク作成ステップに、弧置き換え部３における処理内容が弧置き換えステップに、優先度計算部４における処理内容が優先度計算ステップに、弧除去部５における処理内容が弧除去ステップにそれぞれ相当するものである。
【００１６】
次に、有限状態変換器作成装置１を構成する上述した各部の処理内容について図面を参照しつつ説明する。
まず、有限状態変換器作成装置１各部の処理内容の説明に先立って、有限オートマトン、有限状態変換器、文脈自由文法をそれぞれ定義する。
はじめに、有限オートマトンを定義する。有限オートマトンは、５項組（Σ，Ｑ，ｑ０，Ｆ，Ｅ）で定義される。Σはアルファベットの有限集合，Ｑは状態の有限集合，ｑ０∈Ｑは初期状態，Ｆ⊆Ｑは最終状態の集合，Ｅ  は弧の有限集合である。また、Ｅ⊆Ｑ×Σ×Ｑである。
有限オートマトンは、１つの初期状態と１つ以上の最終状態を持ち、弧のラベルに従って、状態を遷移するネットワークである。また、弧（ｐ，Ａ，ｑ  ）∈Ｅ（ｐ，ｑ∈Ｑ，Ａ∈Σ）に対して、状態ｐを弧の始点、状態ｑを弧の終点と呼ぶ。
【００１７】
次に、有限状態変換器を定義する。有限状態変換器は、６項組（ΣＩ，ΣＯ，Ｑ，ｑ０，Ｆ，Ｅ）で定義される。ΣＩ，ΣＯは、それぞれ入力アルファベット，出力アルファベットの有限集合，Ｑは状態の有限集合，ｑ０∈Ｑは初期状態，Ｆ⊆Ｑは最終状態の有限集合，Ｅは弧の有限集合である。ただし、Ｅ⊆Ｑ×ΣＩ×ΣＯ×Ｑである。
有限オートマトンでは弧に入力ラベルを割り当てたが、さらに出力ラベルを割り当てたものが有限状態変換器である。有限状態変換器では、ΣＩの要素が入力されたときに、ΣＯの要素を出力して遷移する。有限状態変換器を用いることによって、システムに入力された記号列の受理だけでなく、入力に対応する記号列の出力が可能となる。
【００１８】
最後に文脈自由文法Ｇを定義する。Ｇは、４項組（Ｎ，Ｔ，Ｐ，Ｓ０）で定義される。Ｎ，Ｔはそれぞれ非終端記号、終端記号の有限集合である。Ｓ０∈Ｎは開始記号であり、この文法から生成される構文木の根節点となる。さらに、Ｐ  は文法規則の集合である。各規則は、Ａ→α（Ａ∈Ｎ，α＝（Ｎ∪Ｔ）＋）の形式で書かれ、Ａがαに書き換えられることを示す。自然言語の構造の多くは、文脈自由文法で記述可能である。
【００１９】
次に、有限状態変換器作成装置１を構成する各部の処理について説明する。本実施形態では、文脈自由文法を再帰遷移ネットワークで表現し、得られた再帰遷移ネットワークの中の弧を、別のネットワークで置き換えていくことにより、有限状態変換器を獲得する。以下では、まず、再帰遷移ネットワーク作成部２によって実行される再帰遷移ネットワークの作成処理について述べ、次に、弧置き換え部３、優先度計算部４、及び弧除去部５における再帰遷移ネットワークによる置き換え操作を利用した有限状態変換器の作成処理について述べる。
【００２０】
（再帰遷移ネットワーク作成部２における再帰遷移ネットワーク作成処理）
再帰遷移ネットワークは、非終端記号による遷移を許したネットワークの集合である。再帰遷移ネットワークにおいて非終端記号による遷移は、他のネットワークによって定義されるという再帰的な構造を持っている。再帰遷移ネットワークと文脈自由文法の解析能力は等価である。以下では、文脈自由文法から、それと等価な再帰遷移ネットワークを作成する方法を述べる。
まず、範疇Ｘに対して、左辺が範疇Ｘである文法規則の集合ＰＸを表現するネットワークＭＸは、以下のように定義される。ネットワークＭＸは、５項組（Σ，ＱＸ，ｉＸ，ＦＸ，ＥＸ）である。ただし、Σ＝Ｔ∪Ｎ，ｉＸは初期状態、ＦＸは最終状態の集合である。このとき、ＦＸ＝｛ｆＸ｝とする。また、ＱＸは、状態の有限集合、ＥＸは弧の有限集合である。
ＱＸの要素を表現するために、ドット記号（・）付き文法規則を導入する。ドット記号付き文法規則は、Ｘ→α・βのように、ドット記号を文法規則の右辺の任意の位置に挿入したものである。さらに、表記の簡単化のために、ドット記号付き規則を、その左辺、右辺のドット記号の左側、ドット記号の右側の３項組で表現する。例えば、Ｘ→α・βは、（Ｘ，α，β）と表現する。この表現を用いると、ＱＸは次の数式１で表される集合である。
【数１】
2004271764.tif 000003
また、ＥＸは、次の数式２で表される集合である。
【数２】
2004271764.tif 000004
ただし、Ｘ∈Ｎ，Ａ∈Ｎ∪Ｔ，α，β∈（Ｎ∪Ｔ）＋である。
例えば、ＰＸが図２に挙げた規則の集合であるとき、ＭＸは図３に示すネットワークである。ＭＸの初期状態ｉＸから最終状態ｆＸへのパスは、ＰＸの中の１つの文法規則に対応する。従って、文法規則の右辺の記号列をＭＸに入力すれば、文法規則に対応するＭＸのパス上を通り、ｉＸからｆＸへと遷移できる。本実施形態の手法では、再帰遷移ネットワークＭを、ＭＸの集合として数式３により定義する。
【数３】
2004271764.tif 000005
【００２１】
（再帰遷移ネットワーク作成部２における再帰遷移ネットワークの簡単化処理）
上述した処理によって作られる再帰遷移ネットワークには、始点が等しく、かつ、同じラベルを持つ弧が複数存在するため、冗長性を持ち、決定的に遷移できない。そのため、有限オートマトンの最小化手法に基づき、状態を統合する。すなわち、再帰遷移ネットワークの各ＭＸ（Ｘ∈Ｎ）について、等価に変換可能であれば、状態を統合する。ただし、ＦＸの要素数を２個以上にする状態の統合は認めない。ＭＸを置き換え操作に用いる際に、置き換え操作が容易に行えるようにするためである。
ＭＸの簡単化は、表１に示す手順に従って、状態を統合することにより実現する。まず、ＭＸに変化がなくなるまで手順１の操作を繰り返して状態を統合し、次に手順２の操作をＭＸに変化がなくなるまで繰り返す。以下の手続き中の記号は、それぞれｑ，ｑ’，ｑ”∈ＱＸ，Ａ∈ΣＩである。
【表１】
2004271764.tif 000006
図４に、上述した統合操作の一例を示す。手順１では、同じ状態からＡで遷移する状態を統合する。手順２では、Ｄで遷移する先の状態が等しく、他の記号による遷移先を持たない２つの状態を統合する。簡単化された再帰遷移ネットワークでは、ある状態から同じラベルで遷移できる状態は、最大でも、最終状態とそれ以外の状態、それぞれ１つずつである。
【００２２】
（弧置き換え部３における再帰遷移ネットワークを用いた有限状態変換器の作成処理）
次に、上述した再帰遷移ネットワーク作成処理によって作成された再帰遷移ネットワークを用いた有限状態変換器の作成処理について述べる。まずはじめに、初期有限状態変換器Ｍ０を数式４により定義する。
【数４】
2004271764.tif 000007
各記号は、それぞれＱ０＝｛ｉ，ｆ｝，ΣＩ＝Ｎ∪Ｔ，ΣＯ⊂（（［Ｎ）＊（ΣＩ）＊（Ｎ］）＊），Ｆ＝｛ｆ｝，Ｅ０＝｛（ｉ，Ｓ０，Ｓ０，ｆ）｝である。
初期有限状態変換器Ｍ０を表した図が、図５である。Ｍ０の弧をネットワークＭＳ０で置き換え、さらに、新たに作られた弧に対する置き換え操作を再帰的に繰り返すことによって、有限状態変換器を獲得する。置き換え操作は、入力ラベルが非終端記号である弧に対して行い、Ｘを入力ラベルとして持つ弧は、ＭＸで置き換えられる。
【００２３】
次に、置き換え操作の前後における、有限状態変換器の変化について述べる。有限状態変換器Ｍ０に対して、何回かの置き換え操作を実行して得られた有限状態変換器をＭｊとする。Ｍｊを（Ｑｊ，ΣＩ，ΣＯ，ｉ，Ｆ，Ｅｊ）とする。弧ｅ＝（ｑＳ，Ｘ，ＯｌＸＯｒ，ｑｅ）∈ＥｊをＭＸで置き換えて得られる有限状態変換器をＭｊとする。ただし、Ｏｌ、Ｏｒは、それぞれ出力アルファベット中の、左括弧付範疇の系列（［Ｎ）＊及び右括弧付範疇の系列（Ｎ］）＊を表す。Ｍ’ｊは、Ｑｊと弧Ｅｊとに、新たに状態と弧とが追加されて作成される。従って、状態の集合と弧の集合とが変化するため、Ｍ’ｊを（Ｑ’ｊ，ΣＩ，ΣＯ，ｉ，Ｆ，Ｅ’ｊ）とする。このとき、Ｑ’ｊ，Ｅ’ｊは数式５、数式６のように作ることができる。ただし、ｑ１≠ｉＸ，ｑ２≠ｆＸである。
【数５】
2004271764.tif 000008
【数６】
2004271764.tif 000009
【００２４】
置き換え操作の例を図６に示す。尚、図６において、Ｓ０（開始記号）、Ｓ（文）、Ｐ（後置詞）、ＰＰ（後置詞句）、ＮＰ（名詞句）、Ｖ（動詞）、ＶＰ（動詞句）、＄（終止符）である。図６の左の図は、ＰＰを入力ラベルに持つ弧を、左辺がＰＰである文法規則を表現するネットワークＭＰＰで置き換える操作を示しており、右の図は、対応する構文木を表している。
置き換え操作は一般に無限に続けることができる。しかし、有限状態変換器作成装置が実現されるコンピュータのメモリ領域は有限であり、作成できる有限状態変換器の大きさには限りがある。そこで、本実施形態では、有限状態変換器の大きさを表している弧の数に関して閾値を設定し、弧の数が閾値λに達したとき（すなわち、弧の置き換え操作の繰り返しによって有限状態変換器が所定の大きさに達したとき）に弧の置き換え操作を終了することによって、有限状態変換器の作成を近似的に実現する。
【００２５】
（優先度計算部４における統計情報を利用した弧の置き換え順序決定処理）
上述した弧置き換え部３によって実行される弧の置き換え処理によって、漸進的構文解析に用いる有限状態変換器を作成できる。しかし、単純に置き換え操作を繰り返すだけでは、本当に必要な弧を置き換える前に、置き換え操作が打ち切られてしまう可能性がある。従って、置き換え操作を実行するときには、置き換える弧の選択が重要となる。優先度計算部４では、統計情報記憶装置１１に記憶された文法規則の適用頻度に関する統計情報を用い、有限状態変換器の弧と構文木の節点との対応関係を利用して、節点の導出確率が高い節点に対応する弧ほど置き換えの必要性が高いと判断し、弧の置き換え順序を決定する。
まず、有限状態変換器の弧と構文木の節点の対応関係について説明する。有限状態変換器の弧は、Ｓ０を入力ラベルとする弧からネットワークによる置き換え操作を再帰的に実行していくことにより作成される。ネットワークは文法規則の集合を表現しているため、文法規則を適用していると考えることもできる。一方、文脈自由文法において、トップダウンに構文木を生成する場合にも、はじめにＳ０に対して文法規則を適用し、作られた節点に対して文法規則を再帰的に適用することによって、節点は生成される。すなわち、弧と節点は、共に開始記号から文法規則を再帰的に適用して作られるものである。これらの適用操作は対応づけることができ、その操作によって作られた弧と節点も対応づけて考えることができる。図６に、弧と節点の対応の例を番号を用いて示す。例えば、図中の１で示される弧と節点とは、開始記号Ｓ０に対して、ともにＳ０→Ｓ＄，Ｓ→．．．ＶＰ，ＶＰ→ＰＰＶの順に規則が適用されて作られるため、対応する。
【００２６】
有限状態変換器を用いた構文解析において、ある節点を含む構文木を生成するためには、その節点に対応する弧が置き換えられなければならない。しかし、作成できる弧の数は有限であるため、最終的に、全ての弧が置き換えられるわけではない。つまり、全ての構文木が生成できるわけではなく、その中で、できるだけ多くの構文木を生成できる有限状態変換器を作成するためには、弧の置き換え順序を考慮する必要がある。弧の置き換え順序を決定するための指標を、置き換え優先度と呼ぶことにする。導出確率の高い節点を含む構文木ほど頻繁に生成されるため、その節点に対応する弧は、優先して置き換える必要があると考えられる。そこで、置き換え優先度の値を、対応する節点の導出確率とする。有限状態変換器の作成では、統計情報記憶装置１１に記憶された文法規則の適用頻度に関する統計情報を用いて、入力ラベルが非終端記号である全ての弧に対して置き換え優先度を計算し、その値が高い弧から順に弧置き換え部３による置き換え操作を適用する。
【００２７】
次に、節点の導出確率の計算方法について述べる。構文木の節点は、Ｓ０からその節点までのパス上の節点に、文法規則が順次適用されて作られる。そこで、節点の導出確率を、Ｓ０から導出確率を求めたい節点までのパス上の各節点に、順に文法規則が適用される確率とする。図７では、節点ＸｒＭ（ｌＭ）は、構文木の根節点Ｓ０に対して文法規則ｒ１が適用され、ｒ１が生成した節点の中で左からｌ１番目の節点Ｘｒ１（ｌ１）に文法規則ｒ２が適用され、最後に、文法規則ｒＭ−１が生成した節点の左からｌＭ−１番目の節点に文法規則ｒＭが適用されて作られる。この節点の導出確率Ｐ（ＸｒＭ（ｌＭ））を、数式７で計算する。
【数７】
2004271764.tif 000010
ｒｉ（ｌｉ）は、文法規則ｒｉが適用され、かつ、次に適用される文法規則ｒｉ＋１が、ｒｉの右辺ｌｉ番目の要素が生成する節点に適用されることを示す。このとき、文法規則が適用される位置を考えるのは、同じ範疇であっても、位置によって適用されやすい規則は異なるためである。例えば、文法規則Ｎ→ＮＮに対して、右辺の１番目のＮと２番目のＮとでは、適用されやすい文法規則は異なる。
【００２８】
ここで、数式７中のＰ（ｒｉ（ｌｉ）｜ｒ１（ｌ１），．．．，ｒｉ−１（ｌｉ−１））の値は、次の文法規則の適用位置にかかわらないため、数式７は、数式８とすることができる。
【数８】
2004271764.tif 000011
このようにして、節点の導出確率は求められる。しかし、数式８のように、節点の導出において適用された全ての文法規則を条件として文法規則の適用確率を求めると、スパースネス問題が発生し、作成する有限状態変換器が学習データに依存したものとなる。そこで、優先度計算部４では、ある節点に対して文法規則が適用される確率は、その節点から順にさかのぼって最初に到達するＮ−１個の節点を生成した文法規則とその適用位置だけに依存するものとする。また、得られた適用確率に対して、低次の条件付き適用確率と線形補間を行うことによって、スムージングを行う。
【００２９】
まず、数式９に示される近似した文法規則の適用確率Ｐの計算方法について述べる。
【数９】
2004271764.tif 000012
ある節点に対して文法規則を適用するとき、その節点からＳ０までのパス上を順にさかのぼっていき、適用された文法規則と、その右辺の中で次の規則が適用された位置をペアとするＮ−１項組を獲得する。これに、今、適用する文法規則を合わせることによって、（ｒ１（ｌ１），．．．ｒＮ−１（ｌＮ−１），ｒＮ）のＮ項組で表すことができる。例えば、図８では、６つの文法規則が適用されて構文木が作られている。この構文木からは６つの組が得ることができ、例えばＮ＝３のときには、図８に示される６つの３項組を獲得できる。ただし、構文木の開始記号より上の位置では、ヌル規則‘＃’が適用されていると仮定している。
【００３０】
学習データから獲得したＮ項組の集合を用いて、ｒ１（ｌ１），．．．ｒＮ−１（ｌＮ−１）を条件とした文法規則ｒＮの適用確率を、数式１０で計算する。ただし、Ｃ（Ｘ）は、Ｘの出現回数を示す。
【数１０】
2004271764.tif 000013
さらに、文法規則の適用確率には、数式１１によって線形補間した値を用いる。ただし、λ１，．．．，λＮは補間係数である。
【数１１】
2004271764.tif 000014
ただし、ＬＨＳ（ｒＮ）はｒＮの左辺範疇を表す。Ｐ１（ｒＮ｜ＬＨＳ（ｒＮ））以外の条件にＬＨＳ（ｒＮ）を含めないのは、文法規則ｒＮ−１の位置ｌＮ−１にある範疇は、ＬＨＳ（ｒＮ）であるとわかるためである。
最終的に、本手法では数式１２を用いて節点の導出確率を求める。
【数１２】
2004271764.tif 000015
ただし、再帰遷移ネットワークの状態を統合した影響により、複数の文法規則から作られている弧が再帰遷移ネットワークには存在する。そのため、１つの弧に対して構文木の複数の節点が対応することがあるが、その場合には、対応する全ての節点の導出確率の和が節点の導出確率であるとする。
【００３１】
（弧除去部１４における非終端記号をラベルに持つ弧の除去処理）
先に述べた弧置き換え部３によって実行される有限状態変換器作成処理では、弧の数が閾値λに達したら、すぐに置き換え操作を打ち切るため、ネットワークで置き換えられなかった非終端記号を入力ラベルに持つ弧はそのまま有限状態変換器中に残される。しかし、本実施形態の解析手法では、弧の入力ラベルとシステムに入力される単語の品詞が一致する場合にのみ遷移するため、非終端記号を入力ラベルに持つ弧は解析時には使用されない。従って、これらの弧をそのまま残しておくことは無駄であり、弧を除去しても問題とならない。それどころか、これらの弧を除去しつつ、さらに弧を置き換えることができれば、有限状態変換器の解析能力の向上が期待できる。以下、非終端記号をラベルに持つ弧を除去しつつ、さらに置き換え操作を継続する処理について述べる。
まず、弧置き換え部３による処理により有限状態変換器を作成する。弧の数が、閾値λに達して置き換え操作の適用が停止したのち、以下のアルゴリズムを実行する。
【００３２】
（非終端記号を入力ラベルとする弧の除去手続き）
１．非終端記号のラベルの中で最も置き換え優先度の高い弧ｅを、次に置き換える弧として選択する。ここで、弧ｅの入力ラベルをＩ（ｅ）とする。
２．ｅの置き換えの有効性をチェックする。有効でないときにはｅを除去し、１．へ戻る。
３．有限状態変換器の中で、非終端記号を入力ラベルに持つ弧を、置き換え優先度の低い順に除去する。除去する弧の数は、λ−（（有限状態変換器の弧の数）−（ＭＩ（ｅ）が持つ弧の数）−１）個である。ただし、この値が負である場合には除去しない。
４．弧ｅをネットワークＭＩ（ｅ）で置き換える。
５．有限状態変換器に非終端記号を入力ラベルとする弧が残っていれば、再び１．から処理を繰り返す。
上記のアルゴリズムの２．の有効性のチェックでは、弧ｅについて、弧ｅの始点の状態を遷移先とする弧が存在するか、もしくはその状態が初期状態であるかをチェックし、さらに、弧ｅの終点の状態を遷移元とする弧が存在するか、もしくはその状態が最終状態であるかをチェックする。どちらか一方でも当てはまらなければ、弧ｅは解析に使われないため除去される。
この操作によって、残された弧の中で、置き換え優先度の高い弧はさらに置き換えられ、置き換え優先度の低い弧は除去される。しかし、弧を除去することによって、初期状態から到達できない弧や、最終状態まで到達できない弧が新たに現れる。これらの弧も解析に用いることはできない。従って、弧を除去するときには、その影響について調査し、使用できない弧がさらに出現するときにはその弧もまとめて除去する。従って、弧を除去するときには以下の操作を行う。
【００３３】
（不要な弧の除去方法）
弧を除去する場合に、その弧の始点、終点の状態を共有している弧について、以下の点をチェックする。もしどれか１つに該当すれば、その指示に従って弧を除去し、さらに除去した弧について再帰的に同じ操作を実行する。
（１）除去した弧の始点を遷移先とする弧が存在しない場合、その状態を始点とする全ての弧を除去する。
（２）除去した弧の始点を遷移元とする弧が他に存在しない場合、その状態を終点とする全ての弧を除去する。
（３）除去した弧の終点を遷移先とする弧が他に存在しない場合、その状態を始点とする全ての弧を除去する。
（４）除去した弧の終点を遷移元とする弧が存在しない場合、その状態を終点とする全ての弧を除去する。
（１）から（４）までの操作を図にまとめると、図９のようになる。図９の点線で示された弧は、それぞれのパターンにおいて存在しない弧を示す。いずれの図でも、中央の×印の弧が除去されたときに、点線の弧がないために、さらに除去される弧が×印で示されている。
以上詳述した有限状態変換器作成装置１における再帰遷移ネットワーク作成部２、弧置き換え部３、優先度計算部４、及び弧除去部５における各処理ステップが実行された結果として、漸進的構文解析に用いる有限状態変換器が獲得される。
【００３４】
（漸進的構文解析装置２１による漸進的な構文木生成）
次に、上述した有限状態変換器作成装置１によって作成された有限状態変換器２２を用いた漸進的構文解析装置２１について、図面を参照しつつ説明する。
漸進的構文解析装置２１は、図１０に示すように、入力装置３１と、有限状態変換器２２と、連接処理部２３と、出力装置３２とから構成されている。漸進的構文解析装置２１は、具体的には、ＣＰＵ，ＲＯＭ，ＲＡＭ，ハードディスク装置、音声入力装置、ディスプレイ装置等を備えたコンピュータによって実現される。また、連接処理部２３が、本発明の連接処理手段を構成するものである。
【００３５】
入力装置３１は、構文解析の対象となる文を入力するための装置であり、具体的には、音声入力装置、キーボード等の入力装置によって構成される。入力装置３１は、外部から入力された文（単語列）を、順次、有限状態変換器２２に入力する。
有限状態変換器２２は、文法規則の適用の過程を予め計算した結果を有限状態変換器として表現したものであって、上述した有限状態変換器作成装置１によって作成されたものである。有限状態変換器２２は、入力装置３１によって入力される単語列に対して状態遷移すると共に文法規則適用により生成される構文木を順に出力する。有限状態変換器２２は、具体的には、ＲＯＭ又はハードディスク装置に記憶された有限状態変換器プログラムをＣＰＵが読み出して実行することにより実現される。
連接処理部２３は、有限状態変換器２２によって出力された構文木を順次連接する。従って、文の途中段階でも、それまでの入力に対する構文木を生成することができる。連接処理部２３は、具体的には、ＲＯＭ又はハードディスク装置に記憶された連接処理プログラムをＣＰＵが読み出して実行することにより実現される。
出力装置３２は、有限状態変換器２２及び連接処理部２３によって生成された構文解析結果としての構文木を出力する。出力部３２は、具体的には、構文解析結果をディスプレイ装置による表示として、ＲＡＭ又はハードディスク上へのファイル等として出力する。
【００３６】
次に、漸進的構文解析装置２１において漸進的に構文木を生成する処理の詳細内容について説明する。本実施形態の漸進的構文解析装置２１では、基本的には、入力装置３１から有限状態変換器２２へ単語をつぎつぎと入力することによって、状態を遷移して、構文木の出力を得ることができる。しかし、上述した有限状態変換器作成装置１によって作られる有限状態変換器２２は非決定性であるため、ある入力に対して、複数の遷移先が存在する可能性がある。漸進的構文解析では、入力に合わせて構文構造を出力するべきであると考え、本実施形態では幅優先探索を行い、構文木を出力する。すなわち、現在の状態と、これまでに出力された構文木とを表現する記号列のペアを要素とするリストを持ち、１単語ずつが入力されるたびに、現在の状態から遷移できる全ての状態に状態遷移する。そのとき、連接処理部２３が、それ以前に入力された単語列に対する出力構文木を示す記号列に、遷移した弧に記述された出力ラベルを連接して、新しい構文木を生成する。
【００３７】
漸進的構文解析装置２１における動作例を図１１に示す。尚、図１１において示される各出力記号が表す意味内容を以下に括弧書きにて示す。すなわち、Ｓ０（開始記号）、Ｓ（文）、ＮＰ（名詞句）、Ｎ−ＨＵＴＵ（普通名詞句）、ＨＵＴＵ−ＭＥＩＳＩ  （普通名詞）、ＶＡＵＸ（動詞句）、ＶＥＲＢ  （動詞）、ＡＵＸ（助詞）、ＡＵＸ−ＤＥ  （助詞「で」）、ＡＵＸＳＴＥＭ  （助詞語幹）、ＡＵＸＳＴＥＭ−ＭＡＳＵ（助詞語幹「（ござい）ます」）、ＩＮＦＬ（活用語尾）、ＩＮＦＬ−ＳＰＥ−ＳＵ  （活用語尾「す」）、＄（句点）である。
入力装置３１より有限状態変換器２２に１単語入力されるごとに有限状態変換器２２が状態遷移し、遷移した弧の出力ラベルが連接処理部２３によって連接される。ここで、出力記号列（連接された複数の出力ラベル）は１つの構文木を表している。例えば、品詞‘ＨＵＴＵ−ＭＥＩＳＩ  ’（普通名詞）が入力されたときの出力記号列は、図１２の左側に示された構文木を表しており、‘ＡＵＸ−ＤＥ  ’（助詞「で」）まで入力されたときの出力記号列は、図１２の右側に示された構文木を表している。このように、単語が入力されるごとに、次々に構文木を拡張していく。この例では、遷移に曖昧性を含んでいないため、各品詞の入力に対して構文木は一つしか出力されていないが、前に述べたように、複数の状態に遷移可能であれば、その数だけ、状態と記号列のペアは保持され、構文木が作られる。
【００３８】
以上詳述したことから明らかなように、本実施形態によれば、有限状態変換器作成装置１は、文脈自由文法に基づく文法規則の集合を表すネットワークの集合であると共に、前記各ネットワークにおける非終端記号による遷移が他のネットワークによって定義される再帰的構造を有する再帰遷移ネットワークを作成する再帰遷移ネットワーク作成部２と、開始記号を入力ラベルとする弧を持つ有限状態変換器を初期の有限状態変換器とし、前記有限状態変換器の弧をその入力ラベルに対応した前記再帰遷移ネットワーク中のネットワークで置き換え、さらに、その置き換えによって新たに作成された弧を、前記再帰遷移ネットワーク中の別のネットワークに置き換える操作を再帰的に繰り返す弧置き換え部３と、文法規則の適用頻度に関する統計情報に基づいて、前記有限状態変換器における入力ラベルが非終端記号である全ての弧について各々に対応する構文木の節点の導出確率を計算し、得られた導出確率を弧の置き換え優先度とする優先度計算部４と、を備え、前記弧置き換え部３は、前記優先度計算部４で求められた前記弧の置き換え優先度が高い弧から順に置き換え操作を適用すると共に、前記置き換え操作が繰り返し適用されることによって前記有限状態変換器が所定の大きさに達したときに前記弧の置き換え操作の適用を終了することを特徴とする。
【００３９】
従って、有限状態変換器作成装置１によれば、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用されるので、限られた大きさで、より多くの文を解析可能な有限状態変換器を、確実に作成することができる。
また、本実施形態によれば、有限状態変換器作成装置１は、前記有限状態変換器が所定の大きさに達したことにより前記弧置き換え部３による前記弧の置き換え操作の適用が終了した後、非終端記号を入力ラベルに持つ弧を除去しつつ、弧の置き換え操作の適用をさらに実行する弧除去手段５、を備えており、構文解析時に使用されない非終端記号を入力ラベルに持つ弧を除去しつつ、さらに弧の置き換えを行うので、より一層多くの文を解析可能な有限状態変換器を確実に作成することができる。
また、本実施形態によれば、有限状態変換器作成装置１は、構文木における開始記号から対象の節点までのパス上の各節点について順に文法規則が適用される確率を弧の置き換え優先度として用いて弧の置き換え操作を行うことによって、より多くの文を解析可能な有限状態変換器を確実に作成することができる。
【００４０】
また、本実施形態によれば、漸進的構文解析装置２１は、有限状態変換器作成装置１によって作成された有限状態変換器２２と、その有限状態変換器２２へ単語を入力する度に状態遷移に伴って出力される構文木を順次連接する連接処理部２３と、を備えたことを特徴とする。
従って、漸進的構文解析装置２１によれば、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用された有限状態変換器２２を備え、連接処理部２３が、その有限状態変換器２２へ単語を入力する度に状態遷移に伴って出力される構文木を順次連接するように構成されているので、文脈自由文法を近似変換した限られた大きさの有限状態変換器２２を用いて、より多くの文について漸進的に構文解析を行うことができる。
【００４１】
尚、本発明は上述した各実施の形態に限定されるものではなく、本発明の主旨を逸脱しない範囲で種々の変更を施すことが可能である。
例えば、前記実施形態では、漸進的構文解析装置２１を単体で用いる例を示したが、漸進的構文解析装置２１を同時通訳システム又は音声認識システムの一部として組み込むことにより、実時間性に優れ且つ正解率の高い同時通訳システム又は音声認識システムを実現することができる。また、漸進的構文解析装置２１を組み込んだ音声認識システムをロボットに搭載することにより、極めて応答性に優れた音声入力ロボットや対話型ロボットを実現することができる。さらに、金融機関におけるＡＴＭ（銀行自動預払機）、カーナビゲーションシステム、切符販売機等に搭載することも可能である。
【００４２】
また、再帰遷移ネットワーク作成部２において任意の言語（日本語、英語、ドイツ語等の各国言語）の文脈自由文法を選択して用いることにより、所望の言語に対応した有限状態変換器２２を作成することができ、さらに、その有限状態変換器２２を用いて所望の言語に対応した漸進的構文解析装置２１を構成することができる。
【００４３】
【実施例】
（実験方法）
上述した本実施形態の有限状態変換器作成装置１によって有限状態変換器を実際に作成し、この有限状態変換器を用いて漸進的構文解析装置２１を作成した。そして、漸進的構文解析装置２１における漸進的構文解析の効果を検討するために、解析実験を行った。実験に用いた計算機のスペックは、ＣＰＵ  Ｐｅｎｔｉｕｍ（登録商標）４  ２ＧＨｚ，メモリ  ２ＧＢである。実験における学習データセット及びテストデータセットには、構文木付きＡＴＲ音声言語データベース（日本語対話）を用いた。学習データ（文法規則の適用頻度に関する統計情報）として、言語データベースからランダムに９，０８１文を抽出し、そこから、文法規則とそれらの適用確率を獲得した。このとき、文法規則は６９８種類、品詞は３３７種類、範疇は１５３種類であった。一方、テストデータとして１，８７４文を用いた。テストデータ中の文の平均単語長は９．４単語であった。また、有限状態変換器の弧の数の閾値を１５，０００，０００に設定した。この値に設定したのは、有限状態変換器の作成時において、メモリをほぼ限界まで使用したためである。このとき、解析時に使用するメモリの量は６００ＭＢ程度であった。
【００４４】
（実験結果）
まず、本実施形態の有限状態変換器１を用いた漸進的構文解析装置２１（実施例１とする）と、従来技術における漸進的チャート解析を用いた構文解析装置（比較例１とする）とをそれぞれ用いて構文解析を行い、解析速度と精度とについて比較した。実施例１の有限状態変換器は、Ｎ＝３としたときの文法規則の適用確率を使用して置き換え優先度を計算し、置き換える順序を決定した。ただし、Ｎは確率の計算に用いた文法規則の組がＮ項組であることを示す。さらに、非終端記号をラベルとする弧を除去した。比較例１の漸進的チャート解析については、有限状態変換器作成に用いた文法規則の適用確率と同じ考えに基づき、ボトムアップ解析用に条件付き確率を求めて利用した。このとき、文法規則を適用するごとに、適用確率の積を計算し、その値が１Ｅ−１２を越えた場合には、それ以上の規則の適用を取りやめた。さらに、置き換える未決定項への到達可能性を用いて、文法規則の適用を制御した。さらに、実施例１の構文解析装置及び比較例１の構文解析装置とも、１単語あたりの解析時間を１０秒に制限し、その時間を越えた場合には、その単語についての解析を終了し、次の単語の解析へと進ませた。実施例１及び比較例１のそれぞれの構文解析装置における１単語あたりの解析時間、及び正解率を表２に示す。ただし、正解率は、文全体に対して得られた解析結果の中に、正解の構文木が存在した文の割合（％）である。正解の構文木は、文にあらかじめ付与されている構文木とした。
【表２】
2004271764.tif 000016
【００４５】
実験結果より、実施例１の漸進的構文解析装置を用いることによって、比較例１よりも高速に解析できることがわかった。さらに、日本語の発話速度が１単語あたり０．２５秒程度であるのに対し、実施例１の漸進的構文解析装置における解析速度は０．０５秒となっており、発話速度を上回っている。これは、実施例１の漸進的構文解析装置が実時間での漸進的構文解析に有効であることを示している。
また、計算回数について比較するため、それぞれの解析方法について、１単語あたりの計算回数について調査した。有限状態変換器を用いた実施例１による解析については、状態を遷移して構文木を作成するときに１回の計算と数え、比較例１の漸進的チャート解析では、文法規則を適用するとき、及び、項を置き換えるとき、それぞれ１回の計算と数えた。その結果、１単語あたりの計算回数は、実施例１では１，２０９回、比較例１では、３６，３００回であり、実施例１では比較例１よりも計算回数が大幅に少なくなっていることからも、有限状態変換器を用いることによって構文解析処理を高速化できることがわかった。
【００４６】
次に、有限状態変換器を使用した漸進的構文解析装置に関し、置き換え優先度を使用して作成した有限状態変換器を用いた実施例２及び３と、置き換え優先度を使用せずに作成した従来技術における有限状態変換器を用いた比較例２とについて、構文解析結果の正解率を比較する実験を行った。ここで、実施例２は、非終端記号をラベルに持つ弧の除去を実施しないで作成した有限状態変換器を用いた場合であり、実施例３は、弧の除去を実施して作成した有限状態変換器を用いた場合である。また、各実施例２，３について、それぞれ文法規則の適用確率の条件の数をＮ＝０からＮ＝４まで変化させて有限状態変換器の作成を行った。実験結果を図１３に示す。ただし、Ｎは、文法規則適用確率の規則条件数を表す。
実験結果から、有限状態変換器作成に置き換え優先度を利用した実施例２，３の正解率は、利用しなかった比較例２に比べかなり向上しており、置き換え優先度を用いた弧の置き換え順序の制御は、有効であることがわかった。また、非終端記号の弧を除去した有限状態変換器を用いた実施例３は、弧の除去を行わなかった有限状態変換器を用いた実施例２よりも正解率が向上している。従って、いずれの実施例についても置き換え優先度を用いない比較例２よりも正解率が向上しており、さらに、置き換え優先度と非終端記号の弧の除去とを組み合わせることによって、８０％後半の正解率を達成できることがわかった。また、文法規則の適用確率の条件数Ｎを０から４まで増加させるに従って正解率が向上していることがわかる。
【００４７】
【発明の効果】
以上詳述したように、本発明の有限状態変換器作成装置、プログラム、記録媒体、作成方法によれば、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用されるので、限られた大きさで、より多くの文を解析可能な有限状態変換器を、確実に作成することができるという効果を奏する。
また、本発明の漸進的構文解析装置によれば、文法規則の適用頻度に関する統計情報に基づく弧の置き換え優先度が高い弧から順に置き換え操作が適用された有限状態変換器を備え、連接処理手段が、その有限状態変換器へ単語を入力する度に状態遷移に伴って出力される構文木を順次連接するように構成されているので、文脈自由文法を近似変換した限られた大きさの有限状態変換器を用いて、より多くの文について漸進的に構文解析を行うことができるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の一実施形態における有限状態変換器作成装置の全体構成を示すブロック図である。
【図２】文法規則の集合を表すＰＸの一例を示す図である。
【図３】再帰遷移ネットワーク中のＭＸの一例を示す図である。
【図４】再帰遷移ネットワークにおける状態の統合を説明する図である。
【図５】最初に与えられる初期有限状態変換器Ｍ０を示す図である。
【図６】弧の置き換え操作の一例並びに弧と節点との対応関係を示す図である。
【図７】節点の導出における文法規則適用の過程を示す図である。
【図８】構文木から獲得される文法規則の組の一例を示す図である。
【図９】弧の連続的な除去方法を説明する図である。
【図１０】本実施形態の漸進的構文解析装置の全体構成を示すブロック図である。
【図１１】構文解析の一例を示す図である。
【図１２】出力記号列が表す構文木の一例を示す図である。
【図１３】構文解析の実験結果（正解率）を示すグラフである。
【符号の説明】
１…有限状態変換器作成装置、２…再帰遷移ネットワーク作成部（再帰遷移ネットワーク作成手段）、３…弧置き換え部（弧置き換え手段）、４…優先度計算部（優先度計算手段）、５…弧除去部（弧除去手段）、２１…漸進的構文解析装置、２２…有限状態変換器、２３…連接処理部（連接処理手段）。
【図１】
2004271764.tif 000017
【図２】
2004271764.tif 000018
【図３】
2004271764.tif 000019
【図４】
2004271764.tif 000020
【図５】
2004271764.tif 000021
【図６】
2004271764.tif 000022
【図７】
2004271764.tif 000023
【図８】
2004271764.tif 000024
【図９】
2004271764.tif 000025
【図１０】
2004271764.tif 000026
【図１１】
2004271764.tif 000027
【図１２】
2004271764.tif 000028
【図１３】
2004271764.tif 000029