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

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

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

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

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

1 引言

2 非負(fù)二次規(guī)劃

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

乘性規(guī)則：

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

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

3 新的乘性規(guī)則

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

引理1：

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

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

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

單調(diào)收斂：

4 和約束

由于式（15）僅適用于非負(fù)二次規(guī)劃問題，不能直接求解下面目標(biāo)函數(shù)，因?yàn)樗粌H有非負(fù)約束還有和約束問題，因此我們將式（14）中的乘性規(guī)則作進(jìn)一步的推廣。

由于規(guī)劃：

對(duì)應(yīng)的Lagrange函數(shù)為：

則新的更新法則為：

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

5 仿真實(shí)驗(yàn)

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

6 結(jié)束語

SVMs在機(jī)器學(xué)習(xí)中是被運(yùn)用的最廣泛的結(jié)構(gòu)之一。在本文中，我們已經(jīng)推導(dǎo)出一種簡單形式的乘性更新，解決支持向量機(jī)中求解具有和約束的二次規(guī)劃。這種規(guī)則能夠直接并行運(yùn)行并且保證收斂到全局最小值。在文章中我們已經(jīng)給出了理論證明，仿真實(shí)驗(yàn)說明本文算法能夠極大地提高優(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.