机器学习5.线性不可分svm

1、线性不可分SVM王成（副教授）计算机科学与技术学院1.广义线性判别函数x1x2 对图示的两类分布，可以用一个4次多项式决策函数对其分类。这是一个两维函数 做特征空间变换，令 则有 可将一个在低维空间很复杂的决策面，变换成一个高维空间的线性函数： 称之为广义线性判别函数。即 在变换后的空间中是线性的，在原空间是非线性的。 一般来说，对于任意高次判别函数 ，都可以通过适当的变换变成广义线性判别函数 ，利用线性判别函数的简单性来解决复杂问题。 但是，这种变换带来一个很严重的问题： 维数大大增加，例中2维变成15维 维数增加导致所需样本数呈指数增加。目录线性不可分问题核函数松弛变量多输入多输出支持向量

2、机回归算法支持向量机实现研究现状数据线性不可分的情况 解决的一个途径(支持向量机算法)是用“超曲面”代替“超平面”,找一个能够正确分类所有观测样本的的“最大间隔超曲面”。红点 x2+y2-4y=0绿点x2+y2-4y=-3映射形式为：()=例：二维线性不可分映射到三维后线性可分 在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，等价于：用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器。因此，考虑的假设集是这种类型的函数：这里：X-F是从输入空间到某个特征空间的映射1.首先使用一个非线性映射将数据变换到一个特征空间F2.然后在特征空间

3、使用线性学习器分类。低维非线性到高维线性这意味着建立非线性学习器分为如下几步：如何处理线性不可分数据目录线性不可分问题核函数松弛变量支持向量机实现研究现状核函数对于非线性的情况，SVM 的处理方法是选择一个核函数 (,) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。 核函数通过把数据映射到高维空间来增加第一节所述的线性学习器的能力，使得线性学习器对偶空间的表达方式让分类操作更具灵活性和可操作性。因为训练样例一般是不会独立出现的，它们总是以成对样例的内积形式出现，而用对偶形式表示学习器的优势在为在该表示中可调参数的个数不依赖输入属性的个数，通过使用恰当的核函数来替代内积，可以

4、隐式得将非线性的训练数据映射到高维空间，而不增加可调参数的个数(当然，前提是核函数能够计算对应着两个输入特征向量的内积)。 基本概念 低维非线性到高维线性在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数： 这里：X-F是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：1.首先使用一个非线性映射将数据变换到一个特征空间F，2.然后在特征空间使用线性学习器分类。13在上文我提到过对

5、偶形式，而这个对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：对一个函数k，满足所有的x，z都有k(x,z)=,这里的(x)为从X到内积特征空间F的映射，则称k为核函数。求解i, i=1,2,n进行分类回顾：核函数的引入在求解分类函数和利用分类函数进行分类时，都涉及到“高维特征向量求内积”。若映射到的高维空间维数太高甚至是无穷维时，存在“维数灾难”。若存在这么一个函数 (.,.),满足：也就是说，我们要求的高维空间中向量内积运算，可以直接在低维空间进行运算求得，两者的值相等，这样就避免直接在高维空间求向量积可能带来的维

6、数灾难问题。那么分类函数相应为当特征空间维数很高或为无穷维时，直接计算高维空间中的内积是非常困难的，因此需要另外的方法。那么巧妙地将高维空间中的求内积运算转化为低维空间中的运算，避免“维数灾难”。核函数的引入16核函数能简化映射空间中的内积运算，在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子，现在我们的分类函数为：其中 由如下dual问题计算而得：避开了直接在高维空间中进行计算，而结果却是等价的！核函数的引入 因此，只要找到适当的核函数，就可以实现某个线性变换后的线性分类。 寻优函数为： 分类函数为：支持向量机的基本思想： 通过非线性变换将输入空

7、间变换到一个高维空间，然后在这个变换空间中求最优分界面，实现分类。这种非线性变换是通过定义适当的内积函数，用内积运算实现的。（不必真的进行这种非线性变换）支持向量机核函数：如何处理非线性数据01某种试验方法的名称这种方法的特点如果用 X1 和 X2 来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：如果我们构造另外一个五维空间，其中五个坐标为 则有：如果我们做一个映射 :R2R5 ，将 X 按照上面的规则映射为 Z ，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel

