Title :
Exact learning via the Monotone theory
Author :
Bshouty, Nader H.
Author_Institution :
Dept. of Comput. Sci., Calgary Univ., Alta., Canada
Abstract :
We study the learnability of concept classes from membership and equivalence queries. We develop the Monotone theory that proves (1) Any boolean function is learnable as decision tree. (2) Any boolean function is either learnable as DNF or as CNF (or both). The first result solves the open problem of the learnability of decision trees and the second result gives more evidence that DNFs are not “very hard” to learn
Keywords :
Boolean functions; learning (artificial intelligence); CNF; DNF; Monotone theory; boolean function; concept classes; decision trees; equivalence queries; exact learning; learnability; membership; Boolean functions; Circuits; Decision trees; Machine learning; Noise measurement; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-4370-6
DOI :
10.1109/SFCS.1993.366857
