《机器学习》读书笔记

决策树（decision tree）是一类常见的机器学习方法。

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策树结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树的学习目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略。

决策树的生成是一个递归过程。

决策树学习的关键是如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。

4.2.1 信息增益

4.2.2 增益率

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。

决策树剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（postpruning）。

4.3.1 预剪枝

4.3.2 后剪枝

4.4.1 连续值处理

4.4.2 缺失值处理

决策树所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。“多变量决策树”（multivariate decision tree）能实现“斜划分”甚至更复杂划分的决策树。

与传统的“单变量决策树”（univariate decision tree）不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

神经网络（neural networks）是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反映。

神经网络中最基本的成分是神经元（neuron）模型，即上述定义中的“简单单元”。

在“M-P 神经元模型”中，神经元接收到来自 n 个其他神经元传递过来的输入信号，这些输入信号通过带权重的连接进行传递，神经元接收到的总输入值将与神经元的阈值进行比较，然后通过“激活函数”（activation function）处理以产生神经元的输出。

感知机（Perceptron）由两层神经元组成，输入层接收外界输入信号后传递给输出层，输出层是 M-P 神经元，亦称“阈值逻辑单元”（threshold logic unit）。感知机能容易地实现逻辑与、或、非运算。

感知机只有输出层神经元进行激活函数处理，即只拥有一层功能神经元（functional neuron），其学习能力非常有限。

要解决非线性可分问题，需要考虑使用多层功能神经元，输出层与输入层之间的一层神经元被称为隐层或隐含层（hidden layer），隐含层和输出层神经元都是拥有激活函数的功能神经元。

每层神经元与下一层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接，这样的神经网络结构通常称为“多层前馈神经网络”（multi-layer feedforward neural networks），其中输入层神经元接收外界输入，隐含层与输出层神经元对信号进行加工，最终结果由输出层神经元输出。换言之，输入层神经元仅是接受输入，不进行函数处理，隐层与输出层包含功能神经元。

神经网络的学习过程是根据训练数据来调整神经元之间的“连接权”（connection weight）以及每个功能神经元的阈值。换言之，神经网络“学”到的东西蕴含在连接权与阈值中。

误差逆传播（error BackPropagation，简称 BP）算法是迄今最为成功的神经网络学习算法。现实任务中使用神经网络时，大多是在使用 BP 算法进行训练。

BP 算法不仅可用于多层前馈神经网络，还可以用于其他类型的神经网络。但通常说“BP 网络”时，一般是指用 BP 算法训练的多层前馈神经网络。

BP 算法基于梯度下降（gradient descent）策略，以目标的负梯度方向对参数进行调整。

学习率 η∈（0,1）控制着算法每一轮迭代中的更新步长，若太大则容易震荡，太小则收敛速度又会过慢。

BP 算法的目标是要最小化训练集 D 上的累积误差

如何设置隐层神经元的个数仍是个未知问题，实际应用中通常靠“试错法”（trial-by-error）调整。

有两种策略常用来缓解 BP 网络的过拟合，第一种策略是“早停”（early stopping），第二种策略是“正则化”（regularization）。

我们常会谈到两种“最优”：“局部极小”（local minimum）和“全局最小”（global minimum），“全局最小”一定是“局部极小”，反之则不成立。

基于梯度的搜索是使用最为广泛的参数寻优方法。

5.5.1 RBF 网络

5.5.2 ART网络

5.5.3 SOM网络

5.5.4 级联相关网络

5.5.5 Elman 网络

5.5.6 Boltzmann 机

随着云计算、大数据时代的到来，计算能力的大幅提高可缓解训练低效性，训练数据的大幅增加则可降低过拟合风险，因此，以“深度学习”（deep learning）为代表的复杂模型开始受到人们的关注。

典型的深度学习模型就是很深层的神经网络。对神经网络模型而言，提高容量的一个简单方法是增加隐层的数目，模型复杂度也可以通过单纯增加隐层神经元的数目来实现，但没增加隐层数目有效。

无监督逐层训练（unsupervised layer-wise training）是多隐层网络训练的有效手段，其基本思想是每次训练一层隐结点，训练时将上一层隐结点的输出作为输入，而本层隐结点的输出作为下一层隐结点的输入，这称为“预训练”（pre-training）；在预训练全部完成后，再对整个网络进行“微调”（finetuning）训练。

