Structure Learning of Markov Logic Networks through Iterated Local Search
Marenglen Biba
and
Stefano Ferilli
and
Floriana Esposito
Abstract:
Many real-world applications of AI require both probability and
first-order logic to deal with uncertainty and structural complexity.
Logical AI has focused mainly on handling complexity, and statistical
AI on handling uncertainty. Markov Logic Networks (MLNs)
are a powerful representation that combine Markov Networks (MNs)
and first-order logic by attaching weights to first-order formulas
and viewing these as templates for features of MNs. State-of-theart
structure learning algorithms of MLNs maximize the likelihood
of a relational database by performing a greedy search in the space
of candidates. This can lead to suboptimal results because of the
incapability of these approaches to escape local optima. Moreover,
due to the combinatorially explosive space of potential candidates
these methods are computationally prohibitive. We propose a novel
algorithm for learning MLNs structure, based on the Iterated Local
Search (ILS) metaheuristic that explores the space of structures
through a biased sampling of the set of local optima. The algorithm
focuses the search not on the full space of solutions but on a smaller
subspace defined by the solutions that are locally optimal for the optimization
engine. We show through experiments in two real-world
domains that the proposed approach improves accuracy and learning
time over the existing state-of-the-art algorithms.
Download:
Paper (PDF)