Algorithmic research on computational learning and teaching

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

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.