分享课｜北京大学王立威教授：机器学习理论的回顾与展望（一）

3月3日，中国人工智能学会AIDL第二期【人工智能前沿讲习班】在北京中科院自动化所举行，本期讲习班的主题为【机器学习前沿】。周志华教授担任学术主任，前来授课的嘉宾均为中国机器学习界一流专家、资深科研人员和企业精英，包括：耿新、郭天佑、刘铁岩、王立威、叶杰平、于剑、余扬、张长水、郑宇、朱军。

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

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

各位老师，同学们，下午好！非常高兴今天能有机会和大家进行分享，也特别感谢周志华老师对机器学习理论做了一个非常精辟的简介。今天我报告的题目是「机器学习的回顾和展望」。

刚才周老师也提到，机器学习理论的目的是建立一个比较纲领性的认识。大家拿到的 PPT 里面有很多数学细节，既然大家已经有打印的版本，所以我就不花过多的时间讲数学细节，我把主要的时间花在介绍机器学习技术性的内容、最后的一些结论可以对你产生什么启发，也就是一些思想上的东西。

那么言归正传。

大家都知道，在过去几年当中，机器学习最成功的、影响最大的理论毫无疑问是深度学习。深度学习到目前为止，在很多地方发挥了作用，也取得了很多的成功。那么大家不禁要问一个问题了：深度学习现在很成功了，而且大家可能都知道，深度学习到目前为止没有什么机器学习的理论，或者说几乎就没有理论，在这个时点上，我们为什么还要思考理论？所以，我今天想谈一下我个人的观点。

其实机器学习这个领域很有趣，如果大家回顾一下它过去大概 30 多年的发展历史，大家会发现，机器学习里面非常重要的一些算法，除了深度学习以外，其他的一些重要算法，比如说大家耳熟能详的 SVM、boosting，还有 Random Forest 等，几乎全是由做学习理论的人提出来的，而不是由做纯应用的人提出来的。到目前为止，只有 Deep Learning（深度学习）是一个例外，而像报告里会提到的 SVM，是由前苏联的概率学家、机器学习理论的先驱 V.Vapnik 提出来的；而 Random Forest 也得益于统计学家 Leo Breiman 的贡献。如果我们把这个时间点拉长一点，大家可以看到，理论的学习其实对算法的设计研究是有着极其重要的影响的。

我们再来看一看深度学习。现在有很多关于深度学习的观点，比如我的一些同事朋友跟我讲，国外一些做深度学习应用方面特别前沿的人，说（理论）在深度学习的时代毫无用处，因为你们理论通常是一些不等式，比如算法设计出来之后，理论会告诉你这个算法的准确度或者说错误率的上界，但通常这个得出来的数值奇大无比，他们还做了一个比较形象的比喻，说就好比证明一只鸡的体重一定要小于一吨一样，这种说法其实是蛮多的。

我想通过今天和大家的分享，谈一谈我的观点，就是说机器学习理论究竟是做什么来用的，它是不是只是为了证明这个界，为了说明算法在实际应用的错误率能小于多少，还是说它在传达一些更高层的信息。我个人的观点是，机器学习理论是后者，绝对不是为了证明一个算法的边界如何；机器学习理论的目的，在于提供对机器学习的问题的洞察和理解。

第二点，很多人会有这样的观点，我们现在是一个大数据时代，像 ImageNet 这样的数据库资源有上千万。在过去，做机器学习理论的研究者可能处理的都是小数据集，也许理论还有一定的价值，但是今天我们做的都是动辄上千万的数据，是不是我们根本就完全不需要机器学习理论呢？

我给大家提一个问题，一千万个数据就真的是大数据吗？我个人认为是小的数据，而且是非常非常小的。为什么呢？今天上千万的数据几乎都出现在视觉这个领域，人或者其他一些高等动物的视觉，经过多长的时间才形成这样的一个神经网络，能够以极快的速度去视觉感知、认知。这个长度是以亿年为单位，在亿年这样的进化过程当中，每一个时点都是生物以整体的角度在学习和进化，如果你从这个进化的角度来考虑，我们把进化看作一个学习的过程，这不是我提出来的理论，这是图灵奖得主 Leslie Valiant 提出来的。所以大家这么考虑，如果整个的生物群体经历上亿年的进化过程，接触到的数据是什么量级，我认为比千千万不知道要增加多少个零，所以我们今天的数据是非常小的数据。

