Loading...
Please wait, while we are loading the content...
Similar Documents
Exact Learning Boolean Functions via the Monotone Theory (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bshouty, Nader H. |
| Abstract | 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) ... |
| File Format | |
| Journal | Information and Computation |
| Journal | INFORMATION AND COMPUTATION |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Equivalent Formula Boolean Function Membership Query Decision Tree Main Open Problem Monotone Theory Machine Learning Disjunctive Normal Form General Line Output Hypothesis Conjunctive Normal Form Minimal Dnf Size Minimal Cnf Size Unrestricted Equivalence Queires Equivalence Query Minimum Number Polynomial Time Exact Learning Boolean Function |
| Content Type | Text |
