Logistic Regression

Logistic regression is a binary classifier used for categorical labels that builds on linear regression, but instead of predicting a continuous output, it applies the sigmoid function (specifically, the logistic sigmoid) to the linear output to produce a probability. This transformation maps any real-valued input to a value between 0 and 1, which allows logistic regression to output the probability that a given input belongs to a particular class.

As it happens for linear regression and polynomial regression, the logistic regression changes the parameters in order to minimize the loss. The parameters are the following:

• Coefficients ${\beta }_1,{\beta }_2,\dots ,{\beta }_k$ for each feature in the input vector $x$
• Intercept (or bias) ${\beta }_0$ which represents a constant offset in the decision boundary.

The logistic regression loss is defined as:

$${\ell }_{\Theta }(\{x_i,y_i\})=\sum _{i=1}^n(y_i-\sigma (a{x}_i+b){)}^2$$

Where $\sigma (x)=\frac{1}{1+e^{-x}}$ is the logistic sigmoid function

The sigmoid function is used to squash the output of $f$ into a value between $(0,1)$. This means that the function has a saturation effect as it maps $\mathbb{R}\to (0,1)$.

Note that this new loss is non-linear with respect to the parameters, since they appear in the non-linear sigmoid function, and it’s also non-convex.

We want the loss to be convex in order to perform Gradient Descent, so we can write a new loss function with this property that will output an high value if the output label is wrong, and a low value if it’s true.

