A

probabilistic model or method is based on the theory of probability or the fact

that randomness has a vital role in predicting future events. The opposite

is deterministic, that is the opposite of randomness. This explains how something

can be predicted accurately, without the added complication of randomness.

Probabilistic

methods deal random variables and probability

distributions into the model of a

phenomenon or event. While a deterministic model produces a single possible

outcome for an event, a probabilistic method produces a probability distribution as a solution

as shown in Figure 1. These models take into account the

fact that we can rarely know everything about a situation. There’s nearly

always an element of randomness to take into account. For example, life

insurance is based on the fact we know with certainty that we will die,

but we don’t know when. These models can be part deterministic and partially

random or completely random.

.

Fig. 1. A normal distribution curve (Also called bell curve)

The

probabilistic method, first introduced by Paul Erdos, is a

way to prove the existence of a structure with certain properties in combinatorics. The idea is that you create a probability

space, and choosing elements at random

show than any random element from the space has both a positive probability and

the properties sought after. The method is commonly used in a various areas, such

as quantum mechanics, statistical physics, and theoretical computer science.

Probabilistic

Graphical Model have two types

1) Bayesian Networks

2) Markov Random Field (MRF)

I am going to describe

one probabilistic model Markov Random Field (MRF).

1-

Markov Random Field

A Markov Random

Field (MRF) is a graphical model which has joint probability distribution. It contains

an undirected graph G= (N, E) in which E shows links or edges and N shows

random variables. Suppose

is

the set of random variables and S is a set of nodes. Both sets S and

associated with each other. Then, the

edges E encode conditional

independence relationships using the following rule: there are three disjoint

subsets of vertices A, B, and C,

is

conditionally independent of

given

if

there is no way from any vertices in A to any node in B that doesn’t pass

through a node of C. Then it will be like

.

The subsets are dependent if such a path does exists. The neighbor set

of a node n is can be defined

as the set of all vertices which are linked to n via edges in the graph:

}

Given its neighbor set, a node n is

independent of all other vertices in the graph. Therefore, for the conditional

probability of

This

is called the Markov property, and this is the reason why this model gets this

name markov random field. Figure 2 shows the concept of markov random field.

Fig.2. Given the grey nodes, the black node is conditionally independent

of all other nodes

When

the joint probability density of

the random variables is strictly positive, it is also referred to as a Gibbs random field, because, according

to the Hammersley Clifford theorem,

it can then be represented by a Gibbs measure for

an appropriate (locally defined) energy function. The prototypical Markov

random field is the Ising model;

indeed, the Markov random field was introduced as the general setting for the

Ising model. In the domain of artificial

intelligence, a Markov random field is used to model various low to

mid-level tasks in image processing and computer vision.

2-

Why Markov Models?

Markov model is

very simple and efficient statistical model in which we don’t suppose that all

variables are independent; we suppose that there are significant dependencies,

but also conditional independencies which we can take advantage of Markov

models show up in a lot of ways in computer vision. For example:

·

The

shape of contours can be modeled as a Markov chain. In this method, the future

course of a contour which passes from point x might rely on the tangent of the

contour at x, but not on the shape of the contour prior to reaching x. This is

very simple, but is implicitly used in various methods to contour segmentation

and perceptual grouping.

·

In

modeling texture, a patch of an image can be represented by output of a large

number of filters. If we suppose that few of these filter outputs are dependent

on each other, but that there is conditional independence among various filter

outputs, then we can obtain a tractable model for use in texture synthesis.

·

In

modeling texture, we suppose that the appearance of a pixel in a textured image

patch will reply on some of the neighboring pixels, however, it will be

independent of the rest of the image.

·

In

action recognition, we usually model the movements which consist of an action

as a Markov chain. For example, that if I want to predict about what will

happen when somebody is in the middle of leaving work and going for his car,

that this will depend on their current state i.e., what Is position of the car

and person right now, and what is their current trajectory but not on old

states (once you are standing in front of the car, how you will get in doesn’t

really reply on how you left the building and reached in front of the car).

3-

Markov Chains

A Markov chain is a stochastic

model describing a sequence of possible events in which the probability of each

event depends only on the state attained in the previous event. Diffusion of a

single particle can be thought of as a Markov chain. We can also use Markov

chains to model contours, and they are used, implicitly or explicitly, in many

contour-based segmentation technique. The most important benefit of 1D Markov

models is that they lend themselves to dynamic programming solutions.

In a Markov chain,

there are sequence of random variables, which describes the state of a system,

. According to Markov conditional independence

property, each state only depends on the old state i.e.

