Understanding complete separation for logistic regression [duplicate]

Question

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.

2. 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?

Answer 1

Here's a visual explanation of (1)

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 $\log(S(\beta, x_i))$ to negative infinity. When $\beta$ gets very large, the $y_i = 0$ and $x_i < 0$ will do the same to the corresponding $\log(1 - S(\beta, x_i))$. 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.