支持向量机讲解(很详细明了)学习资料
- 格式：docx
- 大小：453.01 KB
- 文档页数：17
下载文档原格式
合集下载
人工智能之支持向量机课件
对第 i 个训练点 x i, y i 引入松弛变量(Slack Variable) i 0 ,
把约束条件放松到 yiwxibi1。（即“软化” 约束条件）
1, lT
l
体现了训练集被错分的情况，可采用 i 作
i1
为一种度量来描述错划程度。
两个目标：1. 间隔
Definition: geometric margin: the margin
w
given by the canonical decision
function, which is when c=1/||w||
Strategy:
wx+b>0 wx+b<0
1) we need to maximise the geometric margin! (cf result from learning theory)
实质：找到一个把 R n 上的点分成两部分的规则.
2维空间上的分类问题) n维空间上的分类问题.
2019/11/14
14
分类学习方法
x 根据给定的训练集 T { ( ( y ) l
x x 其中，x i R n ,y i y { 1 , 1 } ,i 1 ,,l ，寻找 Rn 上的一个实
wx+b=0
2) subject to the constraint that training examples are classified correctly
2019/11/14
12
支持向量
2019/11/14
The training points that are nearest to the separating function are called support vectors. What is the output of our decision function for these points?
支持向量机SVMPPT课件
最后得出原空间中的二次曲线：
[w*
]1
2[w*
]2[
x]1
2[w*
]3[
x]2
2[w*
]4[
x]1[
x]2
[w*]5[
x]12
[w*]6[
x]2 2
b
0
21
-
22
-
应用
• SVM可以用来分类和预测 • 应用领域：
手写数字识别、 对象识别、 语音识别、 基准时间序列预测检验
23
-
8
-
SVM相关概念解释
9
-
SVM原理—数据线性可分
• 2个类的问题
设两类问题训练样本集为
(X1,y1), (X2,y2),…,(Xn,yn),其中
Xi∈Rn, yi={1,-1}, i=1,…,n，这
里线性可分就是指，存在着超 平面（Hyper-plane）直线
f(x) = wX+ b，使得训练样本 中的一类输入和另一类输入分 别位于该超平面的两侧.
[w]1[X ]1 2[w]2[X ]2 2[w]3[X ]3 2[w]4[X ]4 [w]5[X ]5 [w]6[X ]6 b 0
20
-
• 可见，只要利用变换，把 x 所在的2维空间的两类输入 点映射到 x 所在的6维空间，然后在这个6维空间中，使 用线性学习机求出分划超平面：
(w* x) b* 0，其中w* ([w*]1, [w*]6 )T
1
支持向量机SVM
-
主要内容
2
-
1.SVM简介 2.SVM相关概念解释 3.SVM原理
3.1线性可分 3.2线性不可分
3
-
支持向量机简介
[w*
]1
2[w*
]2[
x]1
2[w*
]3[
x]2
2[w*
]4[
x]1[
x]2
[w*]5[
x]12
[w*]6[
x]2 2
b
0
21
-
22
-
应用
• SVM可以用来分类和预测 • 应用领域：
手写数字识别、 对象识别、 语音识别、 基准时间序列预测检验
23
-
8
-
SVM相关概念解释
9
-
SVM原理—数据线性可分
• 2个类的问题
设两类问题训练样本集为
(X1,y1), (X2,y2),…,(Xn,yn),其中
Xi∈Rn, yi={1,-1}, i=1,…,n，这
里线性可分就是指，存在着超 平面（Hyper-plane）直线
f(x) = wX+ b，使得训练样本 中的一类输入和另一类输入分 别位于该超平面的两侧.
[w]1[X ]1 2[w]2[X ]2 2[w]3[X ]3 2[w]4[X ]4 [w]5[X ]5 [w]6[X ]6 b 0
20
-
• 可见，只要利用变换，把 x 所在的2维空间的两类输入 点映射到 x 所在的6维空间，然后在这个6维空间中，使 用线性学习机求出分划超平面：
(w* x) b* 0，其中w* ([w*]1, [w*]6 )T
1
支持向量机SVM
-
主要内容
2
-
1.SVM简介 2.SVM相关概念解释 3.SVM原理
3.1线性可分 3.2线性不可分
3
-
支持向量机简介
支持向量机课件
Transform x (x)
例子
a x12+b x22=1 [w]1 z1+ [w]2z2 + [w]3 z3+ b =0
非线性分类
设训练集 T {(xi , yi ), i 1, l}，其中 xi ([xi ]1,[xi ]2 )T , yi {1, 1} 假定可以用 ([x]1,[x]2 ) 平面上的二次曲线来划分：
i 0, i 1,, n
w
n
y这iix是i 一个凸二
i1 次规划问题
有唯一的最优
解Leabharlann (5)求解问题(5)，得。则参数对(w,b)可由下式计算：
n
w* *i yi xi i 1
b* w* n *i xi
i 1
n 2 *i yi 1
线性可分的支持向量(分类)机
于是，得到如下的决策函数：
12
45 6
求解 i (i=1, …, 5)
例子
通过二次规划求解，得到
1 0,2 2.5,3 0,4 7.333,5 4.833
– 支持向量为 {x2=2, x4=5, x5=6} 判别函数为
b 满足 f (2)=1, f (5) = -1, f (6)=1, 得到 b=9
在规范化下，超平面的几何间隔为
1 w
于是，找最大几何间隔的超平面
表述成如下的最优化问题：
min 1 w 2 w,b 2
(1)
s.t. yi ((w xi ) b) 1,i 1,, n
线性可分的支持向量(分类)机
为求解问题(1),使用Lagrange乘子法将其转化为对偶 问题。于是引入Lagrange函数：
如果想用其它的非线性分划办法，则可以考虑选择其它形式
例子
a x12+b x22=1 [w]1 z1+ [w]2z2 + [w]3 z3+ b =0
非线性分类
设训练集 T {(xi , yi ), i 1, l}，其中 xi ([xi ]1,[xi ]2 )T , yi {1, 1} 假定可以用 ([x]1,[x]2 ) 平面上的二次曲线来划分：
i 0, i 1,, n
w
n
y这iix是i 一个凸二
i1 次规划问题
有唯一的最优
解Leabharlann (5)求解问题(5)，得。则参数对(w,b)可由下式计算：
n
w* *i yi xi i 1
b* w* n *i xi
i 1
n 2 *i yi 1
线性可分的支持向量(分类)机
于是，得到如下的决策函数：
12
45 6
求解 i (i=1, …, 5)
例子
通过二次规划求解，得到
1 0,2 2.5,3 0,4 7.333,5 4.833
– 支持向量为 {x2=2, x4=5, x5=6} 判别函数为
b 满足 f (2)=1, f (5) = -1, f (6)=1, 得到 b=9
在规范化下，超平面的几何间隔为
1 w
于是，找最大几何间隔的超平面
表述成如下的最优化问题：
min 1 w 2 w,b 2
(1)
s.t. yi ((w xi ) b) 1,i 1,, n
线性可分的支持向量(分类)机
为求解问题(1),使用Lagrange乘子法将其转化为对偶 问题。于是引入Lagrange函数：
如果想用其它的非线性分划办法，则可以考虑选择其它形式
支持向量机原理 ppt课件
形式1： 形式2： 形式3：
2.2拉格朗日对偶之等式约束
问题：
目标函数是f(w)，通常解法是引入拉格朗日算子，这 里使用来表示β算子，得到拉格朗日公式为 ：
L是等式约束的个数。然后分别对w和β求偏导，使得 偏导数等于0，然后解出w和β。
2.2拉格朗日对偶之不等式约束
问题：
利用拉格朗日公式变换：
支持向量机
2014-2-21
本讲主要内容
一. 支持向量机 二. 最大间隔分类器 三. 核函数 四.软间隔优化 五.支持向量机总结
一. SVM— warming up
1.1 SVM概念简介 1.2 超平面 1.3 logistic回归 1.4 形式化表示 1.5 函数间隔与几何间隔
三. 核函数
3.1 核函数简介 3.2 核函数有效性判定
3.1 核函数简介
建立一个R2R3的非线性映射 :x1,x2t x1 2, 2x1x2,x2 2t
计算R3中2个矢量的内积：
x t y x 1 2 ,2 x 1 x 2 ,x 2 2y 1 2 ,2 y 1 y 2 ,y 2 2 t x t y 2
1.3 logistic回归
形式化表示：
x 假是设n函维数特为征：向h 量(，x)函数g(gTx就) 是1leo1 giTsxtic
函数。
其图中像如g图(z)所示1：1ez 可以看到，将无穷映 射到了(0,1)
1.4 形式化表示
结果标签是y=-1,y=1，替换logistic回归中的y=0和y=1。
1.1 SVM概念简介
支持向量机（SVM）是 90 年代中期发展起来的基于统 计学习理论的一种机器学习方法，通过寻求结构化风 险最小来提高学习机泛化能力，实现经验风险和置信 范围的最小化，从而达到在统计样本量较少的情况下， 亦能获得良好统计规律的目的。
2.2拉格朗日对偶之等式约束
问题：
目标函数是f(w)，通常解法是引入拉格朗日算子，这 里使用来表示β算子，得到拉格朗日公式为 ：
L是等式约束的个数。然后分别对w和β求偏导，使得 偏导数等于0，然后解出w和β。
2.2拉格朗日对偶之不等式约束
问题：
利用拉格朗日公式变换：
支持向量机
2014-2-21
本讲主要内容
一. 支持向量机 二. 最大间隔分类器 三. 核函数 四.软间隔优化 五.支持向量机总结
一. SVM— warming up
1.1 SVM概念简介 1.2 超平面 1.3 logistic回归 1.4 形式化表示 1.5 函数间隔与几何间隔
三. 核函数
3.1 核函数简介 3.2 核函数有效性判定
3.1 核函数简介
建立一个R2R3的非线性映射 :x1,x2t x1 2, 2x1x2,x2 2t
计算R3中2个矢量的内积：
x t y x 1 2 ,2 x 1 x 2 ,x 2 2y 1 2 ,2 y 1 y 2 ,y 2 2 t x t y 2
1.3 logistic回归
形式化表示：
x 假是设n函维数特为征：向h 量(，x)函数g(gTx就) 是1leo1 giTsxtic
函数。
其图中像如g图(z)所示1：1ez 可以看到，将无穷映 射到了(0,1)
1.4 形式化表示
结果标签是y=-1,y=1，替换logistic回归中的y=0和y=1。
1.1 SVM概念简介
支持向量机（SVM）是 90 年代中期发展起来的基于统 计学习理论的一种机器学习方法，通过寻求结构化风 险最小来提高学习机泛化能力，实现经验风险和置信 范围的最小化，从而达到在统计样本量较少的情况下， 亦能获得良好统计规律的目的。
超详细SVM（支持向量机）知识点
超详细SVM（支持向量机）知识点一. 简单概括一下SVM：SVM 是一种二类分类模型。
它的基本思想是在特征空间中寻找间隔最大的分离超平面使数据得到高效的二分类，具体来讲，有三种情况（不加核函数的话就是个线性模型，加了之后才会升级为一个非线性模型）：•当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；•当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；•当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。
二. SVM 为什么采用间隔最大化（与感知机的区别）：当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。
感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。
线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。
另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。
三. SVM的目标（硬间隔）：有两个目标：第一个是使间隔最大化，第二个是使样本正确分类，由此推出目标函数：稍微解释一下，w是超平面参数，目标一是从点到面的距离公式化简来的，具体不展开，目标二就相当于感知机，只是把大于等于0进行缩放变成了大于等于1，为了后面的推导方便。
有了两个目标，写在一起，就变成了svm的终极目标：四. 求解目标（硬间隔）：从上面的公式看出，这是一个有约束条件的最优化问题，用拉格朗日函数来解决。
上式的拉格朗日函数为：在满足Slater定理的时候，且过程满足KKT条件的时候，原问题转换成对偶问题：先求内部最小值，对和 b 求偏导数=0可得将其带入到上式中可以得到此时需要求解α ，利用SMO（序列最小优化）算法：五. 软间隔：不管直接在原特征空间，还是在映射的高维空间，我们都假设样本是线性可分的。
虽然理论上我们总能找到一个高维映射使数据线性可分，但在实际任务中，寻找一个合适的核函数核很困难。
支持向量机(SVM)原理详解
支持向量机（SVM）原理详解支持向量机(Support Vector Machine, SVM)是一种机器学习算法，用于二分类和多分类问题。
它的基本思想是寻找一个超平面，能够将不同类别的数据分隔开来，并且与最近的数据点之间的间隔最大。
一、原理概述：SVM的基本原理是将原始数据映射到高维空间中，使得在该空间中的数据能够线性可分，然后在高维空间中找到一个最优的超平面。
对于线性可分的情况，SVM通过最大化分类边界与最近数据点之间的距离，并将该距离定义为间隔，从而使分类边界具有更好的泛化能力。
二、如何确定最优超平面：1.线性可分的情况下：SVM寻找一个能够将不同类别的数据分开的最优超平面。
其中，最优超平面定义为具有最大间隔(margin)的超平面。
间隔被定义为超平面到最近数据点的距离。
SVM的目标是找到一个最大化间隔的超平面，并且这个超平面能够满足所有数据点的约束条件。
这可以通过求解一个凸二次规划问题来实现。
2.线性不可分的情况下：对于线性不可分的情况，可以使用一些技巧来将数据映射到高维空间中，使其线性可分。
这种方法被称为核技巧(kernel trick)。
核技巧允许在低维空间中计算高维空间的内积，从而避免了直接在高维空间中的计算复杂性。
核函数定义了两个向量之间的相似度。
使用核函数，SVM可以在高维空间中找到最优的超平面。
三、参数的选择：SVM中的参数有两个主要的方面：正则化参数C和核函数的选择。
1.正则化参数C控制了分类边界与数据点之间的权衡。
较大的C值将导致更少的间隔违规，增加将数据点分类正确的权重，可能会导致过拟合；而较小的C值将产生更宽松的分类边界，可能导致欠拟合。
2.核函数选择是SVM中重要的一步。
根据问题的特点选择合适的核函数能够更好地处理数据，常用的核函数有线性核函数、多项式核函数和高斯核函数等。
四、优缺点：SVM有以下几个优点：1.在灵活性和高扩展性方面表现出色，尤其是在高维数据集上。
2.具有良好的泛化能力，能够很好地处理样本数量较少的情况。
支持向量机资料
支持向量机资料支持向量机1基本情况Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。
其原理也从线性可分说起，然后扩展到线性不可分的情况。
甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机（Support Vector Machine，简称SVM）。
支持向量机的提出有很深的理论背景支持向量机方法是在近年来提出的一种新方法。
SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；⑵它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。
例子如图：将1维的“线性不可分”上升到2维后就成为线性可分了。
在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论。
2一般特征⑴SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。
而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。
⑵SVM通过最大化决策边界的边缘来控制模型的能力。
尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。
⑶通过对数据中每个分类属性引入一个哑变量，SVM可以应用于分类数据。
⑷SVM一般只能用在二类问题，对于多类问题效果不好。
3原理简介SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．简单地说，就是升维和线性化．升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津．但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）．一般的升维都会带来计算的复杂化，SVM 方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”．这一切要归功于核函数的展开和计算理论．选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种：⑴线性核函数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）．最优分类面：最优超平面SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用图2的两维情况说明。
支持向量机网络PPT资料优秀版
p
R(wl)
infR(w)
l w
p
Rem(pwl)liwnfR(w)
2.2 经验风险最小一致性原理(2/2)
➢ 也就是说如果经验风险最小化方法是一致性,那么它必须 提供一个函数序列L(y,wl),l=1,2,…,使得期望风险和经验 风险收敛到一个可能的最小的风险值.
目录
引言 统计学习理论的基本理论 支持向量机 核函数 支持向量机优化方法 支持向量机方法小结 支持向量机应用领域和研究进展 Support Vector Regression 参考文献
目录(1/1)
1 引言(1/13)
1 引言
基于数据的机器学习是现代智能技术中的重要方面,其本质就 是从观测数据出发寻找统计规律,并对未来进行预测. ➢ 人的智慧中一个很重要的方面是从实例学习的能力,通过 对已知事实的分析总结出规律,预测不能直接观测的事实。 ✓ 在这种学习中,重要的是要能够举一反三,即利用学习 得到的规律,不但可以较好地解释已知的实例,而且能 够对未来的现象或无法观测的现象做出正确的预测 和判断。 ✓ 我们把这种能力叫做泛化（推广）能力。
1 引言(4/13)
✓ 但在实际问题中,样本数往往是有限的,有时还十分有 限。
❖ 虽然人们实际上一直知道这一点，但传统上仍以 样本数目无穷多为假设来推导各种算法，希望这 样得到的算法在样本较少时也能有较好的(至少 是可接受的)表现。
✓ 因此当样本数有限时,一些本来在样本数目无穷多为 假设来推导的,理论上很优秀的学习方法实际中表现 却可能不尽人意,可能表现出很差的泛化能力。
➢ SVM becomes popular because of its success in handwritten digit recognition
支持向量机简介PPT课件
经验风险最小化思想图示
举例：神经网络的构造过程
先确定网络结构 ：网络层数，每层节点数 相当于VC维确定， (n / h) 确定。
通过训练确定最优权值，相当于最小化 R emp ( w ) 。 目前存在的问题是神经网络结构的确定大多是凭经验
选取，有一定的盲目性，无法确定泛化的置信界限， 所以无法保证网络的泛化能力。 即使经验误差很小，但可能推广或泛化能力很差。这 就是神经网络中的过学习难题。
研究小样本下机器学习规律的理论。 基本思想：折衷考虑经验风险和推广的置信界
限，取得实际期望风险的最小化。 两大核心： VC维和结构风险最小化。
VC维的概念
描述函数复杂性的指标 假如存在一个由h个样本的样本集能够被一个
函数集中的函数按照所有可能的2h 种形式分 为两类，则函数集能够把样本数为h的样本集 打散(shattering)。函数集的vc维就是用这个函 数集中的函数所能够打散的最大样本集数的样 本数目。
X表示成
x
xp
r
||
w w
||
xp ：x在H上的投影向量 r：是x到H的垂直距离
g (x ) w T (x p r||w w ||) b w T x p b r|w |w T w || r||w g ||(x)w wT /(|x |wp ||：r||是w w w||)方b 向 上w T 的xp单b 位 向r|w |量w Tw ||r||w ||
Support Vector Machine支持向量机简介
报告概览
系统辨识和模式识别问题一般描述及存在问题 统计学习理论基本思想 支持向量机算法
➢ 线性可分 ➢ 近似线性可分 ➢ 非线性可分
SVM软件包 故障诊断中的应用
支持向量机课件
（SVM ）最优分类面SVM 是从线性可分情况下的最优分类面发展而来的, 基本思想可用图中的 两维情况说明.所谓最优分类线就是要求分类线不但能将两类正确分开(训练错误率为0),而且使分类间隔最大，推广到高维空间，最优分类线就变为最优分类面。
设线性可分的样本集(),,1,,,i i x y i n = {},1,1dx R y ∈∈+-，d 维空间中的线性判别函数：()g x wx b =+，分类面方程为0wx b +=我们可以对它进行归一化，使得所有样本都满足()1g x ≥，即使离分类面最近的样本满足()1g x =，这样分类间隔就等于2w 。
因此要求分类间隔最大，就是要求w （或2w ）最小。
要求分类线对所有样本正确分类时，对于任意学习样本()n n y X ，其分布必然在直线1H 之上或直线2H 之下。
即有()()121;1, 1;1, n n n n n n n n g b y C g b y C ⎧=⋅+≥=∈⎨=⋅+≤-=-∈⎩X W X X X W X X 将以上两式合并，有1n n y b ⋅⎡⋅+⎤≥⎣⎦W X就是要求满足[]10n n y wx b +-≥，1,,,i n =图中, 方形点和圆形点代表两类样本, H 为分类线,H1, H2分别为过各类中离分类线最近的样本且平行于分类线的直线, 它们之间的距离叫做分类间隔(margin)。
所谓最优分类线就是要求分类线不但2w 最小的分类面就是最优分类面。
过两类样本中离分类面最近的点且平行于最优分类面的超平面1H ，2H 上的训练样本，就是使上式等号成立的那些样本，它们叫做支持向量。
因为它们支撑了最优分类面。
下面看如何求解最优分类面，由上面的讨论，最优分类面问题可以表示成如下的约束问题，即在条件（1）的约束下，求函数：21()2w w φ= （2） 的最小值，这里目标函数中的21没有其他意义，只是为了下一步导出求解方法时方便。
由此得到两类分类机算法：(1). 给定学习样本集(){}Nn n n y 1 ,=X ，d R X ∈n 、{}1- ,1+∈n y 。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
支持向量机讲解(很详细明了) 精品文档
收集于网络，如有侵权请联系管理员删除 w支持向量机: Maximum Margin Classifier by pluskid, on 2010-09-08, in Machine Learning 84 comments 支持向量机即 Support Vector Machine，简称 SVM 。我最开始听说这头机器的名号的时候，一种神秘感就油然而生，似乎把 Support 这么一个具体的动作和 Vector 这么一个抽象的概念拼到一起，然后再做成一个 Machine ，一听就很玄
了！
不过后来我才知道，原来 SVM 它并不是一头机器，而是一种算法，或者，确切地说，是一类算法，当然，这样抠字眼的话就没完没了了，比如，我说 SVM 实际上是一个分类器 (Classifier) ，但是其实也是有用 SVM 来做回归 (Regression) 的。所以，这种字眼就先不管了，还是从分类器说起吧。
SVM 一直被认为是效果最好的现成可用的分类算法之一（其实有很多人都相信，“之一”是可以去掉的）。这里“现成可用”其实是很重要的，因为一直以来学术界和工业界甚至只是学术界里做理论的和做应用的之间，都有一种“鸿沟”，有些很 fancy 或者很复杂的算法，在抽象出来的模型里很完美，然而在实际问题上却显得很脆弱，效果很差甚至完全 fail 。而 SVM 则正好是一个特例——在两边都混得开。
好了，由于 SVM 的故事本身就很长，所以废话就先只说这么多了，直接入题吧。当然，说是入贴，但是也不能一上来就是 SVM ，而是必须要从线性分类器
开始讲。这里我们考虑的是一个两类的分类问题，数据点用 x 来表示，这是一
个 n 维向量，而类别用 y 来表示，可以取 1 或者 -1 ，分别代表两个不同的类（有些地方会选 0 和 1 ，当然其实分类问题选什么都无所谓，只要是两个不同的数字即可，不过这里选择 +1 和 -1 是为了方便 SVM 的推导，后面就会明了
了）。一个线性分类器就是要在 n 维的数据空间中找到一个超平面，其方程可以表示为
一个超平面，在二维空间中的例子就是一条直线。我们希望的是，通过这个超平面可以把两类数据分隔开来，比如，在超平面一边的数据点所对应的 y 全是
-1 ，而在另一边全是 1 。具体来说，我们令 f(x)=wTx+b ，显然，如果 f(x)=0 ，那么 x 是位于超平面上的点。我们不妨要求对于所有满足 f(x)<0 的点，其对应的 y 等于 -1 ，而 f(x)>0 则对应 y=1 的数据点。当精品文档 收集于网络，如有侵权请联系管理员删除 然，有些时候（或者说大部分时候）数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在，不过关于如何处理这样的问题我们后面会讲，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超
平面是存在的。 如图所示，两种颜色的点分别代表两个类别，红颜色的线表示一个可行的超平
面。在进行分类的时候，我们将数据点 x代入 f(x) 中，如果得到的结果小于
0 ，则赋予其类别 -1 ，如果大于 0 则赋予类别 1 。如果 f(x)=0，则很难办了，分到哪一类都不是。事实上，对于 f(x) 的绝对值很小的情况，我们都很难处理，因为细微的变动（比如超平面稍微转一个小角度）就有可能导致结果类别的改变。理想情况下，我们希望 f(x) 的值都是很大的正数或者很小的负数，这样我们就能更加确信它是属于其中某一类别的。
从几何直观上来说，由于超平面是用于分隔两类数据的，越接近超平面的点越“难”分隔，因为如果超平面稍微转动一下，它们就有可能跑到另一边去。反
之，如果是距离超平面很远的点，例如图中的右上角或者左下角的点，则很容易分辩出其类别。 精品文档
收集于网络，如有侵权请联系管理员删除 实际上这两个 Criteria 是互通的，我们定义 functional margin 为 γˆ=y(wTx+b)=yf(x)，注意前面乘上类别 y 之后可以保证这个 margin 的非
负性（因为 f(x)<0 对应于 y=−1 的那些点），而点到超平面的距离定义为 geometrical margin 。不妨来看看二者之间的关系。如图所示，对于一个
点 x ，令其垂直投影到超平面上的对应的为 x0 ，由于 w 是垂直于超平面的一个向量（请自行验证），我们有
又由于 x0 是超平面上的点，满足 f(x0)=0 ，代入超平面的方程即可算出
不过，这里的 γ 是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别 y即可，因此实际上我们定义 geometrical margin 为：
显然，functional margin 和 geometrical margin 相差一个 ∥w∥ 的缩放因子。按照我们前面的分析，对一个数据点进行分类，当它的 margin 越大的时候，分类的 confidence 越大。对于一个包含 n 个点的数据集，我们可以很自然
地定义它的 margin 为所有这 n 个点的 margin 值中最小的那个。于是，为了使得分类的 confidence 高，我们希望所选择的 hyper plane 能够最大化这个 margin 值。
不过这里我们有两个 margin 可以选，不过 functional margin 明显是不太适合用来最大化的一个量，因为在 hyper plane 固定以后，我们可以等比例地缩精品文档 收集于网络，如有侵权请联系管理员删除 放 w 的长度和 b 的值，这样可以使得 f(x)=wTx+b 的值任意大，亦即 functional margin γˆ 可以在 hyper plane 保持不变的情况下被取得任意大，而 geometrical margin 则没有这个问题，因为除上了 ∥w∥ 这个分母，所以缩放 w 和 b 的时候 γ˜ 的值是不会改变的，它只随着 hyper plane 的变动而变动，因此，这是更加合适的一个 margin 。这样一来，我们的 maximum margin classifier 的目标函数即定义为
当然，还需要满足一些条件，根据 margin 的定义，我们有
其中 ，根据我们刚才的讨论，即使在超平面固定的情况下，γˆ 的值也可以随着 ∥w∥ 的变化而变化。由于我们的目标就是要确定超平
面，因此可以把这个无关的变量固定下来，固定的方式有两种：一是固定 ∥w∥ ，当我们找到最优的 γ˜ 时 γˆ 也就可以随之而固定；二是反过来固定 γˆ ，
此时 ∥w∥ 也可以根据最优的 γ˜ 得到。处于方便推导和优化的目的，我们选择第二种，令 γˆ=1 ，则我们的目标函数化为：
通过求解这个问题，我们就可以找到一个 margin 最大的 classifier ，如下图所示，中间的红色线条是 Optimal Hyper Plane ，另外两条线到红线的距离都是
等于 γ˜ 的： 精品文档
收集于网络，如有侵权请联系管理员删除 到此为止，算是完成了 Maximum Margin Classifier 的介绍，通过最大化 margin ，我们使得该分类器对数据进行分类时具有了最大的 confidence （实
际上，根据我们说给的一个数据集的 margin 的定义，准确的说，应该是“对最不 confidence 的数据具有了最大的 confidence”——虽然有点拗口）。不过，到现在似乎还没有一点点 Support Vector Machine 的影子。很遗憾的是，这个要等到下一次再说了，不过可以先小小地剧透一下，如上图所示，我们可以看到 hyper plane 两边的那个 gap 分别对应的两条平行的线（在高维空间中也应该是两个 hyper plane）上有一些点，显然两个 hyper plane 上都会有点存在，
否则我们就可以进一步扩大 gap ，也就是增大 γ˜ 的值了。这些点呢，就叫做 support vector ，嗯，先说这么多了。 精品文档
收集于网络，如有侵权请联系管理员删除 支持向量机: Support Vector by pluskid, on 2010-09-10, in Machine Learning 49 comments 本文是“支持向量机系列”的第二篇，参见本系列的其他文章。 上一次介绍支持向量机，结果说到 Maximum Margin Classifier ，到最后都没有说“支持向量”到底是什么东西。不妨回忆一下上次最后一张图： 精品文档
收集于网络，如有侵权请联系管理员删除 可以看到两个支撑着中间的 gap 的超平面，它们到中间的 separating hyper plane 的距离相等（想想看：为什么一定是相等的？），即我们所能得到的最
大的 geometrical margin γ˜ 。而“支撑”这两个超平面的必定会有一些点，试想，如果某超平面没有碰到任意一个点的话，那么我就可以进一步地扩充中间的 gap ，于是这个就不是最大的 margin 了。由于在 n 维向量空间里一个点实际上是和以原点为起点，该点为终点的一个向量是等价的，所以这些“支撑”的点便叫做支持向量。 很显然，由于这些 supporting vector 刚好在边界上，所以它们是满
足 y(wTx+b)=1 （还记得我们把 functional margin 定为 1 了吗？），而对于
所有不是支持向量的点，也就是在“阵地后方”的点，则显然有 y(wTx+b)>1 。事实上，当最优的超平面确定下来之后，这些后方的点就完全成了路人甲了，它们可以在自己的边界后方随便飘来飘去都不会对超平面产生任何影响。这样的特性在实际中有一个最直接的好处就在于存储和计算上的优越性，例如，如果使用 100 万个点求出一个最优的超平面，其中是 supporting vector 的有 100 个，那么我只需要记住这 100 个点的信息即可，对于后续分类也只需要利用这 100 个点而不是全部 100 万个点来做计算。（当然，通常除了 K-Nearest Neighbor 之类的 Memory-based Learning 算法，通常算法也都不会直接把所有的点记忆下来，并全部用来做后续 inference 中的计算。不过，如果算法使用了 Kernel 方法进行非线性化推广的话，就会遇到这个问题了。Kernel 方法在下一次会介绍。）