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

2017-09-14 06:48广东工业大学
电子世界 2017年17期
关键词:乘性约束运算

广东工业大学 周 烨

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

广东工业大学 周 烨

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

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

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.

猜你喜欢
乘性约束运算
重视运算与推理,解决数列求和题
Hamy对称函数的Schur乘性凸性
“碳中和”约束下的路径选择
有趣的运算
约束离散KP方程族的完全Virasoro对称
乘性噪声干扰下基于交互多模型的目标跟踪*
具有乘性噪声和随机量测时滞的目标跟踪算法
“整式的乘法与因式分解”知识归纳
适当放手能让孩子更好地自我约束
一类带乘性噪声2-D奇异系统的滤波算法