论文部分内容阅读
一直以来,支持向量机在机器学习领域中都扮演着很重要的角色。其重要求解方法坐标下降法在每次迭代中仅选择一个变量进行更新而令其他变量保持不变,因而往往能够获得很快的收敛速度。在大数据时代下,基于坐标下降的传统用于求解SVMs的序列最小化SMO算法并没有很好的扩展性,并且目前最新的异步贪婪坐标下降算法虽然有很好的训练速度,但仅局限于处理二类分类问题。有序回归问题是监督学习中最重要的研究任务之一,支持向量有序回归机SVOR是其重要的解决方法。由于SVOR问题的复杂性,目前对于SVOR的大规模训练方法的研究仍是空白。为了解决这些问题,本文基于坐标下降方法,对支持向量机的快速训练方法重点进行了以下研究:(1)对于传统的SVMs求解算法SMO,本文提出了 一种通过随机次梯度加速的SMO算法。目前加速SMO主要通过活动集缩减和缓存技术,但引入活动集缩减技术的SMO算法大量的计算时间消耗在前半部分。为了提高求解效率,本文首先利用随机次梯度下降SSGD在前期能够以极快的速度获得可行解的优势,提出了一种广义的通过SSGD加速SMO的算法框架用于求解二类分类、回归以及有序回归等形式的SVMs。随后对SSGD能够加速SMO的原因进行了深入的理论分析和实验验证。最后在多个优化问题和数据集上的实验结果证实了 SSGD-SMO有效地加速了 SMO的收敛速度。(2)通过活动集缩减技术,本文提出了一种加速的异步贪婪坐标下降算法。由于目前最新的基于异步贪婪坐标下降算法AsyGCD的扩展性不够,且仅局限在用于处理二类分类问题。为了解决以上问题,文中首先利用活动集缩减技术提出了一种SVMs加速的异步贪婪坐标下降算法AsyAGCD。随后将AsyAGCD算法拓展到处理回归问题∈-SVR中。此外,文中还比较了 AsyAGCD和AsyGCD的时间复杂度。最后在多个数据集下的实验结果证实了 AsyAGCD比现有的SVMs求解方法更快。(3)对于有序回归问题,本文提出了一种新的有序回归问题表示形式,并给出了相应的异步贪婪坐标下降算法。由于和标准的SVMs相比,SVOR具有更多的等式或不等式约束,使其问题形式更为复杂。为了解决以上问题,文中首先提出了一种不含等式和不等式约束的新的SVOR问题形式。随后对于新的SVOR,提出了相应的异步贪婪坐标下降算法AsySVOR。最后在多个数据集下的实验结果证实了与现有SVOR求解方法相比,尤其在大数据集下,AsySVOR在保证精度的同时具有更快的收敛速度。