一、绪论
1.1引言
1.1.1定义
机器学习是致力于通过计算的手段，利用数据来改善系统自身的性能的学科。
1.1.2研究内容
从数据中产生“模型”的算法（即学习算法）
1.1.3如何运用
有了学习算法，将经验数据传给学习算法后，产生相应模型；在面对新情况时，模型将会给出相应的判断。
1.2基本术语
数据集：一组记录的集合
示例/样本：每条记录
属性：反映事件或对象在某方面的表现或性质的事项。例如每条记录中的“色泽”、“根蒂”、“敲声”就是西瓜的属性
属性空间：属性张成的空间。例如我们把"色泽" "根蒂" "敲声"作为三个坐标轴，则它们张成一个用于描述西瓜的三维空间就是属性空间
特征向量：每个西瓜都可在这个空间中找到自己的坐标位置。由于空间中的每个点对应一个坐标向量，因此我们也把这个坐标向量称为一个特征向量。
将每个属性作为一个坐标轴，多个属性就多个坐标轴，从而形成一个描述物体的属性空间。此空间中的每个样本对应一个点，每个点都有一个坐标向量，把这个坐标向量称为特征向量。
学习/训练：从数据中学得模型的过程
训练数据：训练过程中使用的数据
训练样本：训练过程中使用的每一个样本
训练集：训练样本组成的集合
假设：学得模型对应了关于数据的某种潜在规律
真相/真实：这种潜在规律自身
如果希望学得一个能帮助我们判断没剖开的是不是"好瓜"的模型，仅有前面的示例数据显然是不够的要建立这样的关于"预测" 的模型，我们还需获得训练样本的"结果"信息，例如"((色泽=青绿;根蒂=蜷缩;敲声=浊响)，好瓜)" 。
标记：关于示例结果的信息，比如上面例子中的 "好瓜" 就属于标记。
样例：拥有了标记信息的示例，则称为样例。一般地，用 (xi,yi) 表示第 i 个样例，其中 xi 是特征向量，yi 是这个样本的标记。
标记空间/输出空间：一般的用（xi,yi）表示第i个样例，其中yi∈Y是示例xi的标记，Y是所有标记的集合
根据预测结果的类型，可以将机器学习任务分为二类。
分类：预测结果的类型是离散值，例如"好瓜"，"坏瓜"；
回归：预测结果的类型是连续值，例如西瓜的成熟度0.37、0.95。
学得模型后，使用其进行预测的过程称为测试
测试样本：被预测的样本被称为测试样本
我们还可以对西瓜做聚类
在聚类学习中，“浅色瓜”，“外地瓜”这样的概念我们事先是不知道的，而且学习过程中使用的训练样本通常不拥有标记信息
根据训练数据是否拥有标记信息，学习任务也可大致划分为两大类。
监督学习：训练数据有标记信息，其中分类与回归属于监督学习
无监督学习：训练数据没有标记信息，代表有聚类
机器学习的目标：使得学到的模型能够很好的适用"新样本"
泛化：学得模型适用于新样本的能力
1.3假设空间
1.3.1归纳与假设
归纳：从特殊到一般的“泛化”过程，即从具体的事实归结出一般性规律
假设：从一般到特殊的“特化”过程，即从基础原理推演出具体情况
1.3.2假设空间定义
所有假设构成的集合
1.3.3版本空间
只保留了假设空间中与训练数据集中正例一致的假设，由这些正确的假设构成的集合成为版本空间（简单来说，版本空间就是正例的泛化）。
假设空间大小计算、构建假设空间以及版本空间
举个例子，假设西瓜的好坏由“色泽”，“根蒂”以及“敲声”决定，且"色泽"、"根蒂"和"敲声"分别有3、2、2 种可能取值。
1.3.4假设空间大小
1.3.5假设空间图示
1.3.6训练集
1.4归纳偏好
定义：机器学习算法在学习过程中对某种类型假设的偏好。
任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上"等效"的假设所迷惑，无法产生确定的学习结果。如果没有偏好，刚才那个例子就没有确定的答案了。这样的学习结果显得没有意义。
归纳偏好可以看做学习算法自身在一个可能很庞大的假设空间对假设进行选择的启发式或“价值观”
奥卡姆剃刀：若有多个假设与观察一直，则选择最简单的那个。
1.5发展历程
20世纪80年代，“从样例中学习”的一大主流师符号主义学习，其代表包括决策树和基于逻辑学习。
20世纪90年代中期之前，“从样例中学习”的另一主流技术是基于神经网络的连接主义学习。
20世纪90年代中期, “统计学习（statistical learning）”闪亮登场并迅速占据主流舞台，代表技术是支持向量机（Support Vector Machine,简称SVM）以及更一般的“核方法”（kernel methods）
21世纪初，连接主义卷土重来，掀起了以“深度学习”为名的热潮。深度学习的前身是连接主义学习。
二、模型评估与选择
2.1经验误差与过拟合
错误率：分类错误的样本占样本总数的比例
精度：精度=1-错误率
误差：学习器的实际预测输出与样本的真实输出之间的差异
训练误差/经验误差：学习器在训练集上的误差
泛化误差：学习器在新样本上的误差
过拟合：学习器把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，导致泛化性能下降
形成原因：由于学习能力过于强大，以至于把训练样本所包含的不太一般的特性都学到了
欠拟合：学习器对训练样本的一般性质尚未学好
形成原因：由于学习能力低下造成的
模型选择：
理想的解决方案是对候选模型的泛化误差进行评估，然后选择泛化误差最小的那个模型
2.2评估方法
测试集：测试学习器对新样本的判别能力
测试误差：已测试集上的测试误差作为泛化误差的近似
如果我们还有一个包含m个样例的数据集D={(x1,y1),(x2,y2),...,(xm,ym)}，既要训练，又要测试，就需要通过对D进行适当的处理，从中产生出训练集S和测试集T。
留出法（hold-out）：
直接将数据集D划分为两个互斥的集合，其中一个集合作为训练集S，另一个作为测试集T
训练/测试集的划分要尽可能保持数据分布的一致性。保留类别的方式通常称为（分层采样）
即便是在给定训练/测试集的样本比例后，仍存在多重划分方式对初始数据集D进行分割。
因此，单次使用留出法得到的估计结果往往不够稳定可靠，在使用留出法时，一般多次取平均值。
常见做法：将大约2/3~4/5的样本用于训练，剩余样本用于测试
交叉验证法（cross validation）：
k折交叉验证：均匀分成k份，依次取一份作为测试集，其他k-1份作为训练集，分别做k次训练和测试
交叉验证法评估结果的稳定性和保真性正在很大程度上取决于k的取值
留一法：
优点：评估结果往往被认为比较准确
缺点：训练M个模型的计算开销可能是难以忍受的
自助法（bootstrapping）：
是一种从给定训练集中有放回的均匀抽样，也就是说，每当选中一个样本，它等可能地被再次选中并被再次添加到训练集中。
样本在m次采样中始终不被采到的概率是(1-1/m)m，取极限为1/e约等于0.368
优点：
自助法在数据集较小、难以有效划分训练/测试集时也很有用
从初始数据集中产生多个不同的训练集
缺点：改变了初始数据集的分布，会引入估计误差
调参与最终模型：
在模型选择完成以后，学习算法和参数配置已选定，此时应该用数据集D重新训练模型
测试数据：学得模型在实际使用中遇到的数据
验证集：模型评估与选择中用于评估测试的数据集
通常我们用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集合验证集基于验证集上的性能来进行模型选择和调参
2.3性能度量
除了如何划分集合、如何调参外，还有一点需要讨论——我们以什么样的指标来度量模型的表现？
定义：
衡量模型泛化能力的评价标准
均方误差：
回归任务常用的性能度量
错误率：
精度：
分类混淆矩阵：
查准率（precision）：
预测中的正例实际为正例所占的比例
查全率(recall)：
所有正例被预测为正例所占的比例
查准率P和查全率R是矛盾的
PR图：
P-R图可以直观地表示查准率P和查全率R的关系，曲线面积越大，算法越好。如果一个算法的P-R曲线能“包住”另外一个说明该算法比后者要好。
平衡点(BEP，Break-Even-Point)：查准率P=查全率R时的取值
F1：
产出原因：BEP过于简化
F1是基于查准率与查全率的调和平均
Fβ是加权调和平均，能够让我们表达出对查准率/查全率的不同偏好
其中β>0度量了查全率对查准率的相对重要性
β=1时退化为标准的F1;
β>1时查全率有更大影响;
β<1时查准率有更大影响
很多时候，我们希望在n个二分类混淆矩阵上分别计算出查准率与查全率，记为(P1,R1),（p2,R2）,…,（Pn,Rn）
方法一：一种直接的做法是先在各混淆矩阵上分别计算出查准率和查全率,记为(P1,R1),（p2,R2）,…,（Pn,Rn）,再计算平均值,这样就得到“宏查准率”( macro-p)、“宏查全率”( macro-r),以及相应的“宏F1”( macro-f1)
宏查准率（macro—P）：
宏查全率（macro-R）：
宏F1（macro—F1）：
方法二：还可先将各混淆矩阵的对应元素进行平均,得到TP、FP、TN、FN的平均值，分别记为：
微查准率（micro—P）：
微查全率（micro-R）：
微F1（micro—F1）：
Roc和AUC：
Roc：Roc全称是“受试者工作特征（Receiver Operating Characteristic）”曲线。根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出两个重要量的值，分别以它们的横、纵坐标作图，就得到了Roc曲线。
AUC：其中AUC（Area Under Roc Curve）为Roc曲线下所包含的面积，用于判断学习器间的性能谁更优。
Roc曲线的纵轴是“真正例率（True Positive Rate，简称TPR）”，横轴是“假正例率（False Positive Rate，简称FPR）”。
分类混淆矩阵
计算示例：
我们从高到低，依次将“Score”值作为阈值threshold，当测试样本属于正样本的概率大于或等于这个threshold时，我们认为它为正样本，否则为负样本。举例来说，对于图中的第4个样本，其“Score”值为0.6，那么样本1，2，3，4都被认为是正样本，因为它们的“Score”值都大于等于0.6，而其他样本则都认为是负样本。每次选取一个不同的threshold，我们就可以得到一组FPR和TPR，即Roc曲线上的一点。这样一来，我们一共得到了20组FPR和TPR的值，将它们画在Roc曲线的结果如下图：
为什么使用Roc和Auc评价分类器？
因为Roc曲线有个很好的特性：当测试集中的正负样本的分布变换的时候，Roc曲线能够保持不变。
代价敏感错误率与代价曲线：
产生原因：在前面介绍的一些性能度量可以看出，它们大多隐式的假设了均等代价；然而在现实任务中常会遇到这样的情况:不同类型的错误所造成的后果不同
非均等代价：为权衡不同类型错误所造成的不同损失，可将错误赋予“非均等代价”
二类代价矩阵：一般来说costii=0;若将第0类判定为第1类所造成的损失更大，则cost01>cost10;损失程度相差越大，cost01与cost10的值相差越大
敏感错误率：
D+与D-分别代表样例集D的正例子集和反类子集
代价曲线：
在非均等的代价下，Roc曲线不能直接反映出学习器的期望的总体代价，而代价曲线则可以。其中P是样例为正例的概率，纵轴是取值为[0,1]的归一化代价
Roc曲线上每一点对应了代价平面上的一条线段,设Roc曲线上点的坐标为(TPR,FPR),则可相应计算出FNR,然后在代价平面上绘制条从(0,FPR)到(1,FNR)的线段,线段下的面积即表示了该条件下的期望总体代价;如此将Roc曲线上的每个点转化为代价平面上的一条线段,然后取所有线段的下界,围成的面积即为在所有条件下学习器的期望总体代价。
2.4比较检验
2.4.1产生原因：
直接取得性能度量的值然后“比大小”吗?实际上，机器学习中性能比较这件事要比大家想象的复杂得多。这里面涉及几个重要因素:首先，我们希望比较的是泛化性能，然而通过实验评估方法我们获得的是测试集上的性能，两者的对比结果可能未必相同；第二，测试集上的性能与测试集本身的选择有很大关系，且不论使用不同大小的测试集会得到不同的结果，即便用相同大小的测试集，若包含的测试样例不同，测试结果也会有不同；第三，很多机器学习算法本身有一定的随机性，即便用相同的参数设置在同一个测试集上多次运行，其结果也会有不同。
2.4.2主要有3类方法可以对学习器的性能进行比较：
1.假设检验
二项检验与t检验
上面介绍的两种方法都是对关于单个学习器泛化性能的假设进行检验,而在现实任务中,更多时候我们需对不同学习器的性能进行比较,下面将介绍适用于此类情况的假设检验方法。
2.交叉验证t检验
这里的基本思想是若两个学习器的性能相同,则它们使用相同的训练/测试集得到的测试错误率应相同。
3.McNemar检验
交又验证t检验和 Mcnemar检验都是在一个数据集上比较两个算法的性能,而在很多时候,我们会在一组数据集上对多个算法进行比较.
4.Frieman检验与Nemenyi后续检验
2.5偏差与方差
产生原因：
对学习算法除了通过实验估计其泛化性能,人们往往还希望了解它“为什”具有这样的性能.“偏差方差分解”(bias- variance decomposition)是解释学习算法泛化性能的一种重要工具
期望预测：
使用样本数相同的不同训练集产生的方差：
噪声：
偏差：
期望输出与真实标记的差别称为偏差（bias)
泛化误差公式：
泛化误差可分解为偏差、方差和噪声之和
一般来说，偏差与方差有冲突，称为偏差-方差窘境(bias-variance dilemma)
偏差度量了学习算法的期望预测与真实结果的偏离程度,即刻画了学习算法本身的拟合能力;方差度量了同样大小的训练集的变动所导致的学习性能的变化,即刻画了数据扰动所造成的影响;噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界,即刻画了学习问题本身的难度.偏差一方差分解说明,泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的.给定学习任务,为了取得好的泛化性能,则需使偏差较小,即能够充分拟合数据,并且使方差较小,即使得数据扰动产生的影响小。
三、线性模型
3.1基本形式
线性模型：
试图学得一个通过属性的线性组合来进行预测的函数，即
用向量形式写成
由于w直观的表达了各属性在预测中的重要性，由此线性模型有很好的可解释性
3.2线性回归
3.2.1定义
所谓线性回归，就是已知数据集学成一个线性模型f(x)=w1x1+w2x2+...+wdxd+b=w^Tx+b，使得误差平方和最小。
最小化的过程，称为线性回归模型的最小二乘“参数估计”。让它分别对w和b求导，得
令上面的两个式子为0，解得
3.2.2多元线性回归
可利用最小二乘法对w和b进行估计，把w和b吸入向量形式w^=(w;b)，把数据集D表示为m*(d+1)大小的矩阵X，每行对应一个示例，该行前d个元素对应于示例的d个属性值，最后一个元素均置为1，即
再把标记写成向量形式y=(y1;y2;...;ym)
误差平方和的矩阵形式
当X^TX为满秩矩阵或正定矩阵，令上式为0可得
广义线性模型考虑单调可微函数g(x)
最终学得的线性回归模型为
3.2.3正则化项
在现实任务中，我们会遇到大量的变量，数目甚至超过样例数，导致X的列数多余行数，X^TX往往不是满秩矩阵，此时可以解出多个w^ ，它们都能使均方误差最小化，选择哪一个解作为输出，将由学习算法的归纳偏好决定
3.2.4对数线性回归
假设我们认为示例对应的输出标记在指数尺度上变化，可将输出标记的对数作为线性模型逼近的目标，即
实际上是在试图让逼近y
考虑单调可微函数g(·)，令
这样得到的模型是“广义线性模型”，其中函数g(·)称为联系函数，对数线性回归是广义线性模型在g(·)在ln(·)的特例
3.3对数线性回归
对于分类任务，在广义线性模型中，只需找到一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值联系起来。
对于二分类任务，输出标记y∈ {0,1}，而线性回归模型产生的预测值
是实值，于是将实值z转化为0/1值，用到“单位阶跃函数”
若预测值z大于0就判为正例，小于0判为反例，为临界值可任意判别
然而单位阶跃函数并不连续，希望找到一个一定程度上近似单位阶跃函数的“替代函数”并且它单调可微
对数几率函数是一个常用的替代函数：
将对数几率函数作为g^- (·)代入广义线性模型，得到
几率：y/1-y
对数几率：ln(y/1-y)
若y为样本x作为正例的可能性，则1-y是反例可能性，两者的比值y/1-y称为几率，反映了x作为正例的相对可能性，对几率取对数得到对数几率ln(y/1-y)，可看出式子是在用线性回归模型的预测结果逼近真实标记的对数几率，因此对应的模型称为“对数几率回归”，虽然名字是回归，但是是一种分类学习方法。
优点是它直接对分类可能性进行建模，无须事先假设数据分布，避免了假设分布不准确带来的问题，它不是预测出“类别”，而是可得到近似概率预测，对需利用概率辅助决策的任务很有用。
若将y视为类后验概率估计p(y=1|x)，则上式可重写为
最后可用极大似然法来估计w和b
3.4多分类学习
3.4.1基本思路
基本思路是“拆解法”，将多分类学习任务拆为若干个二分类任务求解，最经典的三种拆分策略：“一对一”(OvO)、“一对其余”(OvR)和“多对多”(MvM)
3.4.2 OVO
给定数据集D={(x1,y1),(x2,y2),…(xm,ym)},yi∈(C1,C2,…CN),OVO将这N个类别两两配对，从而产生N(N-1)/2个分类任务，最终结果可以通过投票产生：即把被预测得最多的类别作为最终分类结果。
3.4.3 OVR
OVR则是每次将一个类的样例作为正例，所有其他的样例作为反例来训练N个分类器。在测试时若只有一个分类器预测为正类，则对应的类别标记作为最终分类结果。
3.4.4 OVO与OVR比较
OVO的存储开销和测试时间开销通常比OVR更大，方式在训练时，OVR的每个分类器均使用全部训练样例，因此，在类别很多时，OVO的训练时间开销通常比OVR更小。
3.4.5 MVM技术
纠错输出码（Error Correcting Output Codes，ECOC）
过程：
编码：对N个类别做M次划分，每次划分将一部分类别化为正类，另一部分分为反类，产生M个训练集——M个分类器。
解码：M个分类器分别预测，这些预测标记组成一个编码，将其与每个类别的编码比较，区别最小的就是最终结果。
类别划分通过“编码矩阵”指定
二元阵：将类别指定为正类和反类
三元阵：在正反类之外还可以指定“停用类”
示意图：
欧氏距离：在a图中分类器f2将C1和C3类的样例作为正例；若基于欧式距离，预测结果是C3
海明距离：两个合法代码对应位上编码不同的位数为码距，又称海明码，例如测试示例：101010，分类示例：100101，此时海明距离为4
总结：一般来说，对于同一个学习任务，ECOC编码越长，纠错能力越强；然而，编码越长，意味着所需训练器的分类器越多，计算、存储开销都会增大。
3.5类别不均衡问题
3.5.1 定义
类别不平衡，就是指分类任务中不同类别的训练样例数目差别很大的情况。
用1式对新样本进行分类，实际上在用预测的y值与一个阈值比较。若：
则预测为正例
然而，正反例数目不同时，观测几率m+/m-，由于我们假设无偏采样，则观测几率就代表真实几率，于是若
则预测为正例
但是原来的分类器基于1式进行决策，所以需要再缩放操作
但是我们很难保证“训练集是真实样本总体的无偏采样”。现有技术有3种做法：
1.“欠采样”：直接去除一些反例。
2.“过采样”：增加一些正例。
3.阈值移动：不增不减，但是预测时采取式2。
