Logistic Regression: Don't Mix It Up

This article is part of a series on the fundamentals of machine learning.

• Part 1. About Machine Learning in Simple Terms
• Part 2. Linear Regression as Simple as It Gets
• Part 3. What Do Trees Think About?
• Part 4. Logistic Regression: Don't Mix It Up

In the previous article, we started exploring the classification problem. We covered what is probably the most intuitively understandable algorithm — decision trees. In this article, we'll look at applying regression to classification problems.

What's Wrong with Trees?

When reading the previous article, it might have seemed that decision trees are the perfect option for classification. Indeed, they can find complex dependencies, their internal logic is understandable, and the training process is reasonably fast. But in reality, they're not perfect. There are several fundamental drawbacks.

First of all — overfitting. A tree memorizes small details too well, but at the same time fails to grasp deeper patterns. As a result, the tree shows excellent performance on familiar data, but quality drops sharply as soon as it encounters data that wasn't in the training set. In the end, we have to artificially limit the tree's growth, which degrades overall performance, but it's the only way to keep the tree from simply memorizing the correct answers and instead push it to solve the problem in general terms.

Second, a tree is a greedy algorithm. It makes the best decision for each step, not for the problem as a whole. And since at some point tree construction is forcibly terminated to combat overfitting, this leads to an incomplete solution.

And third, the tree has fundamental limitations on the types of dependencies. It works very well with separate "islands" of data, but handles continuous dependencies extremely poorly. This is because the tree splits data along the coordinate axes.

The figures above show a successful and an unsuccessful case of data distribution. In the first figure, everything is fine — just three splits. But in the second one, there are already seven. Although, if we look at the data, we can see that a single diagonal line would have been enough, but a decision tree can't do that — it builds splits only along the axes.

What Can We Do?

In fact, there are several ways to deal with the shortcomings of decision trees. The first group of methods involves improving them. One option is to use not one tree, but several. Moreover, during training, each tree learns on its own subset of the data. As a result, we get a set (a "forest") of different trees. And when we need to produce an answer, we show the data to each tree separately, and then hold a vote. The winning result is what we output. This approach (called a "random forest") significantly reduces the impact of overfitting. This method is still used in some cases even now, in the era of neural network dominance.

But everything comes at a price. Here, for the most part, we pay with a loss of intuitiveness. Indeed, while a single tree's decisions are fairly understandable (you can look at its structure and see why it produced a particular answer), understanding the voting logic of many trees is much harder. Plus, the limitations regarding distributions and dependencies between data don't go away.

The second way to solve the problem is to move away from decision trees and similar algorithmic models.

What About Regression?

Let's recall how linear regression works. It works very simply: each input value is multiplied by the corresponding weight, all these products are summed, a bias is added to the sum, and that's the result:

Let's try to use the same approach for classification. What stops us from doing so? First of all — the range of output values. This is regression, which means the model's output is just any number. But we're solving a classification problem and expect only two values: 0 or 1.

The first thing that comes to mind is to simply set a threshold. For example, if the output value is positive, that's 1, if negative — 0. But the threshold approach would be extremely unstable. For example, minus one thousandth gives one answer, and one thousandth — already another. This means all output values would be concentrated very close to zero, and the slightest change in the input data could affect the result. Another problem is that the threshold function is not differentiable, meaning it has no derivative. Derivatives are very important when training any regression models, so the absence of a derivative is a very serious problem.

In fact, the best way to use regression for classification is to somehow map values from the range $\lbrack - \infty,\ + \infty\rbrack$ to the range $\lbrack 0,\ 1\rbrack$. Why would this work, since we need only two values rather than a range? The thing is, a continuous value from the $\lbrack 0,\ 1\rbrack$ range can be interpreted as the probability of one of the answers. For example, if we get a value of 0.6, we can interpret it as a 60% probability of answer 1.

This is also nice because we can set the threshold ourselves depending on the task. For example, imagine a system that automatically buys stocks if it considers them profitable. In such a situation, we'd like to avoid unnecessary risk, so the threshold can be set higher, say 90%. This means the system will only buy stocks if it's very confident about their profitability.

In other situations, on the contrary, it's better to set a lower threshold. Imagine a system that monitors bank transfers and checks whether they're fraudulent. In this case, it's better to make the system more sensitive. For example, so that it triggers at 30% confidence that the operation is fraudulent. At the same time, it doesn't have to immediately block the transfer. The decision can be passed to a human. This way, nothing important will be missed, and a human will make the final decision.

