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 Definitions

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

ML Model: The assumed model underlying the dataset is

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

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

The goal is to propose and apply the model,

\begin{equation} \hat {y}_k = f(x_k) \end{equation}

that provide the most appropriate results with relation to \(y_k\).

Challenge: there are many possible \(f(\cdot )\) options.

Error: The model error is

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

Loss

Loss function: Loss (or cost) function \(\loss (y_k,\hat {y}_k)\) is some distance metric between \(y_k\) and \(\hat {y}_k\). The optimal model parameters of the applied model are found by minimizing a loss function.

Common examples of loss functions include:

• • the sum of squared errors (SSE),

  \(\seteqnumber{0}{}{3}\)

  \begin{equation} \label {eq-sse-loss-sum} \SSE = \sum _{k=1}^{M} e_k^2, \end{equation}

• • mean-square error (MSE) or (biased) error variance

  \(\seteqnumber{0}{}{4}\)

  \begin{equation} \label {eq-mse-loss-sum} \MSE = \frac {1}{M}\sum _{k=1}^{M} e_k^2 = \frac {1}{M}\SSE = s_e^2 \end{equation}

• • and root-mean-square error (RMSE),

  \(\seteqnumber{0}{}{5}\)

  \begin{equation} \RMSE = \sqrt {\MSE }. \end{equation}

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 \\ &= \arg \min \limits _{w_0,w_1}\MSE \\ &= \arg \min \limits _{w_0,w_1} \RMSE . \end {aligned} \end{equation}

Metric: A quantifiable measure used to evaluate how well a model is performing.

For example, the of RMSE is significantly easier to interpret due to same values range and measurement units as an original dataset, than MSE or SSE.

Summary

• 1. Select model \(f(\cdot )\)

• 2. Find model parameters by the minimization of the loss function, \(\loss \)

• 3. Use metrics to evaluate model performance.

2.1.2 Mean and Variance

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

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

The corresponding MSE loss (2.5) 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 related 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.10) into (2.9)) is

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

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

To summarize, the best predictor is the sample mean, \(\hat {y} = \bar {y}\), with \(\MSE =s_y^2\).

2.1.3 Linear Model

The example of 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 linear model error is

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

The minimization of the SSE loss function ((2.4) and 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.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 _{k=1}^M (x_k - \bar x)\,(y_k - \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 Correlation Coefficient

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

\begin{equation} \begin{aligned} r_{xy} &=\frac {s_{xy}}{s_x\,s_y}\\ &= \frac {\displaystyle \sum _{k=1}^M (x_k - \bar x)\,(y_k - \bar y)} {\displaystyle \sqrt {\sum _{k=1}^M (x_k - \bar x)^2} \;\sqrt {\sum _{k=1}^M (y_k - \bar y)^2}} \end {aligned} \end{equation}

Interpretation

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

• • \(r_{xy} > 0\): positive linear association (as \(x\) increases, \(y\) tends to increase).

• • \(r_{xy} < 0\): negative linear association (as \(x\) increases, \(y\) tends to decrease).

• • \(r_{xy} = 0\): no linear association (a nonlinear relationship may still exist).

• • \(|r_{xy}| = 1\): perfect linear relationship (\(y_k = a + bx_k\) for all \(k\)).

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

2.2.3 Normal Equations

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

\begin{equation} \label {eq-lr-univariate-coeff-stat} \begin{aligned} w_1&=\frac {s_{xy}}{s_x^2}= r_{xy}\,\frac {s_y}{s_x}\nonumber \\ &=\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 \nonumber \\ &= \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\ne \mathrm {const}\).

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

  \(\seteqnumber{0}{}{21}\)

  \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 Metrics

2.3.1 Coefficient of Determination (R²)

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

\begin{equation} \label {eq-sst-ssr-sse} \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).

R² of Uni-variate Linear LS 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}

2.3.2 MSE of Linear LS

The general (biased³) MSE is given by

\begin{equation} \MSE = s_y^{2}\bigl (1-r_{xy}^{2}\bigr ) = s_e^{2} \end{equation}

2.4 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 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.

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} \MSE = 1 - r_{xy}^{2} = s_e^2. \end{equation}

Geometrical 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 angle between them is \(\theta \) and \(r_{xy}=\cos \theta \) (Fig. 2.2).

  • Proof. The corresponding dot product is

    \(\seteqnumber{0}{}{40}\)

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

    Using (2.37),

    \(\seteqnumber{0}{}{41}\)

    \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}{}{42}\)

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

Consequences:

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

• • Special cases:

  • – \(r_{xy}=+1\) indicates perfect positive linear association, \(\theta = 0^\circ \).

  • – \(r_{xy}=-1\) indicates perfect negative linear association, \(\theta = 180^\circ \).

  • – \(r_{xy}=0\) indicates no linear association, \(\theta = 90^\circ \).

2.5 Spearman Rank Correlation

The Pearson correlation coefficient \(r_{xy}\) measures linear association. When the relationship between \(x\) and \(y\) is monotonic but non-linear, or when the data contain outliers, the Spearman rank correlation provides a more robust measure.

Let \(R(x_i)\) denote the rank of \(x_i\) among \(\{x_1,\dots ,x_M\}\) (with average ranks for ties), and similarly \(R(y_i)\). The Spearman correlation is the Pearson correlation computed on the ranks:

\begin{equation} r_s = r_{R(x)\,R(y)} \end{equation}

• • Range: \(-1 \le r_s \le +1\).

• • \(|r_s| = 1\): perfect monotonic (not necessarily linear) relationship.

• • Robust to outliers and non-linear monotonic relationships.

• • For linear data, \(r_s \approx r_{xy}\).