# Why is logistic regression a linear classifier?

Since we are using the logistic function to transform a linear combination of the input into a non-linear output, how can logistic regression be considered a linear classifier?

Linear regression is just like a neural network without the hidden layer, so why are neural networks considered non-linear classifiers and logistic regression is linear?

-
Transforming "a linear combination of the input into a non-linear output" is a basic part of the definition of a Linear Classifier. That reduces this question to the second part, which amounts to demonstrating that Neural Networks cannot generally be expressed as linear classifiers. – whuber Apr 12 '14 at 19:51
@whuber: How do you explain the fact that a logistic regression model can take polynomial predictor variables (e.g. $w_1 \cdot x_1^2 + w_2 \cdot x_2^3$) to produce a non-linear decision boundary? Is that still a linear classifier? – stackoverflowuser2010 Jun 25 at 22:33
@Stack The concept of "linear classifier" appears to originate with the concept of a linear model. "Linearity" in a model can take on several forms, as described at stats.stackexchange.com/a/148713. If we accept the Wikipedia characterization of linear classifiers, then your polynomial example would be viewed as nonlinear in terms of the given "features" $x_1$ and $x_2$ but it would be linear in terms of the features $x_1^2$ and $x_2^3$. This distinction provides a useful way to exploit the properties of linearity. – whuber Jul 12 at 13:12

Logistic regression is linear in the sense that the predictions can be written as $$\hat{p} = \frac{1}{1 + e^{-\hat{\mu}}}, \text{ where } \hat{\mu} = \hat{\theta} \cdot x.$$ Thus, the prediction can be written in terms of $\hat{\mu}$, which is a linear function of $x$. (More precisely, the predicted log-odds is a linear function of $x$.)

Conversely, there is no way to summarize the output of a neural network in terms of a linear function of $x$, and that is why neural networks are called non-linear.

Also, for logistic regression, the decision boundary $\{x:\hat{p} = 0.5\}$ is linear: it's the solution to $\hat{\theta} \cdot x = 0$. The decision boundary of a neural network is in general not linear.

-
You answer is the most clear and uncomplicated to me so far. But I'm a bit confused. Some people say that the predicated log-odds is a linear function of $x$ and others say it's a linear function of $\theta$. So?! – Jack Twain Apr 16 '14 at 16:56
then also by your explanation. Can we say that the predication of the neural network is a linear function of the last hidden layer's activations? – Jack Twain Apr 16 '14 at 17:01
The predicted log-odds $\hat{\theta} \cdot x$ is linear in both $\hat{\theta}$ and $x$. But usually we are most interested in the fact that the log-odds is linear in $x$, because this implies that the decision boundary is linear in $x$ space. – Stefan Wager Apr 16 '14 at 17:58
Sure - one way to think about neural nets is that the lower layers build a good feature representation, and then the top layer is a linear classifier. – Stefan Wager Apr 16 '14 at 18:00
I've been using the definition that a classifier is linear if its decision boundary is linear in $x$ space. This is not the same as the predicted probabilities being linear in $x$ (which would be impossible apart from trivial cases, since probabilities must lie between 0 and 1). – Stefan Wager Apr 16 '14 at 22:01

The output of binary regression is a probability of class membership; combined with some decision rule that puts observations into classes, there is quite literally a line drawn through the predicted probabilities that places an observation into one class or another.

While the logistic function is nonlinear, that's not the sense in which "linear" is meant when describing types of classifiers. There appear to be two similar notions of associated with the phrase "linear classifier.

First is the one I was taught. Imagine the classic

A B
B A


classification problem, where A and B are all points on the same plane. In this case, I was taught that this classification problem requires a nonlinear classifier because you can't draw a single line through 2-space that will sort A from B, but you can incorporate Boolean logic into a neural net or nonlinear classifier that will.

But @whuber has pointed out that this definition is a little fast-and-loose with mathematical particulars. While you can't draw a single line to separate the points, there is a simple function which can: if A class is at $(x,y)=(-1,1)$ and $(1, -1)$ and class B are at $(1,1)$ and $(-1,-1)$, then $w=(1,1)$ and $f(t)=||t|-\frac{1}{2}|-\frac{1}{2}$, using the wikipedia notation $f(wx)$ as our classifier.

But the more precise way to think about this is @whuber's presentation, which I record here for completeness, and because I can't state it any better:

