北京大学王立威教授：机器学习理论的回顾与展望（二）

雷锋网［AI科技评论］按：本文根据王立威教授在中国人工智能学会AIDL第二期人工智能前沿讲习班＊机器学习前沿所作报告《机器学习理论：回顾与展望》编辑整理而来，雷锋网在未改变原意的基础上略作了删减。

王立威

王立威，在北京大学教授主要研究领域为机器学习。在包括COLT, NIPS，JMLR, PAMI等权威会议期刊发表论文60余篇。2010年入选 AI’s 10 to Watch，是首位获得该奖项的亚洲学者。2012年获得首届国家自然科学基金优秀青年基金，新世纪优秀人才。任 NIPS 等权威会议 Area Chair，和多家学术期刊编委。以下为王立威教授所做的现场演讲的第二部分，主要覆盖VC理论的介绍。

接下来我想和大家介绍机器学习里面的第一个理论，也是机器学习里到目前为止影响最大、范围最广的一个理论。这个理论叫“VC理论”，VC这个字母代表了两个人名字姓名的首字，他们是Vapnik和Chervonenkis。最开始我提到，机器学习里面除了深度学习以外，有非常多最重要的算法，实际上都是做纯理论的学者提出来的。其中SVM就是由VC理论里面的Vapnik所提出来的。我们来看看“VC理论”讲的是对机器学习理论怎么样的理解。

这里面有很多定义，我就不一条一条的给大家介绍了，只给个别名词给大家解释一下。有些数据，比如这个数据是一幅图像，我们可以认为是图像的空间里存在的数据，如果对这个图像进行分类，我们可以把类别标号也看作一个集合。在学习的时候，其实有一个很重要的假设，也是一个基本的理论框架，就是我们一定假设我们观测到的数据，是按照一定的随机性产生的。比如我们现在拿到一个任务，要研究一个图像分类问题。我现在手里有1千万图像，例如ImageNet，大家可以想象这个ImageNet是从世界上所有可能的、相关性的图像中随机抽取来的，这个假设其实是相当合理的。这里面的数据认为是随机抽取来的，而且这个随机抽取我们可以认为它是按照某种分布状态随机抽取的。并且我们还可以假定，未来当我们从这些数据上学出一个分类器、学出一个模型之后，我们要应用场合的数据。也就是我们真正要去实际应用的时候，那些数据也是随机抽取出来的，并且应该和训练数据从同样的分布中抽取出来的，这种假设是有一定的必然性的。如果我未来应用的场合和我做训练的场景不是同一个分布，稍有区别还可以，但如果应用场景和训练场景没有任何关联，那么机器学习不可能获得成功。

这是一些基本定义。还有一个定义，即你在学习时需要有一个模型，这个模型可能是一个线性模型，比如前面举的例子；也可能是SVM这样的非线性模型。如果是线性模型大家都理解，而SVM可以看成是高维空间，甚至是无穷维这样的线性模型。或者你在学一个深度学习、学一个网络，但是无论你是用哪一种模型，其实你都把分类器限制在某一个集合里了。线性模型就是所有的线性模型集合，SVM是在Hilbert空间中的线性分类器。如果你是一个Network，当你把Network的层级、结构都固定了，那就是在这样固定的层数结构下面，所有可能的Network的集合。因为不同的参数会得到不同的Network。当然如果你层数和结构可变的话，我可以把我的集合再扩展。这样的集合通常叫做假设空间（hypothesis space）。换句话说你学习的模型总是从一个限定里面得出来的，而不是凭空选择的。这个概念其实非常重要。

回顾一下刚才说到的“胡克定律”和“开普勒定律”，其实它们都牵扯到这个问题。“胡克定律”实际上已经把假设空间限制在了线性模型中。限制之后，你再去找最好的线性模型去适应你的数据。“开普勒模型”是限制在椭圆模型中。所以大家也可以看出假设模型是非常重要的。

