自然言語による対話システムは、統語論・意味論・語用論などのさまざまな制約を柔軟に用いて処理を進める必要がある。多様な制約を柔軟に用いることは対話システムに限らずもっと下位のシステム、例えば構文解析においても必要とされる。実際、[Nagata and Morimoto]や[Maxwell and Kaplan]らによってHPSG,LFGなどの句構造規則とカテゴリーに割り当てられた素性に関する制約を混合して用いる単一化文法における構文解析では、二種類の制約の処理の順序を工夫することによって著しい効率向上が得られることが指摘されている。具体的には、統語的な制約を先に処理しその後で意味に関する制約の処理を行なうという方法が一般に効率的であると報告されているが、その理由は両者の処理にかかる計算量のオーダーの違いにある。つまり前者の文脈自由文法の統語解析が入力文の長さの多項式オーダーで済むのに対し、後者の意味に関する制約の処理は一般に素性構造の単一化を必要とし、これは最悪の場合入力の素性構造の大きさの指数オーダーの計算量を必要とする。逆にいえばたとえ意味的な制約の処理でも少ない計算量で処理できるものについては統語的制約より先に処理した方が効率がよいということになるが、素性構造の単一化の計算量は入力の構造に強く依存するので、どの制約を先に処理すべきかをあらかじめ決めておくことはできず、状況または文脈に応じて処理の順序を変える必要が生じる。対話システムにおいても多様な制約を柔軟に用いることが必要とされるのは同様の理由による。この問題に対処するために従来は専ら「手続き的アプローチ」がとられてきた。すなわち「このような文脈に対してはこの制約を優先的に処理せよ」というヒューリスティクスを多数用意しておき、これらに従って制御を行なうという方法である。

　一方、大規模な自然言語処理システムが構築されるようになった近年において重視されているもう一つの要求として「拡張性(scalability)」が挙げられる。制約をものとものとの間の関係を規定するものとして論理式で表現することにすると、文脈を明示的に数え上げて各文脈においてどの制約をどのように用いるかをあらかじめ決めるためには、制約全体でn個の変数を含んでいたとすると、少なくとも変数が具体化されているかいないかの区別は必要であるから、O(2ⁿ)個の条件判断が必要である。すなわち文脈の数は制約の数に対して指数関数的に増大するので、手続き的アプローチは小規模システムでは有効であるが大規模システムの構築のためには不適切であることが分かる。

　本研究では、列挙された文脈ごとに推論を制御するのではなく、各制約に確率を割り当て、エントロピー最小化・期待効用最大化といった一般的た原理に基づいて制御するアプローチをとる。具体的には、まずHorn節で書かれたプログラムに対して各節に基本確率とよばれる定数を割り当て、ゴールに相当する節(先頭節という)を導出するのに用いた節の基本確率の積を、その先頭節の確率と定義する。先頭節からトップダウンに導出を試みた時に、導出に使われた節(のインスタンス)の集合をその先頭節に対する説明とよぶ。例えば、先頭節←p(X)∧q(X).およびプログラム1.p(a).,2.p(X)←q(X).,3.q(a).に対して{←p(X)∧q(X).},{←p(a)∧q(a).,p(a).},{←p(a)∧q(a).,p(a)←q(a).,q(a).}などは先頭節に対する説明である。説明に対しても導出の場合と同様に確率を定義する。この例から分かるように一般に一つのリテラルのインスタンスは複数の説明に属すが、それらの説明の確率の総和(もしくは最大値)をそのリテラルのインスタンスの確率と定義する。そしてリテラルのインスタンスの確率(もしくはその単調増加関数)をもって推論の優先度とするのが本研究でのアプローチである。直観的にいえば、探索空間の中で確率の大きな部分と両立する情報に関する処理が優先されることになる。本研究ではまず、このアプローチに沿った計算の枠組である確率的Horn節制約システム(Probabilistic Horn Constraint System(PHOCS))を実装した。先の説明では’説明’を列挙して見せたが、実際にはPHOCSでは制約ネットワークとよばれるグラフとして格納され、構造共有によって漸進的に作られる。さらにリテラルのインスタンスの確率も制約ネットワーク上で推論によって変化した部分についてだけ再計算を行ない、再計算の結果が以前の値と比べてある閾値より大きい場合だけ隣接するリテラルのインスタンスの確率を再計算する、ということを各リテラルのインスタンスの確率が収束するまで繰り返すことで計算量を抑えている。リテラルのインスタンスの確率の定義および推論の優先度の定義にはいくつかバリエーションがあるが、意味表現を含んだ構文解析および文生成に対して応用することで本アプローチの有効性を実証するとともにこれらのバリエーションの比較検討も行なった。

　本論文は、以下に示す8章からなる。論文の目的は、統語論・意味論・語用論などのさまざまな制約を柔軟に用いる自然言語処理システムを構成する基本的な手法を確立することであり、「制御に関する多数のヒューリスティクスをあらかじめ用意しておく」という従来の手続き的アプローチに代り、「制約によってシステムを宣言的に記述し、確率を使った一般的な原理に基づいて処理の制御を行う」という新しいアプローチを提案している。その手法は斬新であり、また、手法の有効性を示すための十分な計算機実験も行なっている。

