Nonparametric Bayesian LogicPeter Carbonetto, Jacek Kisy´nski, Nando de Freitas and David PooleDept. of Computer ScienceUniversity of British ColumbiaVancouver, BC, Canada V6T 1Z4AbstractThe Bayesian Logic (BLOG) language was re-cently developed for defining first-order proba-bility models over worlds with unknown num-bers of objects. It handles important problemsin AI, including data association and populationestimation. This paper extends BLOG by adopt-ing generative processes over function spaces —known as nonparametrics in the Bayesian liter-ature. We introduce syntax for reasoning aboutarbitrary collections of objects, and their prop-erties, in an intuitive manner. By exploitingexchangeability, distributions over unknown ob-jects and their attributes are cast as Dirichlet pro-cesses, which resolve difficulties in model selec-tion and inference caused by varying numbers ofobjects. We demonstrate these concepts with ap-plication to citation matching.1 IntroductionProbabilistic first-order logic has played a prominent rolein recent attempts to develop more expressive models inartificial intelligence [3, 4, 6, 8, 15, 16, 17]. Among these,the Bayesian logic (BLOG) approach [11] stands out forits ability to handle unknown numbers of objects and dataassociation in a coherent fashion, and it does not assumeunique names and domain closure.A BLOG model specifies a probability distribution overpossible worlds of a typed, first-order language. That is,it defines a probabilistic model over objects and their at-tributes. A model structure corresponds to a possible world,which is obtained by extending each object type and inter-preting each function symbol. Objects can either be “guar-anteed”, meaning the extension of a type is fixed, or theycan be generated from a distribution. For example, in theaircraft tracking domain [11] the times and radar blips areknown, and the number of unknown aircraft may vary inpossible worlds. BLOG as a case study provides a strongargument for Bayesian hierarchical methodology as a basisfor probabilistic first-order logic.BLOG specifies a prior over the number of objects. Inmany domains, however, it is unreasonable for the user tosuggest such a proper, data-independent prior. An inves-tigation of this issue was the seed that grew into our pro-posal for Nonparametric Bayesian Logic, or NP-BLOG,a language which extends the original framework devel-oped in [11]. NP-BLOG is distinguished by its ability tohandle object attributes that are generated by unboundedsets of objects. It also permits arbitrary collections of at-tributes drawn from unbounded sets. We extend the BLOGlanguage by adopting Bayesian nonparametrics, which areprobabilistic models with infinitely many parameters [1].The statistics community has long stressed the need formodels that avoid commiting to restrictive assumptions re-garding the underlying population. Nonparametric modelsspecify distributions over function spaces — a natural fitwith Bayesian methods, since they can be incorporated asprior information and then implemented at the inferencelevel via Bayes’ theorem. In this paper, we recognize thatBayesian nonparametric methods have an important role toplay in first-order probabilistic inference as well. We startwith a simple example that introduces some concepts nec-essary to understanding the main points of the paper.Consider a variation of the problem explored in [11]. Youhave just gone to the candy store and have bought a boxof Smarties (or M&Ms), and you would like to discoverhow many colours there are (while avoiding the temptationto eat them!). Even though there is an infinite number ofcolours to choose from, the candies are coloured from a fi-nite set. Due to the manufacturing process, Smarties maybe slightly discoloured. You would like to discover the un-known (true) set of colours by randomly picking Smartiesfrom the box and observing their colours. After a certainnumber of draws, you would like to answer questions suchas: How many different colours are in the box? Do twoSmarties have the same colour? What is the probabilitythat the first candy you select from a new box is a colouryou have never seen before?The graphical representation of the BLOG model is shownin Fig. 1a. The number of Smarties of different colours,n(Smartie), is chosen from a Poisson distribution withFigure 1: (a) The BLOG and (b) NP-BLOG graphical mod-els for counting Smarties. The latter implements a Dirichletprocess mixture. The shaded nodes are observations.mean γSmartie. A colour for each Smartie s is drawnfrom the distribution HColourDist. Then, for every draw d,zSmartieDrawn[d] is drawn uniformly from the set of Smar-ties {1, . . . , n(Smartie)}. Finally, we sample the observed,noisy colour of each draw conditioned on zSmartieDrawn[d]and the true colours of the Smarties.The NP-BLOG model for the same setting is shown inFig. 1b. The true colours of an infinite sequence of Smar-ties s are sampled from HColourDist. πSmartieis a distri-bution over the choice of coloured Smarties, and is sam-pled from a uniform Dirichlet distribution with parameterαSmartie. Once the Smarties and their colours are gener-ated, the true Smartie for draw d, represented by the indi-cator zSmartieDrawn[d] = s, is sampled from the distributionof Smarties πSmartie. The last step is to sample the observedcolour, which remains the same as in the BLOG model.One advantage of the NP-BLOG model is that it determinesa posterior over the number of Smarties colours withouthaving to specify a prior over n(Smartie). This is impor-tant since this prior is difficult to specify in many domains.A more significant advantage is that NP-BLOG explicitlymodels a distribution over the collection of Smarties. Thisis not an improvement in expressiveness — one can alwaysreverse engineer a parametric model given a target nonpara-metric model in a specific setting. Rather, nonparametricsfacilitate the resolution of queries on unbounded sets, suchas the colours of Smarties. This plays a key role in mak-ing inference tractable in sophisticated models with objectproperties that are themselves unbounded collections of ob-jects. This is the case with the citation matching model inSec. 3.1, in which publications have collections of authors.The skeptic might still say, despite these advantages, thatit is unreasonable to expect a domain expert to implementnonparametrics considering the degree of effort requiredto grasp these abstract notions. We show
View Full Document
Unlocking...