Author name cluster

N.H. Bshouty

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

1 paper

1 author row

I&C Journal 1995 Journal Article

Exact Learning Boolean Functions via the Monotone Theory

N.H. Bshouty

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.

Details DOI