Theory revision with queries: DNF formulas

Judy Goldsmith; Robert H. Sloan; György Turán

doi:10.1023/A:1013641821190

Theory revision with queries: DNF formulas

Judy Goldsmith
, Robert H. Sloan
, György Turán

Producción científica: Article › revisión exhaustiva

7 Citas (Scopus)

Resumen

The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for three classes of disjunctive normal form expressions: monotone k-DNF, monotone m-term DNF and unate two-term DNF. A negative result shows that some monotone DNF formulas are hard to revise.

Idioma original	English
Páginas (desde-hasta)	257-295
Número de páginas	39
Publicación	Machine Learning
Volumen	47
N.º	2-3
DOI	https://doi.org/10.1023/A:1013641821190
Estado	Published - may 2002

Nota bibliográfica

Funding Information:
∗Partially supported by NSF grant CCR-9610348; work done while visiting the Dept. of EECS at the University of Illinois at Chicago and the Dept. of Computer Science at Boston University. †Partially supported by NSF grant CCR-9800070. ∗∗Partially supported by NSF grant CCR-9800070, and OTKA T-25721.

Financiación

∗Partially supported by NSF grant CCR-9610348; work done while visiting the Dept. of EECS at the University of Illinois at Chicago and the Dept. of Computer Science at Boston University. †Partially supported by NSF grant CCR-9800070. ∗∗Partially supported by NSF grant CCR-9800070, and OTKA T-25721.

Financiadores	Número del financiador
National Science Foundation Arctic Social Science Program	CCR-9610348
Boston University School of Public Health/Boston University Medical Campus	OTKA T-25721, CCR-9800070

ASJC Scopus subject areas

Software
Artificial Intelligence

Acceder al documento

10.1023/A:1013641821190

Otros archivos y enlaces

Citar esto

@article{8a1865c9e1784496ae6c24aa7c63989e,

title = "Theory revision with queries: DNF formulas",

abstract = "The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for three classes of disjunctive normal form expressions: monotone k-DNF, monotone m-term DNF and unate two-term DNF. A negative result shows that some monotone DNF formulas are hard to revise.",

keywords = "Boolean function learning, Computational learning theory, Disjunctive normal form, Knowledge revision, Query learning, Theory revision",

author = "Judy Goldsmith and Sloan, \{Robert H.\} and Gy{\"o}rgy Tur{\'a}n",

note = "Funding Information: ∗Partially supported by NSF grant CCR-9610348; work done while visiting the Dept. of EECS at the University of Illinois at Chicago and the Dept. of Computer Science at Boston University. †Partially supported by NSF grant CCR-9800070. ∗∗Partially supported by NSF grant CCR-9800070, and OTKA T-25721.",

year = "2002",

month = may,

doi = "10.1023/A:1013641821190",

language = "English",

volume = "47",

pages = "257--295",

number = "2-3",

}

TY - JOUR

T1 - Theory revision with queries

T2 - DNF formulas

AU - Goldsmith, Judy

AU - Sloan, Robert H.

AU - Turán, György

N1 - Funding Information: ∗Partially supported by NSF grant CCR-9610348; work done while visiting the Dept. of EECS at the University of Illinois at Chicago and the Dept. of Computer Science at Boston University. †Partially supported by NSF grant CCR-9800070. ∗∗Partially supported by NSF grant CCR-9800070, and OTKA T-25721.

PY - 2002/5

Y1 - 2002/5

N2 - The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for three classes of disjunctive normal form expressions: monotone k-DNF, monotone m-term DNF and unate two-term DNF. A negative result shows that some monotone DNF formulas are hard to revise.

AB - The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for three classes of disjunctive normal form expressions: monotone k-DNF, monotone m-term DNF and unate two-term DNF. A negative result shows that some monotone DNF formulas are hard to revise.

KW - Boolean function learning

KW - Computational learning theory

KW - Disjunctive normal form

KW - Knowledge revision

KW - Query learning

KW - Theory revision

UR - https://www.scopus.com/pages/publications/0036568019

UR - https://www.scopus.com/pages/publications/0036568019#tab=citedBy

U2 - 10.1023/A:1013641821190

DO - 10.1023/A:1013641821190

M3 - Article

AN - SCOPUS:0036568019

SN - 0885-6125

VL - 47

SP - 257

EP - 295

JO - Machine Learning

JF - Machine Learning

IS - 2-3

ER -

Theory revision with queries: DNF formulas

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto