Title :
Polynomial-sample learnability about distance-0 and 1 DNF formulas
Author :
Yanagi, S. ; Kudo, M. ; Shimbo, M.
Author_Institution :
Graduate Sch. of Eng., Hokkaido Univ., Sapporo, Japan
Abstract :
We show a positive result for learnability of all arbitrary disjunctive normal form (DNF) formula. We propose a learning algorithm that requires a polynomial number of examples in the size of an unknown formula under probably approximately correct (PAC) learning with a subset query, while it is not polynomial time. Our algorithm is based on Valiant´s (1984) approach with respect to monotone-DNF
Keywords :
learning (artificial intelligence); probability; set theory; PAC learning; computational learning theory; concept learning; disjunctive normal form; learning algorithm; polynomial-sample learnability; probability; probably approximately correct learning; subset query; Intelligent systems; Polynomials;
Conference_Titel :
Knowledge-Based Intelligent Electronic Systems, 1998. Proceedings KES '98. 1998 Second International Conference on
Conference_Location :
Adelaide, SA
Print_ISBN :
0-7803-4316-6
DOI :
10.1109/KES.1998.725916
