问题：
II.E Statistical learning 理解不完善。和连接主义关系是？
I. 大师对人工智能和机器学习的看法
从主流为符号机器学习，发展到主流为统计机器学习，反映了机器学习从纯粹的理论研究和模型研究，发展到以解决现实生活中实际问题的应用研究，这是科学研究的一种进步。
但是王珏教授认为，机器学习已经到了一个转折点。从今往后，统计学习应该和知识的利用相结合，这是一种“螺旋式上升，进入更高级的形式”，否则统计学习可能会停留于现状而止步不前。进入转折点的标志就是 Koller 等的《概率图模型》一书的出版。
Chandrasekaran 教授认为，最近几年AI受益于大数据和统计学。但总有一天，AI会转向更加基础的认知科学研究。我们有必要把统计技术和对认知结构的深刻理解结合起来。
II. Introduction
A. What is Machine Learning 什么是机器学习
The name machine learning was coined in 1959 by Arthur Samuel. 他在1952年发明了一个西洋跳棋程序，借助强化学习技术，具备自我学习能力。Samuel 将机器学习定义为 “不显式编程地赋予计算机能力的研究领域”。
Tom M. Mitchell provided a widely quoted, more formal definition of the algorithms studied in the machine learning field:
A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance at tasks in T, as measured by P, improves with experience E.
B. Basic terms 基础术语
对只涉及两个类别的 binary classfication 任务，一个类称为 positive class ，另一类称为 negative class 。
在 clustering 中，“浅色瓜”、“本地瓜”这样的概念我们事先是不知道的，而且学习过程中使用的训练样本通常不拥有 label 信息。
根据 training data 是否具有 label ，学习任务可以大致分为两大类： supervised learning （以分类和回归为代表）和 unsupervised learning （以聚类为代表）。
机器学习的目标是使得习得模型能很好地适用于 unseen instance ，而不是仅仅在训练样本上工作得很好。即使是聚类这样的无监督任务，我们也希望习得的簇划分能在 unseen instance 上适用。这种能力称为 generalization 。
通常假设样本空间中全体样本服从一个未知 distribution \(D\) ，我们获得每个样本都是独立地从这个分布上采样获得的，即 independent and identically distributed (\(i.i.d.\)) 。
一般而言，训练样本越多，我们能得到的关于 \(D\) 的信息越多，这样就越有可能习得具有强泛化能力的模型。
C. Inductive learning & Hypothesis space 归纳学习和假设空间
Induction 和 deduction 是科学推理的两大基本手段：
- Induction: a process of thought that uses known facts to produce general rules or principles.
从特殊到一般的 generalization ，即将具体事实归纳为到一般规律。 - Deduction: the process of using the knowledge or information you have in order to understand something or form an opinion, or the opinion that you form.
从一般到特殊的 specialization ，即从基础原理推导出与之相洽的定理（演绎）。
显然，从 instance 中学习是一个归纳的过程，因此我们又称之为 inductive learning 。
假设我们要通过色泽（青绿、乌黑、浅白、不限）、根蒂和敲声来判断是否为好瓜，那么 hypothesis space 的大小为：\((3+1) \times (3+1) \times (3+1) + 1 = 65\)。最后一个假设是“不存在好瓜”，但由于训练集中有正例，因此该假设不会出现。
比如其中一个假设为：好瓜等价于色泽不限+根蒂蜷缩+敲声浑浊。
在归纳学习的过程中，由于训练样本有限，因此可能会存在多个假设与训练集一致。这些假设组成一个集合，我们称之为 version space 。
D. Inductive bias & NFL 归纳偏置和“天下没有免费的午餐定理”
Version space 为 inductive learning 带来了麻烦。在实际应用中，一个学习算法必须要产生一个具体的模型，即必须产生偏好。
比如，下图是一个回归学习图示。显然存在无数种假设，使得曲线经过训练集中的所有点。
这种 inductive bias ，可以看作是学习算法在一个庞大的假设空间中对假设进行选择的“价值观”。
那么，有没有一种一般性原则，可以引导算法确立“合理的价值观”呢？
有的！
Occam's razor 是其中之一，其基本原则是：选择最简单的那个。如图中的A，比B更平滑。
但要注意的是，判断哪种原则为“简单”，实际上并不简单（P7）。
回到上面的问题。假设白点是测试点，那么左边的情形下A比B好，右边的情形下B比A好。并且，这两种情况都有可能存在。
进一步， No Free Lunch Theorem 定理（P8）告诉我们，当目标函数（希望学习的真实目标函数）均匀存在时，预测误差与算法无关。即无论是什么算法，它们出错的概率都是相同的，不分好坏。
那么随机乱猜也是一种算法呀~~难不成随机猜的效果和我们的优化算法效果一样？
通常不是的。
我们假设函数空间是 \({\{0,1\}}^{|X|}\)，要学习的是二分类器，那么就有可能产生\(2^{|X|}\)种假设。在计算某种假设的测试误差时，我们认为真实函数f是均匀分布（存在）的。
比如，假设1为：好瓜等价于色泽不限+根蒂蜷缩+敲声浑浊，假设2为：好瓜等价于色泽不限+根蒂硬挺+敲声清脆。
在计算任意一个假设带来的误差时，NFL认为，真实函数均匀分布在假设空间中。即：65种好瓜（最后一种是没好瓜）是平等的，因此才会推出假设1和假设2一样好的结论。
但在实际中，（色泽不限+根蒂蜷缩+敲声浑浊的好瓜）比（色泽不限+根蒂硬挺+敲声清脆的好瓜）常见得多，即真实函数并非均匀分布。
因此， NFL 最重要的启示在于：脱离实际讨论算法优劣是没有意义的。学习算法的归纳偏好与实际问题是否匹配，才是最关键的。
E. History
逻辑推理人工智能
二十世纪五十年代到七十年代， artificial intelligence 的研究处于“推理期”。代表作 Logic Theorist 在1963年证明了著名数学家罗素在书中的全部52条定理，作者 Newell 等因此获得1975年图灵奖。
但是人们逐渐意识到，仅仅具有逻辑推理能力，是远远实现不了人工智能的。要使机器拥有智能，就必须设法让机器拥有知识。专家系统
二十世纪七十年代中期，在 Feigenbaum 等人的号召下，人工智能研究进入“知识期”，提倡让机器具有知识，并产生了大量的专家系统。他本人也因此获得1994年图灵奖。
但人们随后也发现，由人教给机器知识是一件相当困难的事情。如果机器能自我学习知识就好了。机器学习
事实上，二十世纪五十年代已有机器学习的研究。在五十年代中后期，基于神经网络的 connectionism 学习开始出现，代表作有 Rosenblatt 的 Perceptron 。
在六七十年代，基于逻辑表示的 symbolism 学习技术蓬勃发展，代表作有 Michalski 等人的“基于逻辑的归纳学习系统”。
以决策理论为基础的学习技术和强化学习技术等也得到发展。
并且，许多统计学习理论的奠基工作也在此时完成。
Feigenbaum 将机器学习划分为：
- 机械学习，即死记硬背式学习，实际上没有进行学习，而只是在进行信息存储与检索。
- 示教学习，从指令中学习。
- 类比学习，通过观察和发现学习。
- 归纳学习，从样例中学习，也即广义的归纳学习，包括有监督、无监督学习，是当今应用最广的技术。
机器学习——归纳学习——符号主义
在二十世纪八十年代，归纳学习的主流是符号主义学习，代表为 decision tree 和基于逻辑的学习。
Decision tree 以信息论为基础，以最小化信息熵为目标，模拟人类对概念进行判定的树形流程；基于逻辑的学习使用一阶逻辑表示知识，通过修改和扩充逻辑表达式来完成对数据的归纳。
前面提到，人工智能的研究经历了推理期和知识期。因此在“学习期”的开始，人们就倾向于符号主义。
Decision tree 简单易用；基于逻辑的学习表示能力非常强，但由于假设空间过大、复杂度过高，在九十年代中后期，其相关研究陷入低谷。机器学习——归纳学习——连接主义
连接主义学习在二十世纪五十年代取得了大发展，但因为当时很多学者对符号主义有偏爱（图灵奖得主 H.Simon 断言 AI 是对智能行为的符号化建模），加上连接主义无法解决异或问题等一系列障碍，导致连接主义不入流。
1983年， Hopfield 等人使用神经网络求解“流动推销员”这一著名的NP难题取得重大进展，使人们重新关注连接主义；
1986年， Rumelhart 等人重新发明了著名的 BP 算法。与符号主义的明确表示不同，连接主义创造的是黑箱。但由于 BP 的出现，使得连接主义方法可以在很多现实问题上发挥作用。Statistical learning
二十世纪九十年代，统计学习闪亮登场并且迅速占据主流，代表技术是 Support Vector Machine 以及更一般的 kernel methods 。
但实际上，早在六七十年代，支持向量的概率就已经提出了。但直到九十年代中期，支持向量机算法才被提出。
事实上，统计学习与连接主义学习有密切的联系，核方法也逐渐成为了机器学习的基础内容之一。连接主义——深度学习
在二十一世纪初，连接主义卷土重来，掀起了名为“深度学习”的热潮。这受益于大数据时代和高算力。
有趣的是，神经网络在二十世纪八十年代中期走红，与当时的 Intel x86 处理器和内存条技术有很大关系。今天深度学习的热潮与彼时的神经网络的走红何其相似。
III. 模型评估与选择
A. Overfitting & Underfitting 过拟合和欠拟合
在简单的分类问题中，我们可以用以下两个互补的指标：
- error rate ：分类错误样本在总样本中的比例。
- accuracy ：\(1-error\ rate\)
更一般地，我们将学习器的实际输出与真实输出之间的差异，称为 error 。
在训练集上的误差，称为 training error 或 empirical error ；在新样本上的误差，称为 generalization error 。后者才是我们真正希望小的。
实际应用中，我们往往先尝试减小训练误差，并尝试得到一个泛化误差也比较小的学习器。
但二者的关系是不定的。为了阐述这一种矛盾，我们定义两种现象：
- overfitting ：学习器把训练样本的一些特点当作所有潜在样本都具有的特点，导致泛化性能下降。
- underfitting ：学习器对训练样本的一般性质尚未掌握。
过拟合最常见的原因是学习能力过强（数据和算法失配，算法更强）。该问题比较棘手，是机器学习面临的关键问题。
欠拟合最常见的原因正好相反，比较好解决，例如在决策树中增加分支等。
要清楚的是，过拟合是无法避免的，只能缓解。因为机器学习面临的问题通常是NP难甚至更难，然而有效的学习算法通常只在多项式时间内完成。
问题来了，既然新样本是 unseen 的，然而我们又希望选择模型的泛化能力足够强，我们该如何评估模型呢？
B. Model selection ( Validation ) 模型选择（验证）
我们希望能在有限的数据集中，划分出训练集和测试集（实际上是验证集 validation set ）。
测试集用于近似估计泛化误差，要注意：
- 与训练集互斥；
- 从样本真实分布中独立同分布采样获得。
Hold-out （按比例划分）
这种方法最简单：将数据集按互斥、互补原则分为两个子集，分别作为训练集和测试集即可。
注意：
- 为了保证独立同分布，在一般问题中，最好能打乱后划分子集；
在分类问题中，应该采取 stratified sampling ，即每一类中划分子集，最后再合并。 - 我们可以多次 hold-out 取均值，得到更可靠的训练结果和泛化误差估计。
- 一般训练集占2/3到4/5，而测试集容量不应小于30。
K-fold cross validation（若数据集足够大）
步骤如下：
- 将数据集 D 划分为 k 个大小相似的互斥子集，每个子集尽可能保持数据的一致性（可采用分层采样法）。
- 每次都将 k-1 个子集的并集作为训练集，余下1个作为测试集。
- 一共有 k 个测试结果，取均值作为最终结果。
最常用的k有5，10和20。
显然，拆分成 k 个互斥子集，有无数种随机的分法。
为了增大随机性，我们可以随机分 p 次。每一次都执行一次完整的 K-fold cross validation ，最后对这 p 次的结果取均值。我们称之为 p 次 k 折交叉验证。
其中存在一种极端情况： Leave-One-Out 。每次都只留出一个作为验证。显然，此时随机分法只有一种，并且训练集能最大程度上接近于 D ，受拆分的影响小。
但当数据集很大时，这种方法显然难以忍受，因为计算量太大了。
bootstrap（若数据集较小）
参见P27。
C. Performance measure 性能度量
回归任务最常用的性能度量是 mean squared error ，分类问题中最常用的是错误率和准确率。
但在有些情况下，这些指标是不够的。
Precision & Recall & \(F1\)
有时，我们更关心预测得准不准，或者预测得全不全。比如预测癌症，我们希望尽量少的病人被漏诊；比如好瓜预测，我们希望尽量少的坏瓜被识别为好瓜。
此时，我们将预测情况分为四类：
- 实际为真，预测为真：真正例 True Positive
- 实际为假，预测为真：假正例 False Positive
- 实际为真，预测为假：假反例 False Negative
- 实际为假，预测为假：真反例 True Negative
这里的 Positive 和 Negative 是预测结果中的正、反例，True 和 False 指的是预测和真实情况相比。
这四种情况的数目组成一个矩阵，称为 confusion matrix ：
接着，我们就可以定义两个度量：
- 查准率 Precision ：预测为真的样本中，实际为真的比例。
\[P = \frac{TP}{TP + FP}\] - 查全率 Recall ：实际为真的样本中，预测为真的比例。
\[R = \frac{TP}{TP + FN}\]
这两个度量往往是矛盾的：
- 如果追求高 precision ，那么我们的 model 会非常谨慎，则 recall 会很低。
- 如果追求高 recall ，那么 model 会非常宽松：当全部预测为真时，\(recall=100\%\)。
通常只有在一些简单任务中，才可能使 precision 和 recall 都较高。
我们可以绘制出 P-R 曲线，如图：
画法是：模型预测正类时，一定会输出一个概率。不断调整正类的概率阈值，就可以得到在不同查全率下的查准率。
如果一个 model 的 P-R 曲线，能完全包住另一个 model 的曲线，那么前者性能更好一些。
但是一般情况下曲线会有交叉。此时我们通过 Break-Even Point 衡量，它是 \(P=R\) 时的值。谁的 BEP 更大，谁就更好。
有时候，BEP 过于简单了，不够好。我们又引入 \(F1\) 度量。 \(F1\) 度量实际上是二者的 harmonic mean ：
\[
\frac{1}{F1} = \frac{1}{2} ( \frac{1}{P} + \frac{1}{R} )
\]
调和平均值与几何平均、算术平均相比，更重视较小值。
有时候，我们对二者中的一者更重视。此时我们可以改用更一般的 \(F_{\beta}\) 度量：
\[
\frac{1}{F_{\beta}} = \frac{1}{1+{\beta}^2} ( \frac{1}{P} + \frac{{\beta}^2}{R} )
\]
显然，\(\beta > 1\)时 \(R\)更重要。
如果我们有多个confusion matrix，我们可以取平均。详细见P32。
与 P-R 异曲同工：ROC & AUC
在选择模型时，除了综合考虑查准率和查全率，我们还可以换一个思路。
ROC 全称为 Receiver Operating Characteristic ，其纵坐标为“正例被预测出来的比例”，横坐标为“反例被预测错的比例”。
其几何意义更清晰，详见P34。曲线包围的面积称为 Aera Under ROC Curve 。绘制方法和 P-R 基本一致。
代价偏好：代价敏感错误率
详见P36。
D. Hypothesis test 比较检验（统计方法比较学习器性能）
在实际操作中，我们往往只是通过上述这些实验评估结果，就完成了学习器的比较。
显然这是不可靠的。为此我们可以引入统计学方法。通过统计学方法我们可以有如下推断：若在测试集观察到A更好，那么A在统计意义上是否更好。
该部分适用于在上一节验证后进行，详见P37。
IV. 线性模型
A. 基础形式
\[
f(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + b
\]
线性模型的 comprehensibility 或 understandability 较强。