Markov Logic in Infinite Domains
This work addresses a foundational problem in AI for researchers in probabilistic logic and infinite models, though it is incremental as it builds on existing Markov logic frameworks.
The paper tackles the limitation of Markov logic networks (MLNs) to finite domains by extending them to infinite domains using Gibbs measures, showing that MLNs admit Gibbs measures under conditions like finite neighbors and small weights, and relating this to phenomena like phase transitions and satisfiability in first-order logic.
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.