It remains to figure out how to perform the necessary range conversion. Such a conversion must be smooth, without discontinuities or jumps, so that it doesn't interfere with computing derivatives. In fact, there are many functions that can help with this, but the most common one is the sigmoid, or logistic function, which gave this classification method its name.

Figuring Out the Sigmoid

The function itself looks very simple:

If the value of $x$ tends to minus infinity, the denominator of the fraction, on the contrary, shoots off to infinity, which makes the function's value very close to zero. For very large values of $x$, the value of $e^{- x}$ tends to zero, the denominator is close to one, as is the final value of the function. As a result, its graph looks like this:

As you can see, the function smoothly and without discontinuities converts any input value into a range from zero to one.

Now all we have to do is apply this function to the regression result and get the probability of a positive answer:

Just like in ordinary linear regression, we now need to compute all the coefficients $k_{i}$ and the bias $b$.

Training

Any training is the minimization of a loss function between the predicted result and the real one:

More precisely, we minimize the function not for a single pair of values, but the sum across all pairs:

For linear regression, where the results were continuous, the loss function was simply the squared difference:

Here, however, our result is discrete (only 0 or 1). Therefore, we need to use a different function.

At this point, a question may arise: why can't we use the squared difference? After all, our output is a probability, that is, an ordinary number. This question is hard to answer right now, since we don't yet know the details of the training process. For now, we can simply say that when using the squared difference, training can happen, but it will be slow, and the result may be rather mediocre.

A different function is used for the classification problem — namely, binary cross-entropy. This function looks more complex than the simple squared difference:

Despite its apparent complexity, cross-entropy works much better for the classification problem. In the end, we need to make the sum of the functions for each pair of values as small as possible. To do this, we need to find the right coefficients $k_{i}$ and $b$.

And here comes the not-so-good news. The thing is, while we could train simple linear regression very quickly by solving a single system of equations, there's no analytical solution here. This is because our formulas are now nonlinear. So we'll have to look for other ways to find the required coefficients. Such methods exist, and there are several. We'll look at the most popular one — gradient descent.

Let's simplify the model as much as possible. We'll keep, just like in the article on regression, only one input variable $x$ and two coefficients: $k$ and $b$. We'll compute the answer using the formula:

or

Now let's write out the loss function:

As mentioned above, we minimize not the loss function, but the sum of the loss functions across all our data:

The final expression looks rather intimidating, and as already mentioned, can't be optimized analytically. So the main idea here is not to try to reach the minimum at once, but to take many small steps, gradually approaching the minimum.

Traveling Across Surfaces

If we visualize the loss function, we'll see a long, narrow trough. The bottom of this trough is the minimum of the loss function:

Notice — the minimum here is not a point, but a line. This means there are many pairs of $k$ and $b$ that work for us. We just need to find any of them.

We need to descend from the wall of the trough (the random place where we start training) to its bottom. Essentially, we need to follow this algorithm:

1. Find the direction of movement toward the minimum
2. Take a small step toward the minimum (change $k$ and $b$ by some amount)
3. Repeat steps 1 and 2 until we reach the minimum

This algorithm contains the main difference from what we used for ordinary linear regression: there, we immediately found the parameters analytically for which the loss function is at the minimum. Here, we start with random values and gradually change the parameters, approaching the solution. That is, this method is iterative — we repeatedly perform the same actions, gradually improving the result. It remains to figure out how to find the direction to the minimum.

And this is where derivatives take center stage. If we recall their properties, we'll see that the partial derivative with respect to one parameter shows how quickly the function grows with a small increase in that parameter. And here's the key idea: we need to take a step in the opposite direction from the growth. What if there are multiple variables? In that case, we must compute the derivative with respect to each variable and change each variable against the growth of its derivative. In our case, mathematically this looks like this:

The parameter $\rho$ in this expression is simply a small number (for example, 0.01) that we add to keep the step small. Since this number controls the speed of the steps, and therefore the speed of training, it's called the learning rate. I'll explain later how to choose such a number and what else it affects besides the training speed.

We proceed similarly if there are more than two parameters. In this case, we simply compute the derivatives with respect to each parameter. A vector of such derivatives is called a gradient, hence the name of the method — gradient descent. The "descent" refers to the movement toward the function's minimum.

It remains to figure out how to know that we've already reached the minimum. Here we might recall that at the minimum, the derivatives with respect to all parameters become zero and we stop. In practice, this approach usually doesn't work. The thing is, most of the time, gradient descent overshoots the minimum point, then comes back, overshoots the minimum again, now in the opposite direction, and so on. So usually, the change in derivatives is judged less strictly. Most often, we don't even look at the derivatives, but at the loss function $L$ itself. If after another step it has barely changed ($\mathrm{\Delta}L < \ \varepsilon$), we consider that we're very close to the minimum and training can be stopped. Again, there are many nuances, but they'll be covered in a separate article.

