支持向量机(Support Vector Machine, SVM)在1995年由Cortes等[1]首次提出,由于其拥有擅长处理小样本、非线性数据、高维模式识别的特点,并在一定程度下避免了“维数灾难”,所以基于SVM的分类器在文本分类领域中有着广泛的应用,在处理高维数据分类问题时也独占优势。与此同时应用于大型SVM的特征降维方法也成为研究热点。近年来,随机近似算法在大规模机器学习中应用广泛,其中随机投影(Random Projections, RP)方法可以快速有效地解决高维数据的降维问题,用以减少相关优化问题的计算代价。随机投影是通过控制精度来减少维度的方法,保持两个样本之间成对的距离,因此属于基于距离的方法。由于SVM也是基于距离的学习方法,故可以运用随机投影进行特征降维。2007年到2009年期间, Kumar等[2]和Jethava等[3]证明了基于高斯随机投影的SVM可以得到与原问题相近的相关误差,训练时间与投影矩阵和输入矩阵相关。2014年Paul等[4]证明了运用随机投影后的数据经过SVM训练,可以在保持特征空间的几何性质的同时保持分类器的最大间隔和最小闭包球的几何性质,维持了原有的泛化性能,并实践论证,同时从理论上证明了基于随机投影的线性核SVM(Linear kernel SVM based on random projection, rp-LSVM)训练时间与输入的非零数据的数量线性相关。
但随机投影后得到的最优解与原始问题的最优解存在一定误差,2012年Zhang等[5]将凸优化中的Fenchel对偶理论与随机投影相结合,得到一种基于对偶解恢复的随机机器学习方法,能有效地恢复原始优化问题的最优解。大规模的SVM问题本质也是大规模的优化问题,随即投影的降维方法在提升分类器训练效率的同时,也在一定程度下降低了对精度的要求。本文首先将对偶恢复思想应用于rp-LSVM中,提出基于对偶随机投影的线性核SVM(Linear kernel SVM based on dual random projection, drp-LSVM),在保持了rp-LSVM优点的同时,解决了其精度下降的问题。理论分析证明drp-LSVM在几何上比rp-LSVM更接近于所有数据训练得到的原始分类器,证明了drp-LSVM的最大间隔超平面与最小闭包球保持了与rp-LSVM近似的几何性质,同样确保了与原始空间相近的泛化能力。本文还针对提出的drp-LSVM快速求解问题,改进了序列最小优化(Sequential Minimal Optimization, SMO)算法,设计了基于改进SMO算法的drp-LSVM分类器。最后的实验证明了drp-LSVM在继承rp-LSVM优点的同时,减小了训练误差,提高了训练精度,训练结果的各项性能评价更接近于用原始数据训练得到的分类器。基于改进SMO算法的drp-LSVM分类器在减少内存消耗的同时有较高的训练精度。
1 相关概念 1.1 线性核支持向量机设有训练集D={xi, yi}(i=1, 2, …, n),xi∈Rd,类标签yi∈{-1, +1}。对于线性可分的数据,SVM学习问题最基本的思想是基于训练集D在样本空间中找到一个拥有最大间隔的划分超平面[6],转化为凸二次规划问题形式为:
$ \mathop {\min }\limits_\boldsymbol{w} \left\{ {{{\left\| w \right\|}^2}/2} \right\} $ | (1) |
$ {\text{s}}{\text{.t}}{\text{.}}\;\;{y_i}\langle \boldsymbol{w}, {\boldsymbol{x}_i}\rangle \geqslant 1\;\forall i \in \left\{ {1, 2, ..., n} \right\} $ | (2) |
这是SVM的基本形,其中w为划分超平面的法向量。当加入软间隔与正则化思想并且核函数为线性核时,相应的拉格朗日对偶问题为:
$ \mathop {\max }\limits_{\alpha \in {\boldsymbol{R}^n}} \left\{ {\sum\limits_{i = 1}^n {{\alpha _i}}-\frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}{\boldsymbol{x}_i}^{\text{T}}{\boldsymbol{x}_j}} } } \right\} $ | (3) |
$ {\text{s}}{\text{.t}}{\text{.}}\;\;\sum\limits_{i = 1}^n {{\alpha _i}{y_i} = 0} $ | (4) |
其中αi为拉格朗日算子,C≥αi≥0, i=1, 2, …, n,C为常数。
设样本数据集在半径为R的球内,支持向量到超平面的距离和(即SVM的间隔)为γ,则该假设集的VC维(Vapnik-Chervonenkis Dimension)是O(R2/γ2),如此可以估计出泛化误差界。
1.2 随机投影随机投影算法[8-9]在分类、聚类、回归、集成学习等领域有着广泛的应用。定义P:Rn→Rk是RP映射,根据J-L(Johnson-Lindenstrauss)引理[7],标准随机正交矩阵A∈Rk×d可将d维欧氏空间中包含任意m个点的集合映射到k维欧氏空间(
引理1 对任意的ε∈(0, 1) 及正整数n,m为正整数且满足:m≥4(ε2/2-ε3/3)-1ln(n)
定义P为上述RP,对任意的含n个点的集合X,对于所有的u, v∈X,有不等式成立:
$ \begin{gathered} \left( {1 - \varepsilon } \right)||\boldsymbol{u} - \boldsymbol{v}|{|^2} \leqslant ||P\left( \boldsymbol{u} \right) - P\left( \boldsymbol{v} \right)|{|^2} \leqslant \hfill \\ \;\;\left( {1 + \varepsilon } \right)||\boldsymbol{u} - \boldsymbol{v}|{|^2} \hfill \\ \end{gathered} $ | (5) |
定理1 令α∈Rd是x∈Rn经过标准高斯矩阵随机投影得到的,则有如下概率成立:
$ \begin{gathered} P\left\{ {\left( {1 - \varepsilon } \right)||{\boldsymbol{x}}||_2^2 \leqslant ||\alpha ||_2^2 \leqslant \left( {1 + \varepsilon } \right)||{\boldsymbol{x}}||_2^2} \right\} \geqslant \hfill \\ \;\;1 - 2{\text{exp}}\left( { - d/\left( {4\left( {{\varepsilon ^2} - {\varepsilon ^3}} \right)} \right)} \right) \hfill \\ \end{gathered} $ | (6) |
引理2[5] 令0 < ε≤1/2,δ∈(0, 1),V∈Rm×n是任意的正定矩阵,高斯随机矩阵A∈Rm×r,其中r=O(nε-2lg(n/δ)),则至少以1-σ的概率有如下不等式成立:‖VTV-VTAATV‖≤ε。
1.3 SMO算法SMO[10]是目前最快的求解二次规划问题的算法,特别针对LSVM和数据稀疏时性能更优。SVM训练中最核心的问题是求解二次规划问题,传统的方法利用Hessian矩阵求解最优值需要很大的计算和存储代价。SMO算法将大规模的优化问题转化为一系列包含两个变量的子问题,从而避免了复杂的数值解法,有效地节省了时间成本并降低了内存要求。SMO算法类似于坐标上升,每次启发式选择两个参数变量进行优化,不断循环,直到达到函数最优解。
SMO算法的关键步骤可以大概总结为:首先启发式选择两个参数,固定其余参数,整体视为一个二元函数,由约束条件将一个参数用另一个参数表示,视为一个一元函数,并对一元函数求极值点,最后根据上下界和约束条件,对原始解进行修剪,更新参数并取临界特殊情况,进行分析。
2 基于对偶随机投影的线性核支持向量机 2.1 随机投影的对偶恢复设有如下目标优化问题:
$ \mathop {{\text{min}}}\limits_{{\boldsymbol{w}} \in {{\text{R}}^m}} \left\{ {\frac{1}{n}\sum\limits_{i = 1}^n {L\left( {{y_i}{{\boldsymbol{w}}^{\text{T}}}{{\boldsymbol{x}}_i}} \right)} + \frac{\lambda }{2}||{\boldsymbol{w}}||_2^2} \right\} $ | (7) |
其中:
则根据Fenchel对偶定理得到原优化问题的对偶问题:
$ \mathop {{\text{max}}}\limits_{{\boldsymbol{p}} \in {{\text{R}}^n}} \left\{ { - \frac{1}{{2\lambda n}}{{\left( {{\boldsymbol{y}} \circ {\boldsymbol{p}}} \right)}^{\text{T}}}{{\boldsymbol{X}}^{\text{T}}}{\boldsymbol{X}}\left( {{\boldsymbol{y}} \circ {\boldsymbol{p}}} \right) - \sum\limits_{i = 1}^n {{L^*}\left( { - {{\boldsymbol{p}}_i}} \right)} } \right\} $ | (8) |
由凸函数的最优性条件可知
代入原问题有:
$ {{\boldsymbol{w}}_*} = \mathop {{\text{arg}}\;{\text{min}}}\limits_{{\boldsymbol{w}} \in {{\boldsymbol{\text{R}}}^m}} \left\{ {\frac{\lambda }{2}||{\boldsymbol{w}}|{|_2}^2 + \sum\limits_{i = 1}^n {{{\boldsymbol{\hat p}}_i}} {y_i}{{\boldsymbol{w}}^{\text{T}}}{{\boldsymbol{x}}_i}} \right\} $ |
用梯度求解法可求得:
$ {{\boldsymbol{w}}_*} = - X\left( {\boldsymbol{\hat p} \circ {\boldsymbol{y}}} \right)/\left( {\lambda n} \right) $ |
当样本维数m和样本数量n很大的情况下,为降低求解中的计算代价,利用随机投影算法对样本数据进行降维处理。根据随机投影定理,令A∈Rm×d为一个高斯随机矩阵,对任意的矩阵中元素有ai, j~N(0, 1/d),其中
$ \mathop {{\text{min}}}\limits_{z \in {{\boldsymbol{\text{R}}}^d}} \left\{ {\frac{1}{n}\sum\limits_{i = 1}^n {L\left( {{y_i}{{\boldsymbol{z}}^{\text{T}}}{{\boldsymbol{x}}_i}} \right)} + \frac{\lambda }{2}||{\boldsymbol{z}}||_2^2} \right\} $ | (9) |
$ \mathop {{\text{max}}}\limits_{p \in {{\boldsymbol{\text{R}}}^n}} \left\{ { - \frac{1}{{2\lambda n}}{{\left( {{\boldsymbol{y}} \circ {\boldsymbol{p}}} \right)}^{\text{T}}}{{\boldsymbol{X}}^{\text{T}}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{X}}\left( {{\boldsymbol{y}} \circ {\boldsymbol{p}}} \right) - \sum\limits_{i = 1}^n {{L^*}\left( { - {\boldsymbol{p}_i}} \right)} } \right\} $ | (10) |
同样可以求得最优解z*和对偶解
$ {{\boldsymbol{z}}_*} =-{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{X}}\left( {\boldsymbol{\hat q }\circ {\boldsymbol{y}}} \right)/\left( {\lambda n} \right) $ | (11) |
$ {\boldsymbol{\hat q}_i} = \nabla L({y_i}{\boldsymbol{z}}_*^{\text{T}}{{\boldsymbol{\alpha }}_i}) $ | (12) |
转换到高维空间,可以看作数据点被xiTAz*分类,等价于得到一个新的解
易知新解与原优化问题最优解存在较大误差,即:
$ {\left\| {\boldsymbol{\hat w}-{{\boldsymbol{w}}_*}} \right\|_2} = \Omega \left( {\sqrt {m/d} {{\left\| {{{\boldsymbol{w}}_*}} \right\|}_2}} \right) $ | (13) |
由于当E[AAT]=I,当d很大时,有
故将低维空间Fenchel对偶得到的最优解代入到原优化问题中,得到恢复后的最优解。
根据上述推导,得到基于对偶解的随机投影(drp)算法如下。
算法1 drp算法。
输入 训练集D={xi, yi},样本维度m。
输出
1) 选择高斯随机投影矩阵A∈Rm×d,计算投影后的数据矩阵:
2) 计算低维子空间下的最优解z*。
3) 计算对偶解qi=
4) 利用对偶解qi恢复原始空间的新的最优解
由于支持向量机问题可以转化为凸二次规划问题,使用拉格朗日乘子法可得到其对偶问题,类比Zhang等[5]提出的对偶随机投影算法中将低维优化问题的共轭对偶变量代入到原问题中恢复最优解的方法,将低维空间中解出的拉格朗日乘子代入到原始超平面的计算中去,得到恢复的最优超平面。
设X为输入数据矩阵,其中行为输入向量xiT,列为特征,α*=(α1*, α2*, …, αm*)为求解如下LSVM拉格朗日对偶问题的最优解向量:
$ W\left( {{\boldsymbol{\alpha} ^*}} \right) = \sum\limits_{i = 1}^m {{\alpha _i}^*} - \frac{1}{2}{{\boldsymbol{\alpha }}^*}^{\text{T}}{\boldsymbol{YX}}{{\boldsymbol{X}}^{\text{T}}}{\boldsymbol{Y}}{{\boldsymbol{\alpha }}^*} $ | (14) |
A为满足引理1的高斯投影矩阵,
$ \tilde{W}\left( {{\boldsymbol{\alpha }}^{{\tilde{*}}}} \right)=\sum\limits_{i=1}^{m}{{{\boldsymbol{\alpha }}^{{\tilde{*}}}}}-\frac{1}{2}~{{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}\boldsymbol{YXA}{{\boldsymbol{A}}^{\text{T}}}{{\boldsymbol{X}}^{\text{T}}}\boldsymbol{Y}{{\boldsymbol{\alpha }}^{{\tilde{*}}}} $ | (15) |
式(14)、(15) 原问题的最优解与最优对偶解的关系分别为w*T=α*TYX和
设原问题有最优解w*,drp-SVM的最优解为
$ \left\| {\mathop {{\boldsymbol{w}^*}-{\boldsymbol{w}^*}}\limits^ \wedge } \right\|/\left\| {{\boldsymbol{w}^*}} \right\| \leqslant \varepsilon /\left( {1-\varepsilon } \right) $ | (16) |
证明 令E=VTV-VTAATV
将上述式(14)、(15) 问题经过奇异值分解(Singular Value Decomposition, SVD)分解得到:
$ \begin{gathered} W\left( {{{\boldsymbol{\alpha }}^*}} \right) = \sum\limits_{i = 1}^m {{{\boldsymbol{\alpha }}_i}^*} - \frac{1}{2}{{\boldsymbol{\alpha }}^*}^{\text{T}}{\boldsymbol{YU\Sigma }}{{\boldsymbol{V}}^{\text{T}}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{V\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}{{\boldsymbol{\alpha }}^*} - \hfill \\ \frac{1}{2}{{\boldsymbol{\alpha }}^*}^{\text{T}}{\boldsymbol{YU\Sigma E\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}{{\boldsymbol{\alpha }}^*} \hfill \\ \end{gathered} $ | (17) |
$ \tilde W\left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}} } \right) = \sum\limits_{i = 1}^m {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}} }-\frac{1}{2}{{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}{\boldsymbol{YU\Sigma }}{{\boldsymbol{V}}^{\text{T}}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{V\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}} $ | (18) |
由式(17)、(18) 有如下不等式成立:
$ \begin{gathered} W\left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}} } \right) \geqslant \tilde W\left( {{{\boldsymbol{\alpha }}^*}} \right) + \hfill \\ \frac{1}{2}{\left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^*}} \right)^{\text{T}}}{\boldsymbol{YU\Sigma }}{{\boldsymbol{V}}^{\text{T}}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{V\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}\left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^*}} \right) \hfill \\ \end{gathered} $ | (19) |
又由拉格朗日对偶函数的凹性可知:
$ \begin{align} &W\left( {{\boldsymbol{\alpha }}^{{\tilde{*}}}} \right)+\frac{1}{2}{{\left( {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^{*}} \right)}^{\text{T}}}\boldsymbol{YU\Sigma }{{\boldsymbol{V}}^{\text{T}}}\boldsymbol{A}{{\boldsymbol{A}}^{\text{T}}}\boldsymbol{V\Sigma }{{\boldsymbol{U}}^{\text{T}}}\boldsymbol{Y}\left( {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^{*}} \right) \\ &\le \tilde{W}\left( {{\boldsymbol{\alpha }}^{*}} \right)+{{\left( {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^{*}} \right)}^{\text{T}}} \\ &.\left( \boldsymbol{YU\Sigma }{{\boldsymbol{V}}^{\text{T}}}\boldsymbol{A}{{\boldsymbol{A}}^{\text{T}}}\boldsymbol{V\Sigma }{{\boldsymbol{U}}^{\text{T}}}\boldsymbol{Y}-\boldsymbol{YU\Sigma }{{\boldsymbol{V}}^{\text{T}}}\boldsymbol{V\Sigma }{{\boldsymbol{U}}^{\text{T}}}\boldsymbol{Y} \right)\left( {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^{*}} \right) \\ \end{align} $ | (20) |
由式(19)、(20) 两个不等式得到:
$ \begin{gathered} {\left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^*}} \right)^{\text{T}}}\left( {{\boldsymbol{YU\Sigma }}{{\boldsymbol{V}}^{\text{T}}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{V\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}-{\boldsymbol{YU\Sigma }}{{\boldsymbol{V}}^{\text{T}}}{\boldsymbol{V\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}} \right) \cdot \hfill \\ \left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^*}} \right) \geqslant {\left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}} - {{\boldsymbol{\alpha }}^*}} \right)^{\text{T}}}Y{\boldsymbol{U\Sigma }}{{\boldsymbol{V}}^{\text{T}}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{V\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}\left( {\mathop {{\boldsymbol{\alpha }}^{{\tilde{*}}}} - {{\boldsymbol{\alpha }}^*}} \right) \hfill \\ \end{gathered} $ | (21) |
即:
$ \begin{gathered} {\left( {\mathop {\widetilde {{{\boldsymbol{\alpha }}^*}}} - {{\boldsymbol{\alpha }}^*}} \right)^{\text{T}}}{\boldsymbol{YU\Sigma E\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}{{\boldsymbol{\alpha }}^*} \geqslant \hfill \\ {\left( {\mathop {\widetilde {{{\boldsymbol{\alpha }}^*}}} - {{\boldsymbol{\alpha }}^*}} \right)^{\text{T}}}{\boldsymbol{YU\Sigma }}{{\boldsymbol{V}}^{\text{T}}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{\boldsymbol{V\Sigma }}{{\boldsymbol{U}}^{\text{T}}}{\boldsymbol{Y}}\left( {\mathop {\widetilde {{{\boldsymbol{\alpha }}^*}}} - {{\boldsymbol{\alpha }}^*}} \right) \hfill \\ \end{gathered} $ | (22) |
结合引理2可得:
$ \left( 1-\varepsilon \right){{\left\| {{{\boldsymbol{\hat{w}}}}^{*}}-{{\boldsymbol{w}}^{*}} \right\|}_{2}}\le \varepsilon {{\left\| {{\boldsymbol{w}}^{*}} \right\|}_{2}} $ | (23) |
将低位空间的最优解转换高维空间后有关系:
$ {{\boldsymbol{w}}^{{\tilde{*}}}}~=\boldsymbol{A}{{\boldsymbol{A}}^{\text{T}}}{{{\boldsymbol{\hat{w}}}}^{*}} $ | (24) |
则易求得:
$ {{\left\| {{{\boldsymbol{\hat{w}}}}^{*}}-{{\boldsymbol{w}}^{*}} \right\|}_{2}}\le \frac{\varepsilon }{\left( 1-\varepsilon \right)}{{\left\| {{\boldsymbol{w}}^{*}} \right\|}_{2}}+\varepsilon {{\left\| {{\boldsymbol{w}}^{*}} \right\|}_{2}} $ | (25) |
由式(23)、(25) 可以看出,drp-LSVM求得的最优解比直接经过随机投影降维的LSVM的最优解更接近原始最优解,即从几何上更接近于原始分类器。
下面论证drp-LSVM最大间隔超平面的几何性质。
利用SVD有:
$ W({{\boldsymbol{\alpha }}^{*}})\ge \sum\limits_{i=1}^{m}{{{\boldsymbol{\alpha }}^{{\tilde{*}}}}}-\frac{1}{2}{{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{T}\boldsymbol{YU\Sigma }{{\boldsymbol{V}}^{\text{T}}}\boldsymbol{A}{{\boldsymbol{A}}^{\text{T}}}\boldsymbol{V\Sigma }{{\boldsymbol{U}}^{\text{T}}}\boldsymbol{Y}{{\boldsymbol{\alpha }}^{{\tilde{*}}}}-\frac{1}{2}{{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{T}\boldsymbol{YU\Sigma E\Sigma }{{\boldsymbol{U}}^{\text{T}}}\boldsymbol{Y}{{\boldsymbol{\alpha }}^{{\tilde{*}}}} $ | (26) |
即有不等式(27) 如下:
$ W({{\boldsymbol{\alpha }}^{*}})\ge W({{\boldsymbol{\alpha }}^{{\tilde{*}}}})-\frac{1}{2}{{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}\boldsymbol{YU\Sigma E\Sigma }{{\boldsymbol{U}}^{\text{T}}}\boldsymbol{Y}{{\boldsymbol{\alpha }}^{{\tilde{*}}}}\ge \text{ }W({{\boldsymbol{\alpha }}^{{\tilde{*}}}})-\frac{1}{2}{{\left\| \boldsymbol{E} \right\|}_{2}}\left\| {{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}\boldsymbol{YX} \right\|_{2}^{2}\text{ } $ | (27) |
易得不等式(28) 如下:
$ \begin{align} &\left| \ \ \ \left\| {{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}~\boldsymbol{YXA} \right\|_{2}^{2}-\left\| {{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}~\boldsymbol{YX} \right\|_{2}^{2}\ \ \right|=\left| {{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}~\boldsymbol{YXA}{{\boldsymbol{A}}^{\text{T}}}{{\boldsymbol{X}}^{\text{T}}}\boldsymbol{Y}{{\boldsymbol{\alpha }}^{{\tilde{*}}}}-{{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}~\boldsymbol{YX}{{\boldsymbol{X}}^{\text{T}}}\boldsymbol{Y}{{\boldsymbol{\alpha }}^{{\tilde{*}}}} \right| \\ &=\left| {{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}~\boldsymbol{YU\Sigma }\left( -\boldsymbol{E} \right)\boldsymbol{\Sigma }{{\boldsymbol{U}}^{\text{T}}}\boldsymbol{Y}{{\boldsymbol{\alpha }}^{{\tilde{*}}}} \right|\le {{\left\| \boldsymbol{E} \right\|}_{2}}\left\| {{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}~\boldsymbol{YX} \right\|_{2}^{2} \\ \end{align} $ | (28) |
将(28) 代入(27) 则有:
$ W\left( {{\boldsymbol{\alpha }}^{*}} \right)\ge W\left( {{\boldsymbol{\alpha }}^{{\tilde{*}}}} \right)-\frac{1}{2}\frac{{{\left\| \boldsymbol{E} \right\|}_{2}}}{1-{{\left\| \boldsymbol{E} \right\|}_{2}}}\left\| {{\boldsymbol{\alpha }}^{{\tilde{*}}}}^{\text{T}}\boldsymbol{YXA} \right\|_{2}^{2} $ | (29) |
由于
$ \left\| {{\boldsymbol{w}}^{*}} \right\|_{2}^{2}\ge \left\| \widetilde{{{\boldsymbol{w}}^{*}}}~ \right\|_{2}^{2}-\frac{{{\left\| \boldsymbol{E} \right\|}_{2}}}{1-{{\left\| \boldsymbol{E} \right\|}_{2}}}\left\| \widetilde{{{\boldsymbol{w}}^{*}}}~ \right\|_{2}^{2} $ | (30) |
由不等式(28) 可知:
$ \left\| \overset{\wedge }{\mathop{{{\boldsymbol{w}}^{*}}}}\, \right\|_{2}^{2}\le \left( 1/\left( 1-2{{\left\| \boldsymbol{E} \right\|}_{2}} \right) \right)\left\| \widetilde{{{\boldsymbol{w}}^{*}}}~ \right\|_{2}^{2} $ | (31) |
结合式(25)、(31) 得到:
$ \left\| {{\boldsymbol{w}}^{*}} \right\|_{2}^{2}\ge \left( 1-2{{\left\| \boldsymbol{E} \right\|}_{2}} \right)\left\| {{{\boldsymbol{\hat{w}}}}^{*}} \right\|_{2}^{2} $ | (32) |
即:
$ \mathop {{\gamma ^*}^2}\limits^ \wedge \geqslant \left( {1-2{{\left\| {\boldsymbol{E}} \right\|}_2}} \right){\gamma ^*}^2 $ |
由引理2可得:
$ \left\{ \begin{matrix} \overset{\wedge }{\mathop{{{\gamma }^{*}}^{2}}}\,/{{\gamma }^{*}}^{2}\ge 1-2\varepsilon \ \ \ \ \ \ \ \ \ \\ {{\gamma }^{{\tilde{*}}}}^{2}/{{\gamma }^{*}}^{2}\ge 1-\varepsilon /\left( 1-\varepsilon \right) \\ \end{matrix} \right. $ | (33) |
同样可以利用SVD和引理2证明最小闭包球(Minimum Enclosing Ball, MEB)的性质如下。
由于LSVM的MEB的拉格朗日对偶问题为:
$ \begin{gathered} {\text{max}}\left\{ {{{\boldsymbol{\alpha }}^{\text{T}}}\left( {{\text{diag}}\left( {{\boldsymbol{X}}{{\boldsymbol{X}}^{\text{T}}}} \right)} \right) - {{\boldsymbol{\alpha }}^{\text{T}}}{\boldsymbol{X}}{{\boldsymbol{X}}^{\text{T}}}{\boldsymbol{\alpha }}} \right\} \hfill \\ {\text{s}}{\text{.t}}{\text{. }} {{\boldsymbol{\alpha }}^{\text{T}}}1 = 1, {\boldsymbol{\alpha }} \geqslant 0 \hfill \\ \end{gathered} $ | (34) |
设闭包球半径为R,球心向量为xc,则:
$ {R^2} = {{\boldsymbol{\alpha }}^{\text{T}}}\left( {{\text{diag}}\left( {{\boldsymbol{X}}{{\boldsymbol{X}}^{\text{T}}}} \right)} \right) - {{\boldsymbol{\alpha }}^{\text{T}}}{\boldsymbol{X}}{{\boldsymbol{X}}^{\text{T}}}{\boldsymbol{\alpha }} $ | (35) |
$ {{\boldsymbol{x}}_c} = \sum\limits_{i = 1}^m {{\alpha _i}{{\boldsymbol{x}}_i}} $ | (36) |
经随机投影后:
$ {{{\hat{R}}}^{2}}~={{{\boldsymbol{\tilde{\alpha }}}}^{\text{T}}}~\left( \text{diag}\left( \boldsymbol{XA}{{\boldsymbol{A}}^{\text{T}}}{{\boldsymbol{X}}^{\text{T}}} \right) \right)-{{{\boldsymbol{\tilde{\alpha }}}}^{\text{T}}}~\boldsymbol{XA}{{\boldsymbol{A}}^{\text{T}}}{{\boldsymbol{X}}^{\text{T}}}\boldsymbol{\tilde{\alpha }} $ | (37) |
对偶恢复后:
$ {{{\hat{R}}}^{2}}={{{\boldsymbol{\tilde{\alpha }}}}^{\text{T}}}~\left( \text{diag}\left( \boldsymbol{X}{{\boldsymbol{X}}^{\text{T}}} \right) \right)-{{{\boldsymbol{\tilde{\alpha }}}}^{\text{T}}}\boldsymbol{X}{{\boldsymbol{X}}^{\text{T}}}\boldsymbol{\tilde{\alpha }} $ |
结合引理2易推得:
$ {{{\hat{R}}}^{2}}~\le \left( 1+\varepsilon \right){{{\hat{R}}}^{2}}\le \left( 1+\varepsilon \right){{R}^{2}};{{{\hat{R}}}^{2}}\le {{R}^{2}} $ | (38) |
由上述理论分析可以得到,drp-LSVM的间隔和最小闭包球半径与rp-LSVM相近,同样保持了与原始空间的ε相关误差,维持了与原空间相似的泛化性能。
3 基于改进SMO算法的drp-LSVM分类器虽然LSVM的训练和测试速度相对较快,但与KSVM相同,LSVM中最核心的问题还是求解二次规划问题,本文为求解基于对偶随机投影的LSVM设计了基于对偶随机投影的SMO算法,主要思想如下:
假定在求解低维拉格朗日对偶问题的某一次迭代中,需要更新用启发式方法选取的一对拉格朗日算子为
第一步 计算上下界H和L:
$ \left\{ \begin{matrix} L=\text{max}\left( 0,\alpha _{2}^{{\tilde{*}}}-\alpha _{1}^{{\tilde{*}}} \right)\text{且}\ \ \ \ \ \ \ \ \ \ \ \ \ \\ H=\text{min}\left( C,C+\alpha _{2}^{{\tilde{*}}}-\alpha _{1}^{{\tilde{*}}} \right),{{y}_{1}}\ne {{y}_{2}} \\ L=\text{max}\left( 0,\alpha _{2}^{{\tilde{*}}}+\alpha _{1}^{{\tilde{*}}}-C \right)\text{且}\ \ \ \ \ \ \ \ \ \\ H=\text{min}\left( C,\alpha _{2}^{{\tilde{*}}}+\alpha _{1}^{{\tilde{*}}} \right),\ \ \ \ \ \ \ \ {{y}_{1}}={{y}_{2}} \\ \end{matrix} \right. $ | (39) |
第二步 计算Ws的二阶导η,并更新Ws:
$ \eta = {\boldsymbol{x}}_1^{\text{T}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{{\boldsymbol{x}}_1} + {\boldsymbol{x}}_2^{\text{T}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{x_2} - 2{\boldsymbol{x}}_1^{\text{T}}{\boldsymbol{A}}{{\boldsymbol{A}}^{\text{T}}}{{\boldsymbol{x}}_2} $ | (40) |
$ \alpha _{2}^{*}\widetilde{\text{temp}}~~=\alpha _{2}^{{\tilde{*}}}-{{y}_{2}}\left( {{e}_{1}}-{{e}_{2}} \right)\text{=}/\eta $ | (41) |
$ {e_i} = g({\boldsymbol{x}_i}) - {y_i} $ | (42) |
第三步 计算更新
$ \alpha {{_{2}^{{\tilde{*}}}}_{\text{new}}}=\left\{ \begin{matrix} H,\ \ \ \ \ \ \ \ \ \ \alpha _{2\text{temp}}^{{\tilde{*}}}\ge H \\ \alpha _{2\text{temp}}^{{\tilde{*}}},\ \ \ \ \ L\le \alpha _{2\text{temp}}^{{\tilde{*}}}\ \le H \\ L,\ \ \ \ \ \ \ \ \ \ \ \ \alpha _{2\text{temp}}^{{\tilde{*}}}\ \le L \\ \end{matrix} \right. $ | (43) |
$ \alpha {{_{1}^{{\tilde{*}}}}_{\text{new}}}=\alpha _{1}^{{\tilde{*}}}+{{y}_{1}}{{y}_{2}}\left( \alpha _{2}^{{\tilde{*}}}-\alpha {{_{2}^{{\tilde{*}}}}_{\text{new}}} \right) $ | (44) |
第四步 在原空间下更新:
$ {{{\boldsymbol{\hat{w}}}}_{\text{new}}}=\boldsymbol{\hat{w}}+{{y}_{1}}\left( \alpha _{1\text{new}}^{{\tilde{*}}}-\alpha _{1}^{{\tilde{*}}} \right){{\boldsymbol{x}}_{1}}+{{y}_{2}}\left( \alpha {{_{2}^{{\tilde{*}}}}_{\text{new}}}-\alpha _{2}^{{\tilde{*}}} \right){{\boldsymbol{x}}_{2}} $ | (45) |
收敛条件为在界内的样例都能够满足卡罗需-库恩-塔克(Karush-Kuhn-Tucker, KTT)条件,且其对应的αi只在极小范围内变动,设计流程如图 1所示。
实验环境为2.6 GHz Intel Core i5处理器,8 GB内存,操作系统为Linux,开发工具为Python、Java。实验数据来自lib-SVM Data[11],实验一基于Liblinear库[12]进行drp-SVM相关性能测试,参数设置为默认参数。实验二测试基于改进SMO算法的drp-SVM性能。数据集D1、D2分别为gisette_scale[13]、rcv1.binary[14]。D1含训练样本6 000,测试样本1 000,样本维数为5 000,满足中等规模数据量及维数的特征;D2含训练样本202 421,测试样本677 399,维数为47 236,满足大规模高维度数据特征。为保证实验的准确度和可信度,相关实验重复5次,最终实验数据取平均值。
4.1 实验一针对中等规模数据集D1,为检验分类器效果,考虑到数据集维数为5 000,则取四种不同投影维数512、1 024、2 048、4 096,在各种目标维数下分别计算drp-SVM,rp-SVM和原分类器(即用全部数据训练出来的支持向量机,图中用full表示)的相关评估参数。图 2分别为三种分类器在不同维度下精度(Accuracy, ACC)、均方误差(Mean Square Error, MSE)及平方相关系数(Squared Correlation Coefficient, SCC)的关系。
由图 2可看出,相比于rp-SVM,drp-SVM的各项训练指标都更接近于所有训练数据得到的原始分类器。
针对较大规模数据集D2,结合数据集维数47 236,取四种不同投影维数1 024、2 048、4 096、8 192,在各种目标维数下分别计算drp-SVM、rp-SVM和原分类器(即用全部数据训练出来的支持向量机,图中用full表示)的相关评估参数。图 3分别为三种分类器在不同维度下精度(ACC)、均方误差(MSE)及平方相关系数(SCC)的关系。
由图 3可看出,在大规模更高维度的数据集环境下,drp-SVM的各项训练指标更优于rp-SVM,同时更加接近原始分类器。
表 1~2分别为针对数据集D1和D2训练不同分类器在最优投影维数下训练时间(用time表示,单位为s)、最大间隔(γ)、5次交叉检验(5-fold)后的精度以及分类错误率(errorRate)的统计。
从表 1~2可以看出,相比于rp-SVM,drp-SVM保留了其训练时间减少和保持最大间隔的优点,并在此基础上提高了训练精度,减小了误差。
4.2 实验二用数据集D1来测试基于改进SMO算法的drp-SVM性能,为方便对比,将三种算法的训练时间(用time表示,单位为h)、训练中消耗内存比(用memory表示)及分类错误率(用errorRate表示)在一张图中展现,如图 4所示。
由图 4可以看出,运用改进的算法(drp-SMO)的分类器比运用所有数据训练的基于SMO算法的分类器(full-SMO)的分类器更高效、更节省内存,且相比直接经过随机投影的SMO分类器(rp-SMO)准确度更接近原始分类器。
5 结语本文针对特征降维后的支持向量机精度下降等问题,设计了基于对偶随机投影的线性核支持向量机(drp-LSVM)相关算法,并从理论分析的角度证明了求解drp-LSVM问题得到的最优解比rp-LSVM的最优解更接近于原始分类器得到的最优解,保证了在特征降维后,训练得到的分类器能够保持与原分类器相似的几何性质。文中还证明了drp-LSVM的最大间隔超平面与最小闭包球保持了与rp-LSVM近似的ε相关误差,同样确保了与原始空间相近的泛化能力。文中提出针对drp-LSVM的改进SMO算法,设计了基于改进SMO算法的分类器。大规模高维的数据集的实验证明了drp-LSVM在降维特征提高训练速度的同时,训练效果及性能评价更接近于原始分类器,改进SMO算法在保持了算法稳定性的同时拥有较高的训练速度和精度。本文仅围绕特殊的线性核支持向量机以及高斯投影进行了针对性研究,并没有考虑非线性核及其他种类的随机投影特征降维情况。大规模机器学习仍是目前主流的挑战,有关随机机器学习的技术方法有待进一步深入研究。
[1] | CORTES C, VAPNIK V. Support-vector networks[J]. Machine Learning, 1995, 20(3): 273-297. |
[2] | KUMAR K, BHATTACHARYYA C, HARIHARAN R. A randomized algorithm for large scale support vector learning[EB/OL].[2016-10-09]. http://hariharan-ramesh.com/papers/krichiram_nips_07.pdf. |
[3] | JETHAVA V, SURESH K, BHATTACHARYYA C, et al. Randomized algorithms for large scale SVMs[EB/OL].[2016-10-09]. https://www.researchgate.net/publication/45873558_Randomized_Algorithms_for_Large_scale_SVMs. |
[4] | PAUL S, BOUTSIDIS C, MAGDON-ISMAIL M, et al. Random projections for linear support vector machines[J]. ACM Transactions on Knowledge Discovery from Data, 2014, 8(4): Article No. 22. |
[5] | ZHANG L J, MAHDAVI M, JIN R, et al. Recovering the optimal solution by dual random projection[J]. Journal of Machine Learning Research, 2012, 30: 135-157. |
[6] | 周志华. 机器学习[M]. 北京: 清华大学出版社, 2016 : 121 -145. ( ZHOU Z H. Machine Learning[M]. Beijing: Tsinghua University Press, 2016 : 121 -145. ) |
[7] | 刘红, 刘蓉, 李书玲. 基于随机投影的加速度手势识别[J]. 计算机应用, 2015, 35(1): 189-193. ( LIU H, LIU R, LI S L. Acceleration gesture recognition based on random projection[J]. Journal of Computer Applications, 2015, 35(1): 189-193. doi: 10.11772/j.issn.1001-9081.2015.01.0189 ) |
[8] | 王萍, 蔡思佳, 刘宇. 基于随机投影技术的矩阵填充算法的改进[J]. 计算机应用, 2014, 34(6): 1587-1590. ( WANG P, CAI S J, LIU Y. Improvement of matrix completion algorithm based on random projection[J]. Journal of Computer Applications, 2014, 34(6): 1587-1590. doi: 10.11772/j.issn.1001-9081.2014.06.1587 ) |
[9] | PLATT J C. Fast training of support vector machines using sequential minimal optimization[M]. Cambridge, MA: MIT Press, 1999 : 185 -208. |
[10] | CHANG C C, LIN C J. LIBSVM:a library for support vector machines[J]. ACM Transactions on Intelligent Systems & Technology, 2011, 2(3). |
[11] | FAN R E, CHANG K W, HSIEH C J, et al. LIBLINEAR:a library for large linear classification[J]. Journal of Machine Learning Research, 2008, 9: 1871-1874. |
[12] | GOLUB T R, SLONIM D K, TAMAYO P, et al. Molecular classification of cancer:class discovery and class prediction by gene expression monitoring[J]. Science, 1999, 286(5439): 531-537. doi: 10.1126/science.286.5439.531 |
[13] | LEWIS D D, YANG Y, ROSE T G, et al. RCV1:a new benchmark collection for text categorization research[J]. Journal of Machine Learning Research, 2004, 5: 361-397. |