4. Data

• Samples are picked from some unknown distribution + some noise

$L(\hat{f},\mathbb{P})={\mathbb{E}}_X(\hat{f}(X)-f^{\ast }(X){)}^2+{\sigma }^2$ where ${\sigma }^2={\mathbb{E}}_X(Y-f^{\ast }(X){)}^2$

$\mathbb{E}=$ expectation

Bias and variance

K-fold Cross Validation

• Split training data into $k$ subsets
• Train $K$ models: Hold back one as validation set, train on other
• Average validation error
• Pick hyperparameters with lowest validation error
• Train on entire dataset
• Evaluate on unbiased test data

Best: $K=|D_{use}|$ b/c $D’$ would be very similar to $D_{use}$. Typical in practice: $K=$ 5 or 10.

Limit Model Complexity

Limit the search space of possible functions by:

• Restrict polynomial degree
• LASSO (L1 regularization): Limit L1 norm ${\mathrm{argmin}}_{w\in {\mathbb{R}}^d}\Vert y-Xw{\Vert }_2^2\text{s.t.}\Vert w{\Vert }_1\le R$ $⟺{\mathrm{argmin}}_{w\in {\mathbb{R}}^d}\Vert y-Xw{\Vert }_2^2+\lambda \Vert w{\Vert }_1$ for some (unknown) $\lambda$ (lasso)
• Ridge (L2 regularization): Limit L2 norm ${\mathrm{argmin}}_{w\in {\mathbb{R}}^d}\Vert y-Xw{\Vert }_2^2\text{s.t.}\Vert w{\Vert }_2\le R$ $⟺{\mathrm{argmin}}_{w\in {\mathbb{R}}^d}\Vert y-Xw{\Vert }_2^2+\lambda \Vert w{\Vert }_2^2$ for some unknown $\lambda$

Key distinction: LASSO → sparse (feature selection), Ridge → small but nonzero weights.