Coursera台大机器学习课程笔记4 -- Training versus Testing

 这节的主题感觉和training,testing关系不是很大,其根本线索在于铺垫并求解一个问题:
 
 为什么算法PLA可以正确的work?因为前面的知识告诉我们,只有当假设的个数有限的时候,我们才能比较确认我们得到坏的数据集的概率比较低,也就是说算法得出的假设和最佳假设在全局表现相同(错误率相等),可是PLA的假设是平面上的直线,不是无数个么?为什么可以正常泛化?
 
为解释这个问题,有了这节以及下面几节的课程
 可以看到这个问题其实很重要,因为这是我们理解机器为啥能学习的关键一步,因为很多机器学习算法的假设看似都是无限的。下面这个图给出了理解机器为啥能学习的关键:
满足假设个数有限,采样数据足够大是算法泛化能力强大与否的关键,而Ein足够小是保证算法正确的前提。即,机器学习算法的终极目标是找到泛化能力强的错误率低的假设
Coursera台大机器学习课程笔记4 -- Training versus Testing
Training的目的是保证Ein足够小,Test则是确认Ein可以和Eout相同,即泛化效果好
Coursera台大机器学习课程笔记4 -- Training versus Testing
对于M,其对机器学习算法的影响可以理解为,如果M小,泛化能力强,但是选择太少,不一定能找到Ein足够小的假设;如果M大,选择多,有很大概率找到好的假设,但是得到坏数据的概率也相应的增加了。所以,M的大小很关键。既不能小也不能大,那么对于看似无穷大的M的PLA该怎么解释?
Coursera台大机器学习课程笔记4 -- Training versus Testing
 
首先回忆下M是怎么计算出来的,
Coursera台大机器学习课程笔记4 -- Training versus Testing
问题的关键在于不等式的最后一步,是取的Union bound,也就是假设各个假设之间没有交集,这是最坏的情况,可是实际上往往不是如此,很多情况下,都是有交集的,也就是说M实际上没那么大。
Coursera台大机器学习课程笔记4 -- Training versus Testing
那么就会想,什么样的假设有交集?当然是类似的,也就是错误率相同的,分类情况相同的。由此引入Dichotomy的概念。
Coursera台大机器学习课程笔记4 -- Training versus Testing
  上图中提到的dichotomy实际上指的是,能够得出不同X分类的假设的个数。例子是对全体直线,假设数据集大小是N,那么其实最多dichotomy就是2^N,而不是前面说的无限个。这个概念对证明M其实不大的作用不是很大,真正有作用的是成长函数,及M的上线。
Coursera台大机器学习课程笔记4 -- Training versus Testing
  成长函数,则是值最大的Dichotomy。
Coursera台大机器学习课程笔记4 -- Training versus Testing
  通过计算4种不同机器学习问题的Growth Function,发现其实它不是2^N,而是会比它小,那么如果M可以用Growth Function 替代,那么就有希望了。
Coursera台大机器学习课程笔记4 -- Training versus Testing
  Break Point: 对特定假设函数集合,假设数据集的个数是N,那么使得数据集其中k个数据的所有种类的dichotomy都不能被shattered,即为一个break point;
Coursera台大机器学习课程笔记4 -- Training versus Testing
  那么很明显的一个性质(通过数学归纳法),如果k为break point,那么k+1,k+2,。。。等之后所有新加入的数据都为break point
Coursera台大机器学习课程笔记4 -- Training versus Testing
  可以想象得到,M并不是无限的,而是由Growth Function决定的,如果它是多项式级别的话,可以认为机器是可以学习的。
上一篇:Maven 部署说明


下一篇:linux之getopt 函数(转)