机器学习40讲_05_04_计算学习理论
你好，我是王天一。
今天我和你分享的主题是计算学习理论，无论是频率学派还是贝叶斯学派，他们解决的呢都是怎么学的问题。
但是对于一个给定的问题，它具体到底能够学到什么程度，还需要专门的理论来解释。
这个专门的理论呢？就是计算学习理论和机器学习当中各类具体的算法相比啊，这一部分内容会显得具体而枯燥一些。
学习的目的它不是验证已知，而是探索未知。
人类和机器都是如此。
对于机器学习来说呢，如果说不能够通过算法获得存在于训练集之外的信息的话，那么学习任务在这种问题之上就是不可行的。
点击文稿，你可以看到加州理工大学阿布姆斯ta的课程learning from data中的一个例子。
这个例子是什么呢？要根据五个训练数据来预测三个测试数据。
从么在文稿当中有这个例子的分析数据。
在这儿我就直接给出结论。
关于这个问题，唯一确定的结果就是不确定性。
不管数据的生成机制到底是什么样的训练数据，它都没有给出足以决定最优假设的这样的信息。
那既然找不到，对于测试数据具有更好分类结果的假设的话，那这个机器学习还学个什么劲儿呢？但是别忘了啊，我们还有概率这个工具，它可以对不同的假设做出一个定量的描述。
虽然说不能对每个特定问题都给出最优解，但是概率理论呢可以用来给出通用学习问题的求解，从而给出一些基本的原则。
不妨想象一下这样的一个问题，一个袋子里面有红球和白球，那么红球呢所占的比例是缪，白球所占的比例是一减缪在这里啊作为总体参数的缪是一个未知量。
如果我要估计这个缪的话，估计它的方法就是从袋子里面抽出若干个球作为样本。
那么在样本中呢，不妨设这个红球的比例为缪，这个缪是可以计算计算出来的。
缪就是对于未知参数，缪最直接的一个估计，但是用缪来近似缪，它有多高的精确度呢？直观来看的话，两者的取值应该是相差无几，相差较大的情况，虽然说不是不可能发生存在出现的期望渺茫。
如果假定真实值缪等于零点九的话，如果从袋子当中抽出十个球，那你可以利用二项分布来计算一下这个缪等于零点一的概率。
通过这个实例呢来观察缪和缪相差较大的可能性直观的印象。
它之所以准确，是因为背后存在着科学依据。
在概率论当中，有界的独立随机变量的求和结果和求和的这个数学期望之间，它们的偏离程度存在着一个固定的上进。
这个关系呢可以用霍夫丁不等式来表示点击文稿。
你可以看到在上面的红球白球问题当中，霍夫丁不等式，它的表达式，霍夫丁不等式啊，它能够说明很多问题。
首先它说明了用随机变量缪来估计未知的参数。
缪手虽然缪的概率分布在一定的程度上取决于缪，但是估计的精度只和样本容量有关。
其次呢，它说明了想要提高估计精度的话，最本质的方法还是要增加样本的容量，也就是多采一些数据。
当总体的所有数据都被采样的时候，估计值也就完全的等于真实值。
反过来说的话，只要样本的容量足够大，那么估计值和真实值之间的差值将会以一定的概率被限定在一个较小的常数之内。
把红球白球的这个问题稍作推广，就可以得到关于机器学习的一种描述。
如果把装球的袋子看成数据集的话，那里面的每一个球都是一个数据，或者说一个样本。
球的颜色呢代表的我们评估的这个模型啊，我们使用的这个模型在不同的样本之上的一个表现。
如果说模型的输出和真实的输出不同的话，我们就把它设为红球。
反过来，如果模型的输出和真实输出相同的话，我们就认为它是个白球。
这样一来，抽出来的所有的小球实际上代表了什么呢？代表了这个训练数之几。
那么这种情况下，真实值缪可以理解成这个模型符合实际情况的概率。
那么估计值new呢就表示了模型在训练集上它的一个错误的概率。
在这种条件下，再来看霍夫丁不等式的话，它就变成了对于单个模型在训练集上的错误率和在所有数据上的错误率之间关系的描述，实际上也就是训练误差和泛化误差之间的关系。
这个不等式说明了总会存在一个足够大的样本容量n让训练误差和泛化误差近似的相等。
这时候呢我就可以放心大胆的根据模型的训练误差来推导它的泛化误差，从而呢得到关于真实情况的一些信息。
当这个训练误差缪接近于零的时候，那么和它接近的半化误差缪也会接近于零。
由此呢就可以推断出在使用的模型，它整个的输入空间内都能够以较大的概率逼近真实的情况。
简单来说就是这个模型在整个的输入分布上都是可以使用的，而且性能都不错。
但是如果小概率事件真的发生啊，在某些数据之上啊，或者在某些分布的情形之下，训练误差和泛化误差的确存在较大的差别的话，那也只能说是运气不好。
按照上面的这个思路呢，如果要让模型取得较小的泛化误差的话，可以分成两步走。
第一步我先要让训练误差足够小。
第二步呢是让训练误差和泛化误差两者足够的接近。
正是这种思路催生了这个机器学习当中的所谓概率近似正确这样的学习理论。
这套理论呢是用来对机器学习进行数学分析的这个理论框架。
在这个框架之下呢，机器学习利用训练集选择出来的模型，它很可能啊不是百分之百很可能具有较低的泛化误差。
那么这里面呢很可能呢就对应着概率近似正确当中的概率具有较低的泛化误差，则对应着名称当中的近似正确概率近似正确理论啊简称为PAC学习理论。
那么从这个理论当中呢，又会延伸出PAC可学习性的概念。
这里出于可读性的考虑呢，我并没有给出PAC可学习性的一个数学上的定义啊。
那么你查阅任何一本机器学习教材啊，都会有相关的内容。
观察这个数学定义的话，你会发现其中包含着两个描述近似程度的这个参数。
描述近似正确的呢是一个准确度的参数叫布西隆。
它的作用是什么呢？将模型的误差水平，也就是所选的模型和真实的实际情况之间的距离限制在较小的范围之内。
另一个参数是描述概率的。
这个置信参数啊，我们把它叫德耳塔。
由于训练集呢它是随机生成的，所以呢学好模型不是百分之百。
它只是一个一减去delta,以这个概率出现的大概率事件。
所以呢致进参数描述的就是这样的一个概率的水平。
如果一个问题是可学习的话，那到底需要多少的训练数据才能够达到给定的准确度参数和致信参数呢？这个问题的话，需要引入样本的复杂度来解决样本复杂度，它是保证一个概率近似正确解所需要的样本的数量。
换句话说，就是我用多少数据能喂出一个啊差不多正确满足要求的这个模型，可以证明的是什么呢？所有假设空间有限的问题，那么它都是PAC可学习的。
它的样本复杂度呢是有一个固定的下解输出假设的这个泛化误差会随着样本数目的增加，以一定的速度哎收敛为零。
但是在现实当中的学习任务中呢，并不是说所有问题的假设空间都是有限。
像实数域里面的所有区间，或者说高维空间里头所有的超平面啊，它都属于无限的假设空间。
那么如何判断说这种无限假设空间的这个问题，是不是PAC可学习的呢？这就需要引入一个新的概念，叫VC维。
Vc雷的名称呢来源于统计学习理论两位先驱名字首字母的一个缩写。
它是对无限假设空间复杂度的一个度量方式。
它呢也可以给出模型的半化误差在概率意义上的一个上界。
想象一下这个问题啊，如果我要对三个样本进行二分类的话啊，总共有二的三次方啊，等于八种可能的结果啊。
这所有的八种可能结果对应的就是八卦的那个八个two.当所有的样本都是正立啊，或者都是负立的时候，这种情况下我们是不需要对它进行区分的啊，因为都属于同样的类别。
可是一旦样本当中既有正立又有负立的车，这时呢就需要将两者区分开来。
让所有的正立位于空间的一个区域当中。
所有的复利呢位于另一个区域当中，这里区域的划分方式是完全由模型来决定的。
如果对于八种可能分类结果当中的每一个都能够找到一个模型，将其中的正负力完全分开的话，那就说明一个什么问题呢？由这些模型构成的假设空间，可以将这个数据集给它打散，引入了打散这个概念。
点击文稿，你可以看到利用线性模型来打散容量为三的数据集的一个示意图。
其实对于三个数据来说呢，所有对于分类结果的划分，本质上都是把其中的某两个点和另外一个给它区分开来啊，两个点一组。
另外一个一组要完成这个任务的话，只需要一条直线就足够了，不需要更加复杂的性状。
那么在数学上也可以证明线性模型，它可以对任何三个不共线的点进行划分。
只要你这三个数据点不在同一条直线上，那线性模型就能够将这个数据集给它打散。
可是一旦数据集的容量增加到四的话，线性模型就没法完成打散的任务了。
容量为四的数据集，它总共有十六种分类的可能，但是线性模型呢只能区分开其中的十四种剩的那两种是什么？就是易惑问题的两种情况，要将位于对角线位置的这个正力和负力区分开来的话，要么呢你得使用一条曲线，要么呢你就得使用两条直线，单单一条直线是肯定做不到。
有了打散这个概念，就可以进一步来定义VCV一个假设空间，它的VC维是什么呢？是能够被这个假设空间打散的最大集合的大小，也就表示了完全正确分类的最大的能力。
上面这个例子告诉我们，对于具有两个自由度的这个线性模型来说，它最多呢能够打散容量为三的组合，所以它的VC为也就等于三。
如果说假设空间它能够打散任意容量的数据集的话，那它的VCV就是无穷大，具有无穷大。
Vc维的一个假设。
空间呢它的一个实例就是y等于sin KX,也就是正弦函数啊，那么这里的k呢是可以任意取值，为什么这个空间它具有无穷大的VC维呢？你可以思考一下这背后的原因。
从可学习性的角度来看呢，一旦假设空间的VCV有限，它就可以通过调整样本的复杂度来使得训练误差，以任意的精度来逼近泛化误差，从而呢让两者足够接近这个性质。
它取决于什么？取决于你训练的这个模型的特性和学习方法呀、目标函数啊或者数据自身的分布啊都没有关系。
第二呢，它是通用在维度有限的前提之下，VC维的大小呢也会影响到模型的特性。
较小的VC雷。
它虽然能够让训练误差和泛化误差两者更加接近，但是呢这样的假设空间不具备比较强的表达能力，意味着训练误差本身难以降低。
反过来说，VC为更大的假设空间，它的表达能力更强，也可以得到更小的训练误差。
但是训练误差下降所付出的代价是训练误差和泛化误差之间可能出现较大的差异。
那么在训练集上得到的较小的误差呢，并不能够代表同样优异的泛化镜度。
这呢其实也就体现了模型的复杂度，还有泛化性能之间的一个折中的关系。
由于VC维啊，它并不依赖于数据分布的鲜验信息，所以他得到的结果是一个松散的这个误差器。
松散误插件好处是什么呢？适用于任意分布的数据。
啊，不管你这个数据背后的假设是什么啊，它的生成机制是什么，我通过VC为计算出来的误差器都是适用。
可是如果要把数据的分布特性给它纳入到可学习性的框架里面的话，这时候呢我们就会换一个复杂性的指标啊，这个指标呢就是拉德玛赫复杂度给定一个函数空间。
那它的经验拉达玛赫复杂度描述的是这个函数空间和一个随机噪声在给定的数据集之上的一个相关性。
那么这里的随机噪声呢，它是以拉达马赫变量这个形式来出现萨德马赫变量，它是如何分布的呢？以百分之五十的概率取到正负一这两个值啊，也就是等概率的取正负一。
如果说存在着多个数据集，而且每个数据集生成的机制都相同的话，也就是数据都是对同一个概率分布进行独立重复采样。
而得到的话，那么这种情况下，我对不同的数据集上它的经验，拉德玛赫复杂度，它解数学期望得到的呢就是没有经验的啊，也就是把经验去掉，就叫拉德玛赫复杂度。
它有什么意义呢？它表示了这个函数空间在给定的数据分布上，它拟合噪声的一个性能。
看到这儿你可能要问了啊，说我这机器学习学的好好的啊，为什么要去拟合这个噪声呢？其实引入这个拉德玛和复达度啊，它的初衷也是来刻画训练误差，还有泛化误差之间的区别。
点击文稿，你可以看到拉德玛赫变量，还有拉德玛赫复杂动物在分析半化误差时候的作用。
那么在已知的数据分布之下，拉德玛赫复杂度既可以表示函数空间的复杂度，也可以呢进一步的用来计算这个泛化误差计。
这中间的数学细节呢，在这儿呢我就不做介绍。
今天我和你分享的计算学习理论当中一些最主要的概念啊并没有深入到细节当中。
这呢是评估机器学习的理论基础啊，也是关于机器学习理论研究的一主要的对象啊，包括着以下的一些要点。
第一，霍普丁不等式描述了序练误差和泛化误差之间的近似关系。
第二，PAC学习理论。
它的核心在于学习出来的模型，能够以较大的概率接近于最优的模型。
第三，假设空间的VCA是对无限假设空间复杂性的度量，它体现了复杂度和性能的折中。
第四，拉德马赫复杂度是结合了鲜验信息的。
对于函数空间复杂度的一个度量和各种具体的模型相比呢，计算学习理论当中充斥着各种各样的抽象腿打，那么它的内容也显得比较枯燥无味。
那么你觉得关于学习理论的研究，对于解决实际问题到底能够具有什么样的指导意义呢？欢迎发表你的观点。