论文部分内容阅读
支持向量机是一种建立在统计学习理论基础上的机器学习方法,是结构风险最小化思想的具体实现。它在模型的复杂度和推广能力之间寻求最佳折衷,很好地解决了小样本、非线性、过学习、局部极值、维数灾难等问题。它的基本思想就是求取能够使得两类间隔最大的超平面,具有全局最优、适应性强、推广能力强等优点,从而被广泛应用于诸多领域。
SVM的基本思想是求解两类样本间具有最大间隔的超平面,其训练可以归结为求解一个二次规划问题,这个问题的规模是同训练样本的个数成平方关系的,当训练样本较多时,传统的优化方法就会因为内存占用太多不能直接应用。分解方法是目前为止求解SVM问题的一个重要方法,它将大规模二次规划问题变为迭代求解一系列较小规模的子二次规划问题,大大降低了对内存的需求,并取得了很好的效果。
在机器学习领域中,在线学习指的是分类器能够根据依次新来的错分样本不断地作出调整,从而改善分类器的推广能力,使得它能够更准确地预测后续样本。在一些实时系统的检测和分类任务中,如辅助驾驶系统中的行人/建筑物检测、邮件分拣系统中的邮编识别等,既快又准确并且具有在线学习能力的分类器是非常重要的。
本论文研究了具有代表性的支持向量机的分解算法和在线学习算法,并且针对算法中存在的若干关键问题进行了深入的探索和改进,主要工作包括:
1、支持向量机分解算法的收敛性证明。支持向量机通过求解一个二次规划问题获得,而分解算法是一种求解大规模二次规划问题的重要方法。本论文证明了在一种条件温和的工作集选取方法下,分解算法能够在有限步迭代内到达满足松弛Karush-Kuhn-Tucker(KKT)条件的近似最优解。更进一步,我们证明了分解算法SVMlight的工作集选取方法满足文章中工作集的选取条件,从而得到其在没有Hessian矩阵严格正定的条件下依然能够有限步迭代收敛的性质。
2、基于最小包含球调整的在线核心向量机算法。虽然核心向量机算法和支持向量机的分解算法都能够解决大数据量的求解问题,但它们依然不能应用于在线学习问题,因为当新来一个样本被错分时,需要将已有所有训练样本和这个错分样本一起重新训练去调整当前的分类器。本文基于自适应最小包含球的在线调整方法,提出了一种在线核心向量机算法,成功解决了分类器的在线学习问题。其主要包含两步:1)在对已有样本进行训练的过程中移除大量的冗余样本,这些样本的删除不会影响已有样本的分类结果;2)基于训练过程中保留的少量样本和新来的错分样本实现分类器的在线更新。人工的和现实世界的数据实验都证明了我们方法的准确性和有效性。
3、基于凸包顶点样本选取的在线支持向量机算法。从几何上看,SVM的求解等价于求解正负类样本分别所形成凸包之间的最近点对。因此,本文基于选取每一类所形成的凸包上的顶点样本,提出了一种在线支持向量机算法。从理论上讲,我们证明了算法中所选取的样本就是凸包顶点样本,这保证了它们能够最大程度的保持凸包的有效信息,从而使得分类器在实现快速在线更新的同时又不会影响分类精度。在标准数据集上的实验验证了我们方法的正确性和有效证。