9.1 支持向量机算法概述

www.reddit.com 上面有个非常有趣的帖子,Lvhhh用白话文解释了支持向量机算法,非常形象,下面摘录一下。

某日,见蓝球(深色)红球(浅色)于一桌欲分之,见图9-1。

图9-1 红蓝球故事1

插一筷子于蓝红球之间则蓝红球可分,见图9-2。

图9-2 红蓝球故事2

未料,随着球之增多,一红球出界毁吾之分割,见图9-3。可惜可气。

图9-3 红蓝球故事3

不服,遂变化筷子方向则又可分红蓝球也,见图9-4。

图9-4 红蓝球故事4

终有体会,欲合理分清红蓝之球,必使得近处红蓝球于筷子越远越好。

他日,又偶遇众红蓝球,见图9-5,吾又欲分之。

图9-5 红蓝球故事5

拿筷子比划半天无从分离,百思不得其解。遂大怒,猛一拍桌。

见桌上之球于空中仿佛有可分之势,蓝上红下。大喜,顺势抽一张纸隔于蓝红球之间,则蓝红之球可分也,见图9-6。

图9-6 红蓝球故事6

遂可得:若于桌面上不可分(二维),则拍桌,将球腾空而起(三维),则可分之。

支持向量机(Support Vector Machine,SVM)是机器学习领域使用最广泛的算法之一,其原理如图9-7所示,通常用来进行模式识别、分类以及回归分析,它特别适合安全世界里面的非黑即白,所以我们重点介绍与分类相关的知识。

图9-7 SVM原理图

假设只有二维的特征向量,我们需要解决一个分类问题,需要通过将正常用户和黑客区分开来,如果确实可以通过一条直线区分,那么这个问题成为可以线性可区分(linear separable),如果不行则成为不可线性区分(linear inseparable)。讨论最简单的情况,假设这个分类问题是可以线性区分的,那么这个区分的直线成为超平面,距离超平面最近的样本成为支持向量(Supprot Verctor)。

图9-8 SVM从二维平面升级到三维平面

如图9-8所示,对于不可线性区分的情况,需要升级到更高的平面进行区分,比如二维平面搞不定就需要升级到三维平面来区分,这个升级就需要依靠核函数。SVM通过一个非线性映射,把样本空间映射到一个高维乃至无穷维的特征空间中(Hilbert空间),使得在原来的样本空间中非线性可分问题转化为在特征空间中的线性可分问题。简单地说,就是升维和线性化。升维,就是把样本向高维空间做映射,一般情况下这会增加计算的复杂性,甚至会引起“维数灾难”,因而人们很少问津。但是作为分类、回归等问题,很可能在低维样本空间无法线性处理的样本集,在高维特征空间中却可以通过一个线性超平面实现线性划分(或回归)。一般的升维都会带来计算的复杂化,SVM方法巧妙地解决了这个难题:应用核函数的展开定理,就不需要知道非线性映射的显式表达式;由于是在高维特征空间中建立线性学习机,所以与线性模型相比,不但几乎不增加计算的复杂性,而且在某种程度上避免了“维数灾难”。这一切要归功于核函数的展开和计算理论。

选择不同的核函数,可以生成不同的SVM,常用的核函数有以下四种:

·线性核函数K(x,y)=x·y。

·多项式核函数K(x,y)=[(x·y)+1]^d。

·径向基函数K(x,y)=exp(-|x-y|^2/d^2)。

·二层神经网络核函数K(x,y)=tanh(a(x·y)+b)。