首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Learning k  -Term Monotone Boolean Formulae
  • 作者:Yoshifumi SAKAI ; Akira MARUOKA
  • 期刊名称:Interdisciplinary Information Sciences
  • 印刷版ISSN:1340-9050
  • 电子版ISSN:1347-6157
  • 出版年度:1997
  • 卷号:3
  • 期号:2
  • 页码:71-80
  • DOI:10.4036/iis.1997.71
  • 出版社:The Editorial Committee of the Interdisciplinary Information Sciences
  • 摘要:

    Valiant introduced a computational model of learning by examples, and gave the precise definition of polynominal time learnability based on the model. Since then, much effort has been devoted to characterize learnable classes of concepts on this model. Among such learnable classes is the one, denoted monotone k  -term DNF, consisting of monotone disjunctive normal form formulae with at most k terms. So far it has been shown [6], [8] that for fixed k , monotone k  -term DNF is learnable under the assumption that positive examples are drawn according to the uniform distribution. In this paper we introduce a class of probabilistic distributions, called smooth distributions, which is generalization of all the distribution classes which appeared in literature as the ones for specific distributiion setting: A smooth distribution is the one such that a ratio of the probabilities of any two examples with Hamming distance 1 is bounded from below by the inverse of some polynomial. It is proved that monotone k  -term DNF is learnable even if positive examples are drawn according to smooth distributions. From this result it follows the learnability of monotone k  -term DNF under specific distribution dealt with in literature such as product distributions [7] and q  -bounded distributions [2].

  • 关键词:learning algorithm; learning from examples; PAC learning; learnability of monotone k-term DNF; smooth distribution
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有