那么，我们今天的神经网络和生物的进化以亿万年的进化得到的数据有多大的不同？我给大家举一个例子。大家知道人脑或很多高等动物的大脑也是由神经元组成的，比如说人脑有着 10 的 11 次方的神经元，大概 10 的 14 到 15 次方的连接。我个人认为动物的神经网络和机器神经网络的最大不同在哪儿呢？

一个是在于结构，第二在于速度，第三在于运行机制。结构我刚刚讲了一点，在于容量不同，下面我谈一点很显著的区别就是速度。人脑中神经元的种类非常多，现在已知的就有上千种，当然我们可以考虑其中非常主流的一些神经元，对于这样的神经元，大家知道神经元和神经元之间信息的传递是靠一些生物电信号，实际上是化学物质的传递。在人或动物的大脑中，信息从一个神经元传递到相邻的神经元所需要的时间，大家知道是一个什么量级吗？是几十毫秒的量级。几十毫秒什么概念？比如说你突然看到一个场景、一幅图像，你马上就有一个反应，这个反应的时间肯定是在 1 秒钟之内。如果你的整个反应是在 1 秒钟之内，这意味着信息在你大脑的神经网络中传递的深度至多是多少，如果你这个大脑中从一个神经元到达下一层神经元传递的速度是几十毫秒的话，这意味着你大脑处理视觉信息所用的神经网络的深度至多就是几十层，如果你的大脑反应过来，可能已经过去将近 10 秒钟了。所以大家要意识到，我们今天所训练的最最先进的神经网络，和人脑中的、动物大脑中的神经网络依然是截然不同的。两者不一样的地方其实远远大于他们相似的地方。

再举一个比较典型的例子，我们今天的神经网络，实际上都是用计算机模拟出来的，并不是一个真正的硬件。我们在计算机上进行模拟，认为层与层之间的信息的传递完全是同步的，必须上一层的信息全部同时传递到下一层的神经元才能够进行处理。在人脑中没有这样的同步控制信号，所以人脑中的神经元完全是高度分布式的一种计算，所以这就是一个重大的不同。所以今天我们深度学习所用的神经网络，即使从生物、从仿生的角度来讲，其实跟真正的生物依然差别很大。所以要想深度理解，必须有一个很基础的理论。当然我们也要面对现实，机器学习这个领域过去发展了几十年，所建立起来的机器学习的过去经典的理论，比如 SVM 等等这一系列的方法，它对于今天的深度学习确实没有非常好的解释或者说认知，但是这也正是一个很好的机会、一个挑战：我们应该如何建立一个新的理论去认知深度学习？根本目的是，我们能不能够将来设计出更加有效的方法？给大家举一个例子，人脑以这么慢的信息传递速度，其实在很多很多的问题上要比今天的深度学习训练出来的网络效果要好得多，如果我们要能够基于这些理论设计出类似于我刚才讲的人脑的一些方法，岂不是要比今天的深度学习的性能要提高百千万倍？

接下来，我们就开始进入具体的内容。

首先，我们来看看机器学习理论最核心的一个观点就是 generalization（泛化）。谈泛化之前，我们先了解一下机器学习理论是做什么的。机器学习理论是为了给整个机器学习建立完整的框架，所以必须要有很严谨的形式。概括来说，机器学习理论是建立在概率统计的基本理论框架之上。它研究的核心问题在于，如果要实现一个具体的学习任务，需要多少资源能达到这个目的。而在机器学习中，很重要的资源就是数据，所以我们就是要研究究竟需要多少数据我才能够学好。当然如果在数据已经给定的前提下，不同的方法规定了相同的数据，机器学习的成果是不一样的，所以也可以表示出来。

