软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 开发杂谈 -> coursera机器学习技法笔记(1 -> 正文阅读

[开发杂谈]coursera机器学习技法笔记(1


1 Linear Support Vector Machine

1.1 Coursera Introduction


  本门课程主要内容是围绕特征转换进行的,并包括三种主要的思想:
  (1)怎样使用数字的特征并控制其复杂度:该角度启发了SVM模型。
  (2)怎样构建并混合使用具有预测能力的特征:启发了adaboost模型。
  (3)发现并利用潜在的特征:启发了Deep Learning模型。

1.2 Large Margin Separating Hyperplane


  最大间隔的目标是,使得最靠近划分数据集的超平面的点到超平面的距离最大,同时保证超平面能正确划分所有点。即:

max(min1ndistance(xn,w))

s.t.every yn(wTxn+b)0

1.3 Standard Large-Margin Problem


  首先计算distance(xn,w),套用几何公式,xn到以w为法向量的超平面的距离是:

distance(xn,w)=||wTxn?b||||w||
同时,根据条件限制,我们有yn(wTxn+b)0,故上式可写为:

distance(xn,w)=1||w||yn(wTxn?b)
同时我们可以注意到,对w进行放缩(即每个分量同时乘以或除以一个常数)是对distance(xn,w)没有影响的,所以我们对w进行缩放,令min yn(wTxn?b)=1,则整个问题变成了:

max1||w||

s.t. min yn(wTxn+b)=1
鉴于约束条件难解,我们在不改变最优解的条件下放宽约束:

max1||w||

s.t. ?yn(wTxn+b)1
这样做不改变最优解的原因是,当存在w使得?yn(wTxn+b)=c1,我们可以通过不等号两边同时除以c,使得w:=wc,b:=bc在满足约束的时候获得更大的1||w|| ,因此最优解一定符合约束条件。
  最后,我们将优化目标去绝对值,转换为对偶问题,并加上常数方便以后的运算:

max 12wTw

s.t. ?yn(wTxn+b)1

1.4 Support Vector Machine


  以上的优化目标可以用二次规划QP(Q,p,A,c)解决,二次规划的目标是:

max wTQw+pTw

s.t. Awc
在此将b作为w_0加入 w后对照使用即可。

1.5 Reason behind Large-Margin Hyperplane


  本节叙述了SVM能工作的理论基础。可以从优化目标内看出,SVM的目标是在限制yn(wTxn+b)1的条件下对wTw取最小,而regularize是在wTw<c
  从VC维的角度来看,由于限制了最大边际至少大于1,因此使得一些能被PLA打散的数据不能被SVM打散,导致其VC维降低。

2 Dual Support Vector Machine

2.1 Motivation of Dual SVM


  由于我们希望SVM能进行非线性划分,而通过多项式特征转换进行非线性划分会导致大量的VC维,因此我们希望找到一种方法使得其复杂度能与多项式特征个数无关。
  本节后半部分介绍了用拉格朗日乘子来解带约束的优化问题,并解释了拉格朗日乘子的工作原理。

2.2 Largrange Dual SVM


  我们希望将原问题转化为对偶问题:

minb,w(maxall αn0L(b,w,α))maxall αn0(minb,wL(b,w,α))
当满足KKT条件时不等号可以化为等号,推导过程如下:

maxall αn0(minb,w12wTw+Mn=1αn(1?yn(wTxn+b)))
对上式中最小化部分的b求导,并使结果等于0,得到结果:

Mn=1αnyn=0
对上式中最小化部分的w求导,并使结果等于0得到结果:

w=?Mn=1αnynxn
将这两者分别带入优化目标公式中可以得到对偶问题的优化目标公式:

maxall αn0,αnyn=0,w=αnynxn(?12||Mn=1αnynxn||2+Mn=1αn)
  另外,KKT的条件是:
  (1)满足原问题的约束;
  (2)拉格朗日乘子不小于0(在上式中写为α);
  (3)对偶问题的各变量(即wb)求导结果为0;
  (4)拉格朗日项(即拉格朗日乘子乘以约束)均为0(要么拉格朗日乘子为0,要么约束项等于0);
  可以看出,在以上的推导、转换的过程中已经满足了KKT的全部条件,因此可以判定能转化为对偶问题。

2.3 Solving Dual SVM


  我们可以将上节的最优化目标增加符号后转换为最小化优化问题,并利用二次规划解α。这里需要注意的是,由于在对应的二次优化问题中会出现一个极大密集矩阵Qp,q=ypyqxpxq,因此建议使用对SVM特别优化的二次规划计算包。
  当解得α后,我们可以通过

w=?Mn=1αnynxn
来解得w,并通过

αn(1?yn(wTxn+b))=0

b=yn?wTxn
来解得b。以上公式由KKT条件得出。另外我们可以注意到一个有意思的现象是,当αn不等于0时,yn(wTxn+b)=1,说明该样本是支持向量。

2.4 Message behind Dual SVM


2.4.1 SVM与PLA的比较
  可以发现,SVM与PLA在对w的求解上都是类似的,即w是样本点xy的线性组合。其区别在于,SVM采用了支持向量的样本点来求解w,而PLA用“犯错”的样本点来进行线性组合求解w
2.4.2 原始SVM与对偶SVM的比较
  原始SVM是通过拉伸wb来找到合适的wb,其与w的复杂度(特征向量的长度)有密切关系。而对偶问题通过找支持向量(判断αn是否为0)来求解w。其中,原始问题由于与复杂度关系很大,因此适用于特征不多的情况下,而对偶问题由于表面上与特征数量无关,因此使用在数据量少而特征较多的情况下。
  但需要注意的是,对偶问题并没有使得计算复杂度与特征数量完全独立,因为在求对偶问题的矩阵时,Qp,q=ypyqxpxq很明显和特征数量有关系。
另外注意到的一点是,在边界上的点未必是支撑向量,因为它的αn也同样可能是0.

3 Kernel Support Vector Machine

3.1 Kernel Trick


  在SVM的对偶问题中,计算Qp,q=ypyqxpxq时依旧会与特征数量相关,因此有一个trick可以简化多次特征的计算,在这里设zx的多次特征转换之后的特征:

K(x,x)=zTz=1+ni=1xixi+ni=1nj=1xixjxixj=1+xTx+(xTx)2
  因此,只要有关zTz的特征计算,都可以通过计算xTx来实现。这个函数叫核函数(kernel function)。同时,我们还可以通过该方法来计算wTz

wTz=(Mn=1αnynzn)z=Mn=1αnynzTnz=Mn=1αnynK(xTnx)
其中M是支持向量集。通过这种方法,我们能极大缩减高次特征转换所需要的计算资源。

3.2 Polynomial Kernel


  对核函数的计算进行进一步简化,以二次核函数为例,我们设中间一次项系数为2,代表着我们对高次空间z中一次项的系数做了伸缩:

K2(x,x)=1+2xTx+(xTx)2=(1+xTx)2
可以看到,我们再一次简化了计算。将该方法扩展至高次,并添加系数以控制伸缩程度:

K2(x,x)=(δ+γxTx)Q
  这样,计算资源再一次得到了缩减,并且可以通过系数来控制伸缩程度。这种放缩的方法本质上对应着距离定义的变化。

3.3 Gaussian Kernel


  我们可以利用高斯函数作为核函数,即:

K(x,x)=exp(?γ||x?x||2)
由于高斯函数可以通过泰勒展开成为无限高次的多项式组合,因此高斯核代表了无限高次的特征转化。
  但需要注意的是,γ过高时依旧会发生过拟合的现象。

3.4 Comparison of Kernels


  本节对几个kernel做了对比。
  (1)线性SVM的好处是用原始问题求解速度快,并且不用担心过拟合问题,缺点是不能解决非线性数据分类。
  (2)多次核的好处是可以解决非线性分类问题,但参数多难以选择,并且在次数高的时候得到的核的值要么很大,要么逼近0,因此在低阶的时候可以考虑使用多次核。同时,当次数很低,例如是2或是3的时候,或许直接构造出多次特征空间然后用线性SVM的原始问题求解可能会更快。
  (3)高斯核的好处在于非常强大,并且参数少。缺点在于计算复杂,容易过拟合。
  另外,可以将核函数看成是两个向量的相似度,但是由于核的出处是内积,因此如果要构造新的核,需要在一定程度上满足内积的特点:
  (1)对称性,所定义的核必须满足两个向量交换位置值不变。
  (2)所有样本两两之间相互使用核函数进行计算所得到的矩阵是半正定的。

4 Soft-Margin Support Vector Machine

4.1 Motivation and Primal Problem


  我们在原优化目标的基础上加入容忍错误的条目并使错误更轻成为优化目标之一:

minw,b,ε12wTw+CNn=1ε

s.t.?ynwTxn+b1?εn

?εn0
其中,C代表了margin的大小与容忍样本错误度的相对比例,C越大,代表我们希望错误程度越低,即SVM更严格,margin越低,反之亦然。εn代表了第n个节点偏离超平面的程度。

4.2 Dual Problem


  我们按照原来的hard-SVM的方法同样来推导soft-SVM。首先通过拉格朗日乘子将问题转化为min-max问题,然后利用KKT条件转化为max-min问题,在这里注意到的是,设条件?ynwTxn+b1?εn的拉格朗日乘子为αn?εn0的拉格朗日乘子为βn,则先对εn求导,我们可以得到βn=C?αn,代入式子后发现和原来hard-SVM的形式相同,因此soft-SVM的对偶形式为:

maxα(?12||Mn=1αnynxn||2+Mn=1αn)

Cαn0

αnyn=0
其中仅第二行的条件有所区别,原因是新加入条件βn=C?αn0

4.3 Message behind Soft-Margin SVM


  注意到在最后求解b的时候Soft-SVM会与hard-SVM有所区别,通过KKT条件我们可以知道:

αn(1?εn?yn(wTxn+b))=0

(C?αn)εn=0
可以看到,我们必须令0<αn<C并且通过

1?yn(wTxn+b)=0
解出b,这部分的样本叫free-support vector。当αn=C时,εn>0,代表这部分样本到超平面的距离小于最小边界,或者分类错误了。当αn=0εn=0,因此代表这些样本非常安全,离边界很远。

4.4 Model Selection


  选择最好模型参数的方法是利用验证集,同时,SVM还有一个非常有意思的理论可以在某种程度上减少我们验证的次数。
  在交叉测试的留一法中,如果被选中作为测试点的样本是非支持向量,则该点的测试结果一定是正确,同时如果把它放进训练集再换另一个非支持向量出来测试,结果同样是正确。而如果把支持向量作为测试样本,结果未必正确。因此,SVM的误差上限是支持向量数量除以样本总量。
  需要注意的是,由于仅仅是误差上限,因此常常用来排除“错误答案”。
......显示全文...
    点击查看全文


上一篇文章      下一篇文章      查看所有文章
2016-04-03 20:46:48  
开发杂谈 最新文章
BloomFilter
大学四年编程之历程
内核分析
造人论坛——意识的本质和一个人工脑模型
OFDM信号[matlab描述]
人类还会进化吗?
HDUACM1035RobotMotion简单模拟题
树、二叉树(二)
iisphpweb.config处理404,500等,跳转友好
DatabaseAsaFortress
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年4日历
2018-4-21 23:07:36
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --