2
$\begingroup$

Our training data will either be linearly separable or non-linear separable. In both cases the decision boundary is defined by: $$ f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b = 0 $$

and we classify them based on the value of $\sigma(\mathbf{w} \cdot \mathbf{x} + b)$. If this value is greater than 0.5 then the we classify as $y=1$ and and $y=0$ otherwise. That is we classify a point based on the side of the hyperplane it lies on.

When the data are linearly separable, then: $$\exists \mathbf{w},b \,\, \text{such that} \begin{cases} y = 1, \quad \text{for all training points with $y=1$} \\ y = 0, \quad \text{for all training points with $y=0$} \end{cases}$$

One can show that when the data are linearly separable the weights will go to infinity. In other words, gradient descent would not converge. Lets say that at the $k$-th iteration of the gradient descent we have the weights $\mathbf{w}_k$ and $b_k$ and these weights perfectly separate the data. Since $\mathbf{w}_k, b_k$ perfectly separate the data, so do the weights $\alpha \cdot \mathbf{w}_k, \alpha \cdot b_k$, where $\alpha > 0$.

So gradient descent would keep increasing the weights without bound. Is there a problem?

My reasoning is the following: lets say $\mathbf{w} = (w_1, w_2) = (2, 3)$ and $b=1$. The decision function is:

$$2x_1 + 3x_2 + 1 = 0$$

If these weights separate the data, so do the weights (20000, 30000) and $b=10000$ (just multiply the above equation with 10000). So the decision function doesn't change. The only thing that changes when weights get very large is the value returned by the sigmoid (see the figure). So if we want to classify a new point, the answered returned in both cases would be the same.

Now, in the answer of a related question it is stated that there is overfitting (in the case of separable data) when the weights go to infinity. Sorry, but I don't get it. When we regularize in Linear regression for example, we regularize in order to avoid fitting noise and not because large weights are somehow "bad". Although I understand, that penalizing the weights will prevent the model to achieve a zero training loss (predicted probabilities $\to 1$ for training points with $y=1$ and predicted probabilities $\to 0$ for training points with $y=0$), I can't understand how this prevents from overfitting.

Again from the figure, if $w=2$ was the weight we achieved when regularization was applied and $w=20$ when regularization was not applied, if we were asked to classify a point with $x=2$, we will predict $y=1$ in both cases, although with different levels of "confidence" (apologize if this term is not proper).

Can someone explain how large weights translate to overfitting when the data are linearly separable?

$\endgroup$
2
  • 5
    $\begingroup$ 1) Do you understand the purpose of regularization in linear regression? // 2) Why must there be a decision threshold at all? $\endgroup$
    – Dave
    Dec 18, 2022 at 13:05
  • $\begingroup$ @Dave With regularization we want to control overfitting. That is we don't want if we retrain our algorithm on a little different training set to return us a very different model. Same with the case of Logistic Regression when data are not linear separable. In case of linear separable data the weights go to infinity and the decision boundary doesn't change. What is the purpose of regularization then? I suppose to avoid to weights to go to infinity? $\endgroup$
    – ado sar
    Dec 18, 2022 at 18:12

2 Answers 2

4
$\begingroup$

If we now multiply $f$ by a positive scalar $\lambda$ then the decision boundary doesn't change, [...]

This has nothing to do with regularization. When regularizing the model we are not multiplying the outputs by the penalty term. Using ridge regression as an example, during the optimization, we are minimizing

$$ \operatorname{arg\,min}_\boldsymbol{\beta} \| y - \mathbf{X}\boldsymbol{\beta} \|^2_2 + \lambda\| \boldsymbol{\beta} \|^2_2 $$

so in more abstract terms, this is

$$ \operatorname{arg\,min}_\boldsymbol{\beta} \; \text{loss}\big(y,\, f(\mathbf{X}; \boldsymbol{\beta})\big) + \text{penalty}(\boldsymbol{\beta}) $$

But when doing the predictions, we just use $f(\mathbf{X}; \boldsymbol{\beta})$ with the $\boldsymbol{\beta}$ parameters obtained using by minimizing the regularized loss. At no point we multiply $f$ by $\lambda$.

There is no clear relationship between decision boundaries, thresholds, and regularization. Regularization leads to finding different functions, making different predictions.

