Learning Monotone Log-Term DNF Formulas under the Uniform Distribution |
| |
| Authors: | Y. Sakai A. Maruoka |
| |
| Affiliation: | (1) Department of Information and Computer Sciences, Faculty of Engineering, Toyo University, 2100 Kujirai, Kawagoe 350-8585, Japan sakai@cs.toyo.ac.jp , JP;(2) Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan maruoka@ecei.tohoku.ac.jp, JP |
| |
| Abstract: | Based on the uniform distribution PAC learning model, the learnability for the class of monotone disjunctive normal form formulas with at most O (log n ) terms, denoted O (log n )-term MDNF, is investigated. Using the technique of restriction, an algorithm that learns O (log n )-term MDNF by examples in polynomial time is given. Received February 2, 1998, and in revised form April 8, 1999, and in final form June 30, 1999. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
