机器学习基本概念

一.泛化误差和经验误差

1.泛化误差

对于某函数$h$，定义它的泛化误差（英文：generalization error），也称为泛化风险（英文：generalization risk）为：

$$
R(h)=E_{(\boldsymbol{x}, y) \sim \mathcal{D}}[I(h(\boldsymbol{x}) \neq y)]
$$

其中$I$为示性函数

2.示性函数

示性函数，它的自变量为某个事件$\omega$，定义为

$$
I(\omega)=\left\lbrace\begin{array}{ll}
1, & \text { 事件 } \omega \text { 发生 } \\
0, & \text { 事件 } \omega \text { 未发生 }
\end{array}\right.
$$

3.经验误差

对于某函数$h$，定义它在数据集$D$上的经验误差（数据集可以视为过往的经验，所以经验误差的意思就是在数据集上计算出来的误差，英文：empirical error），也称为经验风险（英文：empirical risk）为：

$$
\hat{R}_{D}(h)=\frac{1}{n} \sum_{i=1}^{n} I\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)
$$

其中$I$为示性函数，$n$为数据集$D$的元素个数

4.两者关系

当数据集$D$是分布$D$的独立同分布采样，有经验误差是泛化误差的无偏估计，即

$$
\begin{aligned}
E[\hat{R}(h)] &=E\left[\frac{1}{m} \sum_{i=1}^{m} I\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)\right] \\
&=\frac{1}{m} \sum_{i=1}^{m} E\left[I\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)\right]=R(h)
\end{aligned}
$$

5.霍夫丁不等式

$$
P\left(\left|\hat{R}_D(h)-R(h)\right| > \epsilon \right) \le 2e^{-2\epsilon^2 N}
$$

霍夫丁不等式证明了如果数据集$D$足够大，那么$“\hat{R}_D(h) = R(h)”$ 是 $PAC$的，是机器学习可行的逻辑起点。

二.经验误差最小原则

1.经验误差最小原则

因为数据集$D$足够大时，经验误差与泛化误差是$PAC$的，所以我们利用独立同分布的数据集$D$，用各种方法尽量去遍历假设空间$H$，从中选择使得$\hat{R}_D(h)$最小的$h$，作为最终的$g$，这就是经验误差最小的原则。

$$
g=\operatorname*{argmin}_{h\in\mathcal{H}}\hat{R}_D(h)
$$

2.大小为M的假设空间

$$
P\left(\left|\hat{R}_D(g)-R(g)\right| > \epsilon \right)\le P\left(\bigcup_{i=1}^{M}A_i\right) \le 2Me^{-2\epsilon^2 N}
$$

3.二分类的假设空间

$$
P\left(\left|\hat{R}_D(g)-R(g)\right| > \epsilon \right)\le 4\cdot 2^{2N}\cdot e^{-\frac{1}{8}\epsilon^2 N}
$$

这意味对于二分类，机器学习不一定可行

三.有断点的假设空间

1.成长函数

某假设空间$H$在大小为$N$的数据集$D$上，不论数据集$D$长什么样，总有一个有效大小的最大值。该最大值可以看作是关于$N$的函数，称为成长函数（英文：Growth Function），记作：

$$
\text{成长函数}=m_{\mathcal{H}}(N)
$$

那么我们关心的概率不等式变为

$$
P\left(\left|\hat{R}_D(g)-R(g)\right| > \epsilon \right)\le 4\cdot m_{\mathcal{H}}(2N)\cdot e^{-\frac{1}{8}\epsilon^2 N}
$$

2.断点

（1）假设某假设空间的断点为$k$则其成长函数满足：

$$
m_{\mathcal{H}}(N)\le N^{k-1},\quad N\ge 2, k\ge 3
$$

（2）当满足以下三个条件时：

• 数据集$D$是分布$D$的独立同分布样本，其中包含$N$个元素
• 经验误差$\hat{R}_D(g)$是泛化误差$R(g)$的无偏估计
• 某假设空间$H$的断点为$k$

那么有：

$$
P\left(\left|\hat{R}_D(g)-R(g)\right| > \epsilon \right)\le 4\cdot (2N)^{k-1}\cdot e^{-\frac{1}{8}\epsilon^2 N},N\ 足够大
$$

此时称该假设空间是可学习的。

（3)几种二分类假设空间的断点：

$$
\begin{array}{c|c|c}
\hline
\hline \\
\quad n 维感知机\quad & \quad k=n+2 \quad \\
\quad m 元 M 次多项式\quad & \quad k={m+M\choose m}+1 \quad \\
\quad 多边形\quad & \quad k=\infty\quad \\
\quad 正弦\quad & \quad k=\infty\quad \\
\\
\hline
\end{array}
$$