一种新的基于乘性规则的支持向量机

广东工业大学 周 烨

一种新的基于乘性规则的支持向量机

广东工业大学 周 烨

由于传统的二次规划运算速度慢，已推出适用于二次规划问题的乘性规则。在本文中，推导出新的求解支持向量机中和约束二次规划的乘性规则，同样使得二次规划的目标函数单调下降到全局的最小点，同时又显著提高其优化速度。该方法是构造出新的辅助函数，推导出乘性规则，是一种直接优化的方法，所有变量都可以并行迭代，在本文中会给出完整的证明和给出仿真实验验证其有效性。

二次规划；和约束；乘性规则

1 引言

2 非负二次规划

首先，我们研究的基本问题是非负约束的二次规划。考虑二次规划目标函数的最小化问题：

乘性规则：

非负二次规+划的乘性更新法则是用矩阵A的正数和负数的部分来表示的，特别是，让A—和A表示为非负矩阵，它们包含的元素可以表示为：

这个规则能够简单的实现出来，v的各个分量可以并行参与运算。而且都是非负的，式（3）右端经迭代运算后仍为非负的，因此迭代运算始终满足非负约束。

3 新的乘性规则

在文献【1】中，我们都可以查阅到式（3）推导方法，新的乘性规则也是延续这种推导思路，使得目标函数收敛到全局的最小值。

引理1：

有时候他又从一个极端跑到另一个极端，对女儿宠得没边儿没沿儿。豆豆想养狗，一看见别的小朋友养狗就哭着来找我申请。我告诉她：“豆豆，妈妈特别怕狗，所以咱们家不能养狗。”

式（14）相较与式（3）同样能够保证右端迭代运算后为非负的，所以迭代运算也是始终满足非负的约束。

证明的思路是依据构造一个辅助函数为目标函数提高提供上界，该证明方法已在论文中【1】被证明。

单调收敛：

4 和约束

由于式（15）仅适用于非负二次规划问题，不能直接求解下面目标函数，因为它不仅有非负约束还有和约束问题，因此我们将式（14）中的乘性规则作进一步的推广。

由于规划：

对应的Lagrange函数为：

则新的更新法则为：

具体证明见论文[2-3]

5 仿真实验

（1）通过仿真实验我们来验证本文算法的优越性，我们两种二分类的数据进行实验，一类是自动生成的数据，一类是真实的数据集。三个数据集是机器学习常用的数据集。

6 结束语

SVMs在机器学习中是被运用的最广泛的结构之一。在本文中，我们已经推导出一种简单形式的乘性更新，解决支持向量机中求解具有和约束的二次规划。这种规则能够直接并行运行并且保证收敛到全局最小值。在文章中我们已经给出了理论证明，仿真实验说明本文算法能够极大地提高优化速度。

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