机器学习之支持向量机(Support Vector Machine)(更新中...)

支持向量机

  支持向量机(support vector machines,SVMs)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;支持向量机还包括核技巧,这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划(convex quadratic programming)的问题。

  支持向量机学习方法包含构建由简至繁的模型:线性可分支持向量机(linear support vector machine in linearly separable case)、线性支持向量机(linear support vector machine)及非线性支持向量机(non-linear support vector machine)。简单模型是复杂模型的基础,也是复杂模型的特殊情况。当训练数据线性可分时,通过硬间隔最大化(hard margin maximization),学习一个线性的分类器,即线性可分支持向量机,又称为硬间隔支持向量机;当训练数据近似线性可分时,通过软间隔最大化(soft margin maximization),也学习一个线性的分类器,即线性支持向量机,又称为软间隔支持向量机;当训练数据线性不可分时,通过使用核技巧(kernel trick)及软间隔最大化,学习非线性支持向量机。通过使用核函数可以学习非线性支持向量机,等价于隐式地在高维的特征空间中学习线性支持向量机。核方法(kernel method)是比支持向量机更为一般的机器学习方法。

线性可分支持向量机与硬间隔最大化

  支持向量机的学习是在特征空间进行的。假设给定一个特征空间上的训练数据集,其中,为第i个特征向量,也称为实例,的类标记,当=+1时,称为正例;当=-1时,称为负例,称为样本点。再假设训练数据集是线性可分的。

  学习的目标实在特征空间中寻找一个分离超平面,能将实例分到不同的类。分离超平面对应于方程,它由法向量和截距决定,可用来表示。

  一般地,当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开。线性可分支持向量机利用间隔最大化求最优分离超平面,这时,解是唯一的。

  定义线性可分支持向量机)给定线性可分训练数据集,通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为:

以及相应的分类决策函数称为线性可分支持向量机。

  算法线性可分支持向量机学习算法——最大间隔法

    输入:线性可分训练数据集,其中,

    输出:最大间隔分离超平面和分类决策函数。

    (1)构造并求解约束最优化问题:

          

            

    求得最优解

    (2)由此得到分离超平面:

          

    分类决策函数

          

  在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(support vector)。支持向量是使约束条件等号成立的点,即

          

  对的正例点,支持向量在超平面上,

  对的负例点,支持向量在超平面上。

  称为间隔边界。

  在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用。

  那么,上述算法中的是怎么得到的呢?

  想要求解线性可分支持向量机的最优化问题,将它作为原始最优化问题,应用拉格朗日对偶性,通过求解对偶问题(dual problem)得到原始问题(primal problem)的最优解,这就是线性可分支持向量机的对偶算法(dual problem)。这样做的有点,一是对偶问题往往更容易求解;二是自然引入核函数,进而推广到非线性分类问题。

  首先构建拉格朗日函数(Lagrange function)。为此,对每一个不等式约束引进拉格朗日乘子(Lagrange multiplier),定义拉格朗日函数:

        

  其中,为拉格朗日乘子向量。

  根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:

        

  所以,为了得到对偶问题的解,需要先求对w,b的极小,再求对的极大。

  (1)求

    将拉格朗日函数分别对w,b求偏导数并令其等于0。

        

        

    得

        

        

    将上述两式带入拉格朗日函数,即得

        

             

    即

        

  (2)求的极大,即是对偶问题

        

          

        ,i=1,2,...,N

   将上述目标函数由极大转换成极小,就得到下面与之等价的对偶最优化问题:

        

          

        ,i=1,2,...,N

  设是对偶最优化问题的解,则存在下标j,使得,并可按下式求得原始最优化问题的解

        

        

时间: 09-15

机器学习之支持向量机(Support Vector Machine)(更新中...)的相关文章

支持向量机SVM(Support Vector Machine)

支持向量机(Support Vector Machine)是一种监督式的机器学习方法(supervised machine learning),一般用于二类问题(binary classification)的模式识别应用中. 支持向量机的最大特点是既能够最小化经验损失(也叫做经验风险.或者经验误差),同时又能够最大化几何间距(分类器的置信度),因此SVM又被称为最大边缘区(间距)的分类器. 根据具体应用场景的不同,支持向量机可以分为线性可分SVM.线性SVM和带有核函数的SVM.最终的结果都是得

斯坦福第十二课:支持向量机(Support Vector Machines)

