We explore the use of Mercury for Inductive Logic Programming and present IMP0.5, the product of our research. Mercury is a compiled logic programming language with modern features, which requires the user to write type, mode and determinism declarations for each of their predicates. This information is used by the Mercury compiler to optimise generated code, which, amongst other things, enables Mercury to provide faster execution than Prolog. IMP0.5 is an ILP system, and an ILP software library, which contains re-usable modules of ILP related code. Our aim in creating IMP0.5 as a software library was to significantly reduce the effort required to implement new ILP algorithms. We feel this has been achieved and provide implementations of some typical ILP algorithms, the most notable being the Aleph default algorithm. Since Mercury is a purely declarative language run-time assertion of induced hypotheses is prohibited. Therefore, hypotheses are represented as ground terms, and, to enable fast cover testing, interpreted with a problem specific interpreter, which is generated at compile-time. We also use a cover set representation based on RL-Trees, which is very space efficient and thus beneficial for large searches. Empirical results are generally good, especially for complex background knowledge, and in one case shows a 56 times speed-up compared with Aleph.

This paper presents and evaluates an approach to Bayesian model averaging where the models are Bayesian nets (BNs). A comprehensive study of the literature on structural priors for BNs is conducted. A number of prior distributions are defined using stochastic logic programs and the MCMC Metropolis-Hastings algorithm is used to (approximately) sample from the posterior. We use proposals which are tightly coupled to the priors which give rise to cheaply computable acceptance probabilities. Experiments using data generated from known BNs have been conducted to evaluate the method. The experiments used 6 different BNs and varied: the structural prior, the parameter prior, the Metropolis-Hasting proposal and the data size. Each experiment was repeated three times with different random seeds to test the robustness of the MCMC-produced results. Our results show that with effective priors (i) robust results are produced and (ii) informative priors improve results significantly.

The problem of learning discrete Bayesian networks from data is encoded as a weighted MAX-SAT problem and the MaxWalkSat local search algorithm is used to address it. For each dataset, the per-variable summands of the (BDeu) marginal likelihood for different choices of parents (`family scores') are computed prior to applying MaxWalkSat. Each permissible choice of parents for each variable is encoded as a distinct propositional atom and the associated family score encoded as a `soft' weighted single-literal clause. Two approaches to enforcing acyclicity are considered: either by encoding the ancestor relation or by attaching a total order to each graph and encoding that. The latter approach gives better results. Learning experiments have been conducted on 21 synthetic datasets sampled from 7 BNs. The largest dataset has 10,000 datapoints and 60 variables producing (for the `ancestor' encoding) a weighted CNF input file with 19,932 atoms and 269,367 clauses. For most datasets, MaxWalkSat quickly finds BNs with higher BDeu score than the `true' BN. The effect of adding prior information is assessed. It is further shown that Bayesian model averaging can be effected by collecting BNs generated during the search.

In Datalog, missing values are represented by Skolem constants. More generally, in logic programming missing values, or existentially quantified variables, are represented by terms built from Skolem functors. The CLP( cal BN ) language represents the joint probability distribution over missing values in a database or logic program by using constraints to represent Skolem functions. Algorithms from inductive logic programming (ILP) can be used with only minor modification to learn CLP( cal BN ) programs. An implementation of CLP( cal BN ) is publicly available as part of YAP Prolog at http://www.ncc.up.pt/~vsc/Yap.

The problem of deciding the probability model equivalence of two PRISM programs is addressed. In the finite case this problem can be solved (albeit slowly) using techniques from algebraic statistics, specifically the computation of elimination ideals and Gröbner bases. A very brief introduction to algebraic statistics is given. Consideration is given to cases where shortcuts to proving/disproving model equivalence are available.

We investigate using the Mercury language to implement and design ILP algorithms, presenting our own ILP system IMP. Mercury provides faster execution than Prolog. Since Mercury is a purely declarative language, run-time assertion of induced clauses is prohibited. Instead IMP uses a problem-specific interpreter of ground representations of induced clauses. The interpreter is used both for cover testing and bottom clause generation. The Mercury source for this interpreter is generated automatically from the user's background knowledge using MOOSE, a Mercury parser generator. Our results include some encouraging results on IMP's cover testing speed, but overall IMP is still generally a little slower than ALEPH.

A general method for defining informative priors on statistical models is presented and applied specifically to the space of classification and regression trees. A Bayesian approach to learning such models from data is taken, with the Metropolis-Hastings algorithm being used to approximately sample from the posterior. By only using proposal distributions closely tied to the prior, acceptance probabilities are easily computable via marginal likelihood ratios, whatever the prior used. Our approach is empirically tested by varying (i) the data, (ii) the prior and (iii) the proposal distribution. A comparison with related work is given.

This paper concerns the experimental assessment of tempering as a technique for improving Bayesian inference for C&RT models. Full Bayesian inference requires the computation of a posterior over all possible trees. Since exact computation is not possible Markov chain Monte Carlo (MCMC) methods are used to produce an approximation. C&RT posteriors have many local modes: tempering aims to prevent the Markov chain getting stuck in these modes. Our results show that a clear improvement is achieved using tempering.

Connections and contrasts between deductive reasoning and statistical inference are given. Bayesian statistical inference is analysed, including an account of its relation to deductive logic and the status of prior distributions. Classical statistical inference is investigated with a focus on hypothesis testing.

This report describes the close relationship that obtains between the ICL, PRISM and SLP frameworks. The common feature of these frameworks is that a purely probabilistic component and a purely logical component are connected to produce a hybrid model. A hidden Markov model (HMM) is used as a running example. The Uniqueness Condition, which allows these frameworks to represent statistical models is discussed, and the consequences of using a weakened version of the Uniqueness Condition briefly explored. `Lazy' sampling, based on SLD-resolution, is discussed.

