計算論的学習理論に基づくプログラム部品の再利用難易度の研究

点击翻译按钮获取中文摘要

本研究の目的は、既知のプログラム部品から新たなプログラムを作成する過程を、背景知識を用いた学習過程とみなすことにより、プログラム部品の再利用の難易度を計算論的学習理論と論理プログラミングの立場から明らかにすることにあった。論理プログラミングを用いた学習システムでは、プログラムや背景知識を述語で記述せねばならないことが、学習過程を複雑にしていることはすでに知られていた。そこで、本研究では木構造を扱うプログラムを学習対象とし、既知のプログラム部品は木構造から木構造への関数であると仮定した上で研究を開始した。この仮定は多くの結果を産み出すとともに、今後の論理プログラミングを用いた学習システムに関する展望を与えるものとなった。論理プログラミングでは既知のプログラム部品である関数を等式論理を用いて拡張単一化として扱う。計算論的学習理論では、生成すべき新たなプログラムの候補数と、各候補が目的の仕様を満たしているかどうかを検証する計算量の評価が持内となる。そこで、等式論理にいくつかの条件を与えることにより両者の評価を与え、効率的に学習(生成)可能なプログラムのクラスを与えた。その途中で、関数を論理プログラミングで表現すればML言語で用いられる多層型とみなせることに気づき、実際に両者の共通点を示した。そして、型付き論理プログラミングによる学習手法を考案し、その正当性を証明した。また、本研究費で購入したワークステーションを用いて実働システムを構成し、学習アルゴリズムの実装的検証を行ない、計算量上の問題点を整理し、アルゴリズムの改良を行なった。また、型を正則な木関係と見なした場合に既存の学習手法が適用可能であるかどうかを検証し、適用可能な場合の条件を与えることに成功した。本研究を通じて、学習におけるプログラム部品(既知知識)と型理論の関係が非常に重要であることが判明した。そこで今後は型情報を学習に利用する研究を展開してゆく計画である。