Learning concepts and their unions from positive data with refinement operators

详细信息    查看全文

• 作者：Seishi Ouchi ; Tomohiko Okayama…
• 关键词：Identification in the limit from positive data ; Refinement operator ; Unions of concepts
• 刊名：Annals of Mathematics and Artificial Intelligence
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：79
• 期：1-3
• 页码：181-203
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence (incl. Robotics); Mathematics, general; Computer Science, general; Complex Systems;
• 出版者：Springer International Publishing
• ISSN：1573-7470
• 卷排序：79

文摘

This paper is concerned with a sufficient condition under which a concept class is learnable in Gold’s classical model of identification in the limit from positive data. The standard principle of learning algorithms working under this model is called the MINL strategy, which is to conjecture a hypothesis representing a minimal concept among the ones consistent with the given positive data. The minimality of a concept is defined with respect to the set-inclusion relation – the strategy is semantics-based. On the other hand, refinement operators have been developed in the field of learning logic programs, where a learner constructs logic programs as hypotheses consistent with given logical formulae. Refinement operators have syntax-based definitions – they are defined based on inference rules in first-order logic. This paper investigates the relation between the MINL strategy and refinement operators in inductive inference. We first show that if a hypothesis space admits a refinement operator with certain properties, the concept class will be learnable by an algorithm based on the MINL strategy. We then present an additional condition that ensures the learnability of the class of unbounded finite unions of concepts. Furthermore, we show that under certain assumptions a learning algorithm runs in polynomial time.