通过多层处理，逐渐将初始的“低层”特征表示转化为“高层”特征表示后，用“简单模型”即可完成复杂的分类等学习任务。由此可将深度学习理解为进行“特征学习”（feature learning）或“表示学习”（representation learning）。

以往在机器学习用于现实任务时，描述样本的特征通常由人类专家来设计，这称为“特征工程”（feature engineering）。众所周知，特征的好坏对泛化性能有至关重要的影响，人类专家设计出好特征也并非易事；特征学习则通过机器学习技术自身来产生好特征，这使机器学习向“全自动数据分析”又前进了一步。

给定训练样本集

分类学习最基本的想法就是基于训练集 D 在样本空间中找到一个划分超平面，将不同类别的样本分开。

在样本空间中，划分超平面可通过如下线性方程来描述：

分支主题

其中

支持向量机（Support Vector Machine，简称SVM)的基本型为：

对支持向量机基本型式子使用拉格朗日乘子法可得到其“对偶问题”（dual problem）。

支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。

现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面，对这样的问题，可将样本从原始空间映射到一个更高维的特征向量，使得样本在这个特征空间内线性可分。如果原始空间是有限集，即属性数有限，那么一定存在一个高维特征空间样本可分。

这里的函数 k（·，·）就是“核函数”（kernel function）。

“核函数选择”称为支持向量机的最大变数。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。

现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性划分，所以就要引出“软间隔”（soft margin）的概念。

软间隔允许某些样本不满足约束

软间隔支持向量机为

软间隔支持向量机的最终模型仅与支持向量有关。

称为“正则化”（regularization）问题，Ω（f）称为正则化项，C称为正则化常数。

支持向量回归（Support Vector Regression，简称SVR）假设我们能容忍 f(x)与 y 之间最多有 Є 的偏差，即仅当 f(x) 与 y 之间的差别绝对值大于 Є 时才计算损失。

人们发展处一系列基于核函数的学习方法，统称为“核方法”（kernel methods）。最常见的是通过“核化”（即引入核函数）来将线性学习器拓展为非线性学习器。

机器学习所研究的主要内容是关于在计算机上从数据中产生“模型”（model）的算法，即“学习算法”（learning algorithm）。可以说机器学习是研究关于“学习算法”的学问。

一组记录的集合称为一个“数据集”（data set），其中每条记录是关于一个事件或对象的描述，称为一个“示例”（instance）或“样本”（sample）。反映事件或对象在某方面的表现或性质的事项，称为“属性”（attribute）或“特征”（feature），属性上的取值称为“属性值”（attribute value），属性张成的空间称为“属性空间”（attribute space）、“样本空间”（sample space）或“输入空间”。

由于空间中的每个点对应一个坐标向量，因此也把一个示例称为一个“特征向量”（feature vector）。每个示例由 d 个属性描述，则 d 称为样本的“维数”（dimensionality）。

从数据中学得模型的过程称为“学习”（learning）或“训练”（training）。训练过程中使用的数据称为“训练数据”（training data），其中每个样本称为一个“训练样本”（training sample），训练样本组成的集合称为“训练集”（training set）。

关于示例结果的信息称为“标记”（label），拥有了标记信息的示例称为“样例”（example），所有标记的集合称为“标记空间”（label space）或“输出空间”。

若预测的是离散值，此类学习任务称为“分类”（classification），如“好瓜”，“坏瓜”；若预测的是连续值，此类学习任务称为“回归”（regression），如西瓜成熟度为0.95,0.37等。

对只涉及两个类别的“二分类”（binary classification）任务，通常称其中一个类为“正类”（positive class），另一个为“反类”（negative class）；涉及多个类别时，则称为“多分类”（multi-class classification）任务。

学得模型后，使用其进行预测的过程称为“测试”（testing），被预测的样本称为“测试样本”（testing sample）。

“聚类”（clustering）有助于我们了解数据的内在规律，能为更深入地分析数据建立基础。

根据训练数据是否拥有标记信息，学习任务可大致分为两大类：“监督学习”（supervised learning）和“无监督学习”（unsupervised learning），分类和回归是前者的代表，而聚类则是后者的代表。