8、 方法处理非线性问题的基本思想。例子.设两个向量 和 ，而 即是到前面说的五维空间的映射，因此映射过后的内积为：而这个式子与下面这个是等价的 ： 一个是映射到高维空间中，然后再根据内积的公式进行计算；而另一个则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。 我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (Kernel Function) 20核函数能简化映射空间中的内积运算，在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子，现在我们的分类函数为： 其中 由如下 dual 问题计算而得：这样一来计算的问题就算

9、解决了，避开了直接在高维空间中进行计算，而结果却是等价的！ 是高维或无穷维度空间中的向量积运算核函数K（ .，.）是直接在低维度空间中进行计算，两者计算结果相等按照前面的思路，处理线性不可分数据步骤为:首先寻找一个映射函数将数据映射到高维空间，(在高维空间中数据可能变得线性可分)在高维空间中应用SVM分析求解过程中引入核函数。得到分类函数但实际上，寻找使变得线性可分的映射函数很难。寻找与映射函数对应的核函数更难。核函数的实际应用问题上：理论上核函数的使用下：实际中核函数的使用高维空间中的最优分类面非线性问题通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。分类函

10、数只涉及到训练样本之间的内积运算 ,因此,在高维空间中只需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现, 甚至不必知道变换的形式。SLT指出,根据Hibert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积使用。Mercer条件问题：什么样的函数能作为核函数？ 2.3支持向量机2数据线性不可分的情况对偶优化问题（D）: 求解对偶问题的最优解后,支持向量机的决策函数为： 在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。非线性支持向量机 核函数分类不同的内积核函数将形成不同的算法,目前,在SVM理论研究与实际应用中,

11、最常使用的有以下四类核函数:（1）线性核函数：（2）多项式核函数： , q是自然数。此时得到的支持向量机是一个q阶多项式分类器。（3）Gauss径向基核函数: 。得到的支持向量机是一种径向基函数分类器。（4）Sigmoid核函数： a和t是常数，tanh是Sigmoid函数。常用的核函数RBF核函数如何选择核函数，有哪些指导原则？映射到高维空间就一定线性可分吗？如果高维空间仍然线性不可分，那该怎么办？核函数的选择，没有明确的原则，一般根据具体问题，采用试探的方式。核函数隐藏着一个到高维的映射，可能使得数据在高维变得线性可分，但并不不能保证映射到高维空间后一定线性可分。若仍然线性不可分，引入松弛

12、变量、惩罚系数，放松约束，虽然仍然不能保证对训练数据线性可分，但它会根据我们给出的惩罚因子找到代价最小的分类器。机器学习-周志华著 上有这样一句话：“幸运的是，如果原始空间是有限维，即属性有限，那么一定存在一个高纬度特征空间使样本可分。” 但是没有给出证明或参考文献。两个问题回答高维空间中的最优分类面非线性问题通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。分类函数只涉及到训练样本之间的内积运算。因此,在高维空间中只需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现, 甚至不必知道变换的形式。 在最优分类面中采用适当的内积函数就可以实现某一非线性变换

13、后的线性分类, 而计算复杂度却没有增加。SLT指出,根据Hibert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积使用。目录线性不可分问题核函数松弛变量多输入多输出支持向量机回归算法支持向量机实现研究现状引入松弛变量33现在去考虑映射到高维也不可分的情况，原来的约束条件是其中c是一个参数为常量，是需要优化的变量之一。现在考虑到映射到高维不可分，约束条件变为：其中称为松弛变量，对应数据点x可以偏离的函数间隔的量，即将限制或约束条件加入到目标函数中，得到新的拉格朗日函数：这里的和都是拉格朗日乘子34然后将其看作是变量w和b的函数，分别对其求偏导，然后带入公式中，求带入后公式

