Machine Learning & Signals Learning

2 Uni-Variate Linear Least-Squares

The goal of this chapter is to define and discuss uni-variate linear least-squares (LLS or LS) for a linear model.

Note that LS is also termed linear regression. Uni-variate LS is also referred to as a linear trend-line.

2.1 Uni-variate Linear LS

2.1.1 Definition

A random experiment produces a dataset of \(M\) paired observations \(\left \{x_k,y_k\right \}_{k=1}^M\).

The assumed model underlying the dataset is

\begin{equation} y = f(x) + \epsilon , \end{equation}

where \(f(x)\) is a deterministic function and \(\epsilon \) is zero-mean noise.

The corresponding linear model is

\begin{equation} \hat {y}_k = f(x_k;w_0,w_1)=w_0+w_1 x_k, \end{equation}

where \(w_0\) and \(w_1\) are the model parameters. The corresponding model error is

\begin{equation} e_k = y_k - \hat {y}_k = y_k-w_0-w_1x_k. \end{equation}

The optimal model parameters are found by minimizing a loss function, \(\loss (\cdot )\). Common examples of loss functions include the sum of squared errors (SSE), mean-square error (MSE), and root-mean-square error (RMSE):

\begin{align} \SSE &= \sum _{k=1}^{M} e_k^2,\label {eq-sse-loss-sum}\\ \MSE &= \frac {1}{M}\sum _{k=1}^{M} e_k^2 = \frac {1}{M}\SSE ,\\ \RMSE & = \sqrt {\MSE }. \end{align} For interpretation, \(\MSE \) is an estimator of the error variance. Because constant multiplication factors and monotonic transforms do not affect the location of the minimum, all these loss functions share the same optimal parameters:

\begin{equation} \label {eq-optimization-definition} \begin{aligned} w_0,w_1 &= \arg \min \limits _{w_0,w_1} \SSE (w_0,w_1) \\ &= \arg \min \limits _{w_0,w_1}\MSE (w_0,w_1) \\ &= \arg \min \limits _{w_0,w_1} \RMSE (w_0,w_1). \end {aligned} \end{equation}

For simplicity, \(\SSE \) is used in the following discussion.

The minimization of the loss function (Fig. 2.1),

\begin{equation} \loss (w_0,w_1)=\sum _{k=1}^{M}\bigl (y_k-w_0-w_1x_k\bigr )^2, \end{equation}

is performed by setting the partial derivatives of \(\loss \) to zero:

\begin{equation} \begin{cases} \dfrac {\partial }{\partial w_0} \loss (w_0,w_1) = 0\\[10pt] \dfrac {\partial }{\partial w_1} \loss (w_0,w_1) = 0 \end {cases} \end{equation}

which yields:

\begin{equation} \begin{cases} \displaystyle 2\sum _{k=1}^M \left (y_k - w_0 - w_1x_k\right )\cdot (-1) = 0\\[10pt] \displaystyle 2\sum _{k=1}^M \left (y_k - w_0 - w_1x_k\right )\cdot (-x_k) = 0. \end {cases} \end{equation}

Finally, with some basic algebra:

\begin{equation} \label {eq-ls-normal-eq} \begin{cases} w_0 M + w_1\displaystyle \sum _{k=1}^{M}x_k = \displaystyle \sum _{k=1}^{M}y_k, \\[6pt] w_0 \displaystyle \sum _{k=1}^{M}x_k + w_1 \displaystyle \sum _{k=1}^{M}x_k^{2} = \displaystyle \sum _{k=1}^{M}x_k y_k. \end {cases} \end{equation}

This system of equations is termed the normal equations.

2.1.2 Mean and Variance

The goal of this section is to provide an interpretation of the mean and variance within the context of LS.

A special case of the linear model is one of the form:

\begin{equation} \hat {y} = w_0 \end{equation}

The corresponding MSE loss function is

\begin{equation} \label {eq-ls-one-coeff} \loss (w_0) = \frac {1}{M}\sum _{k=1}^M (y_k-w_0)^2, \end{equation}

with the minimum at the mean of \(y_k\) values,

\begin{equation} \label {eq-ls-one-coeff-mse} w_0 = \frac {1}{M}\sum _{k=1}^M y_k = \bar {y} \end{equation}

The corresponding MSE of the model (substituting (2.14) into (2.13)) is

\begin{equation} \MSE = \frac {1}{M} \sum _{k=1}^M\left (y_k - \frac {1}{M}\sum _{k=1}^M y_k\right )^2 =\sigma _y^2 \end{equation}

which is the sample variance of the \(y_k\) values ¹.

To summarize, \(\hat {y} = \bar {y}\) with \(\MSE =\sigma _y^2\).

2.2 Normal Equations with Statistical Terms

2.2.1 Sample Covariance

The (biased) sample covariance between \(x_1,\dots ,x_M\) and \(y_1,\dots ,y_M\) is given by