$\endgroup$
12
  • $\begingroup$ In the case of linearly separable data the weights will go to infinity. Is correct to say that regularization prevents weights to go to infinity? $\endgroup$
    – ado sar
    Dec 18, 2022 at 18:18
  • $\begingroup$ The $\lambda$ parameter was not referring to the regularization parameter. I just stated that muliplying the weights and the itnercept doesn't change the decision boundary. I will change the symbol to avoid further confusions. $\endgroup$
    – ado sar
    Dec 19, 2022 at 12:04
  • 1
    $\begingroup$ @adosar so your question is not referring to regularization? If $\lambda$ has nothing to do with regularization, then it seems to be irrelevant to the rest of your question. $\endgroup$
    – Tim
    Dec 19, 2022 at 12:05
  • $\begingroup$ My question is referring to regularization. What I can't understand is how regularization help us when the data are linearly-separable and as such weights go to infinity. $\endgroup$
    – ado sar
    Dec 19, 2022 at 12:06
  • 1
    $\begingroup$ @adosar how does this relate to multiplying the parameters by arbitrary constant (if $\lambda$ is not a regularization parameter)? $\endgroup$
    – Tim
    Dec 19, 2022 at 12:07
2
$\begingroup$

The observation that logistic regression estimates probabilities, not a decision boundary, is sufficient to answer the entire question. Changing the weights changes the probability estimates. The question's focus on classification, instead of probability estimation, is the origin of the confusion.

Logistic regression is not a classifier

Our training data will either be linearly separable or non-linear separable. In both cases the decision boundary is defined by: $$ f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b = 0 $$ and we classify them based on the value of $\sigma(\mathbf{w} \cdot \mathbf{x} + b)$.

Logistic regression is not a classifier; instead, logistic regression estimates the probabilities of class membership. Using a decision rule to create a binary decision using a threshold is an entirely ancillary procedure that a person might decide to use atop logistic regression. However, conflating classification and regression is the origin of a great many misunderstandings. See:

Separability implies we can arbitrarily improve the model fit (increase the log-likelihood, equivalently decrease the cross-entropy), which means the estimated probabilities will tend to 0 and 1, with no "middle." So these probability estimates aren't enormously useful if you need to characterize uncertainty, or prioritize which observations are greater risk of some condition.

Another reason you might care about separability is if you're trying to precisely estimate a coefficient. A very large coefficient might have a correspondingly large variance. Or, in a slightly different flavor, we might wonder whether randomly switching a small number of labels might significantly change the estimated coefficients.

This thread How to deal with perfect separation in logistic regression? has a number of suggestions for alternatives to penalization to "deal with" separability in logistic regression. Each solution addresses the problem of separability, but with a slightly different perspective viz. goals and trade-offs.

Weights growing arbitrarily large is not inherently a problem

So gradient descent would keep increasing the weights without bound. Is there a problem?

Whether this is a problem depends on your goals. Your question starts from the premise that the only thing you care about is a decision function. If this is the case, then separability doesn't obstruct your goals, so you don't need to take special steps to fix a non-problem.

Separability and overfitting are distinct

Now, in the answer of a related question it is stated that there is overfitting (in the case of separable data) when the weights go to infinity. Sorry, but I don't get it. When we regularize in Linear regression for example, we regularize in order to avoid fitting noise and not because large weights are somehow "bad".

Although this text links to an answer that I wrote, what you've written does not follow from the text of the answer.

I do not make the claim that there is overfitting when the weights go to infinity. I state that adding a penalty bounds the weights away from infinity. This is true when separability is present, and it's trivially true when separability is not present.

Independently, I also state that penalization can be used to prevent overfitting. But models can overfit even when separability is not present. Overfitting is a separate issue from separability.

My answer does not say that large weights are "bad," whatever that might mean.

Large weights and overfitting are distinct

Can someone explain how large weights translate to overfitting when the data are linearly separable?

The reasoning here is backwards. If the data are linearly separable, then the weights can be arbitrarily increased in magnitude and improve the model fit (decrease cross-entropy/increase log-likelihood). When separability is present, the fit can be improved arbitrarily by increasing the magnitude of the weights; the result is that the weights grow large.

But it is not true that large weights imply overfitting on their own. Neither is it true that large weights on their own imply separability. I think the previous points make this clear, but we also have a number of answers about why shrinkage methods work; notably, shrinkage methods can be used to reduce overfitting whether or not separability is present. See:

$\endgroup$
2
  • $\begingroup$ This sentence was very useful: "these probability estimates aren't enormously useful if you need to characterize uncertainty, or prioritize which observations are greater risk of some condition"? Can you give a real example? Also, do these "overconfident" probabilities affect the performance metrics? $\endgroup$
    – ado sar
    Dec 20, 2022 at 23:16
  • $\begingroup$ calibration is an example: predicted probabilities should match true probabilities. $\endgroup$
    – Sycorax
    Dec 21, 2022 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.