正例から形式文法を帰納推論する枠組みが導入されて以来、様々なクラスの学習可能性が考えられてきた。正例からの学習可能であるために文法が満たすべき性質の必要十分条件も与えられている。正例からの学習はもっとも基本的な帰納推論の枠組みであるが、負例や質問などを用いるものに比べて、学習可能なクラスは少ない。例えば正規言語のクラスなど正例からの学習できないことがわかっている。また、たとえ学習可能であることが示せても、効率的な学習アルゴリズムが存在するかどうかは別の問題であり、一般に、言語クラスの豊かさと、学習の効率性の間にはトレードオフが存在すると考えられる。

　近年、正例からの学習の分野において、文脈自由文法の非正則なサブクラスで、効率的に学習可能なクラスが発見されてきた。Very Simple Grammar のクラスや、その拡張である Right-unique Simple Grammar のクラスがそうである。両者はともに Simple Grammar とよばれる文脈自由文法のサブクラスのサブクラスである。これらの効率的学習アルゴリズムに対していろいろな応用を考えることができる。

　そのひとつとして、本論文では強化学習へ応用する方法を提案している。強化学習の理論的な基礎となっている確率モデルはマルコフ決定過程と呼ばれるものである。さらに、観測状態と真の状態が一致しないような場合は部分観測マルコフ決定過程と呼ばれており、マルコフ決定過程のクラスはそのサブクラスである。一方で、有限状態マルコフ決定過程にスタックを付与した決定過程を考えたばあい、観測の履歴が真の状態にそのまま対応しないため、履歴からでは、どのような状態とスタックの構造をしているのかは直接推測することはできない。しかし、このような状態とスタックの組は、Right-unique Simple Grammar とみなすことができ、観測の履歴は、Right-unique Simple Language の正例となることがわかる。したがって、Right-unique Simple Grammar の学習アルゴリズムを用いれば、観測の履歴、即ち正例から帰納的にもとの文法、即ち状態とスタックの組を推測することができる。しかし、この場合、言語が等しいだけでは正しい文法を帰納推論としたとすることができず、確率言語の意味で齟齬をきたしえないような文法を出力しなければならない。ここで注意すべきは、毎回の履歴が観測される確率は行動によって左右されるため、行動を抜き考えると、毎回の履歴は独立ではなくなり、行動が多数存在したり連続的だったりした場合、PAC学習などの標準的な枠組みで扱うことは難しいことである。しかし、次に述べる結果を用いれば、そのような確率的な齟齬を除くことが可能である。

　本論文では、形式文法、とくにSimple Grammar に対する確率的一般性を、その文法の生成規則に確率値を割り当てた場合に生成しうる確率言語全ての集合ととらえ、それらの間の包含関係について議論を展開している。より具体的に書くと、文法 A にたいし、それが生成しうる確率言語全ての集合を K(A) とする。ある文法クラス X に属する任意の文法 A, B に対して、K(A)⊂K(C) かつ K(B)⊂K(C) となる 文法 C がクラス Y に存在するとき、クラス X は クラス Y の範囲内で統合可能であると呼ぶことにする。本論文では、Very Simple Grammar のクラスがそれ自身の範囲内で統合可能であるのにたいして、Right-unique Simple Grammar (以下RSG) やSimple Grammar (以下SG) のクラスはそれ自身の範囲内では統合不可能であることを示している。また、新たに、RSG のクラスがそのサブクラスとなる、Unifiable Simple Grammar という文法を定義し、その文法クラスがそれ自身の範囲内で統合可能であることを示すことで、RSG のクラスが SG のクラスの範囲内で統合可能であることが示される。ことことから、RSG の特性を考慮すれば、RSG のクラスが「強い意味」で SG のクラスの範囲内で統合可能であることが示せる。ここでいう「強い意味」とは、任意の RSG A に対して、ある SG B が存在して、Aと言語が等しい任意の RSG C に対して K(C)⊂K(B) となることである。また、実際にそのような B を構成する方法、及び構成するための計算量、及び構成後の文法のサイズを与えている。

　本論文は「形式文法の確率的一般性と応用に関する研究」と題し、形式文法の一種である単純文法の種々のサブクラスについて、生成規則に適用確率を与えた場合に生成しうる確率言語の集合を確率的一般性として捉え、種々の文法の確率的一般性相互間の包含関係と強化学習による効率的学習可能性について論じたもので、5章と付録からなる。

　第1章は「序論」と題し、例から法則性を帰納的に学習する技術、わけても形式文法として表現した法則を学習する技術の意義と研究動向について論じ、本論文に述べる効率的な学習を可能とする枠組の理論的基礎を与える研究の位置づけについて論じている。

　第2章は「準備」と題し、確率的文脈自由文法をマルコフ決定過程として捉える方法を示している。まずマルコフ決定過程と強化学習についての基本的な定義と定理を与え、文脈自由文法のサブクラスである単純文法のサブクラスとそれらの正例からの学習について、次いでマルコフ決定過程として捉えた確率文脈自由文法の性質について論じている。

　第3章は「単純文法の確率的一般性と統合可能性」と題し、種々の確率文法間の関係について論じている。まず文法の確率的一般性を文法の生成規則に確率値を割当てた場合に生成しうる確率言語すべての集合と定義し、ある文法クラスXが文法クラスYの範囲内で統合可能であることを、Xによって記述された複数の確率言語を包含する文法をYによって記述できることと定義する。この定義に基づき、文脈自由文法のサブクラスである単純文法のさらにサブクラスで定義される種々の確率言語について、それらの統合可能性・不可能性について論じている。より具体的には、単純文法のさらにサブクラスであるVery Simple Grammarがそれ自身の範囲内で統合可能であるのに対し、やはり単純文法のサブクラスであるRight-unique Simple Grammarや単純文法自身はそれ自身の範囲内で統合可能ではないことを示している。また、Right-unique Simple Grammarをそれ自身の範囲内で統合可能になるように拡張した Unifiable Simple Grammarを構成し、Right-unique Simple Grammarを確率的一般性を失わない形で正例から学習可能であること及びその具体的方法を示している。

　第4章は「決定過程化した文法と強化学習」と題し、決定過程化した文法の定義とそれについて成立する諸定理を与え、その下での強化学習の拡張方法と、学習の収束性を論じている。さらに、未知の文法について正例からの学習と取り入れながら強化学習する方法を示し、簡単な迷路問題の例の下に、実際に文法の学習や学習結果の統合、最適方策の学習を行なう方法について論じている。

　第5章は「結論」と題し、本論文に述べた研究で得られた知見を総括し、その意義と今後の研究方向について論じている。

　以上これを要するに、本論文ではコンピュータに知的な働きをさせる前提として重要である知識獲得の人手コストを低減するために、実例からの確率的な知識の獲得と利用を可能にする方式のひとつとして有力である文法の学習に関し、その基礎となる文法の統合可能性の枠組を提案、強化学習への応用を通して有効性を示しており、その成果は電子工学上貢献するところが少なくない。

　よって本論文は博士(工学)の論文として合格と認められる。