Nonparametric Bayesian Logic

Peter Carbonetto, Jacek Kisynski, Nando de Freitas, David Poole

Abstract

Probabilistic programming languages like Bayesian Logic (BLOG) have traditionally required explicit prior distributions over the number of objects in a model. This paper introduces Nonparametric Bayesian Logic (NP-BLOG), which integrates Dirichlet processes into the BLOG framework. By utilizing the stick-breaking construction, NP-BLOG allows for the dynamic inference of an unknown number of objects directly from data. We demonstrate the efficacy of this approach on an unsupervised citation matching task using the CiteSeer dataset, where NP-BLOG achieves high accuracy with significantly reduced modeling complexity.

Introduction

Reasoning about worlds with an unknown number of objects is a fundamental challenge in artificial intelligence. While languages like BLOG provide a framework for such reasoning, they often necessitate rigid, data-independent priors (e.g., Poisson distributions) for the population size. In many real-world applications, such as resolving identities in large, noisy databases, such priors are difficult to specify accurately.

NP-BLOG addresses this by incorporating Bayesian nonparametrics. Specifically, it leverages Dirichlet Process (DP) mixtures to model collections of unknown objects. This allows the model to "grow" with the data, inferring the number of unique entities—such as authors or publications—without a hardcoded upper bound.

Methodology: From Syntax to Generative Process

The core of NP-BLOG is its ability to map high-level logic statements to nonparametric generative processes. The language relies on the stick-breaking construction of Dirichlet processes to ensure that the resulting graphical models are mathematically well-defined and have a countable set of ancestors for every random variable.

Syntax, generative process, and graphical model for citation title matching in NP-BLOG.

As shown in the figure above, a few lines of syntax can define a complex hierarchical model. The system automatically handles the procedural semantics, mapping dependency statements into a generative process that utilizes auxiliary variables for efficient inference. For identity resolution, NP-BLOG employs a blocked Gibbs sampling algorithm, hiding the underlying mathematical complexity from the user.

Evaluation and Key Results

The authors evaluated NP-BLOG on the task of unsupervised citation matching using subsets of the CiteSeer dataset. The goal was to cluster noisy citation strings into groups representing unique underlying publications across four research areas: Face, Reinforcement Learning, Reasoning, and Constraint Satisfaction.

Performance comparison of NP-BLOG against other methods on the CiteSeer dataset.

The results, summarized in the table above, show that NP-BLOG achieves strong clustering accuracy, ranging from 0.84 to 0.93. While it slightly trails highly tuned supervised models like CRF-Seg, NP-BLOG operates entirely without labeled training data and uses much simpler string metrics. Furthermore, the posterior distribution over the number of publications inferred by the model closely aligned with the ground truth.

Discussion and Conclusion

A key insight of this work is that infinite exchangeability serves as the mathematical bridge between first-order logic and Dirichlet processes. By abstracting the complexities of nonparametric statistics, NP-BLOG allows domain experts to specify models intuitively.

However, limitations remain. The convergence of MCMC chains for these models is still difficult to determine formally, and the assumption of exchangeability may not hold in all domains. Future research will focus on more efficient online inference methods and exploring hybrid models that combine parametric and nonparametric distributions.

Summary updated

Abstract

The Bayesian Logic (BLOG) language was recently developed for defining first-order probability models over worlds with unknown numbers of objects. It handles important problems in AI, including data association and population estimation. This paper extends BLOG by adopting generative processes over function spaces - known as nonparametrics in the Bayesian literature. We introduce syntax for reasoning about arbitrary collections of objects, and their properties, in an intuitive manner. By exploiting exchangeability, distributions over unknown objects and their attributes are cast as Dirichlet processes, which resolve difficulties in model selection and inference caused by varying numbers of objects. We demonstrate these concepts with application to citation matching.
BibTeX
@inproceedings{carbonetto2005nonparametric,
  author = {Peter Carbonetto and Jacek Kisynski and Nando de Freitas and David Poole},
  title = {{Nonparametric Bayesian Logic}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2005},
}
Figure