121.
Logic Programming Revisited: Logic Programs as Inductive Definitions
- Marc Denecker,Maurice Bruynooghe,Victor Marek
This paper investigates the problem and proposes an alternative epistemological
foundation for the canonical model approach, which is not based on common sense but
on a solid mathematical information principle. The thesis is developed that logic programming
can be understood as a natural and general logic of inductive denitions. In particular, logic programs
with negation represent non-monotone inductive denitions. It is argued that this thesis
results in an alternative justication of the well-founded model as the unique intended model of
the logic program. In addition, it equips logic programs with an easy to comprehend meaning
that corresponds very well with the intuitions of programmers.
Categories and Subject Descriptors:...
122.
Towards Combining Inductive Logic Programming with Bayesian Networks
- Kristian Kersting,Luc De Raedt
Recently, new representation languages that integrate first order logic with Bayesian networks have been developed. Bayesian logic programs are one of these languages. In this paper, we present results on combining Inductive Logic Programming (ILP) with Bayesian networks to learn both the qualitative and the quantitative components of Bayesian logic programs. More precisely, we show how to combine the ILP setting learning from interpretations with score-based techniques for learning Bayesian networks. Thus, the paper positively answers Koller and Pfeffer's question, whether techniques from ILP could help to learn the logical component of first order probabilistic models.
123.
Scaling Up Inductive Logic Programming by Learning From Interpretations
- Hendrik Blockeel,Luc De Raedt,Nico Jacobs,Bart Demoen
When comparing inductive logic programming (ILP) and attributevalue
learning techniques, there is a trade-off between expressive
power and efficiency. Inductive logic programming techniques are
typically more expressive but also less efficient. Therefore, the data
sets handled by current inductive logic programming systems are
small according to general standards within the data mining community.
The main source of inefficiency lies in the assumption that
several examples may be related to each other, so they cannot be
handled independently.
Within the learning from interpretations framework for inductive
logic programming this assumption is unnecessary, which allows
to scale up existing ILP algorithms. In this paper we explain this
learning setting in the context of relational...
124.
Inductive Logic Programming for Corpus-Based Acquisition of Semantic Lexicons
- Pascale Sbillot,Pierrette Bouillon,Ccile Fabre
In this paper, we propose an Inductive Logic
Programming learning method which aims at
automatically extracting special Noun-Verb (NV)
pairs from a corpus in order to build up
semantic lexicons based on Pustejovsky's Gen-
erarive Lexicon (GL) principles (Pustejovsky,
1995). In one of the components of this lex-
ical model, called the qualia structure, words
are described in terms of semantic roles. For
example, the relic role indicates the purpose or
function of an item (cut for knife), the agentive
role its creation mode (build for house),
etc. The qualia structure of a noun is mainly
made up of verbal associations, encoding relational
information. The Inductive Logic Pro-
gramming learning method that we have developed
enables...
125.
If Inductive Logic Programming Leads, Will Data Mining Follow?
- Randy Goebel
The increasing popularity of inductive logic programming (ILP) has provided
one clear demonstration that machine learning has become practical.
Despite its relatively conservative basis, it has natural avenues of both theoretical
and practical development. One more general area in which induction
has a role is so-called knowledge discovery in databases (KDD) sometimes
called data mining. There too induction has a role, but many of the
current approaches are based on the creation of abstraction rules, guided
by the use of explicit concept hierarchies and hypothesis rankings based
on measures like "support" and "confidence" computed against extensional
(ground) databases.
We examine some of the directions in KDD, with the goal of...
126.
Discovering Dynamics: From Inductive Logic Programming to Machine Discovery
- Sa So D Zeroski
. Machine discovery systems help humans to find natural laws from collections of
experimentally collected data. Most of the laws found by existing machine discovery systems
describe static situations, where a physical system has reached equilibrium. In this paper, we
consider the problem of discovering laws that govern the behavior of dynamical systems, i.e.,
systems that change their state over time. Based on ideas from inductive logic programming and
machine discovery, we present two systems, QMN and LAGRANGE, for discovery of qualitative
and quantitative laws from quantitative (numerical) descriptions of dynamical system behavior.
We illustrate their use by generating a variety of dynamicalsystem models from examplebehaviors.
Keywords: machine...
127.
Using Inductive Logic Programming to construct Structure-Activity Relationships
- Ashwin Srinivasan,Ross D. King
The existence and rapid growth of chemical databases
have brought into focus the utility of methods that can
assist the discovery of predictive patterns in data, and
communicating them in a manner designed to provoke
insight. This has turned attention to machine learning
techniques capable of extracting "symbolic" descriptions
from data. At the cutting-edge of such techniques
is Inductive Logic Programming (ILP). Given
a set of observations and background knowledge encoded
as a set of logical descriptions, an ILP system attempts
to construct explanations for the observations.
The explanations are in the same language as the observations
and background knowledge -- usually a subset
of first-order logic. This contrasts with algorithms
like decision-trees, and...
128.
Inductive Logic Programming: issues, results and the LLL challenge
- Stephen Muggleton
. Inductive Logic Programming (ILP) [9, 11] is the area
of AI which deals with the induction of hypothesised predicate definitions
from examples and background knowledge. Logic programs
are used as a single representation for examples, background knowledge
and hypotheses. ILP is differentiated from most other forms
of Machine Learning (ML) both by its use of an expressive representation
language and its ability to make use of logically encoded
background knowledge. This has allowed successful applications of
ILP [1] in areas such as molecular biology [12, 10, 6, 5] and natural
language [7, 3, 2] which both have rich sources of background
knowledge and both benefit from the use of...
129.
The Subsumption Theorem in Inductive Logic Programming: Facts and Fallacies
- Shan-hwei Nienhuys-cheng,Ronald Wolf
. The subsumption theorem is an important theorem concerning
resolution. Essentially, it says that if a set of clauses Sigma logically
implies a clause C, then either C is a tautology, or a clause D which
subsumes C can be derived from Sigma with resolution. It was originally
proved in 1967 by Lee. In Inductive Logic Programming, interest in
this theorem is increasing since its independent rediscovery by Bain and
Muggleton. It provides a quite natural "bridge" between subsumption
and logical implication. Unfortunately, a correct formulation and proof
of the subsumption theorem are not available. It is not clear which forms
of resolution are allowed. In fact, at least...
130.
The use of Background Knowledge in Inductive Logic Programming
- Rui Camacho
This report describes experiments in learning models for basic flight
manoeuvres from behavioural traces of a human pilot when using a
flight simulator. A first set of experiments using decision trees is
presented. The auto-pilot built with the generated decision trees flies
more smoothly than the human pilot. However the results show also that
propositional logic-level representations, like decision trees, are inadequate
to fully solve the problem. A learning system using a first-order
representation is required. However, current Inductive Logic Programming
systems have severe limitations when dealing with such complex
domains due to inefficiencies of searching large hypothesis spaces. An
important issue to make the hypothesis space search tractable and...
131.
Discovering Dynamics: From Inductive Logic Programming to Machine Discovery
- Sa So D Zeroski
. Machine discovery systems help humans to find natural laws from collections of
experimentally collected data. Most of the laws found by existing machine discovery systems
describe static situations, where a physical system has reached equilibrium. In this paper, we
consider the problem of discovering laws that govern the behavior of dynamical systems, i.e.,
systems that change their state over time. Based on ideas from inductive logic programming and
machine discovery, we present two systems, QMN and LAGRANGE, for discovery of qualitative
and quantitative laws from quantitative (numerical) descriptions of dynamical system behavior.
We illustrate their use by generating a variety of dynamicalsystem models from examplebehaviors.
Keywords: machine...
132.
Learning to Parse Database Queries Using Inductive Logic Programming
- John M. Zelle,Raymond J. Mooney
This paper presents recent work using the Chill
parser acquisition system to automate the construction
of a natural-language interface for database
queries. Chill treats parser acquisition as
the learning of search-control rules within a logic
program representing a shift-reduce parser and
uses techniques from Inductive Logic Programming
to learn relational control knowledge. Starting
with a general framework for constructing a
suitable logical form, Chill is able to train on a
corpus comprising sentences paired with database
queries and induce parsers that map subsequent
sentences directly into executable queries. Experimental
results with a complete database-query
application for U.S. geography show that Chill
is able to learn parsers that outperform a preexisting,
hand-crafted counterpart. These results
demonstrate the ability...
133.
Knowledge Discovery in Databases - An Inductive Logic Programming Approach
- Katharina Morik
. The need for learning from databases has increased along
with their number and size. The new field of Knowledge Discovery in
Databases (KDD) develops methods that discover relevant knowledge in
very large databases. Machine learning, statistics, and database methodology
contribute to this exciting field. In this paper, the discovery of
knowledge in the form of Horn clauses is described. A case study of directly
coupling an inductive logic programming (ILP) algorithm with a
database system is presented.
1 Introduction
Databases are used in almost all branches of industry and commerce. The aim
of KDD is to discover rules hidden in these collected data.
The task of KDD is challenging, for...
134.
An Inductive Logic Programming Method for Corpus-based Parser Construction
- John M. Zelle,Raymond J. Mooney
Empirical methods for building natural language systems has become an important area of research
in recent years. Most current approaches are based on propositional learning algorithms and have been
applied to the problem of acquiring broad-coverage parsers for relatively shallow (syntactic) representations.
This paper outlines an alternative empirical approach based on techniques from a subfield of
machine learning known as Inductive Logic Programming (ILP). ILP algorithms, which learn relational
(first-order) rules, are used in a parser acquisition system called Chill that learns rules to control the
behavior of a traditional shift-reduce parser. Using this approach, Chill is able to learn parsers for a variety
of different types...
135.
An efficient validation mechanism for Inductive Logic Programming using compositionality
- Arnaud Lallouet,Lionel Martin
Inductive Logic Programming, which consists in learning clauses from examples, can be
viewed as a cycle conception/validation leading to the acceptance of the induced program provided
that it fulfills a certain criterion. We focus on the validation step in the context of
empirical multi-predicate learning of normal clauses. Thanks to a compositional semantics, the
classical validation step of the complete induced program can be replaced by the verification
of local properties for a cut out into units, considerably limiting the usual combinatorial explosion.
Moreover, we provide a semantics-preservative transformation which allows to simplify the
program and provides a further refinement of the cut out.
R'esum'e
La Programmation Logique Inductive...
136.
Using Inductive Logic Programming to construct Structure-Activity Relationships
- Ashwin Srinivasan,Ross D. King
The existence and rapid growth of chemical databases
have brought into focus the utility of methods that can
assist the discovery of predictive patterns in data, and
communicating them in a manner designed to provoke
insight. This has turned attention to machine learning
techniques capable of extracting "symbolic" descriptions
from data. At the cutting-edge of such techniques
is Inductive Logic Programming (ILP). Given a set of
observations and background knowledge encoded as a
set of logical descriptions, an ILP system attempts to
construct explanations for the observations. The explanations
are in the same language as the observations
and background knowledge -- usually a subset
of first-order logic. The use of first-order logic contrasts
with...
137.
An extended transformation approach to Inductive Logic Programming
- Nada Lavrac,Peter Flach
Inductive Logic Programming (ILP) is concerned with learning relational
descriptions that typically have the form of logic programs. In a transformation
approach, an ILP task is transformed into an equivalent learning task in a
different representation formalism. Propositionalisation is a particular transformation
method, in which the ILP task is compiled down to an attributevalue
learning task. The main restriction of propositionalisation methods
such a s LINUS is that they are unable to deal with non-determinate local
variables in the body of hypothesis clauses. In this paper we show how this
limitation can be overcome, by systematic first-order feature construction using
a particular individual-centred feature bias. The approach can be...
138.
Learning Information Extraction Rules: An Inductive Logic Programming approach
- James Stuart Aitken
The objective of this work is to learn information extraction rules by applying Inductive Logic Programming (ILP) techniques to natural language data. The approach is ontology-based, which means that the extraction rules conclude with specific ontology relations that characterise the meaning of sentences in the text. An existing ILP system, FOIL, is used to learn attribute-value relations. This enables instances of these relations to be identified in the text. In specific, we explore the linguistic preprocessing of the data, the use of background knowledge in the learning process, and the practical considerations of applying a supervised learning approach to rule...
139.
On Multi-class Problems and Discretization in Inductive Logic Programming
- Wim Van Laer,Luc De Raedt,Saso Dzeroski
. In practical applications of machine learning and knowledge
discovery, handling multi-class problems and real numbers are important
issues. While attribute-value learners address these problems as a rule,
very few ILP systems do so. The few ILP systems that handle real numbers
mostly do so by trying out all real values applicable, thus running
into efficiency or overfitting problems.
The ILP learner ICL (Inductive Constraint Logic), learns first order logic
formulae from positive and negative examples. The main characteristic
of ICL is its view on examples, which are seen as interpretations which
are true or false for the target theory. The paper reports on the extensions
of ICL to tackle...
140.
Systematic Predicate Invention in Inductive Logic Programming
- L. Martin; C. Vrain
We propose in this paper a new approach for learning predicate definitions from examples and an initial theory. The particularity of this approach consists in inventing a new predicate at most steps of learning; once the learning task is ended, most invented predicates are removed by unfolding techniques. Nevertheless, some predicates remain in the learned definitions, either because they enable to simplify the program, or because their definitions are recursive and the program could not have been learned without inventing these predicates. Moreover, when a new predicate symbol is introduced, a specification for this predicate is built; this specification is...
