Transcript Balls in an urn

BLOG: Probabilistic Models
with Unknown Objects
Brian Milch, Bhaskara Marthi, Stuart Russell, David Sontag, Daniel L. Ong and
Andrey Kolobov
Presentation created by Adi Ashour in context
of seminar in soft logic - 236801
Acknowledgment: Brian Milch
https://sites.google.com/site/bmilch/talks
This talk’s topics
• Motivation for BLOG
• A few examples
• BLOG syntax and semantics
• Inference Algorithm
Self educated
robot
Record
linkage
Motivation
Population
estimation
Self educated
robot
Record
linkage
Motivation
Population
estimation
Artificial Intelligent systems
In the real world
The world keeps
changing - uncertain
The world contains
objects
First – order
probabilistic
models
Artificial Intelligent systems
In the real world
BLOG
=
The world keeps
The world contains
changing - uncertain
objects
Bayesian Logic
First – order
probabilistic
models
Lets see a few examples
• First we’ll have a look at the balls in an urn
problem.
• Second we’ll see the aircraft tracking problem.
• Then, we’ll try to see the difference and
similarity between them.
P(n balls in urn)
Balls in an urn
P(n balls in urn | draws)
Draws
(with replacement)
1
2
3
4
 An urn contains an
unknown number
of balls.
 We drew some
balls from the urn,
observing the
color of each and
replacing it.
 Observed colors
are wrong with
probability 0.2.
How many balls are
in the urn?
3.00 x 10-3
Balls in an urn
Possible Worlds
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
Generative process for
Possible Worlds
Draws
(with replacement)
1
2
3
4
Balls in an urn
Poisson
distribution with
parameter 𝜆:
𝜆𝑘 −𝜆
𝑃 𝑋=𝑘 = 𝑒
𝑘!
Balls are equally
likely to be blue or
green
Observed colors
are wrong with
probability 0.2
Aircraft tracking
Aircraft tracking
Might not be
the correct diagnostic
Aircraft tracking
Another possibility
Unobserved
Object
False
Detection
Generative process for
Aircraft tracking
False
blip
Existence of radar blips depends
on
Sky
Radar
existence and locations of aircraft
Aircraft tracking
Source
a:
t:
2
Time
step depends on its
state at the
previous
Blips time step
Aircraft tracking
An unknown number of aircraft exist in some volume of airspace.
Blips
t:
2
An aircraft’s state (position and velocity) at each time step
depends on its state at the previous time step.
Time
We observe the area with radar: aircraft may appear as
identical blips on a radar screen. Each blip gives the
approximate position of the aircraft that generated it. However,
some blips may be
some blips may be false detections, and some aircraft may not
false detections, and
be detected.
some aircraft may
What aircrafts exist, and what are their trajectories?
not be detected
Are there any aircraft that are not observed?
Lets compare what we’ve seen
• Differences:
In the ball problem, we have a guaranteed number
of draws. In the aircraft problem we have a
changing number of blips.
The balls can only be blue or green. The aircraft
can be many things (all blips are the same) and their
trajectory isn’t easy to determine.
Lets take a closer
look:
Balls in an urn
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
Other types are also
provided automatically
Random functions for
uncertainty of the world
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
Guaranteed facts that
exist in every possible
world
TrueColor(b) ~ TabularCPD[[0.5, 0.5]]();
#Ball ~ Poisson[6]();
BallDrawn(d) ~ UniformChoice({Ball b});
ObsColor(d)
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
Balls in an urn
type Color;
type Ball;
type Draw;
random Color TrueColor(Ball);
random Ball BallDrawn(Draw);
random Color ObsColor(Draw);
header
Our world
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
Balls in an urn
type Color;
type Ball;
type Draw;
A component of
the unknown
random Color TrueColor(Ball);
objects in the
random Ball BallDrawn(Draw);
model
random Color ObsColor(Draw);
header
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
#Ball ~ Poisson[6]();
Number statement:
number statement
#type_name ~ expression
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
Balls in an urn
type Color;
type Ball;
#Blip: (Source,
Time) type Draw;
→ (a, t) ~
random Color TrueColor(Ball);
NumDetectionsDistrib
random (State(a,
Ball BallDrawn(Draw);
t));
random Color ObsColor(Draw);
header
guaranteed Color Blue, Green;
guaranteed Draw Draw1, Draw2, Draw3, Draw4;
Number statement:
#Ball ~ Poisson[6]();
#type_name :number
(𝑔1 , … , statement
𝑔𝑘 )
(𝑥1 , … , 𝑥𝑘 ) ~ expression
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
Balls in an urn
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});
ObsColor(d)
CPD arguments
if (BallDrawn(d) != null) then
~ NoisyCopy(TrueColor(BallDrawn(d)));
Aircraft tracking
Java function
number statements
Is a BLOG model well defined?
#Ball
TrueColor(B1)
TrueColor(B2)
ObsColor(D1)
TrueColor(B3)
…
Infinite parent set
BallDrawn(D1)
Standard BN results no longer apply
Well defined BLOG model
• Let M be a BLOG model.
• Suppose that 𝑉𝑀 is at most countably infinite,
A BLOG model is well-defined if, in a
• graph
and for representation,
each 𝑣 ∈ 𝑉𝑀 andeach
𝜔 ∈ Ωvariable
can be
𝑀:
“reached”
by enumerating
its ancestors
in a
 there is a self-supporting
