求解非凸截断L1-SVM的多阶段非精确线搜割平面方法

截断Hinge损失能够获得更为稀疏的支持向量,因此在鲁棒性上有显著的优点,但却由此导致了难以求解的非凸问题.MM(Majorization⁃Minimization)是一种求解非凸问题的一般框架,多阶段MM策略已经在稀疏性上取得了很好的效果,但是计算复杂度较高.另一方面,非精确线搜割平面方法可以高效求解线性支持向量机问题.针对截断L1⁃SVM(L1 Support Vector Machine)这一非凸非光滑问题,提出一种基于非精确线性搜索的多阶段割平面方法,避免每个阶段都进行批处理求解,克服了计算复杂度高的缺点,具有每个阶段求解速度快的优点.该算法适用于大规模问题的求解,也从理论上保证了其收敛性.最后,与其他多阶段算法进行了实验对比,验证了该方法的有效性.

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

机器学习的主要目的是让计算机系统具有类似于人的学习能力,而数值优化方法对提高其效率,增强其效果有着举足轻重的作用。在L1-SVM优化问题中,可以利用截断Hinge损失剔除过多的支持向量,提高模型的鲁棒性。但却导致了棘手的非凸优化问题。MM(Majorization-Minimization,MM)是一种求解非凸问题的有效框架,主要思想是通过寻找一系列恰当的凸上界,将非凸目标函数转化为一系列凸的子问题进行求解。常用于求解非凸问题的凸凹转化算法(Con⁃cave-Convex Procedure,CCCP)同属这一框架。论文分析了求解截断L1-SVM问题的CCCP算法具有稀疏支持向量的原因,并在此基础上,利用多阶段策略的优点,提出一种多阶段MM方法,得到了更好的稀疏性。最后在大规模数据集上,进行了实验对比,验证了所提算法的有效性。