Machine Learning & Signals Learning
4 Linear Prediction
4.1 Prediction by a Constant
Prediction by a constant: A predictor of the form
\(\seteqnumber{0}{4.}{0}\)\begin{equation} \hat {Y}=b, \end{equation}
where \(b\) is a fixed number, used for every realization of the experiment.
Mean squared error: The quality of a predictor is measured by the mean squared error,
\(\seteqnumber{0}{4.}{1}\)\begin{equation} \label {eq:rand2:mse_def} \MSE (b) = \E [{\bigl (Y-\hat {Y}\bigr )^2}] \end{equation}
and the best predictor is the one that minimizes it,
\(\seteqnumber{0}{4.}{2}\)\begin{equation} b_{opt}=\argmin _{b} \MSE (b) \end{equation}
For a constant predictor the squared error expands into three moments,
\(\seteqnumber{0}{4.}{3}\)\begin{equation} \begin{aligned} \MSE (b) &= \E [{(Y-b)^2}] \\ &= \E [{Y^2-2bY+b^2}] \\ &= \E [Y^2]-2b\,\E [Y]+b^2 \end {aligned} \end{equation}
Only the last two terms depend on \(b\). Setting the derivative to zero,
\(\seteqnumber{0}{4.}{4}\)\begin{equation} \frac {\partial \MSE (b)}{\partial b} = -2\,\E [Y]+2b=0, \end{equation}
gives the optimal constant,
\(\seteqnumber{0}{4.}{5}\)\begin{equation} \label {eq:rand2:b_const} b_{opt} = \E [Y] \end{equation}
Substituting it back into Eq. (4.2) reproduces the definition of the variance,
\(\seteqnumber{0}{4.}{6}\)\begin{equation} \label {eq:rand2:mse_constant} \MSE _{min} = \E [{\bigl (Y-\E [Y]\bigr )^2}] = \Var [Y] \end{equation}
Why “expectation”
This is the answer to the question left open in Sec. 1.2.3. When a random variable must be summarized by one number, the expectation is the number to use: it is the value one should expect in the least-squares sense. The price paid for replacing the variable by that single number is the variance. The two central quantities of the previous chapters are therefore a matched pair, the best constant predictor and its error.
4.2 Two-Dimensional Linear Prediction
Linear prediction: A predictor of the form
\(\seteqnumber{0}{4.}{7}\)\begin{equation} \hat {Y}= ax + b, \end{equation}
where \(x\) is the observed realization of \(X\) for which the prediction is made.1
The two coefficients are again chosen to minimize the mean squared error,
\(\seteqnumber{0}{4.}{8}\)\begin{equation} a_{opt},b_{opt} = \argmin _{a,b} \MSE (a,b) \end{equation}
Differentiating with respect to each coefficient in turn and setting both derivatives to zero,
\(\seteqnumber{0}{4.}{9}\)\begin{align} \frac {\partial \MSE (a,b)}{\partial a} &=\E [{2(Y-aX-b)(-X)}]\nonumber \\ &= -2 \E [XY]+2a\E [X^2]+2b\E [X]=0 \\ \frac {\partial \MSE (a,b)}{\partial b} &=\E [{2(Y-aX-b)(-1)}]\nonumber \\ &= -2\E [Y]+2a\E [X]+2b=0 \end{align} produces a pair of linear equations in \(a\) and \(b\),
\(\seteqnumber{0}{4.}{11}\)\begin{equation} \label {eq:rand2:normal_eq} \begin{bmatrix} \E [X^2] & \E [X] \\\E [X] & 1 \end {bmatrix} \begin{bmatrix} a \\ b \end {bmatrix} = \begin{bmatrix} \E [XY] \\ \E [Y] \end {bmatrix} \end{equation}
whose solution is written most compactly with the covariance and the variance,
\(\seteqnumber{1}{4.13}{0}\)\begin{align} a_{opt} &= \frac {\E [XY]-\E [X]\E [Y]}{\E [X^2]-\bigl (\E [X]\bigr )^2}=\frac {\Cov [X,Y]}{\Var [X]}\label {eq:rand2:a_opt}\\ b_{opt} &= \E [Y]- a_{opt}\E [X]\label {eq:rand2:b_opt} \end{align}
Linear prediction for a pair of random variables: Collecting the two coefficients gives the predictor in its most readable form,
\(\seteqnumber{0}{4.}{13}\)\begin{equation} \label {eq:rand2:predictor} \begin{aligned} \hat {Y} &= a_{opt}x + b_{opt}\\ &= \E [Y] + \frac {\Cov [X,Y]}{\Var [X]}\bigl (x-\E [X]\bigr ) \end {aligned} \end{equation}
Read it as a correction to the constant predictor of Eq. (4.6): start at \(\E [Y]\), then move away from it in proportion to how far the observed \(x\) falls from \(\E [X]\). The proportionality factor is the covariance normalized by the variance of the variable that is being observed.
Prediction error: The error of the optimal linear predictor is the variance of \(Y\), shrunk by a factor that depends only on the correlation coefficient,
\(\seteqnumber{0}{4.}{14}\)\begin{equation} \label {eq:rand2:mse_linear} \MSE _{min} = \E [{\bigl (Y - (a_{opt}X+b_{opt})\bigr )^2}] = \Var [Y]\left (1-\rho _{XY}^2\right ) \end{equation}
Reading the improvement factor
Comparing Eq. (4.15) with Eq. (4.7), observing \(X\) reduces the prediction error by the factor \(1-\rho _{XY}^2\):
-
• \(\rho _{XY}=0\): nothing is gained, and Eq. (4.14) collapses back to the constant \(\E [Y]\).
-
• \(\rho _{XY}=\pm 1\): the error vanishes, because \(Y\) is an exact linear function of \(X\).
-
• In between, \(\rho _{XY}^2\) is the fraction of the variance of \(Y\) that the linear predictor removes.
Since \(\rho _{XY}^2\) enters squared, the sign of the correlation does not matter: a strong negative relation is as useful for prediction as a strong positive one.
Zero mean error: The optimal linear predictor is unbiased: on average it neither over- nor under-shoots,
\(\seteqnumber{0}{4.}{15}\)\begin{equation} \E [{Y - (a_{opt}X+b_{opt})}] = 0 \end{equation}
-
Proof. Take the expectation term by term and substitute \(b_{opt}\) from Eq. (4.13b),
\(\seteqnumber{0}{4.}{16}\)\begin{equation} \begin{aligned} \E [{Y - (a_{opt}X+b_{opt})}] &=\E [Y] - a_{opt}\E [X] - b_{opt}\\ &=\E [Y] - a_{opt}\E [X] - \bigl (\E [Y]- a_{opt}\E [X]\bigr ) = 0 \end {aligned} \end{equation}
Optimality for a jointly Gaussian pair: For a jointly Gaussian pair (Sec. 3.4), Eq. (4.14) is not merely the best linear predictor: it is the best predictor of any form. No non-linear function of \(X\) achieves a lower mean squared error.
Population quantities, not data
Everything in this chapter is written with the operators \(\E [\cdot ]\), \(\Var [\cdot ]\) and \(\Cov [\cdot ]\), which describe the distribution itself and are not available in practice. Given a data set, each of them is replaced by its sample counterpart, the mean by the sample mean and the covariance by the sample covariance. The predictor of Eq. (4.14) then becomes the univariate least-squares line, and the improvement factor \(1-\rho _{XY}^2\) becomes the sample quantity \(1-r_{xy}^2\). That step, and what can go wrong in it, is the subject of the least-squares chapters later in the book.
-
Example 4.1: Two independent random variables \(W_1, W_2 \sim \mathrm {U}[0,1]\) are given, and
\(\seteqnumber{0}{4.}{17}\)\begin{align*} X &= W_1,\\ Y &= 0.9W_1 + 0.1W_2 \end{align*} Compute \(\E [X], \E [Y], \Var [X], \Var [Y], \E [XY], \Cov [X,Y], \rho _{XY}\), the linear predictor and its error.
-
Solution: The two variables share the term \(W_1\), which is what makes them correlated. Fig. 4.1 shows the resulting scatter together with the predictor.
\(\seteqnumber{0}{4.}{17}\)\begin{align*} \E [X] &= \E [W_1] = \frac {1}{2}\\ \E [Y] &= 0.9\,\E [W_1] + 0.1\,\E [W_2] = \frac {1}{2}\\ \Var [X] &= \Var [W_1] =\frac {1}{12}\\ \Var [Y] &= 0.9^2\,\Var [W_1] + 0.1^2\,\Var [W_2] \\ &= \frac {82}{100}\cdot \frac {1}{12} = \frac {41}{600}\approx 0.06833 \end{align*} The mixed moment needs the second moment of a uniform variable, \(\E [W_1^2] = \Var [W_1] + \bigl (\E [W_1]\bigr )^2 = \tfrac {1}{12}+\tfrac 14=\tfrac 13\), and the fact that \(W_1\) and \(W_2\) are independent,
\(\seteqnumber{0}{4.}{17}\)\begin{align*} \E [XY] &= 0.9\,\E [W_1^2] + 0.1\,\E [W_1]\E [W_2]\\ &= \frac {9}{10}\cdot \frac {1}{3} + \frac {1}{10}\cdot \frac {1}{2}\cdot \frac {1}{2} = \frac {3}{10} + \frac {1}{40}\\ \Cov [X,Y] &= \E [XY] - \E [X]\E [Y] \\ &= \frac {13}{40} - \frac {1}{4} = \frac {3}{40} = 0.075\\ \rho _{XY} &=\frac {3/40}{\sqrt {\frac {1}{12}\cdot \frac {41}{600}}} = \frac {9}{\sqrt {82}} \approx 0.9939 \end{align*} Substituting into Eqs. (4.14) and (4.15),
\(\seteqnumber{0}{4.}{17}\)\begin{align*} \hat {Y} &=\frac {1}{2} + \frac {3/40}{1/12}\left (x-\frac {1}{2}\right ) = \frac {1}{2} + \frac {9}{10}\left (x-\frac {1}{2}\right )\\ \MSE _{min} &= \Var [Y]\left (1-\rho _{XY}^2\right ) = \frac {41}{600}\left (1-\frac {81}{82}\right ) \\ &= \frac {1}{1200}\approx 8.33\times 10^{-4} \end{align*} The recovered slope is \(0.9\), exactly the weight with which \(W_1\) enters \(Y\), and the residual error is what the \(0.1W_2\) term contributes.
-
4.3 Exercises
4.1 (Prediction without an offset) A linear predictor of \(Y\) from \(X=x\) without an offset is given, \(\hat {Y}=ax\).
-
(a) Compute the value of \(a\) that minimizes the mean squared error.
-
(b) Compute the resulting mean error, \(\E [{Y-\hat {Y}}]\).
-
(c) Compute the resulting mean squared error, \(\E [{(Y-\hat {Y})^2}]\).
4.2 (Non-linear prediction) A predictor of \(Y\) from \(X\) of the quadratic form \(\hat {Y} = ax^2\) is given.
-
(a) Compute the optimal coefficient \(a\) in the minimum mean-squared-error sense, and an expression for the resulting error.
-
(b) For the variables
\[ \begin {aligned} X &= 0.9W_1 + 0.1W_2, \\ Y &= W_1^2, \end {aligned} \]
with \(W_1,W_2\sim \mathrm {U}[0,1]\) independent, compute the numerical value of the prediction error.
Useful expansions:
\(\seteqnumber{0}{4.}{17}\)\begin{align*} (x + y)^2 &= x^2 + 2xy + y^2 \\[4pt] (x+y)^3 & = x^3 + 3x^2y + 3xy^2 + y^3 \\[4pt] (x+y)^4 & = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4 \end{align*}
-
(c) Compute the error of a linear predictor \(\hat {Y} = ax+b\) for the same variables, and explain the comparison.
4.3 (Linear prediction of a discrete pair) A two-dimensional discrete random variable takes the four values \(\begin {bmatrix} X \\ Y \end {bmatrix} =\left \{ \begin {bmatrix} 0 \\ 0 \end {bmatrix}, \begin {bmatrix} 1 \\ 1 \end {bmatrix}, \begin {bmatrix} 2 \\ 2 \end {bmatrix}, \begin {bmatrix} 2 \\ 3 \end {bmatrix} \right \}\) with equal probability. Compute:
-
(a) The marginal distributions.
-
(b) The expectation and the variance of each marginal.
-
(c) The covariance and the correlation coefficient.
-
(d) The linear predictor of \(Y\) from \(X\).
4.4 (Linear prediction of a discrete pair) A table of five equally likely experimental outcomes is given, \(\begin {bmatrix} X \\ Y \end {bmatrix} = \left \{ \begin {bmatrix} -2 \\ 0 \end {bmatrix}, \begin {bmatrix} -1 \\ 0 \end {bmatrix}, \begin {bmatrix} 0 \\ 3 \end {bmatrix}, \begin {bmatrix} 1 \\ 3 \end {bmatrix}, \begin {bmatrix} 2 \\ 4 \end {bmatrix} \right \}\)
-
(a) What is the linear prediction of \(Y\) for \(x = 1\)?
-
(b) What is the correlation coefficient between \(X\) and \(Y\)?
-
(c) What is the minimum mean squared error of the prediction of \(Y\) from an arbitrary \(x\)?
4.5 (Linear prediction from a joint PDF table) A pair of discrete variables \(X,Y\) is given, with the joint PDF of Table 4.1. For example, \(\Pr [X=1,Y=3]=0.2\). Compute:
-
(a) The correlation coefficient \(\rho _{XY}\).
-
(b) The linear prediction of \(Y\) for \(x=3\).
| \(Y\) | ||||
| \(1\) | \(2\) | \(3\) | ||
| \(X\) | \(1\) | \(0\) | \(0\) | \(0.2\) |
| \(2\) | \(0\) | \(0.2\) | \(0.1\) | |
| \(3\) | \(0.1\) | \(0.2\) | \(0\) | |
| \(4\) | \(0.2\) | \(0\) | \(0\) | |
4.6 (Prediction of Bernoulli variables) A pair of independent random variables \(X\sim \mathrm {Ber}(p_1)\), \(Y\sim \mathrm {Ber}(p_2)\) has the joint PDF
\(\seteqnumber{0}{4.}{17}\)\begin{align*} p_{XY}[0,0] &= 0.08 & p_{XY}[0,1] &= 0.32\\ p_{XY}[1,0] &= 0.12 & p_{XY}[1,1] &= 0.48 \end{align*}
-
(a) What are the values of \(p_1\) and \(p_2\)?
In the remaining parts, keep \(p_1\) and \(p_2\) as parameters.
-
(b) Find the constant \(b_x\) that predicts \(X\) with minimum squared error, and the resulting error.
-
(c) For \(Z = aX + cY\), find the constant \(b_z\) that predicts \(Z\) with minimum squared error, and the resulting error.
-
(d) Do constants \(a\ne 0\), \(c\ne 0\) exist for which \(Z\) and \(X\) are uncorrelated? If so, state the condition.
4.7 (Relation between variables) A zero-mean jointly Gaussian pair \((X,Y)\) is given, with
\[ \Var [X] = 4,\qquad \Var [Y] = 1,\qquad \rho _{XY} = \frac {1}{2} \]
-
(a) Compute \(\Cov [X,Y]\).
-
(b) Compute \(\E [{(X+Y)^2}]\) and \(\Var [{X+Y}]\).
-
(c) Find the best linear MMSE estimator of \(X\) from \(Y\) of the form \(\hat X = aY\), and compute the resulting error \(\E [{(X-\hat X)^2}]\).
-
(d) What is \(\Pr (X+Y>1)\)?
4.8 (Prediction among Gaussian variables) Jointly Gaussian random variables \(X_1\sim N(0,1)\), \(X_2\sim N(1,2)\), \(X_3\sim N(0,1)\) are given, in the notation \(N(\mu ,\sigma ^2)\). The correlation coefficient between \(X_1\) and \(X_2\) is \(\rho _{X_1X_2} = \tfrac {1}{\sqrt {2}}\). Define
\(\seteqnumber{0}{4.}{17}\)\begin{align*} Y_1 &= X_2 + X_3 \sim N(1,5)\\ Y_2 &= -X_1 + 2X_3 \sim N(0,3)\\ Y_3 &= X_1 + 2X_2\\ Y_4 &= 3X_1 + 2X_2 \end{align*}
-
(a) What is the optimal MSE predictor of \(X_2\) from \(X_1\)?
-
(b) What is the optimal MSE predictor of \(Y_4\) from \(Y_3\)?
-
(c) For each of the pairs \((X_1,X_3)\) and \((X_2,X_3)\), prove whether they are independent. Hint: use the stated variances of \(Y_1\) and \(Y_2\).
-
(d) What is the joint distribution of \(Y_3\) and \(Y_4\)?
4.9 (Perimeter and area of a rectangle) Two independent continuous random variables \(X, Y\sim \mathrm {U}[0,1]\) represent the sides of a rectangle. Let \(C\) denote its perimeter and \(A\) its area.
-
(a) Give expressions for \(C\) and \(A\).
-
(b) Compute \(\Cov [C,A]\).
-
(c) Give the linear MSE estimator of \(C\) from \(A\).
-
(d) Determine the minimum squared error of this estimator.