𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Learning Read-k-Satisfy-j DNF

✍ Scribed by Aizenstein, Howard; Blum, Avrim; Khardon, Roni; Kushilevitz, Eyal; Pitt, Leonard; Roth, Dan

Book ID
118178150
Publisher
Society for Industrial and Applied Mathematics
Year
1998
Tongue
English
Weight
331 KB
Volume
27
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Fast Learning of k-Term DNF Formulas wit
Fast Learning of k-Term DNF Formulas with Queries
✍ A. Blum; S. Rudich πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 649 KB

This paper presents an algorithm that uses equivalence and membership queries to learn the class of \(k\)-term DNF formulas in time \(n \cdot 2^{o(k)}\), where \(n\) is the number of input variables. This improves upon previous \(O\left(n^{k}\right)\) bounds and allows one to learn DNF formulas of \

P-sufficient statistics for PAC learning
P-sufficient statistics for PAC learning k-term-DNF formulas through enumeration
✍ B. Apolloni; C. Gentile πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 271 KB

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 di