周一至周五 | 9:00—22:00

离散神经网络求解支持向量机中的凸优化问题

作者:未知

  摘 要:针对正定核函数的支持向量机所导出的凸二次优化问题, 提出了一个离散型神经网络模型。利用KarushKuhnTucker (KKT)条件和投影理论构造投影方程, 使得投影方程的解与优化问题的解一一对应; 进一步基于投影方程建立离散神经网络; 理论结果表明, 网络的平衡点与优化问题的最优解相对应, 且网络具有全局指数收敛性。 相比于连续网络, 所提出的网络结构简单, 减少了计算的复杂度; 所得理论结果保证了网络能够有效求解支持向量机中的优化问题。 最后, 利用分类问题和标准数据集进行实验, 数值结果验证了本文所设计的网络在求解支持向量机优化问题的有效性。
  关键词:离散神经网络; 支持向量机; 凸优化; 全局指数收敛
  DOI:10.15938/j.jhust.2018.04.025
  中图分类号: O23
  文献标志码: A
  文章编号: 1007-2683(2018)04-0133-07
  Abstract:This paper proposes a discretetime neural network model to solve the convex optimization problem deduced by a positivekernelbased support vector machine (SVM). First, the projection equations are constructed through the KarushKuhnTucker (KKT) conditions and projection theory so that there exists a onetoone correspondence between the solution of projection equations and the optimal solution of optimization problem, and then a discretetime neural network was constructed by projection equations. Second, the obtained theoretical results indicate that the equilibrium point of the proposed neural network corresponds to the optimal solution of the optimization problem, and the proposed neural network is globally exponentially convergent. Compared with some continuous neural networks, the architecture of proposed neural network is simple, which decreases the computational complexity. Finally, some classification problems and benchmarking data sets are used in the experiment. The numeral results show the efficiency of the proposed neural network for solving the optimization problem in SVM.
  Keywords:discretetime neural network; support vector machine; convex optimization; global exponential convergent
  0 引 言
  支持向量机(SVM)最初是针对二类分类问题提出的。 SVM采用了结构风险最小化原理, 具有很好的泛化能力[1-2]。 近来, 将SVM与已有的算法相结合, 产生许多新的基于核函数算法, 如支持向量回归算法[1], 费希尔判别法[1],等不断被提出, 并且已经成功应用于函数逼近、模式识别、时间序列分析与预测等专业领域[3-4]。
  正定核的SVM是一类凸二次优化问题。 随着SVM在各个领域的广泛应用, 针对该凸优化问题提出了许多求解算法, 例如, SVMLight算法[5]、序列最小优化算法[6]、拉格朗日方法 [7-8]、以及神经网络优化算法[9-22]。 相比于其它算法, 神经网络优化算法主要优点之一是能很好地获得优化问题的实时解, 这使得其在求解优化问题中表现出了优良的性能并获得广泛的关注[23]。
  目前, 许多文献关注利用神经网络算法求解正定核SVM中的凸优化问题 [9-13]。 在文[9]中, 作者针对分类问题, 提出了一个二层的连续神经网络模型, 能够有效求解SVM中的凸优化问题, 同时研究了网络的收敛性。文[10]中提出了一个带有非连续激活函数的单层神经网络, 用于求解SVM中的凸优化问题。 此外,文[11]基于KKT条件提出了一个原始-对偶连续神经网络模型用以求SVM中的凸优化问题。文[12]针对二次型的SVM问题以及其对应的超平面问题, 构造连续神经网络模型进行求解, 该网络的优点是可以通过模拟电路的形式来实现。 文[13]针对支持向量的分类与回归算法中的凸优化问题, 提出了一个连续单层神经网络模型。 该网络可有效地获得优化问题的最优解, 并且指数收敛到SVM的最优解, 网络的收敛速度可通过调节参数达到足够快。 此外, 针对较一般的优化问题所构造的神经网络算法可以用于求解正定核SVM中的凸优化问题[14-21]。 例如, 文[14]针对带有线性等式以及约束控制的伪凸优化问题, 提出了一个单层神经网路模型。 若网络的参�底愎淮螅� 网络就能有效地收敛到优化问题的最优解; 该网络在动态组合优化方面也获得了成功的应用。 文[15]提出了一个微分包含形式的神经网络, 用以求解非光滑优化问题, 该网络的神经元个数等于优化问题的决策变量的个数, 并且网络能够收敛至优化问题的最优解。 文[18]设计了一个投影神经网络用以求解带有线性约束的退化二次规划问题。 文[19]提出了一个梯度神经网络模型用以求解由非正定核构造SVM中的非凸二次优化问题, 并通过引入ojasiewicz不等式, 证明了网络轨迹指数收敛或有限时间收敛到临界点集。 文[20]针对带有限制约束的二次规划问题, 提出了一个离散神经网络。 一些改进规则的提出使得该网络能有效地获得优化问题的最小解, 而且其中一些规则可保证网络具有指数收敛性。文[21]通过证明该网络的全局指数稳定性, 扩展了文[20]的结论。   本文针对正定核SVM中的优化问题, 利用KKT条件与投影理论, 设计了一个离散神经网络模型, 证明了网络平衡点的存在性、网络的平衡点与SVM中的优化问题的解的一致性、 以及网络的全局指数收敛性。 同连续形式的神经网络算法[9-19]相比, 离散形式的网络可以在计算机或者一些较低的设备条件下也能很容易实现, 并且有效地减少了计算的复杂度。 此外, 正定核SVM中的凸优化的约束条件包含等式约束和不等式约束, 文[20-21]中的网络只能用于求解带有不等式约束的凸二次优化问题, 并不适用于求解等式约束的情形。
  1 预备知识
  这一节首先给出符号说明, 然后简要介绍SVM中的优化问题。 关于SVM的相关详细信息可阅读文[1-4]。
  4 实 验
  这一节, 针对分类问题采用离散网络(7)对优化问题(2)进行求解。 选取步长宽度δ=0.0025,当相邻两点的迭代误差小于5×10-10时停止迭代。
  实验1:首先, 利用本文所提的离散网络与文[13]中网络利用iris数据集进行对比分析。 iris数据集通过四项指标(setal length, setal width, setal length, setal width)将150个样本点分为3类(viginica, versilcolor, setosa), 每一类别包含50个样本点。 为了便于分析, 以下选取第二类与第三类的数据集进行训练分析, 随机选取其中的80个样本点进行训练, 剩下的20个样本点进行检验。
  选取多项式核函数
  k(x,y)=(xTy+1)p
  令C=0.25, 分别选取p=2以及p=4。 随机选取初始点, 图2与图4分别为p=2与p=4时的样本点与支持向量点的分布情况。 其中’+’号代表第二类数据集的训练样本点分布情况, ‘◇’代表对应的支持向量。 ‘*’代表第三类数据集的训练样本点分布情况, ‘o’代表对应的支持向量。 图3与图5分别给出了对应的预测样本点的分布情况, 其中‘□’代表预测错误的样本。
  从图2与图3可见, 此时的支持向量个数为18, 对应的预测样本点的预测误差为0。
  从图4与图5可以见, p=4时共有13个支持向量点, 少于p=2时的情形。 但是, 此时有3个预测样本点出现错误。
  表1给出了与文[13]中的网络的比较结果, 可以看出本文所提的离散网络需要较少的支持向量个数。 此外, 当p=2时的预测误差为0, 预测精度达到了100%。
  实验2: (线性可分情形)考察文[12]所给的线性可分数据,如表2所示。
  实验3: (线性不可分情形)考察文[12]中的线性不可分数据, 如表3所示。
  选取线性核函数以及罚参数C=10。 在初始点[-1, 1, -1, 1, -1, 1, -1, 1, -1, 1]T的条件下, 利用离散网络(7)对表3中数据集进行训练分析, 网络有效地收敛至最优解[-3.24, 10, 0, 0, 8.16, -10, -4.92, 10, -10, 1.80]T
  图7与图8分别给出了文[12]与本文所得的正负两类点的分布图, 以及对应超平面。 其中’*’代表正类样本点、’+’代表负类样本点、’o’代表支持向量点。 实线为所得线性超平面。
  从图7可见, 文[12]中的训练结果共有8个支持向量点, 并有3个正类样本点预测错误, 而且其中还有一个负类样本点刚好在超平面上。 从图8可见, 本文所得结果只有两个样本点预测错误(一个正类样本点, 一个负类样本点), 对应的支持向量点个数为7。 对比图7与图8, 可以发现本文所得结果明显优于文[12]中的结果。
  实验四: 针对分类问题, 利用离散网络(7)对一些标准数据集进行实验仿真进行分析。 以下相关概念将会在实验中用到:
  数据集: Sonar与German数据集, 可在University of California at Irvine机器学习网站上查找相应数据集。 表4给出了数据集的具�w描述。
  实验中用以下高斯核(RBF)
  k(x,y)=exp(‖x-y‖22σ2)。
  参数: 选取C=100, σ=1。
  从Sonar与German的实验可以看出, 本文所提的离散网络在数据量较大的实验中也能取得较好的结果。
  5 结 论
  针对支持向量机的求解问题, 本文提出了一个离散神经网络模型。 一方面, 利用KKT条件与投影理论构造神经网络(7), 保证网络的平衡点与正定核SVM中的优化问题的最优解的一致性; 另一方面, 网络(7)还具有全局指数收敛性, 保证了网络能够快速收敛到优化问题(2)的最优解。 此外, 同连续形式的网络相比, 离散网络对设备的要求不是很高, 这也使得该网络可在更多的设备上应用。 实验结果验证了理论结果的有效性。 尽管离散神经网络(7)是针对严格凸二次优化问题(2)提出的, 但本文的方法可以用于求解一般的带有等式及不等式约束的凸规划问题, 并且有望推广到非严格凸的二次规划以及非凸二次退化问题。
  参 考 文 献:
  [1] SCHLKOPF B, SMOLA A. Learning with kernels[M]. Cambridge : MIT, 2002.
  [2] CORTES C,VAPNIK V N. Support Vector Networks[J]. Machine Learning, 1995, 20:273�C297.
  [3] 孙永倩, 王培东. 基于支持向量机的并行CT图像分割方法[J]. 哈尔滨理工大学学报, 2013, 18(3):42-46.   [4] 尤波, 周丽娜, 黄玲, 应用于假手的肌电信号分类方法研究[J]. 哈尔滨理工大学学报, 2011, 16(3):1-7.
  [5] JOACHIMS T. Making largescale SVM Learning Practical[C]// Cambridge, Massachusetts, Advances in Kernel Methodssupport Vector Learning, MITPress: Platt J, 1999:169-184.
  [6] PLATT J. Fast Training of Support Vector Machines Using Sequential Minimal Optimization. Cambridge[C]// Cambridge, Massachusetts, Advances in Kernel Methodssupport Vector Learning, MITPress: Platt J, 1999: 185�C208.
  [7] MANGASARIAN O, MUSICANT D. Lagrangian Support Vector Machines[J]. Journal of Machine Learning Research, 2001(1):161-177.
  [8] YANG X, SHU L. An Extended Lagrange Support Vector Machine for Classification[J]. Progress in Natural Science, 2004,14(6):519-523.
  [9] ANGUTITA D, BONI A. Improved Neural Network for SVM Learning[J]. IEEE Trans. on Neural Networks, 2002(13):1243-1244.
  [10]YANG Y, HE Q. A Compact Neural Network for Training Support Vector Machines[J]. Neurocomputing, 2012(86):193-198.
  [11]ANGUITA D, BONI A. Neural Network Learning for Analog VLSI Implementations of Support Vector Machines: A survey[J]. Neurocomputing, 2003(55):265-283.
  [12]NAZEMI A, DEHGHAN M. A Neural Network Method for Solving Support Vector Classification Problems[J]. Neurocomputing, 2015(152):369-376.
  [13]XIA Y, WANG J. A Onelayer Recurrent Neural Network for Support Vector Machine Learning[J]. IEEE Trans. on Systems Cybern. B, 2004, 34(2):1261-1267.
  [14]LIU Q, GUO Z, WANG J. A Onelayer Recurrent Neural Network for Constrained Pseudoconvex Optimization and its Application for Dynamic Portfolio Optimization[J]. Neural Networks. 2012(26):99-109.
  [15]LIU Q, WANG J. A Onelayer Recurrent Neural Network for Constrained Nonsmooth Optimization[J]. IEEE Trans. on Systems Cybern. B, 2011, 41(5):1323-1332.
  [16]LIU Q, WANG J. A Onelayer Recurrent Neural Network with a Discontinuous Hardlimiting Activation Function for Quadratic Programming[J]. IEEE Trans. on Neural Networks, 2008, 19(4):558-568.
  [17]XU H. Projection Neural Networks for Solving Constrained Convex and Degenerate Quadratic Problems[C]// IEEE International Conference on Intelligent Computing & Intelligent Systems, 2010:91-95.
  [18]XUE X, BIAN W. A Project Neural Network for Solving Degenerate Convex Quadratic Program[J]. Neurocomputing, 2007(70):2449-2459.
  [19]LIU Feng, XUE X. Subgradientbased Neural Network for Nonconvex Optimization Problems in Support Vector Machines with Indefinite Kernels[J]. Journal of Industrial & Management Optimization. 2016, 12(1):285-301.
  [20]PREZLLZARBE M. Convergence Analysis of a Discretetime Recurrent Neural Networks to Perform Quadratic Real Optimization with Bound Constraints[J]. IEEE Trans. on Neural Networks, 1998, 9(6):1344-1351.
  [21]TAN K, TANG H, YI Z. Global Exponential Stability of Discretetime Neural Networks for Constrained Quadratic Optimization[J]. Neurocomputing, 2004(56):399-406.
  [22]TANK D, HOPFIELD J. Simple Neural Optimization Networks: An A/D Converter, Signal Decision Circuit, and a Linear Programming Circuit[J]. IEEE Trans. on Circuit & Systems, 1986(33):533-541.
  [23]BAZARAA M, SHERALI H, SHETTY C. Nonlinear Programming: Theory and Algorithms[M]. New Jersey: John Wiley & Sons, Inc., 1993.
  (�辑:温泽宇)


常见问题解答