確率論的近似学習と計算論的教示の理論

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

PAC学習可能性に関しては,仮説空間全体の反駁可能性を含めた「反駁PAC学習可能性」を提案し,学習に必要なデータの個数と計算時間についての解析を行った結果,次のような知見が得られた.1.反駁学習に必要なデータの個数の解明.この結果により,従来のPAC学習モデルにおいて必要とされるデータの個数と,反駁学習モデルにおいて必要とされるデータの個数は,入力されるパラメーターの多項式サイズという点では,同じであることを示した.2.概念クラスが多項式時間で反駁学習可能となるための必要十分条件となるアルゴリズムの構築.この結果は,多項式時間反駁学習可能性の特徴付けに役立ち,さらには,多項式時間で反駁学習可能となる概念クラスを見つけ出す手がかりとなる.また,実用的に広く用いられている,順序付き二分決定グラフ(OBDD)の学習可能性についても,そのPAC学習可能性を解明した.これらの結果をふまえて,ゲノム情報データからの知識獲得システムBONSAIを並列に走らせて知識獲得を行うBONSAI Gardenシステムを実働化し,計算機実験を行った.一方,これらの情報処理技術の根幹をなす,文字列照合問題について,パタンもテキストも両方とも圧縮されたデータについて,それらを陽に展開することなく,そのまま文字列の照合を行う多項式時間アルゴリズムの開発にも成功した.これは,今後,さらにさまざまな方向へ拡張が期待される成果である.