Markov Network

Formally, a Markov network consists of:

an Undirected Graph ''G'' = (''V'',''E''), where each vertex ''v'' ∈''V'' represents a random variable in $\mathcal{X}$ and each edge {''u'',''v''} ∈ ''E'' represents a dependency between the random variables ''u'' and ''v'',

a set of Potential Function s $\phi_k$ , one for each Clique ''k'' in ''G''. Each $\phi_k$ is a mapping from possible joint assignments (to the elements of ''k'') to Non-negative Real Number s.

The joint distribution represented by a Markov network is given by:

P(X=x) = rac{1}{Z} \prod_{k} \phi_k (x_{ \{ k \}})

where

x_{ \{ k \}}

is the state of the random variables in the ''k''th clique, and the Normalizing Constant

Z

, where

Z = \sum_{x \isin \mathcal{X}} \prod_{k} \phi_k(x_{ \{ k \} })

.

The Markov Blanket of a node

v_i

in a Markov network is defined to be every node with an edge to

v_i

, i.e. all

v_j

such that

\lbrace v_i, v_j 
brace \in E

. Every node

v

in a Markov network is Conditionally Independent of every other node given the Markov blanket of

v

.

As in a Bayesian network, one may calculate the Conditional Distribution of a set of nodes

V' = \{ v_1 ,..., v_i \}

given values to another set of nodes

W' = \{ w_1 ,..., w_j \}

in the Markov network by summing over all possible assignments to

u 
otin V',W'

; this is called Exact Inference . However, exact inference is in general a #P-complete problem, and thus computationally intractable. Approximation techniques such as Markov Chain Monte Carlo and Belief Propagation are more feasible in practice. (Though note that some particular subclasses of MRF have polynomial algorithms; discovering such subclasses is an active research topic.)

One notable variant of a Markov network is a conditional random field, in which each random variable may also be conditioned upon a set of global observations

o

. In this model, each function

\phi_k

is a mapping from all assignments to both the clique ''k'' and the observations

o

to the nonnegative real numbers. This form of the Markov network may be more appropriate for producing Discriminative Classifiers , which do not model the distribution over the observations.

SEE ALSO

Markov Logic Network

	CATEGORIES ABOUT MARKOV NETWORK

	artificial intelligence

	theoretical computer science

	probability theory

	networks

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Markov Network