学得模型适用于新样本的能力，称为“泛化”（generalization）能力。

归纳（induction）与演绎（deduction）是科学推理的两大基本手段。前者是从特殊到一般的“泛化”（generalization）过程，即从具体的事实归结出一般性规律；后者则是从一般到特殊的“特化”（specialization）过程，即从基础原理推演出具体状况。

机器学习算法在学习过程中对某种类型假设的偏好，称为“归纳偏好”（inductive bias），或简称为“偏好”。任何一个有效的机器学习算法必有其归纳偏好。

“奥卡姆剃刀”（Occam's razor）是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”。

在具体问题现实问题中，算法的归纳偏好是否与问题本身匹配，大多数时候直接决定了算法能否取得好的性能。

无论学习算法a多聪明、学习算法b多笨拙，它们的期望性能是相同的，这就是“没有免费的午餐”（No Free Lunch Theorem，简称NFL定理）。NFL 定理有一个重要前提：所有“问题”出现的机会相同、或所有问题同等重要，但实际情形并不是这样。NFL 定理最重要的寓意是让我们清楚地认识到，脱离具体问题，空泛地谈论“什么学习算法更好”毫无意义，要谈论算法的相对优劣，必须要针对具体的学习问题。学习算法自身的归纳偏好与问题是否相配，往往会起到决定性的作用。

机器学习是人工智能（artificial intelligence）研究发展到一定阶段的必然产物。

决策树学习技术由于简单易用，到今天仍是最常用的机器学习技术之一。事实上，BP算法一直被应用得罪广泛的机器学习算法之一。

连接主义学习的最大局限性是其“试错性”，简单地说，其学习过程涉及大量参数，而参数的设置缺乏理论指导，主要靠手工“调参”，夸张一点说，参数调节上失之毫厘，学习结果可能谬以千里。

以往机器学习技术在应用中取得好性能，对使用者的要求较高；而深度学习技术涉及的模型复杂度非常高，以至于只要下工夫“调参”，把参数调节好，性能往往就好。因此，深度学习虽然缺乏严格的理论基础，但它显著降低了机器学习应用者的门槛，为机器学习技术走向工程实践带来了便利。

深度学习如今火起来的基本原因有两个：数据大了、计算能力强了。深度学习模型拥有大量参数，若数据样本少，则很容易“过拟合”；如此复杂的模型、如此大的数据样本，若缺乏强力计算设备，根本无法求解。

今天，在技术科学的主动分支学科领域中，无论是多媒体、图形学，还是网络通信、软件工程，乃至体系结构、芯片设计都能找到机器学习技术的身影，尤其是在计算机视觉、自然语言处理等“计算机应用技术”领域，机器学习已成为最重要的技术进步源泉之一。

“计算”的目的往往是数据分析，而数据科学的核心也恰是通过分析数据来获得价值。

若要列出目前计算机科学技术中最活跃、最受瞩目的研究分支，那么机器学习必居其中。

美国国家科学基金会在加州大学伯克利分校启动加强计划，强调要深入研究和整合大数据时代的三个关键技术：机器学习、云计算、众包（crowdsourcing）。

收集、存储、传输、管理大数据的目的是为了“利用”大数据，而如果没有机器学习技术分析数据，则“利用”无从谈起。

通常把分类错误的样本数占样本总数的比例称为“误差率”（error rate），即如果在m个样本中有a个样本分类错误，则错误率E=a/m；相应的1-a/m称为“精度”（accuracy），即“精度=1-错误率”。

学习器的实际预测输出与样本的真实输出之间的差异称为“误差”（error），学习器在训练集上的误差称为“训练误差”（training error）或“经验误差”（empirical error），在新样本上的误差称为“泛化误差”（generalization error）。

当学习器把训练样本学得“太好”的时候，很可能把训练样本自身的一些特点当作了所有潜在样本都具有的一般特性，这样就会导致泛化性能下降，这种现象在机器学习中称为“过拟合”（overfitting），与“过拟合”相对应的是“欠拟合”（underfitting），这是指对训练样本的一般性质尚未学好。

测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未在训练过程中使用过。

2.2.1 留出法

2.2.2 交叉验证法

2.2.3 自助法

2.2.4 调参与最终模型

