Transcript An abductive proof procedure and its application in multi

Abduction and Induction in
Scientific Knowledge Development
Peter Flach, Antonis Kakas & Oliver Ray
AIAI Workshop 2006
ECAI 2006
29 August, 2006
1
Central Challenge
(left from the workshops in 1990s)
•
How can we usefully integrate
abduction and induction
•
What are appropriate basic forms of these
two forms of reasoning and how far we
can get with them?
•
•
What are the limits on learning of such an
integration?
What are appropriate applications (from which
we can drive this integration)?
2
Central “Application Theme”
•
Scientific Modelling
•
•
•
Not necessarily classical scientific
domains!
Domains that follow scientific
methodology.
Declarative Modelling
3
This Talk
•
Chart out:
•
•
•
•
a proposal that came out from previous
workshops, and
how this was taken up till now.
some recent applications.
Set the scene for the afternoon’s
discussion
4
Scientific Modelling
•
Development of scientific theories is
incremental where we need to exploit
fully the knowledge acquired so far
•
Declarative Logical Modelling can
facilitate this:
•
•
Ease of Representation – a logical model
expressed directly from the expert
knowledge.
Initial knowledge on a domain is typically
descriptive – well suited for logical
representation.
•
E.g. molecular biology/functional genomics
knowledge
5
Scientific Modelling and Logic
(Logic for Declarative Modelling)
•
Start with models that represent the prior knowledge
of our domain in a logical form, i.e in a theory T.
•
Understand past and current observations, Obs, in
terms of the current model T through synthetic
logical reasoning that generates further information,
H, such that:
•
•
•
T  H |= Obs
T  H is consistent
H is a hypothesis on the incomplete part of the model T
•
The hypothesis H explains the observations Obs
according to T.
•
This a process of rationalization/normalization of
(the disperse set of) observations through our
current model T.
6
Ontological distinction of
Information and Logical Predicates
•
Observable Information/Predicates: describes
observations of scientific experiments.
Testable directly.
•
Abducible Information/Predicates: describe
underlying (theoretical) relations.
Missing/incomplete information that needs to
be inferred – not testable directly.
•
Background Information/Predicates: auxiliary
information that helps us link observable and
abducible information.
7
EXAMPLE: A “socio-economic”
model of Universities
•
Language/Ontology of relations
{sad/1, overworked/1, academic/1,
student/1,
lecturer/1, poor/1}
•
Model & background knowledge
sad(X) if overworked(X), poor(X)
overworked(oliver)
overworked(alex)
overworked(krycia)
lecturer(alex)
lecturer(krycia)
student(oliver)
academic(alex), …
poor(alex).
8
Example of Declarative Modelling
Gene Interaction

Model/Rules for Gene Interaction:
increases_expression(Expt, X) ←
knocks_out(Expt, G),
inhibits(G,X),
not affected_by_other_gene(Expt, G, X),
not affected_by_EnvFactor(Expt, X).
increases_expression(Expt, X) ←
knocks_out(Expt, G),
intermediary_gene(Expt,G1,G),
reduces_expression(Expt,G1),
inhibits(G1,X),
not affected_by_EnvFactor(Expt, X).

Parameter of the model: intermediary_gene/3
9
Scientific Modelling through Logic
•
Any scientific model can be (is) incomplete!
•
Information is separated into three types:
•
•
•
•
Observable (phenotype) – obtained from
experiments via observations
Theoretical (functional genotype) – underlying
relations that cause the observable behaviour
Background – known relevant properties, e.g.
structural or chemical information.
Example: {sad/1, overworked/1,
academic/1, student/1, lecturer/1, poor/1}10
Scientific Modelling (cnt.)
•
The incompleteness of the model resides in
the theoretical part (e.g poor/1)
•
The task is to complete the model by finding
theoretical information and developing a
theory for this.
•
HOW do we synthesize definitions for the
unobserved theoretical relations?
•
ANSWER: Scientific theories are “explanatory” and
“unifying”
11
Synthetic Reasoning for
Declarative Problem Solving

Deduction: concerned with PREDICTION of
phenotype from a given model


Abduction: concerned with EXPLANATION
according to a given model: produces genotype
information


