Intro to ML

This note is a recap of the mathematical background used in the Machine Learning: linear algebra (least squares and the eigenvector problem) and probability and statistics (distributions, confidence intervals, hypothesis testing, and the Bayesian approach).

Reference

• Bishop, C.M., Pattern Recognition and Machine Learning, 2006, Springer.
• Montgomery, D.C., Runger, G.C., Applied Statistics and Probability for Engineers, 2010, John Wiley & Sons.

Linear algebra

Least squares

Consider a dataset of $N$ inputs $x_i = (x_{i1}, \dots, x_{iD})$ with $x_{ij} \in \mathbb{R}$, so that each input has dimension $D$, and a target $t_i \in \mathbb{R}$ for each input. We want to predict the target $t_i$ with a linear combination of the input $x_i$, i.e. we want to find a vector of parameters

that minimizes a loss function. When the loss is the sum of the squared prediction errors, we are performing least squares minimization.

Loss function

The least squares loss is

Defining the design matrix (each row is an input vector $x_i$)

and the residual (error) vector

the loss can be written equivalently as

Minimizing the loss

To minimize the loss we compute its gradient with respect to each component of $w$:

There are two equivalent ways to compute it: an elementwise (traditional) derivative and a matrix derivative.

Traditional (elementwise) derivative. Since only the term $x_{ih} w_h$ depends on $w_h$ inside the inner sum,

For example, with $D = 3$ the inner sum is $x_{i1} w_1 + x_{i2} w_2 + x_{i3} w_3$; for $h = 2$ the derivative picks out the coefficient $x_{i2}$ of $w_2$.

Matrix derivative. Starting from the residual vector $r = t - Xw$, and using $\partial r / \partial w = -X$,

Written componentwise, this is

which matches the elementwise derivative.

Setting the gradient to zero gives the normal equations

whose solution (when $X^\top X$ is invertible) is

Eigenvector problem

Given a square matrix $A \in \mathbb{R}^{N \times N}$, the eigenvalue equations are

• The eigenvectors $v_1, \dots, v_N$ are the directions along which vectors are not deviated by the transformation $A$.
• The eigenvalues $\lambda_1, \dots, \lambda_N$ are the stretch factors for the directions $v_i$.

Graphical representation

When $v$ is an eigenvector of $A$, applying $A$ does not change its direction: it only stretches it by the eigenvalue $\lambda$, so $A v$ lies on the same line through the origin as $v$. In the interactive plot below we use

{
  "data": [],
  "layout": {
    "title": { "text": "Eigenvector: A v = λ v" },
    "xaxis": {
      "range": [-0.8, 5],
      "zeroline": true,
      "zerolinecolor": "#999999",
      "title": { "text": "x" },
      "showgrid": true,
      "gridcolor": "rgba(128,128,128,0.25)"
    },
    "yaxis": {
      "range": [-0.8, 3],
      "scaleanchor": "x",
      "scaleratio": 1,
      "zeroline": true,
      "zerolinecolor": "#999999",
      "title": { "text": "y" },
      "showgrid": true,
      "gridcolor": "rgba(128,128,128,0.25)"
    },
    "showlegend": false,
    "hovermode": "closest",
    "margin": { "l": 50, "r": 30, "t": 50, "b": 50 },
    "shapes": [
      { "type": "line", "x0": 2, "x1": 2, "y0": 0, "y1": 1, "line": { "color": "#999999", "width": 1, "dash": "dot" } },
      { "type": "line", "x0": 0, "x1": 2, "y0": 1, "y1": 1, "line": { "color": "#999999", "width": 1, "dash": "dot" } },
      { "type": "line", "x0": 4, "x1": 4, "y0": 0, "y1": 2, "line": { "color": "#999999", "width": 1, "dash": "dot" } },
      { "type": "line", "x0": 0, "x1": 4, "y0": 2, "y1": 2, "line": { "color": "#999999", "width": 1, "dash": "dot" } }
    ],
    "annotations": [
      { "x": 4, "y": 2, "xref": "x", "yref": "y", "ax": 0, "ay": 0, "axref": "x", "ayref": "y", "showarrow": true, "arrowhead": 3, "arrowsize": 1.5, "arrowwidth": 6, "arrowcolor": "#ff9896", "text": "" },
      { "x": 2, "y": 1, "xref": "x", "yref": "y", "ax": 0, "ay": 0, "axref": "x", "ayref": "y", "showarrow": true, "arrowhead": 3, "arrowsize": 1.5, "arrowwidth": 6, "arrowcolor": "#d62728", "text": "" },
      { "x": 3.1, "y": 2.05, "xref": "x", "yref": "y", "text": "<b>Av = λv</b>", "showarrow": false, "font": { "color": "#d62728", "size": 15 }, "align": "left" },
      { "x": 0.95, "y": 0.72, "xref": "x", "yref": "y", "text": "<b>v</b>", "showarrow": false, "font": { "color": "#d62728", "size": 15 } },
      { "x": 2, "y": -0.35, "xref": "x", "yref": "y", "text": "x", "showarrow": false, "font": { "color": "#888888", "size": 13 } },
      { "x": 4, "y": -0.35, "xref": "x", "yref": "y", "text": "λx", "showarrow": false, "font": { "color": "#888888", "size": 13 } },
      { "x": -0.45, "y": 1, "xref": "x", "yref": "y", "text": "y", "showarrow": false, "font": { "color": "#888888", "size": 13 } },
      { "x": -0.45, "y": 2, "xref": "x", "yref": "y", "text": "λy", "showarrow": false, "font": { "color": "#888888", "size": 13 } }
    ]
  }
}

