最优间隔分类器(optimal margin classifier)
重新回到SVM的优化问题:
我们将约束条件改写为:
从KKT条件得知只有函数间隔是1(离超平面最近的点)的线性约束式前面的系数,也就是说这些约束式,对于其他的不在线上的点(),极值不会在他们所在的范围内取得,此时前面的系数。注意每一个约束式实际就是一个训练样本。
看下面的图:
实线是最大间隔超平面,假设×号的是正例,圆圈的是负例。在虚线上的点就是函数间隔是1的点,那么他们前面的系数,其他点都是。这三个点称作支持向量。构造拉格朗日函数如下:
注意到这里只有没有是因为原问题中没有等式约束,只有不等式约束。
下面我们按照对偶问题的求解步骤来一步步进行,
首先求解的最小值,对于固定的,的最小值只与w和b有关。对w和b分别求偏导数。
并得到
将上式带回到拉格朗日函数中得到,此时得到的是该函数的最小值(目标函数是凸函数)
代入后,化简过程如下:
最后得到
由于最后一项是0,因此简化为
这里我们将向量内积表示为
此时的拉格朗日函数只包含了变量。然而我们求出了才能得到w和b。
接着是极大化的过程,
前面提到过对偶问题和原问题满足的几个条件,首先由于目标函数和线性约束都是凸函数,而且这里不存在等式约束h。存在w使得对于所有的i,。因此,一定存在使得是原问题的解,是对偶问题的解。在这里,求就是求了。
如果求出了,根据即可求出w(也是,原问题的解)。然后
即可求出b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。
关于上面的对偶问题如何求解,可参见SMO算法。
这里考虑另外一个问题,由于前面求解中得到
我们通篇考虑问题的出发点是,根据求解得到的,我们代入前式得到
也就是说,以前新来的要分类的样本首先根据w和b做一次线性运算,然后看求的结果是大于0还是小于0,来判断正例还是负例。现在有了,我们不需要求出w,只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说,与前面所有的样本都做运算是不是太耗时了?其实不然,我们从KKT条件中得到,只有支持向量的,其他情况。因此,我们只需求新来的样本和支持向量的内积,然后运算即可。这种写法为下面要提到的核函数(kernel)做了很好的铺垫。
4. SVM分类器求解(2)的更多相关文章
-
3. SVM分类器求解(1)——Lagrange duality
先抛开上面的二次规划问题,先来看看存在等式约束的极值问题求法,比如下面的最优化问题: 目标函数是f(w),下面是等式约束.通常解法是引入拉格朗日算子,这里使用来表示算子,得到拉格朗日公式为 是等式约束 ...
-
机器学习经典算法详解及Python实现--基于SMO的SVM分类器
原文:http://blog.csdn.net/suipingsp/article/details/41645779 支持向量机基本上是最好的有监督学习算法,因其英文名为support vector ...
-
菜鸟之路——机器学习之SVM分类器学习理解以及Python实现
SVM分类器里面的东西好多呀,碾压前两个.怪不得称之为深度学习出现之前表现最好的算法. 今天学到的也应该只是冰山一角,懂了SVM的一些原理.还得继续深入学习理解呢. 一些关键词: 超平面(hyper ...
-
自己训练SVM分类器进行HOG行人检测
正样本来源是INRIA数据集中的96*160大小的人体图片,使用时上下左右都去掉16个像素,截取中间的64*128大小的人体. 负样本是从不包含人体的图片中随机裁取的,大小同样是64*128(从完全不 ...
-
Python图像处理(15):SVM分类器
快乐虾 http://blog.csdn.net/lights_joy/ 欢迎转载,但请保留作者信息 在opencv中支持SVM分类器.本文尝试在python中调用它. 和前面的贝叶斯分类器一样,SV ...
-
线性SVM分类器实战
1 概述 基础的理论知识参考线性SVM与Softmax分类器. 代码实现环境:python3 2 数据处理 2.1 加载数据集 将原始数据集放入"data/cifar10/"文件夹 ...
-
SVM分类器实现实例
我正在做一个关于SVM的小项目,在我执行验证SVM训练后的模型的时候,得到的report分数总是很高,无论是召回率(查全率).精准度.还是f1-score都很高: 图1 分类器分数report 但是, ...
-
大数据-10-Spark入门之支持向量机SVM分类器
简介 支持向量机SVM是一种二分类模型.它的基本模型是定义在特征空间上的间隔最大的线性分类器.支持向量机学习方法包含3种模型:线性可分支持向量机.线性支持向量机及非线性支持向量机.当训练数据线性可分时 ...
-
支持向量机 (SVM)分类器原理分析与基本应用
前言 支持向量机,也即SVM,号称分类算法,甚至机器学习界老大哥.其理论优美,发展相对完善,是非常受到推崇的算法. 本文将讲解的SVM基于一种最流行的实现 - 序列最小优化,也即SMO. 另外还将讲解 ...
随机推荐
-
jQuery的选择器中的通配符[id^='code'] 等示例及说明
1.选择器 (1)通配符: $("input[id^='code']");//id属性以code开始的所有input标签 $("input[id$='code']&quo ...
-
Apache Spark源码剖析
Apache Spark源码剖析(全面系统介绍Spark源码,提供分析源码的实用技巧和合理的阅读顺序,充分了解Spark的设计思想和运行机理) 许鹏 著 ISBN 978-7-121-25420- ...
-
常用天气预报API接口整理(转)
文章转自:http://www.nohacks.cn/post-35.html 自序: 由nohacks.cn 收集整理,来源于网络,版权归原作者所有,基本收集了网络上能使用的大部分天气API接口,作 ...
-
springmvc 中RequestMapping注解的使用
1.RequestMapping注解既可以修饰方法,又可以修饰类型,类型指定的url相对于web跟路径,而方法修饰的url相对于类url: 2.RequestMapping的几个属性: value:用 ...
-
Java内存分配全面浅析(转)
原文引自CSDN: 本文将由浅入深详细介绍Java内存分配的原理,以帮助新手更轻松的学习Java.这类文章网上有很多,但大多比较零碎.本文从认知过程角度出发,将带给读者一个 ...
-
关于在HTML中使用的script标签
本文是<JavaScript高级程序设计>(第三版)中的第二章的个人学习的总结. 在HTML中使用JavaScript <script>标签 在HTML5中script主要有以 ...
-
痞子衡嵌入式:飞思卡尔i.MX RT系列MCU启动那些事(4)- Flashloader初体验(blhost)
大家好,我是痞子衡,是正经搞技术的痞子.今天痞子衡给大家介绍的是飞思卡尔i.MX RT系列MCU的Flashloader. 在上一篇文章 Serial Downloader模式(sdphost, mf ...
-
Cocos 2d TestCPP 学习
Cocos 2d testcpp包含了大量的demo, 对于新手学习cocos引擎具有非常大的帮助.因为接下来的开发项目有可能会用到该引擎,所以希望可以利用自己的业余时间提前熟悉起来.该篇文章会记录自 ...
-
3.Appium处理原生与H5的嵌套
环境前置准备 手机与电脑USB连接,开启USB调试模式,通过adb devices可查看到此设备. 电脑端.移动端安装chrome浏览器.(尽量保证移动端chrome版本低于电脑端) App webv ...
-
EventFiringWebDriver网页事件监听(一)
Selenium提供了很多的event listening functions来跟踪脚本执行过程中的events. How it works? 在注册了listener的webDriver里面,这些l ...