12.1  优化目标 12.2  大边界的直观理解 12.3  数学背后的大边界分类(可选) 12.4  核函数 1 12.5  核函数 2 12.6  使用支持向量机 12.1  优化目标 到目前为止,你已经见过一系列不同的学习算法.在监督学习中,许多学习算法的性能都非常类似,因此,重要的不是你该选择使用学习算法 A 还是学习算法 B,而更重要的是, 应用这些算法时,所创建的大量数据在应用这些算法时,表现情况通常依赖于你的水平.比 如:你为学习算法所设计的特征量的选择,以及如何选择正则化参数,

机器学习技法——第1-2讲.Linear Support Vector Machine

本栏目(机器学习)下机器学习技法专题是个人对Coursera公开课机器学习技法(2015)的学习心得与笔记.所有内容均来自Coursera公开课Machine Learning Techniques中Hsuan-Tien Lin林轩田老师的讲解.(https://class.coursera.org/ntumltwo-001/lecture) 第1讲-------Linear Support Vector Machine 在机器学习基石介绍的基本工具(主要围绕特征转换Feature Transf

Machine Learning Techniques -1-Linear Support Vector Machine

1-Linear Support Vector Machine 我们将这种定义为margin,则之前判断最优划分的问题转化为寻找最大margain的问题. 对于待选的几个w所表示的线,问题转化成利用对应w比较相对距离的问题. 此时定义w为方向向量,b为之前的w0,即bia. 由于w就是所求点到直线的法线方向,问题转化为求投影的问题. 因为每个点对应符号yn只有在和距离表示的绝对值内部符号为+的时候才说明划分正确,所以可以乘上yn来去除abs() 这里的距离是一种容忍度,所以我们选其中最近的那个.

【Linear Support Vector Machine】林轩田机器学习技法

首先从介绍了Large_margin Separating Hyperplane的概念. (在linear separable的前提下)找到largest-margin的分界面,即最胖的那条分界线.下面开始一步步说怎么找到largest-margin separating hyperplane. 接下来,林特意强调了变量表示符号的变化,原来的W0换成了b(这样的表示利于推导:觉得这种强调非常负责任,利于学生听懂,要不然符号换来换去的,谁知道你说的是啥) 既然目标是找larger-margin s

Support vector machine

https://en.wikipedia.org/wiki/Support_vector_machine In machine learning, support vector machines (SVMs, also support vector networks[1]) are supervised learning models with associated learning algorithms that analyze data used for classification and

机器学习技法(1)--Linear Support Vector Machine

线性支持向量机. 在这种分类问题中,我们需要选一条最“胖”的线,而这条最胖的线就是margin largest的线. 我们的优化目标就是最大化这个margin.也就是在最小化每一个点到这条线的距离.这个距离怎么计算呢? 为了以后不会混淆,w0就不整合成向量w了,另外取一个新名字b.同样地,x0=1也就不用塞进x向量里了. 所以得出:h(x)=sign(wTx+b),而距离distance(x,b,w)满足wTx'+b=0 x'和x''是平面上的两个点,(x''–x')是平面上的向量,如果这个平面

stanford coursera 机器学习编程作业 exercise 6(支持向量机-support vector machines)

在本练习中,先介绍了SVM的一些基本知识,再使用SVM(支持向量机 )实现一个垃圾邮件分类器. 在开始之前,先简单介绍一下SVM ①从逻辑回归的 cost function 到SVM 的 cost function 逻辑回归的假设函数如下: hθ(x)取值范围为[0,1],约定hθ(x)>=0.5,也即θT·x  >=0时,y=1:比如hθ(x)=0.6,此时表示有60%的概率相信 y 等于1 显然,要想让y取值为1,hθ(x)越大越好,因为hθ(x)越大,y 取值为1的概率也就越大,也即:更

【Dual Support Vector Machine】林轩田机器学习技法

这节课内容介绍了SVM的核心. 首先,既然SVM都可以转化为二次规划问题了,为啥还有有Dual啥的呢?原因如下: 如果x进行non-linear transform后,二次规划算法需要面对的是d`+1维度的N个变量,以及N个约束 如果d`的维度超大,那么二次规划解起来的代价就太大了.因此,SVM的精髓就在于做了如下的问题转化: 不需要问太深奥的数学,知道为啥要dual的motivation就可以了. 这里再次搬出前人的智慧:Lagrange Multipliers 但是这里跟ridge regr