当前位置： >>
MOOC台大林轩田老师“机器学习基石”笔记
先简单介绍下这门课程，这门课是在著名的 MOOC（Massive Online Open Course 大型在线公开课）Coursera 上的一门关于机器学习领域的课程，由国立台湾大 学的年轻老师林轩田讲授。这门叫做机器学习基石的课程，共 8 周的课程为整 个机器学习课程的上半部分， 更偏重于理论和思想而非算法，主要分为四大部分 来讲授。 When can Machine Lea
rn？在何时可以使用机器学习？ Why can Machine Learn？ 为什么机器可以学习？ How can Machine Learn？机器可以怎样学习？ How can Machine Learn Better？怎样能使机器学习更好？ 每一大块又分为几周来讲授， 每周的课时分为两个大课，每个大课一般又分为四 个小块来教学，一个小块一般在十分钟到二十分钟之间。 以 VC bound （VC 限制）作为总线将整个基础课程贯通讲解了包括 PLA （Perceptron learning algorithm 感知器）、pocket、二元分类、线性回归 （linear regression）、logistic 回归（logistic regression）等等。 以下不用大课小课来叙述了， 写起来感觉怪怪的，就用章节来分别代表大课时和 小课时。一、The learning problem机器学习问题。1. Course Introduction课程简介。 第一小节的内容就是课程简介，如上已进行了详细的介绍，这里就不多赘述。1.2 What is Machine Learning什么是机器学习？ 在搞清这个问题之前，先要搞清什么是学习。 学习可以是人或者动物通过观察思考获得一定的技巧过程。 而机器学习与之类似，是计算机通过数据和计算获得一定技巧的过程。注意这一对比， 学习是通过观察而机器学习是通过数据 （是计算机的一种观察） 。 对比图如图 1-1。（本笔记的图和公式如不加说明皆是出自林老师的课件，下文 不会对此在做说明）图 1-1 学习与机器学习对比图 a）学习b）机器学习那么紧接着就是要解决上述中出现的一个新的名词&技巧&（skill）。 什么是技巧呢？技巧是一些能力表现的更加出色。 机器学习中的技巧如预测（prediction）、识别（recognition）。 来一个例子： 从股票的数据中获得收益增多的这种技巧，这就是一种机器学习的 例子。 那既然人也可以通过观察获得一个技巧，为什么还需要机器学习呢？ 这就是为什么需要机器学习，简单来说，就是两大原因：一些数据或者信息，人来无法获取，可能是一些人无法识别的事物， 或是数据信息量特别大； 另一个原因是人的处理满足不了需求，比如：定义很多很多的规则满 足物体识别或者其他需求；在短时间内通过大量信息做出判断等等。上面说的是为什么使用机器学习， 那么什么情况下使用机器学习呢？是不是所有 的情况都使用机器学习呢？ 这里给出了三个 ML（机器学习的英文缩写）的关键要素： 1、存在一个模式或者说表现可以让我们对它进行改进提高； 2、规则并不容易那么定义； 3、需要有数据。1.3 Applications of Machine Learning机器学习的应用。 这一小节主要介绍的就是机器学习能用在哪些方面。 个人感觉不是理论介绍的重 点 （不是说应用不重要， 刚好相反， 其实个人认为机器学习甚至整个计算机学 科 最重要的还是应用），就简述下机器学习可以应用在在衣食住行育乐，包含了人 类生活的方方面面，所以机器学习的应用场景很广泛很有市场。1.4 Components of Machine Learning机器学习的组成部分。 这一小节是第一章的重点， 因为它将机器学习的理论应用符号及数学知识进行表 示，而以下各章内容也都是在这小节内容的基础上展开的。 从一个银行是否会发信用卡给用户的例子引出了机器学习可以分为哪几个部分 （组件）。 1.输入(input)：x∈X（代表银行所掌握的用户信息） 2.输出(output)：y∈Y （是否会发信用卡给用户） 3.未知的函数，即目标函数（target function）：f：X→Y（理想的信用卡发放 公式） 4.数据或者叫做资料 （ data） ， 即训练样本 （ training examples） ： D={ （ ( ), …, ( )}（银行的历史记录） ） ,5.假设 （hypothesis） ， 即前面提到的技能，能够具有更好地表现：g： X→Y （能 够学习到的公式） 可以通过一个简单的流程图表示，如图 1-2 所示。图 1-2 机器学习的简单流程图从图中可以清楚机器学习就是从我们未知但是却存在的一个规则或者公式 f 中 得到大量的数据或者说资料（训练样本），在这些资料的基础上得到一个近似于 未知规则 g 的过程。 这么说还是有点抽象， 特别是目标函数 f 又是未知的，那为什么还能找到一个假 设 g 能够接近 f 呢？ 还是以一个更加详细的流程图来说明这一问题，如图 1-3。图 1-3 详细的机器学习流程图这个流程图和图 1-2 有些不同，其中 ML 被更详细的定义为机器学习算法 （learning algorithm）一般用 A 表示。还多出来一个新的项目，就是假设空间 或者叫做假设集合 （hypothesis set） 一般用 H 表示， 它是包含各种各样的假设， 其中包括好的假设和坏的假设， 而这时 A 的作用就体现了，它可以从 H 这个集合 中挑选出它认为最好的假设作为 g。 注： 1、这里还要说明的是机器学习的输入在这个流程图中就变成了两个部分，一个 是训练样本集，而另一个就是假设空间 H。 2、还有一点需要注意的是，我们所说的机器学习模型在这个流程图中也不仅仅 是算法 A，而且还包含了假设空间 H。 3、要求得 g 来近似于未知目标函数 f。 4、给出了机器学习的一个更准确点的定义，就是通过数据来计算得到一个假设 g 使它接近未知目标函数。图 1-3 是还是一个相对比较简单的机器学习流程图， 在往后的章节中会不断的根 据新学的知识继续扩展这幅图的元素。1.5 Machine Learning and Other Fields机器学习与其他各个领域的关系。 1.5.1 ML VS DM （Data Mining） 机器学习与数据挖掘者叫知识发现（KDD Knowledge Discovery in Dataset）。 上一节中已经给出了机器学习的概念，因此只介绍下数据挖掘的概念，就是从大 量的数据中找出有用的信息。 从定义出发，我们可以将两者之间的关系分为 3 种。 1. 两者是一致的： 能够找出的有用信息就是我们要求得的近似目标函数的假 设。 2. 两者是互助的： 能够找出的有用信息就能帮助我们找出近似的假设，反之 也可行。 3. 传统的数据挖掘更关注与从大量的数据中的计算问题。 总的来时，两者密不可分。 1.5.2 M L VS AI （artificial intelligence） 机器学习与人工智能。 人工智能的大概概念就是电脑能够表现出一些智慧行为。 从定义可以得到，机器学习是实现人工智能的一种方式。 1.5.3 ML VS statistic 机器学习与统计。 统计也需要通过数据，来做一个未知的推论。 因此统计是一种实现机器学习的方法。 传统的统计学习更关注与数学公式，而非计算本身。二、Learning to Answer Yes/No二元分类。 解决上一章提出的银行发行信用卡的问题。2.1 Perceptron Hypothesis Set感知器的假设空间。 还是银行发信用卡的例子，银行可能掌握了用户的各种属性，如年龄，年薪，工 作年限，负债情况等等，这些属性可以作为上面提到的样本输入 的向量属性值。但是这样还是无法进行机器学习，因为我们还需要另一个输入， 即假设空间 H。假设空间该如何表示呢？本节提出了一种表示方式，这种学习的 模型称之为感知器（Perceptron）。 其实感知器的产生很早，算是第一代的单层神经网络，这里就不多做介绍，在其 他的读书笔记中进行说明。 这种假设空间的思想就类似考试给的成绩， 对每一题给一个特定的分数， 即权重， 说白了就是给输入向量的每个属性乘以一个加权值 ，在设计一个及格线，即所 谓的阈值或者叫门槛值（threshold），如果加权求和的分数大于这个及格线就 叫及格了，即对应的输出值为 1，小于这个及格线成为不及格，对应的输出值为 -1。 其中 h(x)∈H，如公式 2-1 所示。（公式 2-1） 其中 sign 括号中所包含的内容大于 0 时，取+1；小于 0 时，取-1。 此时可以对 h(x)做一些数学上的简化，注意这仅仅是一种数学表示方式的简化，如公式 2-2 所示。(公式 2-2）如上所示，将阈值的负数表示为权值向量中的一项，用 量 的输入分量则被默认为 1，用 其中 T 表示转置。表示，而对应权值分最终将公式简化为两个向量内积的形式，这里必须说明一个问题，就是不同 h(x) 对应着不同的向量 ，即可以说假设空 间 H 就是向量 的取值范围。 这么描述还是很抽象，因此引入一种方式就是使用图像（或者可以说是几何）来 更形象更具体的来说明以上函数。 （这里说点题外话，由于二元函数和三元函数 可以使用几何图像来一一对应， 用几何的方式更直观的表示函数的意义，方便大 家理解，这在以后的章节中会不断使用） 为了理解的方便将输入向量的维度限制为两个，即 h 函数可以表示成公式 2-3。 (公式 2-3） 将输入向量 对应于一个二维平面上的点（如果向量的维度更高，对应于一个高 维空间中的点）。 输出 y（在分类问题中又称作标签，label）使用○表示+1，×表示-1。 假设 h 对应一条条的直线 （如果在输入向量是高维空间的话，则对应于一个超平 面）这里不止一条，不同的权值 向量对应不同的直线，因为 sign 是以 0 为分 界线的函数，所以可以设 ，该式恰是一条直线的表示。因此每条边的一边为正的，而另一边为表示为负的。 最终得到的图像如图 2-1 所示。图 2-1 感知器在维度为 2 时的几何表示因此这里将感知器作为一条二元线性分类器 （linear ( binary) classifiers） 。2.2 Perceptron Learning Algorithm (PLA)感知器学习算法。 在第一章中， 我们介绍过一个机器学习模型由两部分组成，而上一节仅仅介绍了 它其中的一部分即假设空间 H 如何表示。 本节我们将更详细的介绍感知器的算法 A，即如何从假设空间中找到一个近似未 知目标函数 f 的最好假设 g(x)。 问题是，我们如何找到这个 g(x)呢？ 首先考虑，g(x)和目标函数 f 越接近越好，但问题是我们不知道 f（如果知道了 就不需要学习了） 但是我们知道些什么呢？知道的是样本输入 x 在 f(x)作用下得到的标记 y。 所以如果我们能使得 g(x)在所有的样本输入中都能够得到跟 f 函数作用过输入 得到的输出一样的话，我们认为这时的 g 是不错的。 （在后面的章节还会在这种 思想的基础上更深入的讨论这一问题） 但是问题又来了，假设空间 H 的函数 h(x)有无数种表示，即向量 w 有无数种取 值。 （如在二元输入时，假设空间对于在二维平面上的直线，在那个空间中可以 画出无数条直线） 面对这无数多种情况，我们又该如何求解？我们想到一个简单的方式， 就是一步一步的修正错误的分类，在二维平面中可以 想象成一条初始的直线，在经过不断的纠正它的错误（就是旋转平移之类的）使 得最终的结果可以达到希望的效果。 还要在重复上一节中已经得到的一个结论，在感知器模型中，每一个假设函数 h 都对应一个权值向量 。 因此我们要做的就是不断修正这个权值向量使得最接近 目标函数 f。 下面来详细介绍一下 PLA。 首先我们在设置初始 （注意此处是向量不是向量的分量！），比如设置为 0向量，然后使用训练样本来将权值向量修正的更接近目标函数 f。其修正步骤如 下： 将权值向量的修正次数表示为 t，t=0,1,2,… 在何种情况下需要修正向量 呢？如公式 2-4 所示。(公式 2-4）其中训练样本 标记量。，为在 t 次时使用的输入向量 ，而为在 t 次时的该公式 2-4 的意思就是在 t 次时， 选择的权值向量 ， 有一个训练样本 得在经过 （即 ）假设计算的得到的标签与 f(x)得到的标签不一致。使在这种情况下就需要对权值向量进行修改，使它符合条件。修改的公式如公式 2-5 所示。 （公式 2-5） 从直觉上理解这个公式相对困难，我们还是将它化成一个几何图形，更准确的说 法变成向量加减的形式去理解它，如图 2-2 所示。图 2-2 公式 2-5 的几何解 a) b)图 2-2a 中是在本身标记为+1 时，权值向量和输入向量的内积为负数，对权值向 量略作修改，加上一个标记 y 和输入向量的乘积，得到一个新的权值向量，可以 看出新的权值向量和输入向量的相乘之后符合了标记的要求。 图 2-2b 中是在本身标记为-1 时，权值向量和输入向量的内积为正数，对权值向 量略作修改，加上一个标记 y 和输入向量的乘积，得到一个新的权值向量，可以 看出新的权值向量和输入向量的相乘之后符合了标记的要求。 而非常巧合的是， 只需要乘以一个该训练样本的标记就可以将这两种情况合为一 种情况如公式 2-5 所示。 如此这般的重复查找错误样本和修改加权向量，直到再也找不到可以使公式 2-4 成立的样本为止，此时得到的加权向量，即为我们想要的最终 g。 描述了上面内容之后， 你很可能有一个疑问就如何查找错误样本点，或者如何确 定没有错误的点了。 一个简单的方式就是将训练样本编号，从 1 到 n，整个训练样本就有 n 个点。以 按从 1 到 n 的顺序不断查找错误点， 如果没有错就自动的用下一个样本点继续查 找，当从 1 到 n 这 n 个样本点都没有产生错误时，算法即结束得到 g。将这种方 式的算法叫做 Cyclic PLA。 这时候就又出来几个新的问题， 第一，这个算法一定会找到一个能使所有的样本 都不符合 （即都被分对了类） 的情况吗？就是这个算法会不会停止？第二个问题 这个算法找到的真的是最好的 g 吗？看起来好像只是在训练样本中才符合这一 性质，如果出现新的样本的话又会如何呢？ 第一个问题下一小节将进行介绍，而其他问题会在后面的章节中讨论。2.3 Guarantee of PLAPLA 算法可行的保障。PLA 算法只有在满足训练样本是线性可分（linear separable）的情况下才可以 停止。 什么是线性可分呢？简单的说就是存在一条直线能将两类样本点完全分开。 如图 2-3 所示。图 2-3 线性可分与线性不可分 其中最左边的为线性可分的训练样本， 而右边两个图形为线性不可分的两种情况， 这两种情况会在后面的章节一一解释。 我们需要证明在线性可分的情况下，权值向量在经过一段时间的修正会停止，即 t 次修正会有一个上界。 首先我们考虑是否每次修正都可以使得权值向量 变得更好，就是是否会更接近未知的目标函数所表示的向量。有了这个思路，我们先假设目标函数的权值向 量为 ，可以求解出两个向量相似度的度量方式有很多，其中比较常用的一种 和 做内积。其中 T 表示为停止时方式就是求两个向量的内积，于是我们对 的次数。直接使用这两个向量做内积， 其内积越大并不能代表这两个向量越接近，因为向 量本身的变长也可以导致这一现象。 因此我们需要求解的是这两个向量做归一化 （就是各自除以自身的 L1 范式得到单位向量）之后的内积，这时它俩的内积有 了上界即为 1，如公式 2-6 所示。(公式 2-6）乍一看公式 2-6 完全无从下手，是未知目标向量，是终止时的向量，也是 的可能性不大，一个未知向量，因此思路就是将其中一个未知量消除，消除 因此选择消除在公式中的不确定性，如公式 2-7 所示是解决归一化之前两个向量内积的问题。取所有的样本中 数，所以所有的的最小乘积（因为 必定大于等于 0。）是在线性可分情况下的目标函进行迭代又因为初始值设置为 0 向量，因此(公式 2-7）除了不容易确定之外，的 L1 范式也不容易得出，如公式 2-8 是求解 L1范式的不等式，其思想如公式 2-7。因为只有在犯错的情况下才会进行改变，那什么时候是犯错，就是在公式 2-4 成立的情况，即 ，该公式等价于 ，因此如下（公式 2-8） 通过公式 2-7 和公式 2-8 可以将公式 2-6 写成如公式 2-9，如下式所示。（公式 2-9） 将公式 2-9 中的常数设置为 C，该公式如公式 2-10 所示。(公式 2-10） 可以看出权值向量和目标函数内积会以的速度不断的增长， 但是这种增长不是没 有限制的，它最多只能等于 1。 因此有以下结论，如公式 2-11 所示。（公式 2-11） 求解得到公式 2-12 的结论。（公式 2-12）将公式 2-12 中的值分别使用简单的数字符号代替，如公式 2-13 和公式 2-14 所 示。 （公式 2-13）（公式 2-14） 从公式 2-12 中就可以看出 T 是有上界，即在线性可分的情况下 PLA 算法最终会 停止，找到一个最接近目标函数的假设函数 g。2.4 Non-Separable Data线性不可分的数据。 上一节的阐述 PLA 这个算法一定会停下来这一结论， 是建立在存在一个目标函数， 可以将所有的数据点都线性分开这个假设的基础之上。对于一堆复杂的数 据， 如何能确定它一定是线性可分的？比如一个 PLA 算法运行了很长时间仍然没有 停止， 此时存在两种可能性， 一是该数据集是线性可分的， 但是还没有运行结 束； 另一种， 压根就不存在一条直线可以将数据集分开，就是压根这个算法就不会终 止。假如是后者又该如何处理？ 首先还是要解释下为什么会出现后者，此种情况出现的概率大吗？ 出现不可分的一种可能是从未知目标函数中产生的训练样本存在噪音 （noise） ， 如录入样本时有人工的错误等情况导致数据本身不正确， 使得最终本可以线性可 分的样本集变得线性不可分了，如图 2-4 所示。图 2-4 加入噪音的机器学习流程图而噪音占整个数据集的比例一般不会太大，如图 2-5 所示。这种情况下我们又该 如何计算出最佳的假设 g 呢？图 2-5 存在噪音时线性不可分的情况 其实图 2-5 已经在前面的小节中出现过。 一种新的思路是找出犯错最少的权值向量 ，如公式 2-15 所示。（公式 2-15） 其中表示当满足条件时输出 1，否则为 0。但是这个公式在数学上是 NP 难问题， 我们无法直接求解，于是我们需要找出一种近似的算法来求解这个问题。 这里介绍一个叫 pocket 的算法，它的本质是一种贪心算法，做一简单的介绍： 1. 也是随机的初始化一个权值向量 2. 随机的使用 n 个点中的一个点去发现是否有错误 （此处与 cyclicPLA 使用的循环方式有所不同，不是按顺序一个一个的查看是 否符合条件，而是在 n 个点中随机的抽取，这种方式可以增加 其寻找最优解的速度）3. 和 PLA 一样使用公式 2-5 进行修正. 4. 如果有了修正，则计算出刚刚修正过的权值向量和上一个权值向量到底谁犯的错误比较少，将少的保留重复第 2 步到第 4 步 的动作。假如很长时间都没有新的权值向量比当前的权值向量犯错更少， 则返回该向量作 为函数 g。三、Types of Learning各种类型的机器学习问题。3.1 Learning with Different Output Space不同类型的输出空间。 3.1.1 binary classification 二元分类问题。 前两章中提到的银行发信用卡问题就是一个典型的二元分类问题， 其输出空间只 包含两个标记+1 和-1，分别对应着发卡与不发卡。 当然二元分类问题包含多种情况，如 2.3 节中提到过，如图 3-1 所示。图 3-1 a) 线性可分 b) 线性不可分包含噪音 c) 多项式可分图 3-1a 为线性可分（linear binary separable），如可以使用 PLA 求解；b 是 包含噪音可以使用 pocket 求解，而 c 会在后面章节中详细叙述，属于多项式可 分解。当然解决以上三种 二元分类问题的机器学习方法很多，因为二元分类问 题是机器学习中很重要、核心的问题。3.1.2 Multiclass Classification多元分类。 有二元分类，就不难想到多元分类的问题，该类问题输出标签不止两种，而是 {1,2,…,K}。这在人们的生活中非常常见，比如给水果的图像分类，识别硬币等 等，其主要的应用场景就是模式识别。3.1.3 Regression 回归分析。 该问题的输出空间为整个实数集上或者在一定的实数范围内， 这和前面讲的分类 问题完全不一样，该输出不是一种毫无意义的标记，而是有实际意义的输出值。 比如给定一个大气数据可以推出明天的天气等等之类的问题。 统计学习对该类问 题的研究比较成熟。3.1.4 Structured Learning 结构学习。 当然还有其他更为复杂的问题，比如很多很多类型的分类问题。3.2 Learning with Different Data Label不同的数据标记。 3.2.1 Supervised Learning 监督学习。 知道数据输入的同时还知道数据的标记。 就相当于告诉你题目的同时还告诉你答 案，让你在这种环境下学习，称之为监督学习（supervised learning）或者叫 有师学习（learning with a teacher），之前讨论的一些算法都是这类问题。 举个例子，硬币分类问题，如图 3-2 所示，其中横轴标示硬币的大小，纵轴标示 硬币聚集的堆。图 3-2 有监督的多类别分类问题其中这几种类别的硬币已经被各种不同的颜色所标示好。3.2.2 Unsupervised Learning 无监督学习。 这是一种没有标示（就是没有输出 y）的问题，就是不告诉你题目的正确答案让 你自己去寻找，再以硬币分类为例进行阐述，如图 3-3 所示。图 3-3 无监督的多类别分类问题这种类型的问题最常见的是聚类或者叫分群（clustering），从图中不难看出无 标示的难度比有标示的难度增加不少，而且极有可能犯错，但是这 种问题却拥 有广泛的应用场景（毕竟标示需要花费大量人力物力），如将新闻按照不同的主 题聚类，按用户的属性将用户聚成不同类型的用户群等等。 除了聚类之外还有其他的无监督学习，如密度评估（density estimation）和离 群点检测（outlier detection）等等。3.2.3 Semi-supervised Learning 半监督学习。 是否能在监督式学习和无监督学习之间取一个中庸的方法呢？答案是可以的， 就 是半监督学习，它通过少量有标记的训练点和大量无标记的训练点达到学习的 目的。还是以硬币为例，如图 3-4 所示。这种类型的例子也有很多，比如图像的 识别， 很多情况下我们不可能把每张图片都做上标记（因为做这种标记需要耗费 大 量的人力物力，是一种昂贵的行为），此时，使用半监督学习是一种不错的 选择。图 3-4 半监督学习3.2.4 Reinforcement Learning 强化学习。前面三个是机器学习中最传统的三种方式，除此之外，还有一种方式是通过对一 个行为作出奖励或者惩罚，以此获得的输出，进而进行学习，这种学习方式称之 为强化学习。 一般可以表示为 ，其中向量 还是为输入向量， 表示一种输出，注意 并不一定是最佳输出，最后一项是对输出做出的评判。比如一个广告系统可 以写成如下形式 。3.3 Learning with Different Protocol不同方式获取数据。 对此节的内容进行简单阐述，在不同的协议中可以将机器学习分为三大类： 1. 批量（batch）学习就是将很多数据一次性的给算法进行学习，最常见的方式；2. 在线（online）学习就是一点一点将数据传输进去，如 PLA 和增强学习都适用于这种形式；3. 主动（active）学习是主动提出问题让算法解决，可以节省大量的训练和标记消耗。3.4 Learning with Different Input Space不同的输入空间。 输入又可以称之为特征（features），其主要分为三种：1. 具体特征（Concrete Features），具体特征最大特点就是便于机器学习的处理，也是基础篇中主要讨论的情形。这种情况是人 类或者机器通过一定的方式提取获得的，具有实用性。2. 原始特征（Raw Features），如图片的像素等等，是最为常见到的资料，但是需要经过处理，转换成具体特征，才容易使用， 实用性不太大。3. 抽象特征（Abstract Features），如一些 ID 之类的看似无意义的数据，这就更需要特征的转换、提取等工作（相对于原始特征 而言），几乎没有实用性。四、Feasibility of Learning机器学习的可能性。4.1 Learning is Impossible学习可能是做不到的。 在训练样本集（in-sample）中，可以求得一个最佳的假设 g，该假设最大可能 的接近目标函数 f，但是在训练样本集之外的其他样本（out-of-sample）中， 假设 g 和目标函数 f 可能差别很远。4.2 Probability to the Rescue可能的补救方式。 通过上一小节，我们得到一个结论,机器学习无法求得近似目标函数 f 的假设函 数 g。 回忆在以前学过的知识中， 有无遇到过类似的问题：通过少量的已知样本推论整 个样本集的情况。是否想到一个曾经学过的知识，其实就是概率统计中的知识。 通过一个例子来复习下该知识。 有一个罐子，这个罐子里盛放着橙色和绿色两种 颜色的小球， 我们如何在不查遍所有小球的情况下，得知罐子中橙子小球所占的 比例呢？抽取样本，如图 4-1 所示。图 4-1 抽取样本假设罐子中橙色小球的概率为 ，不难得出绿色小球的概率为 知值； 而通过抽样查出的橙色小球比例为 ，绿色小球的比例为 中计算出的，因此为已知值。 如何通过已知样本 ，求得未知的样本 ？，其中为未， 是从抽样数据可以想象到， 在很大的几率上接近 的结果。因为在罐子里的小球均匀搅拌过 后， 抽出小球中的橙色小球比例很有可能接近整个罐子中橙色小球的比例，不难 想象在抽出的小球数量等于罐中小球数量时，两者完全一致。 这其中不了解的是， 到底有多大的可能性两者接近？此处使用数学的方式给予答 案，如公式 4-1 所示。(公式 4-1）该公式称之为霍夫丁不等式（Hoeffding's Inequality），其中 P 为概率符号， 表示 与 的接近程度， 为此程度的下界，N 表示样本数量，其中不等式左边表示 与 之间相差大于某值时的概率。从该不等式不难得出，随着样本 量的增大， 与 相差较大的概率就不断变小。两者相差越多，即 越大，该概 率越低，就意味着 与 相等的结论大概近似正确（probably approximately correct PAC）。 同时可以得出当 N 足够大时，能够从已知的 推导出未知的 。4.3 Connection to Learning联系到机器学习上。 上一节得出的结论可以扩展到其他应用场景，其中包括机器学习。 为方便理解，做一个对比表，如表 4-1 所示。表 4-1 机器学习与统计中的对比 罐子小球 未知的橙色小球比 例 抽取的小球∈整个 罐子中的小球 橙色小球 绿色小球 小球样本是从罐子 中独立随机抽取的 机器学习 某一确定的假设在整个 X 输入空间中，输入向量 x 满足条 件 的占整个输入空间的比例 整个数据集 X训练输入样本集假设 h 作用于此输入向量 x 与给定的输出不相等 假设 h 作用于此输入向量 x 与给定的输出相等 输入样本 x 是从整个数据集 D 中独立随机选择的更通俗一点的解释上表表达的内容：训练输入样本集类比随机抽取的小球样本； 此样本集中，先确定一个假设函数 h，满足 条件的输入向量 x 占整个样本的比例类比于橙色小球在随机抽取小球样本的比例 ，写成公式的形式可以 入公式 4-2 所示；因此使用上一节中的 PAC（（可能近似正确的理论），在整个输入空间中这个固定的假设函数 h 同目标函数 f 不相等的输入量占整个输入空间 数量的概率 （ 的取值如公式 4-3 所示）与上述随机样本中两个函数不相等 的样本数占抽样数的比例 相同，这一结论也是大概近似正确的。（公式 4-2）（公式 4-3）其中 N 为随机独立抽样的样本数， X 为整个输入空间， E 为取期望值。满足条件为 1 否则为 0，对 1.4 节的机器学习流程图进行扩展，得到如图 4-2 所示。图 4-2 引入统计学知识的机器学习流程图其中虚线表示未知概率 P 对随机抽样以及概率 的影响，实线表示已经随机抽 出的训练样本及某一确定的假设对比例 的影响。 得出的结论如下：对任意已确定的假设函数 h，都可以通过已知的 求出未知的 。以后我们将使用和这种专业的符号，分别表示在某一确定的假设函数 h 中， 随机抽样得到的样本错误率和整个输入空间的错误率，同样可以使用霍 夫丁不等式对以上得到的结论做出相应的数学表达，如公式 4-4 所示。（公式 4-4）但是，我们想得到的不是给定一个已确定的假设函数 h，通过样本的错误比例来 推断出在整个输入空间上的错误概率， 而是在整个输入空间上同目标函数 f 最接 近的假设函数 h。 那如何实现最接近呢？说白了错误率最低。只需在上述结论上再加一个条件，即 错误比例 很小即可。总结下，在 结论基础之上，加上 很小，可以推出也很小，即在整个输入空间中 h≈f。上面说了那么多，可能很多人已经糊涂了，因为这并不是一个学习问题，而是一 个固定假设函数 h，判断该假设函数是否满足上述性质，这准确的讲是一种确认 （Verification），确实如此，这种形式不能称为学习，如图 4-3 所示。图 4-3 确认流程图4.4 Connection to Real Learning联系到真正的学习上。 首先我们要再次确认下我们上一小节确定的概念，要寻找的是一个使得 很小的假设函数 h，这样就可以使得 h 和目标函数 f 在整个输入空间中也很接近。 继续以丢硬币为例，形象的观察这种学习方法有无问题，如图 4-4 所示。图 4-4 丢硬币的例子假设有 150 个人同时丢五次硬币， 统计其中有一个人丢出五次全部正面向上的概 率是多少，不难得出一个人丢出五次正面向上的概率为 丢出全正面向上的概率为 。 ，则 150 人中有一人这其中抛出正面类比于绿色小球的概率也就是。当然从选择的角度肯定要选择犯错最小的， 即正面尽可能多的情况，此例中不难发现存在全部都为正面的 概率是非常大的，此处应注意，选择全为正面的或者说 想得到的结果是 为 0 并不正确（因为 差的太远，而不是 99%）这一结论与真实的情况或者说（我们不仅仅要满足很小条件， 同时还要使得与不能有太大差距） 。因此这种不好的样本的存在得到了很糟糕的结果。 上面介绍了坏的样例（bad sample），把本来很高的 坏抽样样本进行了错误的估计。 到底是什么造成了这种错误， 要深入了解。 我们还需要介绍坏的数据 （bad data） 的概念。 （这里写一下自己的理解，坏的样本 bad sample∈坏的数据 bad data） 坏的数据就是使得 与 相差很大时，抽样到的 N 个输入样本（我的理解不 ，通过一个使得 的是这 N 个输入样本都不好， 可能只是有几个不好的样本，导致该次抽样的数据产 生不好的结果，但此次抽样的数据 集被统一叫做坏的数据），根据霍夫丁不等 式这种情况很少出现，但是并不代表没有，特别是当进行假设函数的选择时，它 的影响会被放大，以下进行一个具体的说 明，如表 4-2 所示。表 4-2 单个假设函数时的霍夫丁不等式 D1 D2 … D1126 … D5678 … h BAD BAD 霍夫丁计算所有不好的 D 出现的概率如公式 4-5 所示。（公式 4-5）单一假设函数中不好的 D 出现的概率其实不算高，但是当在做选择时，面对的是 从整个假设空间选出的无数种可能的假设，因此不好 D 的计算就有所改变，当然 我们先讨论假设函数是有限多种的情况，如表 4-3 所示。表 4-3 M 个假设情况下的霍夫丁不等式 D1 D2 … D1126 … D5678 … 霍夫丁BAD BAD BAD BADBADBADBAD ALL BAD BADBAD BAD ?这其中包含了 M 个假设， 而不好的 D 不是由单一假设就确定的，而是只要有一个 假设在此抽样 D 上表现不好则该抽样被标记为坏的，因此霍夫丁不等式如公式 4-6 所示。(联合上界)(公式 4-6)因此如果|H|=M 的这种有限情况下，抽样样本 N 足够大时，可以确保假设空间 中每个假设都满足 。如果通过算法找出的 g 满足，则通过 PAC 的规则可以保证。五、Training versus Testing训练与测试。5.1 Recap and Preview回顾以及预览。 首先回顾一下上一章学过的内容，学习在何种情况下是可行的。 在可学习的数据来自于一个统一的分布（distribution），且假设空间中的假设 函数为有限个的情况下，其学习流程图如图 5-1 所示。图 5-1 一种可行的学习流程图此图和前几章中的流程图最大的不同是加入了一个模块， 准确的说是一种假设情 况， 假设训练数据样本和未知的测试样本来自同一的分布 （这点尤为重要现有 的 大部分机器学习算法都从这点出发，好像迁移学习不是），并且假设空间的假设 是有限的情况下，即|H| = M，M 是有限的值，在训练样本 N 足够大，假设空间 中的所有的假设都会遵循 PAC 准则，确保 ，每一个假设函数都可以 的假满足近似相等的性质， 因此可以通过算法在这些假设空间中找一个 设， 同样 PAC 也保证了。 因此可以说机器学习在这种情况下是可行的。（训练样本和测试样本满足同分布，假设空间有限，并且训练数据足够大） 接着回顾一下之前四章的内容：第一章介绍了存在一个未知的目标函数 f，机器学习的任务是找出一个假设函数 g，使得假设 g 和目标函数 f 很接近，即 试时的错误率接近零，即 。 ，用第四章的概念可以解释为在测第二章介绍了在训练时使假设函数 g 和目标函数 f 很接近就可以了， 用第四章的 概念可以解释为训练时的错误率接近零，即 。第三章介绍了一种机器学习最基础、最核心的方法：使用批量的数据和监督式的 学习来做二元分类。 第四章介绍了在假设空间不是太多，即假设函数有限的情况下，训练时的错误率 和测试时的错误率很接近，即 。从以上各章节中可以看出将机器学习分为了两个主要问题来解决： 1. 是否能确保是足够接近的？这是连接第一章和第二章的桥梁。2. 如何使得足够小？这是第二章的内容，当然后面的章节还会继续介绍其他的技巧。在第四章中介绍的假设空间的大小 M 与上述两个问题存在何种关系？通过一个 表格进行分析，如表 5-1 所示。表 5-1 M 的大小与两个条件的关系 M 很小的时候 第一个问题 满足， M 小的时候， 两者不相等的几率 变小了 不满足，在 M 变小时，假设的 数量变小，算法的选择变小， 可能无法找到 接近 0 的 M 很大的时候 不满足， M 大的时候， 两者不相等的几率 变大了 满足，在 M 变大时，假设的数 量变大，算法的选择变大，找 到 接近 0 的假设的几率第二个问题假设。变大。显然 M 趋于无穷大时，表现非常不好，如何解决这个问题呢？ 需要寻找一个小于无限大 M 的替代值， 并且这个值还和假设空间有关系， 用 示。以后的几章中讨论如何在 M 为无限大时，保证 。 表5.2 Effective Number of Lines线的有效数量。 第四章的结尾求出了在有限假设空间中 的上限，当时，使用联合上限（union bound），实际不等式的上界被放大了太多。假设在假设空间中包 含无限多的假设函数， 则此上限为无穷大， 而真正合理的上界是不应该大于 1 （因 为是个概率问题，其最大值也不会超过 1）。 造成这一问题的原因是什么呢？很容易想到这个联合上界是不是过于宽松了。 对， 问题确实出在此处，学过集合的同学肯定都知道，两个集合的或集写成两个 集 合相加的形式时，一定要减去它俩的交集。而我们这里的问题出在，这几个集合 不仅相交，而且交集很大，却没有被减掉，因此上界过于宽松。 继续回到假设空间的问题上，两个假设函数出现完全相同坏数据的可能性很大， 如上一章表 4-3 的 h2 和 h3 就出现了几个相同的坏数据。举个简单的例 子，在 二维平面上进行二元线性分类， 假设两条直线 h1 和 h2 很接近，那么就不难得出 两种假设的坏数据也基本重叠，其实这种数据的分布应为图 5-2 所示。图 5-2 不好数据的分布如果可以将这无限大的假设空间分成有限的几类， 按照样本数据划分方式进行分 类， 如是 和 被定义为两种不同的类别。这一思路的原因个人认为有两个： 一是这本身就是一个数据分类错误率的问题，从数据分类方式着手也很切要 害；二是训练样本必然是有限的，分类的方式也是有限的，可以将无限的问题转 换成有限的问题。 先从最简单的分一个样本点着手，假设是一个二元线性分类问题，一个样本的例 子比较容易理解，如图 5-3 所示。图 5-3 单一训练样本分类问题一个样本点分类可以有几种方式？无非两种，该样本为正，或者为负。而假设空 间中的所有假设或者称之为直线，都只能分属于这两种情况。 继续观察两个样本的情况，如图 5-4 所示。图 5-4 两个训练样本分类问题这种情况可以分为如图所示的 4 种情况， 也就是所有的直线可以分属这 4 个类中。 继续观察三个样本的情况，如图 5-5 所示。图 5-5 三个训练样本分类问题出现了 8 种情况，但是如果样本的分布转变一下呢？比如三排成一线，就只有 6 类，如图 5-6 所示。图 5-6 三个训练样本排成一条直线的分类问题继续观察四个样本的情况，如图 5-7 所示。图 5-7 四个训练样本分类问题说明一下此处只画了 8 种情况（其中一种还不可能线性可分），因为直接将其颠 倒就可以得到剩下的 8 种情况，完全是对称的，所示总共有 14 种可以划分的种 类。 不再无休止的继续举例，做一个总结。从上述内容可以看出，将无限多的假设和 有限多的训练数据建立了一种关系，如图 5-为是样本为二维时，二元线性可分 的类型与样本数量的关系图。图 5-7 二元线性可分的类型与样本数量的关系图从图中可以推到出下述公式成立，如公式 5-1 所示。（公式 5-1）其中 N 在大于 3 的情况下， 必然远小于 2 的 N 次方。 其实即使是等于 2 的 N 次方， 也可以说明右边的式子在 N 趋于无穷大的情况下是一个趋近于零的值， 原因很简 单，e 这个自然常数的值大于 2.7 也大于 2，因此右式是个递减函数，此处不做 过多的推导了。5.3 Effective Number of Hypotheses超平面的有效数量。 上一节的内容介绍了，将无限多的假设转换成为有限多种类型上。 这种以训练样本的分类情况来确定一类假设的方式， 称之为二分类 （dichotomy） ， 使用符号表示为 H(x1,x2,…,xN)，即假设空间在特定的训练样本集合 （x1,x2,…,xN）上被分为几类。如表 5-2 所示，对二分类空间与假设空间做出 比较。表 5-2 假设空间与二分空间的对比 假设空间 H 二分 H(x1,x2,…,xN) 举例 在空间中所有的线 {○○×, ○○○, ○××,..} 大小 无限大 上限为以二元线性可分的情况举例， 假设空间是在二维平面上的所有直线，它一定是无 限的； 而二分空间就是能将二维平面上的样本点划分为不同情况的直线种类（不 同情况具体是什么意思，参见上一节），而它最多只是 ，因此是有限的。现在的思路就是使用 H(x1,x2,…,xN)的大小来取代无限大的 M，如何取代呢？ 会发现 H(x1,x2,…,xN)的取值取决于训练样本的分布情况，因此要取消这种依 赖的关系，取消的方式就是寻找在样本点个数固定的情况下最大的 H(x1, x2, …, xN)取值，公式如 5-2 所示。(公式 5-2）符号表示一个比无限大的 M 小且与假设空间 H 有关的关于样本大小 N 的函数。这一函数叫做成长函数（growth function）。 如何具体化 （就是只使用训练样本的大小 N 来表达出该函数）成长函数成为接下 来需要解决的问题。 先从简单的例子着手一步一步的推导到在感知器下该函数的 具体表达。 第一个例子是举一个最简单的情况，在一维实数的情况下，并且限制分类的正方 向指向固定的一边，求解成长函数。给这一分类情况起名叫做正射线（positive rays），如图 5-8 所示。图 5-8 正射线的二元分类用数学的方式表示如下： 1. 输入数据样本为，R 为实数集； ，其中 a 是阈值，表示大1. 其假设空间可以表示为于某个实数 a 数据被分为正类，反之为负类。1. 本质是在一维平面上的感知器，只是比一维感知器少了相反方向可以为正的情况（此种分类已经规定向右的方向为正，而一 维感知器可以规定相反的方向也为正，就比它多了一倍）。正射线分类的成长函数很容易得出，如公式 5-3 所示。（公式 5-3）求出的思路很简单， N 个点两两之间的空隙个数为 N-1， 再加上端点的个数 2 （左 端点是全正，右端点是全负），且可得出在 N 很大的情况下公式 5-4 成立。（公式 5-4）课后题中提到了不规定正方向的情况下成长函数的计算即求在一维情况下感知 器的分类情况，如公式 5-5 所示。（公式 5-5）求解的思路为，在 N 个点上两两之间有 2?(N-1)中可能，因为正方向没有规定 了，所以此处比正射线的种类多出了一倍，剩下样本点都为正类，或者都为负， 这两种情形，因此再加上一个 2。 下一个例子还是在一维空间里， 与正射线分类不同的是，这是一种中间为正两边 为负的情况，叫做中间为正的分类（positive interval），如图 5-9 所示。图 5-9 中间为正的分类其成长函数不难求出，如公式 5-6 所示。(公式 5-6）求解思路如下：此为一个两端都不固定范围的分类（正射线是固定一个端点，直 接到头都为一种类型），因此在 N+1 个空隙中选择两个作为端点（样本两两之间 有 N-1 个空隙，两端还各有一个），因此为一个组合问题 ，但是少算了一种全负情况，即两个端点在同一个空隙之中（是哪个空隙不重要，只要落到一起 即为全负），所以再加 1。 同样在 N 很大时，也小于上限，如公式 5-7 所示。（公式 5-7）接着举一个二维平面上的例子，以凸图形分类为例，在凸区域内部为正，外部为 负，也就是凸区域的边界作为假设函数的划分线，如图 5-10 所示。图 5-10 a) 蓝色部分表示一种凸的图形 b）蓝色部分表示非凸的图形如何求解在这种情形下的成长函数？成长函数是寻找一个最大值的情形， 因此要 取一些极端的情况， 比如所有的点都落在一个圆圈上，用一个凸多边形将所有正 类的样本点连接起来，将此图形稍微的放大一点，得到的凸多边形，其中间的区 域为正，外边的区域为负，如图 5-11 所示。图 5-11 凸多边形分类课程里说到此处就直接给出结果了，如公式 5-8 所示。（公式 5-8）看了很久不知道为啥，想了两种可能的解释，不知道是否正确， 一种是将这个圆圈想象成一条直线， 在这条直线上每个样本点不是根据一个端点 或者两个端点来确定它的正类的范围，而是每个样本都可以为正类，即使它们不 相邻，于是解释就简单了，每个点都可以选择为正类或者负类，就是每个点都有 两种可能的情况，那么 N 个点就可能有 种情况。另外一种想法是直接在二维平面上画图，在这里就阐述一下，以五个样本作为例 子，如图 5-12 所示。图 5-12 五个样本点的凸多边形分类将这五个样本点分成两类的方法一共有多少种（和正射线分类一样，正方向是有 限制的，即多边形内部为正），从最简单两种情况出发，全为正和全为负，其相 加为 2，然后是四个样本为正的情况有多少种（就是图中有多少个凸四边形）， 就是从五个样本中取 4 个的情况有几种， 答案是 就是图中三个样本为正的情况，答案是 画成 2 个样本为正的情况， 答案是 答案是 ，将所有的情况加起来得 ， 推广到 N 中情形， 如公式 5-9 所示。 ， 然后是有多少个三角形，，接着是有多少个直线，将样本点 ， 最后是只有一个样本点为正的情况，（公式 5-9）以上公式可以通过二项式推导出来， 不是凑巧左边的形式正好等于 2 的 N 次方的 形式，二项式的推导如公式 5-10 所示。（公式 5-10）如果 N 个样本点可以写出种类型的假设，即公式 5-8 成立的情况下，我们称 种二分类N 个样本点满足完全二分类情形（shattered），即可以分为 （dichotomy）。5.4 Break Point突破点。 将上一节中列举出来的所有成长函数列在表 5-3 中。表 5-3 各分类的成长函数 正射线 一维空间的感知器 间隔为正的分类 凸图形分类 二维平面的感知器 在某些情况更希望得到一种多项式 （polynomial） 形式的成长函数， 而不是指数 （exponential） 形式的，因为这样上界 的下降速度将会更快。能否找出一种规律将表中二维感知器的成长函数也写成多项式形式的呢？于是提出了一个新 的概念，突破点（break point）。 那什么叫突破点呢？对于三个样本点的感知器， 所有的样本还是满足完全二分类 情形（shattered，也就是还是可以最大化分类的），但是四个样本是却不能满 足完全分类情形（不能满足 种分类了），于是我们称不能满足完全分类情形的样本数量为突破点， 可以想象得出当有更多的样本点时，一定也不能满足完全 分类情形。因此二维感知器成长函数的突破点是 4。在通过一个表 5-4 来说明上 节提到的所有分类情况。表 5-4 各分类的突破点与成长函数的关系 正射线 突破点是 2 一维空间的感知器 突破点是 3 间隔为正的分类 凸图形分类 突破点是 3 没有二维平面的感知器 突破点是 4在某些情况从表中可以看出可能成长函数和突破点之间有一定的关系， 即突破点是 k 的情况 下，成长函数 。（但是这是一个过于宽松的上界，从表 5-4 的第二行可以看出成长函数实际比这个规律要小）六、Theory of Generalization泛化理论（举一反三）。6.1 Restriction of Break Point突破点的限制。 回顾一下上一章中提到的成长函数 的定义：假设空间在 N 个样本点上能产生的最大二分（dichotomy）数量，其中二分是样本点在二元分类情况下的排 列组合。 上一章还介绍了突破点（break point）的概念，即不能满足完全分类情形的样 本点个数，完全二分类情形（shattered）是可分出 的情形。 继续举例说明，假设一种分类情形最小的突破点为 2，即 容易求出在 时，成长函数 ； 。 种二分类（dichotomy）在时，成长函数（突破点是 2），因此最大的二分类个数不可能超过 3，假设为 3。 继续观察 所示。 时的情形， 因理解稍微有些复杂， 还是以图的形式表达， 如图 6-1如图 6-1a)表示在三个样本点时随意选择一种二分的情况，这种分类没有任何问 题，不会违反任意两个样本点出现四种不同的二分类情况（因为突破点是 2）；如图 6-1b)表示在 a)的基础上， 添加不与之前重复的一种二分类，出现了两种不 冲突的二分类， 此时同样也没有任何问题，不会违反任意两个样本点出现四种不 同的二分类情况； 如图 6-1c) 表示在 b)的基础上，再添加不与之前重复的一种二分类，出现了三 种不冲突的二分类， 此时同样也没有任何问题，不会违反任意两个样本点出现四 种不同的二分类情况； 如图 6-1d) 表示在 c)的基础上，再添加不与之前重复的一种二分类，问题出现 了，样本 出现了四种不同的二分情况，和已知条件中 k=2 矛盾（最多只能出现三种二分类），因此将其删去。 如图 6-1e) 表示在 c)的基础上，再添加不与之前重复的一种二分类，此时同样 也没有任何问题，不会违反任意两个样本点出现四种不同的二分类情况； 如图 6-1f) 表示在 e)的基础上，再添加不与之前重复的一种二分类，问题又出 现了， 样本 出现了四种不同的二分情况， 和已知条件中 k=2 的条件不符 （最多只能出现三种二分类），因此将其删去。a) b)c) d)e) f) 图 6-1 样本数为 3 时的二分类情形在突破点是 2，样本点为 3 时，最多只能有四种二分类情况，而。从上述情形，可以做一个猜想，成长函数小于等于某个与突破点 k 有关的二次项，如果可以证明这一结论，即能寻找到一个可以取代无限大 M 的数值， 同理即能公式 4-6 在假设空间为无限大时也是成立，即机器是可以学习的。 假设突破点 ，在样本数为 3 时，最大的二分类个数是多少？答案是 1，可以 想象，在样本为 1 时，只有一种分类情形，假设这种情形是正，则以后所有样本 也为正，才能满足上述条件，所以样本 N 不论为多少，其最大二分类数都是 1。6.2 Bounding Function- Basic Cases上限函数的基本情形。 根据上一小节的例子，提出一个新的概念，上限函数 function），其定义为在最小突破点为 k 时，表示成长函数 （bounding 最大值的函数。 此函数将成长函数从各种假设空间的关系中解放出来，不用再去关心具体的假设，只需了解此假设的突破点，突破点相同的假设视为一类，抽象化成长函数 与假设的关系。 二分类的个数或者称之为成长函数 说白了就是二元（在图中表示为&×&或者&○ &的符号）符号在在长度为 N 的情况下的排列组合（每个不同的排列代 表一个二分类，每种二分类可看做一个向量）个数。 在强调一遍， 提出这种上限函数的好处在于，它的性质可以不用关心到底使用的 是何种假设空间， 只需要知道突破点便可以得到一个上限函数来对成长函数做约 束。 例如： 可以同时表示一维空间的感知器（1D perceptrons）和间隔为正 。注意一维的（positive intervals）的两种假设空间，因为两者都满足成长函数为 ，而间隔为正的成长函数为 ， 一定比这两种情况中最大的还要大，才能约束成长函数，回忆上限函数的定义， 是成长函数 大值&。 想要证明 。 最大值的函数表示，从这个例子中可以理解为何还会出现&最先观察已知的如何表示，通过列表方式找出规律，如图 6-2 所示。图 6-2 已知的取值在的这条斜线上，所有值都等于，这一原因在上一节推导中已经提 的情况，因此在此情况下最大的二到过，原因是突破点代表不能完全二分类 分类数可以是 因此值为 。。在这条斜线的右上角区域所有的点都满足完全二分类的，而在斜线右下角上已给出数值的点都是在上一节中已求出答案的点， 空白地方的 值则是下节需要介绍的内容。6.3 Bounding Function- Inductive Cases上限函数的归纳情形。 这一小节主要是将上一小节空白的内容填写上， 从已有的数据上可以看出一个似 乎是正确的结论：每个值等于它正上方与左上方的值相加。如公式 6-1 所示。（公式 6-1）当然单从观察是无法证明该公式是成立的，以下从结论出发来验证它的正确性。 首先通过计算机求出 的所有二分情况（自己编写程序加上限制条件， 在 16 个二分类中找出符合条件的），其结果如图 6-3 所示。图 6-3的所有二分类图 6-3 中的展示效果还是有些混乱，对这 11 种情况做一次重新排序，将 分开观察，如图 6-4 所示，橙色部分为 出现的二分类，设橙色部分一共 相同的 ，设紫色部分一共 对二分类，即 两两一致、与成对（pair）种二分类；紫色部分为各不种，得公式 6-2。（公式 6-2）图 6-4 以成对和单个的形式展示注意，意味着在样本点为 3 时，不能满足完全二分的情形。需要观察在样 ，于是只本数为 3 时，这 11 种分类会有何变化，不妨假设这三个样本是 剩如图 6-5 所示的 7 种二分类情形。图 6-5 三个样本时缩减之后的二分类其中橙色部分，原本两两成对出现的二分类，在去掉 就合并成了 4 种二分类情况 （ 因为已知所属的那列样本之后， ） 。） ， 紫色部分不变依然为 3 种二分情况 （，在样本数为 3 时，图 6-5 中即表示样本书为 3 的情况，其 一定满足公式 6-3。一定不能满足完全二分，因此 与（公式 6-3）继续观察橙色部分的区域，如图 6-6 所示。图 6-6 三个样本时橙色区域的二分类以下使用反证法证明。假设三个样本在如上图所示的四种二分类情况下， 中任意两列取出， 同之前被删除的满足任意两个样本都可完全二分类。 将列相结合， 一定可得到一种三个样本都满足完全二分类的情形（因为不论是哪两 列与 相结合都会得到 8 种二分类， 每一行二分类都对应两个不同标记的 ， 因 此为 8 种。且两列四行的二分类是全完二分的，在此基础上加上不同属性的列， 应该也不会重复，因此一定也是全完二分的）。但是此结论和已知任意三个样本不 能完全二分冲突了，因此假设不成立，即在图 6-6 中一定存在某两个样本点 不能完全二分的情况，因此得出如公式 6-4 所示的结论。（公式 6-4）由公式 6-2~公式 6-4 推导出公式 6-5。（公式 6-5）最终还能推导出公式 6-6 的通用结论，也就是开始时公式 6-1 的猜想。（公式 6-6）根据这一结论将图 6-2 补齐，如图 6-7 所示。图 6-7 补齐后的上限函数表最后可以通过如下方式证明公式 6-7 是成立的。（公式 6-7）首先需要预先了解组合中的一个定理，如公式 6-8 所示。（公式 6-8）很容易证明情况下公式 6-7 成立，如公式 6-9 所示。（公式 6-9）上一节中已经给出了证明，不仅仅是满足不等号条件，而且满足等号。 再使用数学归纳法证明在 的情况，公式 6-7 成立。假设公式 6-10 成立，则可以得到在 的情况下公式 6-11 成立，同时结合公式 6-6 的结论，公式 6-12 也能被推导出来。（公式 6-10）（公式 6-11）（公式 6-12）这一结果意味着：成长函数的上限函数的上限为。6.4 A Pictorial Proof一种形象化的证明。 在书写这一小节之前，还是想说明一下，我面对这一小节时，看得是一知半解， 因为林老师本身也没打算将这个证明的详细流程全部给出， 我觉得原因有几 个： 一是难度很高，即使全部讲解能听懂的估计也没几个；二是思想更重要，你只需 要知道它用到了什么原理去证明这个问题，这比你了解这枯燥的数学推导更重 要；三是结论比求解过程更重要。当然这不是说求解过程不重要，我会在看懂相 关理论之后， 整理出一个关于 V-C 限制完整证明的笔记，但估计现在也没时间去 看 懂这一理论。 言归正传，开始这一小节的简单阐述。在讲述之前几章时， 一直以为只需要证明出在假设函数为无限多的情况下，寻找 成长函数 作为假设空间个数的上限， 直接使用该上限去取代原本霍夫丁不 接近 0 时， 也接近 0，也就是机器是等式中的 M 便可得出结论，即在可以学习的。实际与这一结果类似，但是稍有偏差，在那本以为的霍夫丁不等式 （如公式 6-13 所示）的公式中多出一些常量。（公式 6-13）先给出结论，公式如 6 -14 所示。（公式 6-14）比较两个公式， 发现最终的结论比猜想的，在不等式的右侧三个不同位置多了三 个常数，分别是开头的地方多了一个 2 倍，成长函数中多了一个 2 倍，指数函数 中多了一个 第一步，用 。按先后循序，分三步简单说明一下这些变化的原因。 取代 。公式 6-15 的说明（不敢叫做证明，目前完全没有头绪，一到三步的说明都是自 己的理解，不正确之处还望指正）。（公式 6-15）其中的可能性是有限多种，因为假设空间的种类被成长函数 种；但是约束住 的可了，而样本的大小又是固定的，所以错误率也最多只有能性还是无限多，因为它的数据是无限大，错误率也自然也会无限多种。为了解 决此问题，提出了一种叫做影子数据的概念（ghost data）。使用跟输入样本一 样多的数据 ，有 ，用这组新的样本取代整个样本去近似求解在无限大 的数据中 的值，求解的近似值记为 。图 6-8 表示 和 的分布情况，其中为它俩的分布中心，假设数据 D 的情况下 再抽取一次数据 半概率，意味着 为从该图中得知 得到的 和 和很大，从图中不难看出， 很大的一很大的几率，最多只有条件很接近的几率最多只有 只可能变得小于 ），即很大这个条件的一半（因 很小的几率最多只有 很大很大这一几率的一半。换句话说很大的几率至少是这一几率的一半，用公式 6-16 表示其含义如下：图 6-8和的分布（公式 6-16）将公式 6-16 稍微调整一下就可以得到公式 6-17。（公式 6-17）从公式 6-17 到公式 6-15 多了一个更强的约束，因此从 变成了 第二步，分解假设空间的种类 其中 的可能性与样本 D 有关，而 与样本。有关，因此整个假设空间的种类可以写成的个数，我们又从之前几章的内容得知，种类的 那，因此坏事情发生的概率如个数并非无限多，其上限最大为成长函数 公式 6-18 所示。（公式 6-18）第三步，使用无取回的霍夫丁。 还是用小球和罐子的那个例子解释，罐子中不再是无限多个小球，而是 2N 个小 球，选择 N 个小球而留下另外 N 个，可以通过公式 6-19 得出如下结论。（公式 6-19）这是一种无放回的霍夫丁，最终得到公式 6-20。（公式 6-20）至此说明了（不敢叫证明）一个在机器学习领域很著名的理论――V-C 上界制 （Vapnik-Chervonenkis bound）。 2 维的感知器，其突破点为 4，因此其成长函数为 ，可以使用这个 VC 上界来说明在样本 N 足够大时候， 发生坏事的情况很少，即选择一个在样本中错误率 很小的 g，可以得出其在整个数据上错误率也很低的结论，说明机器学习是可能 的。七、The VC DimensionVC 维。7.1 Definition of VC DimensionVC 维的定义。 先对上一章的内容作简单总结： 如果一个假设空间存在突破点。则一定存在成长 函数 被某个上限函数 所约束，可求出上限函数等于一个组合的求和形式，易知该形式的最高次项是。图 7-1a)和 b）分别是以上限函数为成长函数上限的情况和以为成长函数上限的情况。图 7-1 a) 以上限函数为上限 b) 以为上限从图中可以看出在且的情况下，满足，得到公式 7-1。（公式 7-1）通过公式 7-1 和上一章的结论可以得出公式 7-2。（公式 7-2）该公式的意义是在输入样本 N 很大时，VC 限制一定成立，同时等式的左边也一 定会在 的情况下被以多项式形式（ ）所约束（注意这里 的条件没 的有了， 原因很简单， VC 限制是样本 N 很大的情况下产生的， 因此一定满足条件），而在 k&3 的情况下有其他的限制可以满足（比如前几章提到的如正射线 之类的分类不需要多项式形式的限制也可以约束住成长函数）。 至此得知，满足以下几个条件，机器便可以学习： 1. 假设空间的成长函数有一个突破点 k （有好的假设空间 H） ；2. 输入数据样本 N 足够的大（有好的输入样本集 D）；1 和 2 通过 VC 限制共同推出了和有很大的可能很接近。1. 一个算法 A 能够找出一个使 足够小的 g（好的算法 A）； 再结合 1 和 2 得出的结论就可以进行学习了（当然这里需要一点好的运气）。 接下来介绍一下这一节的正题， VC 维度或者 VC 维 （VC dimension） 是什么意思。 它的定义和突破点 （break point） 有很大关系， 是最大的一个不是突破点的数。 VC 维是假设空间的一个性质，数据样本可以被完全二分的最大值。用 作为 VC维的数学符号， 假如突破点存在的话， 即最小的突破点减去 1， 如公式 7-3 所示； 如果不存在突破点的话，则 VC 维为无限大。（公式 7-3）如果输入数据量 N 小于 VC 维 不是一定，只能保证存在。，则有可能输入数据 D 会被完全的二分类，这里如果输入数据量 N（或者用 k 表示）大于 VC 维 突破点。 使用 VC 维 对公式 7-1 进行重写，在 且，则有 k 一定是假设空间 H 的时，如公式 7-4 所示。（公式 7-4）对第五章中提到的几种分类， 使用 VC 维取代突破点，表示 VC 维与成长函数的关 系，如表 7-1 所示。表 7-1 VC 维与成长函数的关系 正射线 一维空间的感知器 间隔为正的分类 凸图形分类 二维平面的感知器 在 时对上述条件 1 中好的假设空间重新做一个定义，即有限的 VC 维。一个有限的 VC 维总是能够保证寻找到的近似假设 g 满足 论与下述部分没有关系： 1. 使用的算法 A，即使 2. 输入数据的分布 P； 3. 未知的目标函数 f。，这一结很大，也依然能满足上述的性质；即 VC 维可应对任意的假设空间，任意的数据分布情况，任意的目标函数。 满足这一性质可以得到如图 7-2 所示的流程图， 其中灰色的部分表示上述几个不 会影响 这一结果的部分。图 7-2 由 VC 维保证机器可以学习的流程图7.2 VC Dimension of Perceptrons感知器的 VC 维。 以下两个条件保证了 2 维线性可分的数据是可以学习的。 1. 线性可分的数据通过 PLA 算法运行足够长的时间（T 步骤足够大），则会找出一条可以正确分类的直线，使得样本中没有产 生分错类的情况，即 ；2. 在训练样本和整个数据集都服从同一分布 P 的前提下，有 VC限制保证了，在以上两个条件共同得出且训练样本 N 足够大时，的结论。。这一节讨论的是 PLA 能否处理维数大于二维的数据。 从上一节的内容得知：只要求出 是一个有限数，则可以使用 VC 限制来保证 如何表示。于是问题变成了在维数大于二维时，感知器的 VC 维 （能否表示成一个有限数）。 两种已知感知器的 VC 维表示。 1 维感知器的 VC 维： 。； 2 维感知器的 VC 维：能否以此类推得出 d 维感知器的 VC 维：呢？上述只是一种猜想，接下来是对此猜想进行证明，证明的思路也很传统，证明等 于号的成立分为两步：证明大于等于 以及小于等于 。证明大于等于的思路： 证明存在 d+1 数量的某一数据集可以完全二分；证明小于 等于的思路：证明任何 d+2 数量的数据集都不可以完全二分。 首先证明大于等于。因为只需要证明存在，不妨构造一个输入样本集，假设样本 为一个行向量， 其中第一个样本为 0 向量， 第二个样本是其第一个分量为 1 其 他 分量为 0 的向量， 第三个样本是其第二个分量为 1 其他分量为 0 的向量，以此类 推， 第 d+1 个样本是其第 d 个分量为 1 其他分量为 0 的向量， 如： ， ，…， ，，在感知器中样本 X 如公式 7-5 所乘所示，其中每一个样本加上默认的第 0 个分量，其值为 1（从阈值 b 变成 的样本分量）。（公式 7-5）很容易证明该矩阵式可逆： 除了第一行之外的每一行都减去第一行得到一个对角 矩阵，因此为满秩，可逆。 需要证明的是可以完全二分，关注的重点为输出标记向量 要找出各种权值向量 就可以了。 已知感知器可以使用 定满足 。只能将上述输入样本集 X 映射到全部的二分情况下的 上表示。而只要权值向量使得成立，就一的需求。 假设其中输入矩阵如公式 7-5 所示， 即 X 是可逆矩阵，输出向量 y 的任意一种二分类情况都可以被一个假设函数 w 划分出， 原因是权值 向量 满足 此满 成立。 ，即任何一种二分类情况都会有一个权向量 w 与之对应，因证明小于等于的思路：证明小于等于是不能如上，举一个特殊输入数据集，因为 其要证明在所有的情况下， 证明过程稍微复杂一些，先以一个 2 维空间的例子为 切入点。 假设一个 2 维空间， 则需要观察在 2+2 个输入数据量，不妨假设这四个输入样本 分别是 ， ， ， 。输入数据集 X 如公式 7-6 所示。（公式 7-6）可以想象在标记为-1，与 为+1 时，不可以为-1，如图 7-3 所示。图 7-3 2 维数据样本不可二分的情况用数学的形式如何表达？首先根据这四个样本可以确保公式 7-7 成立。（公式 7-7）该公式等号两边同时左乘权值向量 依旧成立，但在满足 这一条件时，公式左边一定大于 0，如公式 7-8 所示。为-1，与 为+1（公式 7-8）这种样本间线性依赖（linear dependence）的关系导致了无法二分。 那在高维空间结果如何呢？ 假设在 d 维空间中 d+2 个样本，其输入样本集如公式 7-9 所示。（公式 7-9）因为样本间的线性依赖关系， 一定可以得到公式 7-10，其中 系数，该系数可正可负，也可以等于 0，但是不可以全为 0.表示（公式 7-10）此处使用反证法： 设存在一个这样的二分情况， 在公式 7-10 的等号两边左乘权值向量 得公式 7-11。，（公式 7-11）因为 和的第 i 个分量同号（i=1,2,…,d+1），因此左项必然为正，假设不成 。立， 因此在任何 d+2 个输入数据集中必然都存在不能满足的二分类， 即至此大于等于以及小于等于都证明结束，起初的猜想成立。7.3 Physical Intuition of VC DimensionVC 维的直觉。 上一节内容将感知器中数据的维度与 VC 维联系到了一起，也明白了起名时 VC 维中的维的含义。而在感知器中，数据样本的维度又与权值向量的维度一致，不 同的权值向量对应着不同的假设函数，因此称假设函数的参数 是假设空间上的自由度（degree of freedom）。如果从假设空间的数量|H|角度上 描述，则自由度是无限大的；但是从感知器在二元分类上这一限制条件入手，则 可以使用 VC 维作为自由度的衡量。通过之前学习过的两个列子来更具体的看待 VC 维和假设空间参数之间的关系， 如图 7-4 所示。图 7-4 a) 正射线b) 间隔为正的分类其中图 7-4 a） VC 维时， 假设空间有 1 个参数， 即阈值； 图 7-4 b） VC 维 大致时，假设空间有 2 个参数，即左右边界点。因此在大部分情况下，VC 维 等于假设空间参数的个数。5.1 节中提到的两个问题， 本节可以使用 VC 维替代 M，进而描述与这两个问题的 关系，如表 7-1 所示。表 7-1 VC 维的大小与两个条件的关系 很小的时候 第 一 个 满足， 不满足， 很大的时候问 题 小 第 二 个 问 题的时候，不好情况出现的几率变大的时候，不好情况出现的几率 变大了不满足，在变小时，假设的数量满足，在变大时，假设的数量变 接变小，算法的选择变小，可能无法找 到 接近 0 的假设。大，算法的选择变大，找到 近 0 的假设的几率变大。此处写点自己的思考：在一些书中，参数较多的模型都称为复杂模型，很少给出 解释， 这一节的内容给出了很好的解释，因为在很多情况下模型参数的个数大致 等于 VC 维的个数。参数越多或者说模型越复杂，越有可能找出使 最小的假设函数 g， 但是这需要大量训练样本的支持， 因为只有在训练样本数量 N 足够大时， 才能使更复杂 （即参数更多或者说 VC 维更大） 得模型出现不好情况的几率变小， 如上表的右列。7.4 Interpreting VC Dimension解释 VC 维。 VC 限制的公式如 7-12 所示。（公式 7-12）不等式的右边用符号 于 ， 与表示，则好事情发生的几率一定大于等接近程度可以使用含有 的公式表示， 如公式 7-13 所示。(公式 7-13)其中与接近程度，即被称为泛化误差（generalizationerror），通过上式证明该误差小于等于。因此的范围可以用公式 7-14 表示。（公式 7-14）其中最左边的公式一般不去关心，重点是右边的限制，表示错误的上限。又被写成函数， 称为模型复杂度 （model complexity） 。通过一个图表来观察 VC 维到底给出了哪些重要信息，如图 7-5 所示。图 7-5 错误率与 VC 维的关系其中蓝色线表示 变化；紫色部分为随 VC 维的变化；红色部分为模型复杂度 的变化，其中 可以表示用 与随的 表示随 VC 维成的形式。其中 随着的增加而减小，不难理解，因为 ；模型复杂度越大可以选择的假设空间就越 随 的增加而增加也不难大，就有可能选择到更小的理解，从就能得出关系；而因为这前两者的求和， 。使得 最小才是因此出现了一个先降低后增加的过程，使其最小的取值为 学习的最终目的，因此寻找 很重要。VC 维除了表示模型复杂度之外还可以表示样本的复杂度 （sample complexity） 。 假设给定需求 ， ， ，求 N 为多少时，即输入样本多大时才可 ， 与 作以满足这些条件。 我们将 N 的各个数量级代入公式 比较，得到图 7-6。图 7-6 N 的取值与 的关系从图中可以得出在 N 差不多 2 万 9 千时，才可以训练出满足条件的模型，这是一 个很大的数字，即数据的复杂度和 VC 维存在一个理论上的关系， 但在实际应用中，倍数远比这小的多，大概是 。。造成这一现象的原因使自 VC 限制是个非常宽松的约束。宽松的原因主要来自以下四个： 1. 霍夫丁不需要知道未知的，VC 限制可以用于各种分布，各种目标函数；1. 成长函数取代真正的二分类个数本身就是一个宽松的上界，VC 限制可以用于各种数据样本；2. 使用二项式作为成长函数的上界使得约束更加宽松，VC 限 的假设空间；制可以用于任意具有相同 VC 维3. 联合限制（union bound）并不是一定会选择出现不好事情的假设函数，VC 限制可以用于任意算法。其实很难找出在这四个方面都可以任意选择且比 VC 限制约束更紧的限制了，了 解 VC 限制的重点其实也并不是它的约束宽松与否， 而是它给予我们的哲学启示。八、Noise and Error噪音（杂讯）和错误。8.1 Noise and Probabilistic Target噪音（杂讯）和概率目标函数。 这一小节主要讨论有噪音（在 2.4 节提到的）的情况下是否 VC 限制仍可用，其 流程图如图 8-1 所示。图 8-1 含有噪音的机器学习流程图什么是噪音， 或者噪音产生的原因有哪些？仍然举银行发放信用卡的例子，用来 更形象的阐述产生噪音的 3 种原因： 1. 标记 y 中存在的噪音，即错误的标记。如将本应该发放信用卡的用户，错误的标记为不符合规定的用户。2. 标记 y 中存在的另一种噪音，即不同的评判标准评定同一输入样本得到不同结果，如两个用户所有的属性条件都一致，标示 为一个可以发放，而另一个不可以发放。3. 输入样本 x 中存在的噪音，即输入信息不准确，如用户的信息录入错误。回到此节的重点，存在噪音时，VC 限制还能起作用吗？接下来给予一个简单的 推导，不同于前几章，此种情况的 VC 限制完整的重新推导一遍，本节主要提供 的是一种证明思路。 小球罐子的例子再次登场， 之前谈论的没有噪音条件时输入样本和整体样本都服 从同一个概率分布 。 不论是罐子中存在的小球还是抽样出来的小球，其颜色都是固定不变的。此种情况，使用的是确定性（deterministic）的小球。其 中小球的颜色类比 于目标函数 f(x)与假设函数 h(x)是否一致。 标记 y 取决于目 标函数 f，此学习方法叫做判别方法；但是在现实中多数为含有噪音的情况，数 据依然服从统一 的概率分布，但小球颜色并不固定，可以想象为颜色在不停变 色的小球，只能在某一时刻才能确定它的颜色，这种小球可以叫做概率性 （probabilistic）的小球。对应到机器学习上，是含有噪音的样本，即 并不确定，其中标记 y 服从概率分布 ，这一形式被称为目标分布（targetdistribution）而不是目标函数，此方法叫做生成方法。 为何称为目标分布，举一个简单的例子，如一个样本点符合以下公式 8-1。（公式 8-1）则一定会选择错误率小的目标（mini-target），根据此原则该例选择标记为+1 的， 而中 30%几率标记为-1 又是什么意思呢？是噪音。目标函数 f 是一个特殊的 目标分布，其概率符合公式 8-2。（公式 8-2）至此出现了两个分布函数 率越大，和，越大意味着 x 被选为训练样本的概越大意味着该样本是某一类的几率越大，两者结合，即在常见的样本点上分的类尽量正确。 因此得出 VC 限制依然适用， 因为这种含有噪音的输入样本以及标记分别服从 和 ，即 服从 的联合概率分布。了解了本节内容之后，结合噪音和目标分布的概念对机器学习流程图进行修改， 如图 8-2 所示，其中目标函数 f 变成了目标分布 y，同时测试的标记 y 也服从该分布。 ，它产生训练样本的标记图 8-2 结合噪音与目标分布的机器学习流程图8.2 Error Measure错误衡量。 这一小节主要介绍错误的衡量方式对机器学习的影响。以上很多章节都在描述如何使机器学到东西， 即如何使得假设函数 g 和目标函数 f 接近， 即如何使得 尽可能的小。 已知的错误衡量都考虑了哪些问题呢？主要有以下三个因素： 1. 整个样本空间（out-of-sample）：所有未知的样本 x 的平均； 2. 一个点一个点评估(pointwise)：每个点单独评估； 3. 使用分类（classification）的评估方式：，因为是二元分类只有两个类别，因此相同为 0，不同为 1。上述这种分类的错误（classification error）又被叫做 0/1 错误（0/1 error） 可以使用函数 表示逐点的错误衡量（pointwise error measure），因此训练样本的错误衡量及整个样本空间的错误衡量可分别使用公式 8-3 和公式 8-4 表示。（公式 8-3）（公式 8-4）为了表述的简单，又将假设函数表示为，目标函数表示为。除了常用在分类（classification）上的 0/1 错误衡量之外，还有用在回归 （regression） 上的平方错误 （square error） 衡量， 它也是一种逐点 （pointwise） 的错误衡量方式，如公式 8-5 所示。（公式 8-5）给出了两种错误衡量的表达形式，接着讲一下错误衡量和学习之间的关系。错误 衡量对机器学习有着指导作用。 在含有噪音的情况下，目标分布函数 和逐点错误函数 共同决定了理想的错误率最小目标函数（ideal mini-target）f。 目标分布函数 对错误率最小目标函数 f 的影响在上一节中已经阐述过了， 对其的影响。接下来通过一个例子来说明逐点错误函数假设 3 个目标分布函数，，。在 0/1 错误衡量的情况下，不难得出各类错误率，如图 8-3 所示。图 8-3 0/1 错误衡量的情况下各标记的错误率不难得出 y=2 时错误率最低，因此应选择 y=2 的标记，其中有个怪异的标记为 1.9，该标记在 0/1 错误衡量的标准下错误率为 1。 换一种错误衡量方式还是对这些目标分布的错误率进行计算， 如图 8-4 为平方错 误衡量下各标记的错误率。图 8-4 平方错误衡量下各标记的错误率此时错误率最低的标记恰恰是在 0/1 错误衡量中错误率为 1 的标记 1.9，因此使 用平方错误衡量时选择标记 y=1.9。 很容易推出在两种错误衡量下最小目标函数 f 可以分别使用公式 8-6 和公式 8-7 表示。（公式 8-6）（公式 8-7）至此在上一节的基础上对机器学习流图做了进一步的修改，如图 8-5 所示，加入 了错误衡量的模块，该模块对算法和最终的假设选择都起着很大影响。图 8-5 含有错误衡量的机器学习流图8.3 Algorithmic Error Measure算法的错误衡量。 对于二元分类问题错误的类型也分为两类，如图 8-6 所示。图 8-6 分类错误的两种错误类型在目标函数 f 为+1 时， 假设函数 g 却给出了-1， 这种错误叫做错误的拒绝 （false reject），另一种是在目标函数 f 为-1 时，假设函数 g 却给出了+1，这种错误 叫做错误的接受（false accept）。 上一节中提到的 0/1 错误衡量简单的将这两类错误的损失画上了等号， 其实在现 实中这两种错误在不同的场景其损失是不同的。举两个常见的例子， 在超市给年消费额高的会员发放赠品时，如果出现了错误的 接受， 就意味着该会员没有资格领取到赠品， 超市还是给他发放了赠品， 该损 失 只是超市多发了一些赠品； 但如果是错误的拒绝，意味着该会员有资格领取到赠 品， 超市却拒绝给他发放了， 这损失的是超市的信誉， 可能就会因此大批的用户。 另一个例子是在安全部门中， 员工有查看某一资料的权限，系统却拒绝了他的请 求，这是一种错误的拒绝，作为员工，最多也就是抱怨一下，但是如果是一个员 工没 有查看某一资料的权限，系统却同意了，这是一种错误的接受，这个损失 就可能会非常大，甚至有可能威胁到国家的利益。这两种情况的损失可能如图 8-7 所示。图 8-7 a)超市发放赠品的错误损失 b）安全部门的错误损失这两个错误损失也证明了在不同的应用中需要使用不同的错误衡量。 在设计算法时， 最好方式当然按照各种错误损失的情况设计错误衡量，用到算法 中去， 但是最大的问题是错误损失的数值如何确定（如图中这些 10 和 1000 如何 定量的给出）。因此在进行算法设计时，通常采用替代的方式来进行设计，目前 主要有两种替代方式的原则，如下所示： 1. 可以说得通：在分类错误衡量中，可以想象这种噪音的情况相对于整体一定是小的， 因此只需要找到一个足够小的错误即可； 在平方错误衡量中，只要认同噪音服从高斯分布，减小高斯中 平方项，就如同在减少平方错误。将这种近似的错误衡量方式 用 表示。2. 友善的：很容易设计一种算法 A。如寻找最小的 0/1 错误是一个 NP 难问题，而真正在做的算法时，运用错误率比前者更小的原则，即寻找越来越小的错误率。以后的章节中会提到两种 方式： 直接求出结果 （closed-form solution） ； 凸求解方程 （convex objective function）。因为在设计算法时， 很难知道具体的错误衡量， 因此产生了近似的错误衡量 这是本节的重点，在加入了 之后，机器学习的流程图如图 8-8 所示。 ，图 8-8 使用近似错误衡量的机器学习流图8.4 Weighted Classification加权分类。 上一节中提到的如图 8-3 存在的这种错误表示方式，可以称之为成本矩阵（cost matrix）或损失矩阵（loss matrix）再或者错误矩阵（error matrix）。图 8-3 错误矩阵使用如上的错误矩阵分别表示与，如公式 8-8 和公式 8-9 所示。（公式 8-8）（公式 8-9）因为 VC 限制可以在各种算法中起作用，因此在求解已知的算法中只需要使得 尽可能的小，但是这里使用的 和之前的提到的没有加权的 表示为 还是有些区别，为了有所区分，将加权的（weighted） 所示。，公式如 8-10（公式 8-10）假设在一种不是线性可分的情况下 （如果是线性可分一定会产生的情况） ，比如 pocked 算法，先对在这一情况时算法思路进行一个猜想，大部分和原来的 算法一致，即如果 的 比 的更小，则使用 取代原来的 。Pocket 算法可以使用作为错误衡量是被证明了的，但是上述加权的方式却没有被证明，该如何寻找一种保障 pocket 算法在加权错误的情况下，可以使用 类似以上的方式的算法流程呢？ 一个简单的方式是将上述使用 问题等价的问题，如图 8-4 所示。 的原始问题转变成一种使用 且与原始图 8-4 a)使用的原始问题 b) 使用的等价问题等价问题是将原始问题中数据集 D 中标记为-1 的所有数据样本都复制 1000 次， 再将损失矩阵表示不含加权的损失矩阵，而这种损失矩阵正是 pocket 算法使用 的错误衡量方式，唯一的区别，如样本 出错，被复制的其他的 999 个 也跟着一起犯错了，损失相当于是以前的 1000 倍。当然细心的人已经发现了，在算 法做搜寻的过程中碰到标记为-1 的数据样本的几率也增大了 1000。九、Linear Regression线性回归。9.1 Linear Regression Problem线性回归问题。 在第二章中提到的银行发放信用卡问题， 通过是否发放信用卡引出了二元分类问 题；本章再次使用这个例子通过发放用户多大额度的信用卡引出回归 （regression）或者说线性回归（linear regression）的问题。回归问题与二 元分类问题最大的不同在于输出空间，二元分类的输出空间为二元标记，要么+1 要么-1，而回归问题的输出空间 是整个实数空间，即 。以银行发放信用卡为例，输入集合依然是用户的特征空间，如年龄，收入等等， 可以使用与二元分类一致的表示方式 ；因为输出集合的转变导致回归问题的假设函数与二元分类中的有所不同，但思想一致，仍需考虑对每个 输入样本的各个分量进行加权求和，因此最终目标函数 f（含有噪音，使用 y 表 示）的表示如公式 9-1 所示。（公式 9-1）而假设函数的向量表示如公式 9-2 所示。（公式 9-2）从公式 9-2 的表示方式可以看出， 与二元分类假设函数的表示只差了一个取正负 号的函数 sign。 使用图像的方式更形象的描述线性回归，如图 9-1 所示。图 9-1 a) 1 维输入空间的线性回归 b) 2 维空间的线性回归图 9-1a 中表示输入空间为 1 维的线性回归表示，其中圆圈○表示输入样本点， 蓝色直线表示假设函数 ，连接圆圈与蓝色直线之间的红色线段表示样本点到假设函数的距离，称为剩余误差（residuals），在 9-1b 中有类似表示。 而设计算法的核心思想是使总体剩余误差最小。 上一章中也提到过回归使用的错误衡量是平方误差 公式 9-3 所示。 ， 因此 如（公式 9-3）在线性回归问题中，假设函数 h 与权值向量 存在着一一对应的关系，因此公式 9-3 通常表示为权值向量 的形式，如公式 9-4 所示。（公式 9-4）同理表示如公式 9-5 所示，注意这里使用的是含有噪音的形式，因此服从联合概率分布 P。（公式 9-5）VC 限制可以约束各种情况的学习模型，当然回归类型的模型也被也受此约束， 想要学习到知识，只需要寻找 足够小便可以满足 够小的需求。9.2 Linear Regression Algorithm线性回归算法。 此节重点是如何寻找最小的 ，为了表达的简便，将求和公式转化成向量与矩阵的形式，将公式 9-4 转换成公式 9-6 的形式。（为方便显示将向量 w 与向量 x 位置交换，因为是向量内积，符合交换律）（将平方求和转换成矩阵平方的形式）（再拆解成矩阵 X 和向量 w 与向量 y 的形式）(公式 9-6)再回到最初的目标寻找一个最小的，如公式 9-7 所示。（公式 9-7）求解此问题，需要了解左式，其一维（d=1 时）示意图如图 9-2 所示。图 9-2 一维示意图可以看出该函数为连续 （continuous） 、 可微 （differentiable） 的凸 （convex） 函数，其中连续及可微的概念，学过高等 数学的都应该有所了解，凸函数说的 通俗点就如图 9-2 所示， 像一个山谷一样的形式（注意国内数学教材中的凹函数 是这里凸函数的定义，有点澹罢业淖罴 便是山谷中的最低点，对应图中的黑点，以数学的形式表示即梯度（gradient）为 0 的点。（我理解的梯 度，大概意思是某一向量其各个分量的偏导数组成的向量），梯度为的表示方式 如公式 9-8 所示。（公式 9-8）其中 即梯度符号，需要寻找的是，该向量满足，这里 时的的下 。标表示线性 linear 的意思。紧接着的问题是如何求解 继续对公式 9-6 做转化，如公式 9-9 所示。（公式 9-9）其中用矩阵 A 表示，用向量 b 表示，用标量 c 表示，紧接着对求梯度。向量对向量求导数，可能很多人都没有接触甚至没有听说过，最多也就 是了解向量对某标量求导。可通过图 9-3 在 w 为标量情况下的对比形式，理解 求梯度的步骤。图 9-3 a) w 为标量时求的梯度 b) w 为向量时求的梯度线性代数的美妙之处就在于此，如此的相似。因此 的形式。可以写成公式 9-10（公式 9-10）令公式 9-10 求梯度结果为 0，即使 知的情况下，如何求解最佳的假设函数最小。在输入空间 X 与输出向 y 都为已 呢？求解该问题分为两种情况，一是在 可逆的情况下，求解该问题很简单，将公式 9-10 右边的部分设为 0，如 公式 9-11。（公式 9-11）其中表示矩阵 X 的伪逆（pseudo-inverse），注意此处输入矩阵 X 在很少的情况下才是方阵（N=d+1 时）。而这种伪逆矩阵的形式和方阵中的逆矩阵具有很多相似的性质，因此才有此名称。还有一点需要说明， 在大部分的情况下是 可逆的，原因是在进行机器学习时，通常满足 ，即样本数量 N 远远大 于样本的维度 d 加 1， 因此在 中存在足够的自由度使其可以满足可逆的条件。 另一种是 不可逆的情况，实际上可以得到许多满足条件的解，只需要通过其 ，选择其中一个满足 条件的解。他的方式求解出总结下线性回归算法的求解过程，首先通过已知的数据集，构建输入矩阵 X 与输 出向量 y，如公式 9-12 所示。（公式 9-12）通过公式 9-12 直接求得伪逆；在通过公式 9-11 求得假设函数，如公式 9-13 所示。（公式 9-13）9.3 Generalization Issue泛化问题。 本小节讨论的问题理解起来不简单，目前自己还是一知半解，如有表述不正确的 地方还希望指正。 首先要回答一个问题，上一小节中使用到的求解最佳假设函数 能算是机器学习？ 的算法，是否如回答不是，其理由很简单，求解只一步就完成了，不像前面章节中提到的学习 方法需要很多步的过程。实际上，这种求解方式在数学中被称作解析解 （analytical solution）或者叫封闭解或闭式解（closed-form solution）， 此种解是一些严格的公式， 给出任意的自变量就可以求出其因变量，通常与数值 解对应。因此这种求解方式并不像之前提到的 PLA 等算法时 一步一步迭代求出 的 的最小解。回答是的理由更看重结果， 这种直接求解方式是数学推导中的精确解，因此求出 的 一定是 的 最小解，符合求解条件，而且求解伪逆算法（此方法被称为高斯消元法，又见高斯，查了一下一共有 110 项以他名字命名的成果，整个机 器学习笔记中你还会不断 的听到以他命名的成果）并非如公式展示中显示的那 样，一步就可以得出最终结果，而是需要几次的循环迭代（观察了矩阵求伪逆的 程序， 好像是三层循环， 也就印 证了 NG 在他机器学习课程中提到的矩阵求逆的 复杂度为 ），只是被程序封装的看不出迭代的过程而已。而判断是否发生 是否够好！机器学习过程最主要标准是学习到的其实通过改进 VC 限制， 也可以证明在线性回归问题中 VC 起到了很好的约束作用， 即找到了好的 就可以保证 还不错，这里不再证明，因为是件非常繁琐的过程。此处只需要记住 VC 限制不只在二元分类问题中起作用，在线性回归 问题中也发挥着作用。 但是本节使用一种比 VC 限制更容易证明的保证，来说明解析解也可以得到一个 好的 。以下给出证明：为什么解析解求出的 证明与之类似。 首先观察 的平均，用符号的结果是好的。而有关的表示，可写成公式 9-14 所示。（公式 9-14）其中 表示期望，不断的从整体样本空间中抽取样本集，算其平均值， 表示 关于， 表示数据中的噪音，N 为每次抽样的样本数量，d+1 为权值向量 w 的维度。 从上一节中得知，可以将 写成公式 9-15，注意 与 使向量形式。（公式 9-15）其中 I 是的单位矩阵，可以使用的 H 矩阵（hat matrix）表示。此处通过几何图形来更具体的了解 H 矩阵的物理意义，如图 9-4 所示。图 9-4 有关 H 矩阵的几何图形其中紫色向量表示实际输出向量 y。 粉色区域表示输入矩阵 X 乘以不同权值向量 w 所构成的空间，从这个定义得知， 解析解求得最优权值向量 所表示的输出向量 也落在该空间中，其中}