On learning read-k-satisfy-j DNF

Howard Aizenstein; Avrim Blum; Roni Khardon; Eyal Kushilevitz; Leonard Pitt; Dan Roth

doi:10.1137/S0097539794274398

On learning read-k-satisfy-j DNF

Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth

Research output: Contribution to journal › Article › peer-review

Abstract

We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for k · j = O(log n/log log n), where n is the number of input variables.

Original language	English (US)
Pages (from-to)	1515-1530
Number of pages	16
Journal	SIAM Journal on Computing
Volume	27
Issue number	6
DOIs	https://doi.org/10.1137/S0097539794274398
State	Published - Dec 1998
Externally published	Yes

Keywords

Computational learning theory
DNF
Decision trees
Learning

ASJC Scopus subject areas

Computer Science(all)
Mathematics(all)

Online availability

10.1137/S0097539794274398

Library availability

Discover UIUC Full Text

Cite this

@article{e6c9b59ae6424ea6892302fb374284aa,

title = "On learning read-k-satisfy-j DNF",

abstract = "We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for k · j = O(log n/log log n), where n is the number of input variables.",

keywords = "Computational learning theory, DNF, Decision trees, Learning",

author = "Howard Aizenstein and Avrim Blum and Roni Khardon and Eyal Kushilevitz and Leonard Pitt and Dan Roth",

year = "1998",

month = dec,

doi = "10.1137/S0097539794274398",

language = "English (US)",

volume = "27",

pages = "1515--1530",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

T1 - On learning read-k-satisfy-j DNF

AU - Aizenstein, Howard

AU - Blum, Avrim

AU - Khardon, Roni

AU - Kushilevitz, Eyal

AU - Pitt, Leonard

AU - Roth, Dan

PY - 1998/12

Y1 - 1998/12

N2 - We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for k · j = O(log n/log log n), where n is the number of input variables.

AB - We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for k · j = O(log n/log log n), where n is the number of input variables.

KW - Computational learning theory

KW - DNF

KW - Decision trees

KW - Learning

UR - http://www.scopus.com/inward/record.url?scp=0032312992&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032312992&partnerID=8YFLogxK

U2 - 10.1137/S0097539794274398

DO - 10.1137/S0097539794274398

M3 - Article

AN - SCOPUS:0032312992

SN - 0097-5397

VL - 27

SP - 1515

EP - 1530

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

On learning read-k-satisfy-j DNF

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this