　第一章では、問題の背景および従来のアプローチの問題点を指摘し、制約に基づいたシステムの設計について大まかに説明している。まず具体的な対話例を挙げて必要とされる制約をいくつか列挙し、自然言語対話システムに求められている二つの要因、すなわち「柔軟性flexibility」と「拡張性scalability」について説明する。次に自然言語対話システムのアーキテクチャとして、比較的頻繁に採用されている"pipeline architecture"と、古典的な"Blackboard architecture"の二つを取り上げ、それらの問題点の指摘を行なっている。すなわち前者に対しては柔軟性が欠ている点、後者に関しては枠組み自身はよいが実装上の都合で拡張性が損なわれている点をそれぞれ挙げている。

　第二章では、本研究で提案する計算枠組み「確率的Horn節制約システムProbabilistic Horn Constraints System」について説明している。提案された枠組みはHorn節で書かれたプログラムに対して各節に基本確率とよばれる定数を割り当て、ゴールに相当する節(先頭節という)を導出するのに用いた節の基本確率の積を、その先頭節の確率と定義するものである。先頭節からトップダウンに導出を試みた時に、導出に使われた節(のインスタンス)の集合をその先頭節に対する説明とよび、。説明に対しても導出の場合と同様に基本確率の積として確率を定義している。一般に一つのリテラルのインスタンスは複数の説明に属すことになるが、それらの説明の確率の総和(もしくは最大値)をそのリテラルのインスタンスの確率と定義している。そしてリテラルのインスタンスの確率(もしくはその単調増加関数)をもって推論の優先度とする。直観的には、探索空間の中で確率の大きな部分と両立する情報に関する処理を優先するというのが、基本的なアイデアである。また、処理の組合せ的な爆発を防ぐために、説明を制約ネットワークとよばれるグラフとして格納し、構造共有によって余分な処理を避ける枠組となっている。

　第三章では、確率的Horn節制約システムに対して五つの制御方法を適用した比較実験の結果が示されている。五つの制御方法とは、1.複数の説明に属するリテラルのインスタンスの確率をそれらの確率の和とする(summation)、2.それらの最大値とする(viterbi)、3.確率そのものを優先度とするのではなく、確率にC^#fl(ただし、Cは0<C<1なる定数、#flはそのリテラルのインスタンスが属するすべての説明中で未処理の部分の個数)をかけたものを優先度とする(non-prob)、4.特に優先度を設けず、queueの先頭から処理していく(depth-first)、5.ランダムに処理する(random)、である。取り上げられた例題は、動詞・目的語の後ろに来た前置詞句の係り先に曖昧性を含んだ文を解祈するもので、入力文から予想された方の解およびすべての解を見つけるまでの推論ステップ数が比較されている。その結果、summationがdepth-firstよりも平均4.4%少ないステップ数で予想された解を見つけ、viterbiとnon-probはdepth-firstよりも平均0.66%少ないステップ数ですべての解が見つけられたという結果を得ている。

　第四章では、第二章で説明した枠組みのうち、記号的な部分に関して形式的な定義を行い、提案する枠組みは「推論によって元々プログラムが潜在的に持っていた説明を捨てることがない(弱い意味での健全性)」および「矛盾を含む説明は推論によって必ず除去される(完全性)」の二つの理論的な結果を示している。

　第五章では、節に割り当てるべき基本確率をコーパスから自動的に学習するためのアルゴリズムについて説明がなされている。まず、確率的文脈自由文法や確率的木文法などの学習アルゴリズムには1.与えられた文の解析に寄与するすべての部分解析木をテーブルの形で求め、2.このテーブルを元に、文法中の書き換え規則の確率を推定する、という共通の機構が用いられていることを指摘。そして、前者を第二章で説明した推論によって構成し、後者を誤差逆伝搬で用いられている手法を元に、改めてExpectation Maximizationアルゴリズムから導出し直すことで、確率的Horn節制約システムでの学習アルゴリズムを求めている。このアルゴリズムの利点が、補強項を含んだ文法の学習が可能であること、文以外の要素、例えば意味表現などを含んだコーパスが利用可能になることを指摘している。

　第六章では、第五章で説明した学習アルゴリズムの評価実験の結果が示されている。第三章と同じ問題について、実際にコーパスから基本確率を学習させているす。具体的には50文からなるコーパスで学習にかかる計算コストと得られた基本確率の質を調べ、反復計算の回数によって計った計算コストがリテラル数にほぼ比例して増大すること、および対数尤度によって計った学習結果の質がリテラル数にほぼ比例して低下することが確かめられている。これは、一般にリテラル数は一文あたりの曖昧性の数とコーパスのサイズに比例することから、妥当な結果であるといえる。

　第七章では、先行する研究との比較が行なわれている。確率的推論の枠組みとしてShapiroのPrologの拡張、Marker PassingおよびCost Based Reasoning、Bayesian Network、PooleのProbabilistic Horn Abduction、およびFuzzy logicをを取り上げ、今回提案された枠組が、これらの先行研究の一般化になっていることを指摘している。

　第八章では、結論と今後の課題がまとめられている。特に、本年度発表された論文で、Abneyらが、「規則の適用に依存関係がある場合、それらの規則の確率の積として導出の確率を定義するのは不適切である」ことを指摘しており、今回の研究においても、確率に関する部分の定式化を改良することが今後の課題となること、また、様相論理や素姓構造に基づいた文法を扱うために記述力を高める必要があることを指摘している。

　なお、本論文の2章は、電子技術総合研究所橋田浩一氏との共同研究、また、3章、4章は、本学米澤明憲教授との共同研究であるが、論文提出者が主体となって分析、検証を行なったもので、論文提出書の寄与が十分であると判断する。