In matrix form, for a generic pair $(\lambda, v)$,

This problem has a non-null solution only if the matrix $A - \lambda I_N$ is not full rank, or equivalently if

“Eigen” properties

• The rank of $A$ equals the number of non-zero eigenvalues.
• The determinant of $A$ equals the product of its eigenvalues:

• The trace of $A$ equals the sum of its eigenvalues:

Two useful definitions

• A matrix $A$ is positive definite if $x^\top A x > 0$ for all $x \in \mathbb{R}^N \setminus {0}$.
• A matrix $A$ is semi-positive definite if $x^\top A x \ge 0$ for all $x \in \mathbb{R}^N \setminus {0}$.

An easier way to check these properties is through the eigenvalues:

• A positive definite matrix has all positive eigenvalues, i.e. $\lambda_i > 0$ for all $i$.
• A semi-positive definite matrix has all non-negative eigenvalues, i.e. $\lambda_i \ge 0$ for all $i$.

Probability and statistics

Distributions

Discrete random variables

A discrete random variable $X$ is a variable with values in a discrete set $E$ whose value is determined by a stochastic phenomenon. We define a probability function $P : E \to [0, 1]$ that tells how often an event in $E$ occurs:

For instance, in a 20-faced die:

A properly defined probability function satisfies

Cumulative function

Assuming the events are ordered, the cumulative function defines the probability of multiple events:

For instance, in a 20-faced die:

A properly defined cumulative function satisfies

Characterizing the distribution

The quantities that characterize a random variable are the expected value and the variance (the first two moments):

For instance, in a 20-faced die:

Sometimes we compute the standard deviation instead of the variance:

Continuous random variables

If the set $E$ is not discrete, i.e. $E \subseteq \mathbb{R}$, we define the probability density function (pdf):

with properties

The cumulative density function (CDF) is defined as

with properties

A quantile of order $\alpha$ is a point $z_\alpha \in \Omega$ such that

i.e. a point of the domain leaving a cumulated probability $1 - \alpha$ to its left.

Characterizing continuous random variables

The expected value and the variance for a continuous random variable are

For the Gaussian case:

Estimating the distributions

Usually we do not have any information about the distributions, so we need to estimate their mean and variance:

These are consistent estimators for the expected value and the variance, respectively.

Central Limit Theorem

Let us consider the empirical expected value $\bar{X}$. We recall the Central Limit Theorem (CLT):

Theorem (Central Limit Theorem). Assume ${X_1, \dots, X_n}$ is a sequence of independent and identically distributed (i.i.d.) random variables with $\mathbb{E}[X_i] = \mu$ and $\operatorname{Var}[X_i] = \sigma^2 < \infty$. Then

\[\sqrt{n} \left( \frac{\sum_{i=1}^{n} X_i}{n} - \mu \right) \to \mathcal{N}(0, \sigma^2),\]

where the convergence holds in distribution.

Empirical distributions

Even when samples come from different distributions, the sample mean exhibits the same limiting distribution, which is the empirical evidence of the CLT.

Confidence intervals

We need to set a level identifying whether our estimator is “good enough”. The probability that $\bar{X} = \mathbb{E}[X]$ is zero, since the realization of the expected value is itself a continuous random variable. We therefore build intervals where we have high confidence that the true mean $\mathbb{E}[X]$ lies. A 95% confidence interval works 95% of the times.

Options for the confidence intervals:

Gaussian approximation:

Chebyshev inequality (requires $\mathbb{E}[X] = \mu < \infty$ and $\operatorname{Var}[X] = \sigma^2 < \infty$):

Hoeffding inequality (finite support):

Hypothesis testing

A scientific statement we may want to show is that the estimated parameter $\bar{X}$ is equal to $\mu$, or that an estimated parameter $\bar{X}’$ is different from another estimated parameter $\bar{X}’’$.

Statistics answers by defining a null hypothesis $H_0$ and an alternative hypothesis $H_1$:

and then uses the data to provide evidence that either one or the other holds.

Basic Gaussian test

Given the data ${x_1, \dots, x_n}$ we have

Fixing a confidence $1 - \alpha$, with $\alpha \in (0, 1)$, the test statistic $t$ should be close to the real mean $\mu$ with “high” probability:

P-value

To avoid specifying the confidence $\alpha$, we can let the data tell us how confident we can be about their correspondence to a specific hypothesis:

• Small p-values imply that we are confident that the $H_1$ hypothesis holds.
• Large p-values imply that we are not able to tell that the $H_0$ hypothesis does not hold.

Bayesian approach

Confidence bounds include some information about the data, but they do not allow us to incorporate information one has about the distribution parameters. The new idea is that the expected value $\mu$ of the random variable is itself a random variable. We use the Bayes formula to update this information:

Example: Bernoulli variables

Consider the Bayes formula applied to a sequence of observations:

We incorporate information incrementally from a prior distribution $P(\mu)$.

For example, if we have a prior telling us that there were 3 successes over 10 trials, using a Beta distribution as prior for $\mu$ ($\mu \sim \operatorname{Beta}(3, 7)$), the posterior is still a Beta distribution, i.e. Bernoulli and Beta form a conjugate prior-posterior pair.