論文

査読有り
2017年3月

Learning concepts and their unions from positive data with refinement operators

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
  • Seishi Ouchi
  • ,
  • Tomohiko Okayama
  • ,
  • Keisuke Otaki
  • ,
  • Ryo Yoshinaka
  • ,
  • Akihiro Yamamoto

79
1-3
開始ページ
181
終了ページ
203
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1007/s10472-015-9458-6
出版者・発行元
SPRINGER

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.

リンク情報
DOI
https://doi.org/10.1007/s10472-015-9458-6
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000392374300009&DestApp=WOS_CPL
ID情報
  • DOI : 10.1007/s10472-015-9458-6
  • ISSN : 1012-2443
  • eISSN : 1573-7470
  • Web of Science ID : WOS:000392374300009

エクスポート
BibTeX RIS