Efficient learning algorithms based on infomation compression

1.学习过程中的信息压缩和获取机制在PAC学习模型中，学习算法期望通过使用目标的一系列示例来产生近似目标函数的假设。另一方面，引入了称为Occan算法的信息压缩算法的概念，并研究了它与PAC学习算法的关系。研究表明，OCCAM算法可以直接作为PAC学习算法，而PAC学习算法可以修改为随机化的OCCAM算法。通过一个反例说明了PAC学习算法不一定是Occam算法。介绍了自然PAC学习算法需要满足的理性条件，即可保持性和单调性。并且推测，在任何一种…下，PAC学习算法立即变成OCCAM算法还有两个条件。虽然这一猜想到目前为止还没有得到证明，但已经证实在某些技术条件下这一说法是成立的。此外，还介绍了一种信息获取算法的运动，并讨论了它与PAC学习算法和信息压缩算法的关系。析取范式公式的学习在计算学习领域中，判断析取范式公式是否是可学习的形式范例是一个重要的开放问题。得到的主要结果如下：含logn项的单调DNF公式可从正例中学习；新的布尔函数，称为kappa项函数，可从示例中学习。计算复杂性和近似计算学习所需的计算资源取决于其目标的复杂程度。研究了与目标函数计算复杂度有关的布尔复杂度、近似计算、伪随机性等问题。模式匹配中的字符特征提取在用模式匹配的方法实现字符识别时，如何为每个字符模式生成特征向量是关键。从信息压缩的角度出发，研究了用于偏好识别的特征向量定义问题。较少

1. Information compressing and gaining mechanism in learning processIn PAC learning model a learning algorithm is expected to produce a hypothesis that approximates a target function by using a sequence of examples of the target. On the other hand the notion of an information compressing algorithm, called an Occan algorithm, has been introduced and its relation to a PAC learning algorithm has been investigated. It has been shown that an Occam algorithm is immediately a PAC learning algorithm, while a PAC learning algorithm can be modified to obtain a randomized Occam algorithm.We investigate relationship between these types of algorithms. We show that a PAC learning algorithm is not necessarily an Occam algorithm by giving a counter example. Reasonal conditions, called preservability and monotonicity, which natural PAC learning algorithms are expected to satisfy are introduced. And it is conjectured that a PAC learning algorithm becomes immediately an Occam algorithm under any of these … More two conditions. Although the conjecture has not been proved so far, it is verified that the statement holds under some technical conditions. Furthermore, a motion of an information gaining algorithm is introduced and its relation to a PAC learning algorithm and an information compressing algorithm is explored.2. Learning of disjunctive normal form formulaeIn the field of computational learning it is one of the most important open problems to decide whether or not disjunctive normal form (DNF) formulae are learnable form examples. The main results obtained are stated as follows : Monotone DNF formulae with log n terms are learnable from positive examples ; New Boolean functions, called kappa term functions, are learnable from examples.3. Computational complexity and appoximate computationComputational resources needed for learning depend on the complexity of its target. Various issues, such as Boolean complexity, approximate computation, pseudo-randomness, concerning computational complexity of target functions are investigated.4. Extracting character feature on pattern matchingWhen character recognition is implemented by using the method of pattern matching, it is crucial how to make a feature vector for each character pattern. In view of information compression, the problem of defining the feature vectors for precies recognition is investigated. Less