文档章节

SVM分类器之核函数

稀疏矩阵
 稀疏矩阵
发布于 2017/08/21 10:13
字数 1905
阅读 26
收藏 1

       之前一直在讨论的线性分类器,器如其名,只能对线性可分的样本做处理。如果提供的样本线性不可分,结果很简单,线性分类器的求解程序会无限循环,永远也解不出来。这必然使得它的适用范围大大缩小,而它的很多优点我们实在不原意放弃,怎么办呢?是否有某种方法,让线性不可分的数据变得线性可分呢?

       有!其思想说来也简单,来用一个二维平面中的分类问题作例子,你一看就会明白。事先声明,下面这个例子是网络早就有的,我一时找不到原作者的正确信息,在此借用,并加进了我自己的解说而已。

例子是下面这张图:

       我们把横轴上端点a和b之间红色部分里的所有点定为正类,两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么?不能,因为二维空间里的线性函数就是指直线,显然找不到符合条件的直线。

       但我们可以找到一条曲线,例如下面这一条:

      显然通过点在这条曲线的上方还是下方就可以判断点所属的类别(你在横轴上随便找一点,算算这一点的函数值,会发现负类的点函数值一定比0大,而正类的一定比0小)。这条曲线就是我们熟知的二次曲线,它的函数表达式可以写为:

       问题只是它不是一个线性函数,但是,下面要注意看了,新建一个向量y和a:

       这样g(x)就可以转化为f(y)=<a,y>,你可以把y和a分别回带一下,看看等不等于原来的g(x)。用内积的形式写你可能看不太清楚,实际上f(y)的形式就是:

g(x)=f(y)=ay

      在任意维度的空间中,这种形式的函数都是一个线性函数(只不过其中的a和y都是多维向量罢了),因为自变量y的次数不大于1。

      看出妙在哪了么?原来在二维空间中一个线性不可分的问题,映射到四维空间后,变成了线性可分的!因此这也形成了我们最初想解决线性不可分问题的基本思路——向高维空间转化,使其变得线性可分。

       而转化最关键的部分就在于找到x到y的映射方法。遗憾的是,如何找到这个映射,没有系统性的方法(也就是说,纯靠猜和凑)。具体到我们的文本分类问题,文本被表示为上千维的向量,即使维数已经如此之高,也常常是线性不可分的,还要向更高的空间转化。其中的难度可想而知。

       用一个具体文本分类的例子来看看这种向高维空间映射从而分类的方法如何运作,想象一下,我们文本分类问题的原始空间是1000维的(即每个要被分类的文档被表示为一个1000维的向量),在这个维度上问题是线性不可分的。现在我们有一个2000维空间里的线性函数

f(x’)=<w’,x’>+b

       注意向量的右上角有个 ’哦。它能够将原问题变得可分。式中的 w’和x’都是2000维的向量,只不过w’是定值,而x’是变量(好吧,严格说来这个函数是2001维的,哈哈),现在我们的输入呢,是一个1000维的向量x,分类的过程是先把x变换为2000维的向量x’,然后求这个变换后的向量x’与向量w’的内积,再把这个内积的值和b相加,就得到了结果,看结果大于阈值还是小于阈值就得到了分类结果。

       你发现了什么?我们其实只关心那个高维空间里内积的值,那个值算出来了,分类结果就算出来了。而从理论上说, x’是经由x变换来的,因此广义上可以把它叫做x的函数(有一个x,就确定了一个x’,对吧,确定不出第二个),而w’是常量,它是一个低维空间里的常量w经过变换得到的,所以给了一个w 和x的值,就有一个确定的f(x’)值与其对应。这让我们幻想,是否能有这样一种函数K(w,x),他接受低维空间的输入值,却能算出高维空间的内积值<w’,x’>?

       如果有这样的函数,那么当给了一个低维空间的输入x以后,

g(x)=K(w,x)+b

f(x’)=<w’,x’>+b

      这两个函数的计算结果就完全一样,我们也就用不着费力找那个映射关系,直接拿低维的输入往g(x)里面代就可以了(再次提醒,这回的g(x)就不是线性函数啦,因为你不能保证K(w,x)这个表达式里的x次数不高于1哦)。

       万幸的是,这样的K(w,x)确实存在(发现凡是我们人类能解决的问题,大都是巧得不能再巧,特殊得不能再特殊的问题,总是恰好有些能投机取巧的地方才能解决,由此感到人类的渺小),它被称作核函数(核,kernel),而且还不止一个,事实上,只要是满足了Mercer条件的函数,都可以作为核函数。核函数的基本作用就是接受两个低维空间里的向量,能够计算出经过某个变换后在高维空间里的向量内积值。

        回想我们求一个线性分类器,它的形式应该是:

       现在这个就是高维空间里的线性函数(为了区别低维和高维空间里的函数和向量,我改了函数的名字,并且给w和x都加上了 ’),我们就可以用一个低维空间里的函数(再一次的,这个低维空间里的函数就不再是线性的啦)来代替,

       又发现什么了?f(x’) 和g(x)里的α,y,b全都是一样一样的!这就是说,尽管给的问题是线性不可分的,但是我们就硬当它是线性问题来求解,只不过求解过程中,凡是要求内积的时候就用你选定的核函数来算。这样求出来的α再和你选定的核函数一组合,就得到分类器啦!

