離散神經(jīng)網(wǎng)絡(luò)求解支持向量機中的凸優(yōu)化問題

劉鳳秋 張紅旭

摘 要：針對正定核函數(shù)的支持向量機所導(dǎo)出的凸二次優(yōu)化問題， 提出了一個離散型神經(jīng)網(wǎng)絡(luò)模型。利用KarushKuhnTucker （KKT）條件和投影理論構(gòu)造投影方程， 使得投影方程的解與優(yōu)化問題的解一一對應(yīng)； 進一步基于投影方程建立離散神經(jīng)網(wǎng)絡(luò)； 理論結(jié)果表明， 網(wǎng)絡(luò)的平衡點與優(yōu)化問題的最優(yōu)解相對應(yīng)， 且網(wǎng)絡(luò)具有全局指數(shù)收斂性。 相比于連續(xù)網(wǎng)絡(luò)， 所提出的網(wǎng)絡(luò)結(jié)構(gòu)簡單， 減少了計算的復(fù)雜度； 所得理論結(jié)果保證了網(wǎng)絡(luò)能夠有效求解支持向量機中的優(yōu)化問題。 最后， 利用分類問題和標(biāo)準(zhǔn)數(shù)據(jù)集進行實驗， 數(shù)值結(jié)果驗證了本文所設(shè)計的網(wǎng)絡(luò)在求解支持向量機優(yōu)化問題的有效性。

關(guān)鍵詞：離散神經(jīng)網(wǎng)絡(luò)； 支持向量機； 凸優(yōu)化； 全局指數(shù)收斂

DOI：10.15938/j.jhust.2018.04.025

中圖分類號： O23

文獻標(biāo)志碼： 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采用了結(jié)構(gòu)風(fēng)險最小化原理， 具有很好的泛化能力[1-2]。 近來， 將SVM與已有的算法相結(jié)合， 產(chǎn)生許多新的基于核函數(shù)算法， 如支持向量回歸算法[1]， 費希爾判別法[1]，等不斷被提出， 并且已經(jīng)成功應(yīng)用于函數(shù)逼近、模式識別、時間序列分析與預(yù)測等專業(yè)領(lǐng)域[3-4]。

正定核的SVM是一類凸二次優(yōu)化問題。 隨著SVM在各個領(lǐng)域的廣泛應(yīng)用， 針對該凸優(yōu)化問題提出了許多求解算法， 例如， SVMLight算法[5]、序列最小優(yōu)化算法[6]、拉格朗日方法 [7-8]、以及神經(jīng)網(wǎng)絡(luò)優(yōu)化算法[9-22]。 相比于其它算法， 神經(jīng)網(wǎng)絡(luò)優(yōu)化算法主要優(yōu)點之一是能很好地獲得優(yōu)化問題的實時解， 這使得其在求解優(yōu)化問題中表現(xiàn)出了優(yōu)良的性能并獲得廣泛的關(guān)注[23]。

