【论文分享】中科院自动化所多媒体计算与图形学团队NIPS 2017论文提出平均Top-K损失函数，专注于解决复杂样本- 专知

【论文分享】中科院自动化所多媒体计算与图形学团队NIPS 2017论文提出平均Top-K损失函数，专注于解决复杂样本

点击上方“专知”关注获取专业AI知识!

【导读】损失函数的设计一直是机器学习和模式识别中的核心问题。目前中国科学院自动化研究所和美国纽约州立大学奥尔巴尼分校合作提出了一种新的聚合损失函数，即平均损失函数。损失在优化的过程中专注于处理比较难的样本，可以更好地拟合数据的不同分布，特别是不平衡数据和多分布数据。该成果已被NIPS2017接受，以下是相关成果介绍。

论文：Learning with Average Top-k Loss

▌1. 引言：

很多机器学习任务目标于学习一个映射函数以根据输入的数据或特征来预测目标输出。比如根据人的身高年龄来预测人的体重。我们需学习f以尽可能准确的根据x预测y，给定一组训练数据

记f在样本(x, y)上损失为(如二分类中0-1损失）令其中，我们的学习目标可以定义为

我们称L为聚聚聚合合合损损损失失失（aggregate loss），即把每一个样本的单个损失聚合成一个整体的损失，为作用到f上的正则项。聚合损失L对模型f的学习起着很重要的作用，典型的我们有以下几种聚合损失：平均损失(Average loss)、最大损失(Maximum loss)和第k大损失（S. Shalev-Shwartz et al., 2016）等，其定义见表 1，其中定义为中第k大的元素。

Figure 1: 在二分类任务中，不同的聚合损失在仿真数据上的性能比较。Bayes最优分类边界在图中以阴影显示，其中单个样本的损失采用logistic损失。第2列和第4列的图显示了每种情况下当k变化时，ATk损失对应错分比例。

图1结合仿真数据显示了最小化平均损失和最小化最大损失分别得到的分类结果。可以看出，当数据分布不均衡或是某类数据存在典型分布和非典型分布的时候，最小化平均损失会忽略小类分布的数据而得到次优的结果；而最大损失对样本噪音和外点（outliers）非常的敏感，即使数据中仅存在一个外点也可能导致模型学到非常糟糕的分类边界；相比于最大损失损失，第k大损失对噪音更加鲁棒，但其在k > 1时非凸非连续，优化非常困难。

由于真实数据集非常复杂，可能存在多分布性、不平衡性以及噪音等等，为了更好的拟合数据的不同分布，我们提出了平均Top-K损失作为一种新的聚合损失。

▌2. 学习平均Top-K损失

2.1 平均Top-K损失定义

平均Top-K（Average Top-K Loss, ATk）损失定义为样本集z上的前k个最大的损失的平均值，即

可以看出损失具有以下特性：

损失包含了平均损失（k = n）和最大损失（k = 1）。
损失是第k大损失的凸上界。

损失是一种非常通用的聚合损失，其可以和很多现有的定义在单个样本上的损失结合起来，如logistic损失，hinge损失，平方损失（L2），绝对值损失（L1）等等。通过引入自由度 k，损失可以更好的拟合数据的不同分布。从图1中可以看出，当数据存在多分布或类别分布不均衡的时候，最小化平均损失会牺牲掉小类样本以达到在整体样本集上的损失最小；当数据存在噪音或外点的时候，最大损失对噪音非常的敏感，学习到的分类边界跟Bayes最优边界相差很大；当采取损失最为聚合损失的时候（如k=10），可以更好的保护小类样本，并且其相对于最大损失而言对噪音更加鲁棒。从第二列和第四列的错分比例的趋势图也可以看出，最优的k即不是k = 1（对应最大损失）也不是k = n（对应平均损失），而是在[1, n]之间存在一个比较合理的k的取值区间。

2.2 损失的分析和优化

受限于排序算子（前k个最大的损失的平均），损失的原始形式(2)很难进行优化和理论分析，我们首先推导损失的一个等价形式，具体的我们有如下引理：

Lemma 1 (Lemma 1, W. Ogryczak et al. 2003).是一个关于的凸函数。并且当：

其中

根据引理1，损失(2)等价于

可以看出，k聚合损失等价于优化的平均损失，其中λ的取值跟具体的k值有关。从等价损失出发，我们可以更好的理解损失，特别是在分类问题中。

Figure 2: ATk损失在单个损失上的释义，阴影部分对应正确分类的样本。

以二分类问题为例，由于0-1损失非凸非连续，很难优化。实际应用中我们通常会采用0-1损失的一些替代损失，如logistic失和hinge损失等，这些凸损失函数是0-1损失的上界并且具有很好的可优化性质，但是它们通常也会对正确分类的样本带来非0损失，见图2。以logistic损失为例，当（代表样本被正确分类），（其损失非0），因此当平均logistic损失被最小化时，模型的优化过程可能被大量简单样本所主导，导致一些小类样本可能被牺牲掉以达到在整个训练集上的平均损失最小。相比之下，聚合损失诱导的损失相当于对原始损失整体往下移动 λ 个单位（λ ≥ 0）并且做一个截尾操作，从图2可以看出，对于正确分类并距离分类边界面足够远（yf(x)足够大）的样本，其损失为0，这样可以使得模型在学习过程可以专注于处理比较难的样本（如距离分类边界比较近的样本或被错分的样本）。

以图1中的不平衡数据为例，由于正类样本很多，当采取平均聚合损失时学习到的分类器会将所有负类样本都错分成正类以达到整体损失最小。而当我们采取聚合损失时（如k = 10），由于正类中的大部分样本都可以被很容易的分类，其引入的损失（）为0，使得模型优化过程中可以更多的专注复杂样本（小类样本），所学习到的分类器可以更好的保护小类样本。

模型优化: 利用公式(3)，不失一般性，我们假定f是一个由参数w刻画的的学习模型，最小化损失的目标函数可以描述为

其中Ω(w)为作用到模型参数w上的正则项。容易看出当

和Ω(w)是关于w的凸函数的时候，公式(4)中的目标函数是关于(w, λ)的联合凸函数。因此我们可以采用随机（次）梯度法来方便的优化模型(4)，特别的，当时，在算法的第t次迭代中首选随机选取样本，然后更新模型参数如下

其中)关于w的次梯度，是步长因子。

