18
$\begingroup$

This question already has an answer here:

  1. Why does logistic regression not converge for a linearly separable data set?

For linear separable data sets the model parameters go to infinity when mimizing the error function (according to Bishop2006, Pattern recognition and machine learning, section 4.3.2). I don't understand why. It must be connected to setting the score function, i.e. the derivative of the error function, to zero.

The error function is given by $E(\mathbf{w})$ as shown in the figure below. Where $\mathbf{t}$ is the target variable vector of the training set and $\mathbf{w}$ the parameter / coefficient vector. The posterior probabiltiy for class 1 is given by $$y(n) = p(C_1|\mathbf{x}_n) = \sigma(\mathbf{w}'\mathbf{x}_n).$$ Where sigma is the logistic sigmoid function and $\mathbf{x}_n$ is the feature vector for instance $n$ including the predictors.

ErrorFunction

  1. My second question to logistic regression is if the to posterior probabilities $p(C_1|\mathbf{x}_n)$ and $p(C_2|\mathbf{x}_n)$ sum to one?
$\endgroup$

marked as duplicate by kjetil b halvorsen, Michael R. Chernick, Peter Flom - Reinstate Monica Sep 30 '17 at 23:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

27
$\begingroup$

Here's a visual explanation of (1)

enter image description here

Imagine that you have a perfectly separated set of points, with the separation occuring at zero in the picture (so a clump of $y=0$s to the left of zero and a clump of $y=1$s to the right).

The sequence of curves I plotted is

$$\frac{1}{1 + e^{-x}}, \frac{1}{1 + e^{-2x}}, \frac{1}{1 + e^{-3x}}, \ldots $$

so I'm just increasing the coefficient without bound.

Which of the 20 curves would you choose? Each one hewes ever closer to our imagined data. Would you keep going on to

$$\frac{1}{1 + e^{-21x}}$$

When would you stop?

For (2), yes. This is essentially by definition, you've implicitly assumed this in the construction of the binomial likelihood(*)

$$ L = \sum_i t_i \log(p_i) + (1 - t_i) \log(1 - p_i) $$

In each term in the summation only one of $t_i \log(p_i)$ or $(1 - t_i) \log(1 - p_i)$ is non-zero, with a contribution of $p_i$ for $t_i = 1$ and $1 - p_i$ for $t_i = 0$.

Why is there no convergence mathematically?

Here's a (more) formal mathematical proof.

First some setup and notations. Let's write

$$ S(\beta, x) = \frac{1}{1 + \exp(- \beta x)} $$

for the sigmoid function. We will need the two properties

$$ \lim_{\beta \rightarrow \infty} S(\beta, x) = 0 \ \text{for} \ x < 0 $$ $$ \lim_{\beta \rightarrow \infty} S(\beta, x) = 1 \ \text{for} \ x > 0 $$

with each approaching the limit monotonically, the first limit is decreasing, the second is increasing. Each of these follows easily from the formula for $S$.

Let's also arrange things so that

  • Our data is centered, this allows us to ignore the intercept as it is zero.
  • The vertical line $x = 0$ separates our two classes.

Now, the function that we are maximizing in logistic regression is

$$ L(\beta) = \sum_i y_i \log(S(\beta, x_i)) + (1 - y_i) \log(1 - S(\beta, x_i)) $$

This summation has two types of terms. Terms in which $y_i = 0$, look like $\log(1 - S(\beta, x_i))$, and because of the perfect separation we know that for these terms $x_i < 0$. By the first limit above, this means that

$$ \lim_{\beta \rightarrow \infty} S(\beta, x_i) = 0$$

for every $x_i$ associated with a $y_i = 0$. Then, after applying the logarithm, we get the monotonic increasing limit towards zero:

$$ \lim_{\beta \rightarrow \infty} \log(1 - S(\beta, x_i)) = 0$$

You can easily use the same ideas to show that for the other type of terms

$$ \lim_{\beta \rightarrow \infty} \log(S(\beta, x_i)) = 0$$

again, the limit is a monotone increase.

So no matter what $\beta$ is, you can always drive the objective function upwards by increasing $\beta$ towards infinity. So the objective function has no maximum, and attempting to find one iteratively will just increase $\beta$ forever.

It's worth noting where we used the separation. If we could not find a separator then we could not partition the terms into two groups, we would instead have four types

  • Terms with $y_i = 0$ and $x_i > 0$
  • Terms with $y_i = 0$ and $x_i < 0$
  • Terms with $y_i = 1$ and $x_i > 0$
  • Terms with $y_i = 1$ and $x_i < 0$

In this case, when $\beta$ gets very large the terms with $y_i = 1$ and $x_i < 0$ will drive to negative infinity. When $\beta$ gets very negative, the $y_i = 0$ and $x_i < 0$ will do the same. So somewhere in the middle, there must be a maximum.

(*) I replaced your $y_i$ with $p_i$ because the number is a probability, and calling it $p_i$ makes it easier to reason about the situation.

$\endgroup$
  • $\begingroup$ Thank you very much Matthew for your answer! I see from your plot that there is no convergence. Why is there no convergence mathematically? What is the difference to the case where data is separable. Thanks for answering my question 2). I got this one now ^^ $\endgroup$ – Matthias Jul 21 '16 at 5:01
  • 1
    $\begingroup$ @Matthias I put together a proof, and added it to my answer. I hope that's what you're after. $\endgroup$ – Matthew Drury Jul 22 '16 at 3:35
  • 1
    $\begingroup$ Those logistic functions are weakly converging to the Heaviside function. Is there a way of extending the loss function to distributions, or changing the notion of convergence appropriately (those two are the same?) to capture this behavior? $\endgroup$ – Neal Jul 22 '16 at 14:29
  • 1
    $\begingroup$ @MatthewDrury Thank you for prove. It's a nice prove! Yes I was looking for something like this! ^^ One small side comment: I wouldn't call it a loss function, since we want to maximize it. If we take the negative of the likelihood function, then I agree that it is a loss function $\endgroup$ – Matthias Jul 23 '16 at 7:11
  • 1
    $\begingroup$ This limits $ \lim_{\beta \rightarrow \infty} \log(1 - S(\beta, x_i)) = 1$, $ \lim_{\beta \rightarrow \infty} \log(S(\beta, x_i)) = 1$ have to be equal to $0$, not to $1$. $\endgroup$ – Gusev Slava Mar 12 at 12:29

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