# Proving MLE's undefined for logistic regression with separable classes in p dimensions

According to section 4.4.5 of "The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Second Edition" by Trevor Hastie & Robert Tibshirani & Jerome Friedman:

... if the data in a two-class logistic regression model can be perfectly separated by a hyperplane, the maximum likelihood estimates are undefined (i.e. infinite)

I can see how this is the case in $$\mathbb{R}$$ as:

$$l(\beta) = \sum_{x_ix_0}\{\beta_0 + \beta_1x_i -log(1+\exp{(\beta_0 + \beta_1x_i)}\}$$ where the two classes are separated by point $$x_0$$ and coding classes as $$y_1=1$$ and $$y_2=0$$.

Now:

$$l(\beta) = \sum_{x_ix_0}\{\beta_0 + \beta_1x_0 + \beta_1(x_i - x_0) -log(1+\exp{(\beta_0 + \beta_1x_0 + \beta_1(x_i - x_0))}\}$$

Noticing

$$x_1 - x_0 > 0$$ when $$x_i>0$$,

$$x_1 - x_0 < 0$$ when $$x_i<0$$,

and setting $$\beta_0 = -\beta_1x_0$$,

this reduces to:

$$l(\beta) = \sum_{x_ix_0}\{\beta_1(x_i - x_0) -log(1+\exp{(\beta_1(x_i - x_0))}\}$$

which is maximised as $$\beta_1 \to \infty$$

Giving the following (undefined) MLE's: $$\beta_0 = -sign(x_0)\infty$$ and $$\beta_1 = \infty$$

How can this be proven in $$p$$ dimensional space ($$\mathbb{R}^p$$) and thus a separating hyperplane?

• There's no difference at all, because modulo the hyperplane, you're back down to one dimension.
– whuber
Commented Feb 24, 2020 at 17:31
• Thanks @whuber . Would you mind expanding on that? I have updated my question with how I approached it in $\mathbb{R}$ but I'm not entirely clear on how to extend to $\mathbb{R}^p$ Commented Feb 24, 2020 at 18:04

The data are a sequence of observations of vectors of explanatory variables $$x_i$$ in $$p$$ dimensions, to which are associated binary responses $$y_i\in\{0,1\}.$$ "Separated by a hyperplane" means there exists a nonzero $$p$$-vector $$v$$ for which $$x_i^\prime v \gt 0 \text{ when } y_i=1 \text{ and otherwise }x_i^\prime v \lt 0.$$

By minimizing $$x_i^\prime v$$ over all observations with $$y_i=1$$ and minimizing $$-x_i^\prime v$$ over all other observations we obtain a positive number $$a\gt 0$$ for which

$$x_i^\prime v \ge a \text{ when } y_i=1 \text{ and otherwise }x_i^\prime v \le -a.\tag{*}$$

It turns out the issue is reduced to analyzing what happens in the direction of $$v,$$ which essentially reproduces the one-dimensional situation. The details follow. They reveal that the quotation is a little misleading: there is no such thing as "the" maximum likelihood estimate and they aren't all characterized by vectors of "undefined" coefficients.

Let's pause a moment to discuss Bernoulli variables, or "unfair coins." Logistic regression relies on a probability model of $$y_i$$ as an independent flip of an unfair coin, but it does so in a special way. It posits an increasing "link function" $$h$$ that continuously maps the open interval of possible probabilities $$(0,1)$$ one-to-one onto the real numbers. A formula for $$h$$ needn't concern us here; all that matters is the implication that probabilities approaching $$0$$ and $$1$$ correspond under $$h$$ to real numbers that get arbitrarily large in size: that is, "approach infinity." Specifically, $$h$$ has an inverse $$h^{-1}$$ and

$$\lim_{x\to\infty}h^{-1}(x) = 1;\quad \lim_{x\to-\infty}h^{-1}(x) = 0.$$

Back to the question. The likelihood for coefficients $$\beta=(\beta_1, \ldots, \beta_p)$$ is the product, over all observations, of the chance that a Bernoulli variable with parameter $$x_i\beta$$ actually equals $$y_i:$$

$$\mathcal{L}(\beta) = \prod_{i\mid y_i = 1} h^{-1}(x_i^\prime \beta)\, \prod_{i\mid y_i = 0} (1-h^{-1}(x_i^\prime \beta)).$$

Consider a positive real number $$\lambda$$ and use the inequalities $$(*)$$ and the fact $$h^{-1}$$ is increasing (since $$h$$ is) to bound the likelihood for $$v\lambda$$ by

$$\mathcal{L}(v\lambda) = \prod_{i\mid y_i = 1} h^{-1}(x_i^\prime v\lambda)\, \prod_{i\mid y_i = 0} (1-h^{-1}(x_i^\prime v\lambda)) \ge \prod_{i\mid y_i=1} h^{-1}(a\lambda)\, \prod_{i\mid y_i = 0} (1-h^{-1}(-a\lambda)).$$

Because $$a\gt 0,$$ $$a\lambda\to\infty$$ and $$-a\lambda\to-\infty$$ as $$\lambda\to\infty,$$ showing

$$\lim_{\lambda\to\infty} h^{-1}(a\lambda) = 1 = \lim_{\lambda\to\infty} 1 - h^{-1}(-a\lambda),$$

whence

$$\lim_{\lambda\to\infty} \mathcal{L}(v\lambda) \ge \prod_{i\mid y_i=1} 1\, \prod_{i\mid y_i=0} 1 = 1.$$

This is a global maximum because the likelihood, being a product of probabilities, cannot exceed $$1.$$

We're not quite done, because it's logically possible for most of the components of $$v$$ to be zero. When multiplied by large $$\lambda,$$ they would remain zero and not "become undefined" as claimed in the quotation.

The last step is to note that we may always arrange for every component of $$v$$ to be nonzero. One proof of this notices that the values $$x_i v$$ are continuous functions of the components of $$v$$ and therefore the smallest of all the $$|x_i v|$$ (equal to $$a$$ above) is a continuous function of the components. Since $$a\gt 0,$$ we may change every nonzero component of $$v$$ by a sufficiently small amount to assure that the smallest of all the $$|x_i v|$$ is still greater than, say, $$a/2.$$ This new reduced value for $$a$$ will serve just as well in the foregoing analysis. Now, using this adjusted $$v$$ (which defines a different separating hyperplane), all the components of $$\beta=v\lambda$$ diverge as $$\lambda\to\infty.$$

A careful statement of the conclusion, then, is

When a separating hyperplane exists, the likelihood can be maximized in a manner that causes all the coefficients of $$\beta$$ to diverge.

It does not rule out solutions in which some components of $$\beta$$ are finite: but the argument clearly implies that

1. any such components must be zero;

2. at least one component will diverge; and

3. there can be infinitely many directions $$v$$ for which the likelihood of $$\beta=v\lambda$$ is maximized as $$\lambda\to\infty.$$