2.3 实验分析

我们在分类问题和回归问题中对ATk损失进行实验分析，在实验中我们采用线性预测函数，即其中(w, b)为模型参数，模型正则项采用。我们利用随机次梯度下降法优化损失，并随机选取50%，25%，25%的样本分别作为训练集，验证集和测试集。在训练的过程中，我们假定没有任何关于k的先验信息，并通过验证集来选取最合适的k和C。

Figure 3: 分类错误率w.r.t. k

图3给出了在二分类实验中，在四个数据集上分类错误率随k的变化的变化曲线，其中单个样本的损失分别为logistic损失和hinge损失。可以看出在这些数据集上当k = 1时，数据中潜在的噪音对分类结果有很大的负面影响，分类结果比较差；随着k的逐渐增加，噪音和外点数据对分类器的影响逐渐被削弱，分类性能逐渐变好；当k持续增加时（如k = n），由于大量容易被分类的样本被逐渐增加进来，这些简单样本上的非0损失会对分类器带来负面的影响，分类性能反而下降。

更多的理论分析和数值实验结果，请参见原文。

▌3.总结

在该工作中，我们分析了平均损失和最大损失等聚合损失的优缺点，并提出了平均Top-K损失（损失）作为一种新的聚合损失，其包含了平均损失和最大损失并能够更好的拟合不同的数据分布，特别是在多分布数据和不平衡数据中。损失降低正确分类样本带来的损失，使得模型学习的过程中可以更好的专注于解决复杂样本，并由此提供了一种保护小类数据的机制。损失仍然是原始损失`的凸函数，具有很好的可优化性质。我们还分析了损失的理论性质，包括classification calibration等。

论文链接：

http://papers.nips.cc/paper/6653-learning-with-average-top-k-loss

▌特别提示-Learning with Average Top-k Loss论文下载：

请关注专知公众号（扫一扫最下面专知二维码，或者点击上方蓝色专知），