Support Vector Machines

Presentation on theme: "Support Vector Machines"— Presentation transcript:

1 Support Vector Machines
第三讲 Support Vector Machines 支持向量机

2 引 子 2

3 相关参考资料 统计学习理论的本质，Vladimir N. Vapnik 著， 张学工译，清华大学出版社，2000.09
支持向量机导论，N.Cristianini, J.Shawe-Taylor著，电子工业出版社， Support Vector Classification. Steven Gunn.(518/54.29) Bernhard Scholkopf, Alex J. Smola , CHRISTOPHER J.C. BURGES 3

4 1、支持向量机可以做什么？ 支持向量机的应用之一：手写体数字识别 目前最好的识别水平： LeNet 4 多项式支持向量机
（错误率<0.7%） （错误率<0.8%） NIST手写体数字的前100个 4

5 1、支持向量机可以做什么？ 支持向量机的应用之二：性别识别 SVM 男或女 5

6 1、支持向量机可以做什么？ 支持向量机的应用之三：行人检测 6

7 2、支持向量机的提出 问题1：支持向量机为什么会有如此好的性能？ 问题2：何为最优分类面？
它追求的不仅仅是得到一个能将两类样本分开的分类面，而是要得到一个最优的分类面。 To be No.1 问题2：何为最优分类面？ 7

8 2、支持向量机的提出 参考标准：使错分样本数目最少 错分样本数最少 错分训练样本数最少 缺陷1：错分训练样本数目对判别函数的好坏评估不够精细
8

9 2、支持向量机的提出 缺陷2：拥有较少的错分训练样本数的判别函数未必就是一个好的判别函数 9

10 2、支持向量机的提出 支持向量机的标准：使margin尽可能大 margin :两类样本到分类面的最短距离之和 10

11 3、支持向量机的数学模型 a. 线性支持向量机的数学模型 设所求的分类面表达式为： 该分类面若能将训练样本线性分开，则： 上式可简写为：
相当于令函数间隔为1，这样就方便推导。 Ref:关于SVM一篇比较全介绍的博文 支持向量机SVM（一） jerrylead博客 对于有限个数的样本，存在 即： 其中， 11

12 问题：若将分类面（w,b）对应的margin记为 ，则
在上述约束条件下，SVM的求解 则是最大化margin的过程。 问题：若将分类面（w,b）对应的margin记为 ，则 12

13 综上所述，线性SVM的数学模型可以描述为：
给定训练样本集 利用线性SVM求解线性分类面本质上是求解如下优化问题： 优化目标 约束条件 13

14 b.支持向量机的求解 一般的优化问题模型： 支持向量机的优化模型： 14

15 b.支持向量机的求解：拉格朗日对偶法 Step1：构造Lagrange函数 Step2: 求解Lagrange函数的鞍点
求解L(w , b ;α)关于w和b的最小值，关于α的最大值，即： 15

16 Step 3 代入Lagrange函数，得到原始问题的对偶问题：
对L(w , b ;α)关于w和b求偏导，得： Step 3 代入Lagrange函数，得到原始问题的对偶问题： 16

17 具体推导可以参考相关博文 17

18 原始问题 对偶问题 原始问题与对偶问题解的关系： 支持向量机的判别函数：
因为对于非支持向量alpha i 为0，因此，相当于新的x和所有的支持向量作内积运算，然后乘系数alphi，再求和。 支持向量机的判别函数： 18 18

19 Karush-Kuhn-Tucker（KKT）条件与支持向量
对偶问题的解 是最优解的条件： ，它将使得 对于取值不为零的 对于这样的样本，我们称为支持向量（Support Vectors） 19

20 SVM的解的表达式可以重写为： 最优超平面是支持向量的线性组合 支持向量机的判别函数： 20

21 线性SVM求解:例子 x1 =(0, 0)T, y1 = +1 x2 =(1, 0)T, y2 = +1
代入x,y值

22 线性SVM求解:例子 x1 =(0, 0)T, y1 = +1 x2 =(1, 0)T, y2 = +1
课堂练习

