A Markov network, aka a Markov random field, or undirected graphical model, is a Network of Random variables that satisfy a Markov property. In particular they satisfy the properties below (see General Markov network). It is a Graphical model with undirected edges.

Markov networks have in general full expressive power, as in they can represent any probability distribution over the r.v.s. However, the standard network representation doesn't have all the information contained in the factor representation

Product of factors construction

Simple video introduction

In general, we define factors, which are just functions of the random variables. Then the probability distribution is defined to be the normalized product of these factors.

Pairwise Markov Network

The simple case when every factor is just a function of two random variables. Then there is a one-to-one correspondence between the factor expansion and the network representation, unlike in the general case described below.

Example: Lattice Markov networks, often used for Image processing (in particular Image segmentation). See Discrete optimization (c.f.)

Log-linear representation

General Markov networks (General Gibbs distribution)

We need more than pairwise edges, so that we are really talking now about Hypergraphs.

Network representation

However, it can also be represented as a graph, and most often is. It is called the induced Markov network. To construct the network, we put an edge, whenever two variables appear together as arguments in some factor in the product of factors form.

However, there is not a one-to-one correspondence between the factors and this graph representation, cannot read factorization from graph. However, the graph is still useful find out the flow of influence/dependencies b/w r.v.s in the network.

Formal definition

There is a node for each of the Random variables. In the case of Conditional random fields, one for each output $y_k$, and each input $x_k$.

Then we have an edge between any two nodes that in such a way that the r.v. satisfy:

More generally, given disjoint subsets of nodes A, B, and C, X_A is conditionally independent of X_B given X_C if there is no path from any node in A to any node in B that doesn't pass through a node of C.

–>This can be understood by defining Active trails.

Conditional random field

A Conditional random field, is a Markov network, that models a conditional function $p(y|x)$, they are thus called discriminative UGMs.

Video

https://www.coursera.org/learn/probabilistic-graphical-models/lecture/UJ1Ke/conditional-random-fields

See also the generalized Factor graph

Chapter from Murphy's book

Markov Random Field Optimisation

Neural networks [3.8] : Conditional random fields - Markov network

wiki