Lecture Notes in Computer Science vol:4894 pages:24-24
International Conference on Inductive Logic Programming edition:17 location:Corvallis, USA date:19-21 June 2007
There is an increasing interest in upgrading Bayesian networks to the relational case, resulting in directed probabilistic logical models. Many formalisms to describe such models have been introduced and learning algorithms have been developed for several such formalisms. Most of these algorithms are upgrades of the traditional structure-search algorithm for Bayesian networks. However, in 2005 an alternative algorithm for learning Bayesian networks, ordering-search, was introduced that performs at least as well as structure-search while usually being faster. This motivated us to develop an ordering-search algorithm for learning directed probabilistic logical models.
Our ordering-search algorithm is based on the observation that learning a model is relatively easy when an ordering on the predicates is given and each predicate has as potential parents only the predicates that precede it in the ordering (this implies that only non-recursive models are learned). Given such an ordering, we can learn for each predicate separately which of its potential parents are the effective parents. This can simply be done by learning a logical probability tree for that predicate with as inputs all potential parents. The effective parents are then determined as all the predicates that are effectively used in the learned tree. Since often no ordering on the predicates is known beforehand, ordering-search performs hillclimbing through the space of orderings to determine the optimal ordering, in each step applying the above procedure.
We implemented the above ordering-search algorithm for the formalism Logical Bayesian Networks. We also implemented a structure-search algorithm that is very similar to the existing structure-search algorithms for related formalisms. We experimentally compared both algorithms in terms of quality (likelihood of test data) and compactness of the learned models and computational efficiency. We performed experiments on two relational domains: a synthetic domain for which we generated datasets of varying size by sampling from a given model and the UWCSE dataset.
Our experimental results show that ordering-search is competitive with structure-search in terms of quality and compactness of the learned models. However, ordering-search is significantly faster. We conclude that ordering-search is a good alternative to structure-search for learning directed probabilistic logical models.