上海理工大学，理学院，上海

收稿日期：2020年10月26日；录用日期：2020年11月11日；发布日期：2020年11月18日

摘要

为了提高光滑支撑向量机模型的分类性能，文章给出了一种新的光滑函数反比例函数，并利用光滑技术克服了支撑向量机模型的不可微性，通过数学理论上严谨的论证和分析，证明了所给出光滑函数的性质和基于此光滑函数所建立的反比例光滑支撑向量机模型(ISSVM)的收敛性。实验数值表明，反比例光滑支撑向量机比多项式光滑支撑向量机在分类性能上更有优越性。

关键词

光滑支撑向量机，反比例光滑函数，BFGS算法

Inverse Proportional Smooth Support Vector Machine

Zhen Wu, Zhensheng Yu^*

University of Shanghai for Science and Technology, Shanghai

Received: Oct. 26^th, 2020; accepted: Nov. 11^th, 2020; published: Nov. 18^th, 2020

ABSTRACT

In order to improve the classified performance of smooth support vector machine model, a new smoothed function inverse proportional function is presented, and smoothing technique is used to overcome the non-differentiability of support vector machine model. Through rigorous demonstration and analysis in mathematical theory, the properties of the given smoothing function and the convergence of the inverse proportional smoothing support vector machine (ISSVM) model based on the smoothing function are proved. The experimental results show that the inverse proportional smoothing support vector machine is superior to the polynomial smoothing support vector machine in classified performance.

Keywords:Smooth Support Vector Machine, Inverse Proportional Smoothing Function, BFGS Algorithm

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

2001年Lee等人通过对支撑向量机的深入研究引入光滑的概念，使用了sigmoid积分函数p(x,α)对无约束的支撑向量机模型SVM [1] 进行光滑化，得出了分类性能较好的光滑支撑向量机SSVM [2]。继而使用Newton-Armijo算法对SSVM进行求解，结果展现出了SSVM比标准SVM具有更好的分类性能和较高的计算效率，从此光滑函数作为SSVM模型的核心引起了人们的广泛关注，并开辟了支撑向量机的一个新的研究方向。

2005年文献 [3] 提出了两个多项式光滑函数，同时对无约束的支撑向量机模型进行光滑化处理，引出了PSSVM模型。可以证明，PSSVM比SSVM有更好的分类性能。之后文献 [4] 提出了三阶样条光滑函数，从而引出了新的支撑向量机的TSSVM模型。通过分析TSSVM模型的收敛性，并通过数据实验可以说明TSSVM分类器的效果要更优。2008年，文献 [5] 提出了六阶光滑函数，此光滑函数逼近正号函数的精度比三阶样条光滑函数更是高了一个数量级。2014年，吴青等人在此基础上提出指数光滑支持向量分类机 [6] 的模型，证明了其收敛性并通过数值实验表明了指数光滑支持向量机比多项式光滑支持向量机在分类性能上更有优势。

很明显可以得知，光滑支撑向量机的分类性能随着光滑函数的逼近精度提高而改善，那么，能否寻求一种新的光滑函数使得光滑支撑向量机的分类性能获得提升，一直是学者研究关于相关SVM问题的热点。本文通过借鉴指数光滑支持向量机模型中指数光滑函数的性质对反比例函数的研究提出了新的光滑函数，并对支撑向量机模型光滑化处理得出了反比例光滑支撑向量机。

2. 反比例光滑函数

根据光滑函数是支撑向量机研究的重点，依据反比例函数的一些性质，提出反比例光滑函数

$i\left(x,k\right)=\{\begin{array}{l}x,x>\frac{1}{10k}\\ \frac{1}{10k\left(2-10kx\right)},x\le \frac{1}{10k}\end{array}$

性质1已知光滑函数 $i\left(x,k\right)$ 并且 $x_{+}$ 是正号函数，那么

1) $i\left(x,k\right)$ 关于x一阶光滑。

2) 当 $x\to -\infty$ 且 $k>0$ 时， $i\left(x,k\right)\to 0$。

证明 对函数 $i\left(x,k\right)$ 关于变量x求一阶导得分段函数

