PGM 02: Lots of Markov Family members: MC, PMN, CRF…

Markov Chain

Markov Process is a kind of random process. The main idea is given the current state of the system, its future state does not depend on its past states.

One state transfers to another, we need a transaction probability. Every step, we define, the Probability matrix is given below:

Note you have at time n, and this is the prob to the state at time n+1, given the current one.
From the state i to state j, you need probability from i to j. Then you will have a matrix.

Weather Model:

Only two states: rainy and sunny. The values are probabilities. The transaction Matrix A :
If we know the 2nd of April was rainy, so what is the weather would be like on 10th of April?

We will see the probability for sunny is 0.78.

Pairwise Markov Network

Let’s think about undirected graphs. Vertices connected together are pairs and equal to each other.

Four students in a study group, they have below interactions:
For example, A is directly interacting with B and D, but not directly interacting with C. Each edge here, means their relationship. Each of the students has two states: 0 or 1. The table shows the happy assignments. Say when A has state of 0, and b has the same state, then how happy they are if they both reach the state — 30 (top right) in . is the relationship of A and B. But it is not a probabilistic distribution: does not sum up to 1 and ranges out of 0 and 1 — unnormalized.

We could use a partition function Z, to normalized our distributions.

PMN is an undirected graph, who has nodes and edges Xi — Xj, and each edge is associated with a factor (potential) .

It is widely used in images, say any raw pixels could be seen as nodes and they are in a grid net.

We believe they are connected by factors. For example, a pixel is more likely to be the same with its neighbours.

Super pixels

Conditional Random Fields (CRF)

We’ve talked about the raw pixels. How we gather information from them and finally reach the goal of object classification or segmentation?
In image segmentation, we have observed variables X (pixel values) and target variables Y (pixel class labels).

They can be organized as a grid network:

We call Y super pixels (latent variables and we do not know them), they could tell us the labels of the X pixels (clearly known variables). Also, they could be organized as this:

---

Click to access 2652-conditional-random-fields-for-object-recognition.pdf

http://wenku.baidu.com/link?url=7LBbXiKPWAPnqYexmBOhz4iCUSny6Ayg3M53Ls0IiVKdqLq-9YPNAiW3WKJ5UgihjWKmm4yTpahIIeu75BB_mM_Q1QicaLIGrOiwHUO8ktu