模式识别与机器学习第一讲（上）

雷锋网 AI科技评论按，本文作者Frankenstein，首发于知乎专栏闲敲棋子落灯花，雷锋网 AI科技评论获其授权转载。

关键词：有监督学习、无监督学习、强化学习、回归、分类、误差函数、泛化、正则化、超参数、验证集。

序言

从去年5月入坑以来，线上线下都上过机器学习的课（线上是看了Coursera的课入门，线下上了DS-GA 1003 Machine Learning and Computational Statistics），但从没有完整读过一本书。

暑假和小伙伴们约好一起读Pattern Recognition and Machine Learning（模式识别与机器学习，下简称PRML）。初步打算每周读一章，大家轮流主讲。开了专栏以后一直没写过东西，第一部分内容就准备贡献给PRML了。

可能有用的链接：

1. Christopher Bishop at Microsoft Research （https://www.microsoft.com/en-us/research/people/cmbishop/）在这里可以找到部分章节的PPT、书的勘误、部分答案。
   

2. PRML/PRMLT （https://github.com/PRML/PRMLT）陈默（他也上知乎，没关注的可以关注一发）用MATLAB给出了书里的所有模型实现。

3. scikit-learn/scikit-learn （https://github.com/scikit-learn/scikit-learn）视情况我可能会给出少量代码，但大部分内容还是会更加侧重模型的理论和动机，结合适当的数学推导。如果想要了解一些代码的实现的话，scikit-learn应该还是现在最常用的实现，可以考虑学习一下它的模型源代码。
   

书的完整答案理论上是只对教师开放的，但由于大家都可以想见的原因搜一下就可以搜到了。

华盛顿大学的Pedro Domingos教授认为机器学习有以下几个门派：

• 基于逻辑、哲学，出发点为填补现存知识中空白的符号学派

• 基于神经科学，出发点为模拟大脑的联结学派

• 基于进化生物学，出发点为模拟进化的进化学派

• 基于统计，出发点为系统的降低不确定性的贝叶斯学派

• 基于心理学，出发点为发现新旧事物之间相似度的类推学派

在这之外还有基于动物学习、最优控制、动态规划的强化学习以及更加接近传统频率学派的期望最大化。Domingos的slides（https://learning.acm.org/webinar_pdfs/PedroDomingos_FTFML_WebinarSlides.pdf）里有更多这方面的内容。他的《终极算法--机器学习和人工智能如何重塑世界》一书详细科普了五个学派，挺有意思的，感兴趣的可以去看一下（提醒：翻译的不怎么样）。

PRML就是贝叶斯学派的一本经典教科书，从贝叶斯学派的视角系统梳理了机器学习的知识，给人一种万物皆可贝叶斯化的感觉。

在这一系列笔记里，我希望梳理每一章节里比较重要的内容，并结合一些我到目前为止对机器学习的理解做一些适当的拓展和探究。这些内容基本假设读者上过一节机器学习入门课，可能不是self-contained的，可能不适合完全不了解的人阅读，但希望对有一些初步了解的读者能有帮助，也欢迎大家不吝指正。

如无另外点明，每一讲内容都有参考PRML，每一讲其余的参考内容会列在文章末尾。

第一章节（1. Introduction）内容始于多项式曲线拟合的例子，终于信息论。

从机器学习里主流的三类问题——有监督学习、无监督学习、强化学习的定义开始，Bishop用一个有监督学习里的回归问题引出了对误差函数、泛化、模型复杂度、正则化、过拟合、验证集等核心概念。PRML这本书号称是self-contained的，只假设读者具备多元微积分、线性代数水准的数学能力，因此不严格地介绍了概率论里的基本知识以保证读者具备读完余下内容的基础知识。当然还是存在一些小的问题，比如随机变量到底是什么？误差条又是什么？当然瑕不掩瑜，在大部分情况下，本书很好展现了方法和问题的动机。

正文

1. Introduction

机器学习问题可以做如下分类：

1. 有监督学习（supervised learning）: Applications in which the training data comprises examples of the input vectors along with their corresponding target vectors.
   

1. 分类（classification）: to assign each input vector to one of finite number of discrete categories.

1. 例子：识别手写数字并将其标记为0~9这10个数字中的一个。

2. 回归（regression）: the desired output consists of one or more continuous variables.

1. 例子：基于反应物、温度、压力预测化学制造过程的产出。

2. 无监督学习（unsupervised learning）: Pattern recognition problems in which the training data consists of a set of input vectors without any corresponding target values.

1. 聚类（clustering）: to discover groups of similar examples within the data

2. 密度估计（density estimation）: to determine the distribution of data within the input space

3. 降维（dimensionality reduction）: to project the data from a high-dimensional space down to two or three dimensions

4. 数据点/样本生成（data point/sample generation）: to obtain new samples from the probability distribution that is close to the underlying probability distribution of the data points/samples

