Transcript PowerPoint

BLOG: Probabilistic Models
with Unknown Objects
Brian Milch, Bhaskara Marthi, Stuart Russell,
David Sontag, Daniel L. Ong, Andrey Kolobov
University of California at Berkeley
Basic Task
• Given observations, make inferences about
underlying objects
• Difficulties:
– Don’t know list of objects in advance
– Don’t know when same object observed twice
(identity uncertainty / data association / record linkage)
Handling Unknown Objects
• Standard practice: special-purpose
algorithms to resolve identity uncertainty
• Goal: Resolve identity uncertainty by
inference in probabilistic model
• Bayesian LOGic (BLOG): representation
language for models with
– Unknown set of objects
– Unknown map from observations to objects
Outline
• Motivating applications
• Bayesian Logic (BLOG)
– Syntax
– Semantics
• Proof-of-concept experimental results
Example 1: Aircraft Tracking
Detection
Failure
Example 1: Aircraft Tracking
Unobserved
Object
False
Detection
Example 2: Bibliographies
Russell, Stuart and Norvig, Peter. Articial Intelligence. Prentice-Hall, 1995.
S. Russel and P. Norvig (1995). Artificial Intelligence: A Modern
Approach. Upper Saddle River, NJ: Prentice Hall.
Simple Example:
Balls in an Urn
P(n balls in urn)
P(n balls in urn | draws)
Draws
(with replacement)
1
2
3
4
Possible Worlds
3.00 x 10-3
7.61 x 10-4
1.19 x 10-5
…
Draws
Draws
2.86 x 10-4
Draws
1.14 x 10-12
…
Draws
…
…
Draws
Distributions over First-Order
Structures
• Idea goes back to Gaifman [1964]
• Halpern [1990] defines language for stating constraints
on such distributions
– But not specifying a distribution uniquely
• Logic programming approaches [Poole 1993;
Sato & Kameya 2001; Kersting & De Raedt 2001] define unique
distributions, but assume unique names and domain
closure
• PRMs [Koller & Pfeffer 1998] have special constructs for
number uncertainty, existence uncertainty
• BLOG: Unified syntax for distributions over worlds with:
– Varying sets of objects
– Varying mappings from observations to objects
See also MEBN [Laskey and da Costa, UAI 2005]
Generative Process for
Possible Worlds
Draws
(with replacement)
1
2
3
4
BLOG Model for Urn and Balls
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
#Ball ~ Poisson[6]();
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
BallDrawn(d) ~ UniformChoice({Ball b});
ObsColor(d)
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
BLOG Model for Urn and Balls
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
header
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
#Ball ~ Poisson[6]();
number statement
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
BallDrawn(d) ~ UniformChoice({Ball b});
ObsColor(d)
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
dependency
statements
BLOG Model for Urn and Balls
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3,? Draw4;
Identity uncertainty: BallDrawn(Draw1) = BallDrawn(Draw2)
#Ball ~ Poisson[6]();
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
BallDrawn(d) ~ UniformChoice({Ball b});
ObsColor(d)
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
BLOG Model for Urn and Balls
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
Arbitrary conditional
probability distributions
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
#Ball ~ Poisson[6]();
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
BallDrawn(d) ~ UniformChoice({Ball b});
CPD arguments
ObsColor(d)
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
BLOG Model for Urn and Balls
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
#Ball ~ Poisson[6]();
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
BallDrawn(d) ~ UniformChoice({Ball b});
Context-specific
dependence
ObsColor(d)
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
BLOG Model for Urn and Balls
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
#Ball ~ Poisson[6]();
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
BallDrawn(d) ~ UniformChoice({Ball b});
ObsColor(d)
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
Generative Process for
Aircraft Tracking
Existence
of radar blips depends
on
Sky
Radar
existence and locations of aircraft
BLOG Model for Aircraft Tracking
Source
…
a
#Aircraft ~ NumAircraftDistrib();
t
Blips
2
State(a, t)
if t = 0 then ~ InitState()
Time
else ~ StateTransition(State(a, Pred(t)));
#Blip: (Source, Time) -> (a, t)
~ NumDetectionsDistrib(State(a, t));
#Blip: (Time) -> (t)
~ NumFalseAlarmsDistrib();
Blips
ApparentPos(r)
t 2
if (Source(r) = null) then ~ FalseAlarmDistrib()
else ~ ObsDistrib(State(Source(r), Time(r)));
Time
Declarative Semantics
• What is the set of possible worlds?
• What is the probability distribution over
worlds?
What Exactly Are the Objects?
• Objects are tuples that encode generation
history
• Aircraft: (Aircraft, 1), (Aircraft, 2), …
• Blip from (Aircraft, 2) at time 8:
(Blip, (Source, (Aircraft, 2)), (Time, 8), 1)
Basic Random Variables (RVs)
• For each number statement and tuple of
generating objects, have RV for
number of objects generated
• For each function symbol and tuple of
arguments, have RV for function value
• Lemma: Full instantiation of these RVs
uniquely identifies a possible world
Another Look at a BLOG Model
…
#Ball ~ Poisson[6]();
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
BallDrawn(d) ~ UniformChoice({Ball b});
ObsColor(d)
if !(BallDrawn(d) = null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
Dependency and number statements
define CPDs for basic RVs
Just a Bayes Net?
#Ball
TrueColor(B1)
TrueColor(B2)
ObsColor(D1)
TrueColor(B3)
…
Infinite parent set
BallDrawn(D1)
Standard BN results no longer apply
Probability Distribution
• BLOG model specifies:
– Conditional distributions for basic RVs
– Factorization properties for certain finite
instantiations of basic RVs
• Theorem: Under certain conditions
(analogous to BN acyclicity), every BLOG
model defines unique distribution over
possible worlds
Inference
• Does infinite set of basic RVs prevent inference?
• No: Sampling algorithm only needs to instantiate
finite set of relevant variables
• Algorithms:
– Rejection sampling [this paper]
– Guided likelihood weighting [Milch et al., AI/Stats 2005]
• Theorem: For large class of BLOG models,
sampling algorithms converge to correct
probability for any query, using finite time per
sampling step
Proof-Of-Concept Experiment
• Given 10 draws,
all appearing blue
• 5 runs of 100,000
samples each
0.18
0.16
Probability
0.14
0.12
prior
0.1
0.08
0.06
0.04
posterior
0.02
0
0
5
10
15
Number of Balls
20
25
Conclusions
• Bayesian logic (BLOG) models define
unique distributions over first-order model
structures with
– Varying sets of objects
– Varying mappings from terms to objects
• Future work:
– Practical inference algorithms
– Applications to text understanding
– Applications to situation awareness (DBLOG)