A general method for defining informative priors on statistical models is presented and applied specifically to the space of classification and regression trees. Our aim is towards a Bayesian approach to learning such models from data, with the Metropolis-Hastings algorithm used to sample from the posterior. We present some preliminary results where we empirically tested the methodology.

Leibniz's De incerti aestimatione, which contains his solution to the division problem, has not received much attention, let alone much appreciation. This is surprising because it is in this work that the definition of probability in terms of equally possible cases appears for the first time. The division problem is used to establish and test probability theory; it can be stated as follows: if two players agree to play a game in which one has to win a certain number of rounds in order to win the pool, but if they break the game off before either of them has won the required number of rounds, how should the pool be distributed? Our article has two aims: it provides the readers with the first English translation of De incerti aestimatione, and it also gives them a brief commentary that explains Leibniz's philosophical and mathematical concepts necessary in order to understand this work. The translation is as literal as possible throughout; it shows how Leibniz struggled at times to find a solution to the division problem and how he approached it from different angles. The commentary discusses Leibniz's views on four key concepts: fairness, hope, authority and possibility. The commentary then outlines how Leibniz attempted to solve the problem of division.

Relational data is equivalent to non-relational structured data. It is this equivalence which permits probabilistic models of relational data. Learning of probabilistic models for relational data is possible because one item of structured data is generally equivalent to many related data items. Succession and inclusion are two relations that have been well explored in the statistical literature. A description of the relevant statistical approaches is given. The representation of relational data via Bayesian nets is examined, and compared with PRMs. The paper ends with some cursory remarks on structured objects.

In Datalog, missing values are represented by Skolem constants. More generally, in logic programming missing values, or existentially-quantified variables, are represented by terms built from Skolem functors. In an analogy to probabilistic relational models (PRMs), we wish to represent the joint probability distribution over missing values in a database or logic program using a Bayesian network. This paper presents an extension of logic programs that makes it possible to specify a joint probability distribution over terms built from Skolem functors in the program. Our extension is based on constraint logic programming (CLP), so we call the extended language CLP( cal BN). We show that CLP( cal BN) subsumes PRMs; this greater expressivity carries both advantages and disadvantages for CLP( cal BN). We also show that algorithms from inductive logic programming (ILP) can be used with only minor modification to learn CLP( cal BN) programs. An implementation of CLP( cal BN) is publicly available as part of YAP Prolog at http://www.cos.ufrj.br/~vitor/Yap/clpbn.

Selected issues concerning the use of logical representations in machine learning of natural language are discussed. It is argued that the flexibility and expressivity of logical representations are particularly useful in more complex natural language learning tasks. A number of inductive logic programming (ILP) techniques for natural language are analysed including the CHILL system, abduction and the incorporation of linguistic knowledge, including active learning. Hybrid approaches integrating ILP with manual development environments and probabilistic techniques are advocatd.