$i^{\prime }\left(x,k\right)=\{\begin{array}{l}1,x>\frac{1}{10k}\\ \frac{1}{{\left(2-10kx\right)}^2},x\le \frac{1}{10k}\end{array}$

因为 $i^{\prime }\left(x,k\right)$ 在分段点处左右极限存在并且左极限

$\underset{x\to \frac{1}{10k}-}{\lim }\frac{1}{{\left(2-10kx\right)}^2}=1$

与右极限相等，故为 $i^{\prime }\left(x,k\right)$ 在整个区间连续，又因

$i^{″}\left(x,k\right)=\{\begin{array}{l}0,x>\frac{1}{10k}\\ \frac{20k}{{\left(2-10kx\right)}^3},x\le \frac{1}{10k}\end{array}$

在分段点处左右极限皆存在，但其右极限为0而左极限非0，所以 $i^{″}\left(x,k\right)$ 在断点处不连续。综上可知 $i\left(x,k\right)$ 关于x一阶光滑。

当 $x\to -\infty$ 并且 $k>0$ 时，对 $i\left(x,k\right)$ 求极限，即得

$\underset{x\to -\infty }{\lim }\frac{1}{10k\left(2-10kx\right)}=0$

性质2已知光滑函数 $i\left(x,k\right)$ 并且 $x_{+}$ 是正号函数，那么

1) $i\left(x,k\right)\ge x_{+}$。

2) 对于 $x\in \left(-\infty ,+\infty \right)$，当 $k>0$ 时，有

$i^2\left(x,k\right)-x_{+}^2\le 0.00131105\frac{1}{k^2}$

证明 当 $x>\frac{1}{10k}$ 时，显然有 $i\left(x,k\right)\ge x_{+}$，而当 $0\le x\le \frac{1}{10k}$ 时，构造函数

$f_1\left(x,k\right)=i\left(x,k\right)-x_{+}=\frac{1}{10k\left(2-10kx\right)}-x$

对 $f_1\left(x,k\right)$ 求导得

${f^{\prime }}_1\left(x,k\right)=\frac{1}{{\left(2-10kx\right)}^2}-1<0\left(0\le x\le \frac{1}{10k}\right)$

故 $f_1\left(x,k\right)$ 在 $\left(0,\frac{1}{10k}\right)$ 内单调递减，又因 $f_1\left(x,k\right)$ 在 $x=\frac{1}{10k}$ 处取得最小值0，因此

$f_1\left(x,k\right)=i\left(x,k\right)-x_{+}\ge 0$

也即 $i\left(x,k\right)\ge x_{+}$。另当 $x<0$ 时，显然有

$f_2\left(x,k\right)=i\left(x,k\right)-0=\frac{1}{10k\left(2-10kx\right)}>0$

因此也有 $i\left(x,k\right)\ge x_{+}$。综上可得结论(1)。

当 $x\ge \frac{1}{10k}$ 时，结论(2)显然成立。当 $0<x<\frac{1}{10k}$ 时， $x_{+}=x$，于是对

$g_1\left(x,k\right)=i^2\left(x,k\right)-x^2=\frac{1}{100k^2{\left(2-10kx\right)}^2}-x^2$

关于x求导得

${g^{\prime }}_1\left(x,k\right)=\frac{1}{5k{\left(2-10kx\right)}^3}-2x$

用二分法 [7] 求得导函数的零点为

$x_0=0.020312\frac{1}{k}$

可求得 $g_1\left(x,k\right)$ 在 $x_0$ 处取得最大值为

$g_1\left(x_0,k\right)=0.00131105\frac{1}{k^2}$

另当 $x<0$ 时， $x_{+}=0$，于是

$g_2\left(x,k\right)=i^2\left(x,k\right)=\frac{1}{100k^2{\left(2-10kx\right)}^2}$

在 $(-\infty ,0]$ 上单调递增，且其最大值

$g_2\left(0,k\right)=\frac{1}{400k^2}=0.0025\frac{1}{k^2}$

综上可知结论(2)成立，且

$i^2\left(x,k\right)-x_{+}^2\le 0.00131105\frac{1}{k^2}<0.0188\frac{1}{k^2}$

性质2表明了反比例光滑函数对正号函数的逼近精度比六阶光滑函数提高了一个数量级。

光滑因子为 $k=10$ 时，各个光滑函数对正号函数的逼近程度如图1所示，从中可见，反比例光滑函数的逼近效果更好。

图1. 不同光滑函数的逼近程度

3. ISSVM模型及其收敛性

由软间隔支撑向量机的原始型和对偶形式我们可以对其进行求解得到 ${\alpha }_i^{*}$，于是分类函数

