【AIDL专栏】王立威：机器学习理论的回顾与展望(附PPT下载)

AIDL简介

“人工智能前沿讲习班”(AIDL)由中国人工智能学会主办，旨在短时间内集中学习某一领域的基础理论、最新进展和落地方向，并促进产、学、研相关从业人员的相互交流。对于硕士、博士、青年教师、企事业单位相关从业者，预期转行AI领域的爱好者均具有重要的意义。2018年AIDL活动正在筹备，敬请关注公众号获取最新消息。

导读

随着第一期《人工智能前沿讲习班》完美落幕，中国人工智能学会举办的第二期《人工智能前沿讲习班》如约而至，第二期专题是“机器学习前沿”。北京大学信息科学技术学院王立威教授作了题为《机器学习理论：回顾与展望》的报告。本文根据王立威老师的报告内容整理发布，对相关领域的研究工作具有长期价值。

讲师简介

王立威，北京大学信息科学技术学院教授。主要研究领域为机器学习，在COLT、NIPS、JMLR、PAMI等权威会议和期刊发表论文60余篇。2010年入选AI’s 10 to Watch，他是首位获得该奖项的亚洲学者。2012年获得首届国家自然科学基金优秀青年基金及“新世纪优秀人才支持计划”。任NIPS等权威会议的Area Chair和多家学术期刊编委。

前言

人脑是由神经元组成的，人脑和深度学习中的CNN的核心区别有三点，第一是结构，第二是速度，第三是运行机制。结构上，人脑大约有10的11次方个神经元，10的14-15次方的连接，深度学习所用的最大型网络与人脑相比，两者差距非常明显。速度上，人脑视觉的感知和认知是一个非常迅速的过程，神经元传递到相邻的神经元只需几十毫秒。而深度学习远远达不到这个速度。运行机制上，深度学习的Network认为层与层之间的信息传递完全同步，即必须上一层的信息全部同时传递到下一层的神经元才能够进行处理。而人脑没有同步控制信号，神经元完全是高度分布式计算。机器学习领域已经建立起的理论，并不能很好的解释深度学习，应该如何建立新的理论去解释和认知深度学习？

全文目录

一、泛化

二、概率统计背景

三、VC理论和regularization方法

四、Margin理论

五、算法稳定性

六、深度学习算法的讨论

一、泛化

1.1 The core of learning theory——generalization

机器学习理论建立在概率统计的基本理论框架上，核心问题是：为了实现具体的学习任务，需要多少数据才能够学好模型？机器学习理论的基本框架是通过收集数据来学习模型，然后用模型在未知的数据上进行预测。模型在未知数据上预测结果好，则该模型的泛化能力好。泛化是机器学习的核心概念之一。

1.2 Ockham’s Razor

对于建立模型，13世纪威廉姆·奥卡姆提出了一个哲学思想: 如无必要，勿增实体。即在能达到相同结果的模型中，选择尽可能简单的模型。这个思想是机器学习中最核心、最本质的思想。泛化能力是这思想的一种定量化表达。

二、概率统计背景

机器学习建立在概率统计的基础上，下面从宏观上介绍下概率统计。

2.1 Law of large numbers

大数定律是指在试验不变的条件下，重复试验多次，随机变量的平均值趋近于它的数学期望。

2.2 Central limit theorem

中心极限定理是指n个独立同分布的随机变量，当n趋近于无穷大时，其平均值也是一个随机变量，且趋近于正态分布。

2.3 Concentration inequality

扔硬币是概率统计中的常见例子。一个材质均匀的硬币，掷接近无穷多次后，频率趋向于0.5。若某个实验掷一万次硬币，结果是40%向上、60%向下，是否能判断硬币有问题？机器学习里的概率工具，Concentration inequality，能够解决这个定量问题。Concentration inequality表明，掷一万次硬币，频率在0.499—0.501区间是合理的。当量化平均值和数学期望之间的偏差时，Concentration inequality是有力的数学工具。

三、VC理论和regularization方法

3.1 Generalization error and Empirical error

关于泛化误差和经验误差，泛化误差是指学习到的模型在未来的应用场景数据上的错误率，经验误差是指学习到的模型在训练数据上的错误率。两者有本质的区别，这区别正是机器学习理论研究的内容。

根据“大数定律”、“中心极限定理”以及不等式，在训练数据上的错误率趋向于它的数学期望，而数学期望恰是泛化误差。有个想法：训练一个模型，使得其在训练数据上达到很小的错误率，根据“大数定律”，期望错误率也会很小。这想法有个逻辑错误，即learning过程是从很大的模型集合里挑选一个具体模型的过程，此时“大数定律”不再适用，训练错误率不一定接近其期望，有可能差距非常大。