这是机器学习理论的一个基本框架：我们要通过收集数据来学习出一个模型，拿到这个模型以后我们根本的任务是做预测，这个预测是在未知的数据上去做的，所以一个很关键的问题是，我们的目的是希望在未知数据上学出来的模型能够表现出很好的性质，而不仅仅局限在我们已经收集到的数据。

虽然大家通常认为机器学习是过去几十年发展出来的一个学科，但是我个人认为，其实机器学习一直伴随着人类文明的发展。从人类真正有文明、有科学那天，就有机器学习。我给大家举几个例子：

第一个，「胡克定律」，我相信各位肯定都接触过这个中学物理问题，这个定律是探讨拉伸的力和弹簧伸长的长度是什么样的物理关系。如果我们站在胡克的角度，这是一个什么过程？我认为这是一个非常典型的机器学习过程。胡克做的第一步是收集数据。他拿一个弹簧做了很多次实验，根据每一次伸长的距离记录拉力，并将数据记录在一个表上。第二步，胡克（当然是用他的脑子，不是用计算机）学会了一个模型。他最后得出的结论是，这是一个线性的模型。再之后胡克拿了一些新的弹簧，再把它做拉伸，是否还符合这个模型。所以胡克发现「胡克定律」，就是一个非常典型的机器学习的过程：收集数据、建模、做出预测。机器学习的这种思想一直在科学领域不断应用。

有一个问题，为什么胡克会学到一个线性的模型？大家看到这个线性模型，其实他的观测数据上有很多的误差的。比如说胡克做了 100 次实验，得到 100 个点，他为什么不找一个曲线恰好能够通过这 100 个点，使得训练数据上没有误差？比如说我们很容易找到一个 99 阶的多项式，而使得这 100 个点被零误差地覆盖，所以大家要思考一下：胡克为什么能够得到这样一个结果，而不是一个复杂的曲线，里面最本质的思想是什么，大家体会一下。

当然也有人质疑，认为「胡克定律」在物理学上没有任何的地位，不是一个什么了不起的定律，大家看一看「开普勒定律」，这是了不起的贡献。「开普勒定律」讲的是什么？开普勒通过研究过去上千年天文学积累的数据，最后发现三个规律。举一个例子，说行星围绕太阳转动，实际轨迹是一个椭圆，他找到这个椭圆实际上不是精确吻合了这些数据，只是近似吻合，他为什么不找一个复杂的曲线完全吻合这个数据？开普勒在归纳这个数学规律的时候，背后也有一些非常奇妙的思想，并不是简简单单的观测这个数据。最后我们来看一看机器学习里经常见到的，学习一个分类器，我们可以用一个很简单的分类器，用光滑的曲线来表示，我也可以用一个非常复杂的分类器，用弯弯曲曲的线来表示。当大家观察到这幅图的时候，你觉得应该是简单的曲线，但是有一些分类误差比较好呢，还是复杂曲线，对于观测到的数据没有误差更好呢？

我们来总结一下刚才几个例子里面，其实在通过学习模型和数据的时候，物理学家或者机器学习的学者是怎么样思考的，其实这早在 13 世纪威廉姆·奥卡姆就提出了一个哲学思想（奥卡姆剃刀理论），是用拉丁文写的。其实我对他的解释应该有一位更著名的科学家，有一段更著名的话，是对这句话进行最完美的解释「Everything should be made as simple as possible but no simpler」，这句话是爱因斯坦说的，意思是做理论的时候一定要尽可能的简单，但是你又不能过于简单。对应物理模型的时候一定要找到一些模型，允许存在一定的误差，但是又不能过于简单，如果过于简单，和你观测的数据误差太大也不行，奥卡姆剃刀的这一思想实际上是机器学习或者整个人类在获取科学知识的历程中，最核心、最本质的思想。

在今天的机器学习理论里，实际上是把威廉姆·奥卡姆剃刀的思想定量化表示出来了，为什么要定量化？因为今天，机器学习处理的问题，要比物理学的「胡克定律」、「开普勒定律」复杂千万倍。甚至有人这样讲，今天在 21 世纪，如果你去研究物理学，你最后得到的是一个线性模型，我根本不需要看你具体研究的是什么模型，得到的是什么结果，我可以很肯定的告诉你，你做的东西要么就是早就被别人已经做过了，要么就是这个问题太简单没有任何意义。