\begin{equation} s_{xy} = \frac {1}{M}\sum _{i=1}^M (x_i - \bar x)\,(y_i - \bar y) \end{equation}

The sign and magnitude of the sample covariance \(s_{xy}\) indicate the direction and strength of the linear relationship between \(x\) and \(y\):

• • \(s_{xy}>0\): As \(x\) increases, \(y\) tends to increase (most products \((x_i - \bar x)(y_i - \bar y)\) are positive).

• • \(s_{xy}<0\): As \(x\) increases, \(y\) tends to decrease.

• • \(s_{xy}\approx 0\): No linear association.

2.2.2 Normal Equations

It is numerically convenient to rewrite the normal equations (2.11) in terms of sample moments

\begin{equation} \label {eq-lr-univariate-coeff-stat} \begin{aligned} w_1&=\frac {s_{xy}}{s_x^2}=\frac {\sum _k(x_k-\bar x)(y_k-\bar y)}{\sum _k (x_k-\bar x)^2},\\ w_0&=\bar y-w_1\bar x = \bar y-\frac {s_{xy}}{s_x^2}\bar x, \end {aligned} \end{equation}

and the predictive form

\begin{equation} \hat {y}= \bar y + w_1\bigl (x-\bar x\bigr ). \end{equation}

Note that these expressions are independent of whether biased or unbiased definitions are used for \(s_{xy}\) and \(s_x\), since the corresponding normalization factors cancel out.

Remarks.

• • A valid solution requires \(s_x\neq 0\), i.e. variability in \(x_i\).

• • If both variables are centered (\(\bar x=\bar y=0\)), then (2.17) reduces to

  \(\seteqnumber{0}{}{18}\)

  \begin{equation} \label {eq-lr-univariate-coeff-stat-normalized} \begin{aligned} w_0&=0,\\ w_1 &= \frac {\sum _k x_k y_k}{\sum _k x_k^2} \end {aligned} \end{equation}

2.3 Correlation Coefficient

Definition The sample Pearson correlation coefficient between \(\bx \) and \(\by \) is the normalized (dimensionless) covariance:

\begin{align} r_{xy} &=\frac {s_{xy}}{s_x\,s_y}\\ &= \frac {\displaystyle \sum _{i=1}^M (x_i - \bar x)\,(y_i - \bar y)} {\displaystyle \sqrt {\sum _{i=1}^M (x_i - \bar x)^2} \;\sqrt {\sum _{i=1}^M (y_i - \bar y)^2}} \end{align} and the slope in (2.17) can be re-written as

\begin{equation} w_1 = r_{xy}\,\frac {s_y}{s_x}. \end{equation}

Note that there is no difference between biased and unbiased definitions for \(r_{xy}\), since the corresponding coefficients cancel out.

2.3.1 Normalized (z-score) Linear Regression

The goal of this section is to provide an intuitive interpretation of the correlation coefficient.

Rescaling To make the slope directly interpretable, we rescale both variables to zero mean and unit variance:

\begin{equation} z_i = \frac {x_i-\bar x}{s_x}, \qquad t_i = \frac {y_i-\bar y}{s_y}, \qquad i=1,\ldots ,M \end{equation}

The properties of \(z_i\) and \(t_i\) are

\begin{align*} \bar z &= \frac {1}{M}\sum z_i=0,\\ \bar t &=\frac {1}{M}\sum t_i=0,\\ s_z &= s_t = 1. \end{align*}

Normal Equations The linear model in normalized space,

\begin{equation} \hat {t}_i = w_0^* + w_1^*z_i \end{equation}

yields (applying (2.19))

\begin{align} w_0^* &=0,\label {eq-w_0-normalized}\\ w_1^* &= \frac {s_{zt}}{s_z^2} =\frac {\frac {1}{M}\sum _{i=1}^{M} z_i t_i} {\frac {1}{M}\sum _{i=1}^{M} z_i^2} =\frac {1}{M}\sum _{i=1}^{M} z_i t_i =\frac {1}{s_x s_y}\frac {1}{M}\sum _{i=1}^M (x_i-\bar x)(y_i-\bar y) =r_{xy} \label {eq-w_1-normalized} \end{align} Thus, the normalized prediction is

\begin{equation} \hat t_i = r_{xy}\,z_i. \end{equation}

where

\begin{equation} r_{xy}=\frac {s_{xy}}{s_x\,s_y} \end{equation}

is the correlation coefficient. Returning to the original scale gives

\begin{equation*} \frac {\hat y-\bar y}{s_y}=r_{xy}\frac {x-\bar x}{s_x} \end{equation*}

or the familiar form:

\[ \hat y = \bar y + r_{xy}\,\frac {s_y}{s_x}\bigl (x-\bar x\bigr ). \]

Interpretation of \(r_{xy}\)

