Exact Learning Boolean Functions via the Monotone Theory

We study the learnability of boolean functions from membership and equivalence queries. We develop the Monotone Theory that proves (1) Any boolean function is learnable in polynomial time in its minimal disjunctive normal form size, its minimal conjunctive normal form size, and the number of variables n. In particular, (2) Decision trees are learnable. Our algorithms are in the model of exact learning with membership queries and unrestricted equivalence queries. The hypotheses to the equivalence queries and the output hypotheses are depth 3 formulas.

Authors

• N.H. Bshouty

Keywords

No keywords are indexed for this paper.