P-sufficient statistics for PAC learning k-term-DNF formulas through enumeration
✍ Scribed by B. Apolloni; C. Gentile
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 271 KB
- Volume
- 230
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
Working in the framework of PAC-learning theory, we present special statistics for accomplishing in polynomial time proper learning of DNF boolean formulas having a ÿxed number of monomials. Our statistics turn out to be near su cient for a large family of distribution laws -that we call butter y distributions. We develop a theory of most powerful learning for analyzing the performance of learning algorithms, with particular reference to trade-o s between power and computational costs. Focusing attention on sample and time complexity, we prove that our algorithm works as e ciently as the best algorithms existing in the literature -while the latter only take care of subclasses of our family of distributions.