%\documentstyle[a4paper]{article}
\documentclass[a4paper]{article}
\usepackage{times}
\textheight=24cm
\textwidth=16cm
\hoffset=-2.2cm
\voffset=-2cm
%\parskip=1ex
%\baselineskip=1.6ex
%\pagestyle{empty}
\begin{document}
\title{Abduction and Induction in AI: \\
Report of the IJCAI'97 Workshop}
\author{
Peter A.~Flach \\
Dept.~of Computer Science, University of Bristol \\
Merchant Venturers Building, Woodland Road,
Bristol BS8 1UB, United Kingdom \\
{\tt Peter.Flach@cs.bris.ac.uk} \\
\\
Antonis Kakas \\
Dept.~of Computer Science, University of Cyprus \\
POBox 537, CY-1678\ \ Nicosia, Cyprus \\
{\tt antonis@turing.cs.ucy.ac.cy} \\
}
\maketitle
\section{Introduction}
Over twenty researchers participated in this IJCAI'97 workshop to dicuss the
general relationship of abduction and induction. The main aim of the
workshop was set out to address the issue of the relation and
integration of Abdcution and Induction in the context of (practical)
AI problems. This focus was summarized by the following questions:
\begin{itemize}
\item What (if anything) distinguishes/characterizes each form of reasoning
and their corresponding computational models?
\item How can we characterize different prototypical AI tasks for which it is
appropriate to use one of these two forms of reasoning?
\item How can Abduction and Induction be integrated in the context of
Artificial Intelligence problems? For example,
\begin{itemize}
\item How do we learn abductive theories?
\item How do we use abduction in machine learning problems?
\end{itemize}
\end{itemize}
The workshop's organising committee consisted of Peter Flach (then at
Tilburg University, Netherlands), Antonis Kakas (University of Cyprus),
Raymond Mooney (University of Texas at Austin, USA) and Chiaki Sakama
(Wakayama University, Japan). The submitted papers were reviewed and
selected by a program committee additionally including Randy Goebel
(University of Alberta, Canada), Katsumi Inoue (Kobe University, Japan)
and John Josephson (Ohio State University, USA). The workshop assumed
the same format as the the preceding ECAI'96 workshop on Abductive and
Inductive Reasoning \cite{ECAI96report}, devoting ample time to plenary
discussions.
However, this workshop had a different emphasis from its predecessor,
which indicates that a certain amount of progress has been made.
Whereas the discusson at the ECAI'96 workshop revolved almost
exclusively around the question whether and how abduction
and induction are different forms of
reasoning, the discussion at the IJCAI'97 workshop took, for most of
its part, a more practical stance, concentrating on
how to integrate them within an
Artificial Intelligence context. Among the 12 accepted papers the
program committee selected 9 for presentation at the workshop. The
presentations were evenly divided over 3 sessions, addressing the
issues pertaining to the integration of abduction and induction in a
bottom-up fashion starting from specific practical problem of their
integration and ending up with theoretical issues.
These sessions are reviewed in more detail below.
\section{Invited talk: David Poole}
David Poole (Universiy of British Columbia, Canada) gave an invited
talk entitled {\em Learning, Bayesian Probability, Graphical Models,
and Abduction}.\footnote{The slides for David Poole's talk can be found
at {\tt http://www.cs.ubc.ca/spider/poole/talks/ind-ab.pdf}} In his
talk he tried to tie together logic and probabilistic approaches to
induction in terms of belief networks and probabilistic Horn abduction.
Belief (Bayesian) networks are a graphical representation of
independence and provide a way to structure knowledge and to exploit
the structure for computational gain. Poole pointed out the
relationship between belief networks and logic-based (abductive)
representations for evidential reasoning. If we want to do evidential
reasoning (from effects to causes) without knowing the underlying
process, there is a choice between causal modelling (learning
cause$\rightarrow$effect rules) and evidential modelling (learning
effect$\rightarrow$cause rules); we can model causally and use
abduction for evidential reasoning (as do abductive diagnosis and
belief networks) or model evidentially and use deduction for evidential
reasoning (as in neural networks and consistency-based diagnosis).
Poole overviewed the tradeoffs in this choice.
One of the most interesting aspects of Poole's talk was that it
approached the issue of abduction vs.~induction from both a
probabilistic and a logical perspective. For instance, he argued that
Bayesian conditioning (the kind of evidential reasoning done in
Bayesian networks to find causes for observed effects) can be seen as
abduction in probabilistic logic programs, where we try to explain the
evidence conditioning on all the knowledge obtained since the knowledge
base was built. He also provided a view of Bayesian learning as
essentially abductive, where the abductive step is finding the right
parameter values. From this viewpoint, then, the conclusion that there
is no essential difference between abduction and induction seems
inescapable.
In his conclusion, Poole argued that the logical and the probabilistic
approaches can learn from each other. Bayesians have good methods to
handle noise and avoid overfitting, a universal method for finding
explanations (conditioning), and good algorithms for exploiting sparse
structures. They lack however the rich representations used by the
logicians.
\section{Discussion panel 1: Abduction and Inductive Logic Programming}
Chiaki Sakama (Wakayama University, Japan) discussed ways to use
abduction in the process of induction \cite{sakama}. If a clause can
only entail an example by adopting an abductive explanation, a
generalisation is obtained by dropping the abducible from the clause.
Conversely, a knowledge base that entails a negative example can be
specialised by weakening the causes for the entailment by disjoining
them with new abnormality abducibles.
Takashi Kanai and Susumu Kunifuji (Japan Advanced Institute of Science
and Technology) proposed a new integrated method of inductive
generalisation and abductive reasoning \cite{kk}. Abduction is used to
supplement incomplete background knowledge. The approach is a variant
of FOIL \cite{foil}, including an improved information gain heuristic
to deal with the cost of abductive explanations.
Akihiro Yamamoto (visiting Technische Hochschule Darmstadt, Germany;
now at Hoikkaido University, Japan) made a connection between inductive
hypothesis formation and proof procedures for consequence finding.
The proof procedure is a special case of SOL-resolution \cite{sol},
extending SLD-resolution by allowing to skip the proof of
selected subgoals, adding them to an abductive explanation instead.
This is then related to Muggleton's inverse entailment operator
\cite{invent}.
The papers in this session essentially concentrated on abduction as a
tool in the learning process. Immediate questions are then when this is
needed or appropriate, and how it can be done. The ability to extend
imperfect background knowledge abductively was generally found to be
useful, as domain theories are often incomplete in practice. One can go
one step further and argue that also the learned hypothesis will in
general be incomplete (i.e. nonmonotonic) to some extent, in which case
we are not just using but {\em learning} abductive theories. This
obviates the need for learning not only classification rules but also
integrity constraints, which are needed in abductive logic programming
to constrain the possible explanations. Presumably having an abductive
coverage relation also influences the generality structure of the
hypothesis space, and may have a profound impact on the learning
algorithm. Finally, there should be a reasonable trade-off between
treating a wrongly covered negative example as an exception
vs.~revising the hypothesis.
\section{Discussion panel 2: Abduction and Induction --
their relation and integration}
Raymond Mooney (University of Texas at Austin, USA) \cite{mooney}
presented an overview of work on the integration of abduction and
induction in machine learning systems that his group has been doing over the
last years. He argued that each inference can strengthen
the other and presented practical applications to support this. In
particular, he showed how abductive reasoning can be useful in
inductively revising existing knowledge bases by finding appropriate
places of ``repair'' of the knowledge base. Also he showed how
inductive learning can be used to form theories for abductive reasoning.
Akinori Abe (NTT Communication Science Laboratories, Japan) \cite{abe}
observed that abduction and induction can be seen as dual to each
other and can be linked together when we are in a situation of similar
observations. Abductive explanations for similar observations can
form suitable data for inductive generalization. He presented a
framework for Analogical Abductive Reasoning and showed how when this
is applied to similar observations its generated hypotheses can form
good examples for generalization.
Pinar \"{O}zt\"{u}rk (Norwegian University of Science and Technology)
was unfortunately unable to attend the workshop and present her paper
\cite{ozturk}.
The second discussion complemented in some sense the first one by
considering ways in which induction could be useful in abduction. One
interesting possibility would be to abductively explain several
observations seperately, and then to inductively generalise them into a
single explanation. In this way we are extending the capabilities of an
abduction system by generating explanations that are non-ground
rules. From the induction perspective we are learning rules for non-observed
predicates, which points at a link with {\em descriptive} induction.
An important issue that came up was whether the fact that induction
typically requires many observations whereas abduction proceeds from a
single or few observations is at all relevant. A number of people
supported the intuition that abduction deals with incomplete knowledge
regarding a {\em single} situation, whereas induction extends
incomplete knowledge about a {\em class} of situations. Others
objected by pointing at the difficulty of defining the notion of a
situation in a non-syntactic way.
\section{Discussion panel 3: Unifying foundations of abduction and
induction}
Geert-Jan Kruijff (Charles University, Czech Republic) \cite{kruijff}
pointed out the importance of novelty in abductive reasoning and
argued that this forms an important criterion for comparing the
two forms of reasoning. Furthermore, he distinguished the two schools of
``unification'' and ``cooperation'' for the relation of abduction and
induction and argued for the latter. In particular, he argued that
induction can lend further credibility to abductive hypotheses.
Peter Gr\"{u}nwald (CWI, the Netherlands) \cite{grunwald} argued that
probability can provide a conceptual unification for the two inferences.
The difference lies in the ontology of the output of the inference:
abduction generates data while induction generates hypotheses (in the
statistical sense).
He showed how the Minimum Description Length Principle,
which is frequently used as a heuristic in inductive learning,
is also appropriate for abductive reasoning, thus supporting
the claim that the two forms of reasoning can be unified
under probability.
Pei Wang (Indiana University, USA) was unfortunately unable to attend
the workshop and present his paper \cite{wang}.
One issue that came up in the third discussion was that induction seems
to do a better job in assigning credibility to hypotheses. This is not
just because induction is typically based on many observations, but
also because inductive hypotheses allow us to make predictions about
unseen cases and verify them by cross-validation. Some participants
argued against this by pointing out that also abductive hypotheses can
have additional consequences that can be verified.
Related discussion topics were whether and how we can use induction
to increase the credibility of abductive hypotheses, and whether the
selection criteria really differ for abductive and inductive hypotheses.
\section{Concluding remarks}
While the preceding ECAI'96 workshop was successful in bringing people
from different disciplines together and identifying some of the main
general issues, this IJCAI'97 workshop approached the issue of
integrating abduction and induction from a more practical AI
perspective. The main conclusion to be drawn from these two workshops
is that whether one perceives abduction and induction as two of a kind
or as fundamentally different reasoning forms depends strongly on the
domain of application and the particular AI approach employed. Hence,
an appropriate question to ask is not ``What is the relation between
abduction and induction'', but rather ``What are good reasons
for perceiving them as fundamentally different or fundamentally
similar?'' The successor workshop to be organised at ECAI'98 will take
this more relativistic perspective as its starting point.
Another way in which this workshop differed from its predecessor is
that several participants (e.g.~Poole and Gr\"{u}nwald) approached the
issue from a probabilistic perspective. The debate between logical and
symbolic approaches is an important one because, as Poole pointed
out, both can profit from the other's expertise. The discussions at the
workshop tentatively suggested that from the probabilistic
viewpoint there is no essential difference between abduction and
induction. However, one must keep in mind that logical approaches tend
to concentrate on hypothesis formation, while probabilistic approaches
are concerned with evaluation and selection of hypotheses. It may very
well be that the evaluation process is the same for abduction and
induction (and indeed for any other form of reasoning), while the
formation process is different in each case.
Our experience with both of these worskhops has shown that it is
premature to expect universally agreed positions on these difficult
issues. Nevertheless, one generally accepted conclusion of this workshop was
that, if we perceive abduction and induction as
separate inferences, these can be integrated in a {\bf
cycle} of knowledge generation governed by the `equation'
$B \cup H \models O$ where $H$ is the new knowledge generated.
On one side of the cycle this new knowledge then
feeds in the place of $O$ and on the other side it feeds in the place of
$B$. Depending on where we break this cycle we identify the separate
inferences of abduction and induction: abduction generating new
elements for $O$ and induction for $B$.
This then raises the important question of how can one inference be
used to justify (or affect the selection of) the hypotheses generated by
the other inference.
The workshop notes contain 12 short papers and are available on-line
through the workshop's WWW-pages ({\tt
http://www.cs.bris.ac.uk/\~{}flach/IJCAI97/}).
\section*{Acknowledgements}
This workshop has been made possible by financial support from the
European Network of Excellence CompulogNet.
Writing of this report has been partially supported by the Esprit Long
Term Research Project 20237 (Inductive Logic Programming 2).
\begin{thebibliography}{99}
\bibitem{abe}
Akinori Abe,
`The relation between abductive hypotheses and inductive hypotheses',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~1-6.
\bibitem{bell}
John Bell,
`Inductive, abductive and pragmatic reasoning',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~7-12.
\bibitem{codognet}
Philippe Codognet,
`Abductive reasoning: backward and forward',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~13-16.
\bibitem{goebel}
Randy Goebel,
`Abduction and its relation to constrained induction',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~17-18.
\bibitem{grunwald}
Peter Gr\"{u}nwald,
`The Minimum Description Length principle and non-deductive inference',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~19-23.
\bibitem{kk}
Takashi Kanai \& Susumu Kunifuji,
`Extending inductive generalisation with abduction',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~25-30.
\bibitem{kruijff}
Geert-Jan Kruijff,
`Concerning logics of abduction -- on integrating abduction and
induction', {\it Proc.~IJCAI'97 Workshop on Abduction and Induction in
AI}, pp.~31-36.
\bibitem{mooney}
Raymond Mooney, `Integrating abduction and induction in Machine
Learning', {\it Proc.~IJCAI'97 Workshop on Abduction and Induction in
AI}, pp.~37-42.
\bibitem{ozturk}
Pinar \"{O}zt\"{u}rk, `An AI criterion for an account of inference: how
to realize a task', {\it Proc.~IJCAI'97 Workshop on Abduction and
Induction in AI}, pp.~43-48.
\bibitem{sakama}
Chiaki Sakama, `Inductive extension of abduction',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~49-52.
\bibitem{wang}
Pei Wang,
`Return to term logic',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~53-57.
\bibitem{yamamoto}
Akihiro Yamamoto,
`Representing inductive inference with SOLD-resolution',
{\it Proc.~IJCAI'97 Workshop on Abduction and Induction in AI},
pp.~59-63.
\bibitem{ECAI96report}
Peter Flach \& Antonis Kakas,
`Abductive and Inductive Reasoning: report of the ECAI'96 workshop',
{\it Logic Journal of the IGPL} 5(5):773-778, 1997.
\bibitem{foil}
Ross Quinlan,
`Learning logical definitions from relations',
{\it Machine Learning} 5(3):239-266, 1990.
\bibitem{sol}
Katsumi Inoue,
`Linear resolution for consequence finding',
{\it Artificial Intelligence} 56:301-353, 1992.
\bibitem{invent}
Stephen Muggleton,
`Inverse entailment and Progol',
{\it New Generation Computing} 13:245-286, 1995.
\end{thebibliography}
\end{document}