P (

Markov chains have

few significant properties. By solving eigenvalue problem, their steady state

can be found. If a Markov chain involves transitions among a discrete set of

states, it’s very helpful to describe these transitions from state to state

using matrices and vectors.

4-

Difference between

Markov Chains and Markov Random Field

·

A (discrete

time) Markov chain:

A Markov chain is a sequence of

random variables

,

that satisfy

Pr (

·

A Markov Random

Field:

A group of random variables x1,x2,…,xix1,x2,…,xi that satisfy

Pr (

After comparing the above two, we

can see that for a discrete time Markov chain, we can express the conditional probability

Pr(xi|x1,…,xi?1)=Pr(xi|xi?1)=Pr(xi|Neighbor(xi))Pr(xi|x1,…,xi?1)=Pr(xi|xi?1)=Pr(xi|Neigh-bor(xi))

Pr(

As in the sequence

,

obviously is

is

only neighbor. Therefore, the Markov

field is a simple extension of the Markov chain, also showed by the name

transition: chain ? field.

Furthermore, a Markov chain is illustrated

by a directed graph while a Markov random field showed by undirected. However,

every directed graph as an undirected version, and the undirected graph version

of a Markov chain looks the same as the directed version except without the

arrow directions 15.

5-

Extension of

Markov Chain in two Dimension of 2-D MRF

Markov chain has

extension into 2 dimensions of 2-dD Markov Random field.

·

Lattice

Rather than a

subset of the integer line, R ? Z = {0, ±1, ±2, .

. .}, consider some deterministic lattice structure or grid structure (for

instance R ?

= = {(x, y) : x, y ?

Z}). All coordinate pair is basically the location of a site i ?

S ? Z. This is shown in Figure 3.

Fig.3.

Various types of Lattice

The square lattice

has value |?i| = 4, the triangular lattice has value |?i| = 6, and the

honeycomb lattice has value |?i| = 3.

6-

Properties of

Markov Random Field

There are three

properties of Markov Random Field

·

Pairwise Markov

Property:

Two nodes that are not directly connected can be made independent given all

other node.

·

Local Markov

Property:

A set of the nodes (variables) can be made independent form the rest of the

node variables given its immediate neighbors.

·

Global Markov

Property:

A vertex set A is independent of the vertex set B (both B and A are disjoint)

given set C if all chains among A and B intersect C.

7-

Types of Markov

Random Field

·

Pairwise Markov

Random Field: Associated

energy is factorized into a sum of potential functions defined on cliques of

order strictly less than three.

·

Higher Order

Models:

Potential of factor term depends on more than two random variable. Difficult to

train and get inference form.

·

Conditional Random

Field:

In conditional random field observed random variable are not included in

graphical model. Only unobserved variables are latent variable.

8-

Inference Methods

in MRF

There are various

methods for inference process in MRF. Inference process has an important role

in MRD for classification purpose. Some of these inference methods are

described as follow:

·

Graph Cut

Algorithm: This

algorithm utilizes max flow problem to draw useful inference from Markov Random

field. Graph Cut algorithm rapidly compute a local minimum, in the sense that no

“permitted move” will produce a labeling with lower energy.

·

Belief Propagation

Algorithm:

1) Relies upon message passing of various vertices in graph. 2) Exact Method

for Tree models. 3) Improvement in complexity with the help of dynamic

programming.

·

Loopy Belief Propagation: This is approximate

version of belief propagation. This method cannot converge for all the cases. We can guarantee convergence for certain cases

using factor graph.

·

Junction Tree

Algorithm:

1) This is an exact inference technique for arbitrary graphical models. 2)

Possibility of this algorithm is only if graph is triangulated. 3) Due to

exponential complexity, it is not practically easy to implement.

·

Dual Method: Dual method focuses

at reformulating inference issue as linear integer programming problem. We can

extend most of the above algorithms in case of higher order graphical models.

9-

Training of Markov

Random Field

MRF follows two

types of training procedures:

·

Gradient Ascent:

1- Climb up in

steepest direction

2- Not guaranteed

to reach global maximum.

·

Max-margin

Learning:

This algorithm focuses

at adjusting the weight vector such that energy of desired ground truth

solution is less than energy of any other solution by a fixed amount.

10-

MRF

Applications to Vision

In

computer vision, mostly problem are related to noise, and so exact solutions

are most often impossible. Moreover, the latent variables of interest also have

the Markov property. For example, the pixel values in an image mostly rely on

those in the immediate vicinity, and have only weak correlations with those

further away. Hence, computer vision issues can be solve easily by using MRF optimization

method. Below are some examples of vision problems to which MRFs have been used:

Segmentation

Image reconstruction

Edge detection

Image restoration

11- Some Other Applications

of Markov Random Field

Markov

random fields (MRF) have many application in a various fields, ranging

from computer graphics to

machine

learning and computer vision.

·

MRFs are used in image processing to produce textures as they

can be used to create stochastic and flexible image models. In image modelling,

the aim is to search a suitable intensity distribution of a specific image,

where suitability relies on the type of task.

·

MRFs are flexible enough to be used for texture and image

synthesis, image restoration and compression, surface reconstruction, image

segmentation, texture synthesis, super-resolution, image

registration,

stereo

matching and information

retrieval.

·

They can be used to solve various computer vision problems

which can be posed as energy minimization problems or problems where different

regions have to be differentiate using a discriminating features set, within a

Markov random field framework, to predict the class of the region.

Conclusion

Graphical

models analyze those probability distributions whose conditional dependencies

appears in specific graph structures. Markov random field is an undirected

graphical model along with specific factorization properties. 2-Dimensional

MRFs have been largely used in image processing problems. In this report, I

explained two very important concepts Markov Random Field (MRF) and Markov

Chains. The basic difference between them is extension of probability means MRF

is simply an extension of Markov Chains. Both of them have deep rotes in

various applications such as image processing, classification, texture and

image synthesis and many more. Integration of Markov chains with MRF produce

more accurate and efficient results.