机器学习笔记之计算学习理论——PAC学习

引言回顾：霍夫丁不等式霍夫丁不等式的问题及其优化 PAC \text{PAC} PAC引出新问题——霍夫丁不等式无法通过直接比较获取最优假设函数问题的解决方法新方法对于霍夫丁不等式的约束证明 总结

引言

上一节从霍夫丁不等式为切入点，介绍了样本平均值和全样本期望，本节将继续介绍 PAC \text{PAC} PAC学习。

回顾：霍夫丁不等式

霍夫丁不等式( Hoeffding’sInequality ) (\text{Hoeffding's Inequality}) (Hoeffding’sInequality)可表示为如下形式：

P ( ∣ v − μ ∣ > ϵ ) ≤ 2 exp ⁡ ( − 2 ϵ 2 N ) \mathcal P(|v - \mu| > \epsilon) \leq 2 \exp(-2\epsilon^2N) P(∣v−μ∣>ϵ)≤2exp(−2ϵ2N)

其中 N N N表示数据集D \mathcal D D内的样本数量； v v v和 μ \mu μ分别表示样本平均值和全样本方差：

其中x 1 , x 2 , ⋯ , x p x_1,x_2,\cdots,x_p x1​,x2​,⋯,xp​是相互独立的随机变量;

{ v = 1 p ∑ i = 1 p x i μ = 1 p ∑ i = 1 p E [ x i ] \begin{cases} \begin{aligned} & v = \frac{1}{p} \sum_{i=1}^p x_i \\ & \mu = \frac{1}{p} \sum_{i=1}^p \mathbb E[x_i] \end{aligned} \end{cases} ⎩ ⎨ ⎧​​v=p1​i=1∑p​xi​μ=p1​i=1∑p​E[xi​]​​

其中 μ \mu μ是数据集D \mathcal D D所描述分布 D D D的真实期望。也就是说，在分布 D D D客观存在的条件下，其期望μ \mu μ也是一个客观存在的结果；而 v v v表示数据集D \mathcal D D自身样本的均值(期望)结果。

当样本数量N N N增大时，数据集D \mathcal D D所描述的分布越完整，越收敛于分布 D D D；从而均值v v v越趋近于真实期望μ \mu μ。最终使 v v v和 μ \mu μ之间差距大于设定边界ϵ \epsilon ϵ的概率越小。而霍夫丁不等式使用具体公式对该思想进行描述。

关于‘霍夫丁不等式’的证明过程，推荐文章见下方链接。侵删。

再次观察霍夫丁不等式，当设定边界ϵ \epsilon ϵ确定的条件下， ∣ v − μ ∣ > ϵ |v -\mu| > \epsilon ∣v−μ∣>ϵ这个事件(可理解为D \mathcal D D和D D D相差‘较大’，大于设定边界)发生的概率存在上界。也就是该概率必不超过δ = 2 exp ⁡ ( − 2 ϵ 2 N ) \delta = 2\exp(-2\epsilon^2N) δ=2exp(−2ϵ2N)。

相反，也就是说，必然至少存在1 − δ 1 -\delta 1−δ的概率 ∣ v − μ ∣ ≤ ϵ |v - \mu| \leq \epsilon ∣v−μ∣≤ϵ。 δ \delta δ越小， D \mathcal D D和 D D D的差距越小，越符合任务期望的结果。

霍夫丁不等式的问题及其优化

基于数据集 D \mathcal D D归纳得到假设函数h ( x ) h(x) h(x)和 δ \delta δ之间存在关联关系：

δ \delta δ越小，说明函数h ( x ) h(x) h(x)越优秀；其越接近真实函数G ( x ) \mathcal G(x) G(x)；相反， δ \delta δ越大，说明函数h ( x ) h(x) h(x)通过数据集D \mathcal D D的预测分布与真实分布D D D的差距较大，说明 h ( x ) h(x) h(x)对 D D D的泛化能力较差。

新的问题随之到来：

通过假设函数h ( x ) h(x) h(x)的预测分布表达样本平均数和全样本方差，无论 v v v还是 μ \mu μ，它们的表达结果都是不准确的——毕竟 h ( x ) h(x) h(x)和 G ( x ) \mathcal G(x) G(x)之间存在差距。那么两个不准确结果之间的差异自然没有意义。

P { ∣ 1 N ∑ i = 1 N h [ x ( i ) ] − E x ( i ) ∼ D [ h ( x ( i ) ) ] ∣ > ϵ } ≤ 2 exp ⁡ ( − 2 ϵ 2 N ) \mathcal P \left\{\left|\frac{1}{N} \sum_{i=1}^N h[x^{(i)}] - \mathbb E_{x^{(i)} \sim D} \left[h(x^{(i)})\right]\right| > \epsilon \right\} \leq 2 \exp(-2\epsilon^2N) P{​N1​i=1∑N​h[x(i)]−Ex(i)∼D​[h(x(i))] ​>ϵ}≤2exp(−2ϵ2N)

换个思路思考，由于我们的目标是得到最接近G ( x ) \mathcal G(x) G(x)的假设函数 h ( x ) h(x) h(x)，那么直接针对 G ( x ) \mathcal G(x) G(x)和 h ( x ) h(x) h(x)之间的差距进行量化，去描述 ∣ v − μ ∣ |v - \mu| ∣v−μ∣。

数据集D \mathcal D D就是从真实分布D D D中采集的样本，自然会有如下结果：

y ( i ) = G ( x ( i ) ) ( x ( i ) , y ( i ) ) ∈ D y^{(i)} = \mathcal G(x^{(i)}) \quad (x^{(i)},y^{(i)}) \in \mathcal D y(i)=G(x(i))(x(i),y(i))∈D此时 v v v不再被描述为样本均值，而是描述为假设函数h ( x ) h(x) h(x)在 D \mathcal D D上误差的均值：

由于G ( x ( i ) ) = y ( i ) \mathcal G(x^{(i)}) = y^{(i)} G(x(i))=y(i)，也可看作是G ( x ) \mathcal G(x) G(x)和h ( x ) h(x) h(x)在D \mathcal D D上体现的差异的均值。

v = E i n ( h ) = 1 N ∑ i = 1 N [ h ( x ( i ) ) ≠ y ( i ) ] v = \mathbb E_{in}(h) = \frac{1}{N} \sum_{i=1}^N \left[h(x^{(i)}) \neq y^{(i)}\right] v=Ein​(h)=N1​i=1∑N​[h(x(i))=y(i)]同理， μ \mu μ被表示为基于 D D D中所有样本条件下，函数G ( x ) \mathcal G(x) G(x)和 h ( x ) h(x) h(x)在样本中体现差异的期望结果：

μ = E o u t ( h ) = E x ( i ) ∼ D [ h ( x ( i ) ) ≠ G ( x ( i ) ) ] \mu = \mathbb E_{out}(h) = \mathbb E_{x^{(i)} \sim D} \left[h(x^{(i)}) \neq \mathcal G(x^{(i)})\right] μ=Eout​(h)=Ex(i)∼D​[h(x(i))=G(x(i))]

从而得到新的不等式：

个人理解：E i n ( h ) \mathbb E_{in}(h) Ein​(h)和E o u t ( h ) \mathbb E_{out}(h) Eout​(h)之间的区别就是样本量的大小，其余没有区别。只不过将预测划分‘不准确’(误差)作为衡量指标进行描述。

P { ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ } ≤ 2 exp ⁡ ( − 2 ϵ 2 N ) \mathcal P \{|\mathbb E_{in}(h) - \mathbb E_{out}(h)| > \epsilon\} \leq 2\exp(-2\epsilon^2N) P{∣Ein​(h)−Eout​(h)∣>ϵ}≤2exp(−2ϵ2N)

此时我们发现，上述的不等式无论 E i n ( h ) \mathbb E_{in}(h) Ein​(h)还是 E o u t ( h ) \mathbb E_{out}(h) Eout​(h)，都有一个参考系的支撑： G ( x ) \mathcal G(x) G(x)。并且由于数据集D \mathcal D D是分布 D D D所描述全集的一个子集，那么必然有：如果通过优化假设函数h ( x ) h(x) h(x)，使得在数据集D \mathcal D D中的误差 E i n ( h ) \mathbb E_{in}(h) Ein​(h)减小，那么在全集内也必然使其误差 E o u t ( h ) \mathbb E_{out}(h) Eout​(h)减小。而 E o u t ( h ) \mathbb E_{out}(h) Eout​(h)就是我们想要的结果。这就是 PAC \text{PAC} PAC机器学习理论框架。

PAC \text{PAC} PAC

PAC(ProbablyApproximatelyCorrect) \text{PAC(Probably Approximately Correct)} PAC(ProbablyApproximatelyCorrect)，也就是概率近似正确——它通过两个不确定性的组合来描述一个客观事实：

E i n ( h ) , E o u t ( h ) \mathbb E_{in}(h),\mathbb E_{out}(h) Ein​(h),Eout​(h)分别作为在 D \mathcal D D和全集内与真实模型 G ( x ) \mathcal G(x) G(x)的误差，它们之间的近似关系由误差参数ϵ \epsilon ϵ描述：

∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ⇔ E i n ( h ) ≈ E o u t ( h ) |\mathbb E_{in}(h) - \mathbb E_{out}(h)| > \epsilon \Leftrightarrow \mathbb E_{in}(h) \approx \mathbb E_{out}(h) ∣Ein​(h)−Eout​(h)∣>ϵ⇔Ein​(h)≈Eout​(h)而这个近似关系的表达也是不确定的——使用概率的方式对这个近似关系本身的不确定性进行表达。随着数据集D \mathcal D D的样本量 N N N的增加，对应概率结果不断减小：

并且这个表达‘近似关系’的概率结果，我们并不能求出它的具体值，而仅仅是知道它的一个上界δ \delta δ。

P ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ≤ δ \mathcal P(|\mathbb E_{in}(h) - \mathbb E_{out}(h)| > \epsilon) \leq \delta P(∣Ein​(h)−Eout​(h)∣>ϵ)≤δ

并且既然是‘概率值’，无论δ \delta δ数值多小，它都存在发生的可能性。

引出新问题——霍夫丁不等式无法通过直接比较获取最优假设函数

继续观察 E i n ( h ) , E o u t ( h ) \mathbb E_{in}(h),\mathbb E_{out}(h) Ein​(h),Eout​(h)，如果它们等于零意味着什么：根据公式， E i n ( h ) = 0 \mathbb E_{in}(h) = 0 Ein​(h)=0自然意味着数据集 D \mathcal D D内的所有样本均被划分正确。即 h ( x ( i ) ) = y ( i ) , ( x ( i ) , y ( i ) ) ∈ D h(x^{(i)}) = y^{(i)},(x^{(i)},y^{(i)}) \in \mathcal D h(x(i))=y(i),(x(i),y(i))∈D；同理， E o u t ( h ) = 0 \mathbb E_{out}(h) = 0 Eout​(h)=0意味着分布 D D D所描述全集的样本内，所有样本均划分正确。也就是说，此时的 h ( x ) = G ( x ) h(x) = \mathcal G(x) h(x)=G(x)。

如果将 h h h视作一个变量，而 E i n ( h ) , E o u t ( h ) \mathbb E_{in}(h),\mathbb E_{out}(h) Ein​(h),Eout​(h)分别作为该变量的函数。那么从分布 D D D中独立采样出N N N个样本所组成的数据集称作 D N ( 1 ) \mathcal D_N^{(1)} DN(1)​，此时的 E i n ( h ) \mathbb E_{in}(h) Ein​(h)对 D N ( 1 ) \mathcal D_N^{(1)} DN(1)​进行描述，两函数的图像结果表示如下：

图像来源见下方链接，侵删，下同。其中D N ( 1 ) \mathcal D_N^{(1)} DN(1)​表示包含N N N个样本的1 1 1号数据集。

图中的 h ∗ h^* h∗和 G \mathcal G G分别描述了在数据集D N ( 1 ) \mathcal D_N^{(1)} DN(1)​和全集上的最优变量结果。

我们事先知道，只要分布 D D D是不变的，那么 G \mathcal G G所描述的变量值位置是不变的；其次，描述 E i n ( h ) \mathbb E_{in}(h) Ein​(h)的最优变量h ∗ h^* h∗不仅由变量 h h h控制，并且与数据集D \mathcal D D之间存在关联关系。这里使用的是数据集D N ( 1 ) \mathcal D_N^{(1)} DN(1)​，如果换成基于分布 D D D的另一个数据集D M ( 2 ) \mathcal D_M^{(2)} DM(2)​，最优变量h ∗ h^* h∗的位置也可能发生变化。

此时 E i n ( h ) , E o u t ( h ) \mathbb E_{in}(h),\mathbb E_{out}(h) Ein​(h),Eout​(h)已经表述出来，继续观察 ∣ E i n ( h ) − E o u t ( h ) ∣ |\mathbb E_{in}(h) - \mathbb E_{out}(h)| ∣Ein​(h)−Eout​(h)∣的图像结果以及该值与 ϵ \epsilon ϵ的关系：

实际上就是第一张图中阴影部分在 h h h轴上的体现，假设已经设定好了 ϵ \epsilon ϵ的范围，对应图中的红色阴影部分表示 ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ |\mathbb E_{in}(h) - \mathbb E_{out}(h)| > \epsilon ∣Ein​(h)−Eout​(h)∣>ϵ的结果；剩余的蓝色阴影部分则是 ∣ E i n ( h ) − E o u t ( h ) ∣ ≤ ϵ |\mathbb E_{in}(h) - \mathbb E_{out}(h)| \leq \epsilon ∣Ein​(h)−Eout​(h)∣≤ϵ的结果。

但概率值P ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) \mathcal P(|\mathbb E_{in}(h) - \mathbb E_{out}(h)| > \epsilon) P(∣Ein​(h)−Eout​(h)∣>ϵ)如何进行表示呢？是红色阴影面积比上整体阴影面积吗？并不是。这个概率描述的是：在分布 D D D独立采样产生的不同数据集内，相同 h h h产生的 ∣ E i n ( h ) − E o u t ( h ) ∣ |\mathbb E_{in}(h) - \mathbb E_{out}(h)| ∣Ein​(h)−Eout​(h)∣与 ϵ \epsilon ϵ比较，经过统计产生的概率结果。此时我们独立采样出一个包含 N N N个数据的新数据集D N ( 2 ) \mathcal D_N^{(2)} DN(2)​，其对应图像表示如下：

这里比较同一个h h h(红色矩形框)，统计其 ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ |\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon ∣Ein​(h)−Eout​(h)∣>ϵ的次数：

这里的j ⇒ ∞ j \Rightarrow \infty j⇒∞,因为可以从分布D D D中任意独立地进行采样。

I ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ∣ D N ( k ) = { 1 if ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ 0 Otherwise k = 1 , 2 , ⋯ , j \mathbb I(|\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon) |_{\mathcal D_N^{(k)}} = \begin{cases} 1 \quad \text{if } |\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon \\ 0 \quad \text{Otherwise} \end{cases} \quad k = 1,2,\cdots,j I(∣Ein​(h)−Eout​(h)∣>ϵ)∣DN(k)​​={1if∣Ein​(h)−Eout​(h)∣>ϵ0Otherwise​k=1,2,⋯,j

关于数据集D N ( 1 ) \mathcal D_{N}^{(1)} DN(1)​，其 ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ |\mathbb E_{in}(h) - \mathbb E_{out}(h)|>\epsilon ∣Ein​(h)−Eout​(h)∣>ϵ，返回结果1；关于数据集D N ( 2 ) \mathcal D_N^{(2)} DN(2)​，其 ∣ E i n ( h ) − E o u t ( h ) ∣ ≤ ϵ |\mathbb E_{in}(h) - \mathbb E_{out}(h)| \leq\epsilon ∣Ein​(h)−Eout​(h)∣≤ϵ，返回结果0；以此类推，最终可得到概率结果：

而这个概率结果是存在上界的。

另一个注意的点：这里所有采集的数据集合D N ( 1 ) , D N ( 2 ) , ⋯ , D N ( j ) \mathcal D_N^{(1)},\mathcal D_N^{(2)},\cdots,\mathcal D_{N}^{(j)} DN(1)​,DN(2)​,⋯,DN(j)​,它们都是有N N N个样本组成的集合。

P ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) = 1 j ∑ k = 1 j I ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ∣ D N ( k ) ≤ 2 exp ⁡ ( − 2 ϵ 2 N ) \mathcal P(|\mathbb E_{in}(h) - \mathbb E_{out}(h)|>\epsilon) = \frac{1}{j}\sum_{k=1}^{j}\mathbb I(|\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon) |_{\mathcal D_N^{(k)}} \leq 2 \exp(-2\epsilon^2N) P(∣Ein​(h)−Eout​(h)∣>ϵ)=j1​k=1∑j​I(∣Ein​(h)−Eout​(h)∣>ϵ)∣DN(k)​​≤2exp(−2ϵ2N)

至此，已经得到了这个概率值的表示，回顾假设函数h h h， h h h对于这个概率值产生什么样的影响 ? ? ?如果将 P ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) \mathcal P(|\mathbb E_{in}(h) - \mathbb E_{out}(h)| > \epsilon) P(∣Ein​(h)−Eout​(h)∣>ϵ)看做是关于h h h的函数。即：

f ( h ) = 1 j ∑ k = 1 j I ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ∣ D N ( k ) f(h) = \frac{1}{j}\sum_{k=1}^{j}\mathbb I(|\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon) |_{\mathcal D_N^{(k)}} f(h)=j1​k=1∑j​I(∣Ein​(h)−Eout​(h)∣>ϵ)∣DN(k)​​

关于 h h h和 f ( h ) f(h) f(h)的函数关系表示如下：

这仅是一个示意图，我们仅能确定 f ( G ) f(\mathcal G) f(G)。当 h ( x ) = G ( x ) h(x)=\mathcal G(x) h(x)=G(x)时，无论我们如何采集样本，都有 E i n ( h ) = E o u t ( h ) = 0 \mathbb E_{in}(h) = \mathbb E_{out}(h) = 0 Ein​(h)=Eout​(h)=0，从而 f ( h ) = 0 f(h) = 0 f(h)=0。但与此同时，无论 h h h产生的预测分布多么离谱，这个概率值f ( h ) f(h) f(h)均小于 2 exp ⁡ ( − 2 ϵ 2 N ) 2\exp(-2\epsilon^2N) 2exp(−2ϵ2N)。

并且根据上图，也可以看出，当 f ( h ) f(h) f(h)越小时，这意味着 ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ |\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon ∣Ein​(h)−Eout​(h)∣>ϵ这种不好的情况发生的次数更少，而对应的 h h h也越可靠：

∑ k = 1 j I ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ∣ D N ( k ) ⇓ \sum_{k=1}^{j}\mathbb I(|\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon) |_{\mathcal D_N^{(k)}} \Downarrow k=1∑j​I(∣Ein​(h)−Eout​(h)∣>ϵ)∣DN(k)​​⇓

相反，这引出一个新的问题：此时只能根据 PAC \text{PAC} PAC提出的思路，知道函数f ( h ) f(h) f(h)存在上界2 exp ⁡ ( − 2 ϵ 2 N ) 2\exp(-2\epsilon^2N) 2exp(−2ϵ2N)，对于f ( h ) f(h) f(h)的大小/ h h h的可靠程度我们是未知的。

例如下图中的两条曲线：

通过图像可以看出，数据集D N ( 1 ) \mathcal D_N^{(1)} DN(1)​对应学习出的最优模型h ∗ h^* h∗与数据集D N ( 2 ) \mathcal D_N^{(2)} DN(2)​对应学习出的最优模型h ∗ h^* h∗相比，后者要更优秀(因为 h ∗ h^* h∗距离 G \mathcal G G更近)，但真实情况是，我们并不知道 G \mathcal G G的具体位置是什么，导致无法进行比较。

总结一下：

利用霍夫丁不等式来实现机器学习是无法实现的：

关于真实模型 G \mathcal G G是未知的 ⇒ \Rightarrow ⇒ 无法通过假设函数h h h与 G \mathcal G G直接进行比较；如果抛开 G \mathcal G G不谈，仅仅对各假设函数h h h相互比较。即从所有可能的 h h h中挑出一个最优的 h h h。但是我们能够比较的仅仅是 E i n ( h ) \mathbb E_{in}(h) Ein​(h)， E o u t ( h ) \mathbb E_{out}(h) Eout​(h)因无法采出全部样本是无法求解的。即便找到了一个 E i n ( h ∗ ) = 0 \mathbb E_{in}(h^*) = 0 Ein​(h∗)=0，该 h ∗ h^* h∗与 G \mathcal G G的差距也是无法确定的。并且，由于已知的信息仅仅是一个上界，并且这个上界与 h h h自身无关。从而无法通过找出最小上界值的形式确定最优 h h h。

问题的解决方法

针对上面的问题，一种解决方法是：不去单个比较假设函数，而是通过对所有可能的假设函数h h h构建一个假设函数空间H \mathcal H H，并将其划分成若干个部分： { H 1 , H 2 , H 3 , ⋯ } \{\mathcal H_1,\mathcal H_2,\mathcal H_3,\cdots\} {H1​,H2​,H3​,⋯}，从而找到最优的函数空间部分，最终在最优部分中找到的假设函数可信度更高：

上图我们将假设函数空间划分出 3 3 3个子空间H 1 , H 2 , H 3 \mathcal H_1,\mathcal H_2,\mathcal H_3 H1​,H2​,H3​。分别在 D N ( 1 ) , D N ( 2 ) \mathcal D_N^{(1)},\mathcal D_N^{(2)} DN(1)​,DN(2)​数据集条件下，我们能够找到在 H 1 \mathcal H_1 H1​中 E i n ( h ) \mathbb E_{in}(h) Ein​(h)的最小值(蓝色点)；同理，我们也能够找到 H 2 , H 3 \mathcal H_2,\mathcal H_3 H2​,H3​中 E i n ( h ) \mathbb E_{in}(h) Ein​(h)的最小值(分别是橙色点和绿色点)。

相比之下， H 2 \mathcal H_2 H2​中的两个橙色点虽然不是最小值，但相比于蓝色点和绿色点，它们的值都比较小，并且很稳定。因而在 H 2 \mathcal H_2 H2​空间中找出一个优秀的h h h，其可信度是较高的。

如何让假设函数子空间之间进行比较呢 ? ? ?由于霍夫丁不等式只与数据集D N ( i ) ( i = 1 , 2 , ⋯ , j ) \mathcal D_N^{(i)}(i=1,2,\cdots,j) DN(i)​(i=1,2,⋯,j)的选择有关，这意味着 h h h自身也是一个随机变量，它和数据集对判定结果起到共同作用：

关于 ∣ E i n ( h j ) − E o u t ( h j ) ∣ |\mathbb E_{in}(h_j) - \mathbb E_{out}(h_j)| ∣Ein​(hj​)−Eout​(hj​)∣，我们可以将其看作是：在给定假设函数h j h_j hj​的条件下，关于数据集D N ( i ) \mathcal D_N^{(i)} DN(i)​的一个偏差结果。记作 Δ h j ( D N ( i ) ) \Delta_{h_j}(\mathcal D_N^{(i)}) Δhj​​(DN(i)​)；

但需要假设函数共同作用下的结果，同样将 h j h_j hj​作为随机变量放入Δ \Delta Δ函数中：

Δ h j ( D N ( i ) ) ⇒ Δ ( h j , D N ( i ) ) \Delta_{h_j}(\mathcal D_N^{(i)}) \Rightarrow \Delta(h_j,\mathcal D_N^{(i)}) Δhj​​(DN(i)​)⇒Δ(hj​,DN(i)​)

同理，此时我们的样本不再仅仅是 D N ( i ) ∈ D \mathcal D_N^{(i)} \in D DN(i)​∈D(全集)，而是数据集和假设函数相绑定的笛卡尔积结果：

D N ( i ) ∈ D ⇒ ⟨ D N ( i ) , h j ⟩ ∈ D × H \mathcal D_N^{(i)} \in D \Rightarrow \langle\mathcal D_N^{(i)},h_j\rangle \in \mathcal D \times \mathcal H DN(i)​∈D⇒⟨DN(i)​,hj​⟩∈D×H

这种方式对原始的 h h h的选择存在什么样的变化 ? ? ?

原始做法通过 f ( h ) f(h) f(h)进行衡量， f ( h ) f(h) f(h)越小， h h h越优秀；

f ( h ) = 1 j ∑ k = 1 j I ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ∣ D N ( k ) f(h) = \frac{1}{j}\sum_{k=1}^{j}\mathbb I(|\mathbb E_{in}(h) - \mathbb E_{out}(h) |>\epsilon) |_{\mathcal D_N^{(k)}} f(h)=j1​k=1∑j​I(∣Ein​(h)−Eout​(h)∣>ϵ)∣DN(k)​​现在我们不将目光放在某个假设函数h h h上，而是某一假设函数子空间 H i ∈ H \mathcal H_i \in \mathcal H Hi​∈H，如何衡量一个假设函数子空间的好坏，就需要将该空间内的所有假设函数h h h与各数据集D N ( i ) \mathcal D_N^{(i)} DN(i)​各计算一次，从而挑出满足条件( > ϵ >\epsilon >ϵ)的结果并进行比值：

P H = ∑ ⟨ D N ( i ) , h j ⟩ ∈ D × H I ( ∣ E i n ( h j ) − E o u t ( h j ) ∣ > ϵ ) ∣ D N ( i ) ∣ D × H ∣ = ∑ h j ∈ H ∑ D N ( i ) ∈ D [ I ( ∣ E i n ( h j ) − E o u t ( h j ) ∣ > ϵ ) ∣ D N ( i ) ] ∣ D × H ∣ \begin{aligned} \mathcal P_{\mathcal H} & = \frac{\sum_{\left\langle\mathcal D_N^{(i)},h_j\right\rangle \in \mathcal D \times \mathcal H} \mathbb I(|\mathbb E_{in}(h_j) - \mathbb E_{out}(h_j)| > \epsilon)|_{\mathcal D_N^{(i)}}}{|\mathcal D \times \mathcal H|} \\ & = \frac{\sum_{h_j \in \mathcal H}\sum_{\mathcal D_N^{(i)}\in D} \left[\mathbb I(|\mathbb E_{in}(h_j) - \mathbb E_{out}(h_j)| > \epsilon)|_{\mathcal D_N^{(i)}}\right]}{|\mathcal D \times \mathcal H|} \end{aligned} PH​​=∣D×H∣∑⟨DN(i)​,hj​⟩∈D×H​I(∣Ein​(hj​)−Eout​(hj​)∣>ϵ)∣DN(i)​​​=∣D×H∣∑hj​∈H​∑DN(i)​∈D​[I(∣Ein​(hj​)−Eout​(hj​)∣>ϵ)∣DN(i)​​]​​

新方法对于霍夫丁不等式的约束证明

继续观察上式，该式子是否能够受到霍夫丁不等式的约束 ? ? ?

从极端角度观察的话，如果基于某一数据集条件下，只要存在一个假设函数h ′ h' h′，使其 ∣ E i n ( h ′ ) − E o u t ( h ′ ) ∣ > ϵ |\mathbb E_{in}(h') - \mathbb E_{out}(h')| > \epsilon ∣Ein​(h′)−Eout​(h′)∣>ϵ，那么我们就武断地将所有 h ∈ H h \in \mathcal H h∈H在该数据集下都有 ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ |\mathbb E_{in}(h) - \mathbb E_{out}(h)| > \epsilon ∣Ein​(h)−Eout​(h)∣>ϵ。基于这个假设，必然有：

P H ≤ ∣ H ∣ ⋅ ∑ D N ( i ) ∈ D I ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ∣ D N ( i ) ∣ D × H ∣ ( h ∈ H ) = ∑ D N ( i ) ∈ D I ( ∣ E i n ( h ) − E o u t ( h ) ∣ > ϵ ) ∣ D N ( i ) ∣ D ∣ ( h ∈ H ) \begin{aligned} \mathcal P_{\mathcal H} & \leq \frac{|\mathcal H| \cdot \sum_{\mathcal D_N^{(i)} \in D}\mathbb I(|\mathbb E_{in}(h) - \mathbb E_{out}(h)| >\epsilon)|_{\mathcal D_N^{(i)}}}{|\mathcal D \times \mathcal H|} \quad (h \in \mathcal H) \\ & = \frac{\sum_{\mathcal D_N^{(i)} \in D}\mathbb I(|\mathbb E_{in}(h) - \mathbb E_{out}(h)| >\epsilon)|_{\mathcal D_N^{(i)}}}{|\mathcal D|} \quad(h \in \mathcal H) \end{aligned} PH​​≤∣D×H∣∣H∣⋅∑DN(i)​∈D​I(∣Ein​(h)−Eout​(h)∣>ϵ)∣DN(i)​​​(h∈H)=∣D∣∑DN(i)​∈D​I(∣Ein​(h)−Eout​(h)∣>ϵ)∣DN(i)​​​(h∈H)​将分子展开，得到如下结果：由于武断的假设，导致上式结果和h h h无关了，将数据集D N ( i ) \mathcal D_N^{(i)} DN(i)​划分成两种类型：> ϵ > \epsilon >ϵ和< ϵ < \epsilon <ϵ两种。从分布D D D采样的过程中，其产生的数据集合D N ( 1 ) , D N ( 2 ) , ⋯ , D N ( j ) \mathcal D_N^{(1)},\mathcal D_N^{(2)},\cdots,\mathcal D_{N}^{(j)} DN(1)​,DN(2)​,⋯,DN(j)​内部的样本中必然存在重复样本。在展开过程中忽略掉这个重复，因而下面的式子中是≤ \leq ≤，只有在D N ( i ) ( i = 1 , 2 , ⋯ , j ) \mathcal D_N^{(i)}(i=1,2,\cdots,j) DN(i)​(i=1,2,⋯,j)中均不存在重复样本时，才会取等。但这种采样结果概率可以忽略不计。

P H ≤ [ ∑ D N ( i ) ∈ D I ( ∣ E i n ( h 1 ) − E o u t ( h 1 ) ∣ > ϵ ) + ⋯ + ∑ D N ( i ) ∈ D I ( ∣ E i n ( h j ) − E o u t ( h j ) ∣ > ϵ ) ] ∣ D ∣ = P h 1 + ⋯ + P h j ≤ ∣ H ∣ ⋅ 2 exp ⁡ ( − 2 ϵ 2 N ) \begin{aligned} \mathcal P_{\mathcal H} & \leq \frac{\left[\sum_{\mathcal D_N^{(i)} \in D} \mathbb I(|\mathbb E_{in}(h_1) - \mathbb E_{out}(h_1)| > \epsilon) + \cdots + \sum_{\mathcal D_N^{(i)} \in D} \mathbb I(|\mathbb E_{in}(h_j) - \mathbb E_{out}(h_j)| > \epsilon)\right]}{|\mathcal D|} \\ & = \mathcal P_{h_1} + \cdots + \mathcal P_{h_j} \\ & \leq |\mathcal H| \cdot 2\exp(-2\epsilon^2N) \end{aligned} PH​​≤∣D∣[∑DN(i)​∈D​I(∣Ein​(h1​)−Eout​(h1​)∣>ϵ)+⋯+∑DN(i)​∈D​I(∣Ein​(hj​)−Eout​(hj​)∣>ϵ)]​=Ph1​​+⋯+Phj​​≤∣H∣⋅2exp(−2ϵ2N)​

也就是说，通过对假设函数空间为单位进行比较时，同样在霍夫丁不等式中得到证明，存在上界。

总结

上述所描述的新方法主要分为两个步骤：

从完整的假设函数空间H \mathcal H H中选择一个比较优秀的假设函数子空间H i \mathcal H_i Hi​；从 H i \mathcal H_i Hi​中再挑选假设函数h h h。

这种方式贯穿在机器学习的过程中，关于机器学习的三要素：模型，策略(损失函数)，算法，模型的选择相当于函数子空间的选择，例如：线性模型。而策略相当于选择具体假设函数h h h的判别方法。

例如在线性模型的基础上，基于错误驱动的感知机算法，线性判别分析，支持向量机等等。

相关参考：

霍夫丁不等式(Hoeffding‘s Inequality)的证明

VC维是如何推导出来的？为什么说它是机器学习理论最重要的发明?