推論による学習の基礎研究

本研究の目的は、学習の様々な局面で活用される各種の推論および学習方式そのものについて、理論的に定式化し、それを計算可能なレベルまで導き、さらに実用レベルまで効率化することである。この目的を達成するために、本年度は次の各点に重点を置いて基礎となる重要な成果を得た。(1)帰納推論による言語の学習のための統一的枠組み。SmullyanによるEFS(Elementary Formal System)は、形式言語の生成だけでなく受理機構としても有用であることを発見し、形式言語理論との関連を明らかにし、さらに文字列を対象にした論理プログラムとしても位置付けられることを示し、形式言語の学習の統一的枠組みとして最適であることを示した。この枠組みにより形式言語理論を中心にした理論計算機科学の種々の成果を帰納推論に取り込むことおよびホーン節を対象にしたモデル推論と言語の帰納推論とを直接結合させることに成功した。(2)正データからの帰納推論。正データからの帰納推論は能力が劣ると信じられてきたが、上記EFSを使って、実は十分に強力であることを証明した。この成果によって、正データからの学習の有用性が明らかになったので、従来の常識を再検討することが必要となった。(3)アルゴリズム論的教示の理論。Valiantに始まるPAC学習の枠組みで、学習における教示の役割りについて理論的に明らかにして、教示の数学的理論の基礎を築いた。(4)類推における負の事実と抽象化の利用。決定則(determination)による類推とルーツ変換による類推の融合をはかり、同時に負の事実を妥当性のチェックに使う新しい類推の方式を開発した。また、抽象化の手法を普通のH空間や階層構造に適用した新しい類推の方式を提案した。これらの研究によって意味を考慮した類推理論への道が拓けた。

本研究の目的は、学習の様々な局面で活用される各種の推論および学習方式そのものについて、理論的に定式化し、それを計算可能なレベルまで導き、さらに実用レベルまで効率化することである。この目的を達成するために、本年度は次の各点に重点を置いて基礎となる重要な成果を得た。(1)帰納推論による言語の学習のための統一的枠組み。SmullyanによるEFS(Elementary Formal System)は、形式言語の生成だけでなく受理機構としても有用であることを発見し、形式言語理論との関連を明らかにし、さらに文字列を対象にした論理プログラムとしても位置付けられることを示し、形式言語の学習の統一的枠組みとして最適であることを示した。この枠組みにより形式言語理論を中心にした理論計算機科学の種々の成果を帰納推論に取り込むことおよびホーン節を対象にしたモデル推論と言語の帰納推論とを直接結合させることに成功した。(2)正データからの帰納推論。正データからの帰納推論は能力が劣ると信じられてきたが、上記EFSを使って、実は十分に強力であることを証明した。この成果によって、正データからの学習の有用性が明らかになったので、従来の常識を再検討することが必要となった。(3)アルゴリズム論的教示の理論。Valiantに始まるPAC学習の枠組みで、学習における教示の役割りについて理論的に明らかにして、教示の数学的理論の基礎を築いた。(4)類推における負の事実と抽象化の利用。決定則(determination)による類推とルーツ変換による類推の融合をはかり、同時に負の事実を妥当性のチェックに使う新しい類推の方式を開発した。また、抽象化の手法を普通のH空間や階層構造に適用した新しい類推の方式を提案した。これらの研究によって意味を考慮した類推理論への道が拓けた。