第一章 绪论
机器学习的定义
关于“学习算法”的学问。
机器学习的一些基本术语
假设我们收集了一批西瓜的数据，例如：（色泽=青绿;根蒂=蜷缩;敲声=浊响)， (色泽=乌黑;根蒂=稍蜷;敲声=沉闷)， (色泽=浅自;根蒂=硬挺;敲声=清脆)……每对括号内是一个西瓜的记录，定义：
1. 所有记录的集合为：数据集。
2. 每一条记录为：一个实例（instance）或样本（sample）。
3. 色泽或敲声，单个的特点为特征（feature）或属性（attribute）。
4. 对于一条记录，如果在坐标轴上表示，每个西瓜都可以用坐标轴中的一个点表示，一个点也是一个向量，例如（青绿，蜷缩，浊响），即每个西瓜为：一个特征向量（feature vector）。
5. 一个样本的特征数为：维数（dimensionality），该西瓜的例子维数为3，当维数非常大时，也就是现在说的“维数灾难”。
在计算机程序学习经验数据生成算法模型的过程中，每一条记录称为一个“训练样本”，同时在训练好模型后，我们希望使用新的样本来测试模型的效果，则每一个新的样本称为一个“测试样本”。定义：
1. 所有训练样本的集合为：训练集（trainning set），[特殊]。
2. 所有测试样本的集合为：测试集（test set），[一般]。
3. 机器学习出来的模型适用于新样本的能力为：泛化能力（generalization），即从特殊到一般。
在西瓜的例子中，我们预测的是：西瓜是好是坏，即好瓜与差瓜两种，是离散值。同样地，也有通过历年的人口数据，来预测未来的人口数量，人口数量则是连续值。因此我们定义：
1. 预测值为离散值的问题为：分类（classification）。
2. 预测值为连续值的问题为：回归（regression）。
在我们预测西瓜是否是好瓜的过程中，我们事先已经知道了训练集中瓜的好坏，学习器通过学习这些好瓜或差瓜的特征，从而总结出规律，即训练集中的西瓜我们都做了标记，称为标记信息。但也有没有标记信息的情形：我们想将一堆西瓜根据特征分成两个小堆，使得某一堆的西瓜尽可能相似，即都是好瓜或差瓜，对于这种问题，我们事先并不知道西瓜的好坏，样本没有标记信息。因此，我们定义：
1. 训练数据有标记信息的学习任务为：监督学习（supervised learning），容易知道上面所描述的分类和回归都是监督学习的范畴。
2. 训练数据没有标记信息的学习任务为：无监督学习（unsupervised learning），常见的有聚类和关联规则。
模型的评估
所有模型都不是完美的！每种模型都有自己的归纳偏好，只适用于特定情况。要谈论算法的相对优劣，必须要针对具体的学习问题。
第二章 模型评估与选择
误差与过拟合
一般来说，学习器的预测输出和实际真实的输出是有差异的，称为误差。我们定义：
1. 在训练集上的误差称为训练误差（training error）或经验误差（empirical error）。
2. 在测试集上的误差称为测试误差（test error）。
3. 学习器在所有新样本上的误差称为泛化误差（generalization error）。
如果学习器学的太差，对训练样本的一般性质没学好，则称为欠拟合underfitting。相反，如果学的「太好」，把训练样本自身的一些特点当成了所有潜在样本都具有的一般性质，这种情况称为过拟合overfitting。欠拟合比较容易克服，往往因为学习器学习能力太强大导致的过拟合很难处理，实际上过拟合是机器学习面临的关键障碍。首先必须认识到，过拟合无法避免，我们需要做的是降低或者缓解：
机器学习面临的问题通常是NP难或者更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获得最优解，这就意味着我们构造性地证明了P=NP。因此只要相信P≠NP，过拟合就不可避免。
评估方法
通常我们采用一个“测试集”来测试学习器对新样本的判别能力，然后以“测试集”上的“测试误差”作为“泛化误差”的近似。显然：我们选取的测试集应尽可能与训练集互斥。
训练集与测试集的划分方法
一、留出法
将数据集D划分为两个互斥的集合，一个作为训练集S，一个作为测试集T，满足D=S∪T且S∩T=∅，常见的划分为：大约2/3-4/5的样本用作训练，剩下的用作测试。需要注意的是：训练/测试集的划分要尽可能保持数据分布的一致性，以避免由于分布的差异引入额外的偏差，常见的做法是采取分层抽样。同时，由于划分的随机性，单次的留出法结果往往不够稳定，一般要采用若干次随机划分，重复实验取平均值的做法。
二、交叉验证法
将数据集D划分为k个大小相同的互斥子集，满足D=D1∪D2∪…∪Dk，Di∩Dj=∅（i≠j），同样地尽可能保持数据分布的一致性，即采用分层抽样的方法获得这些子集。交叉验证法的思想是：每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集，这样就有K种训练集/测试集划分的情况，从而可进行k次训练和测试，最终返回k次测试结果的均值。交叉验证法也称“k折交叉验证”，k最常用的取值是10，下图给出了10折交叉验证的示意图。
与留出法类似，将数据集D划分为K个子集的过程具有随机性，因此K折交叉验证通常也要重复p次，称为p次k折交叉验证，常见的是10次10折交叉验证，即进行了100次训练/测试。特殊地，当划分的k个子集的每个子集中只有一个样本时，称为“留一法”，显然，留一法的评估结果比较准确，但对计算机的消耗也是巨大的。
三、自助法
我们希望评估的是用整个D训练出的模型。但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比D小，这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小，但计算复杂度又太高了。“自助法”正是解决了这样的问题。自助法的基本思想是：给定包含m个样本的数据集D，每次随机从D 中挑选一个样本，将其拷贝放入D’，然后再将该样本放回初始数据集D 中，使得该样本在下次采样时仍有可能被采到。重复执行m 次，就可以得到了包含m个样本的数据集D’。可以得知在m次采样中，样本始终不被采到的概率取极限为：
这样，通过自助采样，初始样本集D中大约有36.8%的样本没有出现在D’中，于是可以将D’作为训练集，D-D’作为测试集。自助法在数据集较小，难以有效划分训练集/测试集时很有用，但由于自助法产生的数据集（随机抽样）改变了初始数据集的分布，因此引入了估计偏差。在初始数据集足够时，留出法和交叉验证法更加常用。
性能度量
性能度量就是建立衡量模型泛化能力的评价标准。不同的度量标准往往会导致不同的评判结果。因此模型的好坏是相对的，它不仅取决于算法和数据，还取决于任务需求。
回归任务最常用的性能度量是均方误差
E(f;D)=1/m*∑(f(xi)−yi)^2
以下介绍分类任务常用的性能度量。
1. 错误率与精度
2. 查准率precision、查全率recall与F1
3. ROC与AUC
4. 代价敏感错误率与代价曲线
错误率与精度
错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本占样本总数的比例。
查准率、查全率与F1
所谓的查准率P和查全率R分别定义为：
P=TPTP+FP, R=TPTP+FN
变量是分类结果的混淆矩阵confusion matrix，表示为下表：
查准率是在所有预测结果为正例的情况下的真实比例。查全率是所有真实情况为正例的情况下预测正确的比例。
P和R是一对矛盾度量，所以一般会综合两方面考量学习器的好坏，找到最佳平衡点BEP（Break-Even Point）。衡点定义是查全率等于查准率时的取值。
BEP过于简化，更常用的是F1变量，本质上是P和R的调和平均。
1/F1=1/2*(1/P+1/R)
具体应用中可能对P和R有不同的倚重。比如商品推荐中，为了尽可能少打扰用户，更希望推荐内容确是用户感兴趣的，这时候查准率更重要。而在逃犯检索系统中，更希望尽可能少漏掉逃犯，此时查全率更重要。F1度量的一般形式Fβ就可以表达这种偏好。
1/Fβ=1/(1+β^2)(1/P+β^2/R)
也即是Fβ=(1+β^2)PR/(β^2P+R)
当β>1意味着P占比重更大，反之则是R。
ROC与AUC
ROC为受试者工作特征（Receiver Operating Characteristic)曲线，ROC曲线的纵轴是”真正例率“（True Positive Rate），横轴是”假正例率“（False Positive Rate）。AUC是ROC曲线下的面积（Area Under ROC Curve），用来在两个学习器的ROC曲线没有发生交叉时，衡量比较两个学习器的优劣。
更详细的公式、推导和图例请翻看p.33-p.35。
代价敏感错误与代价曲线
不同的错误带来的后果严重程度不一样，因此我们需要为错误赋予一个“非均等代价”（unequal cost）。以二分类为例，我们可根据任务的领域知识设定一个“代价矩阵”（cost matrix）。(p.35 表2.2)
在非均等代价下，ROC曲线不能直接反应出学习器的期望总体代价，而代价曲线则可以达到目的（p.36）
注意！
本书将代价进行了归一化处理，出来的代价曲线也全部是直线。事实上这并不完全正确，归一化处理代价后，代价曲线也可以是曲线。具体的证明写在了p.36页，也可以参考知乎答主对代价曲线的理解：
https://www.zhihu.com/question/63492375
比较检验
机器学习中性能比较这件事情比大家想象的复杂得多，同一个学习方法在同一个测试集上多次运行，其结果都可能不同。而统计假设检验为我们进行学习器性能比较提供了重要依据
简单来说，若在测试集上观察到学习器A比B好，基于假设检验结果则能知道A的泛化性能是否在统计意义上优于B，以及这个结论的把握有多大。
本书列出了四种统计检验方法：假设检验、交叉验证t检验、McNemar检验、Friedman检验与Nemenyi后续检验。
公式图表太多啦，参见p.38~p.44
偏差与方差
通过实验，我们可以估计学习算法的泛化性能，另一方面通过偏差与方差，我们可以了解算法为什么具有这样的性能，偏差-方差分解（bias-variance decomposition）就是用来解释学习算法泛化性能的一种工具，试图拆解期望泛化错误率：
书中对偏差、方差和噪声三个概念进行了定义：
1. 偏差：度量学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力
2. 方差：度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响
3. 噪声：表达了当前任务下任何学习算法所能达到的期望泛化误差的下限，即刻画了学习问题本身的难度
一般来说，偏差与方差是有冲突的，这称为偏差-方差窘境（bias-variance dilemma）。当学习器刚开始学习时，因为学习程度不足，偏差会主导泛化错误率，随着学习器拟合能力逐渐增强，数据集发生的扰动会被学习到，这时方差开始主导泛化错误率。在最后拟合能力非常强的情况下训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合。
第三章 线性模型
基本形式
1. 假定示例有d个属性，x=(x1,x2,...,xd) 2. 试图通过属性的线性组合进行预测
用向量形式表示就是：
线性模型虽然简单，但却是基础。先研究线性、单属性的线性回归问题，便可以进一步研究非线性、多属性的回归和分类问题。本章介绍了几种经典的线性模型，从回归任务开始，然后讨论二分类和多分类问题。
线性回归
根据已有的数据确定一个函数然后预测，怎样衡量函数的准确度呢，均方误差是常用的，几何意义上是求得一条线使得所有的样本到直线的欧式距离之和最小，基于均方误差最小化进行模型求解的方法称为最小二乘法，以单变量为例，求解w和b，有
我们要将均方差最小化，即：
将求解公式等于0可求得w和b的最优封闭解：
多元线性回归的参数求解以同样的思路求解，多参数转为矩阵涉及到矩阵逆的计算，在不满秩的时候经常会出现不止一组解使得均方误差最小；涉及到选择偏好，处理时可加入正则化。也可以使用线性回归的衍生物，即让得到的模型和另外的函数产生关系lny=wx+b，这其实是输入空间到输出的一个非线性预测，对数线性回归。
一般的，考虑单调可微函数g(·),令
这样得到的模型称为广义线性模型（generalizeed linear model）。其中，g(·)成为联系函数（link function）。显然，对数线性回归是广义线性模型在g(·)=ln(·)时的特例。
对数几率回归
线性回归讨论了如何使用线性模型进行回归学习，但若要做的是分类任务该怎么办？式（3.15）可以给我们一个答案：只需找出一个单调可微函数，将分类任务的真实标记y与线性回归模型的预测值联系起来。
考虑二分类任务，其输出标记y属于{0,1}，而线性回归模型产生的预测值z=wTx+b是实值，于是，我们需将实值z转换为0/1值，最理想的是单位介跃函数（unit-step function）
但是单位介跃函数并不连续，因此不能用做g(·)，此时我们希望找到能在一定程度上近似单位介跃函数的替代函数(surrogate function），并希望他单调可微。对数几率函数正是这样一个常用的替代函数：
做一下变换可得：lny/(1−y)=wTx+b。y/1−y含义就是比率，为正例的可能性与为反例的可能性比值。
从本质上讲，对数几率回归模型logistic regression就是在用线性回归模型的预测结果去逼近真实标记的对数几率。
对数几率回归模型虽然还是回归模型，但却是一种分类学习方法。之前普遍翻译为逻辑回归，意义相去甚远，还是用对数几率回归比较符合一些。它的好处在于：
1. 将分类进行建模，无需事先假设数据分布，避免假设分布不准确所带来的问题
2. 不仅分类，还可得到近似概率预测，可利用概率辅助决策
3. 对率函数是任意阶可导的凸函数，可方便求取最优解
确定模型之后，接下来自然要做的就是确定w和b。这里要使用到的方法是极大似然法maximum likelihood method。过程省略，最后我们需要最小化：
上式为关于β的高阶可导连续凸函数，根据凸优化理论，利用经典的数值优化算法如梯度下降法、牛顿法都可求得最优解。
线性判别分析
线性判别分析Linear Discriminant Analysis是一种经典的线性学习方法，应用于分类任务中。
LDA的思想非常简单，将训练集的样本投影到一条直线上，同一类的尽量互相靠近，而不同类之间尽可能相隔的远。使用数学语言，投影即是向量乘积， 同一类尽量靠近，就是协方差要小，不同类相隔远，就是类中心距离远，也就是均值投影的差要大。如图所示：
基于这样的考虑，LDA定义了两个散度矩阵：类内散度矩阵（越小越好） 类间散度矩阵(越大越好)，最后得到了LDA的最大化目标：“广义瑞利商”。
为了确定w的曲直，书中采用了拉格朗日乘子法求解，具体见p.61-p.62。
LDA同样可应用于多分类任务中，方法类似于二分类，具体可见p.62-p.63。
最后补充两点：
1. 从贝叶斯决策理论的角度可以证明LDA在两类数据同先验、满足高斯分布且协方差相等时，LDA可达到最优分类。
2. LDA核心是投影，这样往往实现了降维，因而LDA也常被视为一种经典的监督降维技术。
多分类问题
多分类的问题常常是使用差分策略，通过二分类学习来解决多分类问题，即将多分类问题拆解为多个二分类训练二分类学习器最后通过继承得到结果，最经典拆分策略有三种：“一对一”（OvO）、“一对其余”（OvR）和“多对多”（MvM），核心思想与示意图如下所示：
具体选择哪一种，要看具体情况下的存储和时间开销，以及性能高低。
一对一OvO
假设训练集有四类样本，C1,C2,C3,C4，训练时两两组合为二分类进行训练，新样本通过这C2N个分类器后会得到N(N−1)/2个分类结果，最终结果可根据这些分类结果投票产生。
一对其余OvR
训练时一个类作为正例，其余所有类作为反例。这样共有N个二分类器进行训练，新样本通过分类器时预测结果为正例的即为最终结果。
多对多MvM
本质上讲前两种情况都是MvM的特殊情况。基本思路是训练集每一类通过多个分类器训练会产生一组编码结果，新样本通过分类器产生的编码结果与每个分类器的结果求距离，距离最短者即为最终结果。
这里常用的MvM编码技术是：纠错输出码ECOC Error Correcting Output Codes，其关键在于：
1. 如何划分类别形成二分类训练集，也就是编码
2. 解码，选择如海明距离、欧式距离作为衡量，同时纠错能力强，能容错
类别不平衡问题
类别不平衡就是指分类任务中，不同类别的训练样例数目差别很大的情况。举个很简单的例子，1000个样本，有998个是反例，2个是正例，那么一个对样本永远只预测为反例的学习器也能实现99.8%的正确率，但这种学习器显然是没有用的。
本节假定了正类样例较少，反类样例较多。在现实的分类学习任务中，我们经常会遇到类别不平衡。因此我们必须了解类别不平衡性处理的基本方法。
一个基本策略是再缩放rescaling。
在之前的比率回归问题上，y1−y代表正例可能性与反例可能性的比值，那么如果y/(1−y)>1就可预测为正例。而在类别不平衡的样本中，假设正例数目为m+，反例数目为m−（一般正例数目小于反例数目）。我们可设定学习器的决策条件为：当y/(1−y)>m+/m−即可预测为正例。那么比率即可重改为y′/(1−y′)=[y/(1−y)][m−/m+]。
在实际操作中，再缩放却没那么容易，主要原因是不一定能有效的基于训练集观测几率去推断真实几率。因而往往有三类做法：
1. 欠采样undersampling：去除一些反例数目，使得正例数目接近于反例数目，再进行学习。需要注意，若直接丢弃反例，可能会造成重要信息丢失，一种方法是利用集成学习机制，将反例划分为若干个集合供不同学习器使用，这样每个学习器就相当于欠采样，而全局看则没有丢失重要信息
2. 过采样oversampling：增加正例数目，为防止过拟合，可对训练集正例进行插值产生额外正例，而不是直接重复采样初始正例样本
3. 阈值移动threshold-moving：直接基于原训练集进行学习，但用训练好的分类器进行预测时，将y′/(1−y′)=[y/(1−y)][m−/m+]嵌入决策中
