林轩田老师-机器学习基石学习笔记6

2017/11/09 learning note 共 1308 字,约 4 分钟

这一讲数学的成份非常浓,但是中心思想还是为了希望证明机器学习的可行性条件。其中第五讲中提出的2D perceptrons的成长函数mH(N)是多项式级别的猜想,就是本次课的重点内容。


break point是k,数据量是N

成长函数有着如下几个值的规律:

  N=1时,mH(N)=2

N=2时,由break point2知任意两点都不能被shatteredshatter的意思是对N个点,能够分解为2Ndichotomies),所以mH(N)最大值只能是3

N=3时,简单绘图分析可得其mH(N)=4,即最多只有4dichotomies

所以,我们发现当N>k时,break point限制了mH(N)值的大小,也就是说影响成长函数mH(N)的因素主要有两个:

  • 数据集N
  • break point k

这个时候我们的目标就是


现在,我们引入一个新的函数:bounding functionB(N,k)

Bound Function指的是当break pointk的时候,成长函数mH(N)的潜在最大值。也就是说B(N,k)mH(N)的偏上限,对应mH(N)最多有多少种dichotomy。那么,我们新的目标就是证明

B(N,k)≤poly(N)

  • k=1时,B(N,1)==1
  • N < k时,易得到B(N,k)=2N
  • N = k时,此时N是第一次出现不能被shatter的值,所以最多只能有2N−1dichotomies,则B(N,k)=2N−1

下面要用到一点代数的数学技巧:


这个是B(4,3)的11组,我们将右边的橙色分成两组,根据x4的不同,紫色就一组,这样假设B(4,3)=2α+β


接着根据已知的开始往之前的结论靠:

左图根据之前的定义是α+β,而刚刚好是B(3,3)的,即α+βB(3,3)

而再根据下图:


此处得到的结论是αB(3,2)


由此就得出了之前那个表格的递推式子:

这个式子是对上述整个过程的结论性总结

得到的结论是,对于2D perceptronsbreak pointk=4mH(N)的上界是Nk−1。推广一下,也就是说,如果能找到一个模型的break point,且是有限大的,那么就能推断出其成长函数mH(N)有界。

之后的16分钟的课程,老师将hoeffding不等式融入进来,在这里,我觉得并不是我们机器学习的重点,证明的结论是:

通过重新因为数据的存在得到的Ein的新表达方式替换掉Eout,(Eout removed by verification with ghost data)

之后用mH(2N)去计算重复的不好的hound(之前有提过)

最后的最后带入到hoeffding不等式进行推演得出:


现在2D perceptronsbreak point是4,成长函数mH(N)=O(N3)。所以2D perceptrons是可以进行机器学习的

只要找到hypothesis能让Ein≈0,就能保证EinEout

最终终于证明了,只要breakpoint存在,机器学习就是可行的。



</p>

文档信息

Search

    Table of Contents