有了刚才这些基本的概念，我们来解释一下学习理论最重要的概念——泛化。什么叫做泛化，泛化其实非常简单。前面谈到，学习的目的是希望学好一个模型，并且让这个模型在未来要应用场景的数据上有非常高的准确度。所谓泛化的错误，就是指一个模型在未来的应用场景下的错误率，叫做泛化。为什么叫泛化呢？我们可以把它和我们经验的错误，或说在训练数据中的错误做对比。通常大家训练一个问题的时候，你拿到很多训练数据，你可以学一个分类器，在训练数据上得到一个错误率。而这个训练的错误率和刚才讲的泛化的错误率实际上后面要看到，这二者是有非常本质的区别的。这个区别正是机器学习理论要研究的内容。

刚才我们谈到“大数定律”、“中心极限定理”，讲的都是，比如说掷硬币，掷很多次以后的平均值最后会趋向于数学期望。如果我们仔细的从技术细节上想一想我们刚才的学习的话，如果有一个给定的分类器，这个分类器的错误率，比如说训练数据上的错误率，实际上就是对每一个训练数据是否正确，这个值就是在所有训练数据上做的一个平均：错误的记录1，正确的就记录0，就是这样的一个平均。根据我们刚才讲的“大数定律”、“中心极限定理”，甚至是不等式，它们都说明随着训练数据的增加，你给定的数据在训练集合上的错误率应该趋向于它的数学期望。大家看一下这个数学期望恰恰是我们前面定义的所谓泛化错误，泛化错误其实就是你那个错误率的数学期望，在未来没有看到的数据的错误率就是你的期望值。

那“大数定律”难道不是吧你的问题给直接解决掉了吗？我只要训练，找到一个训练的模型，他在训练上有一个很小的错误，根据“大数定律”是不是期望错误率就很低呢，而“期望错误率”正好是我们未来应用到场景上的错误率。这里有什么问题吗？

这里面有一个很重要的逻辑上的错误，就是大家一定要意识到，学习的过程是从一个很大的模型集合里面挑选一个具体模型的过程，而挑选这个过程使刚才我们说的“大数定律”不能再应用，如果对这个细节感兴趣，大家回去以后仔细看看我上页PPT的内容。挑选这个过程是极其核心的。由于你是可选的模型范围很大，所以这个时候你挑选出来的模型的训练错误率不一定和期望接近，有可能差异非常大。用“胡克定律”举一个比较直观的例子，比如你这里有一个弹簧，做100次实验，假如我把这个模型空间放在所有可能的99阶多项式，我一定可以从这个模型空间中找到99阶的多项式，使得我们观测到的100个数据完全覆盖，这个时候你的训练错误率是零，但这个时候泛化的结果是多少？也就是你新做一个实验、拿到一组新的数据的时候，期望的错误率是多少。如果给你一个99阶的多项式，它的振荡很多，那么新来一个数据以后，这个99阶的多项式肯定性能非常差，从直观上你就能看出来它没有任何的稳定性。这就叫过度拟合（over-fitted）。由于你是从一个很大的集合中挑选出来的这个模型，尽管这个模型把你的数据处理的非常好，但是你过度拟合了，没有达到泛化的目的。

在这里我插一句，虽然我在后面还会重点讲到这个问题，今天可能还有很多在座的老师、同学都在用深度学习，可能在座各位有相当多的老师、同学都有过训练神经网络的经验。大家在训练神经网络的过程中有没有这样的体会；在相当一部分的训练实验中，你训练错误可以降得非常低。但是在我的测试数据上，可能开始这个测试数据还是在降低，但是训练到某一个程度之后再训练下去，测试错误升高了。这是训练深度学习时经常会遇到的问题。这就是典型的过度拟合。在训练数据中做的好，但对于测试数据差别很大了。

其实这种现象也是机器学习最根本的现象，而且我觉得并不是因为深度学习时代来临了，过度拟合就不存在了。即使你用很大的数据集它依然是存在的。刚刚朱军老师给大家讲了一句话，随着深度学习近几年的发展，大家认为防止过拟合这件事情越来越重要。所以大家要意识到，在今天所谓大数据的时代、在深度学习的时代，其实仍然是经常发生的，后面我会更细致的谈到这个问题，在如何处理解决这个问题上谈一些我自己的想法。

