12
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Wanted to add this as a comment to either of the above answers, but my rep isn't high enough. Just wanted to point out that in the case of non-binary outputs, the functions is called the softmax function. $\endgroup$ Sep 9, 2017 at 17:50
  • $\begingroup$ Linear-Chain CRFs are log-linear models, another form of Generalized Linear Models, with interpretations in terms of sequence independence, specifically by factorization in undirected Graphical Models. $\endgroup$
    – Kuo
    Mar 10 at 5:07

3 Answers 3

20
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ +1 for insightful answer. In general, should I think of the partition function $Z(x)$ in any CRF as the normalizer (denominator) in a softmax function? $\endgroup$
    – Mecasickle
    Jan 21, 2017 at 21:06
  • $\begingroup$ @Mecasickle I'd say yes, as the partition function is what is needed for the outputs of the model be real probabilities (i.e. sum up to one). $\endgroup$
    – Cesar
    Jun 15, 2017 at 14:24
6
$\begingroup$

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).

$\endgroup$
3
  • 1
    $\begingroup$ Thanks. Both answers are acceptable but I guess the other one is more useful for third-party reader. :-) $\endgroup$
    – Moh
    Jul 20, 2013 at 17:42
  • $\begingroup$ I don't see any 1.2.2.1 on en.wikipedia.org/w/… or en.wikipedia.org/w/…: which text are you referring to? $\endgroup$ Jan 2, 2017 at 18:09
  • 1
    $\begingroup$ @FranckDernoncourt this refers to the PDF that OP was asking about. $\endgroup$
    – Bitwise
    Jan 2, 2017 at 18:41
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Note: some errors in this answer, will be updated later $\endgroup$ Jun 10, 2020 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.