DOC PREVIEW
BLOG: Probabilistic Models with Unknown Objects

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1 BLOG: Probabilistic Models with UnknownObjectsBrian MilchComputer Science DivisionUniversity of California at Berkeley, [email protected]://www.cs.berkeley.edu/∼milchBhaskara MarthiComputer Science DivisionUniversity of California at Berkeley, [email protected] keley.eduhttp://www.cs.berkeley.edu/∼bhaskaraStuart RussellComputer Science DivisionUniversity of California at Berkeley, [email protected]://www.cs.berkeley.edu/∼russellDavid SontagDepartment of Electrical Engineering and Computer ScienceMassachus etts I nstitute of Technology, [email protected]://people.csail.mit.edu/dsontagDaniel L. OngComputer Science DivisionUniversity of California at Berkeley, [email protected] erkeley.eduhttp://www.ocf.berkeley.edu/∼dlongAndrey KolobovComputer Science DivisionUniversity of California at Berkeley, [email protected] BLOG: Probabilistic Models with Unknown Objects1.1 IntroductionHuman beings and AI systems must convert sensory input into some understandingof what is going on in the world around them. That is, they must make inferencesabout the objects and events that underlie their observations. No pre-specified listof objects is given; the agent must infer the existence of objects that were not knowninitially to exist.In many AI systems, this problem of unknown objects is engineered away orresolved in a preprocessing step. However, there are important applications wherethe problem is unavoidable. Population estimation, for example, involves counting apopulation by sampling from it randomly and measuring how often the same objectis resampled; this would be pointless if the set of objects were known in advance.Record linkage, a task under taken by an industry of more than 300 companies,involves matching entries across multiple databases. These companies exist becauseof uncertainty about the mapping from observations to underlying objects. Finally,multi-target tracking systems perform data association, connecting, say, radar blipsto hypothesized aircraft.Probability models for such tasks are not new: Bayesian models for data asso-ciation have been used since the 1960s [Sittler, 1964]. The models are written inEnglish and mathematical notation and converted by hand into special-purposecode. This can result in inflexible models of limited expressiveness—for example,tracking systems assume independent trajectories with linear dynamics, and recordlinkage systems assume a naive Bayes model for fields in records. It seems natural,therefore, to seek a formal language in which to express probability models thatallow for unknown objects.Recent achievements in the field of probabilistic graphical models [Pearl, 1988]illustrate the benefits that can be exp ected from adopting a formal language:general-purpose inference algorithms, more sophisticated models, and techniquesfor automated model selection (structure learning). However, graphical modelsonly describe fixed sets of random variables with fixed dependencies among them;they become awkward in scenarios with unknown objects. There has also beensignificant work on first-order probabilistic languages (FOPLs ), which explicitlyrepresent objects and the relations between them. We review some of this workin Section 1.7. However, most FOPLs make the assumptions of unique names,requiring that the symbols or terms of the language all refer to distinct objects,and domain closure, requiring that no objects exist besides the ones referred toby terms in the language. These assumptions are inappropriate for problems suchas multi-target tracking, where we may want to reason about objects that areobserved multiple times or that are not observed at all. Those FOPLs that dosupport unknown objects often do so in limited and ad hoc ways. In this chapter, wedescribe Bayesian logic (Blog) [Milch et al., 2005a], a new language that compactlyand intuitively defines probability distributions over outcomes with varying sets ofobjects.1.2 Examples 3We begin in Section 1.2 with three example problems, each of which involvespossible worlds with varying object sets and identity uncertainty. We show Blogmodels for these problems and give initial, informal descriptions of the probabilitydistributions that they define. Section 1.3 observes that the possible worlds in thesescenarios are naturally viewed as model structures of first-order logic. It then definesprecisely the set of possible worlds corresponding to a Blog model. The key ideais a generative process that constructs a world by adding objects whose existenceand properties depend on those of objects already created. In such a process, theexistence of objects may be governed by many random variables, not just a singlepopulation size variable. Section 1.4 discusses exactly how a Blog model specifiesa probability distribution over possible worlds.Section 1.5 solves a previously unnoticed “probabilistic Skolemization” problem:how to specify evidence about objects—such as radar blips—that one didn’t knowexisted. Finally, Section 1.6 briefly discusses inference in unbounded outcomespaces, stating a sampling algorithm and a completeness theorem for a large classof Blog models and giving experimental results on one particular model.1.2 ExamplesIn this section we examine three typical scenarios with unknown objects—simplifiedver sions of the population estimation, record linkage, and multitarget trackingproblems mentioned above. In each case, we provide a short Blog model that,when combined with a suitable inference engine, constitutes a working solution forthe problem in question.Example 1.1An urn contains an unknown number of balls—say, a number chosen from a Poissondistribution. Balls are equally likely to be blue or green. We draw some balls fromthe urn, observing the color of each and replacing it. We cannot tell two identicallycolored balls apart; furthermore, observed colors are wrong with probability 0.2.How many balls are in the urn? Was the same ball drawn twice?The Blog model for this problem, shown in Figure 1.1, describes a stochasticprocess for generating worlds. The first 4 lines introduce the types of objects in theseworlds—colors, balls, and draws—and the functions that can be applied to theseobjects. For each function, the model specifies a type signature in a syntax similar tothat of C or Java. For instance, line 2 specifies that TrueColor is a random functionthat takes a single argument of type Ball and returns a value of type Color.


BLOG: Probabilistic Models with Unknown Objects

Download BLOG: Probabilistic Models with Unknown Objects
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view BLOG: Probabilistic Models with Unknown Objects and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view BLOG: Probabilistic Models with Unknown Objects 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?