支持向量机

支持向量机10212885黄广民简介支持向量机是一种通用的前馈网络类型，最早于1992年提出。支持向量机主要用于模式分类和非线性回归支持向量机是一种线性机器简介支持向量机的主要思想：建立一个超平面作为决策曲面，使得正例和反例之间的隔离边缘被最大化。构建支持向量机学习算法的关键：在“支持向量”xi和输入空间抽取的向量x之间的内积核这一概念。依赖于内积核的不同产生方式，可能建立不同的学习机器。考虑训练样本，其中是输入的第i个例子，是目标输出。假定由子集代表的类和代表的类是“线性可分的”。线性可分模式的最优超平面1,xNiiidxiid1id1id线性可分模式的最优超平面用于分离超平面形式的决策曲面方程：(1)其中X是输入向量，W是可调的权值向量，b是偏置。wx0Tb线性可分模式的最优超平面根据假定，我们可以将方程写成：，对于(2)，对于wx0Tib1id1idwx0Tib线性可分模式的最优超平面超平面与最近的样本点之间的间隔称为分离边缘，用ρ表示。支持向量机的目标是找到一个分离边缘最大的超平面，即最优超平面。也就是要确定使ρ最大时的w和b设w0,b0分别表示权值向量和偏置的最优值。相应地，在输入空间里表示多维线性决策面的最优超平面由(3)定义线性可分模式的最优超平面00wx0Tb线性可分模式的最优超平面判别函数（4）给出从x到最优超平面的距离的一种代数度量00(x)wxTgb线性可分模式的最优超平面将x表达为是x在最优超平面上的常规投影，r是期望的代数距离。如果在最优超平面的正面，是正值；相反如果在最优超平面的负面，是负值。由定义可知，由此推出：或00wxxwrxxwxwTooogbrxwogr(x)0g线性可分模式的最优超平面如果(2)式成立，则说明模式是线性可分的，可以通过调整和的值使(5)式成立如果有某个数据点使得上式的第一行或者第二行的等号成立，则这个点称为支持向量。对于11iiddwx1wx1ToioToiobb（5）线性可分模式的最优超平面考虑一个支持向量对应于。然后根据定义有：对于(6)从支持向量到最优超平面的代数距离是：若(7)其中加号表示在最优超平面的正面，而减号表示在最优超平面的负面。1sdxsxwx1sToogb1sd1xw1wwsooogr11ssddxs线性可分模式的最优超平面表示在两个类之间的分离边缘的最优值，其中这两个类构成训练集合。由此得到：上式说明最大化两个类之间的分离边缘等价于最小化权值向量的欧几里德范数。最优超平面是唯一的，意味着最优权值向量提供正反例之间的最大可能的分离。这个优化条件是通过最小化权值向量的欧几里德范数获得的。22wor（8）线性可分模式的最优超平面支持向量机的训练过程即：给定训练样本，找到权值向量w和偏置b的最优值使得它们满足下面的约束条件对于并且权值向量最小化代价函数这是一个约束最优问题。其特点如下：1.代价函数是w的凸函数。2.约束条件关于w是线性的。1x,Niiidwx1TiidbNi,...,2,11w线性可分模式的最优超平面可以用Lagrange乘子方法解决约束最优问题。建立Lagrange函数辅助非负变量即Lagrange乘子。约束最优问题的解由Lagrange函数的鞍点决定，函数对w和b必定最小化，对a必定最大化。对w和b求微分并置结果为0，得到最优化条件如下：11w,,i,,bwJw,,0wJbw,,0Jbb1wxNiiiid01Niiid（9）（10）线性可分模式的最优超平面目标函数设置成为则可推导出w,,()JbQa1111()(x)x2ppppipTpppijppjQaaaadd（11）线性可分模式的最优超平面最小化L(W,b,a)问题，转化为一个最大化函数Q(a)的对偶问题，即给定训练样本，寻找最大化目标函数的Lagrange乘子，满足约束条件：1,Niiixd1111()(x)x2ppppipTpppijppjQaaaadd1Niia10NiiiadiNa对于=1,2,...,（12）线性可分模式的最优超平面对偶问题完全是根据训练集数据来表达的。而且，函数Q(a)的最大化仅依赖于输入模式点积的集合确定用表示的最优Lagrange乘子后，可用式子(9)计算最优权值向量w0，并写成(,)1xxjNTixj0,1a00,111wxNiid线性可分模式的最优超平面为了计算最优偏置b0，可以使用获得的w0，并对于一正的支持向量利用式子(6)，这样有001wxTb对于1d不可分模式的最优超平面给定一组训练数据，不可能建立一个不具有分类误差的分离超平面。然而，我们希望找到一个最优超平面，它对整个训练集合平均的分类误差的概率达到最小。为了建立不可分离数据点正式处理的阶段，我们引入一组新的非负标量，称之为松弛变量，到分离超平面（即决策面）的定义中，表示为1Niiwx1Tiiidb不可分模式的最优超平面对不可分离的情况的原问题可以正式陈述如下：给定训练样本，寻找权值向量w和偏置b的最优值，使得它们满足约束条件并且使得权值向量w和松弛变量最小化代价函数其中，C是使用者选定的正参数1x,Niiidwx1ξTtiidb对于i=1,2,3…N而且0iii11w,ξwwξ2NTiC不可分模式的最优超平面使用Lagrange乘子的方法，可以得到不可分离模式的对偶问题的表示：给定训练样本，寻找最大化目标函数的Lagrange乘子，满足约束条件：1x,Niiid1111()xx2NNNTiijijijiijQaaaadd1Niia10Niiiad0iaC不可分模式的最优超平面权值向量W的最优解由00,111wxsNiiad其中Ns是支持向量的个数决定偏置最优值的方法也与之前描述的过程相似。