Starting with the idea of linear boundary (which by definition is the zero set of a linear form given by the weights vector $w, x→w⋅x$), any monotonic injective function $f:\mathbb{R}→\mathbb{R}$ will preserve the classification in the sense there exists a number $\lambda$ such that $f(w⋅x)≤\lambda$ determines a half-space with the same boundary and $f(w⋅x)>\lambda$ is its complement. (Some non-injective functions can work, too.) On the other hand, for any classifier with a boundary that is not a union of hyper-planes no combination of any w with any f will work.

In the particular case of my A vs B problem, @whuber has show that there is some function that will classify A and B. But this function is not monotonic injective: $f(-1)=f(1)$, and the derivative changes sign on its domain.

-
Well said. Thank goodness logistic regression is not a classifier. – Frank Harrell Apr 12 '14 at 19:56
@FrankHarrell Thanks! – General Abrial Apr 12 '14 at 20:00
If nonlinearity is unimportant, as you write, then one can demonstrate that your classic problem enjoys a "linear classifier," too. Suppose, for instance, the A's were located at $(x,y)=(-1,1)$ and $(1,-1)$ while the B's were at $(1,1)$ and $(-1,-1)$. Let $w=(1,1)$ and $f(t)=||t|-1/2|-1/2$. Then the set $S=\{(x,y)|f(w\cdot(x,y))\le 0\}$ contains the A's while its complement contains the B's. This actually satisfies Wikipedia's definition of a linear classifier, BTW. The important point is that the logistic transformation is injective. – whuber Apr 12 '14 at 20:07
@whuber You continue to amaze me. What do you make of my revision? – General Abrial Apr 12 '14 at 20:24
Starting with the idea of linear boundary (which by definition is the zero set of a linear form given by the weights vector $w$, $x\to w\cdot x$), any monotonic injective function $f:\mathbb{R}\to\mathbb{R}$ will preserve the classification in the sense there exists a number $\lambda_f$ such that $f(w\cdot x)\le\lambda_f$ determines a half-space with the same boundary and $f(w\cdot x)\gt\lambda_f$ is its complement. (Some non-injective functions can work, too.) OTOH, for any classifier with a boundary that is not a union of hyperplanes no combination of any $w$ with any $f$ will work. – whuber Apr 12 '14 at 20:47

It we have two classes, $C_{0}$ and $C_{1}$, then we can express the conditional probability as, $$P(C_{0}|x) = \frac{P(x|C_{0})P(C_{0})}{P(x)}$$ applying the Bayes' theorem, $$P(C_{0}|x) = \frac{P(x|C_{0})P(C_{0})}{P(x|C_{0})P(C_{0})+P(x|C_{1})P(C_{1})} = \frac{1}{1+ \exp\left(-\log\frac{P(x|C_{0})}{P(x|C_{1})}-\log \frac{P(C_{0})}{P(C_{1})}\right)}$$ the denominator is expressed as $1+e^{\omega x}$.

Under which conditions reduces the first expression to a linear term?. If you consider the exponential family (a canonical form for the exponential distributions like Gauß or Poisson), $$P(x|C_{i}) = \exp \left(\frac{\theta_{i} x -b(\theta_{i})}{a(\phi)}+c(x,\phi)\right)$$ then you end up having a linear form, $$\log\frac{P(x|C_{0})}{P(x|C_{1})} = \left[ (\theta_{0}-\theta_{1})x - b(\theta_{0})+b(\theta_{1}) \right]/a(\phi)$$

Notice that we assume that both distributions belong to the same family and have the same dispersion parameters. But, under that assumption, the logistic regression can model the probabilities for the whole family of exponential distributions.

-

As Stefan Wagner notes, the decision boundary for a logistic classifier is linear. (The classifier needs the inputs to be linearly separable.) I wanted to expand on the math for this in case it's not obvious.

The decision boundary is the set of x such that $${1 \over {1 + e^{-{\theta \cdot x}}}} = 0.5$$

A little bit of algebra shows that this is equivalent to $${1 = e^{-{\theta \cdot x}}}$$

or, taking the natural log of both sides,

$$0 = \theta \cdot x = \sum\limits_{i=0}^{n} \theta_i x_i$$

so the decision boundary is linear.

The reason the decision boundary for a neural network is not linear is because there are two layers of sigmoid functions in the neural network: one in each of the output nodes plus an additional sigmoid function to combine and threshold the results of each output node.

-