Relational Dynamic Bayesian
Networks: a report
Cristina Manfredotti
Dipartimento di Informatica, Sistemistica e Comunicazione (D.I.S.Co.)
Università degli Studi Milano-Bicocca
[email protected]
Bayesian Networks:
• Encode the joint probability distribution of a set of
variables, as a Direct Acyclic Graph
• A Direct Acyclic Graph which nodes are
conditionally independent of its non-descendent
given its parents
A
P(B|A)
P(C)
T
.90
0.01
F
.05
C
B
P(D|C,B)
T
T
.95
T
F
.94
F
T
.29
F
F
.01
A
P(A)
0.01
B
C
D
E
D
P(E|D)
T
.90
F
.05
D
P(F|D)
T
.70
F
.01
Cristina Manfredotti
F
P(A,B,C,D,E,F) =
= P(A)P(B|A)P(C)P(D|C,B)P(E|D)P(F|D)
= ∏P(Zi|Pa(Zi))
D.I.S.Co. Università di Milano - Bicocca
2
The alarm example(1)
• I'm at work, neighbor John calls to say my alarm
is ringing, but neighbor Mary doesn't call.
Sometimes it's set off by minor earthquakes. Is
there a burglary?
• Variables: BurglarEnter, EarthquakeAppens,
AlarmRings, JohnCalls, MaryCalls
• Network topology reflects "causal" knowledge:
– A burglar can set the alarm off
– An earthquake can set the alarm off
– The alarm can cause Mary to call
– The alarm can cause John to call
from Russel&Norvig
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
3
The alarm example(2)
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
4
Bayesian Networks
• Each node is a variable:
≠
Two different nodes
in the network
This is why we have
such structure:
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
5
Bayesian Networks
If we should have 4 neighbors?
We have to construct a graph with 2 more knods.
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
6
A large BN
Thanks to Mark Chavira
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
7
Relational Domain
Objects: groups of attributes which “belong together”
(tables of a database), c.f. a structure in a programming
language
• neighbor
• alarm
• burglar
• (honer of an house)
neighbor’s attributes: his capacity of hearing, his attention, ...
e.g.: Object
alarm’s attributes: its volume, its sensibility, ...
Relational Domain contains a set of objects with
relations and/or predicates between them
e.g.: Relation
e.g.: Predicate
• toCall (the honer of the house)
• toHear (the alarm)
• toRing
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
8
The alarm Relational Domain:
Burglary
•
•
•
Alarm
Neighbor
Honer
g
g
nin • DegOfDef
e
• Volume
llin • DegOfBelieve
t
s
a
i
• Sensibility L
• NoiseAround C
• Teleph
• ToRing
• Teleph
• ...
•...
•...
Red words: predicates, that concern only the object itself
Dashed arrows: relation between an object and an attribute of the object
(or a predicate)
Green arrows: dependence between two attributes
Continouse arrows: relations between two objects
Bold black words: objects names
Black words: objects attributes (caracteristic of the variables, they make
an instanciation of each object different by each other).
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
9
Relational Bayesian Networks
“difficult definition”
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
10
Relational Bayesian Network
• Syntax RBN:
– a set of nodes, one per variable
predicate/relation/attribute
– a directed, acyclic graph
– a conditional distribution for each node
given
given its
its parents
parents,
this distribution must take into account the
actual “complexity” of the nodes!
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
11
Alarm RBN:
Earthquacke
Neigh.DegOfDef
Alarm.Volume
Neigh.NoiseAround
NeighborCalls
I
“relationated”
only that part of
the graph, I could
make the same for
each knodes of
the BN
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
12
Conditional Probability
Distribution/Table
The CPTs will take into account the values of each
attributes
For each variable in the system (i.e. for each actor playing
a role in the represented world) an object will be
instantiated, the conditional probability of each variable
will be the same but they will depend by the particular
instantiation of their attributes. NOT ONLY BY THE FACT
THAT THE ALARM HAS RANG
E.g.:
P(NeighCall |Neigh.DegOfDef, Neigh.NoiseAround,Alarm.Vol) =
= .90 if the Neighbor isn’t def but he listen music (John case).
= .70 if the Neighbor is def but his house is very quite (Mary case).
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
13
Relational Bayesian Networks
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
14
Dynamic Bayesian Networks:
• Extension of BN for modeling dynamic systems.
State at time t represented by a set of random
variables zt = (z1,t,…,zd,t). The state at time t
depends on the states at previous time steps.
• A 2TBN is a BN that contains variables from zt-1
whose parents are variables from zt and/or zt-1,
and variables from zt without their parents. A
2TBN defines P(zt|zt-1) by means of a directed
acyclic graph (DAG) as follows:
P(zt|zt-1) = ∏Ni=1P(zit|Pa(zit))
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
15
Dynamic Bayesian Networks
• A Dynamic Bayesian Network (DBN)
is defined to be a pair of Bayesian
Networks (B0, B→), where B0
represents the initial distribution P(z0),
and B→ is a 2TBN, which defines the
transition distribution P(zt+1|zt).
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
16
Relational Dynamic Bayesian Nets:
Once you defined a RBN and a DBN
it is easy to define a RDBN....
GUESS IT!
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
17
Particle Filters:
Tecnique that implements a ricursive Bayesian FIlter
through a Monte Carlo simulation. The key idea is to
represent the posterior pdf with a set of random
samples with associated weights and compute the
estimation based on these samples and weights.
As the number of samples becomes very large, this
MC caratterization
becomes an equivalent
representation to the usual functional description of
the posterior pdf, and the SIS algorithm filter
approaches the optimal Bayesian estimate.
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
18
Particle Filtering: steps
Fix the number of particles: M
x k( m) ~ p( xk | x k −1 )
1. Particle generation
At time k arrives the observation/measure zk
*( m )
( m)
2a. Weight computation wk = p( z k | xk )
2b. Weight normalization
(m)
k
w
=
wk*( m )
M
∑w
*( m )
k
m =1
3. Resampling
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
19
Particle filtering operations
• Represents the required pdf by a set of samples with
associated weights.
• Computs the estimate based in these samples and
weights.
Posterior pdf
x k( m ) ~ p( x k | x k −1 )
Sample space
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
20
Pros:
• Arbitrary pdf
• Most probable state-space
• Non-Gaussian noise
• More than one model
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
21
Cons:
• Computational complexity
• How to determine the number of
particles
• Probable problems: density extraction,
sampling variance
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
22
Rao-Blackwellized PF:
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
23
Rao-Blackwellized PF
Rao-Blackwellization:
• Some components of the model can have
a liner dynamic and can be estimate by a
traditional Kalman Filter.
• Kalman Filter is combine with PF to reduce
the number of particles to be used for a
satisfying performance.
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
24
“Domingos” PF
Complex & Simple
Predicates
Abstractions:
(set of pairs of objects which are
related in some way)
PF smoothing on an Abstraction lattice
Cristina Manfredotti
D.I.S.Co. Università di Milano - Bicocca
25