Setup

Suppose we have a dataset of training examples

$$D = \{(x_1,y_1),\dots,(x_n,y_n)\}$$

and our goal is to learn some functional relationship

$$y = h(x), h:\mathcal{X} \rightarrow \mathcal{Y}$$

where $h$ is our hypothesis function, mapping from the input space X to the output space $Y$. Here $h$ refers to the whole model function, whether it be classification or regression. $h$ represents a perfect “dream” function that always gives the correct output for any input.

Risk

Risk is a term heavily correlated with loss or cost. We define the risk associated with a hypothesis $h$ as the expected loss:

$$R(h) = \mathbb{E} \, [ \, L(h(x),y) \, ] = \int{L(h(x),y) \, dP(x,y)}$$

where $P(x, y)$ is the joint probability distribution over the input and output space from which we assume our training examples are sampled i.i.d, and $L(h(x), y)$ is the loss function. The goal of a learning algorithm is to find the hypothesis $h$ from the hypothesis space $H$ which minimizes risk $R$. That is,

$$h^* = \text{argmin}_{h \, \in \, \mathcal{H}}R(h)$$

Note that risk here is often called true risk or test error.

Empirical Risk Minimization

We don’t know the joint probability over the data $P(x, y)$, so we cannot compute the risk of hypotheses directly. We can instead use empirical risk:

$$R_{\text{emp}}(h) = \frac{1}{n}\sum_{i=1}^{n}{ L(h(x_i),y_i) }$$

which is another term for training error. This is the best approximation of the true risk associated with $h$ with respect to our finite samples from $P(x, y)$.

Structural Risk Minimization

Strictly minimizing the training error without checks on model complexity often lead to extreme overfitting and thus poor performance on test data (i.e. large true risk). Structural risk minimization incorporates regularization into the formulation to help penalize higher model complexity, reducing the chance we overfit on training data. Structural risk is defined as follows:

$$R_{\text{srm}}(h) = \frac{1}{n}\sum_{i=1}^{n}{ L(h(x_i),y_i) } \, + \, \lambda R(w)$$

where $R$ is a regularizer that penalizes large model complexity, $w$ is the vector of model parameters, and $\lambda$ is a hyperparameter used to control the trade-off between training loss and regularization. Minimizing this structural risk is theoretically better than simply minimizing the empirical risk, leading to a lower true risk. Structural risk minimization is the generalized problem that most classical machine learning models attempt to solve, differing primarily by their choice of loss function and regularizer.