23 可调用Matlab中的二次规划程序，求得1, 2, 3, 4的值，进而求得w和b的值。
代入(3/2,0),(0,3/2)点可以知道 思考：当数据量很大的时候怎么办？

24 二、SVM的Matlab工具箱使用指南 1.训练SVM: [nsv, alpha, b0] = svc(X,Y,ker,C)
X：训练样本的输入特征，X的行数为训练样本的个数，X的列数代表训练样本的特征维数； Y：训练样本对应的标号，为一个列矩阵。矩阵的行数为样本的个数。Y的值只能是1或者-1； Ker:核函数类型，常用的包括:’linear’，’ poly’，’rbf’ C：经验风险与结构风险的权衡参数，详见SVM的数学优化模型。 nsv：支持向量的个数； alpha：对偶问题的解； b0：svm表达式中的偏移量。

25 2.测试SVM: preY = svcoutput(trnX,trnY,tstX,ker,alpha,bias)
alpha - SVM的求解结果 bias - SVM的偏移量

26 3.核函数参数的设置: svkernel.m switch lower(ker) case 'linear' k = u*v';
case 'poly' p1=2; k = (u*v' + 1)^p1; case 'rbf‘ p1=1; k = exp(-(u-v)*(u-v)'/(2*p1^2)); case 'sigmoid‘ p1=1;p2=1; k = tanh(p1*u*v'/length(u) + p2); otherwise end

27 4.在二维坐标中绘制SVM的训练和测试结果:
svcplot(X,Y,ker,alpha,bias) 其中： X 训练样本的输入特征 Y 训练样本的标号 ker - 核函数 alpha - SVM的求解结果 bias - SVM的偏移量

28 利用SVM的Matlab工具箱进行印签提取的示例程序
ker=‘linear’; %选择线性核函数 [nsv alpha bias]=svc(trnx,trny,ker,10); %训练SVM svcplot(trnx,trny,ker,alpha, bias); %显示分类器效果 load fisheriris xdata = meas(51:end,3:4); group = species(51:end); svmStruct = svmtrain(xdata,group,'showplot',true);

29 利用SVM的Matlab工具箱进行印签提取的示例程序
tstnum=1; for i=1:size(RGB,1) for j=1:size(RGB,2) testx=double(RGB(i,j,1:2)); preY=svcoutput(trnx,trny,testx,ker,alpha,bias); tstnum=tstnum+1; if (preY==1) resIm(i,j)=255; else resIm(i,j)=0; end imshow(resIm);

30

31 三、SVM的C语言编程介绍 1.求解SVM的两个开源开发包： 2. 利用SVM的C语言程序直接进行分类器的训练和测试：
Libsvm: SVM-light： 2. 利用SVM的C语言程序直接进行分类器的训练和测试： <label> <index1>:<value1> <index2>:<value2> ... 例： 1 1:67 2:66 3:72 4:72 5:59 6:71 7:54 8:67 9:79 -1 1:101 2:108 3:100 4:99 5:102 6:95 7:93 8:96 9:89

32 使用说明 训练结果

33 3. 利用SVM的C语言开发包编写自己的SVM分类器：
svm_model *svm_train(const svm_problem *prob, const svm_parameter *param) double svm_predict(const svm_model *model, const svm_node *x) struct svm_problem{ int l; double *y; struct svm_node **x;}; struct svm_node{ int index; double value;}; 1 1: : : : : : : : struct svm_parameter{ int svm_type; int kernel_type; double degree; // for poly double gamma; // for poly/rbf/sigmoid double coef0; // for poly/sigmoid // these are for training only double cache_size; // in MB double eps; // stopping criteria double C; int nr_weight; int *weight_label; double* weight; // for C_SVC double nu; // for NU_SVC, ONE_CLASS, and NU_SVR double p; // for EPSILON_SVR int shrinking; // use the shrinking heuristics };

34 svm_parameter param; // parameter int nr_class; // number of classes
struct svm_model{ svm_parameter param; // parameter int nr_class; // number of classes int l; // total #SV svm_node **SV; // SVs (SV[l]) double **sv_coef; // coefficients for SVs in decision functions double *rho; // constants in decision int *label; // label of each class (label[n]) int *nSV; // number of SVs for each class (nSV[n]) int free_sv; // 1 if svm_model is created by svm_load_model // 0 if svm_model is created by svm_train }; svm_type c_svc kernel_type linear nr_class 2 total_sv 239 rho label 1 -1 nr_sv SV 1 1: : : : : : : : 1 1: : : : : : : : : : : : : : : : : : : : : : : :

35 SVM For Nonlinear Problems
35

36 内容提要 1.如何解决少量非线性可分样本？ 2.如何解决大量非线性可分样本？ 3.核函数方法（Kernel Trick）
4.SVM背后的统计学习理论 36

37 1. 线性SVM求解含少量非线性可分样本的思想
基本思想：通过训练误差和类间宽度之间的权衡，得到一个最优超平面。 1.少量样本非线性可分 2.少数outlier影响分隔超平面的最优求取

38 1. 线性SVM求解含少量非线性可分样本的思想
优化目标： 权衡因子 约束条件： 松弛变量 注: 1、松弛变量是允许数据点偏离函数边界的量 2、C是惩罚因子，其值越大表明离群点对目标函数影响越大，也就是越不希望看到离群点。

39 模型修改后，拉格朗日公式也要修改如下：

40 类似的，通过Lagrange函数，转化为对偶问题
1类样本：位于分类间隔之外 1类样本 2类样本：支持向量 在两条间隔线外的点前面的系数为0，离群样本点前面的系数为C，而支持向量的样本点前的系数在（0，c）上。 2类样本 3类样本：位于分类间隔之内 3类样本 40

41 不同的权衡因子得到的不同的分类面 C＝1000 C＝10

42 2.非线性支持向量机 当线性支持向量机划分样本会产生过多训练误差时，需要考虑使用非线性分类面对两类样本进行划分。

43 2.1 寻找非线性问题的三种思路 思路1:原空间法 在原空间中直接求解非线性问题

44 将非线性问题的求解转换成另一个空间中的线性问题求解
思路2 :特征空间法 将非线性问题的求解转换成另一个空间中的线性问题求解 例1：XOR问题

45 例2：物种分类问题

46 寻找特征映射Ф所面临的问题： 1. 特征映射Ф的确定往往需要相当高的技巧和相当专业的领域知识； 2. 特征映射Ф的计算可能会相当复杂；
3. 特征映射Ф往往是一个低维向高维映射的过程，这个映射过程经常面临维数灾难。

47 思路3. 核函数方法 构建到特征空间的隐式映射 判别函数： 结 论： 优化问题：
样本之间的内积 判别函数： 结 论： 构建支持向量机只需要知道任意两个样本之间的内积定义，无需知道样本点自身的特征表示

48 2.2 线性SVM通过核函数扩展为非线性SVM 线性SVM:

49 其中 通过求解如下的优化问题得到： 利用核函数将非线性问题转化为线性问题的手段和方法称之为核函数方法。

50 例：XOR问题中我们构造了一个非线性映射实现了特征的升维：
样本点在新的特征空间中的内积为： 核函数描述了样本点在经过某种特征变换后，在新的特征空间中的内积。

51 核函数 线性支持向量机 非线性支持向量机 优化问题： 判别函数： 利用支持向量机求解异或问题的结果示意图

52 3 核函数方法 3.1 核函数的定义 定义 核函数是一个对称函数，对所有的 满足： 这里 是从X到内积特征空间F 的映射。
定义 核函数是一个对称函数，对所有的 满足： 这里 是从X到内积特征空间F 的映射。 Mercer定理 对于任意的对称函数 且 有 ，它是某个 特征空间中的内积运算的充分必要条件是，对于任意的

53 常用的核函数： 推论 令X是有限输入空间，K(x , z)是X上的对称函数。那么K(x , z)是核函数的充要条件是矩阵： 是半正定的。
多项式核函数 高斯核函数 sigmoid核函数

54 3.2 核函数的构造 令K1和K2是X*X上的核，f(∙)是X上的一个实值函数。B是一个对称半正定矩阵。那么下面的函数是核函数：
3.2 核函数的构造 令K1和K2是X*X上的核，f(∙)是X上的一个实值函数。B是一个对称半正定矩阵。那么下面的函数是核函数： 从核函数中构造 从特征中构造 从相似性度量中构造

55 3.4 如何选择核函数 问题1： 何谓一个好的核函数？ 好的核函数能够真实反映样本间的远近关系。
3.4 如何选择核函数 问题1： 何谓一个好的核函数？ 好的核函数能够真实反映样本间的远近关系。 问题2： 如何判断核函数是否真实的反映的样本间的远近关系？ 比较难！但是初步判断核函数是否真实反映了训练样本之间的远近关系还是可能的。 核函数的选择策略： 选择能够真实反映训练样本远近关系的核函数。

56 问题3：训练样本间的远近关系如何表达？ 物理含义：两个属于同类的样本相似度为1，不同类的样本相似度为0。 问题4：核函数与训练样本间的远近关系的一致性评估 利用矩阵的相似性度量：

57 3.4 关于核函数方法的评述 功能：采用核映射技术，将非线性问题转化为一个线性问题的非线性数据处理方法。核的使用使得将数据隐式表达为特征空间并越过本来需要的特征映射的计算成为可能。 适用条件：如果某个线性问题的求解过程只与样本间的点积相关，则可以采用核函数方法将该线性问题的求解过程推广到非线性问题。 Kernel trick：将所有的计算转变为向量间的点积运算。

58 3.5 核函数方法的应用示例：PCA KPCA PCA的作用：发现数据分布的主要方向 PCA的常用功能： 特征降维 数据压缩 去除噪声
只能得到样本分布的线性主方向

59 PCA求解步骤 Step 1：样本中心化，使得 Step 2：求解中心化后的样本的协方差矩阵 Step 3：求解协方差矩阵的特征值和特征向量，其中最大特征值对应的特征向量即为主方向。 对应的特征向量 为主方向

60 KPCA：基于核函数的非线性主成分分析 Step 1：样本中心化，使得 Step 2：求解中心化后的样本的协方差矩阵 Step 3：求解协方差矩阵的特征值和特征向量 不妨设所求的特征向量为： 则根据特征向量的定义，有：

61 展开后，得到： 根据核函数的定义，有： 其中K为核函数对应的的Gram矩阵。考虑到其逆存在，故： 解该方程得到 即可得到特征空间中的主分量 样本在主方向的投影可表示为：

62 利用PCA得到的主分量重建结果 利用KPCA得到的主分量重建结果

63 KPCA与其它方法的对比

64 KPCA的去噪功能（USPS） Patterns Linear PCA Kernel PCA 7291 train 2007 test
Size: 16 x 16 Linear PCA Kernel PCA

65 3.6 核函数方法在其它方面的应用 Kernel Fisher Discriminant Analysis
3.6 核函数方法在其它方面的应用 Kernel Fisher Discriminant Analysis Kernel K-Means Clustering Kernel Independent Component Analysis ……

66 3.7 核函数方面的研究 Parameters’ selection for Multi-Kernel
3.7 核函数方面的研究 Parameters’ selection for Multi-Kernel Constructing Special Kernel for Special Applications Data Driven Kernel Construction

67 问题： 1.如果已知特征映射 则该特征映射 对应的核函数是？ 2.给定两类样本：(0,0),(1,1);(1,0),(0,1) 求在核函数 导出的特征空间中两类 样本中心间的距离。

68 总 结 支持向量机带给我们的启示： 要学会描述一个问题；要学会用优化模型描述一个问题；要学会用便于求解的优化模型描述一个问题。
总 结 支持向量机带给我们的启示： 要学会描述一个问题；要学会用优化模型描述一个问题；要学会用便于求解的优化模型描述一个问题。 要学会转化问题；要学会将陌生的问题转换成熟悉的问题；要学会将陌生的问题转换成便于求解的熟悉的问题。 68