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

概率近似学习理论与计算教学

• 批准号: 07780334
• 负责人: 篠原 歩
• 金额: $ 0.7万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780334/
• 关键词: PAC学習; 学習アルゴリズム; 例からの学習; ゲノム情報

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

关于PAC可学习性，我们提出了“反驳性PAC可学习性”，它包括整个假设空间的可反驳性，并分析了学习所需的数据数量和计算时间，结果我们发现了以下知识： 1. 阐明。反驳学习所需的数据数量该结果表明，就输入参数的多项式大小而言，传统PAC学习模型中所需的数据数量和反驳学习模型中所需的数据数量是相同的。2.概念类别是多项式的。构建一种算法，为反驳学习在时间上成为可能提供充分必要条件。该结果有助于表征多项式时间内反驳学习的可能性，也为寻找在多项式时间内反驳学习可能的概念类提供线索。此外，多项式时间在实际应用中也得到广泛应用。关于有序二元决策图（OBDD）的学习可能性，我们还阐明了PAC学习可能性。基于这些结果，我们并行运行BONSAI，一个来自基因组信息数据的知识获取系统，用于知识获取。我们将 Garden 系统投入生产并进行了计算机实验。另一方面，对于构成这些信息处理技术基础的字符串匹配问题，我们研究了模式和文本的压缩数据，而没有显式扩展它们。还成功开发了一种可以直接匹配字符串的多项式时间算法。这是一项成果，预计将来会向各个方向扩展。

项目成果

M.Karpinski: "Pattern-matching for strings with short descriptions" Proc.6th Symp.on Combinatorial Pattern Matching(LNCS). 937. 205-214 (1995)

M.Karpinski：“带有简短描述的字符串的模式匹配”Proc.6th Symp.on 组合模式匹配（LNCS）。

松本哲志: "反駁PAC学習可能性" 人工知能学会全国大会(第9回)論文集. 81-84 (1995)

Satoshi Matsumoto：“反驳 PAC 可学习性”日本人工智能学会第九届全国会议论文集 81-84 (1995)。

平田耕一: "順序付き二分決定グラフの学習可能性" 信学技法COMP95. 61. 37-44 (1995)

Koichi Hirata：“有序二元决策图的学习性”IEICE Techniques COMP95 61. 37-44 (1995)。

T.Shoudai: "BONSAI Garden:parallel knowledge Discovery system for amino acid sequences" Proc.3rd.Int.Conf.Intelligent Systems for Molecular Biology. 359-366 (1995)

T.Shoudai：“BONSAI Garden：氨基酸序列的并行知识发现系统”Proc.3rd.Int.Conf.Intelligent Systems for Molebiology。

篠原歩: "短縮記述された文字列上での多項式時間照合アルゴリズム" 情報学基礎論研究会資料. 38-4. 25-32 (1995)

Ayumu Shinohara：“缩写字符串的多项式时间匹配算法”信息学基础研究组材料 38-4（1995）。