# Why does the least square solution give poor results in this case?

There is an image in page 204, chapter 4 of "pattern recognition and machine learning" by Bishop where I don't understand why the Least square solution gives poor results here:

The previous paragraph was about the fact that least-squares solutions lack robustness to outliers as you see in the following image, but I don't get what's going on in the other image and why LS gives poor results there as well.

-
It looks like this is part of a chapter on discrimination between sets. In your first pair of graphs, the one on the left clearly doesn't distinguish well between the three sets of points. Does that answer your question? If not, can you clarify it? –  Peter Flom Nov 18 '12 at 12:25
@PeterFlom: The LS solution gives poor results for the first one, I want to know the reason. And yes, it's the last paragraph of the section about LS classification where the whole chapter is about Linear discriminant functions. –  Gigili Nov 18 '12 at 12:27

The particular phenomenon that you see with the least squares solution in Bishops Figure 4.5 is a phenomenon that only occurs when the number of classes is $\geq 3$.

In ESL, Figure 4.2 on page 105, the phenomenon is called masking. See also ESL Figure 4.3. The least squares solution results in a predictor for the middel class that is mostly dominated by the predictors for the two other classes. LDA or logistic regression don't suffer from this problem. One can say that it is the rigid structure of the linear model of class probabilities (which is essentially what you get from the least squares fit) that causes the masking.

With only two classes the phenomenon does not occur $-$ see also Exercise 4.2 in ESL, page 135, for details on the relation between the LDA solution and the least squares solution in the two class case.

Edit: Masking is perhaps most easily visualised for a two-dimensional problem, but it is also a problem in the one-dimensional case, and here the mathematics is particularly simple to understand. Suppose that the one-dimensional input variables are ordered as

$$x_1 < \ldots < x_k < y_1 < \ldots y_m < z_1 < \ldots < z_n$$

with the $x$'s from class 1, the $y$'s from class two and the $z$'s from class 3. Together with the coding scheme for the classes as three-dimensional binary vectors we have the data organized as follows

$$\begin{array}{c|cccccccc} & 1 & \ldots & 1 & 0 & \ldots & 0 & 0 & \ldots & 0 \\ \mathbf{T}^T & 0 & \ldots & 0 & 1 & \ldots & 1 & 0 & \ldots & 0 \\ & 0 & \ldots & 0 & 0 & \ldots & 0 & 1 & \ldots & 1 \\ \hline \mathbf{x}^T & x_1 & \ldots & x_k & y_1 & \ldots & y_m & z_1 & \ldots & z_n \\ \end{array}$$

The least squares solution is given as three regressions of each of the columns in $\mathbf{T}$ on $\mathbf{x}$. For the first column, the $x$-class, the slope will be negative (all the ones are to the left above) and for the last column, the $z$-class, the slope will be positive. For the middle column, the $y$-class, the linear regression will have to balance the zeroes for the two outer classes with the ones in the middle class resulting in a rather flat regression line and a particularly poor fit of the conditional class probabilities for this class. As it turns out, the max of the regression lines for the two outer classes dominates the regression line for the middle class for most values of the input variable, and the middle class is masked by the outer classes.

In fact, if $k = m = n{}$ then one class will always be masked completely, whether or not the input variables are ordered as above. If the class sizes are all equal the three regression lines all pass through the point $(\bar{x}, 1/3)$ where $$\bar{x} = \frac{1}{3k}\left(x_1 + \ldots + x_k + y_1 + \ldots + y_m + z_1 + \ldots + z_n\right).$$ Hence, the three lines all intersect in the same point and the max of two of them dominates the third.

-

Based on the link provided below, the reasons why LS discriminant is not performing good in the upper left graph are as follow:
-Lack of robustness to outliers.
- Certain datasets unsuitable for least squares classification.
- Decision boundary corresponds to ML solution under Gaussian conditional distribution. But binary target values have a distribution far from Gaussian.

Look at page 13 in Disadvantages of Least Squares.

-

I believe the issue in your first graph is called "masking", and it's mentioned in "The Elements of statistical learning: Data mining, inference, and prediction" (Hastie, Tibshirani, Friedman. Springer 2001), pages 83-84.

Intuitively (which is the best I can do) I believe this is because predictions of an OLS regression are not constrained to [0,1], so you can end up with a prediction of -0.33 when you really want more like 0..1, which you can finesse in the case of two classes but the more classes you have the more likely this mismatch is to cause a problem. I think.

-

Least square is sensitive to scale ( because the new data is of different scale, it will skew the decision boundary) , one usually needs either apply weights (means data to enter to the optimization algorithm is of the same scale) or perform a suitable transformation (mean center, log(1+data) ...etc) on data in such cases. It seems Least Square would work perfect if you ask it to do a 3 classification operation in which case and merge two output classes eventually.

-