Machine Learning & Signals Learning

7 Uni-Variate Linear Least-Squares

The goal of this chapter is to define and discuss uni-variate linear least-squares (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.

7.1 Uni-variate Linear LS

7.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}{7.}{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}{7.}{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}{7.}{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.

7.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 (7.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 (7.10) into (7.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\).

7.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 ((7.4) and Fig. 7.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.

7.2 Covariance & Correlation Coefficient

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

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

7.2.3 Normal Equations with Statistical Terms

It is numerically convenient to rewrite the normal equations (7.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 (7.21) reduces to

  \(\seteqnumber{0}{7.}{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}

7.3 Metrics (R², MSE)

7.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}_{\SST } = \underbrace {\sum _{k=1}^{M}(\hat {y}_k-\bar {y})^2}_{\SSR } + \underbrace {\sum _{k=1}^{M}e_k^2}_{\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 {\SSR }{\SST } =1 - \frac {\SSE }{\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}

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

7.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. 7.4).

  • Proof. The corresponding dot product is

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

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

    Using (7.37),

    \(\seteqnumber{0}{7.}{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}{7.}{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 \).

7.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}\).

7.6 Correlation is not Causation

A non-zero \(r_{xy}\) (or \(r_s\)) quantifies statistical association between \(x\) and \(y\), but it says nothing about whether \(x\) causes \(y\). Several distinct mechanisms can produce the same correlation:

• • Direct causation: \(x\) genuinely drives \(y\).

• • Reverse causation: \(y\) drives \(x\), not the other way around.

• • Confounding (common cause): a third variable \(z\) influences both \(x\) and \(y\), inducing an association between them even though neither causes the other.

• • Selection bias: the way the dataset was sampled induces a correlation that does not exist in the underlying population.

• • Coincidence: in small samples, or when many variable pairs are tested, large \(|r_{xy}|\) values arise purely by chance (spurious correlation).

Further Reading

• • Spurious Correlations by Tyler Vigen is a great illustration of the principle that correlation is not causation.

7.7 Exercises

7.1 (Reading the correlation coefficient) Fig. 7.5 shows the results of four two-dimensional experiments. Rank them from the highest to the lowest absolute correlation coefficient \(\abs {r_{xy}}\), and justify the ranking.

7.2 (Spearman against Pearson) Six measurements are taken of a quantity believed to grow geometrically,

For each dataset:

• (a) Compute the Pearson coefficient \(r_{xy}\).

• (b) Compute the Spearman coefficient \(r_s\) (Sec. 7.5).

• (c) Explain the gap between the two in the clean case, and what changes in the noisy one.

Useful sums for both datasets: \(\sum _k(x_k-\bar {x})^2 = 17.5\) and \(\sum _k(y_k-\bar {y})^2 = 703.5\).

7.3 (simulation: how often does noise look correlated) Find out, by simulation, how large a correlation coefficient has to be before it means anything.

Generate \(M\) pairs \((x_k,y_k)\) of independent standard normal values (randn), so that the true correlation is zero, and compute \(\hat {r}_{xy}\). Repeat \(k\) times, for \(M = 10\), \(30\) and \(100\). Fig. 7.6 shows the result of such a simulation with \(k=10^5\).

• (a) Reproduce Fig. 7.6 with your own simulation and \(k=10^4\). What do the three boxes have in common, and what changes with \(M\)?

• (b) Compare the std values \(s\) in the figure with \(1/\sqrt {M-1}\).

• (c) What is shown in red? Explain the red lines and the red numbers, and what the red number at \(M=10\) means for a reader who finds \(\abs {r_{xy}} > 0.6\), a value most readers would call a strong correlation, in a dataset of ten points.

• (d) State the practical rule this suggests for reporting a correlation coefficient.

7.4 (simulation: regression error against sample size) This assignment focuses on the effect of the sample size on linear least-squares. Generate data from a known linear model, \(y_k = w_1x_k + w_0 + \epsilon _k\) with \(\epsilon _k\) of variance \(\sigma ^2\), fit it by LS, and study the resulting \(\MSE \).

• • Perform linear regression using the LS method and analyze the \(\MSE \) across different sample sizes \(M\).

• • Repeat each \(\MSE \) evaluation at least 30 times.

• • Summarize the results in a boxplot (e.g., as in Fig. 7.7).

• • Does it seem reasonable that the \(\MSE \) grows with an increase in \(M\) (more data)?

Hint for the last part: count how many of the \(M\) errors are free to vary once two coefficients have been fitted to the same data.