3. 强化学习（reinforcement learning）: Problems about finding suitable actions to take in a given situation in order to maximize a reward, where optimal outputs are unknown.

1. 例子：Play the game of backgammon to a high standard with a neural network using appropriate reinforcement learning techniques (Tesauro, 1994). (这可能是深度强化学习最早成功的案例之一了。)

2. 上面的案例也可作为credit assignment的一个例子。具体地说，在一局游戏结束后，胜利或失败被以某种形式归因于游戏中采取的所有行动。个人认为这里credit assignment是指在一个episodic task结束后，如何恰当的给特定行动，或者在某个特定状态采取特定行动赋予合适的reward。

3. 这里也有提到explore v.s. exploit和trial and error的思想。但总的来说因为本书基本没怎么触及强化学习，讲的不是特别好。如果要比较好了解强化学习的话还是应该看Sutton & Barto （http://incompleteideas.net/sutton/book/bookdraft2016sep.pdf）那本书。

本章主要介绍了一些最重要的概念和一些简单的例子。在这之中包括将贯穿全书的三个工具：概率论、决策论以及信息论。

1.1 Example: Polynomial Curve Fitting

Example/Motivation: (a simple regression problem)

Given a real-valued target variable t, we wish to use this observation to predict the value of a real-valued target variable t. In particular, given N observations of x written as together with corresponding observations of t written as , can we fit the data so that we can make predictions of the value of the target variable for some new value of the input variable?

这是一个典型的二维回归问题。上过Andrew Ng Coursera 公开课的朋友们应该还记得一上来遇到的那个给定住宅面积预测住宅价格的问题。Bishop这里给的训练数据则是 在 个均匀分布点上的取值加以基于同一高斯分布产生的随机噪声。如下图是 时的情况。

首先我们考虑用一个阶多项式拟合数据，

, (1.1)

是一个关于 的线性方程。

定义：关于未知参数的线性方程被称为线性模型（linear models）。

我们基于训练数据决定的取值，一个潜在的假设是我们需要预测的 和训练数据来自同一分布或两者分布非常接近，否则就没有意义了。

a. 误差函数

怎样的 取值是好的呢？我们需要一把尺子来度量，这就是误差函数（error function）。通过累加每一个训练数据的预测目标变量相对真实目标变量的偏移程度，误差函数负责衡量训练好的模型，即 和训练数据分布之间的相似程度，其取值一般为非负。误差函数的值越大，对于训练数据而言模型越糟。

例子：（平方误差函数）

很自然地，在回归问题中，当模型完美拟合训练数据时，误差一般会降到0。但值得注意的是在分类问题中，即便分类完美无缺误差也可能不为0。

以下图为例，我们有一个二元分类问题。在二维平面上有一个红色类和一个蓝色类。假设我们想用一条直线（在第二讲里我们会提到，它们被称为决策边界）来把它们分开。图中同样①和②都完美进行了分类，但我们会更希望模型训练得到的是①而不是②因为①离两个类最短距离之和要大于②。直觉来说当我们有更多数据样本而不只是眼前6个的时候①成功的可能性更高。这个问题的正式名称是泛化，我们在后面会提到。因此我们可能设计一个误差函数使得②的误差高于①。因此同样①、②在数据上都能没有错误地进行分类，②的误差可能仍然不为0。

训练模型的过程中，我们希望调整 来减少误差函数的值，可以说是面向减少误差建模，故用来表示误差的值。

对于某些误差函数（涉及函数的convexity，凸性），如平方误差，我们可以通过对表达式关于未知参数（如之于）进行求导，令求导后的表达式等于0来得到最优参数,这样得到的参数有闭型（有限次常见运算组合给出的表达式）。

b. 由泛化而来的模型选择问题

现在我们知道了对于一个给定的正整数M，如何拟合训练数据。一个接踵而来的问题是我们要如何决定M的取值。

考虑的四种情况，对于每一种情况，我们都基于平方误差找到拟合训练数据最好的多项式，如下图。红线为多项式图形，绿线为的图形。

由上图可知，越大，多项式拟合数据的能力越强。当时，多项式甚至完美拟合了所有数据。然而我们从形状上可以发现此时多项式的形状与相去甚远。可以预见当我们在上取新的数据点的话，多项式很难较好拟合这些新的数据点。相较之下，时我们得到的多项式形状则相当接近的形状。像时我们得到的模型这样能很好拟合训练数据却对于从同一概率分布得到的新数据拟合能力极差的情况，被称为过拟合。像时这样模型连训练数据都无法很好拟合的情况被称为欠拟合。

回到问题的出发点，我们希望训练出的模型能尽可能学习到数据的原始分布（或者不妨称之为数据的生成器），使得模型能精准预测来自该分布的新数据。模型不光需要在训练数据上有好的表现，在新的数据上也应如此。正确预测新数据标签（即里的）的能力被称为泛化。

