How Conditional Random Fields and Logistic Regression could be the same?

Question

If you have read this tutorial about CRF, on page 4 under the section Classification, it wants to relate CRF to Logistic Regression (or Maximum Entropy, as it is known by this name in NLP community).

The formulation of Logistic Regression is said to be

$ p(y|x) = \frac{1}{Z(X)}exp \{ \lambda_y + \sum_{j=1}^{K}\lambda_{y,j}x_{j}\} $.

On the other hand, on the Wikipedia page for logistic regression, the formulation is

$ f(t) = \frac{1}{1+e^{-t}} $

and the classifier's formulation is the explanation of this formulation which is derived from Logistic Function.

My question is, first, how Logistic Regression and Maximum Entropy Classifier are related to each other and are identical?

Second, the CRF tutorial says Logistic Regression (or Maximum Entropy Classifier) is simple CRF model, how?

Answer 1

From the formulation of a general conditional model (lets omit the bias $\lambda_y$ for simplicity ),

$$ P(y|x) = \frac{1}{Z(x)} \exp( \sum\limits_{k=1}^K \lambda_{y,j}x_j ) $$ Where $Z(x) = \sum\limits_y \exp(\sum\limits_{k=1}^K \lambda_{y,j}x_j ) $

Call $w_y = [\lambda_{y,1},...\lambda_{y,k}]$

$$ \Rightarrow P(y|x) = \frac{1}{Z(x)} \exp(w_y^\top x) $$

If $y$ can take only binary values, i.e. $y \in \{+1,-1\}$,

$$ P(y = 1|x) = \frac{\exp(w_{+1}^\top x)}{ \exp(w_{+1}^\top x) + \exp(w_{-1}^\top x) } $$

$$ P(y = 1|x) = \frac{1}{ 1 + \exp( (w_{-1}-w_{+1})^\top x ) } $$

Call $w' = w_{+1}-w_{-1}$

$$ P(y = 1|x) = \frac{1}{ 1 + \exp( -w'^\top x ) } $$

Similarly,

$$ P(y = -1|x) = \frac{1}{ 1 + \exp( +w'^\top x ) } $$

This corresponds to binary logistic regression with $t = w'^\top x$. So by restricting the conditional model to 2 outcomes you get the binary logistic regression model.

Answer 2

First of all, let's clarify what you read in the wikipedia article you linked to.

This:

$f(t) = \frac{1}{1+e^{-t}}$

Is simply a logistic function. It is not logistic regression. If you continue reading, you will see this form:

$\pi(x) = \frac{1}{1+e^{-(\beta_0+\beta_1x)}}$

Which shows the logistic regression form with one variable. $x$ will be the data and $\beta_0,\beta_1$ will be the parameters that you fit.

With multiple variables, you get multinomial logistic regression - see this wikipedia article. This article explains that a Maximum Entropy Classifier is simply a logistic regression model used for classification (i.e. to predict binary classes). This is also the first form of logistic regression which you present in your question. This form now fits one parameter per variable (sometimes with an additional bias parameter), and adds an additional term $Z$ (aka the partition function) which simply normalizes everything into a probability distribution.

Finally, the text explains (1.2.2.1) how this form of logistic regression can be viewed as a CRF, via interpreting the function as a multiplication of feature functions (similar to how you multiply factors in random fields - see the beginning of the text).

Answer 3

I'd like to plug in my understanding here in very simple words.

For the CRFs we need to calculate the probability of each sequence of the ground truth tags. How can we calculate the probabilities? We can calculate the potential of the sequence(numerator) and the total potentials(denominator/normalization) of all possible sequences somehow like that we do in logistic regression.

Let me apply that to the logistic regression first(when $|y|>2$ it becomes the Multi-class Logistic Regression/or Softmax Regression, but they are the same thing in nature). The total potentials of the logistic regression is $$Z(x) = \sum\limits_y \exp(\sum\limits_{k=1}^K \lambda_{y,k}x_k ) $$ and the sequence potential(here more appropriately the label potential or logit) is $$\exp( \sum\limits_{k=1}^K \lambda_{y,k}x_k )$$ with the sequence length of just 1, then we can divide the sequence potential by they total potentials to get the probability: $$P(y|X) = \frac{1}{Z(X)} \exp( \sum\limits_{k=1}^K \lambda_{y,k}x_k )$$ Now that we have obtained the probability of the right tag/label we can calculate the negative log likelihood using this: $- \log P(y|X)$(the loss for a sample).

We can easily see that the logistic regression(here the general multi-class logistic regression) is very simple because the label sequence length is just one, then it is very natural for us to ask if we can combine several logistic regressions together to form a sequence of tags given the observed X(condition)? The answer is yes, and we get the CRF. The difference lies in that in logistic regressions we have only unary potentials/scores(|y| logits) but in CRFs we have a binary potentials between each two sets of unary potentials for each two continuous time-steps, and the binary potentials form the transformation matrix(only one matrix for all two continuous time-steps) meaning the transition potentials/scores from each tag in one time-step to each next tag in the next time-step. Here the key points come, that is how can we calculate the probability of a sequence of ground truth tags?

It's very simple with the transition scores(binary potentials). We just multiply all the potentials in the path of the ground truth sequence tags as the numerator and the sum of all possible paths(multiplications) as the denominator. But the denominator seems very expensive to compute since there are $|y|^{|sequence\_length|}$(here we ignore the start and end symbol) possible paths. But we can utilize the math tool named generalized distributive law and implement it using the programming tool named dynamic programming.

Once we have got the probability of the ground truth tag sequence we can use the negative log likelihood as the loss for each sample to train the weights for the features(like those in the logistic regression for the unary potentials or unary scores or emission scores or logits) and the weights in the transition matrix(binary potentials or binary scores).

Hope this helps to some extent.