Superficial understanding of conditional random fields

Conditional random field （Conditional Random Field,CRF） It is the basic model of naturallanguageprocessing , Is an undirected graph probability model . After long-term development, it has been widely used in part of speech tagging 、 Image classification and many other scenes .

One 、 Basic concepts

Random Airport : Given a set of random variables : $X=\{X_1,X_2,X_3...,X_n\}$, Every random variable $X_i$ It can be in another set $Y=\{Y_1,Y_2,Y_3...,Y_m\}$ Random values in . Take an example of image classification ： You can take all pixels of an image as random variables : $I=\{I_1,I_2,I_3...,I_n\}$ , All categories are : $C=\{C_1,C_2,C_3...,C_m\}$, So image classification is actually a category for each pixel , Therefore, it can be regarded as a random airport .

Markov random Airport ： Special case of random airport , It assumes that the value of a certain position in the random field is only related to the value of its adjacent position , Independent of other locations . For example, the above example of image classification , The classification of a pixel , Only follow the surrounding 8 The classification of neighborhood pixels is related to other pixels .

Conditional random field ： Given a random variable $X$ The value of , If random variable $Y$ It's a Markov random airport , It's called conditional probability distribution $P(Y|X)$ It's conditional random airport . That is, the conditional random field is a conditional probability distribution model of another set of output sequences given a set of input sequences . As in the above example of image classification , Generally, the pixel color information of a given image $I$ , Predict each pixel $I_i$ The category of can be regarded as a strip random field .

Two 、 Potential function

Given the following random field ：

chart 1 . Probability undirected graph

The edges in the graph indicate that the nodes are related to each other , This relationship is two-way 、 symmetrical . Such as ：$x_3$ and $x_5$ There are edges between them , be $x_3$ and $x_5$ There is a correlation , This correlation is measured by potential function . for example , The following potential functions can be defined ：
$$\psi (x_3,x_5)=\{\begin{array}{ll}2& x_3=x_5\\ 0.1& otherwise\end{array}$$

Then it shows that the model prefers variables $x_3$ and $x_5$ Have the same value , The potential function describes the correlation between local variables , It can also be understood as the local soft constraints of the model . To satisfy nonnegativity , Exponential functions are often used to define potential functions ：
$$\psi (x)=e^{-H(x)}$$

3、 ... and 、 The main target

Our goal is to calculate the maximum a posteriori probability $P(Y|X)$, I.e. given $X$ after , The most correct classification result $Y$, bring $P(Y|X)$ Get the maximum .

So how to solve such a probability problem ?

To solve a given probabilistic undirected graph model , We want to write the global joint probability as the product of several sub joint probabilities , That is, factoring the probability graph , This is convenient for the learning and calculation of the model . As a matter of fact , The most important feature of probabilistic undirected graph model is that it is convenient for factorization . In the actual calculation process , An undirected graph is generally divided into cliques one by one （ group (clique) Is a complete subgraph of an undirected graph , Since it is a complete graph , Of course, every pair of vertices must be connected by an edge . Pictured 1 Medium $\{x_2,x_3,x_5\}$,$\{x_3,x_4,x_5\}$, And all subgraphs composed of two adjacent vertices ), And define the potential function on each clique to calculate the maximum probability .

Here we introduce the words in the paper ：

chart 2 . Formalization of maximum a posteriori probability for conditional random fields

How to calculate is not expanded , You can refer to the paper ：Efficient inference in fully connected crfs with gaussian edge potentials.

Four 、DenseCRF

The paper ：Efficient inference in fully connected crfs with gaussian edge potentials[J]. .
Code ：https://github.com/heiwang1997/DenseCRF
DenseCRF This is the paper at the end of the last section , The effect on image classification is very good and efficient . The general classification effect is shown in the figure below 3 Shown , It should be noted that the input here already contains the classification of the initial pixels ,CRF The pixels are reclassified accurately . You can see the 4 Column DenseCRF The classification is very precise .

chart 3 . DenseCRF Classification effect

Basic CRF The model consists of a first-order potential function ( Classification trend of single variable ) Graph model composed of potential function composed of adjacent elements , Obviously , On the image task , One disadvantage of this model is that it only considers adjacent neighborhood elements , Not considering the whole .
DenseCRF It is proposed to connect each pixel with all other pixels , Achieve dense full connection model , For more accurate classification . But at the same time , Will result in too many sides , Therefore, this paper also provides an efficient algorithm , But there is no further introduction in this article , Just a simple introduction DenseCRF The design of the .

Look at the picture 2 The original English part of , The maximum a posteriori probability actually required $P(Y|X)$ It's equivalent to asking for $E(X)$ The minimum value of , So it is actually a problem of energy minimization . and DenseCRF The energy function of is expressed as ：
$$E(x)=\sum _i{\psi }_u(x_i)+\sum _{i<j}{\psi }_p(x_i,x_j)$$
The energy function consists of two terms ： The former is called univariate potential function (unary potential function), The latter is called binary potential function (pairwise potential function).

Unary potential function: Each pixel is associated with a nary potential, Represents the classification loss of each pixel . If a pixel $I_i$ Get the correct classification , Then the pixel's unary Loss ${\psi }_u(x_i)$ smaller . This item mainly penalizes the wrong pixel classification .

Pairwise potential function: Any two pixels are associated with a pairwise potential, Used to punish two pixels with different labels .1） If two labels are different pixels , Their texture 、 shape 、 Color 、 The location is quite different , Then the punishment is less , It is hoped that this classification will be maintained ;2） conversely , If these properties are very close , Then the punishment is greater , In fact, I hope they can be reclassified into the same category .

Pairwise potential function The definition and explanation of the word are posted directly to the original text ：

chart 4 . DenseCRF Yes pairwise potential The explanation of

Reference material

[1] You know ：CRF The principle of conditional random field 、 Example 、 Formula derivation and application
[2] You know ： How to easily and pleasantly understand the condition of random airport （CRF）？
[3] You know ： Fully understand the conditional random fields （CRF）： principle 、 Application, for example, 、CRF++ Realization
[4] CSDN: Markov random field of probability graph （Markov Random Field,MRF）
[5] CSDN: Markov random Airport MRF
[6] You know ：FCN(3)—DenseCRF
[7] You know ：FCN(5)—DenseCRF deduction