Logistic regression

Main assumption:

$$log(\frac{p_j}{1-p_j}) = w x_j$$

i.e. the logarithm odd ratio of the label is a linear function of feature vector $x_j$, with $p_j => p(y_j = 1)$ The sigmoid loss comes directly from this basic assumption! We can also express the probability of $y=1$ as a function of weights by rewriting:

$$p_j(w)=Sigmoid(w x_j)$$

Derivation:

In the logit function, we are actually interested in $p_j$ i.e. the function argument. To get to it, we must compute the inverse of the logit (which is the sigmoid), by rewriting the formula as an expression for $p_j$. For convenience, I write $w \dot x_j = y$. Then we have:

$$y = log \frac{ p_j }{ 1 - p_j}$$ $$e^{y} = \frac{ p_j }{ 1 - p_j}$$ $$1+e^{y} = \frac{ 1 }{ 1 - p_j}$$ $$\frac{1}{1+e^{y} } = 1 - p_j$$ $$p_j = 1 - \frac{1}{1+e^{y} }$$

Also see Bishop p. 197 for a way to write posterior class probabilities in binary classification as the logistic sigmoid. He instead directly starts with the sigmoid and derives the logit later as the inverse.

Use $Sigmoid(-x)=1-Sigmoid(x)$ to write out likelihood $p(D|w)$ under the assumption of i.i.d. from general form $p(D|w) = \prod_j^J p^(y_j=1)^{y_j} (1-p(y_j=1)^{1-y_j}) $:

$$p(D|w) = \prod_j^J p_j(w)^{y_j} p_j(-w)^{1-y_j}$$

As usual, we use the log likelihood in practice. If we take the negative log likelihood as a loss function, we get the cross entropy loss.

Also handy to know the derivative of the sigmoid

$$\frac{ \partial \sigma }{ \partial a} = \sigma ( 1 - \sigma)$$

Bonus exercise: Show that the norm of the maximum likelihood estimate of the weights tends to infinity when the dataset is linearly separable.

I found that this is exercise 4.14 in Bishop, under 4.3.2. Logistic Regression.

If our data is linearly separable, then for each data point we either have $w^T \phi(x_n) > 0$ let's say when it belongs to $C_1$, or $w^T \phi(x_n) < 0$ when it belongs to $C_2$. We can assume that we have already found the weight vector linearly separating the dataset. From here on, the log likelihood loss can only be lowered by assigning $p(C_1|x_n)=1$ to all $x_n \in C_1$ and $p(C_1|x_m)=0$ for all $x_m \in C_2$. Due to the squashing behavior of the sigmoid, this is achieved by taking the limit $w^T \phi(x_n) -> \infty$ and $w^T \phi(x_m) -> -\infty$. This in turn can only be achieved by $|w| -> \infty$ because $\phi$ is a fixed linear basis function.

This is clearly a scenario of overfitting. For linearly separable data, you will observe that the loss keeps decreasing, but this does not actually mean you learn anything new, because you are achieving just only by inflating the norm of the weight vector.

This will lead to very bad error calibration unless you have infinite data points in the training set. If the training set is linearly separable then for each prediction the assigned probability will be very high (approaching 1). This means that any errors made on the testing set will also be assigned a high probability; hence the bad error calibration.

From Bishop:

It is worth noting that maximum likelihood can exhibit severe over-fitting for data sets that are linearly separable. This arises because the maximum likelihood solution occurs when the hyperplane corresponding to $\sigma=0.5$, equivalent to $w^T \phi = 0$, separates the two classes and the magnitude of $w$ goes to infinity. In this case, the logistic sigmoid function becomes infinitely steep in feature space, corresponding to a Heaviside step function, so that every training point from each class $k$ is assigned a posterior probabibility $p(C_k|x)=1$. Furthermore, there is typically a continuum of such solutions because any separating hyperplane will give rise to the same posterior probabilities at the training data points, as will be seen later in Figure 10.13. Maximum likelihood provides no way to favour one such solution over another, and which solution is found in practice will depend on the choice of optimization algorithm and on the parameter initialization. Note that the problem will arise even if the number of data points is large compared with the number of parameters in the model, so long as the training data set is linearly separable. The singularity can be avoided by inclusion of a prior and finding a MAP solution for $w$, or equivalently by adding a regularization term to the error function. (Bishop, p.206)