目前， 許多文獻關(guān)注利用神經(jīng)網(wǎng)絡(luò)算法求解正定核SVM中的凸優(yōu)化問題 [9-13]。 在文[9]中， 作者針對分類問題， 提出了一個二層的連續(xù)神經(jīng)網(wǎng)絡(luò)模型， 能夠有效求解SVM中的凸優(yōu)化問題， 同時研究了網(wǎng)絡(luò)的收斂性。文[10]中提出了一個帶有非連續(xù)激活函數(shù)的單層神經(jīng)網(wǎng)絡(luò)， 用于求解SVM中的凸優(yōu)化問題。 此外，文[11]基于KKT條件提出了一個原始-對偶連續(xù)神經(jīng)網(wǎng)絡(luò)模型用以求SVM中的凸優(yōu)化問題。文[12]針對二次型的SVM問題以及其對應(yīng)的超平面問題， 構(gòu)造連續(xù)神經(jīng)網(wǎng)絡(luò)模型進行求解， 該網(wǎng)絡(luò)的優(yōu)點是可以通過模擬電路的形式來實現(xiàn)。 文[13]針對支持向量的分類與回歸算法中的凸優(yōu)化問題， 提出了一個連續(xù)單層神經(jīng)網(wǎng)絡(luò)模型。 該網(wǎng)絡(luò)可有效地獲得優(yōu)化問題的最優(yōu)解， 并且指數(shù)收斂到SVM的最優(yōu)解， 網(wǎng)絡(luò)的收斂速度可通過調(diào)節(jié)參數(shù)達到足夠快。 此外， 針對較一般的優(yōu)化問題所構(gòu)造的神經(jīng)網(wǎng)絡(luò)算法可以用于求解正定核SVM中的凸優(yōu)化問題[14-21]。 例如， 文[14]針對帶有線性等式以及約束控制的偽凸優(yōu)化問題， 提出了一個單層神經(jīng)網(wǎng)路模型。 若網(wǎng)絡(luò)的參數(shù)足夠大， 網(wǎng)絡(luò)就能有效地收斂到優(yōu)化問題的最優(yōu)解； 該網(wǎng)絡(luò)在動態(tài)組合優(yōu)化方面也獲得了成功的應(yīng)用。 文[15]提出了一個微分包含形式的神經(jīng)網(wǎng)絡(luò)， 用以求解非光滑優(yōu)化問題， 該網(wǎng)絡(luò)的神經(jīng)元個數(shù)等于優(yōu)化問題的決策變量的個數(shù)， 并且網(wǎng)絡(luò)能夠收斂至優(yōu)化問題的最優(yōu)解。 文[18]設(shè)計了一個投影神經(jīng)網(wǎng)絡(luò)用以求解帶有線性約束的退化二次規(guī)劃問題。 文[19]提出了一個梯度神經(jīng)網(wǎng)絡(luò)模型用以求解由非正定核構(gòu)造SVM中的非凸二次優(yōu)化問題， 并通過引入ojasiewicz不等式， 證明了網(wǎng)絡(luò)軌跡指數(shù)收斂或有限時間收斂到臨界點集。 文[20]針對帶有限制約束的二次規(guī)劃問題， 提出了一個離散神經(jīng)網(wǎng)絡(luò)。 一些改進規(guī)則的提出使得該網(wǎng)絡(luò)能有效地獲得優(yōu)化問題的最小解， 而且其中一些規(guī)則可保證網(wǎng)絡(luò)具有指數(shù)收斂性。文[21]通過證明該網(wǎng)絡(luò)的全局指數(shù)穩(wěn)定性， 擴展了文[20]的結(jié)論。

本文針對正定核SVM中的優(yōu)化問題， 利用KKT條件與投影理論， 設(shè)計了一個離散神經(jīng)網(wǎng)絡(luò)模型， 證明了網(wǎng)絡(luò)平衡點的存在性、網(wǎng)絡(luò)的平衡點與SVM中的優(yōu)化問題的解的一致性、 以及網(wǎng)絡(luò)的全局指數(shù)收斂性。 同連續(xù)形式的神經(jīng)網(wǎng)絡(luò)算法[9-19]相比， 離散形式的網(wǎng)絡(luò)可以在計算機或者一些較低的設(shè)備條件下也能很容易實現(xiàn)， 并且有效地減少了計算的復(fù)雜度。 此外， 正定核SVM中的凸優(yōu)化的約束條件包含等式約束和不等式約束， 文[20-21]中的網(wǎng)絡(luò)只能用于求解帶有不等式約束的凸二次優(yōu)化問題， 并不適用于求解等式約束的情形。

1 預(yù)備知識

這一節(jié)首先給出符號說明， 然后簡要介紹SVM中的優(yōu)化問題。 關(guān)于SVM的相關(guān)詳細信息可閱讀文[1-4]。

4 實 驗

這一節(jié)， 針對分類問題采用離散網(wǎng)絡(luò)（7）對優(yōu)化問題（2）進行求解。 選取步長寬度δ=0.0025，當(dāng)相鄰兩點的迭代誤差小于5×10-10時停止迭代。

實驗1：首先， 利用本文所提的離散網(wǎng)絡(luò)與文[13]中網(wǎng)絡(luò)利用iris數(shù)據(jù)集進行對比分析。 iris數(shù)據(jù)集通過四項指標(biāo)（setal length， setal width， setal length， setal width）將150個樣本點分為3類（viginica， versilcolor， setosa）， 每一類別包含50個樣本點。 為了便于分析， 以下選取第二類與第三類的數(shù)據(jù)集進行訓(xùn)練分析， 隨機選取其中的80個樣本點進行訓(xùn)練， 剩下的20個樣本點進行檢驗。

選取多項式核函數(shù)

k（x，y）=（xTy+1）p

令C=0.25， 分別選取p=2以及p=4。 隨機選取初始點， 圖2與圖4分別為p=2與p=4時的樣本點與支持向量點的分布情況。 其中+號代表第二類數(shù)據(jù)集的訓(xùn)練樣本點分布情況， ‘◇代表對應(yīng)的支持向量。 ‘*代表第三類數(shù)據(jù)集的訓(xùn)練樣本點分布情況， ‘o代表對應(yīng)的支持向量。 圖3與圖5分別給出了對應(yīng)的預(yù)測樣本點的分布情況， 其中‘□代表預(yù)測錯誤的樣本。

從圖2與圖3可見， 此時的支持向量個數(shù)為18， 對應(yīng)的預(yù)測樣本點的預(yù)測誤差為0。

