29 Model Definition

• $\mathcal{X}$ : input space (input domain).
• $\mathcal{Y}=\{0,1\}$ : output space
• $c:\mathcal{X}\to \mathcal{Y}$ : classifier

Basic Assumption

All samples are drawn independently and identically distributed (i.i.d.) from some unknown distribution $\mathcal{D}$ over $\mathcal{X}\times \mathcal{Y}$.

• $S=\{(x_i,y_i){\}}_{i=1}^n\sim {\mathcal{D}}^n$ : a random i.i.d. sample set. (training sample or test sample, depending on the context).

True Error & Observed Error

A classifier $c$ is good if the following quantity is small :

• True Error : $c_{\mathcal{D}}\equiv {\mathrm{Pr}}_{(X,Y)\sim \mathcal{D}}\left(c(X)\ne Y\right)$.

  Problem

  This quantity is unknown because the true distribution is unknown.

Instead we have a sample from this unknown distribution. The following quantity is an empirical proxy based on the sample :

• Observed Error : ${\hat{c}}_S\equiv \frac{1}{n}{\sum }_{i=1}^n\mathbb{I}\left[c(x_i)\ne y_i\right]$ where $I(.)$ denotes indicator function.

Question

Is $c_{\mathcal{D}}$ a deterministic quantity (a number), or a random variable ?

Answer : Depends - if $c$ is a fixed function then $c_{\mathcal{D}}$ is deterministic (a number in $[0,1]$). If $c$ is the classifier trained on the sample $S$, then $c_{\mathcal{D}}$ is a random variable as a function of $c$.