4
$\begingroup$

Let us say that the predictor X perfectly predicts the label Y such that Y = 1 if X >= c and Y = 0 if X < c. Then why can't linear regression give zero classification error?

This question was asked in Machine Learning course on Coursera and according to them, zero classification rate isn't possible. I can't see why is this the case. Of course, I am assuming that this condition is true forever and not just for the training set (no such mention in the question)

Edit:- Let me break the problem down so that you know what I am thinking -

  1. According to the question, there is a variable X and a variable Y such that if X >= C (some fixed value) then Y = 1 and if X < C then Y = 0.

  2. Now, according to the definition of classification error -

    classification error = (no. of misclassified objects)/(total no. of objects)

  3. By this definition, it means that Y was supposed to be 1 when it was classified as 0 (or the other way around).

  4. This means that there exists a value C such that X >= C but the hypothesis h(x) classified it as 0. (Am I right till here?)

  5. But according to the question, this can never be the case.

  6. Now, here is the part where I am getting confused - is the question only talking about training data? Or is the question actually stating the property of the entire population?

If the question is talking only about training data, then the answer is understandable. However, if the property of the predictor is true throughout the population, then I am unable to understand it.

Please let me know if you need more details.

$\endgroup$
7
  • 2
    $\begingroup$ Hint: the linear regression passes through the two subsets of data. $\endgroup$
    – whuber
    Aug 4, 2016 at 22:17
  • 3
    $\begingroup$ After writing that previous comment I have been thinking through what the claim means and I confess I'm stuck. Could you elaborate on exactly how linear regression will "give" a classification error? What is needed here is a way to go from the linear model--whose predictions of $Y$ will almost never be exactly 0 or 1--to a classification. How is that supposed to work? $\endgroup$
    – whuber
    Aug 5, 2016 at 14:16
  • $\begingroup$ @whuber If the value of the regression function is greater than a fixed value (threshold), it can be classified as 1 otherwise it is 0. In my case, the value of regression function is always greater than a certain threshold when X >=C and so we classify Y as 1. When X < C, we classify Y as 0. Did this explanation help? $\endgroup$
    – kusur
    Aug 5, 2016 at 15:23
  • $\begingroup$ @whuber What did you mean by your hint? $\endgroup$
    – kusur
    Aug 5, 2016 at 15:26
  • 1
    $\begingroup$ In logistic regression, we might think of "perfect separation" as the existence of arbitrarily good fits whose graphs divide the $(x, \text{logit(y)})$ plane into two halves, one of which contains just the $y=1$ points and the other of which contains just the $y=0$ points. The hint points out that linear regression won't ever do that. However, since you're not using the actual linear regression solution $y=b_0+b_1x$ for classification, and instead are using the indicator of $b_0+b_1x\ge C$, that analogy doesn't seem as helpful as I originally thought. $\endgroup$
    – whuber
    Aug 5, 2016 at 15:49

7 Answers 7

4
$\begingroup$

I agree with the OP: a binary classifier obtained by thresholding a linear regression can work perfectly. A simple (but realistic) example will show why.

Suppose that I have collected data about the weights of balls used in various sports. I plan to use these data to predict the kind of ball from its weight. Specifically, I want to predict whether a ball is a ping-pong ball or a football: I am uninterested in any other predictions.

Ping-pong balls officially weigh 2.7 grams and therefore need to be measured with special scales. The scales used in this study cannot record weights greater than 10 g.

Footballs (soccer balls) officially may weigh between 410 and 450 g. These were measured with a balance and comparison weights ranging from 300 g and up (to accommodate worn and dirty footballs, which may have weights outside the official range).

Pause a moment to note that these measurements may be imperfect and noisy. They could even be biased.

Coding footballs as "1" and ping-pong balls as "0", I plan to regress the type of ball ($y$) against its weight $(x)$. From the foregoing information it is clear that the intercept must be negative but very close to $0$ and the slope will be very close to $(1-0)/(430 - 2.7)$.

This is what the data might look like (showing weights of ten ping-pong balls and ten footballs):

Figure

The black line is a least-squares fit. The horizontal gray line in the middle is at a height of $c=1/2$.

Indeed, let's just do the linear regression right now--without any data!--and fit the model

$$\hat y = \frac{1}{430}x.$$

This fit won't be perfect due to measurement errors in the weights: there will be nonzero residuals. That won't be a problem.

By the way, this is a one-parameter model, the very simplest possible. It would be stretch to claim it is "overfit."

As a classification threshold I will choose the (natural) value $c = 1/2$. Working backwards from this estimate by solving the equation

$$\frac{1}{430} x \gt c = 1/2$$

to find weights that predict footballs, we easily find that this classifier predicts a ball is a football when its reported weight exceeds $215$ g and otherwise predicts the ball is a ping-pong ball.

Because no ping-pong ball can ever have a measured weight above $10$ g and no football can ever have a measured weight less than $300$ g, this obviously is a perfect classifier (not just for the training dataset--which is empty, anyway).


One moral of this little thought experiment is to remind us never to let statistics stand in the way of the obvious.

