Markov Logic in Infinite Domains
Parag Singla
and
Pedro Domingos
Abstract:
Combining first-order logic and probability has
long been a goal of AI. Markov logic (Richardson
& Domingos, 2006) accomplishes this by attaching
weights to first-order formulas and viewing
them as templates for features of Markov
networks. Unfortunately, it does not have the
full power of first-order logic, because it is only
defined for finite domains. This paper extends
Markov logic to infinite domains, by casting it
in the framework of Gibbs measures (Georgii,
1988). We show that a Markov logic network
(MLN) admits a Gibbs measure as long as each
ground atom has a finite number of neighbors.
Many interesting cases fall in this category. We
also show that an MLN admits a unique measure
if the weights of its non-unit clauses are small
enough. We then examine the structure of the set
of consistent measures in the non-unique case.
Many important phenomena, including systems
with phase transitions, are represented by MLNs
with non-unique measures. We relate the problem
of satisfiability in first-order logic to the
properties of MLN measures, and discuss how
Markov logic relates to previous infinite models.
Download:
Paper (PDF)
Technical Report (PDF)