TR03-039 Authors: Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

Publication: 6th June 2003 05:42

Downloads: 1488

Keywords:

A theory, in this context, is a Boolean formula; it is

used to classify instances, or truth assignments. Theories

can model real-world phenomena, and can do so more or less

correctly.

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 Horn formulas and read-once formulas, where revision

operators are restricted to deletions of variables or clauses,

and for parity formulas, where revision operators include

both deletions and additions of variables.

We also show that the query complexity of the read-once revision

algorithm is near-optimal.