学界 | 代替支持向量机,南大周志华组提出多类最优边界分配机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。

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

原文发布于微信公众号 - 机器之心(almosthuman2014)

原文发表时间:2017-07-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

10 大深度学习架构:计算机视觉优秀从业者必备(附代码实现)

选自Analytics Vidhya 作者:FAIZAN SHAIKH 机器之心编译 参与:路雪、李亚洲、黄小天 近日,Faizan Shaikh 在 Ana...

2768
来自专栏CDA数据分析师

使用 TensorFlow 和 Python 进行深度学习(附视频中字)

TensorFlow是谷歌研发的开源框架。本讲座介绍了如何使用TensorFlow创建深度学习应用程序,以及与其他Python机器学习库进行比较。 我叫Ian ...

2609
来自专栏机器之心

深度 | 最后一届ImageNet挑战赛落幕,「末代」皇冠多被国人包揽

选自LSVRC 2017 机器之心编译 参与:机器之心编辑部 近日,ImageNet 最后一届挑战赛成绩已经公布,多个国内院校和企业在各个比赛项目上取得了非常不...

3695
来自专栏腾讯技术工程官方号的专栏

NeurIPS 2018 | 腾讯AI Lab详解3大热点:模型压缩、机器学习及最优化算法

? 导读:AI领域顶会NeurIPS正在加拿大蒙特利尔举办。本文针对实验室关注的几个研究热点,模型压缩、自动机器学习、机器学习与最优化算法,选取23篇会议上入...

4292
来自专栏专知

【干货】基于属性学习和额外知识库的图像描述生成和视觉问答

【导读】这篇论文提出一种将高层次的概念与CNN-RNN成功结合的方法,并且实验表明这种方法在图像语义生成和视觉问答方面都取得了显着的进步。通过设计一个视觉问答模...

3709
来自专栏ATYUN订阅号

谷歌研究:通过自动增强来提高深度学习性能

计算机视觉深度学习的成功可部分归功于大量标记训练数据,随着质量提高,多样性和训练数据量,模型的性能通常会提高。但是,收集足够的高质量数据来训练模型以实现良好性能...

1164
来自专栏AI科技大本营的专栏

一文清晰讲解机器学习中梯度下降算法(包括其变式算法)

本篇文章向大家介绍梯度下降(Gradient Descent)这一特殊的优化技术,我们在机器学习中会频繁用到。 前言 无论是要解决现实生活中的难题,还是要创建一...

2852
来自专栏数据派THU

10大深度学习架构:计算机视觉优秀从业者必备(附代码实现)

? 来源:机器之心 作者:FAIZAN SHAIKH 本文长度为3000字,建议阅读5分钟 本文包括深度学习领域的最新进展、keras 库中的代码实现以及论文...

3409
来自专栏人工智能头条

从业务角度理解深度学习及其应用

1762
来自专栏AI科技大本营的专栏

AI 技术讲座精选:机器学习中梯度下降算法(包括其变式算法)简介

前 言 无论是要解决现实生活中的难题,还是要创建一款新的软件产品,我们最终的目标都是使其达到最优状态。作为一名计算机科学专业的学生,我经常需要优化各种代码,以便...

3484

扫码关注云+社区

领取腾讯云代金券