Combined logical-probabilistic frameworks are very old; often the result of grand attempts to formulate a calculus of general reasoning. A careful account of the assumptions and achievements of these systems can help us address issues in contemporary logical-probabilistic frameworks. This paper aims to provide such an account drawing on the pioneering work of Leibniz and Boole. In Leibniz, we find the first account of epistemic probability in terms of possible worlds. In Boole, we see the extent to which a combined logical-probabilistic calculus is possible using a propositional representation.

Supervised machine learning and data mining tools have become popular for the analysis of gene expression microarray data. They have the potential to uncover new therapeutic targets for diseases, to predict how patients will respond to specific treatments, and to uncover regulatory relationships among genes in normal and disease situations. Comparative experiments are needed to identify the advantages of the leading supervised learning algorithms for microarray data, as well as to give direction in methodological decisions. This paper compares support vector machines, Bayesian networks, decision trees, boosted decision trees, and voting (ensembles of decision stumps) on a new microarray data set for cancer with over 100 samples. The paper provides evidence for several important lessons for mining microarray data, including: (1) Bayes nets and ensembles perform at least as well as other approaches but arguably provide more direct insight; (2) the common practice of throwing out low or negative average differences, or those accompanied by an absent call, is a mistake; (3) looking for consistent differences in expression may be more important than large differences.

We present a general framework for defining priors on model structure and sampling from the posterior using the Metropolis-Hastings algorithm. The key ideas are that structure priors are defined via a probability tree and that the proposal distribution for the Metropolis-Hastings algorithm is defined using the prior, thereby defining a cheaply computable acceptance probability. We have applied this approach to Bayesian net structure learning using a number of priors and proposal distributions. Our results show that these must be chosen appropriately for this approach to be successful.

Stochastic logic programs (SLPs) are logic programs with labelled clauses which define a log-linear distribution over refutations of goals. The log-linear distribution provides, by marginalisation, a distribution over variable bindings, allowing SLPs to compactly represent quite complex distributions. We analyse the fundamental statistical properties of SLPs addressing issues concerning infinite derivations, `unnormalised' SLPs and impure SLPs. After detailing existing approaches to parameter estimation for log-linear models and their application to SLPs, we present a new algorithm called failure-adjusted maximisation (FAM). FAM is an instance of the EM algorithm that applies specifically to normalised SLPs and provides a closed-form for computing parameter updates within an iterative maximisation approach. We empirically show that FAM works on some small examples and discuss methods for applying it to bigger problems.

Stochastic logic programs (SLPs) and the various distributions they define are presented with a stress on their characterisation in terms of Markov chains. Sampling, parameter estimation and structure learning for SLPs are discussed. The application of SLPs to Bayesian learning, computational linguistics and computational biology are considered. Lafferty's Gibbs-Markov models are compared and contrasted with SLPs.

This paper gives a brief introduction to a particular machine learning method known as inductive logic programming. It is argued that this method, unlike many current statistically based machine learning methods, implies a view of grammar learning that bears close affinity to the views linguists have of the logical problem of language acquisition. Two experiments in grammar learning using this technique are described, using a unification grammar formalism, and positive-only data.

In this extended abstract, rather than crossing the boundary between attribute-value and relational learning, we place ourselves above any such boundary and look down on the problem from the point of view of general principles of statistical inference. We do not pretend that this paper gives a full account of all relevant issues, but argue that starting from this generalised viewpoint and working down towards actual learning problems (e.g. decision tree learning, regression, ILP, etc) makes it easier to find the essential contrasts and similarities between different learning problems. Our primary goal (not achieved here) is to abstract away from superficial issues, such as the concrete syntactic representation of a problem or worse the sociological origin of an approach.

Algorithms for exact and approximate inference in stochastic logic programs (SLPs) are presented, based respectively, on variable elimination and importance sampling. We then show how SLPs can be used to represent prior distributions for machine learning, using (i) logic programs and (ii) Bayes net structures as examples. Drawing on existing work in statistics, we apply the Metropolis-Hasting algorithm to construct a Markov chain which samples from the posterior distribution. A Prolog implementation for this is described. We also discuss the possibility of constructing explicit representations of the posterior.

We use Inductive Logic Programming (ILP) within a chart-parsing framework for grammar learning. Given an existing grammar G, together with some sentences which G can not parse, we use ILP to find the ``missing'' grammar rules or lexical items. Our aim is to exploit the inductive capabilities of chart parsing, i.e. the ability to efficiently determine what is needed for a parse. For each unparsable sentence, we find actual edges and *needed edges*: those which are needed to allow a parse. The former are used as background knowledge for the ILP algorithm (P-Progol) and the latter are used as examples for the ILP algorithm. We demonstrate our approach with a number of experiments using context-free grammars and a feature grammar.

We report work on effectively incorporating linguistic knowledge into grammar induction. We use a highly interactive bottom-up inductive logic programming (ILP) algorithm to learn `missing' grammar rules from an incomplete grammar. Using linguistic constraints on, for example, head features and gap threading, reduces the search space to such an extent that, in the small-scale experiments reported here, we can generate and store all candidate grammar rules together with information about their coverage and linguistic properties. This allows an appealingly simple and controlled method for generating linguistically plausible grammar rules. Starting from a base of highly specific rules, we apply least general generalisation and inverse resolution to generate more general rules. Induced rules are ordered, for example by coverage, for easy inspection by the user and at any point, the user can commit to a hypothesised rule and add it to the grammar. Related work in ILP and computational linguistics is discussed.

