下次自动登录
现在的位置:
& 综合 & 正文
机器学习中的算法-svm学习
本文由LeftNotEasy发布于
一、线性分类器：
首先给出一个非常非常简单的分类问题（线性可分），我们要用一条直线，将下图中黑色的点和白色的点分开，很显然，图上的这条直线就是我们要求的直线之一（可以有无数条这样的直线）
假如说，我们令黑色的点 = -1， 白色的点 =
+1，直线f(x) = w.x + b，这儿的x、w是向量，其实写成这种形式也是等价的f(x) = w1x1 + w2x2 … + wnxn + b, 当向量x的维度=2的时候，f(x) 表示二维空间中的一条直线， 当x的维度=3的时候，f(x) 表示3维空间中的一个平面，当x的维度=n & 3的时候，表示n维空间中的n-1维超平面。这些都是比较基础的内容，如果不太清楚，可能需要复习一下微积分、线性代数的内容。
刚刚说了，我们令黑色白色两类的点分别为+1, -1，所以当有一个新的点x需要预测属于哪个分类的时候，我们用sgn(f(x))，就可以预测了，sgn表示符号函数，当f(x) & 0的时候，sgn(f(x)) = +1, 当f(x) & 0的时候sgn(f(x)) = –1。
但是，我们怎样才能取得一个最优的划分直线f(x)呢？下图的直线表示几条可能的f(x)
一个很直观的感受是，让这条直线到给定样本中最近的点最远，这句话读起来比较拗口，下面给出几个图，来说明一下：
第一种分法：
第二种分法：
这两种分法哪种更好呢？从直观上来说，就是分割的间隙越大越好，把两个类别的点分得越开越好。就像我们平时判断一个人是男还是女，就是很难出现分错的情况，这就是男、女两个类别之间的间隙非常的大导致的，让我们可以更准确的进行分类。在SVM中，称为Maximum Marginal，是SVM的一个理论基础之一。选择使得间隙最大的函数作为分割平面是由很多道理的，比如说从概率的角度上来说，就是使得置信度最小的点置信度最大（听起来很拗口），从实践的角度来说，这样的效果非常好，等等。这里就不展开讲，作为一个结论就ok了，:)
上图被红色和蓝色的线圈出来的点就是所谓的支持向量(support vector)。
上图就是一个对之前说的类别中的间隙的一个描述。Classifier Boundary就是f(x)，红色和蓝色的线（plus plane与minus plane）就是support vector所在的面，红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙。
这里直接给出M的式子：（从高中的解析几何就可以很容易的得到了，也可以参考后面Moore的ppt）
另外支持向量位于wx + b = 1与wx + b = -1的直线上，我们在前面乘上一个该点所属的类别y（还记得吗?y不是+1就是-1），就可以得到支持向量的表达式为：y(wx + b) = 1，这样就可以更简单的将支持向量表示出来了。
当支持向量确定下来的时候，分割函数就确定下来了，两个问题是等价的。得到支持向量，还有一个作用是，让支持向量后方那些点就不用参与计算了。这点在后面将会更详细的讲讲。
在这个小节的最后，给出我们要优化求解的表达式：
||w||的意思是w的二范数，跟上面的M表达式的分母是一个意思，之前得到，M = 2 / ||w||，最大化这个式子等价于最小化||w||, 另外由于||w||是一个单调函数，我们可以对其加入平方，和前面的系数，熟悉的同学应该很容易就看出来了，这个式子是为了方便求导。
这个式子有还有一些限制条件，完整的写下来，应该是这样的：（原问题）
s.t的意思是subject to，也就是在后面这个限制条件下的意思，这个词在svm的论文里面非常容易见到。这个其实是一个带约束的二次规划(quadratic programming, QP)问题，是一个凸问题，凸问题就是指的不会有局部最优解，可以想象一个漏斗，不管我们开始的时候将一个小球放在漏斗的什么位置，这个小球最终一定可以掉出漏斗，也就是得到全局最优解。s.t.后面的限制条件可以看做是一个凸多面体，我们要做的就是在这个凸多面体中找到最优解。这些问题这里不展开，因为展开的话，一本书也写不完。如果有疑问请看看wikipedia。
二、转化为对偶问题，并优化求解:
这个优化问题可以用去解，使用了的理论，这里直接作出这个式子的拉格朗日目标函数：
求解这个式子的过程需要的相关知识（另外pluskid也有专门讲这个问题），并且有一定的公式推导，如果不感兴趣，可以直接跳到后面用蓝色公式表示的结论，该部分推导主要参考自。
首先让L关于w，b最小化，分别令L关于w，b的偏导数为0，得到关于原问题的一个表达式
将两式带回L(w,b,a)得到对偶问题的表达式
新问题加上其限制条件是（对偶问题）:
这个就是我们需要最终优化的式子。至此，得到了线性可分问题的优化式子。
求解这个式子，有很多的方法，比如等等，个人认为，求解这样的一个带约束的凸优化问题与得到这个凸优化问题是比较独立的两件事情，所以在这篇文章中准备完全不涉及如何求解这个话题，如果之后有时间可以补上一篇文章来谈谈:)。
三、线性不可分的情况（软间隔）：
接下来谈谈线性不可分的情况，因为线性可分这种假设实在是太有局限性了：
下图就是一个典型的线性不可分的分类图，我们没有办法用一条直线去将其分成两个区域，每个区域只包含一种颜色的点。
要想在这种情况下的分类器，有两种方式，一种是用曲线去将其完全分开，曲线就是一种非线性的情况，跟之后将谈到的核函数有一定的关系：
另外一种还是用直线，不过不用去保证可分性，就是包容那些分错的情况，不过我们得加入惩罚函数，使得点分错的情况越合理越好。其实在很多时候，不是在训练的时候分类函数越完美越好，因为训练函数中有些数据本来就是噪声，可能就是在人工加上分类标签的时候加错了，如果我们在训练（学习）的时候把这些错误的点学习到了，那么模型在下次碰到这些错误情况的时候就难免出错了（假如老师给你讲课的时候，某个知识点讲错了，你还信以为真了，那么在考试的时候就难免出错）。这种学习的时候学到了“噪声”的过程就是一个过拟合（over-fitting），这在机器学习中是一个大忌，我们宁愿少学一些内容，也坚决杜绝多学一些错误的知识。还是回到主题，用直线怎么去分割线性不可分的点：
我们可以为分错的点加上一点惩罚，对一个分错的点的惩罚函数就是这个点到其正确位置的距离：
在上图中，蓝色、红色的直线分别为支持向量所在的边界，绿色的线为决策函数，那些紫色的线表示分错的点到其相应的决策面的距离，这样我们可以在原函数上面加上一个惩罚函数，并且带上其限制条件为：
公式中蓝色的部分为在线性可分问题的基础上加上的惩罚函数部分，当xi在正确一边的时候，ε=0，R为全部的点的数目，C是一个由用户去指定的系数，表示对分错的点加入多少的惩罚，当C很大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重，当C很小的时候，分错的点可能会很多，不过可能由此得到的模型也会不太正确，所以如何选择C是有很多学问的，不过在大部分情况下就是通过经验尝试得到的。
接下来就是同样的，求解一个拉格朗日对偶问题，得到一个原问题的对偶问题的表达式：
蓝色的部分是与线性可分的对偶问题表达式的不同之处。在线性不可分情况下得到的对偶问题，不同的地方就是α的范围从[0, +∞)，变为了[0, C]，增加的惩罚ε没有为对偶问题增加什么复杂度。
四、核函数：
刚刚在谈不可分的情况下，提了一句，如果使用某些非线性的方法，可以得到将两个分类完美划分的曲线，比如接下来将要说的核函数。
我们可以让空间从原本的线性空间变成一个更高维的空间，在这个高维的线性空间下，再用一个超平面进行划分。这儿举个例子，来理解一下如何利用空间的维度变得更高来帮助我们分类的（例子以及图片来自）：
下图是一个典型的线性不可分的情况
但是当我们把这两个类似于椭圆形的点映射到一个高维空间后，映射函数为：
用这个函数可以将上图的平面中的点映射到一个三维空间（z1,z2,z3)，并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。
用另外一个哲学例子来说：世界上本来没有两个完全一样的物体，对于所有的两个物体，我们可以通过增加维度来让他们最终有所区别，比如说两本书，从(颜色，内容)两个维度来说，可能是一样的，我们可以加上
作者 这个维度，是在不行我们还可以加入 页码，可以加入 拥有者，可以加入
购买地点，可以加入 笔记内容等等。当维度增加到无限维的时候，一定可以让任意的两个物体可分了。
回忆刚刚得到的对偶问题表达式：
我们可以将红色这个部分进行改造，令：
这个式子所做的事情就是将线性的空间映射到高维的空间,k(x, xj)有很多种，下面是比较典型的两种：
上面这个核称为多项式核，下面这个核称为高斯核，高斯核甚至是将原始空间映射为无穷维空间，另外核函数有一些比较好的性质，比如说不会比线性条件下增加多少额外的计算量，等等，这里也不再深入。一般对于一个问题，不同的核函数可能会带来不同的结果，一般是需要尝试来得到的。
五、一些其他的问题：
1）如何进行多分类问题：
上面所谈到的分类都是2分类的情况，当N分类的情况下，主要有两种方式，一种是1 vs (N – 1)一种是1 vs 1，前一种方法我们需要训练N个分类器，第i个分类器是看看是属于分类i还是属于分类i的补集（出去i的N-1个分类）。
后一种方式我们需要训练N * (N – 1) / 2个分类器，分类器(i,j)能够判断某个点是属于i还是属于j。
这种处理方式不仅在SVM中会用到，在很多其他的分类中也是被广泛用到，从林教授（libsvm的作者）的结论来看，1 vs 1的方式要优于1 vs (N – 1)。
2）SVM会overfitting吗？
SVM避免overfitting，一种是调整之前说的惩罚函数中的C，另一种其实从式子上来看，min ||w||^2这个看起来是不是很眼熟？在最小二乘法回归的时候，我们看到过这个式子，这个式子可以让函数更平滑，所以SVM是一种不太容易over-fitting的方法。
&&&&推荐文章:
【上篇】【下篇】机器学习（15）
先给个定义：核函数K（kernel function）就是指K(x, y) = ，其中x和y是n维的输入值，f(·) 是从n维到m维的映射（通常而言，m&&n）。是x和y的内积（inner product），严格来说应该叫欧式空间的标准内积，也就是很多人常说的点积（dot product）。
光看这一段还是不明白kernel是什么，用来干什么的...对吧？不要急。一个好的知识分享者是不会把一篇空洞的定义扔下就不管的，TA会告诉你这个概念的intuition，然后给你举个小小的栗子，最后告诉你几个应用场景。Andrew Ng的Machine Learning为什么会成为一门现象级的MOOC？原因之一就是因为他除了是个学术上的大神，也同样是个极有质素的知识分享者。所以我要学习他。
好了，intuitively（这也模仿得太生硬了吧…），要计算，我们要先分别计算f(x)和f(y)，然后再求它们的内积。上面的定义里也说了，经过映射后的x和y，维数大大增加，计算内积的成本可能会非常之大，而且在高位空间费力牛劲儿地计算内积，内积又是一个scalar，相当于说又把我们的计算从高维空间拉回到一维空间！所以我们特别想要一个“简便运算法”，帮助我们不需要奔向高维空间就能在家门口计算得到想要的内积。这时候该轮到我们的猪脚——kernel登场了，它能帮我们做到这一点。
举个小小栗子。
令 x = (x1, x2, x3, x4); y = (y1, y2, y3, y4);
令 f(x) = (x1x1, x1x2, x1x3, x1x4, x2x1, x2x2, x2x3, x2x4, x3x1, x3x2, x3x3, x3x4, x4x1, x4x2, x4x3, x4x4); f(y)亦然；
令核函数 K(x, y) = ()^2.
接下来，让我们带几个简单的数字进去看看是个什么效果：x = (1, 2, 3, 4); y = (5, 6, 7, 8). 那么：
f(x) = ( 1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16) ;
f(y) = (25, 30, 35, 40, 30, 36, 42, 48, 35, 42, 49, 56, 40, 48, 56, 64) ;
= 25+60+105+160+60+144+252+384+105+252+441+672+160+384+672+1024
好累，对不对？可谁让f(·)把四维空间的数据映射到十六维空间里呢？
如果我们用核函数呢？
K(x, y) = (5+12+21+32)^2 = 70^2 = 4900.
就是这样！
所以现在你看出来了吧，kernel其实就是帮我们省去在高维空间里进行繁琐计算的“简便运算法”。甚至，它能解决
无限维空间
无法计算的问题！因为有时f(·)会把n维空间映射到无限维空间去，对此我们常常束手无策，除非是用kernel，尤其是RBF kernel（K(x,y) = exp(-||x-y||^2) ）。
在有kernel之前，做machine learning的典型的流程应该是：data --& features --& learning algorithm，但kernel给我们提供了一个alternative，那就是，我们不必定义从data到feature的映射函数，而是可以直接kernel(data) --& learning algorithm，也可以是data --& features --& kernel(features) --& learning algorithm。
所以虽然我们看到kernel常被应用在SVM（SVM中的kernel应该是后一种用法，后文再说），但其实要用到内积的learning algorithm都可以使用kernel。“用到内积的learning algorithm”其实并不少见，不信你可以想一想最普通不过的linear classifier/regressor有没有一个步骤是计算特征向量（feature vectors）。
那么kernel在SVM究竟扮演着什么角色？
初学SVM时常常可能对kernel有一个误读，那就是误以为是kernel使得低维空间的点投射到高位空间后实现了线性可分。其实不然。这是
把kernel和feature space transformation
混为了一谈
。（这个错误其实很蠢，只要你把SVM从头到尾认真推导一遍就不会犯我这个错。）
还是简单回顾一下吧。SVM就是 y = w'·φ(x) + b，其中φ(x)是特征向量（feature vectors），并且是φ(x)使得数据从低维投射到高位空间后实现了线性可分。而kernel是在解对偶问题的最优化问题时，能够使φ(x)更方便地计算出来，特别是φ(x)维数很高的时候。
------------------------------正文完，附上几个链接--------------------------------
kernel的种类繁多，如果想详细了解，可以看看这个帖子
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2132658次
积分：22697
积分：22697
排名：第286名
原创：248篇
转载：762篇
评论：138条
(7)(6)(2)(27)(6)(3)(7)(1)(3)(5)(1)(2)(1)(6)(2)(4)(3)(3)(7)(5)(28)(4)(18)(20)(12)(6)(6)(5)(9)(5)(5)(7)(7)(7)(1)(2)(7)(10)(23)(5)(44)(31)(29)(39)(93)(18)(14)(72)(7)(28)(48)(41)(25)(14)(1)(4)(11)(9)(14)(7)(7)(8)(5)(1)(24)(20)(18)(7)(16)(7)(41)(13)(9)核机器学习
kernel machine learning
核机器学习
基于3个网页-
Kernel Machine Learning Method
kernel machine learning
- 引用次数：4
And the kernel machine learning can make many methods in pattern recognition have the ability to process nonlinear data by means of kernel mapping. This has very important significance in terms of hyperspectral imagery processing.
而核机器学习能够通过核映射的形式使得众多的模式识别方法具有非线性数据处理能力,这对处理高光谱图像这类复杂数据具有非常重要的意义。
参考来源 -
kernel-based machine learning
- 引用次数：1
参考来源 -
&2,447,543篇论文数据，部分数据来源于
$firstVoiceSent
- 来自原声例句
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！机器学习/深度学习（25）
//想买mac pro，大陆价格贵得很，在找港台或者美帝的小伙伴代购。囧囧=。=以后不能玩烧显卡的游戏了，谁有mac的待机时间太吸引人了。
上一次我们学习了对偶形式，对偶形式的解决其实也是一个二次规划的问题，而且这个二次规划问题好像是和我们所在的空间没有关系。
但是实际上，是隐藏在了矩阵计算中。这就是我们的瓶颈所在。
在矩阵计算中，每一项都有zz‘相乘，因为z是x在z空间的转换，所以可以写成zz’=f(x)f(x')，因为有的符号这个页面编辑不太方面，相应换一下，能看懂就行=。=
按照我们正常的思路就是先做完转换再去做内积，显然这是一个很费力气的过程。我们现在考虑能不能把这两个步骤合起来，来减少我们的运算量
下面来看这样一个例子：
f2(x)=（1，x1,x2,...,xd,x1*x1.x1*x2,...,x1*xd,x2*x1,x2*x2,...,x2*xd,...xd*xd）其实就是一个二次式
那么按照普通的思路
这个计算过程还是比较容易理解吧=。=
我们观察这个式子，显然最后面那一堆可以看成是中间那一堆的平方嘛
显然我们最后可以只通过计算xx就能算出结论，不需要转换到Z空间。
我们就把上面这个转换和内积合在一起的计算机称为kernel function
那自然在我们刚才二次规划问题中，计算的时候，也可以采用这样的思想
q=yyzz=yyk(x,x),其中k代表了kernel function ，当然我这里的式子都是表达一下意思，并没有详细标明下标，要看最准确的还是看老师的原视频比较好，这里能够明白意思就好。
接着，上次讲了，我们应该如何求b，从支持向量里面选择一个
b=y-wz，这个时候，我们发现我们求b的时候又有z了，怎么办？
可是记得我们上次学得w是关于z的线性组合
所以可以代换，具体步骤见下图
上图还包括了，得到b以后，如何求出分类器的推导，很简单。
前面我们通过一个特殊的例子得到了一个二次的kernel，那是不是在二次的时候，我们只能用这儿kernel呢？
其实不是的，我们可以看下图
可以看到我们可以同调整这个γ来调整这个二次项前面的系数。
在调整后这个γ以后，其实都是映射到一个空间，同时配合一个w来算一个权值，但是不同的γ对应到的几何意义肯定不一样，那么对应的margin以及SVs肯定会发生变化
其中方框框代表了SVs
当然不仅仅是2次项
显然这三个变量控制了这个kernel
当然按照我们的这场思维，太高次的kernel是不是会导致overfit呢，还好在我们的SVM里面，我们有一个larg-margin来帮助我们控制复杂度，所以可以看到利用SVM加上kernel不但可以有效的控制计算复杂度，还可以有效的控制复杂度。
那么我们现在有一个很疯狂的想法，无限多维的转换。
引入高斯kernel
看一下高斯kernel的步骤
中间用了一下泰勒展开，其他地方在数学上没有任何难度，大家应该都能看懂，泰勒展开忘了，可以去翻高数书=。=
想当年我高数也是考了98的，现在好多都忘了=。=，被吊打
那么带入我们刚才知道的利用kernel表示的g
显然前面那个γ也是一个参数
其实仔细观察这个式子，我们可以发现，其实这个式子就是SVs的高斯函数组合，不是SVs的点，显然因为α是0，可以不考虑了
所以也被人称作Radial Basis Function（RBF）
当然这个γ的选择也是要注意的，虽然SVM有large-margin控制复杂度，但也只是控制，所以还是有可能出现overfit
那我们上面提到这么多kernel，下边进行好坏对比
linear：安全，快，能看得比较明白，坏处自然是不能处理比较复杂的数据
polynomial：自然限制少，能够自己考虑这个Q，坏处对于Q很大的时候，数值计算会比较困难，参数选择比较困难，因为有3个参数需要选择、
gaussian ：能做出复杂边界，宽松,gaussion数值困难小，参数选择较小，坏处是，不太好表达，不能很好表达，可能会出现overfit，最常用的
kernel不仅要对称还要半正定
我们现在都是要求在Z空间里面要线性可分，所以如果有noise，这样会导致overfitting
下一节来解决。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：50617次
积分：1019
积分：1019
排名：千里之外
原创：42篇
转载：84篇
(2)(1)(1)(2)(1)(2)(5)(2)(4)(12)(5)(4)(12)(19)(8)(1)(7)(2)(4)(10)(10)(13)}