Algorithmic research on computational learning and teaching

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

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.