從圖4與圖5可以見， p=4時共有13個支持向量點， 少于p=2時的情形。 但是， 此時有3個預(yù)測樣本點出現(xiàn)錯誤。

表1給出了與文[13]中的網(wǎng)絡(luò)的比較結(jié)果， 可以看出本文所提的離散網(wǎng)絡(luò)需要較少的支持向量個數(shù)。 此外， 當(dāng)p=2時的預(yù)測誤差為0， 預(yù)測精度達到了100%。

實驗2： （線性可分情形）考察文[12]所給的線性可分?jǐn)?shù)據(jù)，如表2所示。

實驗3： （線性不可分情形）考察文[12]中的線性不可分?jǐn)?shù)據(jù)， 如表3所示。

選取線性核函數(shù)以及罰參數(shù)C=10。 在初始點[-1， 1， -1， 1， -1， 1， -1， 1， -1， 1]T的條件下， 利用離散網(wǎng)絡(luò)（7）對表3中數(shù)據(jù)集進行訓(xùn)練分析， 網(wǎng)絡(luò)有效地收斂至最優(yōu)解[-3.24， 10， 0， 0， 8.16， -10， -4.92， 10， -10， 1.80]T

圖7與圖8分別給出了文[12]與本文所得的正負(fù)兩類點的分布圖， 以及對應(yīng)超平面。 其中*代表正類樣本點、+代表負(fù)類樣本點、o代表支持向量點。 實線為所得線性超平面。

從圖7可見， 文[12]中的訓(xùn)練結(jié)果共有8個支持向量點， 并有3個正類樣本點預(yù)測錯誤， 而且其中還有一個負(fù)類樣本點剛好在超平面上。 從圖8可見， 本文所得結(jié)果只有兩個樣本點預(yù)測錯誤（一個正類樣本點， 一個負(fù)類樣本點）， 對應(yīng)的支持向量點個數(shù)為7。 對比圖7與圖8， 可以發(fā)現(xiàn)本文所得結(jié)果明顯優(yōu)于文[12]中的結(jié)果。

實驗四： 針對分類問題， 利用離散網(wǎng)絡(luò)（7）對一些標(biāo)準(zhǔn)數(shù)據(jù)集進行實驗仿真進行分析。 以下相關(guān)概念將會在實驗中用到：

數(shù)據(jù)集： Sonar與German數(shù)據(jù)集， 可在University of California at Irvine機器學(xué)習(xí)網(wǎng)站上查找相應(yīng)數(shù)據(jù)集。 表4給出了數(shù)據(jù)集的具體描述。

實驗中用以下高斯核（RBF）

k（x，y）=exp（‖x-y‖22σ2）。

參數(shù)： 選取C=100， σ=1。

從Sonar與German的實驗可以看出， 本文所提的離散網(wǎng)絡(luò)在數(shù)據(jù)量較大的實驗中也能取得較好的結(jié)果。

5 結(jié) 論

針對支持向量機的求解問題， 本文提出了一個離散神經(jīng)網(wǎng)絡(luò)模型。 一方面， 利用KKT條件與投影理論構(gòu)造神經(jīng)網(wǎng)絡(luò)（7）， 保證網(wǎng)絡(luò)的平衡點與正定核SVM中的優(yōu)化問題的最優(yōu)解的一致性； 另一方面， 網(wǎng)絡(luò)（7）還具有全局指數(shù)收斂性， 保證了網(wǎng)絡(luò)能夠快速收斂到優(yōu)化問題（2）的最優(yōu)解。 此外， 同連續(xù)形式的網(wǎng)絡(luò)相比， 離散網(wǎng)絡(luò)對設(shè)備的要求不是很高， 這也使得該網(wǎng)絡(luò)可在更多的設(shè)備上應(yīng)用。 實驗結(jié)果驗證了理論結(jié)果的有效性。 盡管離散神經(jīng)網(wǎng)絡(luò)（7）是針對嚴(yán)格凸二次優(yōu)化問題（2）提出的， 但本文的方法可以用于求解一般的帶有等式及不等式約束的凸規(guī)劃問題， 并且有望推廣到非嚴(yán)格凸的二次規(guī)劃以及非凸二次退化問題。

參 考 文 獻：

[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–297.

[3] 孫永倩， 王培東. 基于支持向量機的并行CT圖像分割方法[J]. 哈爾濱理工大學(xué)學(xué)報， 2013， 18（3）：42-46.

[4] 尤波， 周麗娜， 黃玲， 應(yīng)用于假手的肌電信號分類方法研究[J]. 哈爾濱理工大學(xué)學(xué)報， 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–208.

[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.

（編輯：溫澤宇）