Transcript Continuous Bayesian Logic Programs

APRIL
Applications of Probabilistic Inductive Logic Programming
Albert-Ludwigs University
Freiburg, Germany
Imperial College of
Science, Technology and Medicine,
London, Great Britain
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Abstract
The project adresses
„probabilistic logic learning“
i.e. the integration of probabilistic reasoning with
first order logic representations and machine
learning. The objective is to critically assess the
promise of this approach using application of
functional genomics.
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Context
Real-world applications
Uncertainty
Complex, structured domains
Probability theory
Logic: objects, relations, functors
Hidden Markov Models,
Stochastic Context-Free Grammars,
Bayesian networks, ....
Logic Programs
(Prolog)
„Probabilistic Logic“
?
„Probabilistic Logic Learning“
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Learning
Objectives (1)
One of the key open questions of artificial intelligence
concerns
"probabilisitic logic learning",
i.e. the integration of
probabilistic reasoning with
first order logic
representations and
machine learning.
Probabilitstic
Logic
Learning
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
What is „Probabilistic Logic Learning?
- Probabilistic
•
•
•
Representations and reasoning
Probabilistic
Logic
mechanisms grounded in probability
theory, e.g. HMMs, Bayesian networs,
Learning
stochastics grammars ...
Successfully used in a wide range of
applications such as computational biology, speech
recognition, ...
Robust models
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
What is „Probabilistic Logic Learning?
- Logic
•
•
First-order logic
Elegant representation of
complex situations involving a
variety of objects as well as
reltions among these objects:
bloodtype(X,a) <-
Probabilistic
Logic
Learning
mother(M,X),bloodtype(M,a),
father(F,X),bloodtype(F,a).
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
What is „Probabilistic Logic Learning?
- Learning
• Computing various aspects of
a „probabilistic logic“ on the
basis of data
•
•
•
•
Probabilistic
Logic
Learning
Often it is easier to obtain data
and to learn a model than using
traditional knowledge engineering techniques
Parameter estimation
Learning the „logical“ structure
Fully vs. unobservable random variables
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Research Context:„Probabilistic Logics“
•
•
Studies of probabilistic logics:
Nielson, Halpern, Poole, ...
Recently: Koller, Sato, Jaeger ,...
Probabilistic
Logic
Learning
objects/relations
Logics
Probabilistic Logics
propositional
HMMs, Bayesian networks, ...
deterministic
probabilistic
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Research Context: „Probabilistic
Learning“
•
(ML) Parameter estimation
•
•
•
Different scores
•
•
Probabilistic
Logic
Learning
LogLikelihood, BIC, MDL, MML, ...
Structural learning
•
•
•
Gradient-based algorithms
Family of EM algorithm
Score-based hill-climbing
Independency tests
Monte Carlo Markov Chain (MCMC) techniques
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Research Context: „Logic Learning“
•
•
•
•
Inductive Logic Learning
Machine Learning and
Probabilistic
Logic
Data Mining within first-order
Learning
representations
Broadened the application domain
of Data Mining, especially in bio- and
chemoinformatics
Some of the best-known examples of Scientific
Discovery by AI systems
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Objectives (2)
Overall goal:
To critically investigate "probabilistic logic learning"
methods by answering the following questions:
1. Are there significant applications for which "first
order probabilistic logic" is better than state-ofthe-art representations?
2. Can models be learned within such a "first order
probabilistic logic"?
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Description of Work (1)
In order to answer the questions, we plan
1. to investigate and evaluate various alternative first
order probabilistic representations and reasoning
mechanisms such as:
o Stochastic Logic Programs [Muggleton 95, Cussens 99],
o Bayesian Logic Programs" [Kersting, De Raedt 00].
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Description of Work (2)
2. to employ the most promising such representations
to model a functional genomics application;
3. to develop and to employ simple learning
techniques to enable the learning of parts of the
probabilistic logic representation;
4. to identify the main goals, directions and questions
to be addressed in probabilistic logic learning.
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Application: Functional Genomics (1)
Hieter P. and Boguski M. (1997) Functional Genomics: It's all
how you read it. Science 278, 601-02:
Functional Genomics
ˆ
„Development and application of global (genome-wide or
system-wide) experimental approaches to assess gene
function by making use of the information and reagents
provided by structural genomics.“
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Application: Functional Genomics (2)
Hieter P. and Boguski M.:
"[Functional genomics] is characterized by high throughput or
large-scale experimental methodologies combine with
statistical and computational analysis of the results. The
fundamental strategy in a functional genomics approach is to
expand the scope of biological investigation from studying
single genes or proteins to studying all genes or proteins at
once in a systematic fashion."
Probabilistic Logic Learning
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Application: Functional Genomics (3)
•
Inductive Logic Learning supports the
use (as background knowledge) of
generally known metabolic pathways
and encoded enzyme chemistry.
deterministic
•
Probabilistic approaches make
probabilistic descriptions of outcomes
of experiments, i.e. they account for
uncertainty due to e.g. noise, hidden
variables, etc.
Probabilistic Inductive Logic
Learning should enable
probabilistic descriptions of
experiments, as well as
supporting the general, i.e.
first-order description of
probabilistic behaviour in
e.g. the enzyme chemistry.
propositional
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Stochastic Logic Programs /
Bayesian Logic Programs
Stochastic Logic Programs [Muggleton 95, Cussens 99]
• Probabilities defined over proofs
• Single probability values associated to Horn clause
• Log-linear models
Bayesian Logic Programs [Kersting, De Raedt 00]
• Ground atoms = random variables
• Conditional probability distribution associated to Horn
clause
• Dependency graph resticted to least Herbrand
universum= (possibly infinite) Bayesian network
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.
Related Projects
DARPA project:
Evidence Extraction and Link Discovery (EELD)
http://www.darpa.mil/iso/EELD/
APRIL, Application of Probabilistic Inductive Logic Programming, IST-2001-33053
Albert-Ludwigs-University, Freiburg, Germany & Imperial College of Science, Technology and Medicine, London, Great Britain.