3. 训练与测试

• 训练与测试
• 例证
• 重要概念：断点

训练与测试

以一次期末考试为例：

在测试中：
Ein 是考前复习时，与复习资料之间的误差。
Eout 是考试中，与考试资料之间的误差。
在训练中：
Ein 是对于练习题的学习误差。
Eout 是对于联系材料整体的学习误差。
但是在学习过程中，因为对材料整体越来越熟悉，反应你学习的复杂程度（次数）。

M来自哪里

对于不良事件记为：B_m
此时

其反应为B1到BM中至少有一个发生。

很明显，我们对Bad event的约束有很多重复，所以可以从这方面入手进行优化。

M的优化

以感知器模型为例进行说明：
Ein 与 Eout 其物理意义如图：

Eout.png Ein.png

当模型有所改变时：

改变十分微小的时候，h1 和 h2 两者的Ein 和Eout的差值几乎不变，这就是重叠部分的来源。

二分

因为输入空间是无限的，所以我们选择去考量有限个输入点序列。并统计点的二分数量（对或者错）
就像我们在上排图中改变感知器模型任意次，单下排图中的样本点时，我们只会认为这是同一种情况。

所以说，我们将整个输入空间变为了一个输入序列。进而可以为假设限定上限。

增长函数

对于上述的情况，我们为M设定了增长函数来对其进行限定。

将M的增长函数应用于感知器模型

我们发现，N=4的例子中，我们无法取得所有的组合方式，所以2^N这一上限无法达到。

例证

positive rays

positive intervals

凸集

三种情况下的增长函数

总结

因为指数的数字非常小，所以当m是一个多项式的时候，小的指数会使得多项式中绝大多数的失效，进而简化多项式。同时使得不等式右侧足够的小，这样一来就说明了模型的推广性与可用性。

image.png

重要概念：断点（break point）

定义

定义：自断点起，你无法获得所有的二分组合。
其对应了模型的复杂程度。

下图中，四个点的分布无法使用感知器模型进行彻底的二分，所以在该假设空间中，K=4。所以，我们在得知断点的情况下，无需关系N的大小。如此一来，可以将增长函数进行限定。

上述三个例证的断点

应用方式

K = 2时，任意三个点的组合：

image.png

不能够获得K=2个点的所有组合。
仅四个可实现的组合，证明了K是一个极佳限定方式。