2.4 Sample, loss, and error
Definition
2.5
I.i.d. sample
For a distribution \(D\) on \(X\) and a target concept \(c\), an i.i.d. sample of size \(m\) is a tuple \(S = ((x_1, c(x_1)), \dots , (x_m, c(x_m)))\) with each \(x_i \sim D\) drawn independently.
Definition
2.6
Zero-one loss
For \(h, c : X \to \{ 0,1\} \) and \(x \in X\), the zero-one loss is \(\ell (h, c, x) = \mathbf{1}[h(x) \neq c(x)]\).
Definition
2.7
Empirical and true error
For a hypothesis \(h\), a target \(c\), a distribution \(D\), and a sample \(S\) of size \(m\):
\begin{align*} \hat{R}_S(h) & = \frac{1}{m} \sum _{i=1}^{m} \mathbf{1}[h(x_i) \neq c(x_i)] & & \text{(empirical error)}, \\ R_D(h) & = \Pr _{x \sim D}\! \left[ h(x) \neq c(x) \right] & & \text{(true error)}. \end{align*}