台湾大学机器学习——课程笔记(5~8)

从这里开始有所深入,会涉及到很多数学公式的推倒,有一定的难度,也难免费心,有的部分需要反复多看几次。

————————————————————————————————

第五章:

5-1训练和测试的过程到底有什么不一样

Learning在某些情况下是可行的
为什么机器可以学到东西?
Learning流程图:
如果hypothesis不是很大,Ein和Eout就可以很相近
选一个Ein最低的,如果很接近0的话,那么Eout也可以很接近0,这样我们就达到了Learnig的效果
必须保证:Ein要很接近0
两个核心问题:要保证,拿一个新的资料去验证我们已经学习过的模型,可以保持一个比较吻合的状态
这里我们把learning拆成了两个问题:
1、Ein和Eout到底会不会接近
2、有连接的话,如何让Ein变得越小越好

问:M(hypothesis的大小)和这两个问题有什么关系
1、M相对比较小:选择太少了,但是坏事情发生的几率也可以很小
2、M相对比较大:选择多了,但是坏事情发生的几率也增加了
结论:M很重要,选择正确的M是与我们Learning的效果有关系
无限多的M显然是不好的
我们要想办法解决无限大的M到底发生什么事
我们要把M换成有限的数量(不一定可以换)
如果可以换的话,我们就可以用m(一个有限的数量)来替代M
m和M有很类似的角色,来告诉我们未来该怎么选择hypothesis
目标:有学习的效果
5-2 M是如何推倒来的
union bound连级
问题:当我们加无限多个项的时候,有可能就会跑去无限大的数字去
这个bound到底出了什么问题?
原理:坏事情不太会重叠
若我们今天有两个很接近的hypothesis,他的Ein和Eout就会很接近
那么坏事情就会很接近,叠起来,可是我们使用union bound的时候,我们没有考虑叠加的情况,所以导致我们无法处理无限大的情况
解决:我们要找出重叠的部分
我们能不能把无限多的hypothesis分类,然后去找哪些部分有重叠。
只有一个点的情况:这直接上只有两种线,一种说x1是圈圈,另一种说x1是叉叉
有两个点的情况:有四种线
有三个点的情况:八种线
若把三个点放在同一条线上:只有六种线

四个点:14种(最多)
用有限的数字取代N,当你的N够大的时候,坏事发生的几率会很接近0,
Ein和Eout很接近,可以说学习成功了
5-3 
hypothesis和dichotomy的区别:
D是对特定动作的区别
H:可能有无线多条
D:代表有几种不一样的组合(最多就是2的n次方那么多种)
想要移除对x的依赖
mh(将要取代M,与hypothesis有关)
我们到底能不能写出函数
设定一个门槛值Positive Ray:决定了hypothesis
可以切出多少种不一样的dichotomy:N+1
用竖线切出N+1个区块
想象hypothesis是一维的输入 ->Positive Interval
成长函数:
 5-4 Break Point
我们想要用m取代M
我们的成长函数到底是多项式,还是指数?
找出成长函数里面第一个看起来有希望的点,这个点就是Break Point
convex sets没有Break Point
是不是Break Point有一线曙光的时候,成长函数成长的速度和函数一样快
——————————————————————————————————
第六章:

6-1 举一反三的理论

如果M跑到无限大去,我们就无法实现学习了,所以我们在找m
我们希望m增长缓慢,能够取代掉长得很快的M
m成长函数最多能够产生多少种dichotomy
positive rays:一维
成长函数在2个点的时候只能产生3中可能性 break point在2
positive intervals:不能处理叉叉在中间,圈圈在外面的情况,break point在3
convex set:在二维平面上,在凸的集合里面是圈圈,外面是叉叉,没有break point
2D perceptrons:四个点对称对望,break point 在4
只要一开始是break point,那之后的k+1,k+2。。。都是break point
约定:任意两个点不能shatter
6-2 Bounding Fuction
不想成长函数到底什么样子,而去思考排列组合上到底可以有多少种
证明:B(N,k)<=
N:有几个点
k:break point漏出一线曙光的地方
当N和k的值一模一样的时候,B(N,k) = 2`N – 1
6-3 
想办法把B(4,3)和B(3,?)找出联系
橘色的解都是放闪光的(成双成对)
还有三个是形单影只的
B(4,3) = 11 = 2α + β
α+β:dichotomies on (x1,x2,x3)
任意三个点不能shatter,最多最多B(3,3)
B(N,k) <= B(N-1,k) + B(N-1,k-1)
从成长函数,到上限函数,到上限的上限
 成长函数会被上限函数Bound住,上限函数,会被上限的上限函数Bound住……
6-4 A Pictorial Proof
Ein只有有限个(和data有关)。Eout是无限多个。
现在想做的就是将Eout也变成有限多个。
Eout什么时候会是有限多个?
把Eout换成Ein`
————————————————————————————————
第七章:

7-1 VC Dimension

