上一期回顾机器学习100天|Day1数据预处理100天机器学习|Day2简单线性回归分析100天机器学习|Day3多元线性回归100天机器学习|Day4-6LogisticRegression100天机器学习|Day7K-NN100天机器学习|Day8逻辑回归数学原理100天机器学习|Day9-12Supportvectormachine100天机器学习|Day11to实现KNN100天搞定机器学习|Day13-14SVM实现机器学习100天|Day15朴素贝叶斯机器学习100天|Day16SVM通过内核技术搞定机器学习100天|Day17-18神奇逻辑回归100天|第19-20天加州理工学院公开课：机器学习和数据挖掘第17天，Avik-Jain第22天完成由YaserAbu-Mostafa教授的加州理工学院机器学习课程-CS156的课程2。1HoeffdingInequality假设有一个罐子，里面装满了橙色和绿色的球，为了估计罐子里橙色和绿色的比例，我们随机抓了一把球，称为样本：其中，让罐子里的橙球是μ，橙球在样本中的比例是v，样本的大小是N，我们有实数分布μ，样本分布v和样本分布v之间的差异容差是ε，并且以下不等式成立：即概率存在上限。只要我们保证样本量N很大，就可以让“μ和v相差很大”的概率很小。2对于假设函数h的情况如果我们的假设函数h已经确定了，那么我们就可以将我们的问题映射到jar模型中：每个球代表一个输入x，橙色代表h的预测值和真实值functionf不一样，green的意思是一样的，就是：那么罐子里所有的球都是可能的输入x，抓到的一把球代表我们的训练集（注意！这里其实是一个假设：我们的训练集和test集合都是由相同的未知概率分布P生成的，即来自同一个jar)，那么橙色球的比例μ代表我们的假设函数h在真实输入空间中的预测误差率Eout(我们最终的想减少），v表示我们在训练集中的预测误差率Ein（我们的算法可以最小化），由Hoeffding不等式，我们可以得到：也就是只要我们能够保证训练集N的量足够大,可以保证th的错误率e训练集非常接近真实的预测错误率。3对于h的数量有限的情况，我们在上一节中证明了对于给定的假设函数h，只要训练集足够大，我们就可以保证其对训练集的预测效果和真实的预测效果有很大概率接近。但是，我们只能保证它们的预测效果接近，或者预测效果都不好？我们的机器学习算法是在假设空间中选择一个h，让这个h在训练集上的错误率很小，那么这个h在整个输入空间上的错误率是不是很小呢？本节我们要证明的是，当假设空间只有有限的h时，只要训练集N足够大，这也是大概率成立的。首先，我们看这张表：首先，对于给定的h，我们可以定义一个概念：“badtrainingset”（对应表中红色的bad）。所谓badtrainingset就是h的Ein和真实的Eout在这个训练集上的差异超过了我们定义的公差ε。Hoeffding不等式保证对于给定的h（表中的一行），选择不良训练集的概率非常低。然后，对于假设空间中有M个候选的h，我们重新定义了“badtrainingset”的概念（对应表中橙色的bad），只要对任意h都是bad，那么就是一个bad。那么我们选择一个橙色坏训练集的概率可以推导出如下：由于M是有限的，只要训练集N足够大，我们选择一个坏训练集的概率还是很小的。换句话说，我们的训练集很可能是一个很好的训练集，h都在上面很好。只要算法选择了一个在训练集上表现良好的h，那么它的预测能力在PAC中也是不错的。.即存在不等式：因此，机器学习过程如下：（这里多出来的橙色部分表示训练集和测试集是由相同的概率分布生成的）因此，当h的个数有限时，机器学习算法确实可以学到一些东西。我们稍后会讨论当假设空间中存在无限大的h时，机器学习是否仍然有效。在上一节中，我们证明了当假设空间的大小为M时，可以得到概率的上界：即只要训练数据量N足够大，那么训练上的Ein集和真实预测错误率Eout是PAC（largeprobability）接近的。然而，我们的上述理论仅在假设空间的大小是有限的情况下才有效。如果假定空间是无限的，则右边概率的上限变为无限大。事实上，右边的边界是一个比较弱的边界。在本节中，我们将找到一个更强的边界来证明我们的机器学习算法对于假设空间无限大的情况仍然可行。我们将用一个m代替大M，并证明当假设空间有一个断点时m有一个多项式级上界N。2增长函数对于给定的一组训练集x1,x2,...,xN。定义函数H(x1,x2,...,xN)，表示在假设空间H中使用假设函数h可以将多少种圆叉组合分为训练集（即有多少种的二分法，最大值为2^N)。例如，假设空间是平面上的所有线，训练数据集是平面上的N个点，则有：当N=1时，有2种划分方式：当N=2时，有4种划分方式:N=3时，有8种划分方式：当N=4时，有14种划分方式（因为有两种不能用直线划分）：…………另外，划分的数量是相关的到训练集，（比如N=3，如果三个点共线，则不能生成2种划分，所以只有6种划分，而不是8种）：为了消除对训练数据，我们定义增长函数：因此，增长函数的含义是：利用假设空间H，最多有多少种划分训练集（大小N）的方法。增长函数只与两个因素有关：训练集的大小N和假设空间的类型H。下面列出几个假设空间的增长函数：3断点这里定义断点。所谓断点是指当训练集的大小为k时，增长函数满足：即训练集不能被假设空间打散的容量。很容易想到，如果k是一个断点，那么k+1，k+2....也是一个断点。4增长函数的上界由于第一个断点会限制后续的增长函数，所以我们定义上界函数B(N,k)，即在第一个断点为k的限制下，增长functionmH(N)的最大可能值：现在我们开始推导这个上界函数的上界：首先，B(N,k)生成的Dichotomy可以分为两种，一种是第N-1个点是成对的，一个是前N-1个点只出现一次：所以显然有：那么，对于所有前N-1个点在这里产生的情况：显然这里的数是α+β，显然,之前N-1个点生成的Dichotomy的个数仍然受限于断点为k的前提,所以:那么,对于前N-1个成对出现的Dichotomy点:我们可以说第一个这里的N-1个点数会限制在第k-1个断点。反证：如果这里有k-1个点可以被打散，那么我们可以通过组合我们的第N个点找到k个可以被打散的点，这与B(N,k)的定义相矛盾。因此，我们有：结合上文，我们有：利用这个递推关系和边界情况，我们可以简单地用数学归纳法证明它（实际上可以证明下面是一个等号关系）：因此，增长函数在多项式级别有一个上限。5VC-Bound这里我们不涉及严格的数学证明，而是使用一种流行的方法来引出VC-Bound。这就是如何用m替换M。所以我们得到机器学习问题的PAC概率的上界，称为VC-Bound：所以我们得到一个更强的边界，当右边的增长函数有一个断点时，它的上界是N^k-1级是的，只要我们的N足够大，“存在一个让坏情况发生的假设函数h”的概率就会很小。6结论结论：当假设空间的增长函数有断点时，只要N足够大，我们就可以PAC保证训练集是一个好的训练集，h以上的Ein和Eout都是近似的，并且算法可以对这些h做出自由选择。也就是说，机器学习算法确实可以工作。通俗地说，机器学习起作用的条件：1良好的假设空间。使增长函数有一个断点。2个很好的训练数据集。使N足够大。3个好算法。允许我们选择在训练集上表现良好的h。4祝你好运。因为还是有一定的小概率会发生不好的事情。END本文转自：https://www.cnblogs.com/coldyan/
