4. 泛化理论

• 证明m_h(N) 是多项式
• 证明m_h(N) 可以在Hoeffding不等式中代替M

证明m_h(N)为多项式

为了证明m_h(N)是多项式
将要证明m_h(N) ≤...≤...≤ 某一多项式

主要的参数：
B(N,k)：k作为断点时，N个点能被二分的最大组合数。

B(N,k)的递归边界

在满足k的情况下构建下表格，分析其结构。
说明：
为了能够表达递归，所以将Xn分离出来。目的是使得B(N,k) = B(N',k')且N != N'、k!=k'。
表格中每行不重复。

此时，B(N,k) = α + 2β

估算α与β

仅关注N-1个点的时候，

此时，α + β ≤ B(N-1,k)

现在关注S₂

image.png

此时 β ≤ B(N-1,k-1)

综上：

所以B的计算矩阵如下：

归纳为：

推导方式如下：

B 与 m_h(N)

举例

证明m_h(N) 可以在Hoeffding不等式中代替M

增长函数如何描述重叠

在二分过程中，单一的二分结果表示一个有效假设，而假设空间中有无穷多的假设。所以我们考虑能否用有效假设effective(N) ，即增长函数m_h(N) ， 来代替hoeffding不等式中的M。

但是Ein的可能取值是有限个的，但Eout涉及整个假设空间，所以它的可能取值是无限的。

Eout的处理

可以通过将Eout 替换为验证集(verification set) 的Ein’ 来解决这个问题。

我们将原本进行一次的抽样进行两个次，这样一来获得了Ein’。原本Eout 与 Ein相关联，现在Ein Ein’ 都与Eout相关联，那么Ein 与Ein’ 也相关联。Ein 和 Eout之间比例的所有差异情况都可以在Ein 和Ein’ 上反应出来。（从Ein 完全相同与Ein’ 到 Ein 完全不同于Ein’）

证明流程 VC不等式