权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Algorithmic research on computational learning and teaching

计算学习与教学的算法研究

基本信息

批准号：
02680031
负责人：
MIYANO Satoru
金额：
$ 1.15万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1990
资助国家：
日本
起止时间：
1990 至 1991
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-02680031/
关键词：
Computational learning Teaching theory Analogical reasoning Machine learning Parallel algorithm Decision tree

项目摘要

This research concentrates on computational learning from the view point of algorithmic teaching. We introduced the notion of teachability with which we established a relationship between the learnability and teachability. We obtained some results on the complexity issues of a teacher in relation to learning. We also considered the analogical reasoning in relation to learning. We showed that NP-hard aspect appears in analogicaj reasoning. In our framework, the set cover problem proved to be an important issue for finding keys in teaching. For this problem we devised a parallel algorithm which solves the minimal set cover problem. We also investigated elementary formal systems with respect to polynomial-time learnability. We identified some important and useful subclasses of elementary formal systems which are polynomial-time learnable. Based on these theoretical researches, we developed a machine learning system which employs decision trees over regular patterns. This system finds important keys from randomly chosen samples which may explain the given samples reasonably. In addition to theoretical analysis of our system, experiments show that this machine learning system exhibited quite successful results. In order to find keys in teaching, we also developed a system based on elementary formal systems which employs the approximation algorithm for minimum set cover problem. Comparison of these two systems showed that the former is faster and efficient than the latter. But, by theoretical reasons, the latter system can cope with problems with larger variety.

本研究从算法教学的角度对计算学习进行了研究。我们引入了可教性的概念，用它来建立可学性和可教性之间的关系。我们在教师与学习有关的复杂性问题上得到了一些结果。我们还考虑了与学习有关的类比推理。我们证明了在类比推理中出现了NP-难方面。在我们的框架中，集合覆盖问题被证明是教学中寻找关键字的一个重要问题。针对这个问题，我们设计了一个并行算法来解决最小集覆盖问题。我们还研究了关于多项式时间可学习性的初等形式系统。我们确定了初等形式系统的一些重要和有用的子类，它们是多项式时间可学习的。在这些理论研究的基础上，我们开发了一个基于规则模式的决策树机器学习系统。该系统从随机选择的样本中找出重要的密钥，可以合理地解释给定的样本。除了对我们的系统进行理论分析外，实验表明，该机器学习系统取得了相当成功的结果。为了在教学中寻找关键问题，我们还开发了一个基于初等形式系统的系统，该系统采用了最小集合覆盖问题的近似算法。两种系统的比较表明，前者比后者更快、更高效。但是，由于理论上的原因，后一种制度可以应对种类更多的问题。