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.
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.
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