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 DNF size, its minimal CNF 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 queires. The hypotheses to the equivalence queries and the output hypotheses are depth 3 formulas. 1 Introduction One of the main open problems in machine learning is whether boolean functions are learnable from membership and equivalence queries in polynomial time in the number of variables and their (disjunctive normal form) DNF sizes (the minimum number of terms in an equivalent formula in Disjunctive Normal Form). A more general line of research is whether all boolean functions are learnable in polynomial time using other representations, such as (conjunctive normal form) ...