第七章-支持向量机

袁春清华大学深圳研究生院李航华为诺亚方舟实验室目录1.线性可分支持向量机与硬间隔最大化2.线性支持向量机与软间隔最大化3.非线性支持向量机与核函数4.序列最小最优化算法一、线性可分支持向量机与硬间隔最大化线性可分支持向量机函数间隔和几何间隔间隔最大化学习的对偶算法线性可分支持向量机二分类问题：输入空间：欧式空间或离散集合特征空间：欧式空间或希尔伯特空间线性可分支持向量机、线性支持向量机：假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量；非线性支持向量机：利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量；支持向量机的学习是在特征空间进行的.线性可分支持向量机假设特征空间上的训练数据集：正例和负例学习的目标：找到分类超平面，线性可分支持向量机：给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为决策函数：6w·x+b0w·x+b0w·x+b=0w线性可分支持向量机与硬间隔最大化超平面选择7?MarginsSupportVectorsSupportVectors点到超平面的距离9xx'bxwxg)(||||||wb函数间隔和几何间隔点到分离超平面的远近表示分类预测的确信程度的符号与类标记y的符号是否一致表示分类是否正确所以：表示分类的正确性和确信度函数间隔和几何间隔函数间隔样本点的函数间隔训练数据集的函数间隔表示分类预测的正确性和确信度当成比例改变w和bxx'||||||wb函数间隔和几何间隔几何间隔样本点的几何间隔：正例和负例函数间隔和几何间隔几何间隔对于给定的训练数据集T和超平面(w,b)训练数据集的几何间隔即间隔最大化最大间隔分类超平面根据几何间隔和函数间隔的关系考虑可以取最大化和最小化等价间隔最大化线性可分支持向量机学习的最优化问题凸二次规划(convexquadraticprogramming)的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。一个点集（或区域），如果连接其中任意两点1x2x凸集1.根据一阶导数（函数的梯度）来判断函数的凸性设f(x)为定义在凸集R上，且具有连续的一阶导数的函数，则f(x)在R上为凸函数的充要条件是对凸集R内任意不同两点，不等式1x2x21211Tfxfxxxfx恒成立。凸性条件2.根据二阶导数（Hesse矩阵)来判断函数的凸性凸性条件设f(x)为定义在凸集R上且具有连续二阶导数的函数，则f(x)在R上为凸函数的充要条件：Hesse矩阵在R上处处半正定对于约束优化问题minfx..st0jgx1,2,...,jm若fxjgx都为凸函数，则此问题为凸规划。凸规划1.若给定一点,则集合0x为凸集。2.可行域为凸集3.凸规划的任何局部最优解就是全局最优解凸规划的性质凸优化问题凸优化问题:指约束最优化问题其中，目标函数f(w)和约束函数gi(w)都是Rn上连续可微的凸函数，约束函数hj(w)是Rn上的仿射函数当目标函数为二次函数，g函数为仿射函数时，为凸二次规划问题。线性可分支持向量机学习算法输入：线性可分训练数据集输出：最大间隔分离超平面和分类决策函数1、构造并求解约束最优化问题求得w*和b*2、得到分离超平面分类决策函数1支持向量和Margins（边界）在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(supportvector)；支持向量是使约束条件式等号成立的点，即正例：负例：例：拉格朗日对偶如何求解：在约束最优化问题中，常常利用拉格朗日对偶性(Lagrangeduality)将原始问题转换为对偶问题，通过解对偶问题得到原始问题的解1拉格朗日对偶1、原始问题设f(x),c(x),h(x)是定义在Rn上的连续可微函数引进拉格朗日函数为乘子考虑x的函数，P为原始问题拉格朗日对偶为乘子假设给定某个x，如果x违反约束条件：拉格朗日对偶考虑极小问题：与原始最优化问题等价拉格朗日对偶1、原始问题则：称为广义拉格朗日函数的极小极大问题定义原始问题的最优值拉格朗日对偶2、对偶问题定义：则最大值问题：称为广义拉格朗日函数的极大极小问题表示为约束最优化问题：称为原始问题的对偶问题，对偶问题的最优值原始问题和对偶问题的关系定理：若原始问题和对偶问题都有最优值，则推论：设x*，和α*，β*分别是原始问题和对偶问题的可行解，并且d*=p*，则x*，和α*，β*分别是原始问题和对偶问题的最优解原始问题和对偶问题的关系定理：若原始问题和对偶问题都有最优值，则推论：设x*，和α*，β*分别是原始问题和对偶问题的可行解，并且d*=p*，则x*，和α*，β*分别是原始问题和对偶问题的最优解KKT条件定理：对原始问题和对偶问题，假设函数f(x)和ci(x)是凸函数，hj(x)是仿射函数，并且不等式ci(x)是严格可行的，则x*，和α*，β*分别是原始问题和对偶问题的解的充分必要条件是x*，和α*，β*满足karush-Kuhn-Tucker(KKT)条件。学习的对偶算法对于线性可分支持向量机的优化问题，原始问题：应用拉格朗日对偶性，通过求解对偶问题，得到原始问题的解。优点：对偶问题往往容易解引入核函数，推广到非线性分类问题1学习的对偶算法定义拉格朗日函数原问题：极小极大，对偶问题：极大极小学习的对偶算法先求L(w,b,α)对w，b的极小，再求对α的极大1、求：，对w，b分别求偏导并令等于0由得：学习的对偶算法求对α的极大，即是对偶问题：2学习的对偶算法定理：设是对偶最优问题的解则存在下标j，使得，并可按下式求得原始问题的解。证明：由得：21学习的对偶算法定理：设是对偶最优问题的解则存在下标j，使得，并可按下式求得原始问题的解。证明：由，其中至少有一个反证法：假设：,由可知w*=0，但这不是原始优化问题的解，产生矛盾对此：j有21学习的对偶算法由此定理可知，分离超平面可以写成：分类决策函数可以写成：这就是说，分类决策函数只依赖于输入x和训练样本输入的内积，上式称为线性可分支持向量机的对偶形式.线性可分支持向量机学习算法输入：线性可分训练数据集输出：最大间隔分离超平面和分类决策函数1、构造并求解约束最优化问题求得最优解：线性可分支持向量机学习算法2、计算并选择α*的一个正分量，计算3、求得分离超平面分类决策函数支持向量考虑原始优化问题和对偶优化问题，将数据集中对应于的样本的实例xi称为支持向量支持向量一定在分割边界上，由KKT互补条件：对应于的样本xi或例子：正例点负例点解：对偶形式将带入目标函数并记为例子：对求偏导数，并令其为0，易知在取极值，但该点不满足约束条件，所以最小值应在边界上达到当时，最小值当时，最小值于是在获得极小，这样对应的实例向量为支持向量例子：计算得：分离超平面为：分类决策函数为：二、线性支持向量机与软间隔最大化训练数据中有一些特异点（outlier），不能满足函数间隔大于等于1的约束条件。解决方法：对每个样本点引进一个松弛变量使得函数间隔加上松弛变量大于等于1，约束条件变为：目标函数变为：C0为惩罚参数线性支持向量机与软间隔最大化线性不可分的线性支持向量机的学习问题：可证明w的解是唯一的，b不是，设该问题的解是w*,b*,可得到分离超平面和决策函数3线性支持向量机与软间隔最大化原始问题的拉格朗日函数：其中：对偶问题是拉格朗日函数的极大极小问题首先求对w,b,ξ的极小，由得：带入3线性支持向量机与软间隔最大化得：再对求α的极大，得到对偶问题：线性支持向量机与软间隔最大化原始问题的对偶问题：定理：设是对偶问题的一个解，若存在α*的一个分量，则原始问题的解w*,b*344线性支持向量机学习算法输入：线性不可分训练数据集输出：分离超平面和分类决策函数1、构造并求解约束最优化问题求得最优解：线性支持向量机学习算法2、计算并选择α*，适合条件，计算3、求得分离超平面分类决策函数支持向量合页损失函数hingelossfunction线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：第一项：称为合页损失函数合页损失函数hingelossfunction线性支持向量机原始最优化问题:等价于：合页损失函数hingelossfunction三、非线性支持向量机与核函数非线性分类问题：非线性可分问题如果能用Rn中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题.非线性支持向量机与核函数非线性问题往往不好求解，所以希望能用解线性分类间题的方法解决这个问题。采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。原空间：新空间：非线性支持向量机与核函数用线性分类方法求解非线性分类问题分为两步:首先使用一个变换将原空间的数据映射到新空间;然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法核技巧应用到支持向量机，其基本想法：通过一个非线性变换将输入空间(欧氏空间R”或离散集合)对应于一个特征空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机)。分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成.非线性支持向量机与核函数核函数定义：设X是输入空间(欧氏空间Rn的子集或离散集合)，又设H为特征空间(希尔伯特空间)，如果存在一个从X到H的映射使得对所有函数K(x,z)满足条件则称为核函数，为映射函数，式中为和的内积非线性支持向量机与核函数核技巧的想法是：在学习与预测中只定义核函数K(x,z)，而不显式地定义映射函数，通常，直接计算K(x,z)比较容易，而通过和计算K(x,z)并不容易。注意：φ是输入空间Rn到特征空间H的映射，特征空间H一般是高维，映射可以不同。非线性支持向量机与核函数例：假设输入空间是R2，核函数是,试找出其相关的特征空间H和映射解：可以取：容易验证：非线性支持向量机与核函数例：假设输入空间是R2，核函数是,试找出其相关的特征空间H和映射解：同样：都满足条件。核函数在支持向量机的应用注意到：线性支持向量机对偶问题中，无论是目标函数还是决策函数都只涉及输入实例和实例之间的内积。目标函数中的内积用核函数代替，目标函数：决策函数：正定核问题：己知映射函数φ，可以通过和的内积求得核函数K(x,z).不用构造映射φ,能否直接判断一个给定的函数K(x,z)是不是核函数?或者说，函数K(x,z)满足什么条件才能成为核函数?假设K(x,z)是定义在XxX上的对称函数，并且对任意的K(x,z)关于的Gram矩阵是半正定的，可以依据函数K(x,z)，构成一个希尔伯特空间(Hilbertspace)；其步骤是首先定义映射φ，并构成向量空间S，然后在S上定义内积构成内积空间;最后将S完备化构成希尔伯特空间.正定核1、定义映射，构成向量空间S映射：对任意定义线性组合:考虑由线性组合为元素的集合S,由于集合S对加法和数乘运算是封闭的，S构成一个向量空间。正定核2、在S上定义内积，构成内积空间在S上定义一个运算“*”，对任意f，g属于S定义运算*：证明内积空间：正定核3、将内积空间S完备化为希尔伯特空间由：内积得到范数：因此，S是一个赋范向量空间；根据泛函分析理论，对于不完备的赋范向量空间S，一定可以使之完备化，得到完备的赋范向量空间H；一个内积空间，当作为一个赋范向量空间是完备的时候，就是希尔伯特空间，这样，就得到了希尔伯特空间H。再生性：正定核正定核的充要条件设K：，是对称函数，则K(x,