机器学习——Hoeffding不等式

Posted on Edited on In

这次用霍夫丁不等式来证明学习的可行性。首先要说明一个定理，叫做“No Free Lunch”定理。如果真是需要预测的值是完全随机的情况下，我们无论最后建立一个什么样的模型，误差期望都是一致的。这样学习似乎是不可行的。但是实际上，事物都有自己的规律。我们可以套用霍夫丁不等式来说明，在某个验证集上这个模型的准确率是p，那么在总体上它预测的实际准确率很大可能与p是相差不大的（Probably Approximately Correct）。

Hoeffding不等式：P[ν−υ|>ϵ]≤2e−2ϵ2NP[\nu - \upsilon|> \epsilon ] \leq 2 e^{-2\epsilon ^2N}

其中ν\nu是我们测的期望，而υ\upsilon是真实期望，这是未知的，N是测试抽取的样本数量，而ϵ\epsilon是我们可以容忍的误差值，因此实际上也就是υ∈[ν−ϵ,ν+ϵ]\upsilon ∈ [\nu - \epsilon , \nu + \epsilon]的概率是大于等于2e−2ϵ2N2 e^{-2\epsilon ^2N}的，也就是置信区间与置信度的关系。

因此霍夫丁不等式对独立随机变量的和与其期望值偏差的概率上限。

从另一个简单的例子来说：假如我们有一个罐子里装了红球和绿球，我们想要测的是红球的占比。每次取出N个球，则这N个球中红球占比为ν\nu，而总体红球占比为υ\upsilon，我们假设可以接受的误差范围为ϵ\epsilon，那么这几个量满足霍夫丁不等式。总体球中取出N个有m中不同的组合，而这些组合中红球占比误差很大的组合占了所有组合的比重是小于2e−2ϵ2N2 e^{-2\epsilon ^2N}的。而这些误差很大的样本组合就是所谓的Bad Data。因为从它测出来的值与实际值偏差很大。

从另一方面来讲，如果我们测试的数目足够多，依然很有可能选到错误样本。就像你我是天才的概率很小，但这个世界总会出现天才。用霍夫丁不等式来说，假如我们测试了t次，那么出现一次bad data 的概率是小于2te−2ϵ2N2te^{-2\epsilon ^2N}，为什么可以简单相加？如下：

假如一件事发生的概率是p，那么n次它至少发生一次的概率是1−(1−p)n1-(1-p)^n。

令 g(p)=1−(1−p)n−np,g′(p)=n(1−p)n−1−n=n[(1−p)n−1−1];g(p) = 1- (1-p)^n - np, g'(p) = n(1-p)^{n-1} - n = n[(1-p)^{n-1} - 1]; 令g′(p)=0g'(p) = 0,则p=0;p = 0; 当p∈[0,1]∈[0,1]时候， g′(p)≤0,g(0)=0g'(p) \leq 0, g(0) = 0,所以g(p)≤0g(p)\leq 0; 因此 1−(1−p)n≤np1- (1-p)^n \leq np

上述是一个简单的证明，而实际上独立随机变量至少发生一件的概率是小于它们各自发生的概率之和的。在概率论中这相当于是个常识。

应用到机器学习当中，如果H是有限的，也就是我们可选假说个数是有限的，只要选取足够大的测试样本量（Hoeffding不等式中的N足够大），出现错误估计的概率依然是非常小的，该test dataset有很大的概率对每个假说都能正确评估它在总体样本上的性能，因此我们可以选择一个表现最好的来当做g，它对大多数样本都会使用，相比之下也就更接近f。

这就说明学习是可行的。

这里还有个问题：如果H的个数是无限的呢？