In problems where we have a set of observed variables X and a set of target variables Y:
| Observed variables: X={xi | i=1,2,…,M} |
| Target variables: Y={yj | j=1,2,…,N} |
The goal is to model the conditional distribution P(Y|X).
There are many application of such a problem in practice, like image segmentation, Part-Of-Speech tagging, etc. For these problems, we can model the conditional distribution P(Y|X) as a Conditional Random Field.
Condition Random Field as Markov Network
Conditional Random Fields (CRFs) can be represented by a special form of Markov Network (Figure 1).
Figure 1. An example Markov Network representation of Conditional Random Field. [1] The circles and the double circles denote the the target variables Y and the observed variables X respectively. The links refer to the dependencies among the random variables.
As we can see from Figure 1, there is no edge among observed variables. This doesn’t mean the observed variables X are independent of each other. The dependencies are just not interesting in representing the conditional distribution P(Y|X).
Condition Random Field as Factor Graph
The Markov Network representation is ambiguous. Figure 2 gives a simple example about the ambiguity of the Markov Network.
Figure 2. Both of the factor graphs (middle and right) correspond to the same Markov Network (left). [2]
To disambiguate the Markov Network representation of Conditional Random Field is the factor graph representation. Figure 3 demonstrates the same Conditional Random Field represented as a factor graph.
Figure 3. An example Factor graph representation of Conditional Random Field. [1] The circles and the double circles denote the the target variables Y and the observed variables X respectively. The solid squares denote the factors.
References:
[1]: Hugo Larochelle. “Neural networks [3.9] : Conditional random fields - factor graph”
[2]: Charles Sutton and Andrew McCallum. “An introduction to conditional random fields.” Foundations and Trends® in Machine Learning 4.4 (2012): 267-373.