机器学习基本概念

发布于 2021-01-24  755 次阅读


一.泛化误差和经验误差

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}
$$