Transcript View

Cognitive Computer Vision
Kingsley Sage
[email protected]
and
Hilary Buxton
[email protected]
Prepared under ECVision Specific Action 8-3
http://www.ecvision.org
Lecture 3


Graphical models
Probabilistic graphical models
–
–
–
–
Directed graphs
Unidirected graphs
Notation
Rolling out over time
What are graphical models?

Represent salient relationships graphically e.g.
What are probabilistic graphical
models?



A probabilistic graphical model is a type of
probabilistic network that has roots in AI,
statistics and neural networks
Provides a clean mathematical formalism that
makes it possible to understand the
relationships between a wide variety of network
based approaches to computation
Allows to see different methods as instances of
a broader probabilistic framework
What are probabilistic graphical
models?




Probabilistic graphical models use graphs to
represent and manipulate joint probability
distributions
Graphs can be directed – usually referred to
as a belief network or Bayesian network
Graphs can be undirected – usually referred
to as a Markov Random Field
A basis for algorithms for computation
Joint probability – a reminder

A probability dependent on more than one
variable e.g. p(AND|a,b): a
a
b
p(AND|a,b)
0
0
0
0
1
0
1
0
0
1
1
1
b
Discrete case of a logic
AND gate
A continuous case where
light values are high p(AND|a,b)
Directed graphs

A

B

Intuitively, the notion of
causality (although this can
be a philosophical argument)
A  B, so the value of A
directly determines the value
of B
P(A,B) = P(B|A).P(A)
Traffic lights model from lecture 2
as a directed graph
OBSERVABLE
HIDDEN
hidden
STOP
GET
READY
TO STOP
GET
READY
TO GO
GO
observable
Examples of directed graphs







Hidden Markov Models (later in the course)
Kalman filters
Factor analysis
Independent component analysis
Mixtures of Gaussians (later in the course)
Probabilistic expert systems
The list goes on …
Joint probability – conditional
independence

N variables are conditionally independent if one
value does not depend on the other e.g:
A
B
Here, A and B are conditionally
independent:
A  B iff P( A, B)  P( A).P( B)
But A and C and B and C are not:
C
P( A, B, C )  P(C | A, B)
P(C )  P(C | A, B ).P( A, B )
P(C )  P(C | A, B ).P( A).P( B)
Undirected graphs

A

B

Intuitively, the notion of
correlation (although this can
be a philosophical argument)
A  B, so the values of A and
B are interdependent
Directed graphs can be
converted into undirected
graphs (but beyond the scope
of this course)
A undirected graph for a computer
vision task
Notation
A


B


C
Squares denote discrete
nodes
Circles denote continuous
valued nodes
Clear denotes hidden node
Shaded denotes observed
node
Rolling out over time


Probabilistic graphical model notation is very
good at showing how models are propagated in
time
Expose the dependencies between the
different elements of the graphical structure
Rolling out our traffic light example
over 2 time steps …
OBSERVABLE
t=1
t=2
hidden
hidden
observable
observable
HIDDEN
STOP
GET
READY
TO STOP
GET
READY
TO GO
GO
Remember the concept of the
temporal order of a model ?
t=1
t=2
hidden
hidden
observable
observable


In this model, the value of the
hidden nodes (and thus the
observable ones) at time t+1
only depends on the previous
time step t
So this is a first order
temporal model
Remember the concept of the
temporal order of a model ?
t=1
t=2
t=3
t=4
hidden
hidden
hidden
hidden
observable
observable
observable
observable
A second order temporal model
…
…
So why are graphical models
relevant to Cognitive CV?




Precisely because they allows us to see different
methods as instances of a broader probabilistic
framework
These methods are the basis for our model of
perception guided by expectation
We can put our model of expectation on a solid
theoretical foundation
We can develop well-founded methods of learning
rather than just being stuck with hand-coded models
Summary



Probabilistic graphical models put the
formalisms on a well-founded mathematical
basis
We can distinguish directed and undirected
graphs
Here we concentrate on directed graphs that
we can roll out over time easily
Next time …


A family of graphical models
A lot of excellent reference material can be
found at:
http://cosco.hiit.fi/Teaching/GraphicalModels/Fall2003/material.html