机器学习：训练与测试

本节的主要内容来自Hsuan-Tien Lin的机器学习基石课程[1]。

学习的两个核心问题：

1. 能确保$E_{out}(g)$接近$E_{in}(g)$么？
2. 能够使$E_{in}(g)$足够小么？

$\lvert\mathcal H\rvert=M$与上述两个问题有什么关系？

太小的$M$使坏事儿发生的概率小，$E_{out}(g)$接近$E_{in}(g)$接近的概率大，但是不一定能找到很小的$E_{in}(g)$；太大的$M$使坏事儿发生的概率增大了。

M的起源

坏事情（$\mathcal B$AD Event）$\mathcal B_m~\left(\left\lvert E_{in}(h_m) - E_{out}(h_m)\right\rvert > \epsilon\right)$发生的概率为

\begin{equation*} \begin{aligned} P(\mbox{BAD}) & = P(\mathcal B_1 \mbox{ or }\mathcal B_2 \mbox{ or }\ldots\mathcal B_M) \\ &\leq P(\mathcal B_1) + P(\mathcal B_2) + \ldots + P(\mathcal B_M)\\ &\leq 2M\exp\left(-2\epsilon^2N\right) \end{aligned}。 \end{equation*}

事实上，过高的估计了坏事情发生的概率上界，因为$\mathcal B_m$之间可能有很大的相似区域重叠，比如感知器算法两次的判别界很接近。因此，可以期望得到比$M$小得多的值约束这个概率上界，也就是$\mathcal H$中的元素个数不会太多。

有效判别界

在$H$中，对相似的假设（判别函数）进行分组合并，有效减少假设的数目$M$。以下两图通过2维平面的线性判别界为例说明判别函数的类别。

图 1: ［左］：1个点的分类情况；［右］：2个点的分类情况 [PNG]

上图左可见，对于只有1个点的数据集，只有2种分类情况，$\mathcal H$只需2种假设就够了；上图右可见，对于2个点的数据集，有4种分类情况，$\mathcal H$只需4种假设就够了。

图 2: ［左］：3个点的分类情况；［右］：4个点的部分分类情况 [PNG]

上图中，打叉表示线性不可分。上图左可见，对于有3个点的数据集，有6种分类情况，$\mathcal H$只需6种假设就够了；上图右可见，对于4个点的数据集，有14种分类情况（图中只画出了其中一半的情况），$\mathcal H$只需14种假设就够了。

$N$输入数据$\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N$所需判别界的类别数目称之为判别界的有效数目（effective number of lines）。通过分析可知，$\mbox{effective}(N)\leq 2^N$，用其代替$M$可得 \begin{equation} P\left[\left\lvert E_{in}(g) - E_{out}(g)\right\rvert > \epsilon\right]\leq 2\cdot\mbox{effective}(N)\cdot\exp\left(-2\epsilon^2N\right)。 \end{equation}

成长函数

将$h(\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N)=(h(\mathbf x_1), h(\mathbf x_2), \ldots, h(\mathbf x_N))\in\{\times, \circ\}^N$称为一个二分法（dichotomy）。这就将假设限定在了数据集$\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N$上。$\mathcal H(\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N)$表示$\mathcal H$在$\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N$上的所有二分法。

$\lvert\mathcal H(\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N)\rvert$的大小受数据$\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N$的影响，不同的$N$个点，得到的值可能不一样。将成长函数（growth function）定义为 \begin{equation} m_{\mathcal H}(N) = \max_{\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N\in\mathcal X}\lvert\mathcal H(\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N)\rvert， \end{equation} 成长函数消除数据集依赖，是$N$个点数据集二分法数目的最大值，最大值为$2^N$。

对2维平面的线性判别界，$m_{\mathcal H}(1)=2$、$m_{\mathcal H}(2)=4$、$m_{\mathcal H}(3)=8$、$m_{\mathcal H}(4)=14$。

图 3: ［左］：1维空间正射线判别函数；［右］：1维空间正区间判别函数 [PNG]

上图左，对1维空间的正射线判别函数，$\mathcal X = \mathbb R$，$h(x)=\mbox{sign}(x-a)$（$a$是分类阈值），$m_{\mathcal H}(N)=N+1$。

上图右，对1维空间的正区间判别函数，$\mathcal X = \mathbb R$， \[ h(x)=\left\{ \begin{aligned} &+1 &x\in[\ell, r)\\ &-1 &\mbox{otherwise} \end{aligned} \right. ， \] $m_{\mathcal H}(N)=\binom{N+1}{2}+1={1\over 2}N^2+{1\over 2}N + 1$。

断点

图 4: 假设集打碎输入数据 [PNG]

对于2维平面上的$N$个点，$\mathcal X\in \mathbb R^2$，若$\mathcal H$是凸包，那么如上图所示，$m_{\mathcal H}(N)=2^N$。

如果某$N$个点数据集（也就是空间中存在按某种方式排列的$N$个点）的所有二分法都能被$\mathcal H$实现，就称这$N$个点被$\mathcal H$打碎（shatter）。也就是，若$m_{\mathcal H}(N)=2^N$，当且仅当某$N$个点的数据集能被打碎。

如果不存在$k$个点的数据集能够被$\mathcal H$打碎，就称$k$是$\mathcal H$的一个断点（break point），也就是对任意$k$个点$m_{\mathcal H}(k) < 2^k$¹。如果$k$是断点，那么$k,k+1,k+2,\ldots$都是断点，通常研究最小的断点$k$。若$k$是最小断点，那么一定存在一个$k-1$点的数据集能被$\mathcal H$打碎。

成长函数与断点

$m_{\mathcal H}(N)=O\left(N^{k-1}\right)$。

正射线和正区间判别函数的最小断点分别是$2$和$3$，2维感知器的最小断点是$4$，凸包没有断点²。

参考资料

1. [1]H.-T. Lin, “Lecture 5: Training versus Testing.” Coursera, 2014. [Online]

脚注