$$c(x_i,y_i)=\{\begin{array}{ll}-\ln (\sigma (a{x}_i+b))& y_i=1\\ -\ln (1-\sigma (a{x}_i+b))& y_i=0\end{array}$$

This works well because if the prediction $\sigma (a{x}_i+b)$ is near the $0$, and the true label is $1$, then $-\ln (\sigma (a{x}_i+b))\to \infty$. On the other hand, if the true label is $0$, then $-\ln (1-\sigma (a{x}_i+b))\to 0$.

We can rewrite the function on a single line:

$$c(x_i,y_i)=-y_i\ln (\sigma (a{x}_i+b))-(1-y_i)\ln (1-\sigma (a{x}_i+b))$$

The function is still non-linear with respect to the parameter, but is convex. This is known as Binary Cross Entropy Loss.

The loss for the entire dataset will be:

$${\ell }_{\Theta }(\{x_i,y_i\})=\sum _{i=1}^{n}c(x_i,y_i)$$

Closed form solution for Logistic Regression

As we did for the linear regression case, we want to find a closed form solution by putting the gradient of the loss equal to zero. Since the loss is convex, we will find the global minimum.

Math

Finding theta such as ${\nabla }_{\Theta }{\ell }_{\Theta }=0$

We set the gradient to zero and we want to solve it for $\Theta$.

$$\begin{array}{r}{\nabla }_{\Theta }\sum _{i=1}^n{y}_i\ln \left(\sigma \left(a{x}_i+b\right)\right)+\left(1-y_i\right)\ln \left(1-\sigma \left(a{x}_i+b\right)\right)=0\end{array}$$

Since the gradient operation is linear, the gradient of the summation is just the sum of the gradient of each term, so we can consider just the gradient of a single term.

$$\begin{array}{r}{\nabla }_{\Theta }{y}_i\ln \left(\sigma \left(a{x}_i+b\right)\right)+\left(1-y_i\right)\ln \left(1-\sigma \left(a{x}_i+b\right)\right)\\ {\nabla }_{\Theta }{y}_i\ln \left(\sigma \left(a{x}_i+b\right)\right)+{\nabla }_{\Theta }\left(1-y_i\right)\ln \left(1-\sigma \left(a{x}_i+b\right)\right)\\ y_i{\nabla }_{\Theta }\ln \left(\sigma \left(a{x}_i+b\right)\right)+\left(1-y_i\right){\nabla }_{\Theta }\ln \left(1-\sigma \left(a{x}_i+b\right)\right)\\ y_i{\nabla }_{\Theta }\underset{f(g(h(\Theta )))}{\underbrace{\ln \left(\sigma \left(a{x}_i+b\right)\right)}}+\left(1-y_i\right){\nabla }_{\Theta }\ln \left(1-\sigma \left(a{x}_i+b\right)\right)\end{array}$$

We can apply the chain rule in order to take the derivative of the composition of three function.

$$\begin{array}{r}\frac{\partial }{\partial a}f(g(h(a,b)))=\frac{\partial f}{\partial g}\cdot \frac{\partial g}{\partial h}\cdot \frac{\partial h}{\partial a}\end{array}$$

We solve the first partial derivative:

$$\begin{array}{r}\frac{\partial h}{\partial a}=\frac{\partial }{\partial a}a{x}_i+b=x_i\end{array}$$

We solve the second partial derivative:

$$\begin{array}{r}\frac{\partial g}{\partial h}=\frac{\partial \sigma (a{x}_i+b)}{\partial (a{x}_i+b)}=\frac{\partial }{\partial \left(a{x}_i+b\right)}\frac{1}{1+e^{-\left(a{x}_i+b\right)}}=\frac{e^{-\left(a{x}_i+b\right)}}{{\left(1+e^{-\left(a{x}_i+b\right)}\right)}^2}\\ =\frac{1}{1+e^{-\left(a{x}_i+b\right)}}\frac{e^{-\left(a{x}_i+b\right)}}{1+e^{-\left(a{x}_i+b\right)}}\\ =\frac{1}{1+e^{-\left(a{x}_i+b\right)}}\frac{\left(1+e^{-\left(a{x}_i+b\right)}\right)-1}{1+e^{-\left(a{x}_i+b\right)}}\\ =\frac{1}{1+e^{-\left(a{x}_i+b\right)}}\left(1-\frac{1}{1+e^{-\left(a{x}_i+b\right)}}\right)\\ =\text{ - }\sigma \left(a{x}_i+b\right)\left(1-\sigma \left(a{x}_i+b\right)\right)\end{array}$$

Finally we solve the third partial derivative:

$$\begin{array}{r}\frac{\partial f}{\partial g}=\frac{\partial \ln \left(\sigma \left(a{x}_i+b\right)\right)}{\partial \sigma \left(a{x}_i+b\right)}=\frac{1}{\sigma \left(a{x}_i+b\right)}\end{array}$$

Plugging everything in the equation at $(6)$:

$$\begin{array}{r}\frac{\partial }{\partial a}f(g(h(a,b)))=\frac{1}{\sigma \left(a{x}_i+b\right)}\cdot \sigma \left(a{x}_i+b\right)\left(1-\sigma \left(a{x}_i+b\right)\right)\cdot x_i\\ =\left(1-\sigma \left(a{x}_i+b\right)\right)\cdot x_i\end{array}$$

And so:

$$\frac{\partial }{\partial a}\ln \left(\sigma \left(a{x}_i+b\right)\right)=\left(1-\sigma \left(a{x}_i+b\right)\right)x_i$$

Now this should be done also for the left ther of $(5)$, and everything should be repeated w.r.t. $b$ in order to compute the full gradient.

We can see from a part of the partial derivative which constitutes the gradient:

$$\frac{\partial }{\partial a}\ln \left(\sigma \left(a{x}_i+b\right)\right)=\left(1-\sigma \left(a{x}_i+b\right)\right)x_i$$

that the system of equations that we have when we set the gradient to $0$ wouldn’t be a linear system, since both $a$ and $b$ are involved in a non-linear function and so it cannot be easily solved.

Furthermore, the system is a transcendental equation, because it involves the exponential function inside the sigmoid function, which definition is the sum of an infinite series. Because of that, an analytical solution, and so a closed form solution, doesn’t exist.

In order to find the parameters that minimize the loss, we need to use an iterative method like stochastic gradient descent.

Multinomial Logistic Regression

If the output label are not binary, we want to perform multi-class classification, and so we need multinomial logistic regression.

The cost function for more than 2 classes translates to:

$$c(x_i,y_i)=-\sum _{j=1}^K{1}_{ij}\ln \left(P(y=j|x_i)\right)$$

Where $P(y=j|x_i)$ can be substituted with the softmax function, and so the final loss function becomes:

$$c(x_i,y_i)=-\sum _{j=1}^K{y}_{ij}\ln \left(\frac{e^{{\beta }_j^T{x}_i}}{{\sum }_{k=1}^K{e}^{{\beta }_k^T{x}_i}}\right)$$

Where:

• $x$ is the feature vector
• $K$ is the number of classes
• ${\beta }_j$ is the weighted vector for class $j$
• $1_{ij}$ is the indicator function, which returns $1$ if $y_i=j$ (the true class for $x_i$ is j), and $0$ otherwise.

Note

The softmax function is used instead of the sigmoid since the first can squash into the interval $[0,1]$ multiple values, considering them all in the process, while the latter only works with two values independently. Using the sigmoid won’t return a vector that sums to 1, hence not a probability distribution.

---

tags: machine-learning