|
Given
a Boolean formula that is not quite right, how does one fix it?
That is, if a given formula differs from an unknown target
formula, what is the complexity of revising the given formula?
The tools available for determining the revisions are queries to
membership and equivalence oracles, namely, questions of the
form: "Is this an instance of the target formula," and
``Is this hypothesis equivalent to the target formula?" In
the latter case, if the answer is ``No," the oracle returns
an instance that is true for exactly one of the hypothesis and
the target.
Others have done considerable empirical work on theory revision:
build good ad hoc systems, and empirically measure their
performance on various testbeds. In this talk, I present
highlights from my line of work on a learning theory approach to
theory revision, presenting algorithms with provable bounds on
resource consumption. Portions of this work have appeared
or will appear in such conferences as the ACM Computational
Learning Theory Conference (COLT), the ACM Symposium on the
Theory of Computing (STOC), and such journals as Machine
Learning, Artificial Intelligence, and the Journal of Machine
Learning Research. This is joint work with one to
three of Judy Goldsmith (U. Kentucky), Balazs Szorenyi (U.
Szeged, Hungary), and Gyorgy Turan (UIC).
|