支持向量机（SVM ）原理及应用 一、SVM 的产生与发展 自1995年Vapnik (瓦普尼克)在统计学习理论的基础上提出SVM 作为模式识别的新方法之后，SVM 一直倍受关注。同年，Vapnik 和Cortes 提出软间隔(soft margin)SVM ，通过引进松弛变量i ξ度量数据i x 的误分类(分类出现错误时i ξ大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM 的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年，Vapnik 等人又提出支持向量回归 (Support Vector Regression ，SVR)的方法用于解决拟合问题。SVR 同SVM 的出发点都是寻找最优超平面(注：一维空间为点；二维空间为线；三维空间为面；高维空间为超平面。)，但SVR 的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston 等人根据SVM 原理提出了用于解决多类分类的SVM 方法(Multi-Class Support Vector Machines ，Multi-SVM)，通过将多类分类转化成二类分类，将SVM 应用于多分类问题的判断：此外，在SVM 算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens 提出的最小二乘支持向量机 (Least Square Support Vector Machine ，LS —SVM)算法，Joachims 等人提出的SVM-1ight ，张学工提出的中心支持向量机 (Central Support Vector Machine ，CSVM)，Scholkoph 和Smola 基于二次规划提出的v-SVM 等。此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM 的典型应用进行总结，并设计开发出较为完善的SVM 工具包，也就是LIBSVM(A Library for Support Vector Machines)。LIBSVM 是一个通用的SVM 软件包，可以解决分类、回归以及分布估计等问题。 二、支持向量机原理 SVM 方法是20世纪90年代初Vapnik 等人根据统计学习理论提出的一种新的机器学习方法，它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该子集中的判别函数，使学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。 支持向量机的基本思想：首先，在线性可分情况下，在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输
支持向量机 一、SVM的想法 回到我们最开始讨论的KNN算法，它占用的内存十分的大，而且需要的运算量也非常大。那么我们有没有可能找到几个最有代表性的点(即保留较少的点)达到一个可比的效果呢? 我们先看下面一个例子：假设我们的训练集分为正例与反例两类，分别用红色的圆圈与蓝色的五角星表示，现在出现了两个未知的案例，也就是图中绿色的方块，我们如何去分类这两个例子呢? 在KNN算法中我们考虑的是未知样例与已知的训练样例的平均距离，未知样例与正例和反例的“距离”谁更近，那么他就是对应的分类。 同样是利用距离，我们可以换一个方式去考虑：假设图中的红线是对正例与反例的分类标准(记为w x+b=0)，那么我们的未知样例与红线的“距离”就成了一个表示分类信度的标准，而w y+b(y为未知样例的数据)的符号则可以看成是分类的标识。 但是遗憾的是我们不知道这样的一条分类标准(分类线)是什么，那么我们一个比较自然的想法就是从已知的分类数据(训练集)里找到离分割线最近的点，确保他们离分割面尽可能的远。这样我们的分类器会更稳健一些。 从上面的例子来看，虚线穿过的样例便是离分割线最近的点，这样的点可能是不唯一的，因为分割线并不确定，下图中黑线穿过的训练样例也满足这个要求：
所以“他们离分割面尽可能的远”这个要求就十分重要了，他告诉我们一个稳健的超平面是红线而不是看上去也能分离数据的黄线。 这样就解决了我们一开始提出的如何减少储存量的问题，我们只要存储虚线划过的点即可(因为在w x+b=-1左侧，w x+b=1右侧的点无论有多少都不会影响决策)。像图中虚线划过的，距离分割直线(比较专业的术语是超平面)最近的点，我们称之为支持向量。这也就是为什么我们这种分类方法叫做支持向量机的原因。 至此，我们支持向量机的分类问题转化为了如何寻找最大间隔的优化问题。 二、SVM的一些细节 支持向量机的实现涉及许多有趣的细节：如何最大化间隔，存在“噪声”的数据集怎么办，对于线性不可分的数据集怎么办等。 我这里不打算讨论具体的算法，因为这些东西完全可以参阅july大神的《支持向量机通俗导论》，我们这里只是介绍遇到问题时的想法，以便分析数据时合理调用R中的函数。 几乎所有的机器学习问题基本都可以写成这样的数学表达式： 给定条件：n个独立同分布观测样本(x1 , y1 ), (x2 , y2 ),……,(xn , yn )
算法四：支持向量机 说到支持向量机，必须要提到july大神的《支持向量机通俗导论》，个人感觉再怎么写也不可能写得比他更好的了。这也正如青莲居士见到崔颢的黄鹤楼后也只能叹“此处有景道不得”。不过我还是打算写写SVM的基本想法与libSVM中R的接口。 一、SVM的想法 回到我们最开始讨论的KNN算法，它占用的内存十分的大，而且需要的运算量也非常大。那么我们有没有可能找到几个最有代表性的点(即保留较少的点)达到一个可比的效果呢? 要回答这个问题，我们首先必须思考如何确定点的代表性?我想关于代表性至少满足这样一个条件：无论非代表性点存在多少，存在与否都不会影响我们的决策结果。显然如果仍旧使用KNN算法的话，是不会存在训练集的点不是代表点的情况。那么我们应该选择一个怎样的“距离”满足仅依靠代表点就能得到全体点一致的结果? 我们先看下面一个例子：假设我们的训练集分为正例与反例两类，分别用红色的圆圈与蓝色的五角星表示，现在出现了两个未知的案例，也就是图中绿色的方块，我们如何去分类这两个例子呢?
在KNN算法中我们考虑的是未知样例与已知的训练样例的平均距离，未知样例与正例和反例的“距离”谁更近，那么他就是对应的分类。 同样是利用距离，我们可以换一个方式去考虑：假设图中的红线是对正例与反例的分类标准(记为w x+b=0)，那么我们的未知样例与红线的“距离”就成了一个表示分类信度的标准，而w y+b(y为未知样例的数据)的符号则可以看成是分类的标识。 但是遗憾的是我们不知道这样的一条分类标准(分类线)是什么，那么我们一个比较自然的想法就是从已知的分类数据(训练集)里找到离分割线最近的点，确保他们离分割面尽可能的远。这样我们的分类器会更稳健一些。 从上面的例子来看，虚线穿过的样例便是离分割线最近的点，这样的点可能是不唯一的，因为分割线并不确定，下图中黑线穿过的训练样例也满足这个要求：
支持向量机（SVM ）简明学习教程 一、最优分类超平面 给定训练数据),(,),,(11l l y x y x ，其中n i R x ∈，}1,1{-∈i y 。 若1=i y ，称i x 为第一类的，I ∈i x ；若1-=i y ，称i x 为第二类的，II ∈i x 。 若存在向量?和常数b ，使得?????II ∈<-I ∈>-i i T i i T x if b x x if b x ,0,0?? （1），则该训练集可被超平面 0=-b x T ?分开。 （一）、平分最近点法 求两个凸包集中的最近点d c ,'，做d c ,'的垂直平分面x ，即为所求。 02 )(2 22 2 =-- -?-=-d c x d c x d x c T ，则d c -=?，2 ) ()(d c d c b T +-= 。 求d c ,，?? ?? ?≥==≥==∑∑∑∑-=-===. 0,1, . 0,1,1 111 i y i y i i i y i y i i i i i i x d x c αα ααα α
所以2 1 1 2 ∑∑-==-= -i i y i i y i i x x d c αα，只需求出最小的T l ),,(1ααα =。 算法：1）求解. 0,1,1..2121min 1 1 2 12 11≥===-∑∑∑∑∑-===-==i y i y i l i i i i y i i y i i i i i i t s x y x x αααααα；2）求最优超平面0=-b x T ?。 （二）、最大间隔法 附加条件1=?，加上（1）式。记C x C i T x i >=I ∈??min )(1，C x C i T x i <=II ∈??max )(2。 使?????II ∈<-I ∈>-=-= i i T i i T x if b x x if b x t s C C ,0,0,1..2 ) ()()(max 21??????ρ （2） 可以说明在（2）下可以得到一个最优超平面，且该超平面是唯一的。 如何快速生成一个最优超平面？？？ 考虑等价问题：求权向量w 和b ，使?????II ∈-<-I ∈>-i i T i i T x if b x w x if b x w ,1,1，且?最小。 这种写法已经包含最大间隔。 事实上b C C C x if C b x w x if C b x w i i T i i T =+=??????II ∈=+-))()((21),(1),(121021????中心，而w w =?， 故w b C = ，w C C 1 2)()()(21=-=???ρ。 所以（2）式可以转化为求解： 1 )(..min ≥-b x w y t s w i T i （3） 总结，求最优超平面，只需求解： 1 )(..2 1)(min ≥-= Φb x w y t s w w w i T i T （QP1） 对（QP1）构造lagrange 函数： 令∑=---=l i i T i i b x w y w b w L 1 2]1)([21),,(αα，其中0),,(1≥=T l ααα 为lagrange 乘子。 下求L 的鞍点：
支持向量机算法推导及其分类的算法实现 摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。简述核函数的概念，以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足，提出SVM 的改进版本DAG SVM。 Abstract：This article begins with a linear classification problem, Gradually discuss formation of SVM, and their derivation. Description the concept of kernel function, and the core position in SVM algorithm. Describes the reasons for the introduction of slack variables, and propose soft-margin linear classification. Summary the application of SVM in one-to-one and one-to-many linear classification. Based on SVM shortage in one-to-many problems, an improved version which called DAG SVM was put forward. 关键字：SVM、线性分类、核函数、松弛变量、DAG SVM 1. SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。 对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM 的精髓。高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。
模式识别课程大作业报告——支持向量机（SVM）的实现 ： 学号： 专业： 任课教师： 研究生导师：
容摘要 支持向量机是一种十分经典的分类方法，它不仅是模式识别学科中的重要容，而且在图像处理领域中得到了广泛应用。现在，很多图像检索、图像分类算法的实现都以支持向量机为基础。本次大作业的容以开源计算机视觉库OpenCV 为基础，编程实现支持向量机分类器，并对标准数据集进行测试，分别计算出训练样本的识别率和测试样本的识别率。 本报告的组织结构主要分为3大部分。第一部分简述了支持向量机的原理；第二部分介绍了如何利用OpenCV来实现支持向量机分类器；第三部分给出在标准数据集上的测试结果。
一、支持向量机原理概述 在高维空间中的分类问题实际上是寻找一个超平面，将两类样本分开，这个超平面就叫做分类面。两类样本中离分类面最近的样本到分类面的距离称为分类间隔。最优超平面指的是分类间隔最大的超平面。支持向量机实质上提供了一种利用最优超平面进行分类的方法。由最优分类面可以确定两个与其平行的边界超平面。通过拉格朗日法求解最优分类面，最终可以得出结论：实际决定最优分类面位置的只是那些离分类面最近的样本。这些样本就被称为支持向量，它们可能只是训练样本中很少的一部分。支持向量如图1所示。 图1
图1中，H是最优分类面，H1和H2别是两个边界超平面。实心样本就是支持向量。由于最优超平面完全是由这些支持向量决定的，所以这种方法被称作支持向量机（SVM）。 以上是线性可分的情况，对于线性不可分问题，可以在错分样本上增加一个惩罚因子来干预最优分类面的确定。这样一来，最优分类面不仅由离分类面最近的样本决定，还要由错分的样本决定。这种情况下的支持向量就由两部分组成：一部分是边界支持向量；另一部分是错分支持向量。 对于非线性的分类问题，可以通过特征变换将非线性问题转化为新空间中的线性问题。但是这样做的代价是会造成样本维数增加，进而导致计算量急剧增加，这就是所谓的“维度灾难”。为了避免高维空间中的计算，可以引入核函数的概念。这样一来，无论变换后空间的维数有多高，这个新空间中的线性支持向量机求解都可以在原空间通过核函数来进行。常用的核函数有多项式核、高斯核（径向基核）、Sigmoid函数。 二、支持向量机的实现 OpenCV是开源计算机视觉库，它在图像处理领域得到了广泛应用。OpenCV中包含许多计算机视觉领域的经典算法，其中的机器学习代码部分就包含支持向量机的相关容。OpenCV中比较经典的机器学习示例是“手写字母分类”。OpenCV中给出了用支持向量机实现该示例的代码。本次大作业的任务是研究OpenCV中的支持向量机代码，然后将其改写为适用于所有数据库的通用程序，并用标准数据集对算法进行测试。本实验中使用的OpenCV版本是2.4.4，实验平台为Visual Studio 2010软件平台。 OpenCV读取的输入数据格式为“.data”文件。该文件记录了所有数据样
支持向量机通俗导论（理解SVM的三层境界） 在本文中，你将看到，理解SVM分三层境界， ?第一层、了解SVM(你只需要对SVM有个大致的了解，知道它是个什么东西便已足够)； ?第二层、深入SVM(你将跟我一起深入SVM的内部原理，通宵其各处脉络，以为将来运用它时游刃有余)； ?第三层、证明SVM(当你了解了所有的原理之后，你会有大笔一挥，尝试证明它的冲动)； 第一层、了解SVM 1.0、什么是支持向量机SVM 然在进入第一层之前，你只需了解什么是支持向量机SVM就够了，而要明白什么是SVM，便得从分类说起。 分类作为数据挖掘领域中一项非常重要的任务，目前在商业上应用最多(比如分析型CRM里面的客户分类模型，客户流失模型，客户盈利等等，其本质上都属于分类问题)。而分类的目的则是学会一个分类函数或分类模型(或者叫做分类器)，该模型能吧数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知类别。 其实，若叫分类，可能会有人产生误解，以为凡是分类就是把一些东西或样例按照类别 给区分开来，实际上，分类方法是一个机器学习的方法，分类也成为模式识别，或者在概率统计中称为判别分析问题。 你甚至可以想当然的认为，分类就是恰如一个商场进了一批新的货物，你现在要根据这些货物的特征分门别类的摆放在相关的架子上，这一过程便可以理解为分类，只是它由训练有素的计算机程序来完成。 说实话，上面这么介绍分类可能你不一定内心十分清楚。我来举个例子吧，比如心脏病的确诊中，如果 我要完全确诊某人得了心脏病，那么我必须要进行一些高级的手段，或者借助一些昂贵的机器，那么若我 们没有那些高科技医疗机器怎么办？还怎么判断某人是否得了心脏病呢？ 当然了，古代中医是通过望、闻、问、切“四诊”，但除了这些，我们在现代医学里还是可以利用一些比 较容易获得的临床指标进行推断某人是否得了心脏病。如作为一个医生，他可以根据他以往诊断的病例对 很多个病人(假设是500个)进行彻底的临床检测之后，已经能够完全确定了哪些病人具有心脏病，哪些没
SVM 支持向量机 目录 一、简介 (1) 二、线性分类器 (3) 三、分类间隔指标 (4) 四、线性分类器的求解 (8) 五、核函数 (9) 六、松弛变量 (11) 七、惩罚因子C (15) 八、SVM用于多类分类 (17) 九、SVM的计算复杂度 (19) 一、简介 支持向量机在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础 上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力）。 以下逐一分解并解释一下：统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，用传统的机器学习方法构造分类系统是一种技巧，一个人做的结果可能很好，另一个人差不多的方法做出来却很差，缺乏指导和原则。 VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。SVM关注的是VC维，和样本的维数是无关（甚至样本可以是上万维的，这使得SVM很适合用于解决文本分类的问题，也因此引入了核函数）。 结构风险最小：机器学习本质上就是对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型作为假设），而真实模型是未知的。假设与问题真实解之间的误差，叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设（即分类器）之后，我们可以用某些可以掌握的量来逼近误差，最直观的方法就是使用分类器在样本数据上的分类的结果与真实结果（样本是已标注过的数据，即准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。
. . 实验报告 实验名称：机器学习：线性支持向量机算法实现 学员：张麻子学号： *********** 培养类型：硕士年级： 专业：所属学院：计算机学院 指导教员： ****** 职称：副教授 实验室：实验日期：
. . 一、实验目的和要求 实验目的：验证SVM（支持向量机）机器学习算法学习情况 要求：自主完成。 二、实验内容和原理 支持向量机（Support V ector Machine, SVM）的基本模型是在特征空间上找到最 佳的分离超平面使得训练集上正负样本间隔最大。SVM是用来解决二分类问题的有监督学习算法。通过引入了核方法之后SVM也可以用来解决非线性问题。 但本次实验只针对线性二分类问题。 SVM算法分割原则：最小间距最大化，即找距离分割超平面最近的有效点距离超平面距离和最大。 对于线性问题： w T x+b=0 假设存在超平面可最优分割样本集为两类，则样本集到超平面距离为： ρ = min{|w T x+b| ||w|| }= a ||w|| 需压求取： max a ||w|| s.t. y i(w T x+b)≥a 由于该问题为对偶问题，可变换为： min 1 2 ||w||2 s.t. y i(w T x+b)≥1 可用拉格朗日乘数法求解。 但由于本实验中的数据集不可以完美的分为两类，即存在躁点。可引入正则化参数Ｃ，用来调节模型的复杂度和训练误差。
. . min 1 2||w||2+C ∑εi s.t. y i (w T x +b)≥1?εi , εi >0 作出对应的拉格朗日乘式： 对应的ＫＫＴ条件为： 故得出需求解的对偶问题： {min 1∑∑αi αj y i y j (x i T x j )?∑αi s.t. ∑αi y j = 0 , C≥αi ≥0, 本次实验使用python 编译器，编写程序，数据集共有２７０个案例，挑选其中70%作为训练数据，剩下30%作为测试数据。进行了两个实验，一个是取Ｃ值为１，直接进行ＳＶＭ训练；另外一个是利用交叉验证方法，求取在前面情况下的最优Ｃ值。 三、实验器材 实验环境：windows7操作系统+python 编译器。
支持向量机(SVM)原理及应用概述
支持向量机（SVM ）原理及应用 一、SVM 的产生与发展 自1995年Vapnik (瓦普尼克)在统计学习理论的基础上提出SVM 作为模式识别的新方法之后，SVM 一直倍受关注。同年，Vapnik 和Cortes 提出软间隔(soft margin)SVM ，通过引进松弛变量i ξ度量数据i x 的误分类(分类出现错误时i ξ大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM 的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年，Vapnik 等人又提出支持向量回归 (Support Vector Regression ，SVR)的方法用于解决拟合问题。SVR 同SVM 的出发点都是寻找最优超平面(注：一维空间为点；二维空间为线；三维空间为面；高维空间为超平面。)，但SVR 的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston 等人根据SVM 原理提出了用于解决多类分类的SVM 方法(Multi-Class Support Vector Machines ，Multi-SVM)，通过将多类分类转化成二类分类，将SVM 应用于多分类问题的判断：此外，在SVM 算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens 提出的最小二乘支持向量机 (Least Square Support Vector Machine ，LS —SVM)算法，Joachims 等人提出的SVM-1ight ，张学工提出的中心支持向量机 (Central Support Vector Machine ，CSVM)，Scholkoph 和Smola 基于二次规划提出的v-SVM 等。此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM 的典型应用进行总结，并设计开发出较为完善的SVM 工具包，也就是LIBSVM(A Library for Support Vector Machines)。LIBSVM 是一个通用的SVM 软件包，可以解决分类、回归以及分布估计等问题。 二、支持向量机原理 SVM 方法是20世纪90年代初Vapnik 等人根据统计学习理论提出的一种新的机器学习方 法，它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该子集中的判别函数，使学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。 支持向量机的基本思想：首先，在线性可分情况下，在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输
东北大学 研究生考试试卷 考试科目：信号处理的统计分析方法 课程编号：09601513 阅卷人: 刘晓志 考试日期：2012年11月07日 姓名：赵亚楠 学号：1001236 注意事项 1.考前研究生将上述项目填写清楚. 2.字迹要清楚,保持卷面清洁. 3.交卷时请将本试卷和题签一起上交. 4.课程考试后二周内授课教师完成评卷工作,公共课成绩单与试卷交研究生院培养办公室, 专业课成绩单与试卷交各学院,各学院把成绩单交研究生院培养办公室. 东北大学研究生院培养办公室
目录 一、SVM的产生与发展3 二、支持向量机相关理论4 （一）统计学习理论基础4 （二）SVM原理4 1．最优分类面和广义最优分类面5 2．SVM的非线性映射7 3．核函数8 三、支持向量机的应用研究现状9（一）人脸检测、验证和识别9（二）说话人／语音识别10 （三）文字／手写体识别10 （四）图像处理11 （五）其他应用研究11 四、结论和讨论12
一、SVM 的产生与发展 自1995年Vapnik 在统计学习理论的基础上提出SVM 作为模式识别的新方法之后，SVM 一直倍受关注。同年，Vapnik 和Cortes 提出软间隔(soft margin)SVM ，通过引进松弛变量i ξ度量数据i x 的误分类(分类出现错误时i ξ大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM 的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年，Vapnik 等人又提出支持向量回归 (Support Vector Regression ，SVR)的方法用于解决拟合问题。SVR 同SVM 的出发点都是寻找最优超平面，但SVR 的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston 等人根据SVM 原理提出了用于解决多类分类的SVM 方法(Multi-Class Support VectorMachines ，Multi-SVM)，通过将多类分类转化成二类分类，将SVM 应用于多分类问题的判断：此外，在SVM 算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens 提出的最小二乘支持向量机 (Least Square Support VectorMachine ，LS —SVM)算法，Joachims 等人提出的SVM-1ight ，张学工提出的中心支持向量机 (Central Support Vector Machine ，CSVM)，Scholkoph 和Smola 基于二次规划提出的v-SVM 等。此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM 的典型应用进行总结，并设计开发出较为完善的SVM 工具包，也就是LIBSVM(A Library for Support Vector Machines)。上述改进模型中，v-SVM 是一种软间隔分类器模型，其原理是通过引进参数v ，来调整支持向量数占输入数据比例的下限，以及参数ρ来度量超平面偏差，代替通常依靠经验选取的软间隔分类惩罚参数，改善分类效果；LS-SVM 则是用等式约束代替传统SVM 中的不等式约束，将求解QP 问题变成解一组等式方程来提高算法效率；LIBSVM 是一个通用的SVM 软件包，可以解决分类、回归以及分布估计等问题，它提供常用的几种核函数可由用户选择，并且具有不平衡样本加权和多类分类等功能，此外，交叉验证(cross validation)方法也是LIBSVM 对核函数参数选取问题所做的一个突出贡献；SVM-1ight 的特点则是通过引进缩水(shrinking)逐步简化QP 问题，以及缓存(caching)技术降低迭代运算的计算代价来解决大规模样本条件下SVM 学习的复杂性问题。
机器学习课程作业（1） 提交截止日期：2017年10月10日周二 1. 一个优化问题的原问题（Prime Problem ）与对偶问题（Dual Problem ）定义如下： 原问题 Minimize: ()f ω Subject to: ()0,1,2,...,i g i K ω≤= ()0,1,2,...,i h i M ω== 对偶问题 定义 ()()()()()()()11,,K M T T i i i i i i L f g h f g h ωαβωαωβωωαωβω===++=++∑∑ 对偶问题为： Maximize: ()(),inf ,,L ωθαβωαβ= Subject to: 0,1,2,...,i i K α≥= (a) 证明：如果*ω是原问题的解，*α，*β是对偶问题的解，则有：()()***,f ωθαβ≥ (b) 证明 (强对偶定理)：如果()g A b ωω=+,()h C d ωω=+，且()f ω为凸函数，即对任意1ω和2ω，有()()()()()121211f f f λωλωλωλω+-≤+-, 则有：()()*** ,f ωθαβ= 2. 求下列原问题的对偶问题 (a) (1l and 2l -norm SVM Classification) : Minimize: 221211 12N N i i i i C C ωδδ==++∑∑ Subject to: 0,1,2,...,i i N δ≥= ()1T i i i y x b ω?δ??+≥-??
(b) (SVM regression): Minimize: ()()2221211 12N N i i i i i i C C ωδζδζ==++++∑∑ Subject to: (),1,2,...,T i i i x b y i N ω?εδ+-≤+= (),1,2,...,T i i i y x b i N ω?εζ--≤+= 0i δ≥, 0i ζ≥ (c) (Kernel Ridge Regression): Minimize: 221 12N i i C ωδ=+∑ Subject to: (),1,2,...,T i i i y x i N ω?δ-== (d) (Entropy Maximization Problem): Minimize: ()1log N i i i x x =∑ Subject to: T x b ω≤ 11N i i x ==∑ 3. 如图所示，平面上有N 个点12{,,...,}N x x x ，求一个半径最小的圆，使之能包含这些点。 图1. 平面上N 个点，求最小的圆包含这些点。 (a) 写出这个优化问题的数学表达式。 (b) 写出(a)的对偶问题。 (c) 编写程序求解这个问题（选做）