T |= Obs
T U H |= Obs
H specific (genotype) information
Induction: concerned with GENERALIZATION of
information outside the observed situations

T U H |= Obs
H general (genotype) information
12
EXAMPLE: A “socio-economic” model of
Universities (Cnt.)
•
Model & background knowledge
sad(X) if overworked(X), poor(X)
overworked(oliver)
overworked(alex)
overworked(krycia)
lecturer(alex)
lecturer(krycia)
student(oliver)
academic(alex), …
Abducible
•
Observations = {sad(alex), sad(krycia), not sad(oli)}
•
Abductive Explanation =
{poor(ale), poor(krycia), not poor(oli)}
13
Logical Reasoning for
Scientific Analysis
Observe
Generalizes
the rationalization
and hence the Obs
Generate hypotheses
Abduction
Induction
Experiment
Verify hypotheses
Revise Model
Rationalises
the
Observations
14
The cycle of abductive and inductive
knowledge development
O
T’ = T U H
H
Induction
T U H |= Obs
Abduction
H
T
O’= H
15
Integration of
Abduction & Induction

Abduction: problem solving given an adequate
but incomplete model of the problem domain



Integration with Induction



Generates explanations: specific hypotheses on the
incomplete part of the model
Rationalizes/normalizes the observations.
Feed explanations to Induction.
Induction: development of the model by a (partial)
theory for its incomplete part.
Tight Integration
•
Explanations and their Generalization are evaluated as
16
a whole.
EXAMPLE: A “socio-economic” model of
Universities (Cnt.)
sad(X) if overworked(X), poor(X)
overworked(oliver)
overworked(alex)
overworked(krycia)
lecturer(alex)
lecturer(krycia)
student(oliver)
academic(alex), …
•
Observations = {sad(alex), sad(krycia), not sad(oli)}
•
Abductive Explanation =
{poor(ale), poor(krycia), not poor(oli)}
17
•
Inductive Hypotheses: poor(X) if lecturer(X)
EXAMPLE: Verifying Hypotheses
•
poor(X) if lecturer(X)
•
The socio-economy specialist is sceptical as it
knows that students are poor.
•
•
The hypotheses is rejected and new partial
information is now given:
poor(X) if student(X)
Model now is refined to:
sad(X) if not student(X),overworked(X),poor(X)
sad(X) if student(X), alone(X)
poor(X) if student(X)
18
EXAMPLE: Verifying Hypotheses
Model now is refined to:
sad(X) if not student(X),overworked(X),poor(X)
sad(X) if student(X), alone(X)
poor(X) if student(X)
•
•
Observations = {sad(alex), sad(krycia), not sad(oli)}
•
Abductive Explanation =
{poor(ale), poor(krycia), not alone(oli)}
•
Inductive Hypotheses: poor(X) if young(X), lecturer(X)
(Note: “poor(X) if young(X)” is rejected because we
19
know young(bill), rich(bill).)
Current Situation

Frameworks of Integration





Inverse Entailment
HAIL
SOLDR
CF-Induction
Systems of Integration

Progol 5

ProLogICA
HAIL (?)



INTHELEX (?)
CF-Induction (?)
20
Current Situation (Cnt)
Applications
•
•
•
•
Gene Regulatory Pathways
Inhibition in Metabolic Networks
Signal Networks
Robot Navigation (Learning Action Theories
e.g. Event Calculus)
21
Future Outlook

Challenges remain

Appropriate basic forms of reasoning:





Normal & Disjunctive LP
Trade off between generality & efficiency
Chart out the limits of learning
Understand their relevancy for scientific modelling applications
Let applications drive the Theoretical & Practical
Development



Computational Bioscience
Natural Language
Cognitive Robotics
22
CONCLUSIONS
•
Use of logical inference can be powerful
method for “rationalization” of scientific
phenomena.
•
But it needs a good problem domain model with:
•
•
•
•
Clear hypotheses of the basic model
Parameters of variation of analysis of the phenomena
Well-informed strategy of use and feedback analysis
Offers a systematic methodology for
modelling and analysis under
known/engineered hypotheses.
23
Microarray Gene Mutation
Experiments at CMMI
24