一種新的基于乘性規(guī)則的支持向量機

廣東工業(yè)大學 周 燁

一種新的基于乘性規(guī)則的支持向量機

廣東工業(yè)大學 周 燁

由于傳統(tǒng)的二次規(guī)劃運算速度慢，已推出適用于二次規(guī)劃問題的乘性規(guī)則。在本文中，推導出新的求解支持向量機中和約束二次規(guī)劃的乘性規(guī)則，同樣使得二次規(guī)劃的目標函數(shù)單調下降到全局的最小點，同時又顯著提高其優(yōu)化速度。該方法是構造出新的輔助函數(shù)，推導出乘性規(guī)則，是一種直接優(yōu)化的方法，所有變量都可以并行迭代，在本文中會給出完整的證明和給出仿真實驗驗證其有效性。

二次規(guī)劃；和約束；乘性規(guī)則

1 引言

2 非負二次規(guī)劃

首先，我們研究的基本問題是非負約束的二次規(guī)劃。考慮二次規(guī)劃目標函數(shù)的最小化問題：

乘性規(guī)則：

非負二次規(guī)+劃的乘性更新法則是用矩陣A的正數(shù)和負數(shù)的部分來表示的，特別是，讓A—和A表示為非負矩陣，它們包含的元素可以表示為：

這個規(guī)則能夠簡單的實現(xiàn)出來，v的各個分量可以并行參與運算。而且都是非負的，式（3）右端經(jīng)迭代運算后仍為非負的，因此迭代運算始終滿足非負約束。

3 新的乘性規(guī)則

在文獻【1】中，我們都可以查閱到式（3）推導方法，新的乘性規(guī)則也是延續(xù)這種推導思路，使得目標函數(shù)收斂到全局的最小值。

引理1：

有時候他又從一個極端跑到另一個極端，對女兒寵得沒邊兒沒沿兒。豆豆想養(yǎng)狗，一看見別的小朋友養(yǎng)狗就哭著來找我申請。我告訴她：“豆豆，媽媽特別怕狗，所以咱們家不能養(yǎng)狗。”

式（14）相較與式（3）同樣能夠保證右端迭代運算后為非負的，所以迭代運算也是始終滿足非負的約束。

證明的思路是依據(jù)構造一個輔助函數(shù)為目標函數(shù)提高提供上界，該證明方法已在論文中【1】被證明。

單調收斂：

4 和約束

由于式（15）僅適用于非負二次規(guī)劃問題，不能直接求解下面目標函數(shù)，因為它不僅有非負約束還有和約束問題，因此我們將式（14）中的乘性規(guī)則作進一步的推廣。

由于規(guī)劃：

對應的Lagrange函數(shù)為：

則新的更新法則為：

具體證明見論文[2-3]

5 仿真實驗

（1）通過仿真實驗我們來驗證本文算法的優(yōu)越性，我們兩種二分類的數(shù)據(jù)進行實驗，一類是自動生成的數(shù)據(jù)，一類是真實的數(shù)據(jù)集。三個數(shù)據(jù)集是機器學習常用的數(shù)據(jù)集。

6 結束語

SVMs在機器學習中是被運用的最廣泛的結構之一。在本文中，我們已經(jīng)推導出一種簡單形式的乘性更新，解決支持向量機中求解具有和約束的二次規(guī)劃。這種規(guī)則能夠直接并行運行并且保證收斂到全局最小值。在文章中我們已經(jīng)給出了理論證明，仿真實驗說明本文算法能夠極大地提高優(yōu)化速度。

[1]F.Sha,L.K.Saul,and D.D.Lee.Multiplicative updates for nonnegative quadratic programming in support vector machines.In S.Becker,S.Thrun, and K. Obermayer, editors, Advances in Neural and Information Processing Systems,volume 15,Cambridge,MA.

[2]F.Sha,L.K.Saul,and D.D.Lee.Multiplicative updates for large margin classifiers.In Proceedings of the Sixteenth Annual Conference on Computational Learning Theory(COLT-03)(pp.188-202).Berlin:Springer.2003.

[3]F.Sha,L.K.Saul,and D.D.Lee.Multiplicative updates for nonnegative quadratic programming[J].Neural Computation,19(8):2004-2031,2014.