NationMaster - Encyclopedia: Markov network

A Markov network, or Markov random field, is a model of the (full) joint probability distribution of a set $mathcal{X}$ of random variables. A Markov network is similar to a Bayesian network in its representation of dependencies, but a Markov network can represent dependencies that a Bayesian network cannot, such as cyclic dependencies. Given two random variables X and Y, the joint distribution of X and Y is the distribution of X and Y together. ... A random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. ... A Bayesian network or Bayesian belief network or just belief network is a form of probabilistic graphical model. ...

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 functions $φ k$ , one for each clique k in G. Each $φ k$ is a mapping from possible joint assignments (to the elements of k) to non-negative real numbers.

The joint distribution represented by a Markov network is given by: This article just presents the basic definitions. ... The term potential function can mean more than one thing. ... K5, a complete graph. ... A negative number is a number that is less than zero, such as −3. ... In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite lineâ€”the number line. ...

$P(X=x) = frac{1}{Z} prod_{k} phi_k (x_{ { k }})$

where $x {k}$ is the state of the random variables in the kth clique, and the normalizing constant $Z$ , where The concept of a normalizing constant arises in probability theory and a variety of other areas of mathematics. ...

$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 rbrace in E$ . Every node $v$ in a Markov network is conditionally independent of every other node given the Markov blanket of $v$ . In machine learning, the Markov blanket for a node in a Bayes net is the set of nodes composed by the s parents, its children, and its childrens parents. ... In probability theory, two events A and B are conditionally independent given a third event C precisely if the occurrence or non-occurrence of A and B are independent events in their conditional probability distribution given C. Two random variables X and Y are conditionally independent given an event C...

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 notin 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 loopy 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.) Given two jointly distributed random variables X and Y, the conditional probability distribution of Y given X (written Y | X) is the probability distribution of Y when X is known to be a particular value. ... The title given to this article is incorrect due to technical limitations. ... Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods) are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its stationary distribution. ... Belief propagation is an iterative algorithm for computing marginals of functions on a graphical model most commonly used in artificial intelligence and information theory. ...

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 $φ 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.

Andrey Markov Summary (1675 words)
	Markov involved himself in anti-Czarist, liberal politics and protested Czar Nicholas II (1868-1918) refusal to elect writer Maxim Gorky (1868-1936) to the St. Petersburg Academy in 1902.
	Markov was born in Ryazan, Russia, on June 14, 1856.
	Markov then stayed on at St. Petersburg to work for his master's degree, which was granted in 1880, then for his doctorate, which he received in 1884.

Markov network - Wikipedia, the free encyclopedia (366 words)
	A Markov network is similar to a Bayesian network in its representation of dependencies, but a Markov network can represent dependencies that a Bayesian network cannot, such as cyclic dependencies.
	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.
	This form of the Markov network may be more appropriate for producing discriminative classifiers, which do not model the distribution over the observations.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

See also GA_googleFillSlot("encyclopedia_square");

See also