这理念与训练Network的过程非常吻合，即模型在训练数据上错误率非常低，但是在测试数据上的结果非常糟糕，这种现象称为过拟合。

3.2 The idea of uniform generalization

Uniform是指为了学到的模型在未来数据上有好的泛化能力，需要模型集合里的所有候选模型（分类器）都具备好的泛化能力。而模型集合里的所有候选模型（分类器）的泛化能力与集合里候选模型（分类器）的个数有关，即模型集合含有的分类器越多，模型的复杂程度越高，就需要越多的数据保证分类器的泛化能力。

3.3 VC theory

训练模型所需的数据量与模型的复杂度呈正相关。目前影响最大、范围最广的机器学习理论——“VC理论”，很好的刻画了无穷大的集合，如果其中都是分类器，则刻画了集合的复杂度。简言之，VC维度越大，模型越复杂，就需要更多的训练数据。

VC 维可以确定训练误差和泛化误差之间的量化关系，训练误差和泛化误差相差上述公式所示的数量级。对于经典的线性模型，如果VC 维是10，所需的数据量至少是VC 维的10倍，即需要100个数据方可达到较好的泛化能力。如果模型的VC 维是一亿，却只有1000个训练数据，就不可能训练好的模型。由此可知，对于训练误差相近的模型，模型越简单泛化能力越好。

上图横轴表示模型复杂度，竖轴表示误差。当模型复杂度过低时，处于“Underfitting”状态，训练误差和泛化误差都很大。当模型复杂度过高时，处于“Overfitting”状态，训练误差很低，但是泛化误差很大。因此，需要找到合适的模型复杂度范围，使得训练误差和泛化误差都处于比较低的状态。

3.4 The idea of regularization

利用VC理论的思想设计算法：设计算法的方法中使用最多的是regularization。即在损失函数后加一个模型复杂程度的相关项，对损失函数中的某些参数进行限制。常见的有L2-Regularization 、L1-Regularization 、Boosting 以及Dropout。

四、Margin理论

常见的SVM和Boosting方法中都有large margin的概念。对于SVM，空间中有正、负两类的点，用一条直线将这两类点分开，且使得两类点与分类面的间距越大越好，这个间距就是margin。Boosting是将很多基本分类器进行组合的过程。比如组合100个分类器，若50%的分类器将数据判为正类，50%的分类器将数据判为负类，则这个数据的margin是0，若100%的分类器将数据判为某一类，则这个数据的margin非常大。即Boosting的Margin体现了Boosting所用的基本分类器对数据分类结果的置信度（confidence），对泛化能力有重要影响。

两者相比，VC 理论只考虑了用数据分类的对错和模型的复杂程度来衡量泛化，而Margin 理论需要考虑更多的信息来衡量泛化，比如Deep learning的输出不仅是对或错，往往输出一个实数值，这个值在某种程度上反映了置信度（confidence）的大小，即算法的输出有很多置信度（confidence）的信息。

五、算法稳定性

第三个比较重要的学习理论是Algorithmic Stability。如何衡量稳定性？假设某训练集有10000个数据，某算法用该训练集训练出一个结果，然后把这10000个数据中的1个数据换成新的数据，若此时分类器没有显著的变化，则此学习算法是稳定的；若有显著变化，则此算法是不稳定的。直观上，稳定的算法有较好的泛化能力。

训练Deep Learning最常用的算法就是Stochastic Gradient Descent（SGD）。上图是2016年SGD稳定性的结果，在convex function上应用SGD算法稳定性很好。尽管Deep Learning的loss function是非凸的，但可以证明SGD仍然具有一定的稳定性。

六、Loss Surface

学习网络是试图最小化loss的过程，loss function是高维函数，loss surface是指分析高维空间中loss function的形状。有人认为loss surface对于深度网络没有局部最小值，但这是不可能的，网络的局部最优点数目非常多，高维函数一定有local minimum，所以这种观点是不成立的。因此loss surface可研究的内容还有很多。

总结

目前为止，机器学习理论还不能很好的解释Deep Learning，即使VC Theory、Margin Theory以及Algorithmic Stability等等，都不能很完美的解释Deep Learning，Learning theory仍然具有重要意义，深入研究Learning theory能够有助于理解Deep Learning以及设计更好的学习算法。

感谢AIDL志愿者邓琪瑶协助整理！