instantiation
that agrees
with
𝜔 and
includes 𝑉.
finite
self-supporting
instantiations list
• Then M is well-defined.
Rejection algorithm
Input:
evidence e,
query Q
1. Start from evidence e(could be a set of evidence)
2. Check if the current node is “supported”
No – move to first un-instantiates parent. → step 2
Yes
• If basic variable: propose value from distribution.
• If derived expression: just calculate values.
3. Check if e is “supported”
No – move to first unsupported evidence. → step 2
Yes – increment counter 𝑁𝑞 (𝑞 =sampled value for Q)
4. 𝑁 accepted samples? No → step 2
Yes - calculate estimated probability
𝑁𝑞
𝑁
. (done)
Rejection algorithm
Input:
evidence e,
query Q
1. Start from evidence e(could be a set of evidence)
2. Check if the current node is “supported”
𝑃 𝑄=
𝑒 un-instantiates
=
No – move
to 𝑞first
parent. → step 2
Yes number of times the
sample with 𝑄 = 𝑞
• If basic variable: propose value from distribution.
was consistent with e
• If derived expression: just calculate values.
divided by number
3. Checkofifoverall
e is “supported”
successful
𝑁𝑞
No – move
to
first
samples = unsupported evidence. → step 2
𝑁
Yes – increment counter 𝑁𝑞 (𝑞 =sampled value for Q)
4. 𝑁 accepted samples? No → step 2
Yes - calculate estimated probability
𝑁𝑞
𝑁
. (done)
Rejection algorithm
Input:
evidence e,
query Q
1. Start from evidence e(could be a set of evidence)
2. Check if the current node is “supported”
No – move to first un-instantiates parent. → step 2
Yes
3.
Does
this
• If basic variable: propose value from distribution.
algorithm
• If derived
expression: just calculate values.
stop?
Checkalways
if e is “supported”
No – move to first unsupported evidence. → step 2
Yes – increment counter 𝑁𝑞 (𝑞 = sampled value for Q)
4. 𝑁 accepted samples? No → step 2
Yes - calculate estimated probability
𝑁𝑞
𝑁
. (done)
Another definition for well defined
Suppose, M is a BLOG model where:
Uncountable built-in types do not serve as function
arguments or as the return types of generating
functions.
Each quantified formula and set expression ranges
over a finite set, once generating function
restrictions are taken into account.
The symbol graph is acyclic.
Then M is well-defined and the algorithm converges
to 𝑃 𝑄 𝑒 in a finite time per step.