回到刚才的问题，如何保证机器学习有一个很好的泛化能力呢？这里面就提到一个很重要的概念uniform generation。简单来讲它意思是说，你现在的目的是保证你学出来的分类器未来能有很好的效果，而你要想保证这一点，实际在很大程度上是要保证你刚才模型侯选的这个空间里几乎所有的分类器都得有一个比较好的泛化能力，同时具有一个比较好的泛化能力。只有做到这一点的时候，你学出来分类器才能有一个比较好的泛化能力，因为你在观测到训练数据之前，不知道你学出来的将会是哪一个分类器，所以你如果能保证对集合里面所有可能的分类器都有很好的泛化能力，就能保证你学出来的也有这样的能力。

那么如何才能够保证所有的集合里面侯选的分类器都有很好的泛化能力呢？它和什么有关呢？我今天不讲太多数学上的细节，它的核心点在于，你侯选模型的集合究竟有多大。具体到这一个符号，指的是，如果你侯选的模型集合是有限的，只含有有限多的分类器，这个符号就代表了它所含分类器的个数。简而言之模型含有的分类器越多，那么要保证学出来的分类器有较好的泛化能力，就需要更多的数据。

回到胡克的那个例子，如果你用一个很简单的模型，比如用一个一阶线性模型，待会儿我会谈到，一阶线性模型虽然是一个比较小的集合，但实际上含有无穷多的元素，因为线性模型有无穷多个，它是连续的。这个地方大家可以先从直观的角度去认为它是一个比较小的模型，它所含的元素个数比较少。由于一阶的线性模型某种意义上是一个比较小的集合，这个时候，只需要少数实验，可能10个观测数据可能就可以学出一个比较好的模型，再来一个新的数据，它的泛化能力就比较好。但是如果真的想学一个99阶多项式这样的模型，所需要的数据量就大太多了。刚才我们讲，你有100个数据想学99阶多项式，这个学习理论告诉你100个数据太少了，得需要1万个数据。当你观测到1万个数据的时候，大家再用99阶多项式再去看，哪一个最好的99阶多项式能够和我的训练数据更吻合呢，可能大家会惊讶的发现，这99阶多项式，99、98一直到第二次项前面的系数实际上几乎是0，实际上它就是一个现象级。

下面我总结一下。这个学习理论告诉大家，假如我是从一个侯选的集合里选择一个模型，要想学好，所需要的数据量一定和模型的复杂程度呈正相关。用今天大家更常见的深度学习来做一个比较形象的比喻，如果你想训练一个1千层的网络，比如这个网络说有几百万个节点，和你想训练一个10层的网络，这个网络可能就是几千个节点，大家想一想哪个网络需要的训练数据量更大呢？肯定是模型很复杂的、深层的节点数更多的，需要的训练数据量更大。换一种表示方式，如果我给定了你10万个数据，你应该选择一个什么样规模的网络来训练，这个对实际应用有很大的指导意义，如果你不了解这个机器学习的基本思想，那就没有指导性。所以机器学习能告诉你大致应该在一个什么样的范围内选择模型的复杂程度，这个实际上就给出了机器学习理论是干什么用的。它不是具体的证明，而是告诉你一些高水平的想法。这个地方告诉你的是，当你有一些数据量的时候，你要根据你的数据量来选择模型复杂程度。如果大家不相信回去可以做实验，拿1万个数据，看看你用一个几百层的神经网络训练出来，会不会发生我刚才讲的过度拟合的现象。我估计你做10次实验起码有8、9次都会发生这个现象。

刚才给大家讲到VC理论，如果它只是这么简单的故事，也不能称之为理论。它理论技术上的核心，是它能够给出非常精确的量化描述。这个量化描述本质上是它能针对无穷大的集合给出一个复杂描述。刚刚说了如果有限大的集合，这个集合里的元素数量就是对它大小的刻画，但当这个集合是无穷大的时候，怎么刻画呢？所以V、C两人就提出了一套理论，对无穷大的集合给出一个刻画的参数，叫做VC维度（VC dimesnion）。它非常好的刻画了无穷大的集合，如果它含有的都是分类器的话，它的复杂度有多大。大家会发现它的应用范围之广，你会发现它在计算机很多领域都有广泛应用。