由此，我们可以提出一种衡量模型泛化能力的量化方法。除了训练数据外，我们另外取一组测试数据。在知道数据真实分布的情况下（如例子中的），我们直接从数据分布里采集新的数据点。否则我们可以预先把手头的数据集划分成训练数据和测试数据。在训练模型（拟合训练数据）的过程中，拟合仅仅基于训练数据。在训练完后，我们用测试数据检测模型的泛化能力，计算误差函数的数值。

当我们用这一方法应用到多项式模型上时，我们会发现时模型在测试数据上的表现相比时所有模型的表现都要糟糕的多。回到式1.1，当时，考虑标量的话，我们有十个未知参数。当我们有十个线性独立的数据点时，我们可以精确得到每个未知参数的唯一解，因而得到的多项式模型完全依赖于训练数据点。事实上我们应该可以通过插值法得到近乎完全一样（考虑到可能存在数值误差）的多项式。我们注意到时多项式对训练数据的拟合其实已经相当不错了。一个由此而生的想法是在数据拟合改进有限的情况下，我们应该尽可能选择简单的模型，在多项式模型里就是选择尽可能小的。上述原则也可以被概括为“如无必要，勿增实体”，即是著名的奥卡姆剃刀原理。当然不同人对于这个问题可能存在不同看法（https://www.quora.com/Does-Occams-Razor-apply-in-machine-learning）。有人就认为我们在考虑泛化能力的前提下还是要尽可能选择复杂的模型从而尽可能避免关于数据分布信息的丢失。

对于某一特定模型，避免过拟合还有一种方法是使用尽可能多的训练数据。同样在的情况下，当我们取15个数据点乃至100个数据点时，随着训练数据集越来越大，我们曲线拟合的结果也越来越好。

在这100个数据点上，时得到的模型很可能不如来得好。通常数据集越大，我们所能拟合的模型的复杂程度或表示能力越高，因此得到的模型可能更接近于数据的真实分布。一种粗略的机制是训练数据的样本数量应当不小于未知参数数量的某一固定倍数（如5倍或10倍）。值得一提的是未知参数的数量并不能完全衡量模型的复杂度，在第三章我们会接触到更多这方面的内容。

c. 正则化（regularization）

动机：复杂的模型拥有更强的表示能力，有没有可能在无法随意增加数据集的情况下，避免或改善过拟合的问题呢？

回到之前的回归问题，当时，如果我们具体写出拟合得到多项式的系数值的话会发现系数的绝对值非常大。系数越大，模型上下起伏越厉害。而系数越小，模型的形状越平滑。我们希望能在拟合训练数据程度和模型波动程度之间达成一个平衡，并寄希望于这种平衡能在一定程度上反映出模型对于真实数据分布的学习程度。我们引入一种叫正则化的方法。

具体地，我们给原本的误差函数加上一个正则项，令（或者在更一般的情况下我们考虑，预测函数的复杂度）， 决定了正则项的权重，可以看做是一个衡量模型复杂度的函数。最常见的就是范数（-norm），。上述正则化采取的是Tikhonov形式（form），另外一种正则化的形式是Ivanov形式：使得。一般由交叉验证（cross validation）决定。

我们定义Tikhonov形式和Ivanov形式等价，如果：

• , Ivanov解， 使得，对于某些也是一个Tikhonov解：，。
  

• 反过来，，使得与对应的Tikhonov解为一个与对应的Ivanov解。

换言之，两者的解空间相同。

两种形式是否满足上述等价的定义要根据具体的误差函数和模型复杂函数来决定。

范数可能是最常见的正则项了：, （1.4）。值得注意的是通常我们不选择把纳入正则项，因为这会导致结果取决于对目标变量/标签的原点的选择。

加入正则项这样的技巧在统计里被称为收缩（shrinkage），因为他们降低了系数的数值。在神经网络里，这种途径被称为权重下降（weight decay）。

在式1.4中，我们选择了一个二阶正则式。当为平方误差函数时，目标函数为式1.4的回归问题被称为ridge regression。如果我们选择了一个一阶正则项,即 时，代表的回归问题被称为lasso(least absolute shrinkage and selection operator) regression，在3.1.4我们会更深入地学习这个问题。

d.训练集，验证集，测试集

我们往往通过超参数（hyperparameter），一类由我们预先选择而不是模型从数据习得的参数，来决定模型的复杂度（如之前提到的以及）。我们不应该基于测试集（测试数据的集合）来决定模型复杂度，否则模型可能会直接对测试集过拟合，这无异于作弊。同样由于过拟合的考虑，我们也不能基于训练集（训练数据的集合）来选择超参数。我们取一个新的数据集，验证集，来选择模型超参数。当我们知道数据的真实分布时，我们可以直接从分布采集验证集，否则我们可以把手上的数据集分成训练集、验证集或者训练集、验证集、测试集。