• • Units of x- and y-axes are standard deviation from the origin since \(t_i\) and \(z_i\) are centered and standardized.

• • In the normalized space, \(r_{xy}\) is the regression slope. A one-standard-deviation increase in \(x\) (\(z\) changes by 1) changes \(y\) by \(r_{xy}\) standard deviations on average (\(\hat {t}\) changes by \(r_{xy}\)).

• • Let’s define two vectors, \(\bz \) and \(\bt \), both in \(\mathbb R^{M}\). The corresponding dot product is

  \(\seteqnumber{0}{}{31}\)

  \begin{equation} \bz \cdot \bt = \norm {\bz }\norm {\bt }\cos (\theta ) \end{equation}

  Using (2.29),

  \(\seteqnumber{0}{}{32}\)

  \begin{equation} \bz \cdot \bt = \sum _{i=1}^M z_it_i = M r_{xy}. \end{equation}

  Since \(\norm {\bz } = \sqrt {\sum z_i^2} = \sqrt {M s_z^2} = \sqrt {M}\), we have

  \(\seteqnumber{0}{}{33}\)

  \begin{equation} \norm {\bz }\norm {\bt } = \sqrt {M}\cdot \sqrt {M} = M \end{equation}

  Finally, \(r_{xy}=\cos \theta \), where \(\theta \) is the angle between the centered and standardized data vectors \(\bz \) and \(\bt \) (Fig. 2.2).

  Consequences:

  • – Range: \(-1 \le r_{xy} \le +1\).

  • – Special case of perfect linear fit (zero error)

    \(\seteqnumber{0}{}{34}\)

    \begin{align*} r_{xy} = \pm 1 &\;\Longrightarrow \; \theta = 0^\circ \text { or }180^\circ \\ r_{xy} = 0 &\;\Longrightarrow \; \theta = 90^\circ \end{align*}

  • – \(r_{xy}=+1\) indicates perfect positive linear association.

  • – \(r_{xy}=-1\) indicates perfect negative linear association.

  • – \(r_{xy}=0\) indicates no linear association.

Regression error as a function of \(r_{xy}\)

With the optimal normalized model \(\hat t = r_{xy} z\) the residuals are

\begin{equation} e_i = t_i - \hat {t}_i = t_i - r_{xy} z_i \end{equation}

with

\begin{equation} \text {MSE} = 1 - r_{xy}^{2} = s_e^2. \end{equation}

Consequences:

• • \(r_{xy}=0\) \(\Rightarrow \) the best linear predictor is \(\hat y=\bar y\) and the MSE equals the sample variance of \(y\). There is no linear association and the MSE is maximal.

• • \(|r_{xy}|=1\) \(\Rightarrow \) perfect fit, zero residual error. It means that the data points lie perfectly on a straight line.

• • Typically, the residual errors are (approximately) Gaussian distributed.

Note, the unbiased estimator of \(s_e^{2}\) requires \(1/(M-2)\) factor instead \(1/M\).

2.3.2 Coefficient of Determination Metric

To emphasize the difference between loss and metrics, the following example of an LR metric is provided. The coefficient of determination, denoted \(R^2\) or \(r^2\) (R-squared), is based on the relation:

\begin{equation} \underbrace {\sum _{k=1}^{M}(y_k-\bar {y})^2}_{\text {SST}} = \underbrace {\sum _{k=1}^{M}(\hat {y}_k-\bar {y})^2}_{\text {SSR}} + \underbrace {\sum _{k=1}^{M}e_k^2}_{\text {SSE}}, \end{equation}

where:

• • SST: Total sum of squares.

• • SSR: Sum of squares due to regression.

• • SSE: Sum of squared errors (or residual sum of squares).

The \(R^2\) metric is defined as:

\begin{equation} R^2 =\frac {\text {SSR}}{\text {SST}} =1 - \frac {\text {SSE}}{\text {SST}}, \end{equation}

providing a unitless goodness-of-fit measure that shares an intuitive \(\,[0,1]\) range:

• • \(R^2=1\): Perfect fit.

• • \(R^2=0\): The model is no better than predicting the mean, \(\hat {y}_i = \bar y\).

• • \(R^2<0\): The model performs worse than the mean (possible for machine learning models on test data).

Uni-variate case For the uni-variate LR case, it is the fraction of the sample variance of \(y\) explained by the linear fit,

\begin{equation} R^{2}=r_{xy}^{2}. \end{equation}

The general (biased) MSE of unnormalized values is

\begin{equation} \begin{aligned} \MSE &= \frac {1}{M} \sum _{k=1}^{M} \bigl (y_k-\hat y_k\bigr )^{2}\\ &=s_y^{2}\bigl (1-r_{xy}^{2}\bigr ) \\ &=\frac {1}{M}\SSE = \frac {1}{M}\left (\text {SST}-\text {SSR}\right ). \end {aligned} \end{equation}