复习:举一反三的学说 Theory of Generalization
成长函数会被上限函数Bound住,上限函数会被多项式函数Bound住,多项式的最高项是N的k-1次方
VC Bound:坏事情的几率很小很小
不管我们的演算法作了什么选择,都可以说我们的演算法做的选择受支配
我们可以把成长函数代换成上限的上限函数
本来我们就假设N够大,k要>=3
如果k比3小,那就不能用N的k-1次方这个Bound
几个条件让我们Learning做得到
1、要有个好的成长函数
2、要N足够大
3、一个好的演算法
VC Dimension(VC维度)是什么呢?
给最大的非break point的昵称
如果break point不存在,那么VC Dimension就是无限大
四种不同的VC Dimensions分析:
一个好的hypothesis,Ein和Eout会接近,并且和你选择的演算法是没有关系的
和你的资料有什么distribution产生没有关系

和你的目标长什么样子也没有关系

7-2 VC Dimension的感知器
在多维的情况,演算法发生了什么事情?
一维:dVC = 2
二维:dVC = 3
d维:dVC = d+1
一组特别的资料,有d+1笔
反矩阵存在,且唯一
给任意一种排列组合,y都能做到X*w之后取正负号等于y
如果2,3是圈,1是×,那x4一定大于0
线性依赖的关系会限制dichotomy
对于一般的资料:
d+2这个向量一定是正的
前面都会限定了,那么最后一个也会被限定
7-3 有效二元分类自由度
两个老问题:
1、Ein和Eout是否够接近
2、Ein是否足够小
small M:坏事情几率很小,但是Ein没有办法做到很小
large M :Ein很小,但是坏事情发生的几率变大啦
small dVC:坏事情几率很小,但是Ein没有办法做到很小
large dVC:自由度很高,我们可以选到一个比较小的Ein,但是坏事情发生几率变大
7-4
有很高的机会,Ein和Eout的差别会被限制在这个根号里面:
 model complexity:随着dVC变大,越来越大
out-of-sample error:先下降,后上升,最好的Ein在中间
VC Bound -> Sample Complexity
资料越多,坏事情发生的几率越小
VC Bound到底有多宽松
我们使用了Union Bound在最差的地方
虽然VC Bound非常宽松,但是要做到和VC Bound一样的话,很难很难
对于所有hypothesis,宽松的程度是差不多的
VC Bound背后的哲学意义到底是什么?
————————————————————————————————
第八章

8-1杂讯和错误

如果在图里加上了noise会不会有影响?
例如:
noise in y:一个好的顾客,但是没给信用卡
noise in y:两个一样的顾客,但是没给其中一个人信用卡
noise in x:顾客的资料不精准
VC Bound的核心是什么?
我们有一个罐子,但是我们不知道罐子里有多少橘色的弹珠->我们犯错误的地方
想象:罐子中有变色龙弹珠,有的时候会变来变去
y也是取样来的
目标分布:告诉我们,对每一个点,mini-target是多少
PLX:常常会被simple到
8-2 错误的评估
怎么样说服人家,相信我们的g和f是很像的
到底我们要怎么打分数
g的特性:
out-of-sample:在样本之外吻合的情况
pointwise:我们可以在每一个x上面衡量,做抽样的平均
classification:我们做的到底对还是不对
zero-one:0,1的错误方式,不是0就是1
squared error:很多时候我们做的错误衡量可以和之前一样,考虑每个点上的正确还是错误,然后做了一个在out-of-sample上的平均
每个点上错误的方式
用err来做代表
in-sample:我们在每个点上衡量错误的状况
out-of-sample:在有noise的状况上,衡量g和y的差别
在未来课程中我们还是会采用这种err的方式,集中在Pointwise的方式
1、0/1分布
2、squared error平方的错误:预测的y和我们想要的y到底差多远->隔得越远,跑得越快,通常用在预测实数的问题。使用错误的距离和错误距离的平方
错误衡量会影响到我们最好的那个f长什么样子
错误衡量会用来看看g好还是不好
结论:错误衡量是很重要的部分
8-3 错误衡量的算法
错误衡量哪里来?
想象:你要做一个指纹辨识的应用
分类器:+1:是你  -1:不是你
分类器可能会犯两种错误:
1、 false accept
2、 false reject
应用:在超市里通过指纹决定要不要给顾客打折
false reject:让顾客不高兴,损失未来的效益
false accept:失去一点点盈利,留下指纹
应用2:CIA辨识某个人可不可以进入系统查看机密
false reject:非常严重的失误
false accept:员工不太高兴,但是没什么损失
结论:不同的错误会想要不同的错误衡量
设计算法的时候就要想办法把不同的错误衡量方式用进去
用替代的方式:找一些有意义的错误衡量
杂讯的量很少,
平方:高斯的杂讯——平方项会在中间出现,找出最小的高斯杂讯
采用friendly:采用比较好设计演算法,寻求Ein会越来越小
err hat(err上面带个帽子)对演算法是很重要的
err是我们真正的应用程式的目标
8-4 衡量分类
每个case都有不同的配分
成本矩阵(错误矩阵、损失矩阵)
难题:我们要让Ein越来越小,加上VC可以用的话,我们就可以相信Eout会和Ein越来越接近
问题:对加权的Ein来说,它理论上的保障可靠与否
修改pocket演算法,让它和原来的pocket有一样的保证
问题:如果-1有错,就算他1000倍错误,+1有错就算他1倍错误
想象:拿到另外一组资料,+1,不管,-1的话,复制1000倍
想办法在新的办法上把每一种错误都收一块钱的方法做好(0/1)
考虑权重的pocket方法
拜访权重高的点的几率要增加

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据