$\begin{array}{c}f\left(x\right)=\text{sign}\left[\underset{i=1}{\overset{m}{{\displaystyle \sum }}}{y}_i{\alpha }_i^{*}\left(\phi \left(x_i\right),\phi \left(x\right)\right)+b^{*}\right]\\ =\text{sign}\left[\underset{i=1}{\overset{m}{{\displaystyle \sum }}}{y}_i{\alpha }_i^{*}K\left(x_i,x\right)+b^{*}\right]\end{array}$ (1)

其中

$b^{*}=\frac{1}{m}\underset{i=1}{\overset{m}{{\displaystyle \sum }}}\left(y_i-\underset{i=1}{\overset{m}{{\displaystyle \sum }}}{y}_i{\alpha }_j^{*}\left(\phi \left(x_j\right),\phi \left(x_i\right)\right)\right)$ (2)

令 $M={\left(x_1,x_2,\cdots ,x_m\right)}^{\text{T}}$

$x_i=\left(x_i{}_1,x_i{}_2,\cdots ,x_i{}_n\right)\left(i=1,2,\cdots ,m\right)，$

$e=\text{ones}\left(m,1\right)$，$D=\text{diag}\left(y_1,y_2,\cdots ,y_m\right)$，$H=DK\left(M,M^{\text{T}}\right)D$

则原始问题改写为

$\{\begin{array}{l}\underset{\alpha ,b}{\min }\frac{1}{2}{\alpha }^{\text{T}}H\alpha +C{e}^{\text{T}}\xi \\ \text{s}\text{.t}\text{.}D\left(K\left(M,M^{\text{T}}\right)D\alpha +eb\right)-e+\xi \ge 0,\xi \ge 0\end{array}$ (3)

对于任何核函数，上式均是个凸二次规划问题，不妨取 $H=I$，同时用b衡量分类间隔 $\left(\frac{2}{{\Vert \left(w,b\right)\Vert }_2}\right)$，于是在对偶问题中 $b=-e^{\text{T}}D\alpha$，同时让松弛变量 ${\xi }^{\text{T}}\xi$ 最小，则(3)式转化为

$\{\begin{array}{l}\underset{\alpha ,b}{\min }\frac{1}{2}\left({\alpha }^{\text{T}}\alpha +b^2\right)+\frac{c}{2}{\xi }^{\text{T}}\xi \\ \text{s}\text{.t}.D\left(K\left(M,M^{\text{T}}\right)D\alpha +eb\right)-e+\xi \ge 0,\xi \ge 0\end{array}$ (4)

由约束条件知，

$\xi ={\left(e-D\left(K\left(M,M^{\text{T}}\right)D\alpha +eb\right)\right)}_{+}$

这里是非光滑的。将其代入问题(12)，得到一个强凸无约束优化问题

$\underset{\alpha ,b}{\min }\frac{1}{2}\left({\alpha }^{\text{T}}\alpha +b^2\right)+\frac{c}{2}{\Vert {\left(e-D\left(K\left(M,M^{\text{T}}\right)D\alpha +eb\right)\right)}_{+}\Vert }^2$ (5)

有唯一解。

我们用反比例函数对上述无约束支撑向量机模型SVM进行光滑化，可以得到一个新的光滑支撑向量机模型

$\underset{\alpha ,b}{\min }\frac{1}{2}\left({\alpha }^{\text{T}}\alpha +b^2\right)+\frac{c}{2}{\Vert i\left(e-D\left(K\left(M,M^{\text{T}}\right)D\alpha +eb\right),k\right)\Vert }_2^2$ (6)

称之为ISSVM模型。

记 $\omega =\alpha ,\gamma =-b,A=K\left(M,M^{\text{T}}\right)D$，则上式可化为

$\underset{\omega ,\gamma }{\min }\frac{1}{2}\left({\omega }^{\text{T}}\omega +{\gamma }^2\right)+\frac{c}{2}{\Vert i\left(e-D\left(A\omega -e\gamma \right),k\right)\Vert }_2^2$

分析反比例光滑支撑向量机模型，可以证明此模型收敛。该模型的最优解在 $k\to +\infty$ 时无限逼近无约束SVM模型的最优解。

定理1设 $A\in {ℝ}^{m\times n}$，$b\in {ℝ}^{m\times 1}$，定义实函数

$f_{+}\left(x\right):{ℝ}^n\to ℝ$

$f_{+}\left(x\right)=\frac{1}{2}{\Vert {\left(Ax-b\right)}_{+}\Vert }_2^2+\frac{1}{2}{\Vert x\Vert }_2^2$

$f_i\left(x,k\right):{ℝ}^n\times \mathbb{N}\to ℝ$

$f_i\left(x,k\right)=\frac{1}{2}{\Vert i\left(Ax-b,k\right)\Vert }_2^2+\frac{1}{2}{\Vert x\Vert }_2^2$

则有结论

1) $f_{+}\left(x\right)$ 和 $f_i\left(x,k\right)$ 都是强凸函数。

2) 优化函数 $\underset{x}{\min }{f}_{+}\left(x\right)$ 存在唯一解 $x^{*}$，优化函数 $\underset{x}{\min }{f}_i\left(x,k\right)$ 存在唯一解 ${\left(x^{*}\right)}^k$。

