机器学习基石笔记——学习的可行性

这节课主要讲的就是机器学习的可行性，讨论问题是否能用机器学习来解决

1.NFL

NFL定理表明没有一个机器学习算法是可以在任何领域总是产生最准确的学习器。我们平常所说的一个学习算法比另一个算法更“优越”，效果更好，只针对特定的问题，特定的先验信息，数据分布，训练样本的数目，代价函数或奖励函数。

2.联系机器学习

这里我们引入两个值$E_{in}(h)$Ein​(h)和$E_{out}(h)$Eout​(h)。$E_{in}(h)$Ein​(h)表示在抽样样本中，$h(x)$h(x)与$y_n$yn​不相等的概率；$E_{out}(h)$Eout​(h)表示实际所有样本中，$h(x)与f(x)$h(x)与f(x)不相等的概率是多少。

注：这里的BAD表示是$E_{in}(h)$和$E_{out}(h)$相差很远。

从这里我们可以看出，不同的数据集$D_n$Dn​，对应不同的hypothesis（h1,h2,…），有可能成为Bad Data也就是$E_{in}(h)$Ein​(h)和$E_{out}(h)$Eout​(h)相差很远，那么$D_n$Dn​就是Bad Data。只有当$D_n$Dn​在所有的hypothesis上都是好的数据，才说明$D_n$Dn​不是Bad Data，可以*选择演算法A进行建模。那么根据霍夫不等式。Bad Data的上界可表示为练级（union bound）的形式。

其中M是hypothesis的个数，N是样本D的数量，$\epsilon$ϵ是参数，exp表示以e为底的指数函数。根据霍夫不等式，当M有限，且N足够大的时候，Bad Data出现的概率就更低了，即能保证D对于所有的h都有$E_{in}(h) \approx E_{out}(h)$Ein​(h)≈Eout​(h)，满足PAC，演算法A的选择不受限制，那么满足这种情况，我们就可以和之前一样选择一个演算法A，选择使$E_{in}(h)$Ein​(h)和$E_{out}(h)$Eout​(h)最小的g，保证$g \approx f$g≈f，就会有不错的泛化能力。

这里我们来总结一下整个过程，根据我们的霍夫不等式，证明出对于某个h，当N足够大的时候，$E_{in}(h)$Ein​(h)和$E_{out}(h)$Eout​(h)是PAC的，对于h的个数的问题，当h的个数M是有限的时候同样能满足$E_{in}(h)$Ein​(h)和$E_{out}(h)$Eout​(h)是PAC的，用简单的例子来阐述，如果我们连续抛掷100次硬币，我们现在估算每次抛掷的正反面情况，我们首先抽选出5次的抛掷结果，结果显示五次都是正面，那么我们能根据这个结果推算出100次都是正面吗，这显然是不太合理的，也就是我们的选择的5次可能就是Bad Data，所以我们要尽可能多的选择抽样个数，可以选择20个，甚至更多，也就是N的数量，保证N足够大，h的数量有限，这样我们对这20个的估算结果就可以推演到100个上，这样就能保证我们的准确性很高。
这样就能保证我们的准确性很高。
这节课老师讲的可能有点稍微的绕，但是机器学习就是一门非常严谨的关于数学的学科，必须要按照数学的思维去，阐述这样一个过程。