简言之VC维度越大，说明模型越复杂。这样的模型想要训练好，就需要有很多的训练数据。如果感兴趣的老师、同学们可以具体去看一些例子，常见模型是可以计算VC维度的。如果用线性模型这种很经典的模型，它可以给大家一个大致的量化说明。如果你的模型的VC维度是10，你需要多少训练数据？我认为大概需要VC维度10倍，也就是100个训练数据。所以如果你的VC维度是1亿的模型，而你只有1千个训练数据，那就不可能训练好，过度拟合的肯定很严重。但如果你VC dimesnion比数据量小太多，就走向了另一个极端——拟合不足（under-fitted）。就是说最好的模型还不能拟合训练数据，所以在这些方面大家要多做注意。

• 最后总结一下，VC维度刻画的到底是什么？

VC维度刻画的是你从一个什么样的模型集合中去训练，刻画的是模型集合的复杂程度，它研究的是结构的性质。VC维度本身没有给我们讲任何算法的事。只告诉你现在有这么样一个VC维度，你可以对任何一个模型集合，比如说估计它的VC维度，你大概知道需要用多少训练数据，但这对你的学习算法有什么用VC维度其实没有回答这个问题。你的学习算法呼应VC维度，实际上就是从你这个模型集合里面去找一个使得训练错误最小的。大家会看到，后面很多其他的学习理论和VC理论是非常重要的，VC理论对算法没有太多牵扯，它研究的是集合大小的复杂程度。有了VC维度D之后，我大概可以泛化错误和训练错误之间有什么样的量化关系。核心就是√D/N，N是数据量，D就是VC dimesnion，所以我刚才讲数据量至少是VC dimesnion的10倍，才能使跟号下的数据足够小。

这个地方用一个图能比较好的反映泛化错误和训练错误。这个图横坐标是模型集合的复杂程度，它是左低右高；纵轴代表错误，这条曲线是经验错误，这个U型曲线是泛化/测试错误。随着你的模型从最简单，也就是拟合不足、训练错误和泛化错误都很大，到最右边得过度拟合，也就是训练错误很低了，但是由于模型非常复杂，泛化错误也很大，所以你一定要找到一个非常合适的复杂程度作为最终模型所选择的范围。这是VC理论给我们提供的一个思想：大家一定要找到合适复杂程度的模型。

刚刚讲的VC理论本身其实没有涉及到算法，但是做机器学习最终还是要落实到算法，有什么方法能够利用VC理论这样的思想帮助我设计算法呢？其实用到最多的就是正则化（regularization）。可能很多人都听说过这个方法，比如说在结构风险最小化（SRM）里面提出来的，用层级（hierarchy）来做模型的集合。更多的正则化是，我优化的目标是我训练的数据，但是我要加上一个和模型复杂程度相关的一项。

刚才讲了模型的复杂程度对泛化错误的影响，如果用到算法，一个很自然的思想就是用到正则化当中。这个是在算法层面上的实现，这是非常重要的。大家可以看SEM，非常典型的L2的正则化，前面是一个所谓的训练损失。还有L1的正则化，LASSO等等。

还有Boosting，它是一个迭代的过程，每迭代一步，生成一步基本分类器，最后把所有基本分类器综合到一块。显然随着迭代的不断增加，模型会越来越复杂。我如何解决模型过于复杂最后导致的过度拟合呢？early stoping就是一种方法。那在深度学习中你有没有用到过early stoping呢？很多时候你用Network的时候，实际几乎总是在用early stoping，你训练一定的epoch你就得停掉。如果不停，让它不断的迭代下去，我觉得最后很可能就会过度拟合。你迭代1000个和迭代50个的结果可能会及其不同。但是1千个之后的epoch可能比50的小很多，但是你的迭代1000个时的测试错误可能就已经大得没办法看了。

本文为北京大学王立威教授《机器学习理论的回顾与展望》主题报告（二），后续主题报告敬请关注雷锋网［AI科技评论］后续报道。