(公众号：)［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科技评论］先前报导。版权文章，予以许可禁令刊登。

下文闻刊登须知。

本文来源：NG体育-www.xyc0851.com