机器学习:SVM(一)——线性可分支持向量机原理与公式推导

发布日期:2019-01-19

原理

SVM基本模型是定义在特征空间上的二分类线性分类器(可推广为多分类),学习策略为间隔最大化,可形式化为一个求解凸二次规划问题,也等价于正则化的合页损失函数的最小化问题。求解算法为序列最小最优化算法(SMO)当数据集线性可分时,通过硬间隔最大化,学习一个线性分类器;数据集近似线性可分时,即存在一小部分outlier,除这些点外,其他的样本线性可分,此时通过软间隔最大化,学习一个线性分类器;当数据集线性不可分时,将输入映射到高维空间使得线性可分,利用原本空间中的核函数表示特征向量映射到高维空间之后的内积,这种方法称为核技巧,此时学习到非线性支持向量机。函数间隔与几何间隔一个点距离超平面远近可以表示分类预测的确信程度,在超平面(w cdot x + b = 0({w^T}x + b = 0))确定的情况下,(|{w^T}x + b|)能够相对表示距离超平面的远近,取正例(y=+1),负例(y=-1)(y({w^T}x + b))可以表示分类正确性以及确信度。大小表示远近,正负表示分类正确与否。超平面关于某个样本点((x_iy_i))的函数间隔为[{hat gamma _i} = {y_i}(w cdot {x_i} + b)]超平面关于训练集的函数间隔为[hat gamma = mathop {min {{hat gamma }_i}}limits_{i = 12...N} ]在成比例改变(wb)时,函数间隔会变大,但此时超平面并没有改变。因此需对法向量施加约束,从而有了几何间隔。超平面关于某个样本点((x_iy_i))的几何间隔为[{gamma _i} = {y_i}(frac{{w cdot x_i + b}}{{||w||}})]超平面关于训练集的几何间隔为[ {gamma } = mathop {min {gamma _i}}limits_{i = 12..N} ]线性可分支持向量机选择一个超平面将空间分成两部分,一部分全部为正例,一部分全部为负例,要求几何间隔最大。感知机的策略是误分类数最小,因此满足条件的超平面不唯一,有无穷多。而线性可分支持向量机基于几何间隔最大的超平面唯一。算法描述输入:线性可分训练集(T = { ({x_1}{y_1})({x_2}{y_2})...({x_N}{y_N})} {y_i} in { + 1 - 1} i = 12..N)输出:分离超平面和分类决策函数(1).构造并求解约束最优化问题[egin{array}{l}mathop {min }limits_alpha frac{1}{2}sumlimits_{i = 1}^N {sumlimits_{j = 1}^N {{alpha _i}{alpha _j}{y_i}{y_j}({x_i} cdot {x_j}) - sumlimits_{i = 1}^N {{alpha _i}} } } s.t.sumlimits_{i = 1}^N {{alpha _i}{y_i}} = 0{alpha _i} ge 0i = 12...Nend{array}]求得最优解({alpha ^*} = {(alpha _1^*alpha _2^*...alpha _N^*)^T})(2).计算[{w^*} = sumlimits_{i = 1}^N {alpha _i^*{y_i}} {x_i}]并选择一个(alpha _j^* > 0),计算[{b^*} = {y_i} - sumlimits_{i = 1}^N {alpha _i^*{y_i}({x_i}} cdot {x_j})](3).求得分离超平面[{w^*} cdot x + {b^*} = 0]分类决策函数:[f(x) = sign({w^*} cdot x + {b^*})]

公式推导

预备知识

拉格朗日函数与求解约束最优化问题。假设(f(x)c_i(x)h_j(x))是定义在(R^n)上的连续可微函数,对于约束最优化问题[egin{array}{l}mathop {min }limits_x f(x)s.t.{c_i}(x) le 0i = 12...k{h_j}(x) = 0j = 12...lend{array}]首先引入拉格朗日函数[L(xalpha eta ) = f(x) + sumlimits_{i = 1}^k {{alpha _i}} {c_i}(x) + sumlimits_{j = 1}^l {{eta _j}} {h_j}(x){alpha _i} ge 0]则在(x)满足约束条件下[mathop {min }limits_x f(x) = mathop {min }limits_x mathop {max }limits_{alpha eta } L(xalpha eta ){alpha _i} ge 0]这样一来,就把原始问题表示为广义拉格朗日函数的极小极大问题。对偶问题。记极小极大问题为原始问题,则其对偶问题为(mathop {max }limits_{alpha eta } mathop {min }limits_x L(xalpha eta )),称为广义拉格朗日函数的极大极小问题。假设原始问题与极大极小问题函数都有最优值,两者关系为前者最优值大于等于后者最优值。对应于最优值,存在可行解。当最优值相等时,两个问题的可行解即为两个问题的最优解。KKT条件。由上我们可以得出思路,当原始问题与对偶问题的最优值相等时,可行解为最优解,可用解对偶问题替代解原始问题。假设(f(x)c_i(x))为凸函数,(h_j(x))为仿射函数,并且不等式约束是严格可行的,则此时(x^*)({alpha ^*}{eta ^{^*}})分别是原始问题和最偶问题的充要条件是满足KKT条件:[egin{array}{l}{abla _x}L({x^*}{alpha ^*}{eta ^*}) = 0{abla _alpha }L({x^*}{alpha ^*}{eta ^*}) = 0{abla _eta }L({x^*}{alpha ^*}{eta ^*}) = 0{alpha _i} ge 0{c_i}({x^*}) le 0{alpha _i}{c_i}({x^*}) = 0i = 12...k{h_j}({x^*}) = 0j = 12...lend{array}]第五式为对偶互补条件!其中一个因子必为0。以线性可分支持向量机来看,第一个因子为零,样本不会在求和中出现。第二个因子为零,样本在间隔边界上,此时为支持向量。同时保证了二式。

