《海量数据挖掘-王永利》大间隔分布学习机.docVIP

大间隔分布学习机 张腾， 周志华 （南京大学软件新技术国家重点实验室） 摘要：支持向量机(SVM)已经成为最流行的机器学习算法之一。支持向量机的主要思想就是最小间隔最大化，即最大化最小样本与分类面之间的距离。最近的理论结果表明最大化最小间隔并不是保证更好的泛化性能得必要条件，而间隔分布被证明更为重要。本文我们提出最大间隔分布学习机(Large margin Distribution Machine, LDM). 我们通过一阶和二阶统计量，即间隔均值和间隔方差，来描述间隔分布。大间隔分布学习机(LDM)是一种通用学习方法，并可以用于所有支持向量机可以使用的地方。本文从理论上及实验上证明了大间隔分布学习机的优越性。 关键字：间隔分布，最小间隔，分类 1 引言 支持向量机(SVM)[5],[26] 已经成为最为成功的学习算法之一。支持向量机的基本思想是通过求解一个二次规划问题(QP)找到一个最大间隔分类面。虽然支持向量机已经提出很久，仍然还有许多工作致力于改进支持向量机的性能[16],[6],[25],[14],[8]。 支持向量机可以被看作最大化最小间隔，即最小样本与分类面之间的距离。间隔理论[26]给支持向量机提供了很好的理论支持。值得指出的是间隔理论不仅对支持向量机有很好的解释，而且也为其他的学习方法泛化性提供了理论解释，比如集成学习[31]里的AdaBoost算法[10]。Schapire等人[21]首次用间隔理论解释了AdaBoost对于可以防止过拟合问题。随后Breiman[4]指出最小间隔的重要性并提出了一种类似boosting的算法，Arc-gv。这种算法可以最大化最小间隔但是泛化性不好。接着Reyzin等人发现虽然Arc-gv尝试使最小间隔尽量大，但是仍然遇到了不好的间隔分布。他们推测间隔分布对于泛化性更为重要，而不是最小间隔。这个推测经过理论研究[27],[11]最近已经被Gao和Zhou证明[11]。他们指出不能仅仅考虑单个点之间的间隔，还需要考虑间隔均值和间隔方差[11]。这些理论研究仅仅局限于boosting类的算法，间隔分布在支持向量机里的作用还没被研究。 本文，我们提出大间隔学习机(LDM)，尝试通过优化间隔分布来获得更好的泛化性能。受文献[11]的理论结果的启发，我们利用间隔分布一阶和二阶统计量来刻画间隔分布，并尝试同时最大化间隔均值和最小化间隔方差。对于优化问题的求解，我们提出了利用对坐标下降法(dual coordinate descent)求解核大间隔分布学习机；利用平均随机梯度下降法(averaged stochastic gradient descent, ASGD)求解大规模线性核大间隔分布学习机。在20个正常规模的数据集和12个大规模数据集上的实验表明大间隔分布学习机优于传统的支持向量机和其他必威体育精装版的学习算法。这也说明了对于支持向量机类的学习方法间隔分布比最小间隔更为重要。 本文剩余部分安排如下：第2节介绍了一些知识背景；第3节介绍了大间隔分布学习机；第4节是我们的实验结果；第5节讨论一些相关工作；第6节对本文作出了总结。 2 背景知识 我们用表示样本空间，表示标签集合，是一个未知分布。一个大小为关于分布独立同分布(i.i.d)的训练集可以表示为：。我们的目标是学习一个可以预测将类不可见样本的的标签。 对于支持向量机，被认为是一个线性模型，即，其中是线性预测器，是通过核函数()在特征空间的映射。根据[5],[26]，样本的间隔距离可以写为： (1) 文献[7]显示对于线性可分情况训练样本可以被硬间隔支持向量机0错误分割，即： 硬间隔可以看作最大大化。 对于非线性可分情况，即训练样本不能被0错误分隔，支持向量机采用软间隔方式，即： (2) 其中度量样本的损失，是平衡两项的参数。这里存在一个常数使得(2)等价于下面形式 这里是松弛最小间隔，是平衡参数。值得注意的是实际上刻画的是最大的p各最小间隔[11]。因此，支持向量机(包括硬间隔和软间隔)仅考虑了单点间隔而没有考虑整体间隔分布。 3 大间隔分布学习机 本节，我们首先形式化间隔分布，然后提出优化算法求解并给出理论保证。 3.1 形式化 用于刻画间隔分布的最直接的统计量是一阶和二阶统计量，即间隔均值和间隔方差。用表示第i列为的矩阵，即。是一列向量，是阶以为对角元的对角矩阵。根据在(1)中的定义，间隔均值可以表示为： (3) 间隔方差可以表示为：