Minimizing the Maximal Loss: How and Why-ICML(2)

(ICML16) Minimizing the Maximal Loss: How and Why...



Minimizing the Maximal Loss: How and Why

Author: Shai Shalev-Shwartz and Yonatan Wexler

前言：先说一声迟到的圣诞快乐！好啦，话不言多，立刻进入正题。这是一篇属于机器学习中计算学习理论范畴的论文，挑中这篇文章的原因是这篇文章讨论了机器学习当中的一个基础问题：如何有效最小化经验风险？我们知道，AdaBoost是一种采用了委员会机制的方法，通过组合弱学习器，最小化经验风险。而这篇文章提出了一种作用于采样训练数据上的“boosting”机制：基于在线学习方法，从训练集中每次采样有利于当前优化的样本数据，用以模型学习效率的提升。接下来，进入正题！

1  知识点概要

a  PAC（Probably Approximately Correct-可能近似正确）学习

在PAC学习理论中涉及到几个基础概念：X是输入空间，D是输入空间上的一个分布，h∈H是输入x输出标签y的一种假设（hypothesis）。PAC学习的目标是：假设训练集是来自于D的独立同分布地采样，目标是找到一种假设h，使得LD(h)< ε，其中LD(h)=Px~D[h(x)≠h*(x)]，h*表示最优假设，ε表示误差范围。由于零误差的实现比较困难（ε=0），因此我们只能从概率上保证（以1−δ的概率）模型误差小于一个较小的值ε。

b  VC维（Vapnik-Chervonenkis Dimension）

提到VC维就需要明确一个概念“shatter”：当假设空间H作用于N个输入样本时，产生的二分（dichotomies）数量等于这N个点总的组合数2N时，就称这N个输入被H给shatter掉了。一个假设空间H的VC维是这个H最多能够shatter掉的点的数量，记为VC(H)。如果不管多少个点，H都能shatter它们，则VC(H)=无穷大。

VC提供了解释PAC学习可行的两个核心条件：1）是否经验误差和期望误差相近（训练和测试中的期望损失相近）？ 2）经验误差是否足够小？当VC维较小时，条件（1）容易满足，但条件（2）不容易满足。当VC维较大时，条件（2）容易满足，但条件（1）不容易满足。这就是所谓的欠拟合和过拟合问题。有一篇写得相当不错的博文深入的介绍了VC维了，大家可以参考[1]。

2  动机及主要贡献典型的有监督的机器学习应用场景为：给定训练集S=((x1, y1), …, (xm,ym))∈(X, Y)m，学习函数hw:X→Y，其中w∈W是函数h参数向量。定义损失函数l: W×X×Y→[0, 1]用来评价参数化的函数h在训练样本(x, y)上的表现。有两种一般的适用学习规则用来指导有监督的机器学习：1）最小化平均损失
；2）最小化最大损失
。最小化Lmax可以更有效地利用训练集中较为稀少的训练样本（离群点-outlier），另外，由于Lmax≥Lavg，这使得在相同约束条件LD(h)< ε下，最小化Lmax能够更好地拟合训练集。但在实际应用中，最小化Lavg仍然比最小化Lmax更为流行，这是因为：1）在假设训练样本独立同分布的情况下，最小化Lavg支持在线学习方法，例如：SGD（Stochastic Gradient Descent）方法；2）最小化Lmax可以更好地拟合训练集，但相比最小化Lavg存在更大的过拟合风险；3）由于最小化Lmax对离群点敏感，使得最小化Lmax很不稳定。

那么是否可以有这样一种方法，能够综合最小化Lmax以及Lavg的优势，模型在线学习的训练策略，训练过程中保证模型在有效降低经验风险的情况下，防止模型过拟合并且获得稳定的解？为此文章提出了一种在训练过程中自适应地调整训练集样本分布的方法，在线学习策略中所采样的训练集样本，其样本分布会根据当前训练的损失进行自适应地调整。这种调整策略既能保证模型能够有效捕捉训练集中的离群点信息，又能保证训练模型的稳定性，并防止因为过度拟合离群点所带来的过拟合现象。

3   Focused Online Learning（FOL）令Sm={p∈[0,1]m: ||p||1=1}为训练集中m个样本分布所定义的单纯形。在FOL中，损失函数的形式为：

其中
。在总共T轮的训练中，在每一迭代轮t中，选取训练样本it ~ pt用于当前的训练，并根据当前迭代轮的损失调整训练集中的样本分布。具体FOL算法为：另外，作者还给出了用于快速采样训练样本以及更新样本分布的方法：4 FOL和AdaBoost

AdaBoost的策略是通过组合弱学习器的方式，最小化经验风险。假设有m个弱分类器，AdaBoost组合这m个弱分类器：其中Gm为当前组合的弱分类器，fm-1为m-1步的组合结果，βm为当前弱分类器所对应的系数。在Adaboost中，系数βm的根据第m-1步组合后的模型误差计算所得。FOL对训练样本的分布进行更新的策略近似于AdaBoost的更新策略，虽然FOL和AdaBoost的作用方式不同，但最终都能有效的最小化经验风险。

5  实验结果在实验中作者采用CNN模型进行人脸识别，模型分别采用了SGD和FOL这两种优化策略。在训练集上，FOL的收敛速度明显优于SGD。这是因为当分类误差达到一个很小的值（

    关注 KingsGarden