3) 对于任意的 $k\ge 1$，有

${\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }^2\le \frac{0.00131105\text{m}}{2k^2}$

4) $x^{*}$ 和 ${\left(x^{*}\right)}^k$ 满足

$\underset{k\to \infty }{\lim }{\left(x^{*}\right)}^k=x^{*}$

证明因为 ${\Vert \cdot \Vert }_2^2$ 具有强凸性，所以 $f_{+}\left(x\right)$ 和 $f_i\left(x,k\right)$ 也满足强凸性质。

由性质1可知，水平集 $L_v\left(f_i\left(x,k\right)\right)$ 和水平集 $L_v\left(f_{+}\left(x\right)\right)$ 满足

$L_v\left(f_i\left(x,k\right)\right)\subseteq L_v\left(f_{+}\left(x\right)\right)\subseteq \left\{x:{\Vert x\Vert }^2\le 2v\right\}\left(v\ge 0\right)$

因此它们都是 ${ℝ}^n$ 中的紧子集，从而有 $\underset{x}{\min }{f}_{+}\left(x\right)$ 和 $\underset{x}{\min }{f}_i\left(x,k\right)$ 都有解存在，而由 $\underset{x}{\min }{f}_{+}\left(x\right)$ 和 $\underset{x}{\min }{f}_i\left(x,k\right)$ 的强凸性可得解具有唯一性。

5) 我们不妨假设 $x^{*}$ 和 ${\left(x^{*}\right)}^k$ 分别是 $\underset{x}{\min }{f}_{+}\left(x\right)$ 和 $\underset{x}{\min }{f}_i\left(x,k\right)$ 的唯一解，则有

$f_{+}\left({\left(x^{*}\right)}^k\right)-f_{+}\left(x^{*}\right)\ge \nabla f_{+}\left(x^{*}\right)\left({\left(x^{*}\right)}^k-x^{*}\right)+\frac{1}{2}{\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }_2^2=\frac{1}{2}{\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }_2^2$

$f_i\left(x^{*},k\right)-f_i\left({\left(x^{*}\right)}^k,k\right)\ge \nabla f_i\left({\left(x^{*}\right)}^k,k\right)\left(x^{*}-{\left(x^{*}\right)}^k\right)+\frac{1}{2}{\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }_2^2=\frac{1}{2}{\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }_2^2$

两式相加得

$\begin{array}{c}{\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }_2^2\le \left(f_i\left(x^{*},k\right)-f_{+}\left(x^{*}\right)\right)-\left(f_i\left({\left(x^{*}\right)}^k,k\right)-f_{+}\left({\left(x^{*}\right)}^k\right)\right)\\ \le f_i\left(x^{*},k\right)-f_{+}\left(x^{*}\right)=\frac{1}{2}{\Vert i\left(A{x}^{*}-b,k\right)\Vert }_2^2-\frac{1}{2}{\Vert {\left(A{x}^{*}-b\right)}_{+}\Vert }_2^2\end{array}$

又根据性质2可知

${\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }^2\le \frac{0.00131105\text{m}}{2k^2}$

根据上式可知

$\underset{k\to \infty }{\lim }{\Vert {\left(x^{*}\right)}^k-x^{*}\Vert }^2\le \underset{k\to \infty }{\lim }\frac{0.00131105m}{2k^2}=0$

因此

$\underset{k\to \infty }{\lim }{\left(x^{*}\right)}^k=x^{*}$

4. 求解ISSVM模型的BFGS算法

由性质1可知光滑函数 $i\left(x,k\right)$ 是一阶光滑函数，我们可选用BFGS算法 [8] [9] 来对上述ISSVM模型进行优化。其具体算法步骤如下：

步骤1初始化

$H^0=I,\left(\left({\omega }^0\right),{\gamma }^0\right)=p^0\in {ℝ}^{n+1},\epsilon ={10}^{-8},{\alpha }^0=I,i=0,$