This chapter introduces Inductive Logic Programming (ILP) and Learning Language in Logic (LLL). No previous knowledge of logic programming, ILP or LLL is assumed. Elementary topics are covered and more advanced topics are discussed. For example, in the ILP section we discuss subsumption, inverse resolution, least general generalisation, relative least general generalisation, inverse entailment, saturation, refinement and abduction. We conclude with an overview of this volume and pointers to future work.

We examine the vexed question of connections between logical and probabilistic reasoning. The reasons for making such a connection are examined. We give an account of recent work which uses loglinear models to make the connection. We conclude with an analysis of various existing approaches combining logic and probability.

Recent work on loglinear models in probabilistic constraint logic programming is applied to first-order probabilistic reasoning. Probabilities are defined directly on the proofs of atomic formulae, and by marginalisation on the atomic formulae themselves. We use Stochastic Logic Programs (SLPs) composed of labelled and unlabelled definite clauses to define the proof probabilities. We have a conservative extension of first-order reasoning, so that, for example, there is a one-one mapping between logical and random variables. We show how, in this framework, Inductive Logic Programming (ILP) can be used to induce the features of a loglinear model from data. We also compare the presented framework with other approaches to first-order probabilistic reasoning.

We use Inductive Logic Programming (ILP) within a chart-parsing framework for grammar learning. Given an existing grammar G, together with some sentences which G can not parse, we use ILP to find the ``missing'' grammar rules or lexical items. Our aim is to exploit the inductive capabilities of chart parsing, i.e. the ability to efficiently determine what is needed for a parse. For each unparsable sentence, we find actual edges and *needed edges*: those which are needed to allow a parse. The former are used as background knowledge for the ILP algorithm (P-Progol) and the latter are used as examples for the ILP algorithm. We demonstrate our approach with a number of experiments using context-free grammars and a feature grammar.

We consider the task of tagging Slovene words with morphosyntactic descriptions (MSDs). MSDs contain not only part-of-speech information but also attributes such as gender and case. In the case of Slovene there are 2,083 possible MSDs. P-Progol was used to learn morphosyntactic disambiguation rules from annotated data (consisting of 161,314 examples) produced by the MULTEXT-East project. P-Progol produced 1,148 rules taking 36 hours. Using simple grammatical background knowledge, e.g. looking for case disagreement, P-Progol induced 4,094 clauses in eight parallel runs. These rules have proved effective at detecting and explaining incorrect MSD annotations in an independent test set, but have not so far produced a tagger comparable to other existing taggers in terms of accuracy.

The aim of these notes is to analyse ILP methods which have been applied to NLP, drawing exclusively on work conducted in Europe.

