(57)【要約】【課題】確率文脈自由文法探索において、探索結果の精度を維持しつつ、計算コストを低減する技術に関する。【解決手段】確率文脈自由文法探索において、終端記号と非終端記号（ノード）と確率付き生成規則の集合によって定義される文法Ｇが与えられたとする。まず、文法Ｇをランダムに並び換える（ステップＳ１０１）。次に、ノードをすべて集約して近似確率Ｐ２を算出し（ステップＳ１０５）、文法Ｇに対してノードの枝刈り（枝刈りされた部分は探索の対象外とされる）を行いつつ、ノードを高さごとに集約して近似確率Ｐ１を算出して（ステップＳ１０７）、解候補の確率θと比較し（ステップＳ１０６、Ｓ１０８）、ノードの枝刈りを行いつつ、厳密な確率Ｐの算出に用いられる文法の数やノードの数を低減した上で、厳密な確率計算を行う（ステップＳ１０９）。【選択図】 図３
2010066970.tif 000002
【特許請求の範囲】
【請求項１】
確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、
文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、
問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、
前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（１）を適用して第１の近似確率Ｐ１を算出し、前記第１の近似確率Ｐ１と前記確率θとを比較し、前記第１の近似確率Ｐ１が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記取得した前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、
最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、
を備えることを特徴とする確率文脈自由文法探索装置。
【数１】
2010066970.tif 000024
【請求項２】
確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、
文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、
問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、
前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（３）を適用して第２の近似確率Ｐ２を算出し、前記第２の近似確率Ｐ２と前記確率θとを比較し、前記第２の近似確率Ｐ２が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、
最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、
を備えることを特徴とする確率文脈自由文法探索装置。
【数２】
2010066970.tif 000025
【請求項３】
確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、
文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、
問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、
前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（３）を適用して第２の近似確率Ｐ２を算出し、前記第２の近似確率Ｐ２と前記確率θとを比較し、前記第２の近似確率Ｐ２が前記確率θ以上の場合、前記探索対象とする文法に対して式（１）を適用して第１の近似確率Ｐ１を算出し、前記第１の近似確率Ｐ１と前記確率θとを比較し、前記第１の近似確率Ｐ１が前記確率θ以上の場合、前記探索対象とする文法に対して式（３）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記取得した前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、
最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、
を備えることを特徴とする確率文脈自由文法探索装置。
【数３】
2010066970.tif 000026
【請求項４】
確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、
文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、
問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、
前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（４）を適用して第３の近似確率Ｐ３を算出し、前記第３の近似確率Ｐ３と前記確率θとを比較し、前記第３の近似確率Ｐ３が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、
最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、
を備えることを特徴とする確率文脈自由文法探索装置。
【数４】
2010066970.tif 000027
【請求項５】
前記データ集合において、前記非終端記号から前記終端記号への遷移が、構文解析木によって表現されているとき、
前記探索部は、
前記探索対象とした前記文法に対して、式（５）または式（６）を適用して、前記問い合わせシーケンスの部分シーケンスの根となる非終端記号の確率の推定値を算出し、
前記確率の推定値が前記確率θより小さい場合、
前記部分シーケンスの根となる非終端記号からの遷移を表す構文解析木について、探索を行わないこと、
を特徴とする請求項１または請求項３に記載の確率文脈自由文法探索装置。
【数５】
2010066970.tif 000028
【請求項６】
前記探索部は、前記探索対象とする前記データ集合の文法を異なる順番で読み出すこと、
を特徴とする請求項１ないし請求項４のいずれか一項に記載の確率文脈自由文法探索装置。
【請求項７】
確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置において用いられる確率文脈自由文法探索方法であって、
前記確率文脈自由文法探索装置が、
文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、探索部とを有し、
前記探索部が、
問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、
前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（３）を適用して第２の近似確率Ｐ２を算出し、前記第２の近似確率Ｐ２と前記確率θとを比較し、前記第２の近似確率Ｐ２が前記確率θ以上の場合、前記探索対象とする文法に対して式（１）を適用して第１の近似確率Ｐ１を算出し、前記第１の近似確率Ｐ１と前記確率θとを比較し、前記第１の近似確率Ｐ１が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記取得した前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、
最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索ステップを実行すること、
を特徴とする確率文脈自由文法探索方法。
【数３】
2010066970.tif 000029
【請求項８】
前記データ集合において、前記非終端記号から前記終端記号への遷移が、構文解析木によって表現されているとき、
前記探索部は、
前記探索対象とした前記文法に対して、式（５）または式（６）を適用して、前記問い合わせシーケンスの部分シーケンスの根となる非終端記号の確率の推定値を算出し、
前記確率の推定値が前記確率θより小さい場合、
前記部分シーケンスの根となる非終端記号からの遷移を表す構文解析木について、探索を行わないこと、
を特徴とする請求項７に記載の確率文脈自由文法探索方法。
【数５】
2010066970.tif 000030
【請求項９】
確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置において用いられる確率文脈自由文法探索方法であって、
前記確率文脈自由文法探索装置が、
文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、探索部とを有し、
前記探索部が、
問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、
前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（４）を適用して第３の近似確率Ｐ３を算出し、前記第３の近似確率Ｐ３と前記確率θとを比較し、前記第３の近似確率Ｐ３が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、
最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索ステップを実行すること、
を特徴とする確率文脈自由文法探索方法。
【数４】
2010066970.tif 000031
【請求項１０】
コンピュータを請求項１ないし請求項６のいずれか一項に記載の確率文脈自由文法探索装置を構成する各部として、コンピュータを機能させるための確率文脈自由文法探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、確率文脈自由文法探索において正解となる確率の高い文法を探索するときに、計算コストを低減する確率文脈自由文法探索装置、確率文脈自由文法探索方法、および確率文脈自由文法探索プログラムに関する。
【背景技術】
【０００２】
確率文脈自由文法（PCFG; Probabilistic Context-Free Grammar）は、人間の行動認識（非特許文献１）、自然言語処理（非特許文献２）、あるいはＲＮＡ（RiboNucleic Acid）の構造解析（非特許文献３）等に用いられている。確率文脈自由文法は、各生成規則に確率が対応している文脈自由文法であって、その導出（構文解析）の確率が、その導出で使われた生成規則群の確率の積で表されることに特徴がある。
【非特許文献１】Yuri A. Ivanov，et al.，“Recognition of Visual Activities and Interactions by Stochastic Parsing”，IEEE Transactions on Pattern Analysis and Machine Intelligence，vol.22，no.8，p.852-872，(2000)
【非特許文献２】北研二，“確率的言語モデル”，東京大学出版会，p.127-135，(1999)
【非特許文献３】阿久津達也，“バイオインフォマティックスの数理とアルゴリズム”，共立出版，p.140-141，(2007)
【０００３】
（確率文脈自由文法の概要）
ここで、確率文脈自由文法の概要について、以下に説明する。説明に使用される主な記号とその定義を表１に示す。
【表１】
2010066970.tif 000003
【０００４】
まず、確率文脈自由文法における文法Ｇは以下の要素の組で定義される。
終端記号の集合：ｘ＝｛ｘｉ｝（１≦ｉ≦ｓ）
非終端記号の集合：ｙ＝｛ｙｉ｝（１≦ｉ≦ｎ）
確率付き生成規則の集合：ｐ＝｛ｐ（ｙｉ→ｙｊ，ｙｋ），ｐ（ｙｉ→ｘｊ）｝
【０００５】
また、ある文法Ｇが問い合わせシーケンスＸに対して適用されたとき、その文法Ｇが正解らしい度合いを表す確率Ｐ（厳密な確率）は以下のようにして求めることができる（Christopher D. Manning et al.，“Foundations of Statistical Natural Language Processing”，The MIT Press.，(1999)）。
【０００６】
【数６】
2010066970.tif 000004
【０００７】
ここで、ｐi,jは問い合わせシーケンスＸの部分シーケンス［ｘｉ，・・，ｘｊ］から求められる解の確率である。また、ｕ，ｖはともに非終端記号の集合である。
【０００８】
終端記号ｘと非終端記号ｙとの関係は、構文解析木として、図１０に示すように、線分によって表される。図１０は、構文解析木の一例を示す図である。
図１０に示す、ｐ11，ｐ12・・等は、白丸印で表しているノード（非終端記号ｙ）の確率である。そして、各ノードの確率ｐi,j（ｙ）は、動的計画法を用いてボトムアップすることによって算出される。以下に、その具体例を示す。
【０００９】
（具体例１）
問い合わせシーケンスＸと文法Ｇexとが以下のように与えられているものとする。
問い合わせシーケンスＸ＝［ｘ２，ｘ１，ｘ３］
文法Ｇex；
ｙ１→ｙ２ｙ３0.25，ｙ１→ｙ３ｙ２0.75，ｙ２→ｙ２ｙ２0.25
ｙ２→ｙ２ｙ３0.25，ｙ２→ｘ１0.25，   ｙ２→ｘ２0.25
ｙ３→ｙ３ｙ２0.25，ｙ３→ｘ１0.5，    ｙ３→ｘ３0.25
ただし、「→」は、左辺の項から右辺の項へ遷移する構文解析木があることを示している。また、小数点で表されている数字は、遷移する確率を表す。
【００１０】
そのとき、各ノードの確率ｐi,j（ｙ）は以下のように計算される。
ｐ1,1（ｙ１）＝0，         ｐ1,1（ｙ２）＝0.25，       ｐ1,1（ｙ３）＝0，
ｐ2,2（ｙ１）＝0，         ｐ2,2（ｙ２）＝0.25，       ｐ2,2（ｙ３）＝0.5，
ｐ3,3（ｙ１）＝0，         ｐ3,3（ｙ２）＝0，          ｐ3,3（ｙ３）＝0.25，
ｐ1,2（ｙ１）＝0.25２・0.5，ｐ1,2（ｙ２）＝0.25２・0.5， ｐ1,2（ｙ３）＝0，
ｐ2,3（ｙ１）＝0.25３，     ｐ2,3（ｙ２）＝0.25３，      ｐ2,3（ｙ３）＝0，
ｐ1,3（ｙ１）＝0.25４・0.5，
【００１１】
そして、この文法Ｇexを用いたときに、問い合わせシーケンスＸに適用される構文解析木の解は以下のようになる。
【００１２】
【数７】
2010066970.tif 000005
【００１３】
したがって、この問い合わせシーケンスＸに対する解の確率Ｐは、0.25４・0.5となる。
【００１４】
ここで、具体例１において、一つの文法Ｇexを用いたときの問い合わせシーケンスＸの解の確率ｐを計算するために必要な計算量について説明する。必要な計算量はＯ（ｎ３Ｌ３）となる。この根拠は、具体例１では、構文解析木が（ｙｉ→ｙｊ，ｙｋ）で表現されているように、３つの非終端記号がそれぞれｎ通りあるので、すべての非終端記号の組み合わせは（Ｏ（ｎ３））となる。そして、すべての非終端記号の組み合わせ（Ｏ（ｎ３））に対して、問い合わせシーケンスの数分のノード（Ｏ（Ｌ））ごとに確率を計算する。さらに、具体例１では、構文解析木の高さがＬのノードの数はΣｉ（ただし、１≦ｉ≦Ｌ）＝Ｌ（Ｌ＋１）／２、すなわち（Ｏ（Ｌ２））となるので、それらのノードの数（Ｏ（Ｌ２））に対して確率を計算するからである。そして、厳密な確率計算を行う場合には、正解となる確率の高い文法を選択するために、確率文脈自由文法のデータ集合の文法Ｇexの中にあるすべての文法に対して確率を計算する必要がある。すなわち、厳密な確率計算を行う場合には、すべての文法Ｇexの数をｍとすると（表１参照）、Ｏ（ｍｎ３Ｌ３）の計算量が必要になる。また、これらの計算に必要な記憶容量も計算量に依存して大きくなる。したがって、厳密な確率計算を行うと、計算コストが莫大になる。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
前記したように、すべての確率文脈自由文法のデータ集合の中から、正解である確率の高い文法を探索するためには、大きな計算コストを必要とするという問題がある。
そこで、本発明の課題は、このような問題を解決するために、計算コストを低減することを目的とする。
【課題を解決するための手段】
【００１６】
前記課題を解決するために、請求項１に記載の発明は、確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（１）を適用して第１の近似確率Ｐ１を算出し、前記第１の近似確率Ｐ１と前記確率θとを比較し、前記第１の近似確率Ｐ１が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記取得した前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、を備えることを特徴とする。
【００１７】
【数１】
2010066970.tif 000006
【００１８】
このような構成によれば、確率文脈自由文法探索装置は、まず、第１の近似確率Ｐ１を算出する第１近似確率計算を行う。そのため、第１近似確率計算（式（１）参照）では、文法の構文解析木において同じ高さとなる非終端記号を集約しているので、減らされた非終端記号の数の分の計算量を減らすことが可能となる。そして、第１近似確率計算によって検索対象の数を絞ってから、厳密な確率計算（式（２）参照）を実行する。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。
【００１９】
請求項２に記載の発明は、確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（３）を適用して第２の近似確率Ｐ２を算出し、前記第２の近似確率Ｐ２と前記確率θとを比較し、前記第２の近似確率Ｐ２が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、を備えることを特徴とする。
【００２０】
【数２】
2010066970.tif 000007
【００２１】
このような構成によれば、確率文脈自由文法探索装置は、まず、第２の近似確率Ｐ２を算出する第２近似確率計算を行う。そのため、第２近似確率計算（式（３）参照）では、すべての非終端記号を一つに集約しているので、減らされた非終端記号の数の分の計算量を減らすことが可能となる。そして、第２近似確率計算によって検索対象の数を絞ってから、厳密な確率計算（式（２）参照）を実行する。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。
【００２２】
請求項３に記載の発明は、確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して請求項３の式（３）を適用して第２の近似確率Ｐ２を算出し、前記第２の近似確率Ｐ２と前記確率θとを比較し、前記第２の近似確率Ｐ２が前記確率θ以上の場合、前記探索対象とする文法に対して式（１）を適用して第１の近似確率Ｐ１を算出し、前記第１の近似確率Ｐ１と前記確率θとを比較し、前記第１の近似確率Ｐ１が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記取得した前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、を備えることを特徴とする。
【００２３】
【数３】
2010066970.tif 000008
【００２４】
また、請求項７に記載の発明は、確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置において用いられる確率文脈自由文法探索方法であって、前記確率文脈自由文法探索装置が、文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、探索部とを有し、前記探索部が、問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（３）を適用して第２の近似確率Ｐ２を算出し、前記第２の近似確率Ｐ２と前記確率θとを比較し、前記第２の近似確率Ｐ２が前記確率θ以上の場合、前記探索対象とする文法に対して式（１）を適用して第１の近似確率Ｐ１を算出し、前記第１の近似確率Ｐ１と前記確率θとを比較し、前記第１の近似確率Ｐ１が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記取得した前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索ステップを実行すること、を特徴とする。
【００２５】
このような構成によれば、確率文脈自由文法探索では、まず、最も計算コストを低減可能な第２の近似確率計算を行って、探索対象となる文法の数を絞りこみ、次に、第１の近似確率計算を行って、さらに探索対象となる文法を絞りこんだ上で、厳密な確率計算を実行する。第２近似確率計算（式（３）参照）では、すべての非終端記号を一つに集約しているので、減らされた非終端記号の数の分だけ格段に計算量を減らすことが可能であるが、その代わりに探索対象となる文法の絞込みが緩い。次に、第１近似確率計算（式（１）参照）では、文法の構文解析木において同じ高さとなる非終端記号を集約しているので、第２近似確率計算より、さらに探索最小となる文法の絞込みを行うことが可能となる。したがって、このような手順を踏むことによって、さらに、計算コストの低減を図ることが可能となり、また探索結果の精度の維持との両立が図られる。
【００２６】
請求項４に記載の発明は、確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置であって、文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（４）を適用して第３の近似確率Ｐ３を算出し、前記第３の近似確率Ｐ３と前記確率θとを比較し、前記第３の近似確率Ｐ３が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索部と、を備えることを特徴とする。
【００２７】
【数４】
2010066970.tif 000009
【００２８】
また、請求項９に記載の発明は、確率文脈自由文法を用いて、問い合わせシーケンスに対して正解となる確率の高い文法を探索する確率文脈自由文法探索装置において用いられる確率文脈自由文法探索方法であって、前記確率文脈自由文法探索装置が、文法の終端記号の集合、非終端記号の集合、および確率付き生成規則の集合によって表した文法の集まりであるデータ集合を記憶する記憶部と、探索部とを有し、前記探索部が、問い合わせシーケンスに適用される文法の候補と、その文法の候補が正解となる確率θとに初期値を設定し、前記データ集合から一つの探索対象とする文法を取得して、その取得した前記探索対象とする文法に対して式（４）を適用して第３の近似確率Ｐ３を算出し、前記第３の近似確率Ｐ３と前記確率θとを比較し、前記第３の近似確率Ｐ３が前記確率θ以上の場合、前記探索対象とする文法に対して式（２）に適用して厳密な確率Ｐを算出し、前記厳密な確率Ｐと前記確率θとを比較し、前記厳密な確率Ｐが前記確率θ以上の場合、前記確率θを当該厳密な確率Ｐに更新し、前記問い合わせシーケンスに適用される文法の候補を、当該厳密な確率Ｐが前記確率θ以上となった前記探索対象とする文法に更新する探索処理を、前記データ集合に含まれるすべての文法に対して繰り返し行い、最後に更新された前記問い合わせシーケンスに適用される文法の候補を前記問い合わせシーケンスに対して正解となる確率の高い文法として出力する探索ステップを実行すること、を特徴とする。
【００２９】
このような構成によれば、確率文脈自由文法探索装置は、まず、第３の近似確率Ｐ３を算出する第３近似確率計算を行う。そのため、第３近似確率計算（式（４）参照）では、すべての非終端記号を一つに集約しているので、減らされた非終端記号の数の分の計算量を減らすことが可能となる。そして、第３近似確率計算によって検索対象の数を絞ってから、厳密な確率計算（式（２）参照）を実行する。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。
【００３０】
請求項５に記載の発明は、請求項１または請求項３に記載の確率文脈自由文法探索装置では、前記データ集合において、前記非終端記号から前記終端記号への遷移が、構文解析木によって表現されているとき、前記探索部が、前記探索対象とした前記文法に対して、式（５）または式（６）を適用して、前記問い合わせシーケンスの部分シーケンスの根となる非終端記号の確率の推定値を算出し、前記確率の推定値が前記記憶部に記憶している解候補の確率より小さい場合、前記部分シーケンスの根となる非終端記号からの遷移を表す構文解析木について、探索を行わないこと、を特徴とする。
【００３１】
【数５】
2010066970.tif 000010
【００３２】
また、請求項８に記載の発明は、請求項７に記載の確率文脈自由文法探索方法であって、前記データ集合において、前記非終端記号から前記終端記号への遷移が、構文解析木によって表現されているとき、前記探索部が、前記探索対象とした前記文法に対して、式（５）または式（６）を適用して、前記問い合わせシーケンスの部分シーケンスの根となる非終端記号の確率の推定値を算出し、前記確率の推定値が前記記憶部に記憶している解候補の確率より小さい場合、前記部分シーケンスの根となる非終端記号からの遷移を表す構文解析木について、探索を行わないこと、を特徴とする。
【００３３】
このような構成によれば、確率文脈自由文法探索では、第１近似確率計算、第３近似確率計算、または厳密な確率計算を行う際に、探索を行わない構文解析木の根となる非終端記号を抽出する。そして、抽出した非終端記号を根とする構文解析木について探索を行わないので、計算コストを低減することが可能となる。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。
【００３４】
請求項６に記載の発明は、請求項１ないし請求項４のいずれか一項に記載の確率文脈自由文法探索装置において、前記探索部が、前記探索対象とする前記データ集合の文法を異なる順番で読み出すこと、を特徴とする。
【００３５】
このような構成によれば、確率文脈自由文法探索装置は、ランダムな順番で文法を読み出すことによって、問い合わせシーケンスとの組み合わせに対する計算コストの期待値を低減することが可能となる。
【００３６】
請求項１０に記載の発明は、コンピュータを請求項１ないし請求項６のいずれか一項に記載の経路計算装置を構成する各部として、コンピュータを機能させるための経路計算プログラムとした。
【００３７】
このような経路計算プログラムをインストールされたコンピュータは、このプログラムに基づいた機能を実現することができる。
【発明の効果】
【００３８】
本発明によれば、確率文脈自由文法探索において、正解となる確率の高い文法を探索するときに、計算コストを低減することが可能になる。
【発明を実施するための最良の形態】
【００３９】
次に、本発明を実施するための最良の形態（以降「実施形態」と称す）について、適宜図面を参照しながら詳細に説明する。
【００４０】
（第１実施形態）
第１実施形態では、確率文脈自由文法のデータ集合の文法Ｇ＝｛Ｇ１，Ｇ２，・・，Ｇｍ｝と、問い合わせシーケンスＸ＝｛ｘ１，ｘ２，・・，ｘＬ｝が与えられたとき、すべての確率文脈自由文法のデータ集合を用いて、問い合わせシーケンスＸに対して解の確率の最も高い文法を厳密に探索する。具体的には、第１実施形態では、確率を近似計算して探索の解候補を絞り込み、少数に絞り込んだ解候補の文法に対して厳密な確率計算を行う。このように実行することによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能である。
【００４１】
まず、第１実施形態に係る確率文脈自由文法探索装置の構成を、図１を用いて説明する。図１は、第１実施形態に係る確率文脈自由文法探索装置の構成の一例を示す図である。
図１に示すように、確率文脈自由文法探索装置１は、探索部１０および記憶部２０を含んで構成される。
【００４２】
探索部１０は、入力となる問い合わせシーケンスＸを受け付けて、記憶部２０の確率文脈自由文法ＤＢ（Data Base）２１に格納されている確率文脈自由文法のデータ集合の文法Ｇを参照して、受け付けた問合せシーケンスＸの解を出力する。
記憶部２０は、確率文脈自由文法ＤＢ２１を格納する以外に、探索部１０の機能を実現するアプリケーションプログラムや、探索部１０によって算出された演算結果等を記憶する。記憶部２０は、ＨＤＤ（Hard Disk Drive）等の記憶装置によって実現される。
【００４３】
次に、探索部１０の機能について、図２を用いて説明する。図２は、探索部の機能を示す図である。
図２に示すように、探索部１０は、データ並び換え処理部１１、計算判定部１２、確率計算部１３、および探索結果保存部１４によって構成される。
【００４４】
データ並び換え処理部１１は、確率文脈自由文法ＤＢ２１に格納された確率文脈自由文法のデータ集合の文法Ｇに、ランダムな順番でアクセスし、アクセスして取得した文法Ｇを確率計算部１３に引き渡す。
計算判定部１２は、確率計算部１３によって算出された確率に基づいて、近似した確率計算（以降、近似確率計算という）を行うかあるいは厳密な確率計算を行うか、または次の順番の文法Ｇを対象として確率計算を行うかを判定する。なお、近似確率計算については、後記する。
確率計算部１３は、計算判定部１２による判定結果に基づいて、確率文脈自由文法のデータ集合の近似確率または厳密な確率を計算する。
探索結果保存部１４は、探索処理の途中における解候補およびその解候補の近似確率または厳密な確率を一時的に記憶する。なお、探索結果保存部１４は、記憶部２０に設けられていても構わない。
【００４５】
なお、探索部１０は、演算処理等を実行する図示しないＣＰＵ（Central Processing Unit）と、このＣＰＵが演算処理等に用いる図示しないメインメモリとによって構成される。そして、探索部１０は、アプリケーションプログラムがメインメモリに展開され、ＣＰＵが、それを実行することにより、各部（１１〜１４）の機能を具現化する。メインメモリは、ＲＡＭ（Random Access Memory）等により実現される。
【００４６】
次に、探索部１０における処理の流れについて、図３を用いて説明する（適宜、図２参照）。図３は、第１実施形態における探索部の処理の流れを示す図である。
まず、図２のデータ並び換え処理部１１は、確率文脈自由文法ＤＢ２１に格納された確率文脈自由文法のデータ集合の文法Ｇをランダムに並び換える（ステップＳ１０１）。そして、データ並び換え処理部１１は、並び換えられた文法Ｇを順に取得し、取得した文法Ｇを確率計算部１３に引き渡す。なお、ランダムに並び換える処理については、後記する。
【００４７】
そして、ステップＳ１０２では、確率計算部１３は、確率文脈自由文法のデータ集合の文法の解候補となる文法をＧanswerとし、初期値として、ダミーの文法Ｇ０をセットする。また、そのダミーの文法Ｇ０に対応する解候補の確率θは、０とする。そして、解候補の文法Ｇanswerとその解候補の確率θとは、互いに関連付けられて、探索結果保存部１４に記憶される。
ただし、ステップＳ１０４以降の探索処理の過程において、解候補の確率θは、探索によって直前の解候補の確率より高くなる文法を見つけたときの、その確率値である。したがって、解候補の確率θは、新しい解候補の文法Ｇが見つかるたびに単調に増加し、更新される。なお、この解候補の確率θが探索過程において単調に増加することは、近似確率計算であっても厳密な確率計算であっても同じである。
【００４８】
ステップＳ１０３では、確率計算部１３は、確率文脈自由文法のデータ集合の文法すべてを対象に確率計算を行うために、まず、変数ｉ＝１と設定する。
ステップＳ１０４では、確率計算部１３は、変数ｉがｍ以下か否かを判定する。
変数ｉがｍ以下の場合（ステップＳ１０４でＹｅｓ）、確率計算部１３は、文法Ｇｉについて第２近似確率計算を行って、近似確率Ｐ２を算出する（ステップＳ１０５）。なお、第２近似確率計算については、後記する。
【００４９】
次に、計算判定部１２が、近似確率Ｐ２がθ以上か否かを判定する（ステップＳ１０６）。
近似確率Ｐ２がθ以上の場合（ステップＳ１０６でＹｅｓ）、確率計算部１３は、文法Ｇｉに対してノードの枝刈りを行いつつ、第１近似確率計算を行って、近似確率Ｐ１を算出する（ステップＳ１０７）。なお、ノードの枝刈りおよび第１近似確率計算については、後記する。
【００５０】
そして、計算判定部１２が、近似確率Ｐ１がθ以上か否かを判定する（ステップＳ１０８）。
近似確率Ｐ１がθ以上の場合（ステップＳ１０８でＹｅｓ）、確率計算部１３は、文法Ｇｉに対してノードの枝刈りを行いつつ、厳密な確率計算を行って、厳密な確率Ｐを算出する（ステップＳ１０９）。
【００５１】
次に、計算判定部１２は、厳密な確率Ｐがθ以上か否かを判定する（ステップＳ１１０）。
厳密な確率Ｐがθ以上の場合（ステップＳ１１０でＹｅｓ）、確率計算部１３は、文法ＧｉをＧanswerにセットし、解候補の確率θを厳密な確率Ｐに更新する（ステップＳ１１１）。そして、解候補の文法Ｇanswerとその解候補の確率θとは、探索結果記憶部１４に記憶される。
そして、ステップＳ１１２へ進み、変数ｉが１増加されて、ステップＳ１０４へ戻り、次の文法Ｇi+1に対する処理が行われる。
【００５２】
最後に、変数ｉがｍより大きくなると（ステップＳ１０４でＮｏ）、確率計算部１３は、Ｇanswerを解として出力する（ステップＳ１１３）。
なお、ステップＳ１０６，Ｓ１０８，およびＳ１１０でＮｏの場合、ステップＳ１１２へ進み、変数ｉが１増加されて、ステップＳ１０４へ戻り、次の文法Ｇi+1に対する処理が行われる。
また、図３に示す処理の流れにおいては、後記する定理１によって、解候補の確率Ｐ，近似確率Ｐ１，および近似確率Ｐ２の間にはＰ≦Ｐ１≦Ｐ２の関係が保たれていることが明らかなため、正解となる確率の高い文法を漏れなく探索することが保証されている。
【００５３】
（近似確率計算の概要）
近似確率計算には、前記したように、第１近似確率計算および第２近似確率計算がある。
ここでは、近似確率計算を行うときの、３つの基本的手法の概要について説明する。３つの基本的手法とは、＜ノードの集約＞、＜ノードの枝刈り＞、および＜ランダムな並び換え＞である。
【００５４】
＜ノードの集約＞
近似確率計算を行うために、構文解析木のノードｙを集約する。この集約の方法について、図４を用いて説明する。図４（ａ）は、ノードを高さごとに集約する場合の概念図であり、（ｂ）は、ノードをすべて集約する場合の概念図である。
なお、図４（ａ）に示す、ノードを高さごとに集約する場合は、第１近似確率計算に対応している。また、図４（ｂ）に示す、ノードをすべて集約する場合は、第２近似確率計算に対応している。
【００５５】
（ａ）ノードを高さごとに集約する場合；第１近似確率計算
第１近似確率計算における近似確率Ｐ１は、以下のようにして求められる。
【００５６】
【数８】
2010066970.tif 000011
【００５７】
ここで、ｐｉは、高さがＬ−ｉのノードの確率とする。
以下に、具体例を示す。
【００５８】
（具体例２）
具体例１の文法Ｇexに対して、第１近似確率計算における近似確率Ｐ１は以下のように計算される。
ｐ１（ｙ１）＝0，              ｐ１（ｙ２）＝0.25，      ｐ１（ｙ３）＝0.5，
ｐ２（ｙ１）＝0.25・0.5・0.75，ｐ２（ｙ２）＝0.25２・0.5，ｐ２（ｙ３）＝0.25２・0.5，
ｐ３（ｙ１）＝0.25３・0.5２・0.75
よって、近似確率Ｐ１は0.25２・0.5２・0.75となる。したがって、Ｐ（＝0.25４・0.5）＜Ｐ１となる。
また、この近似計算の計算量はＯ（ｎ３Ｌ２）となる。これはすべての非終端記号の組み合わせ（Ｏ（ｎ３））に対してノード（Ｏ（Ｌ））ごとに確率を計算し、さらにノードごとに構文解析木の高さの数（Ｏ（Ｌ））に対して確率を計算するからである。したがって、計算量については、厳密な確率計算の計算量Ｏ（ｎ３Ｌ３）≧第１近似確率計算の計算量Ｏ（ｎ３Ｌ２）となる。
【００５９】
（ｂ）ノードをすべて集約する場合；第２近似確率計算
また、第２近似確率計算における近似確率Ｐ２は、以下のようにして求められる。
【００６０】
【数９】
2010066970.tif 000012
【００６１】
ここで、ｐmax（ｘ）とｐmax（ｙ）は、終端記号ｘおよび非終端記号ｙの生成確率の最大値であり、以下の式で表される。
【００６２】
【数１０】
2010066970.tif 000013
【００６３】
ここで、ｐmax（ｘ）とｐmax（ｙ）は、文法Ｇが与えられたとき、事前に計算することができる。
以下に、具体例を示す。
【００６４】
（具体例３）
具体例１の文法Ｇexに対して、近似確率Ｐ２は0.75２・0.5３となる。したがって、Ｐ（＝0.25４・0.5、具体例１参照）＜Ｐ１（＝0.25２・0.5２・0.75、具体例２参照）＜Ｐ２となる。また、計算量については、この第２近似確率計算に必要な計算コストは、文法が与えられるｐmax（ｘ）およびｐmax（ｙ）を計算できるため、Ｏ（１）となる。なお、Ｏ（１）は、構文解析木の大きさおよひ非終端記号の数によらず一定であることを表す。したがって、厳密な確率計算の計算量Ｏ（ｎ３Ｌ３）≧第１近似確率計算の計算量Ｏ（ｎ３Ｌ２））≧第２近似確率計算の計算量Ｏ（１）となる。
【００６５】
前記した各近似確率計算には、２つの優位な点がある。第１の優位な点は、これらの近似確率計算を用いたとしても、正解となる確率の高い文法を漏れなく探索することが保証されていることである。探索漏れが発生しない理由は、後記する定理１に示すように、近似確率計算によって算出された確率は厳密な確率計算によって算出された確率より小さくならないからである。さらに、第１近似確率計算によって算出された近似確率Ｐ１は、第２近似確率計算によって算出された近似確率Ｐ２より大きくなることはないからである。
また、第２の優位な点は、具体例１〜具体例３に示したように、厳密な確率計算の計算量がＯ（ｎ３Ｌ３）であるのに対して、第１近似確率計算の計算量がＯ（ｎ３Ｌ２）、第２近似確率計算の計算量がＯ（１）となることである。
したがって、まず、第２近似確率計算を行って、文法を残すか否かを判断し、次に残された文法に対して第１近似確率計算を行って、その文法を残すか否かを判定し、最後に厳密な確率計算を行えば、正解となる確率の高い文法を探索することが可能となる。しかも、近似確率計算を行ったことにより、計算量を低減できる。
【００６６】
（ノードの枝刈り）
厳密な確率計算および第１近似確率計算を実行するときに、解候補とならないことが明らかな文法の構造解析木について、ノードの枝刈りを行うことができる。すなわち、「ノードの枝刈り」とは、ノードｙから派生する枝（構造解析木）を探索対象にしないことである。
ノードの枝刈りについて、図５を用いて説明する。図５は、ノードの枝刈りの一例を示す図である。
図５において、ノードの枝刈りが行われた枝は、破線によって表されている。ノードの枝刈りは、以下のようにして行われる。
【００６７】
解候補の探索処理は、正解となる確率の高い文法を保持しながら行われる。すなわち、探索処理のある時点において、解候補の確率をθとすると、その後の探索処理において、θは、新しい解候補が見つかるたびに、大きくなるように更新される。したがって、問い合わせシーケンスＸの部分シーケンスに対するノードの確率がθより小さければ、そのノードの枝刈りが行われる。前記したように、θは探索処理の間に小さくなることはないので、正解となる確率の高いノードを枝刈りしてしまうことはない。
なお、ノードの枝刈りは厳密な確率計算に対してだけでなく、第１近似確率計算に対しても適用することができる。すなわち、ノードの枝刈りと第１近似確率計算とを併用すると、計算コストを低減して、効率よく探索することができる。
【００６８】
また、正解となる確率の高い文法は、近似確率計算によっては算出されず、厳密な確率計算によってのみ算出される。厳密な確率計算では、前記したように計算量はＯ（ｎ３Ｌ３）となるが、厳密な確率計算を行う前に、ノードの枝刈りが行われていれば、効率よく探索を行うことができる。
【００６９】
ここで、厳密な確率計算において枝刈りを行うことができることを、以下に説明する。なお、説明に使用するｅi,i+jは、問い合わせシーケンスＸの部分シーケンスの根となるノードにおける確率ｐi,i+jの推定値であるものとする。
【００７０】
【数１１】
2010066970.tif 000014
【００７１】
ここで、ｐmax（ｘ）とｐmax（ｙ）は、それぞれ式（４），（５）で定義したものと同じである。
【００７２】
推定値ｅi,i+jは、終端記号ｘおよび非終端記号ｙの生成確率の最大値を用いることにより、部分シーケンス［ｘｉ，・・，ｘi+j］の根となるノードを含む構文解析木の確率の上限値となる。
なぜなら、後記する定理２によって、ｅi,i+j（ｙ）が解候補の確率θより小さな値になれば、その根となるノードの非終端記号ｙが構文解析木に含まれないことが明らかなためである。したがって、探索結果に影響を与えることなく枝刈りすることができる。
【００７３】
また、ノードの枝刈りは、厳密な確率計算を行う場合だけなく、第１近似確率計算を行う場合にも、厳密な確率計算と同様に適用することができる。第１近似確率計算において、近似確率ｐｉを計算する場合の推定値ｅｉは、以下のとおりである。
【００７４】
【数１２】
2010066970.tif 000015
【００７５】
以下に、具体例を示す。
【００７６】
（具体例４）
具体例１の問い合わせシーケンスＸと文法Ｇexに対してθ＝0.01とすると、ｅ1,1（ｙ２）＞θであるので、部分シーケンスｘ１に対するノードの非終端記号ｙ21,1が配列Εに加えられる。同様にして、長さ１の部分シーケンスに対して、ｙ22,2，ｙ32,2，ｙ33,3が配列Εに加えられる。長さが２の部分シーケンスにおける推定値は、配列Εに含まれる非終端記号ｙからのみ計算し、ｙ11,2，ｙ21,2が配列Εに新たに加えられる。最終的に、推定値を計算するために必要なノードの非終端記号は｛ｙ21,1，ｙ22,2，ｙ32,2，ｙ33,3，ｙ11,2，ｙ21,2｝となる。
【００７７】
（ランダムな並び換え）
前記したように、第１近似確率計算を用いた解候補の探索においては、解候補の確率θより小さいノードについて、ノードの枝刈りが行われる。しかし、確率文脈自由文法のデータ集合から読み出される文法の順番によっては、第１近似確率計算によって全く枝刈りすることができない状況が起こりうる。そのため、確率文脈自由文法のデータ集合の文法Ｇをランダムに並び換えることにより、最大の計算コストになることを防ぐ。図６は、文法のランダムな並び替えを説明する概念図である。並び換えは、確率文脈自由文法のデータ集合から読み出される文法の順番を、乱数を用いてランダムに発生させた順番に交換することによって行われる。
【００７８】
探索処理においては、問い合わせシーケンスＸの部分シーケンスごとに、データ集合の中にある文法Ｇに対して一つずつ確率を計算して解候補であるか否かの判定をしていく。もし、探索処理に用いられる文法Ｇの順番が固定されていると、問い合わせシーケンスＸとの組み合わせによっては、ノードの枝刈りが行えず、最大の計算量になりうる。それを解消するため、探索処理ごとにデータ集合内の文法Ｇの並び換えを行う。その結果、問い合わせシーケンスＸが同じであっても、その計算量は探索処理ごとに違ってくる。例えば、ある問い合わせシーケンスＸに対する１回目の探索処理では厳密な確率計算を１０回行うことになるが、２回目の探索処理では、願密な確率計算は１回で済むこともある。すなわち、ある問い合わせシーケンスＸに対して、常に最大の計算コストになることを避けることができる。
【００７９】
このように、確率文脈自由文法のデータ集合の文法Ｇをランダムに並び換えることによって、その文法が最も高い確率に該当する確率は、すべての文法に対して等しくなり、その期待値はＯ（log(ｍ)・ｎ３Ｌ３）となる。
【００８０】
また、ランダムな並び換えは、確率文脈自由文法のデータ集合の文法Ｇのすべてに対してＯ（１）の処理を行うため、その計算コストはＯ（ｍ）となる。
【００８１】
以上、第１実施形態に記載の確率文脈自由文法探索装置１は、まず、ランダムな順番で文法を読み出す。このことによって、問い合わせシーケンスとの組み合わせに対する計算コストの期待値を低減することが可能となる。次に、第２の近似確率Ｐ２を算出する第２近似確率計算を行う。第２近似確率計算では、すべての非終端記号を一つに集約しているので、減らされた非終端記号の数の分だけ格段に計算量を減らすことが可能であるが、その代わりに探索対象となる文法の絞込みが緩い。そして、第２近似確率計算によって検索対象の数を絞ってから、ノードの枝刈りを行いつつ第１の近似確率Ｐ１を算出する第１近似確率計算を行う。第１近似確率計算では、文法の構文解析木において同じ高さとなる非終端記号を集約し、またノードの枝刈りを行っているので、減らされた非終端記号の数の分の計算量が少なくなる。また、第１近似確率計算では、第２近似確率計算より、さらに探索対象となる文法の絞込みを行うことが可能となる。そして、第１近似確率計算によって探索対象の数を絞ってから、さらにノードの枝刈りを行いつつ厳密な確率計算を実行する。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。
【００８２】
なお、第１実施形態について説明したが、本発明は、これらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
例えば、近似確率計算は、第１近似確率計算および第２近似確率計算のいずれか一方であっても構わない。
【００８３】
（第２実施形態）
第２実施形態では、確率文脈自由文法のデータ集合の文法Ｇと、問い合わせシーケンスＸ＝｛ｘ１，ｘ２，・・，ｘＬ｝と確率の高さが上位に入る割合ε（以降、上位割合という）とが与えられたとき、問い合わせシーケンスＸに対して上位割合εに入る文法を近似的に探索する。すなわち、［１／ε］個の文法を探索することで、上位割合εに入る文法を近似的に探索する。
この場合、上位割合εに入る文法を近似的に探索する場合における計算コストはＯ（log(１／ε)・ｎ３Ｌ３）となる。これは、上位割合εの文法がデータ集合から探索される期待値が１／εだからである。結果として、上位割合εに入る文法を近似的に探索するための計算コストはデータ集合の中にある文法の数ｍに依存しない。
つまり、１／ε＜ｍと設定すれば、第２実施形態は、第１実施形態に比べて、さらに、計算コストの低減を図ることが可能である。
【００８４】
第２実施形態における探索部の処理の流れを、図７を用いて説明する。図７は、第２実施形態における探索部の処理の流れを示す図である。
なお、ステップＳ１０４ａ以外の処理は、第１実施形態における処理と同様であるので、同じ符号を付し、詳細な説明を省略する。
【００８５】
ステップＳ１０１では、まず、データ集合の文法Ｇをランダムな順番に並び換える。そして、並び換えられた［１／ε］個の文法Ｇに対して（ステップＳ１０４ａ）、第２近似確率計算によって、近似確率Ｐ２を算出する（ステップＳ１０５）。そして、近似確率Ｐ２≧θの場合（ステップＳ１０６でＹｅｓ）、第１近似確率計算によって、ノードの枝刈りを行いつつ、近似確率Ｐ１を算出する（ステップＳ１０７）。そして、近似確率Ｐ１≧θの場合（ステップＳ１０８でＹｅｓ）、厳密な確率計算によって、ノードの枝刈りを行いつつ、厳密な確率Ｐを算出する（ステップＳ１０９）。厳密な確率Ｐ≧θの場合（ステップＳ１１０）、そのときの文法Ｇを新たな解候補とし、Ｇanswerに設定する（ステップＳ１１１）。なお、近似確率Ｐ１および厳密な確率Ｐの計算過程においては、前記した推定値（式（９）参照）を用いてノードの枝刈りを行う。
【００８６】
以上、第２実施形態における確率文脈自由文法探索装置１は、第１実施形態に記載の確率文脈自由文法探索装置１と同様に、まず、ランダムな順番で文法を読み出す。このことによって、問い合わせシーケンスとの組み合わせに対する計算コストの期待値を低減することが可能となる。次に、第２の近似確率Ｐ２を算出する第２近似確率計算を行う。第２近似確率計算では、すべての非終端記号を一つに集約しているので、減らされた非終端記号の数の分だけ格段に計算量を減らすことが可能であるが、その代わりに探索対象となる文法の絞込みが緩い。そして、第２近似確率計算によって検索対象の数を絞ってから、ノードの枝刈りを行いつつ第１の近似確率Ｐ１を算出する第１近似確率計算を行う。第１近似確率計算では、文法の構文解析木において同じ高さとなる非終端記号を集約し、またノードの枝刈りを行っているので、減らされた非終端記号の数の分の計算量が少なくなる。また、第１近似確率計算では、第２近似確率計算より、さらに探索対象となる文法の絞込みを行うことが可能となる。そして、第１近似確率計算によって探索対象の数を絞ってから、さらにノードの枝刈りを行いつつ厳密な確率計算を実行する。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。さらに、第２実施形態は、探索対象となる文法の個数を第１実施形態で用いられる文法の個数より少なくしているので、第１実施形態よりも計算コストを低減できる。
【００８７】
なお、第２実施形態について説明したが、本発明は、これらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
例えば、近似確率計算は、第１近似確率計算および第２近似確率計算のいずれか一方であっても構わない。
【００８８】
（第３実施形態）
第３実施形態では、第１実施形態における第１近似確率計算および第２近似確率計算の代わりに、第３近似確率計算を用いる場合の探索部の処理の流れを、図８を用いて説明する。図８は、第３実施形態における探索部の処理の流れを示す図である。
なお、図８においては、第１実施形態における処理の流れ（図３参照）とは、ステップＳ１２１およびステップＳ１２２が新たに追加され、ステップＳ１０５〜ステップＳ１０８の処理が削除された以外は、同様であるので、同じ符号を付し、詳細な説明を省略する。
【００８９】
図８において、ｉがｍ以下の場合（ステップＳ１０４でＹｅｓ）、確率計算部１３は、文法Ｇｉに対して第３近似確率計算を行って、文法Ｇｉが解候補となる近似確率Ｐ３を算出する（ステップＳ１２１）。
そして、計算判定部１２が、近似確率Ｐ３がθ以上か否かを判定する（ステップＳ１２２）。
近似確率Ｐ３がθより小さい場合（ステップＳ１２２でＮｏ）、ステップＳ１１２へ進み、変数ｉが１増加されて、ステップＳ１０４へ戻り、次の文法Ｇi+1に対する処理が行われる。
近似確率Ｐ３がθ以上の場合（ステップＳ１２２でＹｅｓ）、処理はステップＳ１０９へ進む。
ステップＳ１０９以降の処理については、第１実施形態（図３参照）と同様であるので、説明を省略する。
【００９０】
前記した第３近似確率計算には、優位な点がある。この優位な点は、この第３近似確率計算を用いたとしても、正解となる確率の高い文法を漏れなく探索することが保証されていることである。探索漏れが発生しない理由は、後記する定理３に示すように、第３近似確率計算によって算出された確率は厳密な確率計算によって算出された確率より小さくならないからである。すなわち、近似確率Ｐ３≧厳密な確率Ｐである。
【００９１】
（第３近似確率計算）
ここで、第３近似確率計算について説明する。第３近似確率計算は、ノードをすべて集約した場合の近似確率Ｐ３を算出する。近似確率Ｐ３は、以下のようにして求める。
【００９２】
【数１３】
2010066970.tif 000016
【００９３】
ここで、ｐmax（ｘｉ）は、終端記号ｙごとの生成確率の最大値であり、以下のようにして求める。
【００９４】
【数１４】
2010066970.tif 000017
【００９５】
ｐmax（ｘｉ）は、文法が与えられたときに事前に計算することができる。
以下に、具体例を示す。
【００９６】
（具体例５）
実施例１の文法Ｇexに対して、ノードをすべて集約した近似確率Ｐ３は、0.752・0.5・0.252となる。したがって、Ｐ（＝0.25４・0.5、具体例１参照）＜Ｐ３となる。また、第３近似確率計算に必要な計算コストはＯ（Ｌ）となる。したがって、計算量については、厳密な確率計算の計算量Ｏ（ｎ３Ｌ３）≧第３近似確率計算の計算量Ｏ（Ｌ）となる。
【００９７】
以上、第３実施形態における確率文脈自由文法探索装置１によれば、第１実施形態に記載の確率文脈自由文法探索装置１と同様に、まず、ランダムな順番で文法を読み出す。このことによって、問い合わせシーケンスとの組み合わせに対する計算コストの期待値を低減することが可能となる。次に、第３の近似確率Ｐ３を算出する第３近似確率計算を行う。第３近似確率計算では、すべての非終端記号を一つに集約しているので、減らされた非終端記号の数の分の計算量が少なくなる。そして、第３近似確率計算によって検索対象の数を絞ってから、さらにノードの枝刈りを行いつつ厳密な確率計算を実行する。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。
【００９８】
なお、第３実施形態について説明したが、本発明は、これらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
例えば、第３近似確率計算は、第１近似確率計算および第２近似確率計算のいずれか一方または双方と併用しても構わない。また、第３近似確率計算を、第１近似確率計算および第２近似確率計算の双方と併用する場合には、第２近似確率計算を行った後に第３近似確率計算を行う順にするとよい。
【００９９】
（第４実施形態）
第４実施形態では、第２実施形態における第１近似確率計算および第２近似確率計算の代わりに、第３近似確率計算を用いる場合の探索部の処理の流れを、図９を用いて説明する。図９は、第４実施形態における探索部の処理の流れを示す図である。
なお、図９においては、第２実施形態における処理の流れ（図７参照）とは、ステップＳ１２１およびステップＳ１２２が新たに追加され、ステップＳ１０５〜ステップＳ１０８の処理が削除された以外は、同様であるので、同じ符号を付し、詳細な説明を省略する。
【０１００】
図９において、ｉが１／ε以下の場合（ステップＳ１０４ａでＹｅｓ）、確率計算部１３は、文法Ｇｉに対して第３近似確率計算を行って、文法Ｇｉが解候補となる近似確率Ｐ３を算出する（ステップＳ１２１）。
そして、計算判定部１２が、近似確率Ｐ３がθ以上か否かを判定する（ステップＳ１２２）。
近似確率Ｐ３がθより小さい場合（ステップＳ１２２でＮｏ）、ステップＳ１１２へ進み、変数ｉが１増加されて、ステップＳ１０４へ戻り、次の文法Ｇi+1に対する処理が行われる。
近似確率Ｐ３がθ以上の場合（ステップＳ１２２でＹｅｓ）、処理はステップＳ１０９へ進む。
ステップＳ１０９以降の処理については、第２実施形態（図７参照）と同様であるので、説明を省略する。
【０１０１】
以上、第４実施形態に記載の確率文脈自由文法探索装置１によれば、第２実施形態に記載の確率文脈自由文法探索装置１と同様に、まず、ランダムな順番で文法を読み出す。このことによって、問い合わせシーケンスとの組み合わせに対する計算コストの期待値を低減することが可能となる。次に、第３の近似確率Ｐ３を算出する第３近似確率計算を行う。第３近似確率計算では、すべての非終端記号を一つに集約しているので、減らされた非終端記号の数の分だけ計算量が少なくなる。そして、第３近似確率計算によって検索対象の数を絞ってから、さらにノードの枝刈りを行いつつ厳密な確率計算を実行する。このような手順を踏むことによって、計算コストの低減と探索結果の精度の維持とを両立させることが可能となる。さらに、第４実施形態は、探索対象となる文法の個数を第３実施形態で用いられる文法の個数より少なくしているので、第３実施形態よりも計算コストを低減できる。
【０１０２】
なお、第４実施形態について説明したが、本発明は、これらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
例えば、第３近似確率計算は、第１近似確率計算および第２近似確率計算のいずれか一方または双方と併用しても構わない。また、第３近似確率計算を、第１近似確率計算および第２近似確率計算の双方と併用する場合には、第２近似確率計算を行った後に第３近似確率計算を行う順にするとよい。
【０１０３】
以上、各実施形態において、確率文脈自由文法探索装置１（図１参照）の各部の処理について説明したが、これらの処理は、確率文脈自由文法探索装置１をコンピュータで実現したときに搭載されるプログラムによって実現されてもよい。このプログラムは、通信回線を介して提供することもできるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【０１０４】
（理論的解析）
ここで、各実施形態において用いた各定理、および精度と計算量について示す。なお、Ｌを問い合わせシーケンスの長さ、ｍをデータ集合における文法の数、ｎを非終端記号の数、εを上位割合（確率の高さが上位に入る割合）とする。
【０１０５】
《定理１》  近似確率Ｐ１，Ｐ２は、すべての文法に対して以下の不等式が成り立つ。
【０１０６】
【数１５】
2010066970.tif 000018
【０１０７】
《証明１》  部分シーケンス［ｘｉ］の確率ｐi,iに対して、以下のことが成り立つ。
ｐi,i（ｙ）＝ｐ（ｙ→ｘｉ）≦ｐ１（ｙ）≦ｐmax（ｘ）
そのため、部分シーケンス［ｘｉ，ｘi+1］の確率ｐi,i+1に対して、以下のことが成り立つ。
【０１０８】
【数１６】
2010066970.tif 000019
【０１０９】
よって、同様に部分シーケンス［ｘｉ，・・，ｘi+j］の確率ｐi,i+jに対して、以下のことが成り立つ。
ｐi,i+j（ｙ）≦ｐj+1（ｙ）≦{ｐmax（ｘ）}j+1・{ｐmax（ｙ）}j
【０１１０】
そのため、
Ｐ≦Ｐ１≦Ｐ２
が成り立つ。
【０１１１】
《定理２》  構文解析木が部分シーケンス［ｘｉ，・・，ｘi+j］のノードを含む場合、以下の不等式が成り立つ。
【０１１２】
【数１７】
2010066970.tif 000020
【０１１３】
《証明２》  部分シーケンス［ｘｉ，・・，ｘi+j］のノードの親ノードの確率ｐi-1,i+jとｐi,i+j+1に対して以下のことが成り立つ。
ｐi-1,i+j（ｙ），ｐi,i+j+1（ｙ）≦ｐi,i+j（ｙ）・ｐmax（ｘ）・ｐmax（ｙ）
よって、同様にシーケンス［ｘｉ，・・，ｘＬ］のノードの確率について、
ｐ1,Ｌ（ｙ）≦ｐi,i+j（ｙ）・｛ｐmax（ｘ）・ｐmax（ｙ）｝Ｌ-j-1
が成り立つ。よって、
Ｐ＝ｐ1,Ｌ（ｙ１）≦ｅi,i+j（ｙ）
となる。
【０１１４】
《定理３》  すべての文法に対して、近似確率Ｐ３に対して以下の不等式が成り立つ。
【０１１５】
【数１８】
2010066970.tif 000021
【０１１６】
《証明７》  部分シーケンス［ｘｉ］の確率ｐi,iに対して、以下のことが成り立つ。
ｐi,i（ｙ）＝ｐ（ｙ→ｘｉ）≦ｐmax（ｘｉ）
そのため、部分シーケンス［ｘｉ，ｘi+1］の確率ｐi,i+1に対して以下のことが成り立つ。
【０１１７】
【数１９】
2010066970.tif 000022
【０１１８】
よって、同様に部分シーケンス［ｘｉ，・・，ｘi+j］の確率ｐi,i+jに対して以下のことが成り立つ。
【０１１９】
【数２０】
2010066970.tif 000023
【０１２０】
そのため、
Ｐ≦Ｐ３
が成り立つ。
【０１２１】
＜精度について＞
《補助定理１》  本発明の各実施形態においては、正解となる確率の高い文法を求める場合、探索結果が正確であることを保証する。
《証明３》  Ｇbestを正解となる確率の高い文法とし、その確率をθbestとする。定理１および定理２より、すべての文法に対してＰ≦Ｐ１≦Ｐ２となる。また、Ｇbestに対してθbest≦Ｐ１≦Ｐ２となる。θbest≧θであるためＧbestの確率がθより小さくなることはない。探索処理においては確率がθより大きな文法は枝刈りしないため、Ｇbestが探索処理において枝刈りされることはない。
【０１２２】
《補助定理２》  本発明の実施形態においては、上位割合εの文法を探索する場合、探索結果は平均的に上位割合ε以内となる。
《証明４》  データ集合は、ランダムに並び換えられているため、ある文法が上位割合ε以内である確率はεである。そのため、文法をｉ個探索した場合、ｉ番目で初めて上位割合ε以内の文法が解候補になる確率はε（１−ε）i-1となる。よって、探索する文法の数の期待値はΣｉ・ε（１−ε）i-1≒１／εとなる。探索処理は、［１／ε］個の文法を探索するため、平均的に上位割合ε以内の文法を求めることができる。
【０１２３】
＜計算量について＞
《補助定理３》  本発明の各実施形態においては、ある文法の確率を計算するために少なくともＯ（１）、多くてもＯ（ｎ３Ｌ３）の計算量を要する。
《証明５》  ある文法がノードをすべて集約する近似確率のみで枝刈りできる場合、必要な計算量はＯ（１）である。文法が近似確率のみで枝刈りできない場合は、正確な確率を計算しなければならないので、近似確率の計算量はＯ（１＋ｎ３Ｌ２）となる。したがって、最大の計算量は厳密な確率計算によるものとなり、その計算量はＯ（ｎ３Ｌ３）となる。
【０１２４】
《補助定理４》  本発明の各実施形態においては、正解となる確率の高い文法を求める場合、正確な確率計算を行うときの計算コストは、平均的にＯ（log(ｍ)・ｎ３Ｌ３）となり、上位εの文法を求める場合には、その計算コストは平均的にＯ（log(１／ε)・ｎ３Ｌ３）となる。
《証明６》  データ集合の文法Ｇをランダムに並び換えているので、ｉ番目の文法がそれまでの探索処理において、正解となる確率の高い文法である確率は１／ｉである。そのため、ｍ個の文法を検索したときに、解候補が更新される回数の期待値はΣ１／ｉ≒ｌｎ（ｍ）＋Ｏ（１）（ただし、Σの変数ｉの範囲は、１≦ｉ≦ｍ）となる。また、ノードを高さごとに集約する近似確率Ｐ１は、ほぼ、厳密な確率計算による確率Ｐと等しい（Ｐ１≒Ｐ）ため、ほとんどの文法は近似確率においてノードの枝刈りを実行することができる。よって、確率を計算する回数は、解候補を更新する回数に依存する。そのため、正解となる確率の高い文法を求める場合は、計算コストは平均的にＯ（log(ｍ)・ｎ３Ｌ３）となる。また、上位割合εの文法を求める場合は、［１／ε］個の文法を探索するので、その計算コストは平均的にＯ（log(1/ε）・ｎ３Ｌ３）となる。
【図面の簡単な説明】
【０１２５】
【図１】第１実施形態に係る確率文脈自由文法探索装置の構成の一例を示す図である。
【図２】探索部の機能を示す図である。
【図３】第１実施形態における探索部の処理の流れを示す図である。
【図４】（ａ）は、ノードを高さごとに集約する場合の概念図であり、（ｂ）は、ノードをすべて集約する場合の概念図である。
【図５】ノードの枝刈りの一例を示す図である。
【図６】文法のランダムな並び換えを説明する概念図である。
【図７】第２実施形態における探索部の処理の流れを示す図である。
【図８】第３実施形態における探索部の処理の流れを示す図である。
【図９】第４実施形態における探索部の処理の流れを示す図である。
【図１０】構文解析木の一例を示す図である。
【符号の説明】
【０１２６】
１      確率文脈自由文法探索装置
１０    探索部
１１    データ並び換え処理部
１２    計算判定部
１３    確率計算部
１４    探索結果保存部
２０    記憶部
２１    確率文脈自由文法ＤＢ
【図１】
2010066970.tif 000032
【図２】
2010066970.tif 000033
【図３】
2010066970.tif 000034
【図４】
2010066970.tif 000035
【図５】
2010066970.tif 000036
【図６】
2010066970.tif 000037
【図７】
2010066970.tif 000038
【図８】
2010066970.tif 000039
【図９】
2010066970.tif 000040
【図１０】
2010066970.tif 000041