Full text:

Available as PDF.

URI: http://hdl.handle.net/1979/1833.

Abstract:

Machine learning is concerned with algorithms that allow computers to learn models from data. An important application of machine learning is knowledge discovery, which is the automated extraction of useful patterns from data. Two kinds of models that have received special attention are probabilistic models and logical models (models using elements of logic programming or first-order logic). The advantage of the former is the ability to model stochastic or noisy data, the advantage of the latter is the ability to handle relational data. There is a growing interest in combining these advantages, by using so-called probabilistic logical models.

In this dissertation we focus on directed probabilistic logical models. We introduce Logical Bayesian Networks (LBNs), a formalism for representing such models, and compare it to related formalisms. The most important difference with other formalisms is that in LBNs we quantify probabilistic dependencies using logical probability trees (instead of conditional probability tables and combining rules). This has the advantage that context-specific independencies can be captured.

The main part of this dissertation is concerned with the development of algorithms for learning LBNs from relational data. Since probability trees are a central component of LBNs, we need an accurate and efficient learning algorithm for probability trees. For this reason we first perform an extensive experimental comparison of several such algorithms, using relational data as well as attribute-value (non-relational) data.

We introduce two algorithms for learning non-recursive LBNs. The first algorithm is based on searching over directed acyclic graphs and is relatively close to existing learning algorithms for formalisms related to LBNs. The second algorithm is based on searching over orderings. Experiments on relational data show that the two algorithms are comparable in terms of the quality of the learned models and that searching over orderings is significantly more efficient.

In a next step we show how the above algorithms can be used for learning recursive LBNs under a simplifying assumption. We also introduce an algorithm for learning recursive LBNs which does not require this assumption. We do this by generalizing the algorithm for searching over orderings. Experiments on relational data show that the new algorithm can indeed learn useful recursive dependencies, but for learning non-recursive dependencies the original algorithm is superior.

Doctoral jury: