支持向量机原理 ppt

支持向量机
2014-2-21
-
1
本讲主要内容
一. 支持向量机
二. 最大间隔分类器
三. 核函数
四.软间隔优化
五.支持向量机总结
-
2
一. SVM— warming up
1.1 SVM概念简介 1.2 超平面 1.3 logistic回归 1.4 形式化表示 1.5 函数间隔与几何间隔
-
16
2.3 最大间隔分类器
重新回到SVM的优化问题：
我们将约束条件改写为：
-
17
2.3 最大间隔分类器
从KKT条件得知只有函数间隔是1（离超平面最近的
点）的线性约束式前面的系数 ，也就是说这些约
束式
，对于其他的不在线上的点( )，极值
不会在他们所在的范围内取得，因此前面的系数 .
注意每一个约束式实际就是一个训练样本。
-
6
1.3 logistic回归
形式化表示：
x 假是设n函维数特为征：向h 量(，x)函数g(gTx就) 是1leo1 giTsxtic 函数。
其图中像如g图(z)所示1：1ez 可以看到，将无穷映 射到了(0,1)
-
7
1.4 形式化表示
结果标签是y=-1,y=1，替换logistic回归中的y=0和y=1。
利用拉格朗日公式变换：
令
知
-
14
2.2拉格朗日对偶之不等式约束
原来要求的min f(w)可以转换成
求了。
利用对偶求解:
D的意思是对偶，
将问题转化为先求拉格朗日关
于w的最小值，将α和β看作是固定值。之后在
求最大值的话：
-
15
2.2拉格朗日对偶之不等式约束
下面解释在什么条件下两者会等价。假设f和g都是凸 函数，h是仿射的。并且存在w使得对于所有的i， 。在这种假设下，一定存在 使得是 原问题的解 ， 是对偶问题的解。还有另外， 满足库恩-塔 克条件（Karush-Kuhn-Tucker, KKT condition），该 条件如下：
形式1： 形式2： 形式3：
-
12
2.2拉格朗日对偶之等式约束
问题：
目标函数是f(w)，通常解法是引入拉格朗日算子，这 里使用来表示β算子，得到拉格朗日公式为 ：
L是等式约束的个数。然后分别对w和β求偏导，使得 偏导数等于0，然后解出w和β。
-
13
2.2拉格朗日对偶之不等式约束
问题：
这就启示我们可以不必定义非线性映射Φ而直接在输 入空间中定义核函数K来完成非线性映射。
这样做的条件是：
1. 定义的核函数K能够对应于特征空间中的内积； 2. 识别方法中不需要计算特征空间中的矢量本身，而只须计算
计算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
定义核函数：Kx,yxty2，则：xtyKx,y
输入空间
特征空间
-
25
3.1 核函数简介
上个例子说明：特征空间中两个矢量之间的内积可以 通过定义输入空间中的核函数直接计算得到。
ቤተ መጻሕፍቲ ባይዱ
同时将替换成w和b。以前的
，其中认为 。现在我们替换 为b，后面
替换为
（ 即 ）。
我们只需考虑 的正负问题，而不用关心g(z)，因此我 们这里将g(z)做一个简化，将其简单映射到y=-1和y=1上。 映射关系如下：
-
8
1.5 函数间隔与几何间隔
定义函数间隔为：
x是特征，y是结果标签。i表示第i个样本。（这是单
的
最小值只与w和b有关。对w和b分别求偏导数。
-
20
2.3 最大间隔分类器
得到： 代入后，结果如下：
由于最后一项是0，因此简化为
-
21
2.3 最大间隔分类器
此时的拉格朗日函数只包含了变量。然而我们求出了 才能得到w和b。
接着是极大化的过程
-
22
2.3 最大间隔分类器
前面提到过对偶问题和原问题满足的几个条件，首先 由于目标函数和线性约束都是凸函数，而且这里不存 在等式约束h。存在w使得对于所有的i， 因此，
个样本） 全局函数间隔： 在训练样本上分类正例和负例确信度最小那个函数间隔
-
9
1.5 函数间隔与几何间隔
几何间隔：
全局几何间隔：
-
10
二. 最大间隔分类器
2.1 二次规划原问题建立
2.2 拉格朗日对偶 2.2.1 等式约束 2.2.1 不等式约束
2.3 最大间隔分类器
-
11
2.1 二次规划原问题建立
-
18
2.3 最大间隔分类器
实线是最大间隔超平面，假设×号的是正例，圆圈的 是负例。在虚线上的点就是函数间隔是1的点，那么他 们前面的系数 ，其他点都是 。这三个点称作支 持向量。构造拉格朗日函数如下：
-
19
2.3 最大间隔分类器
下面我们按照对偶问题的求解步骤来一步步进行，
首先求解
的最小值，对于固定的 ，
一定存在 使得 是原问题的解，是对偶问题的解。
在这里，求 就是 求了。
如果求出了 ， 原问题的解）。然后
根据即可求出w（也是 ，
即可求出b。即离超平面最近的正的函数间隔要等
于离超平面最近的负的函数间隔。
-
23
三. 核函数
3.1 核函数简介 3.2 核函数有效性判定
-
24
3.1 核函数简介
建立一个R2R3的非线性映射 :x1,x2t x1 2, 2x1x2,x2 2t
-
4
1.2 超平面
超平面H是从n维空间到n-1维空间的一 个映射子空间。
设d是n维欧式空间R中的一个非零向量， a是实数，则R中满足条件dX=a的点X所 组成的集合称为R中的一张超平面。
-
5
1.3 logistic回归
Logistic 回归目的是从特征学习出一个 0/1 分类模型，而这个模型是将特性的线 性组合作为自变量，由于自变量的取值 范围是负无穷到正无穷。因此，使用 logistic 函数（或称作 sigmoid 函数）将 自变量映射到(0,1)上，映射后的值被认 为是属于 y=1 的概率。
-
3
1.1 SVM概念简介
支持向量机（SVM）是 90 年代中期发展起来的基于统 计学习理论的一种机器学习方法，通过寻求结构化风 险最小来提高学习机泛化能力，实现经验风险和置信 范围的最小化，从而达到在统计样本量较少的情况下， 亦能获得良好统计规律的目的。
通俗来讲，它是一种二类分类模型，其基本模型定义 为特征空间上的间隔最大的线性分类器，即支持向量 机的学习策略便是间隔最大化，最终可转化为一个凸 二次规划问题的求解。