TY - JOUR
T1 - Learning monotone log-term DNF formulas under the uniform distribution
AU - Sakai, Y.
AU - Maruoka, A.
PY - 2000
Y1 - 2000
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0034406593&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034406593&partnerID=8YFLogxK
U2 - 10.1007/s002249910002
DO - 10.1007/s002249910002
M3 - Article
AN - SCOPUS:0034406593
SN - 1432-4350
VL - 33
SP - 17
EP - 33
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 1
ER -