$\endgroup$
5
  • $\begingroup$ "Because no ping-pong ball can ever have a measured weight above 101g and no football can ever have a measured weight less than 300 g, this obviously is a perfect classifier (not just for the training dataset--which is empty, anyway)." And this is where your answer differs from the OP. Of course you can get a perfect classifier if you exclude cases near the boundary. What the Coursera course is saying is that you can't have a perfect classifier that remains valid for all values of x. $\endgroup$ Feb 1, 2018 at 20:30
  • 1
    $\begingroup$ @Accumulation I haven't excluded any cases. One of the points of this example is that it is realistically possible for cases not to exist near the boundary, period. Sometimes a property (or linear combination of properties) of objects perfectly discriminates them. $\endgroup$
    – whuber
    Feb 1, 2018 at 20:31
  • $\begingroup$ Obviously, given almost any classifier, it is possible for there to be test data for which the classifier has perfect classifier (and for any classifier for which this is not possible, inverting the classifier would result in a perfect classifier). Clearly the question is asking whether it is possible to have a classifier that is perfect across any theoretical test set, not whether it's possible given some practical constraint. $\endgroup$ Feb 1, 2018 at 20:48
  • $\begingroup$ @Accumulation I agree. The point is that "any theoretical test set" is not determined mathematically: it's determined by reality. Although perhaps it might be of mathematical interest to contemplate the effects of data or objects that cannot exist, that is of no statistical or practical interest. $\endgroup$
    – whuber
    Feb 1, 2018 at 21:08
  • $\begingroup$ Your question does not reflect your title. Are you asking about whether linear regression perfectly fits this case or not? (And if so, how do you mean for the linear regression to yield a binary classification?) $\endgroup$
    – Ben
    Apr 11, 2021 at 13:06
0
$\begingroup$

because linear regression fits a line into your data and your threshold predictor is not a line model but a step function. That is the reason that you are adding an activation function to your line model for a binary classification.

$\endgroup$
3
  • 2
    $\begingroup$ This is being automatically flagged as low quality, probably because it is so short. At present it is more of a comment than an answer by our standards. Can you expand on it? We can also turn it into a comment. $\endgroup$ May 20, 2017 at 18:25
  • $\begingroup$ I don't understand the downvotes though? The answer is short but basically correct? If the data generating process is a step function, you can't perfectly fit a line to the data unless $X$ only takes two values. $\endgroup$ May 21, 2017 at 16:53
  • $\begingroup$ I could argue about the grammar of this answer, but it is correct. The classifier is a step function, which can never be written in the form $y = ax +b$ . $\endgroup$
    – meh
    Aug 3, 2017 at 19:09
0
$\begingroup$

I think I saw the same question. If that's so, the statement was that if we use the threshold classification (the definition is as mentioned by you), linear regression will obtain zero classification error. willin that statement is the same as saying will always, which is obviously not true since it's only the case for certain set of training data.

As explained by the teacher in the first example(cancer example), first he showed that we can get zero classification error but then he said "if the data is spreaded across the x-axis then it will not work". Which he showed by simple mathematics showing that linear regression is not a good choice for classification problems, as they will not always give zero classification error.

$\endgroup$
2
  • 1
    $\begingroup$ Can you expand on this as at the moment, at least to me, it is not clear. $\endgroup$
    – mdewey
    Jun 15, 2017 at 17:13
  • $\begingroup$ @mdewey To quote the statement: If there is a feature x that perfectly predicts y, i.e. if y=1 when x>=c and y=0 whenever x<c (for some constant c), then linear regression will obtain zero classification error. As a metaphor, I can say If I drive, the cat will die, but that's not the case, the cat only dies if I drive onto it. Same here, linear regression will obtain zero classification error only if certain training data is provided. $\endgroup$
    – msrc
    Jun 16, 2017 at 8:39
0
$\begingroup$

It is working on the training set you are currently working on. Yes, you get zero classification error. But what if you have a new training set? You would have to tweak that constant 'c' every time you get a new training set. And what will happen when you apply the model to a test set i.e. new data? It won't work!

$\endgroup$
0
$\begingroup$

I think the question hangs on the previous example provided in the video lecture. Basically, it is trying to show that the existence of a perfect predictor does not lead to zero classification error. Linear regression

In the above figure, we can see that tumor size is the perfect predictor of the outcome. Let's forget about linear regression for a moment, and let's just think about the data. The tumor size is the perfect predictor here because regardless of the two hypotheses shown below with pink and black lines, when the tumor size is less than the value indicated by the green line, it is benign, otherwise, it is malignant. But, it does not mean that the regression will give zero classification error. For instance, when the data in the rightmost top gets added, the regression fails to properly classify some of the data that corresponds to the malignant cases. Thus, the perfect predictor feature does not lead to zero classification error. (Apologies for the sloppy drawing)

Yes, this may be the case for the entire population of the data, not only the training set. And, still, linear regression may fail to correctly classify some of the data.

One thing to remember is that when we say that the feature perfectly predicts the outcome, the classification has not happened yet.

$\endgroup$
0
$\begingroup$

Let us say that the predictor X perfectly predicts the label Y such that Y = 1 if X >= c and Y = 0 if X < c. Then why can't linear regression give zero classification error?

The classifier that gives zero classification error is the boundary placed at $X=c$. But, that zero error boundary is not obtained by linear regression.

The problem is that even though you might have a perfect seperation of the data, you will still need to decide on the exact place of the decision boundary between the classes. Linear regression will produce a fit and this fit is not precise.

For instance if the fit is a logistic regression or least discriminant analysis and we choose the point where the prediction is $p=0.5$ then this point might be slightly above or below $c$ and will actually almost never be exactly equal to $c$.

However, if the variable $X$ is discrete then it is possible to obtain the classifier $X=c$.

$\endgroup$
-1
$\begingroup$

I think the answer of the question means that the linear regression can't give zero claassification error on the test or the validation set, not the training set. The original purpose of this question is to see if you understand the concept of overfitting, I guess.

$\endgroup$
1
  • 1
    $\begingroup$ In that case, the classification error can be non zero. But like I said, this wasn't mentioned in the question, so I cannot assume it. $\endgroup$
    – kusur
    Aug 4, 2016 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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