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

劉鳳秋 張紅旭

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

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

DOI：10.15938/j.jhust.2018.04.025

中圖分類(lèi)號(hào)： O23

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 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 引 言

支持向量機(jī)（SVM）最初是針對(duì)二類(lèi)分類(lèi)問(wèn)題提出的。 SVM采用了結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理， 具有很好的泛化能力[1-2]。 近來(lái)， 將SVM與已有的算法相結(jié)合， 產(chǎn)生許多新的基于核函數(shù)算法， 如支持向量回歸算法[1]， 費(fèi)希爾判別法[1]，等不斷被提出， 并且已經(jīng)成功應(yīng)用于函數(shù)逼近、模式識(shí)別、時(shí)間序列分析與預(yù)測(cè)等專(zhuān)業(yè)領(lǐng)域[3-4]。

正定核的SVM是一類(lèi)凸二次優(yōu)化問(wèn)題。 隨著SVM在各個(gè)領(lǐng)域的廣泛應(yīng)用， 針對(duì)該凸優(yōu)化問(wèn)題提出了許多求解算法， 例如， 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)點(diǎn)之一是能很好地獲得優(yōu)化問(wèn)題的實(shí)時(shí)解， 這使得其在求解優(yōu)化問(wèn)題中表現(xiàn)出了優(yōu)良的性能并獲得廣泛的關(guān)注[23]。

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

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

1 預(yù)備知識(shí)

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

4 實(shí) 驗(yàn)

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

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

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

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

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

從圖2與圖3可見(jiàn)， 此時(shí)的支持向量個(gè)數(shù)為18， 對(duì)應(yīng)的預(yù)測(cè)樣本點(diǎn)的預(yù)測(cè)誤差為0。

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

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

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

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

選取線(xiàn)性核函數(shù)以及罰參數(shù)C=10。 在初始點(diǎn)[-1， 1， -1， 1， -1， 1， -1， 1， -1， 1]T的條件下， 利用離散網(wǎng)絡(luò)（7）對(duì)表3中數(shù)據(jù)集進(jìn)行訓(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ù)兩類(lèi)點(diǎn)的分布圖， 以及對(duì)應(yīng)超平面。 其中*代表正類(lèi)樣本點(diǎn)、+代表負(fù)類(lèi)樣本點(diǎn)、o代表支持向量點(diǎn)。 實(shí)線(xiàn)為所得線(xiàn)性超平面。

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

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

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

實(shí)驗(yàn)中用以下高斯核（RBF）

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

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

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

5 結(jié) 論

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

參 考 文 獻(xiàn)：

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

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

（編輯：溫澤宇）