分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程​​​​https://www.captainai.net/troubleshooter无论是频率学派的方法还是贝叶斯学派的方法解决的都是怎么学的问题。但对一个给定的问题到底能够学到什么程度还需要专门的计算学习理论computational learning theory来解释。与机器学习中的各类具体算法相比这部分内容会略显抽象。学习的目的不是验证已知而是探索未知人类和机器都是如此。对于机器学习来说如果不能通过算法获得存在于训练集之外的信息学习任务在这样的问题上就是不可行的。下图就是来自于加州理工大学教授亚瑟·阿布-穆斯塔法Yaser S. Abu-Mostafa的课程Learning from Data中的一个例子假设输入$\mathbf{x}$是个包含三个特征的三维向量输出$y$则是二元的分类结 果训练集中包含着五个训练数据学习的任务是预测剩下的三个测试数据对应的分类结果。横线上方为训练数据下方为待估计的分类结果$f_1$~$f_8$代表所有可能的映射关系。预测三个二分类的输出总共就有$2 ^ 3 8$种可能的结果如上图所示。可在这穷举出来的8个结 果里到底哪个是符合真实情况的呢遗憾的是单单根据这5个输入数据其实是没有办法确定最适 合的输出结果的。输出结果为黑点可能对应所有只有1个特征为1的输入数据此时三个测试数据的 结果应该全是白点也可能对应所有奇偶校验和为奇数的输入数据此时三个测试数据的结果应 该是两白一黑或者还有其他的潜在规律。关于这个问题唯一确定的结果就是不确定性不管生 成机制到底如何训练数据都没有给出足以决定最优假设的信息。既然找不到对测试数据具有更好分类结果的假设那机器学习还学个什么劲呢别忘了我们还有 概率这个工具可以对不同假设做出定量描述。虽然不能对每个特定问题给出最优解但概率理 虽 论可以用来指导通用学习问题的求解从而给出一些基本原则 论 。不妨想象一下这个问题一个袋子里有红球和白球所占比例分别是$\mu$和$1 - \mu$。在这里作 为总体参数的$\mu$是个未知量其估计方法就是从袋子里抽出若干个球作为样本样本中的红球比 例$\nu$是可以计算的也是对未知参数$\mu$最直接的估计。但是用$\nu$来近似$\mu$有多高的精确度呢直观看来两者的取值应该相差无几相差较大的情况虽然不是不可能发生但是希望渺茫。在真 实值$\mu 0.9$时如果从袋子中抽出10个球你可以利用二项分布来计算一下$\nu \le 0.1$的概率 由此观察$\nu$和$\mu$相差较大的可能性。直观的印象之所以准确是因为背后存在科学依据。在概率论中有界的独立随机变量的求和结 在 果与求和数学期望的偏离程度存在一个固定的上界这一关系可以用 果 Hoeffding不等式Hoeffdings Inequality来表示 。在前面的红球白球问题中Hoeffding不等式可以表示为$$ P[| \nu - \mu | \epsilon] \le 2e ^ {-2 \epsilon ^ 2 N}$$这个式子里的$\epsilon$是任意大于0的常数$N$是样本容量也就是抽出的球的数目。Hoeffding不等式能够说明很多问题。首先它说明用随机变量$\nu$来估计未知参数$\mu$时虽然前 者的概率分布在一定程度上取决于后者但估计的精度只和样本容量$N$有关其次它说明要想提 高估计的精度最本质的方法还是增加样本容量也就是多采一些数据当总体的所有数据都被采 样时估计值也就完全等于真实值了。反过来说只要样本的容量足够大估计值与真实值的差值 将会以较大的概率被限定在较小的常数$\epsilon$之内。红球白球的问题稍做推广就是对机器学习的描述。把装球的袋子看成数据集里面的每个球就都 是一个样本球的颜色则代表待评估的模型在不同样本上的表现红球表示模型输出和真实输出不 同白球表示模型输出和真实输出相同。这样一来抽出来的所有小球就表示了训练数据集真实 值$\mu$可以理解成模型符合实际情况的概率估计值$\nu$则表示了模型在训练集上的错误概率。经过这样的推广Hoeffding不等式就变成了对单个模型在训练集上的错误概率和在所有数据上的错误 概率之间关系的描述也就是训练误差和泛化误差的关系。它说明总会存在一个足够大的样本容 它 量$N$使两者近似相等这时就可以根据模型的训练误差来推导其泛化误差从而获得关于真 使 实情况的一些信息 实 。当训练误差$\nu$接近于0时与之接近的泛化误差$\mu$也会接近于0据此可 以推断出模型在整个的输入空间内都能够以较大的概率逼近真实情况。可如果小概率事件真的发 生泛化误差远大于训练误差那只能说是运气太差了。按照上面的思路让模型取得较小的泛化误差可以分成两步一是让训练误差足够小二是让 让 泛化误差和训练误差足够接近 泛 。正是这种思路催生了机器学习中的“概率近似正确 概 ”Probably ApproximatelyCorrect, PAC学习理论它是一套用来对机器学习进行数学分析的理论框架。在这个 框架下机器学习利用训练集来选择出的模型很可能对应名称中的 机 “概率概 ”具有较低的泛化 误差对应名称中的 误 “近似正确 近 ”。如果观察PAC可学习性 可 PAC learnable的数学定义这里出于可读性的考虑没有给出大部分机器 学习教材里都会有这个定义你会发现其中包含两个描述近似程度的参数。描述描 “近似正确 近 ”的是的 准确度参数 准 $\epsilon$它将模型的误差水平也就是所选模型和实际情况之间的距离限制在较 小的范围内描述 小 “概率概 ”的是置信参数 的 $\delta$由于训练集是随机生成的所以学好模型只是 以$1 - \delta$出现的大概率事件而并非 出 100%发生的必然事件 发 。如果问题是可学习的那需要多少训练数据才能达到给定的准确度参数和置信参数呢这要用样本 复杂度来表示。样本复杂度 样 samplecomplexity是保证一个概率近似正确解所需要的样本数量。可 以证明所有假设空间有限的问题都是PAC可学习的其样本复杂度有固定的下界输出假设的泛 化误差会随着样本数目的增加以一定速度收敛到0。但是在现实的学习任务中并非所有问题的假设空间都是有限的像实数域上的所有区间、高维空 间内的所有超平面都属于无限假设空间。如何判断具有无限假设空间的问题是否是PAC可学习的 呢这时就需要VC维登场了。VC维Vapnik-Chervonenkis dimension的名称来源于统计学习理论的 两位先驱名字的首字母它是对无限假设空间复杂度的一种度量方式也可以用于给出模型泛化误 差在概率意义上的上界。想象一下如果要对3个样本进行二分类的话总共有$2 ^ 3 8$种可能的分类结果。当所有样本都 是正例或都是负例时是不需要进行区分的可当样本中既有正例又有负例时就需要将两者区分 开来让所有正例位于空间的一个区域所有负例位于空间的另一个区域。区域的划分方式是由模 型来决定如果对于8种分类结果中的每一个都能找到一个模型能将其中的正负例完全区分那就 说明由这些模型构成的假设空间就可以将数据集打散shatter。上图就是一个利用线性模型打散容量为3的数据集的例子。其实对于3个数据来说所有对分类结果 的划分本质上都是把其中的某两个点和另外一个区分开来而完成这个任务只需要一条直线而无 需更加复杂的形状。可以证明线性模型可以对任何3个不共线的点进行划分也就是将这个数据集 打散。可是一旦数据集的容量增加到4线性模型就没法把它打散了。容量为4的数据集总共有16种类别划 分的可能但线性模型只能区分开其中的14种不能区分开的是什么呢就是异或问题的两种情 况也就是红色图示中的特例。要将位于对角线位置的正例和负例区分开来要么用一条曲线要 么用两条直线单单一条直线是肯定做不到的。在打散的基础上可以进一步定义VC维。假设空间的VC维是能被这个假设空间打散的最大集合的大 小它表示的是完全正确分类的最大能力。上面的例子告诉我们对于具有两个自由度的线性模型 来说它最多能打散容量为3的集合其VC维也就等于3。如果假设空间能打散任意容量的数据集 那它的VC维就是无穷大了。一个具有无穷VC维的假设空间是$y sin(kx)$你可以思考一下这背后的 原因。从可学习性的角度来看一旦假设空间的VC维有限就可以通过调整样本复杂度来使训练误差以任 意的精度逼近泛化误差使泛化误差和训练误差足够接近。这个性质取决于模型的特性与学习方 法、目标函数、数据分布都没有关系因而是通用的。从这个结论出发就可以得到任何任 VC维有限 维 的假设空间都是 的 PAC可学习的 可 。在维度有限的前提下VC维的大小也会影响模型的特性。较小的 较 VC维虽然能够让训练误差和泛化 维 误差更加接近但这样的假设空间不具备较强的表达能力想想上面线性模型的例子训练 误误差本身难以降低。反过来 误 VC维更大的假设空间表达能力更强得到的训练误差也会更 维 小但训练误差下降所付出的代价是训练误差和泛化误差之间更可能出现较大的差异训练集 小上较小的误差不能推广到未知数据上 上 。这其实也体现了模型复杂度和泛化性能之间的折中关系。由于VC维并不依赖于数据分布的先验信息因此它得到的结果是个松散的误差界 误 error bound 这个误差界适用于任意分布的数据。要是将数据的分布特性纳入可学习性的框架复杂性的指标就 变成了Rademacher复杂度 复 Rademachercomplexity。函数空间的经验经 Rademacher复杂度 复 empiricalRademachercomplexity描述函数空间和随机噪声在给 定数据集上的相关性这里的随机噪声以Rademacher变量Rademacher variable的形式出现它以各 50%的概率取$\pm1$这两个值。如果存在多个数据集而每个数据集中的数据都是对同一个概率分 布的独立重复采样那么对每个数据集的经验Rademacher复杂度求解数学期望。得到的就是“没有经 没 验的验 ”Rademacher复杂度 复 它表示了函数空间在给定的数据分布上拟合噪声的性能。看到这里你可能不明白了学得好好的为什么要去拟合噪声呢其实引入Rademacher复杂度的初衷是 刻画训练误差和泛化误差之间的区别。泛化误差是没办法计算的只能想方设法地去近似而交叉 验证就是最常用的近似手段。如果将容量为$m$数据集等分成训练集$S_1$和验证集$S_2$那训练误 差与泛化误差之差就可以写成$$ E_{S_1}(h) - E_{S_2}(h) \dfrac{2}{m} [\sum\limits_{x_i\in S_1} e(h, x_i) - \sum\limits_{x_i\in S_2} e(h, x_i) ]$$其中$h$表示待评价的假设。显然当$x_i$落入$S_1$时损失函数$e(\cdot)$的系数为1当$x_i$落入 $S_2$时损失函数$e(\cdot)$的系数为-1。如果用随机变量$\sigma_i$对$\pm1$的系数进行建模的话 上面的式子就可以改写称$$ E_{S_1}(h) - E_{S_2}(h) \dfrac{2}{m} [\sum\limits_{i} \sigma_ie(h, x_i)] $$如果把$\sigma_i$看成Rademacher变量那这个式子就是Rademacher复杂度。到这儿就不难理解 Rademacher复杂度的含义了。在已知的数据分布下Rademacher复杂度既可以表示函数空间的复杂 度也可以用来计算泛化误差界其数学细节在这儿就不做介绍了。今天我和你分享了计算学习理论的一些最主要的概念并没有深入数学细节。这是评估机器学习的 理论基础也是机器学习理论研究的主要对象其要点如下Hoeffding不等式描述了训练误差和泛化误差之间的近似关系PAC学习理论的核心在于学习出来的模型会以较大概率接近于最优模型假设空间的VC维是对无限假设空间复杂度的度量体现了复杂性和性能的折中Rademacher复杂度是结合了先验信息的对函数空间复杂度的度量。和各种具体的模型相比计算学习理论充斥着各种各样的抽象推导其内容也显得比较枯燥无味。 那么关于学习理论的研究对解决实际问题到底具有什么样的指导意义呢