Linear regressions, the probabilistic viewpoint

$\def\sa{a} \def\sb{b} \def\sc{c} \def\sd{d} \def\se{e} \def\sf{f} \def\sg{g} \def\sh{h} \def\si{i} \def\sj{j} \def\sk{k} \def\sl{l} \def\sm{m} \def\sn{n} \def\so{o} \def\sp{p} \def\sq{q} \def\sr{r} \def\ss{s} \def\st{t} \def\su{u} \def\sv{v} \def\sw{w} \def\sx{x} \def\sy{y} \def\sz{z} \def\va{\vec{a}} \def\vb{\vec{b}} \def\vc{\vec{c}} \def\vd{\vec{d}} \def\ve{\vec{e}} \def\vf{\vec{f}} \def\vg{\vec{g}} \def\vh{\vec{h}} \def\vi{\vec{i}} \def\vj{\vec{j}} \def\vk{\vec{k}} \def\vl{\vec{l}} \def\vm{\vec{m}} \def\vn{\vec{n}} \def\vo{\vec{o}} \def\vp{\vec{p}} \def\vq{\vec{q}} \def\vr{\vec{r}} \def\vs{\vec{s}} \def\vt{\vec{t}} \def\vu{\vec{u}} \def\vv{\vec{v}} \def\vw{\vec{w}} \def\vx{\vec{x}} \def\vy{\vec{y}} \def\vz{\vec{z}} \def\ga{\mathfrak{A}} \def\gb{\mathfrak{B}} \def\gc{\mathfrak{C}} \def\gd{\mathfrak{D}} \def\ge{\mathfrak{E}} \def\gf{\mathfrak{F}} \def\gg{\mathfrak{G}} \def\gh{\mathfrak{H}} \def\gi{\mathfrak{I}} \def\gj{\mathfrak{J}} \def\gk{\mathfrak{K}} \def\gl{\mathfrak{L}} \def\gm{\mathfrak{M}} \def\gn{\mathfrak{N}} \def\go{\mathfrak{O}} \def\gp{\mathfrak{P}} \def\gq{\mathfrak{Q}} \def\gr{\mathfrak{R}} \def\gs{\mathfrak{S}} \def\gt{\mathfrak{T}} \def\gu{\mathfrak{U}} \def\gv{\mathfrak{V}} \def\gw{\mathfrak{W}} \def\gx{\mathfrak{X}} \def\gy{\mathfrak{Y}} \def\gz{\mathfrak{Z}} \def\ra{A} \def\rb{B} \def\rc{C} \def\rd{D} \def\re{E} \def\rf{F} \def\rg{G} \def\rh{H} \def\ri{I} \def\rj{J} \def\rk{K} \def\rl{L} \def\rm{M} \def\rn{N} \def\ro{O} \def\rp{P} \def\rq{Q} \def\rr{R} \def\rs{S} \def\rt{T} \def\ru{U} \def\rv{V} \def\rw{W} \def\rx{X} \def\ry{Y} \def\rz{Z} \def\rva{\vec{A}} \def\rvb{\vec{B}} \def\rvc{\vec{C}} \def\rvd{\vec{D}} \def\rve{\vec{E}} \def\rvf{\vec{F}} \def\rvg{\vec{G}} \def\rvh{\vec{H}} \def\rvi{\vec{I}} \def\rvj{\vec{J}} \def\rvk{\vec{K}} \def\rvl{\vec{L}} \def\rvm{\vec{M}} \def\rvn{\vec{N}} \def\rvo{\vec{O}} \def\rvp{\vec{P}} \def\rvq{\vec{Q}} \def\rvr{\vec{R}} \def\rvs{\vec{S}} \def\rvt{\vec{T}} \def\rvu{\vec{U}} \def\rvv{\vec{V}} \def\rvw{\vec{W}} \def\rvx{\vec{X}} \def\rvy{\vec{Y}} \def\rvz{\vec{Z}} \def\seta{A} \def\setb{B} \def\setc{C} \def\setd{D} \def\sete{E} \def\setf{F} \def\setg{G} \def\seth{H} \def\seti{I} \def\setj{J} \def\setk{K} \def\setl{L} \def\setm{M} \def\setn{N} \def\seto{O} \def\setp{P} \def\setq{Q} \def\setr{R} \def\sets{S} \def\sett{T} \def\setu{U} \def\setv{V} \def\setw{W} \def\setx{X} \def\sety{Y} \def\setz{Z} \def\fa{a} \def\fb{b} \def\fc{c} \def\fd{d} \def\fe{e} \def\ff{f} \def\fg{g} \def\fh{h} \def\fi{i} \def\fj{j} \def\fk{k} \def\fl{l} \def\fm{m} \def\fn{n} \def\fo{o} \def\fp{p} \def\fq{q} \def\fr{r} \def\fs{s} \def\ft{t} \def\fu{u} \def\fv{v} \def\fw{w} \def\fx{x} \def\fy{y} \def\fz{z} \def\fA{A} \def\fB{B} \def\fC{C} \def\fD{D} \def\fE{E} \def\fF{F} \def\fG{G} \def\fH{H} \def\fI{I} \def\fJ{J} \def\fK{K} \def\fL{L} \def\fM{M} \def\fN{N} \def\fO{O} \def\fP{P} \def\fQ{Q} \def\fR{R} \def\fS{S} \def\fT{T} \def\fU{U} \def\fV{V} \def\fW{W} \def\fX{X} \def\fY{Y} \def\fZ{Z} \def\ma{A} \def\mb{B} \def\mc{C} \def\md{D} \def\me{E} \def\mf{F} \def\mg{G} \def\mh{H} \def\mi{I} \def\mj{J} \def\mk{K} \def\ml{L} \def\mm{M} \def\mn{N} \def\mo{O} \def\mp{P} \def\mq{Q} \def\mr{R} \def\ms{S} \def\mt{T} \def\matu{U} \def\mv{V} \def\mw{W} \def\mx{X} \def\my{Y} \def\mz{Z} \def\loss{\mathcal{L}} \newcommand{\dkl}[2]{D_{\text{KL}}\mathopen{}\paren{#1\,||\,#2}} \newcommand{\dataset}{S} \newcommand{\ndataset}{N} \newcommand{\idataset}{n} \newcommand{\inputRV}{\mathcal{X}} \newcommand{\inputvec}{\vec{x}} \newcommand{\ninputvec}[1]{\vec{x}_{#1}} \newcommand{\iinputvec}[1]{x_{#1}} \newcommand{\niinputvec}[2]{x_{#1, #2}} \newcommand{\icpnt}{i} \newcommand{\inputmatrix}{X} \newcommand{\inputdim}{D} \newcommand{\outputval}{y} \newcommand{\ioutputval}[1]{y_{#1}} \newcommand{\outputvec}{\vec{y}} \newcommand{\trainset}{S_{\text{train}}} \newcommand{\testset}{S_{\text{test}}} \newcommand{\truemodel}{f_{\text{true}}} \newcommand{\trainedmodel}{f_{\trainset}} \newcommand{\linmodel}[1]{f_{#1}} \newcommand{\bestmodel}{f^{*}} \newcommand{\model}{f} \newcommand{\hyperparam}{\lambda} \newcommand{\linparamv}{\vec{w}} \newcommand{\ilinparam}[1]{w_{#1}} \newcommand{\indivloss}{l} \newcommand{\modelclass}{\mathcal{F}} \newcommand{\linclass}{\modelclass_{\text{lin}}} \newcommand{\g}{\mathcal{G}} \newcommand{\gmse}{\g_{\text{MSE}}} \newcommand{\glasso}{\g_{\text{lasso}}} \newcommand{\gridge}{\g_{\text{ridge}}} \newcommand{\glogit}{\g_{\logit}} \newcommand{\l}{\mathcal{L}} \newcommand{\lmse}{\l_{\text{MSE}}} \newcommand{\lmae}{\l_{\text{MAE}}} \newcommand{\llasso}{\l_{\text{lasso}}} \newcommand{\lridge}{\l_{\text{ridge}}} \newcommand{\llogit}{\l_{\logit}} \newcommand{\logit}{\sigma} \newcommand{\reg}{\mathcal{R}} \DeclareMathOperator*{\argmin}{argmin} \DeclareMathOperator*{\argmax}{argmax} \DeclareMathOperator*{\mean}{mean} \DeclareMathOperator*{\avg}{avg} \DeclareMathOperator*{\span}{span} \DeclareMathOperator*{\var}{var} \DeclareMathOperator*{\bias}{bias} \newcommand{\expectation}{\mathbb{E}} \newcommand{\brak}[1]{\left[#1\right]} \newcommand{\paren}[1]{\left(#1\right)} \newcommand{\realset}{\mathbb{R}} \newcommand{\realvset}[1]{\realset^{#1}} \newcommand{\prob}{\mathbb{P}} \newcommand{\gaussian}{\mathcal{N}} \newcommand{\iid}{\stackrel{\text{i.i.d.}}{\sim}} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \newcommand{\normtwo}[1]{\norm{#1}_{2}} \newcommand{\normone}[1]{\norm{#1}_{1}} \newcommand{\card}[1]{\left\lvert#1\right\rvert} \newcommand{\grad}{\nabla} \newcommand{\dconv}{\stackrel{d}{\to}} \newcommand{\pconv}{\stackrel{p}{\to}} \newcommand{\rva}[1]{#1} \newcommand{\rve}[1]{\vec{#1}} \newcommand{\obs}[1]{#1} \newcommand{\vobs}[1]{\vec{#1}} \newcommand{\distrib}[1]{#1} \newcommand{\distribof}[2]{#1_{#2}} \newcommand{\density}[1]{#1} \newcommand{\densityof}[2]{#1_{#2}} \newcommand{\distributed}{\sim} \newcommand{\const}[1]{#1} \newcommand{\fun}[1]{#1}$

General formulation

Let $(\rvx, \ry)$ be a pair of random variables on $\realvset{\sd} \times \realset$ .

A linear regression model assumes that $\expectation[\ry \mid \rvx = \vx]$ is a linear function of $\vx$ :

$\expectation[\ry \mid \rvx = \vx] = \vw\cdot\vx$

Where the parameter $\vw \in \realvset{\sd}$ is unknown.

A common use-case for this hypothesis is when $\ry$ is the sum of a linear signal and $0$ -mean random-noise $\epsilon$ :

$\ry = \vw\cdot\rvx + \epsilon$

Learning

Learning consists in finding an estimate for $\vw$ based on a sample $\trainset$ made of $\sn$ independent observations of $(\rvx, \ry)$ :

$\trainset = \{(\vx_\si, \sy_\si) \mid \si \leq \sn\}$

This can be done in two (sometimes equivalent) ways:

use an appropriate estimator tailored to the distribution of $\sy$ ; or
define a loss function and minimize the expected risk.

Let’s detail the second approach.

Loss function

The “best” value for the parameter $\vw$ can be defined through a loss function:

$\indivloss(\vw\cdot\vx, \sy)$

which measures the error between $\vw\cdot\vx$ and $\sy$ . Thus, $\indivloss$ increases with how wrongly $\vw\cdot\vx$ estimates $\sy$ .

Risk

For a fixed value of $\vw$ , the expected error in prediction is:

$\fr(\vw) = \expectation_{\rvx, \ry}[\indivloss(\vw\cdot\vx, \sy)]$

Which we will name the risk.

Ideally, we would want to minimize it:

$\begin{align*} \hat{\vw}_\text{ideal} =& \argmin_{\vw} \fr(\vw) \end{align*}$

But since we don’t know the distribution of $(\rvx, \ry)$ , the true risk is unknown. So we need to find a proxy: we will first estimate the risk, then estimate the parameters.

Empirical risk

For a fixed $\vw$ , the best estimate for the true risk given a sample $\sets$ is the sample average of the loss:

$\hat{\fr}(\vw, \sets) = \frac{1}{\card{\sets}}\sum_{(\vx, \sy) \in \sets} \indivloss(\vw\cdot\vx, \sy)$

Using the usual convergence theorems (law of large number, CLT, Chernoff bound) we know that:

the empirical risk is an unbiased estimator for the true risk; and
the error between them decreases as $\mathcal{O}(1 / \sqrt{\card{\sets}})$ .

Learning using the empirical risk

Given a sample $\trainset$ dedicated to training, we can compute our estimate for $\vw$ :

$\begin{align*} \hat{\vw}_{\trainset} =& \argmin_{\vw} \hat{\fr}(\vw, \trainset) \end{align*}$

We use $\trainset$ as subscript to reminds us that $\hat{\vw}$ greatly depends on the training-sample.

The training-error is the empirical risk computed on the training sample:

$\hat{\fr}(\hat{\vw}_{\trainset}, \trainset)$

It can’t reliably be used to estimate $\fr(\hat{\vw}_{\trainset})$ because of the way $\hat{\vw}$ is computed. For instance, with extreme overfiting it can happen that the training error is $0$ , but the real risk way above $0$ .

How does the model performs on unseen data?

To assess how our model performs on unseen data, we estimate the risk $\fr(\hat{\vw}_{\trainset})$ , which is also called the generalization error.

As explained previously, we can do so using a sample $\testset$ on which $\hat{\vw}_{\trainset}$ does not depend. i.e.

$\testset \cap \trainset = \emptyset$

Under this condition, the test-error:

$\hat{\fr}(\hat{\vw}_{\trainset}, \testset)$

is an unbiased estimate of the generalization error and converges at the speed of $\mathcal{O}(1 / \sqrt{\card{\testset}})$ .

How big should the testing sample be?

This can be answered using a Chernoff bound:

$\prob{\abs{\fr(\hat{\vw}) - \hat{\fr}(\hat{\vw}, \testset)} \geq \epsilon} \leq 2e^{-2\card{\testset}\epsilon^2 / (b -a)^2}$

If we assume for instance that $\abs{b - a} = 1000$ , the probability that the true risk $\fr(\hat{w})$ and the empirical risk $\hat{\fr}(\hat{w}, \testset)$ differ by more that $0.001$ is less than $2e^{-2\card{\testset}}$ . When the $\testset$ contains $1000$ samples, this evaluates to $10^{-869}$ …