On Learning Read-k-Satisfy-j DNF
Lists
Only you see this
Abstract
We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k•j=O(logn/loglogn). Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size > 2W(n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].
BibTeX
@inproceedings{blum1994learning,
author = {Avrim Blum and Roni Khardon and Eyal Kushilevitz and Leonard Pitt and Dan Roth},
title = {{On Learning Read-k-Satisfy-j DNF}},
booktitle = {Conference on Learning Theory},
year = {1994},
doi = {10.1145/180139.181051},
}Loading related content...