机器学习基石第五节 学习笔记

Training versus Testing



先来看两个主要问题：



所以就有了一个问题：



以dichotomies H（X1，X2...）的大小取代M，以此选定M的大小



增长函数 Growth Function



polynomial 多项式

exponential 指数

perceptron 感知器



总结

这节的主题感觉和training，testing关系不是很大，其根本线索在于铺垫并求解一个问题：



为什么算法PLA可以正确的work？因为前面的知识告诉我们，只有当假设的个数有限的时候，我们才能比较确认我们得到坏的数据集的概率比较低，也就是说算法得出的假设和最佳假设在全局表现相同（错误率相等），可是PLA的假设是平面上的直线，不是无数个么？为什么可以正常泛化？



增长函数（growth function）、对分（dichotomy）、打散（shattering）和断点（break point）



1.增长函数



增长函数表示假设空间H对m个示例所能赋予标记的最大可能结果数。



比如说现在数据集有两个数据点，考虑一种二分类的情况，可以将其分类成A或者B，则可能的值有：AA、AB、BA和BB，所以这里增长函数的值为4.



增长函数值越大则假设空间H的表示能力越强，复杂度也越高，学习任务的适应能力越强。不过尽管H中可以有无穷多的假设h，但是增长函数却不是无穷大的：对于m个示例的数据集，最多只能有2^m 个标记结果，而且很多情况下也达不到2^m的情况。



2.对分



对于二分类问题来说，H中的假设对D中m个示例赋予标记的每种可能结果称为对D的一种对分（dichotomy）。对分也是增长函数的一种上限。

3.打散



打散指的是假设空间H能实现数据集D上全部示例的对分，即增长函数=2^m 但是认识到不打散是什么则更加重要——有些情况下H的增长函数不可以达到对应的2^m值，比如说在二维实平面上的线性划分情况中，以下的情况就不可以线性可分（也就是说不能算作赋予标记的结果）：



虽然图画的非常直击灵魂，但是你应该可以体会到这种情况下二维平面的线性分类器是不可以给上面的情况分类的2^4=16种对分中至少有一种不能被线性划分实现 ）



4.VC维--Vapink-Chervonenkis Dimension



在上面那个4个点的图中，因为4个点的情况下以及不能做到对分，所以二维实平面上所有线性划分构成的假设空间H的VC维为3.

5.Break Point



在一些教课书中并没有提出Break Point的概念，这是林轩田《机器学习基石》公开课里的一种辅助概念。现在简单说一下break point的意义——我们希望假设空间H的增长函数越小越好（这样子假设空间比较简单），或者至少不要增长的太快——如果按照2^m 这种趋势增长那简直是没天理了。上面说道了，随着m的增大，一定会出现一个m使假设空间无法shatter（打散）。这种不满足2^m的情况说明增长函数从这个点开始变缓了，是一个可喜可贺的重大突破，所以我们把第一个不满足shatter的m值称为break point（这里翻译成突破点）



给个不啰嗦的定义——



If no k inputs can be shattered by H , call k a break point for H .



从这个定义上看某个假设空间H的VC维数就是最大的非break point值，也就是break point-1.