ECCC-Report TR03-039https://eccc.weizmann.ac.il/report/2003/039Comments and Revisions published for TR03-039en-usFri, 06 Jun 2003 05:42:20 +0300
Paper TR03-039
| Theory Revision with Queries: Horn, Read-once, and Parity Formulas |
Judy Goldsmith,
Robert H. Sloan,
Balázs Szörényi,
György Turán
https://eccc.weizmann.ac.il/report/2003/039A 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.
Fri, 06 Jun 2003 05:42:20 +0300https://eccc.weizmann.ac.il/report/2003/039