Computing Derivatives

Now that we've figured out how to train a logistic regression, it remains only to compute the derivatives.

We need to compute the derivatives of the loss function with respect to two parameters. But, as we've already seen, the final expression is rather intimidating, and computing the derivative will be quite difficult. So it's reasonable to break the computation into parts. Let's look at what the final function consists of.

The process of multiplying the input data by weights and adding the bias is called the summation function. Let's denote it with the letter $z$:

Next, we apply the sigmoid to this result. This process is called the activation function. Let's denote it with the letter $a$:

And finally, we compute the loss function between our prediction and the correct answer. Let's denote the function itself as $L$. In our case:

We need to compute two derivatives: $\frac{\partial L}{\partial k}$ and $\frac{\partial L}{\partial b}$. And here, just like in the article on linear regression, we can use the chain rule:

Similarly for $b$. Agree, it's much more convenient to compute derivatives in parts than as a whole.

Let's start computing from the last function:

Let's additionally combine into a common denominator and simplify:

Now let's compute the derivative of the sigmoid activation:

It seems there's nothing more to simplify, but here we can pull off a very elegant mathematical trick. Let's split the fraction into two:

What's the first fraction? It's our original function! So we can make this transformation:

But that's not all. Let's transform the second part:

One more trick. Let's add and immediately subtract $e^{z}$ from the numerator:

Now the final transformation. Let's divide the fraction by $e^{z}$. This is equivalent to multiplying the numerator and denominator by $e^{- z}$:

What do we see? Our original function again! As a result, the derivative of the sigmoid is fully expressed through the sigmoid itself:

But the beauty doesn't end there. Let's now compute the product of the two derivatives we've already found:

In the end, from a bulky expression, we're left with a tiny line. And we're almost ready to compute the final derivatives. All that's left is to compute the derivative of the summation function with respect to $k$ and $b$:

Everything is ready. The final formulas for the derivatives:

Another very nice thing is that if instead of one-dimensional input data we take multidimensional data, almost nothing changes in the formulas. We just need to compute a few more derivatives using the formula:

The Long-Awaited Descent

Now we have everything we need to derive the training algorithm. Initially, we initialize the coefficients $k$ and $b$ with random numbers. Usually, the numbers are quite small, in the range from zero to one hundredth. Then the training process itself begins:

1. For each pair of input data and correct answer, compute the derivatives with respect to all parameters $k$ and $b$
2. Once computed for all examples, average each derivative, that is, sum the derivatives for each example and divide by the number of examples
3. Take a gradient descent step: $k_{i} = k - \ \rho \bullet \frac{1}{n} \bullet \sum_{}^{}{x_{ij}\left( a_{j} - y_{j} \right)}$. Similarly for $b:b = b - \rho \bullet \frac{1}{n} \bullet \sum_{}^{}\left( a_{j} - y_{j} \right)$
4. Repeat steps 1-3 until we reach the minimum (or rather, end up next to it)

After training is complete, our model is ready for use. To do this, we first compute the weighted sum:

And then apply the sigmoid:

The final value $\widehat{y}$ is the probability that the object's class is 1. We can interpret this probability, as mentioned above, in different ways depending on the task.

Problems Again

Despite the fact that logistic regression seems like a very good option, it's also not without problems. On the one hand, yes, it's better than decision trees in terms of overfitting. But on the other hand, it has the exact opposite problem. Recall that decision trees worked very well with separate "islands" of data but handled continuous distributions poorly. Here, the situation is reversed.

Logistic regression draws exactly one separation line, albeit at any angle. Thus, if the data can be separated by a single line, logistic regression will work perfectly. But if such a separation is impossible, training won't succeed in any case.

Figure 2 shows a good situation for regression — the data is linearly separable. But in the first case, no matter how we draw the line, some objects will always be misclassified.

What should we do in this case? Ideally, we'd like to draw a single line, like in logistic regression, but not a straight one — one of arbitrary shape. This would allow us to separate any data, solving the problems of both logistic regression and decision trees.

And there's a way to do this. We just need to combine several logistic regressions: the outputs of some should be the inputs of others. Perhaps someone has already recognized this construction as a neural network. But I'll talk about neural networks and how they're trained in the next article.

To be continued…