Abduction and the Dualization Problem*
(invited lecture for DS 2003)
Author: Thomas Eiter
Affiliation: Knowledge-Based Systems Group,
Institute of Information Systems,
Vienna University of Technology, Vienna, Austria
Abstract.
Abduction is a fundamental mode of reasoning which was extensively
studied by C.S. Peirce, who also introduced the term for inference of
explanations for observed phenomena. Abduction has taken on increasing
importance in Artificial Intelligence (AI) and related disciplines,
where it has been recognized as an important principle of common-sense
reasoning. It has applications in many areas of AI and Computer
Science including diagnosis, database updates, planning, natural
language understanding, learning, to number some of them.
In a logic-based setting, abduction can be viewed as the task to find,
given a set of formulas T (the background theory) and a formula Q (the
query), a minimal set of formulas E (an explanation) from a set of
abducibles A such that T union E is satisfiable and logically entails
Q. In many application scenarios T is a propositional Horn theory, Q
is a literal or a conjunction of literals, and the abducibles A are
certain literals of interest. For computing abductive explanations,
well-known early systems such as Poole's Theorist or assumption-based
Truth Maintenance Systems have been devised in the 1980s.
Besides computing some explanation, the problem of generating several
or all explanations has received more attention in the last
years. This is important since often one would like to select one out
of a set of alternative explanations according to a preference or
plausibility relation. In general, a query may have exponentially many
explanations, and thus efficient generation of all explanations may be
understood in terms of polynomial total-time (or output-polynomial
time), i.e., in time polynomial in the combined size of the input and
the output. Furthermore, if exponential resources are prohibitive, one
would like to know whether a few explanations (e.g., polynomially
many) can be generated in polynomial time.
In recent and ongoing work, we have investigated the computational
complexity of these issues, and compiled several results for charting
the tractability / intractability frontier of these problems. In this
talk, we shall recall some of the results and then focus on abduction
from Horn theories represented by their characteristic models. In this
setting, the background theory T is represented by a set of so called
characteristic models, charset(T), rather than by formulas. The
benefit is that for certain formulas, logical consequence from T
efficiently reduces to deciding consequence from charset(T) (which is
easy) and thus admits tractable inference. In fact, finding some
abductive explanation for a query literal is polynomial in this
setting, while this is well-known to be NP-hard under formula-based
representation.
Computing all abductive explanations for a query literal is
polynomial-time equivalent (in a precise sense) to the problem of
dualizing a Boolean function given by a monotone CNF. The latter
problem, Monotone Dualization, is with respect to complexity a
somewhat mysterious problem which since more than 20 years resists to
a precise classification in terms of well-established complexity
classes. Currently, no polynomial total-time algorithm solving this
problem is known; on the other hand, there is also no stringent
evidence that such an algorithm is unlikely to exist (such as, eg.,
coNP-hardness of the associated decision problem whether, given two
monotone CNFs F and G, they represent dual functions). On the
contrary, results in the 1990's provided some hints that the problem
is closer to polynomial total-time, since as shown by Fredman and
Khachyian, the decisional variant can be solved in quasi-polynomial
time, i.e., in time O(n^{log n}). This was recently refined to
solvability in polynomial time with limited nondeterminism, i.e.,
using a poly-logarithmic number of bit guesses. We will consider some
possible extensions of the results for abductive explanations which
are polynomial-time equivalent to Monotone Dualization.
Apart from this peculiarity, Monotone Dualization has been recognized
as an important problem since there are a large number of other
problems in Computer Science which are known to be polynomial-time
equivalent to this problem. It has a role similar to the one of SAT
for the class NP: A polynomial total-time algorithm for Monotone
Dualization implies polynomial total-time algorithms for all the
polynomial-time equivalent problems.
We consider some possible extensions og the results for abductive
explanations which are polynomial-time equivalent to Monotone Dualization.
Besides generating all abductive explanations for a literal,
there are many other problems in
Knowledge Discovery and Data Mining which are polynomial-time
equivalent or closely related to Monotone Dualization, including
learning with oracles, computation of infrequent and frequent sets,
and key generation. We shall give a brief account of such problems,
and finally will conclude with some open problems and issues for
future research.
The results presented are joint work with Kazuhisa Makino, Osaka
University.
*The full version of this paper is
published in the Proceedings of the 6th International Conference
on Discovery Science, Lecture Notes in Artificial Intelligence Vol. 2843
©Copyright 2003 SPRINGER
|