换句话说，物理学中较为简单的定律早就被发现了。今天机器学习处理的问题是一些非常非常复杂的问题，给大家处理一些图像、一些声音，还有搜集到的一些数据，牵扯到很多的人的因素，这是很复杂的东西，你不可能指望用简单的方程，低次的一些方程或者低次的一些物理系统去描述。所以当你本质的模型已经极其复杂的时候，我究竟应该用一个多复杂的模型来表示？我需要一个定量的指导。所以机器学习最重要的是在一个定量的层面上，对刚才我们讲的奥卡姆剃刀理论，给出一个定量的定义。

那么我们前面提到，机器学习建立在概率统计的基础上，这里面我就不对概率统计的数学细节做过多的解释了，如果感兴趣的老师、同学们可以课后去看我们这个印发给大家的具体内容，我还是在思想上给大家做一个比较稍微宏观一点的介绍，在这之前有一些准备的工作。

大家可能都知道，概率论里有一个叫「大数定律」的理论，讲的是如果我观测一个随机变量很多次，它的平均值应该是趋向于它的数学期望。比如说以前有一个掷硬币的例子，假如说掷一万次，这里面向上的次数应该是多少呢？如果这是一个非常均等公平（fair coin）的硬币，那么你掷接近无穷多次之后，频率最后应该是趋向于 0.5，这就是大数定律。之前数学家 Nicolaus Bernoulli，就找了一个硬币，掷了几万次，最后观测出这样的一个数值。

那么我问大家一个问题：现在有一个这样的硬币，大家掷 1 万次，我们知道掷出来的结果和 0.5 非常接近，但是究竟有多近呢？假如说你掷 1 万次，发现 40% 是向上，60% 向下，你觉得这个硬币有没有问题？

我接下来要讲的机器学习理论就是为了给出一个定量的结果，就必须用一些能回答这个问题的数学工具。如果你掷出来正反面的概率是 40% 和 60%，那么你的硬币本身有没有毛病，或者说如果硬币没有问题，你掷硬币的时候应该会在一个什么区间里。

有一个定理和我刚才讲的这个理论是有点相关的，叫中心极限定理，大家应该听说过，如果我有很多独立分布的随机变量，我们考虑一个平均值，它也是一个随机变量，但最后一定会趋向于一个正态分析，而且会告诉你正态分布的方差是多少。

那么机器学习里面用的概率工具就能够回答我刚才说的定量问题，叫做「Concentration inequality」，其中比较重要的一点在于，它给出了数学上非常精确的一个定量描述，一个硬币，假如说它是一个正常的硬币，如果掷 1 万次，在什么区间里是比较合理的呢？应该在 0.499—0.501 这个区间是比较合理的，就是由这些不等式精确地给出了。如果你掷出来的是 0.4 或者哪怕是 0.45，那么这个硬币 99.99% 的可能性是有问题的。

所以这样一个概率里面表示的，实际上是我们机器学习里面常用的数学工具。

刚刚讲 Concentration inequality 是一大类概率数学的不等式，其中最有代表性的，大家对这个名字能够有所耳闻就可以了，叫 Chernoff Bound，是描述刚才讲的掷硬币的平均值和你的数学期望大概有多大偏差，这是一个量化的刻画，所以如果将来有一天遇到类似的问题需要找一个数学工具来解决的话，可以首先去查一下 Chernoff Bound，这些在网上都可以得到。

还有不等式，这都是非常常用的工具，具体的不再给大家做过多的细节介绍。

接下来我想和大家介绍机器学习里面的第一个理论，也是机器学习里到目前为止影响最大、范围最广的一个理论。这个理论叫“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千个之后的airpok可能比50的小很多，但是你的迭代1000个时的测试错误可能就已经大得没办法看了。

本文为北京大学王立威教授《机器学习理论的回顾与展望》主题报告（上），主题报告（下）敬请关注后续报道。