其中I为单位矩阵。

步骤2计算

$F^i=F\left(p^i,k\right),g^i=\nabla F\left(p^i,k\right),$

其中 $F\left(p^i,k\right)$ 指光滑函数。

步骤3如果

${\Vert g^i\Vert }_2^2\le \epsilon$ 或迭代次数达到最大，那么迭代停止，并取 $\left({\left({\omega }^i\right)}^{\text{T}},{\gamma }^i\right)=p^i$ 为ISSVM模型的最优参数解；

否则计算梯度方向 $d^i=-H^i{g}^i$。

步骤4沿着方向 $d^i$ 采用线搜索计算步长 ${\alpha }^i$，于是有

$s^i=-{\alpha }^i{H}^i{g}^i$

再计算出

$F^{i+1}=F\left(p^{i+1},k\right),g^{i+1}=\nabla F\left(p^{i+1},k\right),y^i=g^{i+1}-g^i$

步骤5计算

$H^{i+1}=\left(I-\frac{s^i{\left(y^i\right)}^{\text{T}}}{{\left(s^i\right)}^{\text{T}}{y}^i}\right)H^i\left(I-\frac{y^i{\left(s^i\right)}^{\text{T}}}{{\left(s^i\right)}^{\text{T}}{y}^i}\right)+\frac{s^i{\left(s^i\right)}^{\text{T}}}{{\left(s^i\right)}^{\text{T}}{y}^i}$

步骤6令 $i=i+1$，转步骤2。

5. 数值实验

对于SSVM，FSSVM，TSSVM，ESSVM和ISSVM5种模型采用BFGS算法求解无约束优化模型，算法采用的最大的迭代次数为1000，且取 $\epsilon ={10}^{-8}$。使用matlab2018a作为运行环境，实验结果记录CPU耗时、样本分类的训练正确率和测试正确率，根据这3个指标对这五种模型的分类性能进行比较和分析。

实验1 为了说明ISSVM具有解决大规模数据集的能力，采用的数据集是NDC数据集 [10]，数据集的样本数数量级至少在万以上。在采用BFGS算法对模型进行求解时，为求结果的准确性，对训练数据使用10折交叉验证方法 [11]。结果如表1所示。

表1. NDC数据集实验

由表1可知，新提出的反比例光滑支撑向量机ISSVM模型具有解决大规模数据问题的能力，并且在分类正确率和测试正确率上都有着较好的表现。在解决大规模数据问题时，ISSVM在CPU耗时和正确率上有着一定的优势。

数值实验数据来自用python编写的随机线性不可分数据集，统共样本数据有1200样本，测试样本有288个，每个样本有29个特征，采用了高斯核来将其映射到高维特征空间上得到分类结果如图2~5。

图2. 分类结果(1)

图3. 分类结果(2)

图4. 分类结果(3)

图5. 分类结果(4)

可以看出在小规模数据集下其分类的正确率都有着良好的性质。

除此之外，我们还补充了对于非线性数据集Checkerboard数据集的实验结果。当采用的核函数为高斯核函数 $K\left(x,y\right)=\exp \left(-\mu {\Vert x-y\Vert }^2\right)$ 时 [12] 结果如表2所示：

表2. Checkerboard数据集实验

由表2可知，ISSVM在处理非线性数据时，其耗时最短并且有着更高的分类正确率和测试正确率，说明了ISSVM处理非线性数据集的性能更好。

6. 结语

本文给出了一种新的光滑函数反比例函数，并基于光滑支撑向量机的过程应用此光滑反比例函数建立了ISSVM模型。与以往的光滑函数如多项式光滑函数、sigmoid积分函数、样条光滑函数等相比较而言，其逼近正号函数的精度提高了不同的数量级。实验数据表明，该反比例光滑支撑向量机模型对于大数据集具有较好的分类性能，相比于三阶样条光滑支撑向量机模型等而言，反比例光滑支撑向量机模型对线性数据分类所花费的时间更短且正确率也有所提升，整体比较来说对于非线性数据也能有较好的分类性能。反比例光滑函数相比其他光滑函数有着逼近程度更强的能力，反比例光滑支撑向量机相比于其他光滑支撑向量机模型的性能也更优越。

文章引用

吴 振,宇振盛. 反比例光滑支撑向量机
Inverse Proportional Smooth Support Vector Machine[J]. 运筹与模糊学, 2020, 10(04): 278-288. https://doi.org/10.12677/ORF.2020.104029

参考文献