14、的极大值我们会发现，没有了参数 ，与之前的模型唯一不同是在于 又多了小于等于C的条件。而和函数化的非线性形式也是一样的，只要把换成K(Xi,Xj)即可。目录线性不可分问题核函数松弛变量多输入多输出支持向量机回归算法支持向量机实现研究现状多输入多输出支持向量机回归算法 支持向量机是从线性可分情况下的最优分类面发展而来的。支持向量机形式上类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应于一个支持向量，其结构如图1所示。支持向量机线性回归（1）支持向量机线性回归支持向量机线性回归支持向量机线性回归支持向量机线性回归由此推出支持向量机线性回归支持向量机线性回归支持向量机线性回归支持向量机

15、线性回归支持向量机线性回归支持向量机非线性回归支持向量机非线性回归(14)支持向量机非线性回归SVM优点总结 SVM发展到现在经久不衰（十大经典机器学习和数据挖掘算法之一），反思一下SVM为何如此强大：首先模型选择非常好，提出了最大距离分类面和KKT对偶化是分不开的，转化为对偶问题不但运算效率高，而且很自然的扩展到存在松弛的线性可分、通过核函数转为高维线性可分对偶问题的目标函数模型只是将输入空间内积转化为对应映射空间（更高维）的内积，而且由于核函数还使得运算过程在低维进行。不需要估计数据点的分布、概率密度函数这之类的先验知识（如贝叶斯分类器等），推广能力强！目录线性不可分问题核函数松弛变量支持

16、向量机实现研究现状支持向量机实现SVMlight - 2.private:/usr/local/binsvm_learn, svm_classifybsvm - 2.private:/usr/local/binsvm-train, svm-classify, svm-scalelibsvm - 2.private:/usr/local/binsvm-train, svm-predict, svm-scale, svm-toymySVMMATLAB svm toolbox支持向量机实现目录线性不可分问题核函数松弛变量支持向量机实现研究现状研究现状应用研究支持向量机研究支持向量机算法研究应用研究S

17、VM的应用主要于模式识别领域贝尔实验室对美国邮政手写数字库进行的实验分类器错误率人工表现2.5%决策树C4.516.2%最好的两层神经网络5.9%SVM4.0%SVM与神经网络（NN）的对比SVM的理论基础比NN更坚实，更像一门严谨的“科学”（三要素：问题的表示、问题的解决、证明）SVM 严格的数学推理NN 强烈依赖于工程技巧推广能力取决于“经验风险值”和“置信范围值”，NN不能控制两者中的任何一个。NN设计者用高超的工程技巧弥补了数学上的缺陷设计特殊的结构，利用启发式算法，有时能得到出人意料的好结果。“我们必须从一开始就澄清一个观点，就是如果某事不是科学，它并不一定不好。比如说，爱情就不是科

18、学。因此，如果我们说某事不是科学，并不是说它有什么不对，而只是说它不是科学。” by R. Feynman from The Feynman Lectures on Physics, Addison-Wesley同理，与SVM相比，NN不像一门科学，更像一门工程技巧，但并不意味着它就一定不好！主要应用领域手写数字识别语音识别人脸识别文本分类支持向量机研究如何针对不同的问题选择不同的核函数仍然是一个悬而未决的问题。标准的SVM对噪声是不具有鲁棒性的,如何选择合适的目标函数以实现鲁棒性是至关重要的。支持向量机算法研究支持向量机的本质是解一个二次规划问题,虽然有一些经典（如对偶方法、内点算法等）,但

19、当训练集规模很大时,这些算法面临着维数灾难问题。为此,人们提出了许多针对大规模数据集的SVM训练算法。支持向量机算法研究（续1）思路1：分解子问题块算法SMO算法(Sequential Minimal Optimization)思路2：序列优化思路3：近邻SVM支持向量机算法研究（续2）训练SVM的绝大多数算法都是针对分类问题,只有一小部分算法考虑了回归函数的估计问题。提高算法效率、降低复杂度。支持向量机算法研究（续3）SVM增量学习算法的研究超球面SVM算法研究One-class SVM算法SVM多值分类器算法One-against-the-rest（一对多方法）One-against-one（一对一方法）Multi-class Objective Functions（多类SVM）Decision Directed A