学界 | 代替支持向量机，南大周志华组提出多类最优边界分配机mcODM

选自arXiv

机器之心编译

参与：李泽南、路雪

南京大学机器学习与数据挖掘研究所张腾与周志华的新研究提出了在多类分类问题上的全新解决方法——mcODM，并在诸多数据集的对比中证明了它的表现优于其他四种多类 SVM 方式。在即将于 8 月开始的 ICML2017 大会上，张腾与周志华会对该研究进行现场讲解（8 月 7 日，11:24-11:42 @ C 4.6 & C 4.7）。

支持向量机（SVM）和提升方法（Boosting）一直是近十多年来的主流学习方式。前者源自于统计学习理论（Cortes & Vapnik，1995），其核心为搜索大间隔分离器的理念，即在 RKHS（再生核 Hilbert 空间）中最大化从实例到分类边界的最小距离。值得注意的是，用边距理论（margin theory）解释的后者也有着很长的历史，因为经验认为它可以免于过拟合（Reyzin & Schapire，2006；Wang et al., 2011；Zhou，2012）。

最近，用于提升方法的边距理论（margin theory）再次进入了人们的视线中，并且展示了边界分布，而非单一分布对于泛化表现具有更大的重要性。这些研究表明支持向量机可能还有很大的提升空间。受此认可的启发（Zhang＆Zhou，2014； 2016）提出了一种二元分类方法，通过一阶和二阶统计特征来优化边界分布，实现了令人满意的实验结果。随后，周志华等人将这一思想扩展到了一种能够利用未标记数据并处理非平衡错误分类成本的方法上。

尽管研究已经表明，对于二元分类，通过最大化边距平均值和最小化边距差异来优化边界分布可以获得优越的性能，但在多类分类中，优化问题仍然是开放的。此外，多类别分类的边界比二元分类要复杂得多，这使得最终的优化成为难以进行的不可微分非凸过程。

在本论文中，张腾与周志华提出了 mcODM（多类最优边界分配机），有效地解决了这个问题。为了优化，mcODM 被置于一系列凸二次规划（QP）中，研究人员也扩展了 Block Coordinate Descent（BCD）算法（Tseng，2001），以解决每个 QP 的双重问题。BCD 每次迭代的子问题也是一个 QP，通过特殊结构，研究人员导出了一种排序算法，它比通用 QP 算法更为高效。研究人员进一步提出了基于 Rademacher 复杂度泛化误差约束，并进一步提出了多类分类的泛化误差与边界分布关系的分析。在多达 22 各数据集的广泛验证中，mcODM 的表现超越了其他三种多类 SVM。

算法 1 展示了核 mcODM 的细节。

图 1. 五种方法在类别数量增长的数据集上的泛化性能。

表 2. 22 个数据集上的准确率（meanstd.）对比结果。对比过程使用了线性核函数。每个数据集上的最优准确率加粗显示。黑点标记表示 mcODM 的性能极大地优于/差于与之对比的方法（成对 t 检验结果在 95% 的水平）。倒数第三行和倒数第二行是平均排序和 top1 次数。最后一行是 mcODM 的胜率/平率/负率（win/tie/loss）。ovoSVM 和 ecocSVM 未在 48 小时内在某些数据集上返回结果。

表 2 总结了 22 个数据集上的具体结果。如表 2 所示，我们的方法的整体性能优于其他与之对比的方法。具体来说，在 22 个数据集上，mcODM 的性能在 17/19/18/17 个数据集上明显优于 mcSVM/ovaSVM/ovoSVM/ecocSVM。此外，与其他四种未考虑边界分布的方法相比，mcODM 的胜率/平率/负率往往优于它们或者至少持平。

研究人员在除 aloi 以外的所有数据集上把新方法的单一迭代时间成本（single iteration time cost）与 mcSVM、ovaSVM、ovoSVM 进行了对比。所有实验均在 MATLAB 2012b 内使用一台配有共计 82.60 GHz CPU 和 32GB 主内存的机器上完成。图 3 显示每个数据集上的平均 CPU 时间（以秒计）。用于 ovaSVM、ovoSVM 和 mcSVM 的二元 SVM（binary SVM）都由 LIBLINEAR（Fan et al., 2008）包执行。图中可见小数据集上所有方法的效率相近，但类别大于 10 的数据集（如 sector 和 rcv1、mcSVM 和 mcODM）可快速学会所有记分函数（scoring function），学习速度明显快于 ovaSVM 和 ovoSVM，后者由于二进制分解（binary-decomposition）导致效率低下。注意：LIBLINEAR 可快速实施二元 SVM 和 mcSVM，这说明新的方法的计算能力更强大。

图 3. mcSVM、ovaSVM、ovoSVM 和 mcODM 在除 aloi 以外的所有数据集上的单一迭代时间成本。

论文：Multi-Class Optimal Margin Distribution Machine

论文链接：https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icml17mcODM.pdf

最近的研究表明，最大化支持向量机的最小边距不一定能带来更好的泛化性能，而优化边界分配至关重要。虽然研究已经表明，对于二进制分类，通过一阶和二阶统计来表征边界分配可以实现优异的性能，但多类分类的问题仍然是开放的。同时由于多类分类的边界复杂度，通过均值和方差优化其分布也是非常困难的。在本研究中，我们提出了 mcODM（多类最优边界分配机），可以有效地解决这个问题。我们还对新方法进行了理论分析，验证了它在多类分类边界分配问题上的意义。实证研究进一步表明，在所有实验数据集中，mcODM 总是优于另外四种多类 SVM。

本文为机器之心编译，转载请联系本公众号获得授权。