求解大规模非凸优化问题的多阶段MM方法*

袁友宏 周 凯

（陆军炮兵防空兵学院 合肥 230031）

1 引言

支持向量机（Supporting Vector Machine，SVM）是由Vapnik等人于1992年提出的一种标准的机器学习算法［1］。从最初的“边缘最大化”发展到如今的“正则化项+损失函数［2］”，学者们对SVM的研究从未停止。SVM应用广泛，然而在处理大规模数据时，会因为过多的支持向量，使得计算代价明显增大，特别是在预测阶段［3］。利用截断Hinge损失函数，可以得到稀疏的支持向量，降低计算代价，但却令凸优化问题转变为非凸优化问题。2013年，Mairal将解决非凸优化问题的CCCP［4］和DCA（Difference Convex Algorithm，DCA）［5］等常用方法，归结为一个统一的MM框架［6］，在非凸优化领域中受到广泛应用。

从理论上分析，基于0-1损失的分类误差是最好的，然而是一个NP难问题［7～8］。因此，有很多近似0-1损失的其它损失函数，例如Hinge损失，最小二乘损失和指数损失等。研究表明，SVM优化问题中使用的Hinge损失（或称为L1损失）是其成功的关键［9］。2007年，Singer使用随机投影次梯度对大规模SVM进行求解（称为Pegasos），取得了轰动一时的实际效果［10］。尽管SVM获得了巨大成功，但对于大规模问题，有如下不足：

1）对于训练数据中的噪声样本，SVM十分敏感。

2）支持向量的数量会随着样本数线性增加，从而导致在大规模问题中，支持向量集合过大，预测阶段所需时间大大增加。

3）过多的支持向量导致SVM鲁棒性较差。

适当的修改Hinge损失可能显著提升SVM的表现。著名学者Shen提出了截断Hinge损失函数（称为截断L1-SVM问题）方法［11］，其中通过截断损失函数去逼近0-1损失函数，能够有效减少离群点对分类超平面的干扰，并且减少了支持向量的数目。……