3
$\begingroup$

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_i<x_0}\{-log(1+\exp{(\beta_0 + \beta_1x_i)}\} + \sum_{x_i>x_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_i<x_0}\{-log(1+\exp{(\beta_0 + \beta_1x_0 + \beta_1(x_i - x_0))}\} + \sum_{x_i>x_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_i<x_0}\{-log(1+\exp{(\beta_1(x_i - x_0))}\} + \sum_{x_i>x_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?

$\endgroup$
2
  • $\begingroup$ There's no difference at all, because modulo the hyperplane, you're back down to one dimension. $\endgroup$
    – whuber
    Commented Feb 24, 2020 at 17:31
  • $\begingroup$ 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$ $\endgroup$
    – Seraf Fej
    Commented Feb 24, 2020 at 18:04

1 Answer 1

3
$\begingroup$

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

$\endgroup$
0

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.