variable selection and bias-variance tradeoff for linear regression

Question

I can understand bias-variance tradeoff for the $k$-nearest neighbor method. (Please correct me if I'm wrong.) Small values of $k$ lead to a flexible model with the $E[Y|X]$ estimate, having small bias and large variance. With large value of $k$, we have to average many neighbors, so the $E[Y|X]$ estimate tends to have larger bias and smaller variance. So to choose $k$, we tradeoff between bias and variance.

However, I don't quite see how this tradeoff manifest itself in the variable selection of linear regression. Are there known rules about when or if using a subset of the input variables will reduce the test error for linear regression? Does using fewer variables lead to lower variance and higher bias in this case? And how to justify/prove them? Thanks a lot!

Answer 1

Is $k$-nearest neighbors biased? Just like OLS, KNN takes a weighted linear combination of the outcomes and produce a prediction as a function of $X$. The original notion that using a small $k$ increases variability at the tradeoff of greater generality is of note. So whatever possible "bias" exists depends on the probability model you have used for the data, and you can dream up crazy scenarios when KNN falls apart, and when OLS falls apart.

Variable selection is too broad a subject to meaningfully answer your question. To put it in perspective: using too few variables increases bias and variance. Using too many variables also increases bias and variance. The "best" model is the one where $N$ is so large, you can include every single variable in a model and estimate their values with perfect precision. The idea of trimming nonpredictive variables is one of approximation. In practice, we pick the best-fitting model from a panel of candidates according to external validation, split sample validation, or cross validation. These minimize the MSE... but whether that arises from having less bias or less variance depends again on the probability model at hand. You can play God with your simulation and make it all one, all the other, both, or none.

Answer 2

I haven't found a complete/very satisfactory answer yet, but I'll share what I have discovered, and give a partial answer here, hoping that it might stimulate a better answer.

For linear regression, including more input variables in the model do not necessarily increase the variance of the test error. It could well reduce the variance of the test error.

To see this, consider the following example: Let $X_1, X_2, X_3, Z$ be independent zero-mean normal random variables with variances being $1,1,1$ and $0.1$ respectively. Suppose $\mathbf X=[X_1\:X_2\:X_3]$ are our input variables, and the output variable is given by $Y=f(\mathbf X)+Z$, where $f(\mathbf X)=X_1+X_2$. Now, consider the following 3 linear estimates (models):

$$\hat f_1(\mathbf X_A)=[X_1]\mathbf a_1,$$ $$\hat f_2(\mathbf X_B)=[X_1\: X_2]\mathbf a_2,$$ $$\hat f_3(\mathbf X_C)=[X_1\:X_2\:X_3]\mathbf a_3,$$

and their respective MSE, i.e. $MSE_i=E\left[\left(Y-\hat f_i(\mathbf X_{l(i)})\right)^2\right], i=1,2,3,$ and $l(i)=A,B,C.$ With the LMMSE estimate, it's well-known that the bias ($E\left[Y-\hat f_i(\mathbf X_{l(i)})\right]$) is zero, so the MSE equals the variance of the estimation error, i.e. $$MSE_i=Var\left(Y-\hat f_i(\mathbf X_{l(i)})\right)=\sigma_Y^2-K_{Y\mathbf X_{l(i)}}^TK_{\mathbf X_{l(i)}}^{-1}K_{Y\mathbf X_{l(i)}}.$$

For this simple example, it's easy to verify that $\sigma_Y^2=2.1,$ and $K_{Y\mathbf X_A}^T=[1], K_{Y\mathbf X_B}^T=[1\:1],$ $K_{Y\mathbf X_C}^T=[1\:1\:0]$, and $K_{\mathbf X_A}=1, K_{\mathbf X_B}=I_2, K_{\mathbf X_C}=I_3.$ As a result,

$$MSE_1 = 1.1$$ $$MSE_2 = 0.1$$ $$MSE_3 = 0.1$$

So we see from this example that the MSE and variance of the estimation error decrease as we increase the number of variables in our linear model from 1 to 2.

The linear regression is essentially an approximation (estimate) of the LMMSE estimate. With large training set, the linear regression computes an $\hat f$ which is fairly close to that of the LMMSE estimate, but is of course random (due to the training set). As a result, an analytical expression of the test error of the linear regression $E\left[\left(Y_{test}-\hat f(\mathbf X_{test})\right)^2\right]$ appears hard to me even for the above simple example. Nonetheless, we may estimate the test error with the sample mean method. With the training set size being 100, and with 100,000 trials of the test error, here's what I found:

$\begin{array}{|l|c|c|c|} \hline i & \textrm{bias} & \textrm{variance} & MSE_i \\ \hline 1 & 0.0002480855 & 1.106343 & 1.106343 \\ \hline 2 & 0.00006668096 & 0.1013964 & 0.1013965 \\ \hline 3 & -0.0005098247 & 0.1027781 & 0.1027783 \\ \hline \end{array}$

Note that this empirical result is very close to the analytical LMMSE computation above.