A system for `tagging' words with their part-of-speech (POS) tags is constructed. The system has two components: a lexicon containing the set of possible POS tags for a given word, and rules which use a word's context to eliminate possible tags for a word. The Inductive Logic Programming (ILP) system Progol is used to induce these rules in the form of definite clauses. The final theory contained 885 clauses. For background knowledge, Progol uses a simple grammar, where the tags are terminals and predicates such as nounp (noun phrase) are nonterminals. Progol was altered to allow the caching of information about clauses generated during the induction process which greatly increased efficiency. The system achieved a per-word accuracy of 96.4% on known words drawn from sentences without quotation marks. This is on a par with other tagging systems induced from the same data [DaeZavBerGil96-WVLC96,Bri94-AAAI94,CutKupPedSib92-ANLP92] which all have accuracies in the range 96-97%. The per-sentence accuracy was 49.5%.

We summarise recent work on using Inductive Logic Programming (ILP) for Natural Language Processing (NLP). ILP performs learning in a first-order logical setting, and is thus well-suited to induce over the various structured representations used in NLP. We present Stochastic Logic Programs (SLPs) and demonstrate their use in ILP when learning from positive examples only. We also give accounts of work on learning grammars from children's books and part-of-speech tagging.

Elementary results concerning the connections between deductive relations and probabilistic support are given. These are used to show that Popper-Miller's result is a special case of a more general result, and that their result is not ``very unexpected'' as claimed. According to Popper-Miller, a purely inductively supports b only if they are ``deductively independent''---but this means that neg a vdash b. Hence, it is argued that viewing induction as occurring only in the absence of deductive relations, as Popper-Miller sometimes do, is untenable. Finally, it is shown that Popper-Miller's claim that deductive relations determine probabilistic support is untrue. In general, probabilistic support can vary greatly with fixed deductive relations as determined by the relevant Lindenbaum algebra.

The effect of noise in a dichotomous process is studied from the Bayesian viewpoint. Winkler's approximation to the posterior distribution in the presence of noise is shown to break down badly near the limits of its application. Information loss is measured using effective sample size. An account of the relationship between effective sample size/information loss and sampling data is given which differs sharply from that of previous work in this area.

We consider algorithms for learning functions f: X rightarrow Y, where X and Y are finite, and there is assumed to be no noise in the data. Learning algorithms, alg , are connected with galg , the set of prior probability distributions for which they are optimal. A method for constructing galg from alg is given and the relationship between the various galg is discussed. Improper algorithms are identified as those for which galg has zero volume. Improper algorithms are investigated using linear algebra and two examples of improper algorithms are given. This framework is then applied to the question of choosing between competing algorithms. ``Leave-one-out'' cross-validation is hence characterised as a crude method of ML-II prior selection. We conclude by examining how the mathematical results bear on practical problems and by discussing related work, as well as suggesting future work.

Various ways of estimating probabilities, mainly within the Bayesian framework, are discussed. Their relevance and application to machine learning is given, and their relative performance empirically evaluated. A method of accounting for noisy data is given and also applied. The reliability of estimates is measured by a significance measure, which is also empirically tested. We briefly discuss the use of likelihood ratio as a significance measure.

The first chapter presents Bayesian confirmation theory. We then construct infinitesimal numbers and use them to represent the probability of unrefuted hypotheses of standard probability zero. Popper's views on the nature of hypotheses, of probability and confirmation are criticised. It is shown that Popper conflates total confirmation with weight of evidence. It is argued that Popper's corroboration can be represented in a Bayesian formalism. Popper's propensity theory is discussed. A modified propensity interpretation is presented where probabilities are defined relative to descriptions of generating conditions. The logical interpretation is briefly discussed and rejected. A Bayesian account of estimating the values of objective probabilities is given, and some of its properties are proved. Belief functions are then compared with probabilities. It is concluded that belief functions offer a more elegant representation of the impact of evidence. Both measures are then discussed in relation to various betting procedures designed to elicit their values from an individual's belief state. De Finetti's arguments concerning `coherence' are discussed. It is then shown that it is not possible to use bets to derive belief function values unless the better is allowed to vary the amount of the stake. Hume's thinking on induction is discussed. It is argued that some of the problems of Popper's philosophy derive from Hume's. The Popper-Miller argument is presented and criticised. It is concluded that the core of the argument is valid, but of limited applicability. The correspondence between probabilistic support and deductive relations is discussed. There are two appendices. The first criticises Popper's view on the connection between the content and testability of a hypothesis. The second concerns a nonstandard probability measure proposed in 1967.