明白了以上这些,会自然的问接下来两个问题:

1. 既然有很多的核函数,针对具体问题该怎么选择?

2. 如果使用核函数向高维空间映射后,问题仍然是线性不可分的,那怎么办?

       第一个问题现在就可以回答你:对核函数的选择,现在还缺乏指导原则!各种实验的观察结果(不光是文本分类)的确表明,某些问题用某些核函数效果很好,用另一些就很差,但是一般来讲,径向基核函数是不会出太大偏差的一种,首选。

本文转载自:http://www.blogjava.net/zhenandaci

共有 人打赏支持
稀疏矩阵
粉丝 2
博文 9
码字总数 2847
作品 0
初识机器学习——吴恩达《Machine Learning》学习笔记(十二)

支持向量机(Support Vector Machines) 优化目标(Optimization objective) SVM与logistic回归 SVM假设函数 直观上对大间隔的理解(Large Margin Intuition) SVM也被称为大间距分类器,SVM代价函...

Ta来自江湖
08/06
0
0
《Scikit-Learn与TensorFlow机器学习实用指南》第5章 支持向量机

第5章 支持向量机 来源:ApacheCN《Sklearn 与 TensorFlow 机器学习实用指南》翻译项目 译者:@QiaoXie 校对:@飞龙 支持向量机(SVM)是个非常强大并且有多种功能的机器学习模型,能够做线性...

wizardforcel
04/24
0
0
Scikit-learn实战之SVM分类

Support vector machines (SVMs) 是一系列的有监督的学习方法,主要用于分类、回归和异常点检测。 1. SVM的主要优点如下: 在高维空间有效; 当样本空间的维度比样本数高时任然有效; 使用训...

u013709270
2016/11/27
0
0
支持向量机基本原理及在基因数据中的实践

这是一个梗,懂的人才能get到笑点 关于这个同学举牌子的典故我知道,我也是CMU的。这是在2009年在Pittsburgh举行的G20峰会现场外面。很多反对G20的,支持G20的都来凑热闹。我们这位同学也来了...

真依然很拉风
2017/07/29
0
0
BAT面试必考算法题之专项题目(1-10)

值此秋招之际,特推出BAT面试必考算法系列,助力大家步入互联网大厂。今天是专项题目1道到10道 本文是天善智能签约讲师 张龙祥老师的课程Hellobi Live | 数据分析岗位面试经验分享 课件,未经...

天善智能
08/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

C++ gflags

gflags是google一个开源的处理命令行参数的库,相比getopt,更加容易使用。 定义参数 gflags主要支持的参数类型包括 DEFINEbool: boolean DEFINEint32: 32-bit integer DEFINEint64: 64-bit ...

SibylY
27分钟前
0
0
intellij IDEA Properties中文unicode转码问题

在IDEA中创建了properties文件,发现默认中文不会自动进行unicode转码。如下 在project settings - File Encoding,在标红的选项上打上勾,确定即可 效果图如下: unicode转码后效果...

muzi1994
27分钟前
0
0
Java IO类库之PipedWriter

一、PipedWriter介绍 PipedWriter是字符管道输出流,继承自Writer,功能与PipedOutputStream类似,通过与PipedReader组合使用实现类似管道的功能,在多线程环境下,一个线程使用PipedWriter...

老韭菜
32分钟前
0
0
精简分页组件(手写)

需要引入CSS(没错就是这4行) .pagelist { text-align: center; color: #666; width: 100%; clear: both; margin: 20px 0; padding-top: 20px }.pagelist a { color: #666; margin: 0 2px;......

AK灬
32分钟前
3
0
29 岁成为阿里巴巴 P8,工作前 5 年完成晋升 3 连跳,他如何做到?

泡泡是我的好朋友。今年 31 岁,毕业后就进了阿里巴巴,工作五年内从 P4 晋升至 P6、P7、P8。 和他很少聊到工作,但总觉得他有很棒的职场心得,应该分享出来,于是有了这次采访。希望对职场新...

Java填坑之路
34分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部