具体推导

在上面算法描述中我们知道,要求出超平面只需要解决算法描述中的(1),后面超平面问题即可迎刃而解。关键是(1)怎么得到的,下面推导为过程,其中用到了预备知识。

基于最大几何间隔分离超平面可表示为[egin{array}{l}mathop {max }limits_{wb} gamma s.t.{y_i}(frac{{w cdot x + b}}{{left| w ight|}}) ge gamma i = 12..Nend{array}]考虑到几何间隔与函数间隔的关系,可将问题改写为[egin{array}{l}mathop {max }limits_{wb} frac{{hat gamma }}{{left| w ight|}}s.t.{y_i}(w cdot x + b) ge hat gamma i = 12..Nend{array}]函数间隔取值对最优化问题求解不影响,因此可取1,颠倒分子分母后,最大化与最小化等价,于是得到如下最优化问题[egin{array}{l}mathop {min }limits_{wb} frac{1}{2}{left| w ight|^2}s.t.{y_i}(w cdot x + b) - 1 ge 0i = 12..Nend{array}]构造拉格朗日函数[L(wbalpha ) = frac{1}{2}{left| w ight|^2} + sumlimits_{i = 1}^N {{alpha _i}} [1 - {y_i}(w cdot {x_i} + b)] = frac{1}{2}{left| w ight|^2} - sumlimits_{i = 1}^N {{alpha _i}} {y_i}(w cdot {x_i} + b) + sumlimits_{i = 1}^N {{alpha _i}},{alpha _i} ge 0 ]此时,在约束条件下[mathop {min }limits_{wb} frac{1}{2}{left| w ight|^2} = mathop {min }limits_{wb} mathop {max }limits_alpha L(wbalpha ){alpha _i} ge 0],为极小极大问题。对偶问题为极大极小问题 (mathop {max }limits_alpha mathop {min }limits_{wb} L(wbalpha ){alpha _i} ge 0)我们知道普通条件下原问题是不能利用对偶条件来求解的,需要某些条件进行限定,即(KKT)条件。因此我们给出限定约束如下:[egin{array}{l}{abla _w}L = 0{abla _b}L = 0{alpha _i} ge 0{y_i}(w cdot {x_i} + b) - 1 ge 0{alpha _i}{y_i}(w cdot {x_i} + b) = 0end{array}]此时我们只需求解对偶问题[mathop {max }limits_alpha mathop {min }limits_{wb} L(wbalpha ){alpha _i} ge 0]即可。我们需要先求极小,将解带入得到极小的函数值,再求极大。1.将拉格朗日求偏导并令其等于0[egin{array}{l}{abla _w}L = w - sumlimits_{i = 1}^N {{alpha _i}} {y_i}{x_i} = 0{abla _b}L = sumlimits_{i = 1}^N {{alpha _i}{y_i} = } 0w = sumlimits_{i = 1}^N {{alpha _i}} {y_i}{x_i}sumlimits_{i = 1}^N {{alpha _i}{y_i} = } 0end{array}]2.带入拉格朗日函数,可得[egin{array}{l}L = frac{1}{2}sumlimits_{i = 1}^N {sumlimits_{j = 1}^N {{alpha _i}{alpha _j}} } {y_i}{y_j}({x_i} cdot {x_j}) - sumlimits_{i = 1}^N {{alpha _i}} {y_i}[(sumlimits_{j = 1}^N {{alpha _j}} {y_j}{x_j}) cdot {x_i} + b] + sumlimits_{i = 1}^N {{alpha _i}} = - frac{1}{2}sumlimits_{i = 1}^N {sumlimits_{j = 1}^N {{alpha _i}{alpha _j}} } {y_i}{y_j}({x_i} cdot {x_j}) + sumlimits_{i = 1}^N {{alpha _i}} end{array}],即[min L = - frac{1}{2}sumlimits_{i = 1}^N {sumlimits_{j = 1}^N {{alpha _i}{alpha _j}} } {y_i}{y_j}({x_i} cdot {x_j}) + sumlimits_{i = 1}^N {{alpha _i}} ]3.对上式求极大,相当于加符号求极小,从而得到最终形式[egin{array}{l}mathop {min }limits_alpha frac{1}{2}sumlimits_{i = 1}^N {sumlimits_{j = 1}^N {{alpha _i}{alpha _j}} } {y_i}{y_j}({x_i} cdot {x_j}) - sumlimits_{i = 1}^N {{alpha _i}} s.t.sumlimits_{i = 1}^N {{alpha _i}{y_i} = } 0{alpha _i} ge 0i = 12...Nend{array}]因此我们只需考虑求解上面的最终形式,从而进一步求得(wb)即可得线性可分支持向量机。这也是一个约束最优化问题,利用序列最小最优化算法(SMO)即可求解。

总结

求解线性可分支持向量机,即利用SMO求解最终形式最优化问题,得到(alpha)进一步求得(wb),从而得到分离超平面和分类决策函数。其中的推导过程需要理解明白,单纯记住一个最终模型没有意义。