Statistical Decision Theory¶
Table of Contents
This puts the prediction task under a statistical inference paradigm.
Statistical machine learning deals with the problem of prediction by using existing data to form a model. There are two distinct aspects of such a task
Note
Inference:
Since the model space can be arbitrarily complex, we assume some structure to the model.
The model can be a simplistic mathematical model which predicts a deterministic outcome given an unknown input.
The model can also be a probabilistic model which aims at learning the joint or the conditional distribution.
The task of inference (learning) is to use data to come up with an optimal model through some meaning of optimality.
Prediction:
Once we have the model, the task of prediction is simplified if our model is a deterministic one.
When our model is probabilistic, then we must instantiate (draw a sample) the outcome to a fixed value given an unknown input.
Statistical decision theory deals with the prediction problem which has it’s own notion of optimality, usually defined with the help of a loss function.
Statistical Inference¶
This is defined separately for regression and classification problem.
Analytic Solutions¶
Warning
Under this paradigm, the data is a realisation of some underlying random process.
We define the prediction problem under this framework.
The optimal solutions under this often rely on having access to the underlying distribution or some other quantities involving the distribution.
We also discuss ways to define the notion of optimality.
Single Random Variable¶
Note
We have a single real-valued rv \(X\).
We consider the estimation problem where we find an estimate \(\hat{x}\), a single value, for any future observation of \(X\).
We define Prediction Error (PE): The rv \(\tilde{X}=X-\hat{x}\), which has the same pdf as \(X\).
The optimality of our estimate is defined with the help of a loss function such that
\[\hat{X}_{\text{OPT}}=\underset{\hat{X}}{\arg\min} L(X,\hat{X})\]Loss function is usually some function of PE.
MSE loss function is defined as
\[\mathbb{E}_X[\tilde{X}^2]=\mathbb{E}_X[(X-\hat{x})^2]=\mathbb{E}_X[X^2]-2\mathbb{E}_X[X]\hat{x}+\hat{x}^2\]
Tip
To find \(\hat{x}\), we can differentiate w.r.t. \(\hat{x}\) to minimize MSE.
Note that \(\mathbb{E}_X[X^2]\) and \(\mathbb{E}_X[X]\) are constants.
Therefore
\[\frac{\partial}{\mathop{\partial\hat{x}}}\mathbb{E}_X[(X-\hat{x})^2]=-2\mathbb{E}_X[X]+2\hat{x}\implies\hat{x}_{\text{OPT}}=\mathbb{E}_X[X]\]
Two Random Variables¶
Note
We assume that the data \(X\) and the target \(Y/G\) are distributed per a joint distribution
[Regression] \(X,Y\sim F_{X,Y}(x,y)\)
[Classification] \(X,G\sim F_{X,G}(x,g)\)
We assume that we’ll have access to future realisations of \(X=x\) but not the target.
The task is to find an estimator for the target as function of data, \(\hat{Y}=f(X)\) or \(\hat{G}=g(X)\).
We use these to predict future values for the target as \(\hat{y}=f(x)\) and \(\hat{g}=g(x)\).
The optimality of our estimate is defined with a non-negative loss function, \(L\).
[Regression] \(\hat{Y}_{\text{OPT}}=\underset{\hat{Y}}{\arg\min} L(Y,\hat{Y})\)
[Classification] \(\hat{G}_{\text{OPT}}=\underset{\hat{G}}{\arg\min} L(G,\hat{G})\)
We wish the predictors to have minimal expected prediction error (EPE) over the joint.
[Regression] \(EPE=\mathbb{E}_{X,Y} L(Y,\hat{Y})\)
[Classification] \(EPE=\mathbb{E}_{X,G} L(G,\hat{G})\)
EPE can be reformulated as conditional expectation on observed input variables \(X\).
[Regression] \(EPE=\mathbb{E}_X\left[\mathbb{E}_{Y|X}[L(Y,\hat{Y}|X]\right]\)
[Classification] \(EPE=\mathbb{E}_X\left[\mathbb{E}_{G|X}[L(G,\hat{G}|X]\right]\)
Tip
Since \(L\) is non-negative, this quantity is minimised when it’s minimum at each point \(X=x\).
As we’re fixing \(X\) to a constant, the outer expectation \(\mathbb{E}_X\) goes away.
[Regression] \(\hat{y}_{\text{OPT}}=\underset{\hat{y}}{\arg\min}\left(\mathbb{E}_{Y|X}[L(Y,\hat{y}|X=x]\right)\)
[Classification] \(\hat{g}_{\text{OPT}}=\underset{\hat{g}}{\arg\min}\left(\mathbb{E}_{G|X}[L(G,\hat{g}|X=x]\right)\).
For particular choice of loss functions, we arrive as optimal (Bayes) estimator definitions
[Regression] With MSE loss, \(\hat{Y}=\mathbb{E}_{Y|X}[Y|X]\), mean of the conditional pdf.
[Classification] With 0-1 loss, \(\hat{G}\) corresponds to the mode of the conditional pmf.
Regression¶
Bayes Estimator¶
Note
This is the estimator which minimises MSE for each point \(X=x\).
\[L(Y,\hat{y})=\mathbb{E}_{Y|X}[(Y-\hat{y})^2|X=x]\]To find minimum, we differentiate w.r.t \(\hat{y}=f(x)\), a single value
\[\frac{\partial}{\mathop{\partial\hat{y}}}L(Y,\hat{y})=\frac{\partial}{\mathop{\partial\hat{y}}}\left(\mathbb{E}_{Y|X}[Y^2|X=x]-2\mathbb{E}_{Y|X}[Y|X=x]\hat{y}+\hat{y}^2\right)=-2\mathbb{E}_{Y|X}[Y|X=x]+2\hat{y}\]Therefore, the optimal estimator at each realisation \(X=x\) is given by
\[\hat{y}=f(x)=\mathbb{E}_{Y|X}[Y|X=x]\]We note that this estimator is unbiased.
Note
TODO - Alternate proof from Sayed and orthogonality conditions !!!IMPORTANT!!!
Approximating The Analytic Solutions¶
Warning
In practical problems, we often don’t have access to the underlying distribution.
In such cases, we resort to the approximation framework that tries to mimic the optimal solution.
We use statistical inference to estimate the unknowns of our model.
Regression - Approximating The Conditional Mean¶
Assuming locally constant nature of the fucntion¶
Note
In kNN regression approach, we approximate Bayes estimator by
replacing expectation with sample average
approximating the point \(X=x\) with a neighbourhood \(N(x)\) where \(|N(x)|=k\)
The parameter \(k\) is chosen using model selection approaches.
Usually the choice of \(k\) determines the roughness of this model, with larger values resulting in smoother model.
In this case \(f(x)=\mathbb{E}_{Y|X}[Y|X=x]\approx\text{Avg}(y_i|x_i\in N(x))\)
The implicit assumption is that the function behaves locally constant around each point \(x\)
Therefore, it can be estimated with the average value of the target \(y_i\) for each data point in the neighbourhood \(x_i\).
Explicit assumption from a model¶
Note
In linear regression, we explicitly assume that the estimator is affine in \(X_j\).
In this case, \(f(x)=\mathbb{E}_{Y|X}[Y|X=x]\approx \beta^T x + \beta_0\)
We usually add a dummy variable \(X_0=1\) in \(X\) and write this as a linear function
\[f(x)=\mathbb{E}_{Y|X}[Y|X=x]\approx \beta^T x\]
In basis expansion, we assume that the estimator is an affine in some transform \(h(x)\in\mathbb{R}^M\).
Example: \(x=(x_1,x_2)^T\overset{h}{\longrightarrow}(1,x_1,x_2,x_1x_2,x_1^2,x_2^2)^T\)
In this case, \(f(x)=\mathbb{E}_{Y|X}[Y|X=x]\approx \beta^T h(x)\)
Bias-Variance Tradeoff¶
Notation¶
Warning
All vectors are named for their column vector form.
For row-representation, we use the transpose notation.
Note
Data is associated with a random variable \(X\).
Observed data points are instances of the rv, \(X=x\in\mathbb{R}^d\) for some \(d\geq 1\).
If \(d> 1\), \(X\) is a random vector.
In this case, individual components can referred to as \(X_j\) and \(X=(X_1,\cdots,X_d)\).
Note
[Regression] The target quantity is associated with a continuous rv \(Y\) taking values \(Y=y\in\mathbb{R}^K\), for some \(K\geq 1\).
It might also be a random vector, with \(Y=(Y_1,\cdots,Y_K)\).
Single dimensional observations for target are usually written as \(Y=y\in\mathbb{R}\).
[Classification] The target quantity is associated with a discrete rv \(G\in\mathcal{G}\) with \(|\mathcal{G}|=K\).
Note
We have a total of \(N\) observations, and all the observations together are taken in the matrix form
\[\begin{split}\mathbf{X}_{N\times d}=\begin{bmatrix}-& x_1^T & - \\ \vdots & \vdots & \vdots \\ -& x_N^T & -\end{bmatrix}=\begin{bmatrix}|&\cdots&|\\ \mathbf{x}_1 & \cdots & \mathbf{x}_d \\ |&\cdots&|\end{bmatrix}\end{split}\]The vector \(\mathbf{x}_j\in\mathbb{R}^N\) represents the column vector for all the observations for rv \(X_j\).
A particular observation for \(X=x_i\in\mathbb{R}^d\) is taken in the row-vector form, \(x_i^T\in\mathbb{R}_{1\times d}\).
For \(K> 1\), we can also associate the target with the row vector form, \(y_i^T\in\mathbb{R}_{1\times K}\) [regression] or \(g_i^T\in\mathcal{G}_{1\times K}\) [classification].
Curse of Dimensionality¶
Note
As we move to higher dimensional space, the notion of distance doesn’t follow our intuition.
As this SO post puts it (quoting verbatim)
Another application, beyond machine learning, is nearest neighbor search: given an observation of interest, find its nearest neighbors (in the sense that these are the points with the smallest distance from the query point).
But in high dimensions, a curious phenomenon arises: the ratio between the nearest and farthest points approaches 1, i.e. the points essentially become uniformly distant from each other.
This phenomenon can be observed for wide variety of distance metrics, but it is more pronounced for the Euclidean metric than, say, Manhattan distance metric.
The premise of nearest neighbor search is that “closer” points are more relevant than “farther” points, but if all points are essentially uniformly distant from each other, the distinction is meaningless.
More resource on this: