Markov Logic in Infinite Domains
  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.