性能度量（performance measure）是用于衡量模型泛化能力的评价标准。

性能度量反映了任务需求，在对比不同模型的能力时，使用不同的新能度量往往会导致不同的评判结果，这意味着模型的“好坏”是相对的，什么样的模型是好的，不仅取决于算法和数据，还决定于任务需求。

2.3.1 错误率与精度

2.3.2 查准率、查全率与 F1

2.3.3 代价敏感错误率与代价曲线

统计假设检验（hypothesis test）为我们进行学习器性能比较提供了重要依据。

“二项检验”（binomial test）和“t 检验”（t-test）是关于单个学习器泛化性能的假设进行检验，而在现实任务中，更多时候需要对不同学习器的性能进行比较，此时可以使用交叉验证 t 检验、McNemar检验、Friedman检验与Nemenyi后续检验等方法。

“偏差-方差分解”（bias-variance decomposition）是解释学习算法泛化性能的一种重要工具。

泛化误差可分解为偏差、方差与噪声之和。偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力；方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响；噪声则表达了在当前任务上任何学习算法所能达到的预期泛化误差的下界，即刻画了学习问题本身的难度。

偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务为了取得好的泛化性能，则需使用偏差较小，即能够充分拟合数据，并且使方差较小，即使得数据扰动产生的影响小。

线性模型形式简单、易于建模，但却蕴含着机器学习中一些重要的基本思想。许多功能更为强大的非线性模型（nonlinear model）可在线性模型的基础上通过引入层级结构或高维映射而得。并且线性模型有很好的可解释性（comprehensibility）。

“线性回归”（linear regression）可以学得一个线性模型以尽可能准确地预测实值输出标记。

线性回归试图学得

均方误差有非常好的几何意义，它对应 了常用的欧几里得距离或简称“欧氏距离”（Euclidean distance）。基于均方误差最小化来进行模型求解的方法称为“最小二乘法”（least square method）。在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧氏距离之和最小。

“多元线性回归”（multivariate linear regression）

“广义线性模型”（generalized linear model），其中函数g（·）称为“联系函数”（link function）。

对数几率函数（logistic function）为：

“对数几率回归”（logistic regression，亦城logit regression），其对应的函数为：

线性判别分析（Linear Discriminant Analysis，简称LDA）是一种经典的线性学习方法，在二分类问题上因最早由Fisher提出，亦称“Fisher判别分析”。

LDA的思想为：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近，异类样例的投影点尽可能远离。在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别。

LDA也适用于多分类任务，也是常被视为一种经典的监督降维技术。

有些二分类学习方法可直接推广到多分类，但在更多情形下，可以基于一些基本策略，利用二分类学习器来解决多分类问题。

最经典的才分策略有三种：“一对一”（One vs. One，简称OvO）、“一对其余”（One vs. Rest，简称OvR）和“多对多”（Many vs. Many，简称MvM）。

OvO的存储开销和测试时间开销通常比OvR更大，在类别很多时，OvO的训练时间开销通常比OvR更小。至于预测性能，则取决于具体的数据分析，在多数情形下两者差不多。

"纠错输出码"（Error Correcting Output Codes，简称ECOOC）是一种最常用的MvM技术。

一般来说，对同一个学习任务，ECOOC编码越长，纠错能力越强。然而，编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大。

对同等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强。因此，在码长较小时看根据这个原则计算出理论最优编码。

类别不平衡（class-imbalance）就是指分类任务中不同类别的训练样例数目差别很大的情况。

只要分类器的预测几率高于观察几率就应判定为正例，即

“再缩放”（rescaling）策略

再缩放的思想虽简单，但实际操作却不不容易，主要因为“训练集是真实样本总体无偏采样”这个假设往往不成立，也就是说，我们未必能有效地基于训练集观测几率来推断出真实几率。现有技术大体上有三类做法：第一类是直接对训练集里的反类样例进行“欠采样”，即去除一些反例使得正、反例数据接近，然后再进行学习；第二类是对训练集里的正类样例进行“过采样”，即增加一些正例使得正、反例数目接近，然后再进行学习；第三类则是直接基于原始训练集进行学习，但在用训练好的分类器进行与测时，将式（3.48）嵌入到其决策过程中，称为“阈值移动”（threshold-moving）。