机器学习概论

一、分类

1.基本分类

(1)监督学习

监督学习是指从标注数据中学习预测模型的机器学习问题，标注数据表示输入输出的对应关系，预测模型对给定的输入产生相应的输出。监督学习的本质是学习输入到输出的映射的统计规律。

每个具体的输入是一个实例，通常由特征向量表示。这时，所有特征向量存在的空间称为特征空间特征空间的每一维对应于一个特征。

监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。换句话说，学习的目的就是找到最好的这样的模型。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间。假设空间意味着学习的范围的确定

(2)无监督学习

无监督学习是指从无标注数据中学习预测模型的机器学习问题。无标注数据是自然得到的数据，预测模型表示对数据的类别、转换或概率。无监督模型学习的本质是数据中的统计规律或潜在结构。

(3)强化学习

强化学习是指智能系统在于环境互动中学习最优行为策略的机器学习问题。假设智能系统与环境的互动基于隐马尔科夫决策过程，智能系统观测到的是与环境互动得到的数据序列。强化学习的本质是学习最优的序贯决策。

强化学习的马尔科夫决策过程是状态、奖励和动作序列的随机过程，由五元组 $(S,A,P,r,\gamma)$

S是有限状态(state)的集合
A是有限动作(action)的集合
P是状态转移概率函数: $P(s'|s,a)=P(s_{t+1}|s_t=s,a_t=a)$
r是奖励函数: $r(s,a) = E(s_{t+1}|s_t=s,a_t=a)$
$\gamma$ 是衰减系数; $\gamma \in [0,1]$

(4)半监督与主动学习

半监督学习是指利用标注数据和未标注数据学习预测模型的机器学习问题。通常有少量标注数据，大量未标注数据。半监督学习旨在利用未标注数据中的信息，辅助标注数据，进行监督学术，以较低城镇达到很好的学习效果。

主动学习是指机器不断主动地给出实例让教师进行标注，然后利用标注数据学习预测模型的机器学习问题。通常的监督学习使用给定的标注数据，往往是随机得到的，可以看作是“被动学习”，主动学习的目标是找出学习最有帮助的实例让教师标注，以较小的标注代价，达到较好的学习效果。

半监督学习和主动学习更接近监督学习

2.按技巧分类

(1)贝叶斯学习

贝叶斯学习，又称贝叶斯推理，是统计学、机器学习中重要的方法。其主要想法是在给定数据条件下模型的条件概率，即后验概率，并应用这个原理进行模型的估计，以及对数据的预测。将模型、未观测要素及其参数使用变量表示，使用模型的先验分布是贝叶斯学习的特点。
朴素贝叶斯、潜在狄利克雷分配的学习属于贝叶斯学习。

假设数据变量D表示数据，随机变量 $\theta$ 表示模型参数。根据贝叶斯定理，可以用以下公式计算后验概率 $P(\theta|D)$

$P(\theta|D) = \frac{P(\theta)P(D|\theta)}{P(D)}$
模型估计时，估计整个后验概率分布 $P(\theta|D)$ 。如果需要给出一个模型，通常取后验概率最大的模型。

预测时，估计整个后验概率分布的期望值
$P(x|D)=\int P(x|,\theta,D)p(\theta|D)$
这里的x是样本

贝叶斯估计与极大似然估计在思想上有很大的不同，代表着统计学中频率学派和贝叶斯派对统计的不同认识。其实，可以简单地把两者联系起来，假设先验分布是均匀分布，取后验概率最大，就能从贝叶斯估计对到极大似然估计。
[站外图片上传中...(image-5ba9fd-1565409215401)]

3.核方法

核方法是使用核函数表示和学习非线性模型一种极其学习方法，可以用于监督学习和无监督学习。有一些线性模型的学习基于相似度计算，更具体地，向量内积计算。核方法可以把它们拓展到非线性模型的学习，使其应用范围更广泛。

核函数支持向量机，以及核PCA、核均值属于核方法。

把线性空间扩展到非线性模型，直接的做法是显式地定义从输入空间（低维空间）到特征空间（高维空间）的映射，在特征空间中进行内积。

二、模型评估与选择

1.经验误差与过拟合

通常我们把分类错误的样本数占样本总数的比例称为“错误率”，即如果在m个样本中有a个样本分类错误，则错误率 $E=a/m$ ；相应的， $1-a/m$ 称为精度，即精度=1-错误率.更一般的，我们把学习器的实际预测输出与样本的真实输出之间的差异称为误差。学习器在训练集上的误差称为训练误差或经验误差，在新样本上的误差称为泛化误差。

我们实际希望的，是在新样本上表现得很好的学习器，为了达到这个目的，应该从训练样本中尽可能学习适用于所有潜在样本的“普遍规律”，这样才能在遇到新样本时做出正确的判别，然而，当学习器把训练样本学得“太好”了的时候，很可能把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，这样会导致泛化性能下降，这种现象在机器学习中称为“过拟合”。欠拟合则通常是由于学习能力低下而造成的，欠拟合比较容易克服。

在现实任务中，我们往往有很多种学习算法可供选择，甚至对同一个学习算法，当使用不同的参数配置时，也会产生不同的模型，那么，我们该选用哪一个学习算法，使用哪一种参数配置呢?这就是机器学习中的“模型选择”。

2.评估方法

通常，我们可以通过实验测试来对学习器的泛化误差进行评估进而做出选择。为此，需使用一个“测试集”来测试学习器对新样本的判别能力，然后以测试集上“测试误差”作为泛化误差的近似。通常，我们假设测试样本也是从样本真实分布中独立同分布而得，但需注意的是，测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现，未在训练过程中使用过。

(1)留出法

“留出法”直接将数据集D划分成两个互斥的集合，其中一个集合做为训练集S，另一个作为测试集，即 $D=S\cup T,S \cap T = \varnothing$ 。S在训练出模型后，用T来评估其测试误差，作为泛化误差的估计。

需注意的是训练/测试集的划分要尽可能保持数据一种性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。如果从采样的角度来看待数据集划分过程，则保留类别比例的采样方式通常称为“分层抽样”。

(2)交叉验证法

“交叉验证法”先将数据集D划分为k个大小相似的互斥子集，即 $D=D_1 \cup D_2 \cup \dots \cup D_k,D_i \cap D_j = \varnothing(i \ne j)$ 。每个子集 $D_i$ 都尽可能保持数据分布的一致性，即从D中通过分层采样得到。然后，每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集；这样就可以得获得k组训练/测试集。最终返回的是k个测试结果的均值。显然，交叉验证法评估结果的稳定性和保真性在很大程度上取决于k的取值，为强调这这一点，通常把交叉验证法称为“k折交叉验证”，k最常取值是10。

(3)自助法

自助法在数据集较小，难以有效划分训练/测试集时很有效；此外，自助法能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大的好处。然而自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。因此，在初始数据集足够时，留出法和交叉验证法更常用些。

自助法，直接以自助采样为基础，给定包含m个样本的数据集D，我们对它进行采样产生数据集D'；每次随机从D中挑选一个样本，我能对它进行采样产生数据集D'，然后再将样本放回初始数据集D中，使得样本在下次采样时仍然有可能被采到；这个过程重复执行m次后，我们就得到了包含m个样本的数据集D'，这就是自助采样的结果。显然，D有一部分样本会在D'中多次出现，而另一部分样本不会出现。可以做一个简单的估计，样本在m次采样中始终不被采到的概率是 $(1-\frac{1}{m})^m$ ，取极限得到
$\lim\limits_{m \to \infty}(1-\frac{1}{m})^m = \frac{1}{e} \approx 0.368$

(4)调参与最终模型

大多数学习算法都有些参数需要设定，参数配置不同，学得的模型的性能往往有显著差别。因此，在进行模型评估与选择时，除了要对适用学习算法进行选择，，还需对算法参数进行设定，这就是通常所说的“调节参数”或简称“调参”。

学习算法的很多参数是在实数范围内取值，因此对每种参数配置都训练出模型来是不可行的。现实中常用的做法，是对每个参数选定一个范围和变化步长，例如在[0,0.2]范围内以0.05为步长，则实际要评估的候选参数值有5个，最终从这5个候选值中产生选定值。显然，这样选定的参数值往往不是“最佳”值，但这是在计算开销和性能估计之间进行折中的结果。通过这个折中，学习过程才变得可行。

我们常常把学习得模型在实际使用中遇到的数据称为测试数据，为了加以区分，模型评估与选择用于评估测试的数据集通常称为“验证集”。例如，在研究对比不同算法的泛化性能时，而把训练数据划分为训练集合验证集，基于验证集上的性能来进行模型选择和调参。

三、性能度量

对学习器的泛化能力进行评估，不仅需要有效可行的实验估计，还需要衡量模型泛化能力的评价标准，这就是性能度量。性能度量反映了任务需求，在对比不同模型的能力时，使用不同的性能度量往往会导致不同的评判结果；这意味着模型的“好坏”是相对的，什么样的模型是好的，不仅取决于算法和数据，还决定于任务需求。

在预测任务中，给定例集 $D=\{(x_1,y_1),(x_2，y_2),\dots,(x_m,y_m) \}$ ，其中 $y_i$ 是示例 $x_i$ 的真实标记，要评估学习器 $f$ 的性能，就要把学习器预测结果 $f(x)$ 与真实标记 $y$ 进行比较
回归任务最常用的性能度量是“均方误差”
$E(f;D)=\frac{1}{m}\sum_{i=1}^m (f(x_i)-y_i)^2$
更一般的，对于数据分布D和概率密度函数p(.)，均方误差可描述为
$E(f;D)=\int_{x \in D}(f(x)-y)^2 p(x)dx$

下面主要介绍分类任务中常用的性能度量

(1)错误率与精度

错误率是分类错误的样本占样本总数的比例，精度是分类正确的样本数占样本总数的比例，对样例集D，分类错误率定义为
$E(f;D)=\frac{1}{m}\sum_{i=1}^m I(f(x_i) \ne y_i)$

$I$ 是指示函数

精度定义为
$acc(f;D)=\frac{1}{m}\sum_{i=1}^m I(f(x_i) = y_i)=1- E(f;D)$
更一般的，对于数据分布D和概率密度函数p(.),错误率和精度可分布描述为
$\begin{align} E(f;D)=\int_{x \in D}(I(f(x) \ne y) p(x)dx \\ acc(f;D)=\int_{x \in D}(I(f(x) = y) p(x)dx = 1- E(f;D) \end{align}$

(2)查准率与查全率

在信息检索、Web搜索等应用中，我们经常会关心“检索出的信息中有多少比例是用户感兴趣的”，“用户感兴趣的信息中有多少被检索出来了",“查准率”与“查全率”是更为适用于此类需求的性能度量。

对于而分类为题，可将样例根据真实类别与学习器预测类别的组合划分为真正例(true positive)、假正例(false positive)，真反例(true negative)，假反例(false negative)四种情形，令TP、FP、TN、FN分别表示其对应的样本例数，则显然有 $TP+FP+TN+FN$ =样例总数。分类结果的“混淆矩阵”(confusion matrix)

分类与混淆矩阵.png

查准率P与查全率R分别定义为
$\begin{align} P = \frac{TP}{TP+FP} \\ R=\frac{TP}{TP+FN} \end{align}$
查准率是一对矛盾的度量，一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低。通常只有一些简单任务中，才可能使查全率和查准率都很高。

在很多情形下，我们可根据学习器的预测结果对样例进行排序，排在前面的是学习器认为“最可能”是正例的样本，排在后面的则是学习器认为"最不可能"是正例的样本，按此顺序逐个把样本作为正例进行预测，则每次计算出查全率和查准率，以查准率为纵轴，查全率为横轴。就得到了查准率-查全率曲线，简称"P-R"曲线。

P-R曲线与平衡点示意图.png

P-R曲线直观地显示出学习器在样本总体上的查全率，查准率。在进行比较时，若一个学习器的P-R曲线被另一个学习器的曲线完全“包住”，则可断言量后者的性能优于前者（图中学习器A的性能优于B）；如果两个学习器P-R曲线相交，则难以一般性地断言两者孰优孰劣。

“平衡点”(Break-Even Point)是“查准率=查全率”时的取值，而基于BEP的比较，可认为学习器A优于B。

但BEP过于简化了些，更常用的是 $F_1$ 度量
$F_1 = \frac{2*P*R}{P+R}=\frac{2*TP}{样例总数+TP-TN}$

在一些应用中，对查准率和查全率的重视程度有所不同。例如在商品推荐系统中，为了尽可能少打扰用户，更希望推荐内容确是用户感兴趣的，此时查准率更重要；而在逃犯信息检索中，更希望尽可能少漏掉逃犯，此时查全率更重要。 $F_1$ 度量的一般形式---- $F_{\beta}$ ,能让我们表达出对查全率/查准率的不同偏好

$F_{\beta}=\frac{(1+\beta^2)P*R}{(\beta^2*P)+R}$
$\beta > 0$ ，查全率对查准率的相对性重要

$\beta = 1$ ,退化成标准的 $F_1$
$\beta > 1$ ，查全率有更大的影响
$\beta < 1$ ，查准率有更大的影响

(3)ROC与AUC

很多学习器为测试样本产生一个实值或概率预测，然后将这个预测值与一个分类阈值进行比较，若大于阈值则分为正例，否则为反例。例如，神经网络在一般情形下是对每个测试样本预测出一个 $[0,1]$ 之间的实值，然后将这个值与0.5进行比较，大于0.5则判为正例，否则为反例，这个实值的或预测结果的好坏，直接决定了学习器的泛化能力。

可以根据这个实值，或概率预测结果，我们可将测试样本进行排序，“最可能”是正例的排在最前面，“最不可能”是正例的排在最后面。这样，分类过程就相当于在这个排序中以某个“截断点”将样本分为两部分，前一部分作为正例，后一部分则判为反例。

在不同任务中，我们可根据任务需求来采用不同的截断点，例如若我们更重视“查准率”，则可选择排序中靠前的位置进行截断；若更重视“查全率”，排，则可选择靠后的位置进行截断。ROC曲线则是从这个角度出发来研究学习器泛化性能的有力工具。

与P-R曲线，我们根据学习的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出两个重要量的值，纵轴是“真正的正例”(True Positive Rate,TPR),横轴是“假正例率”(Flase Postive Rate，FPR）,两者分别定义为
$\begin{align} TPR = \frac{TP}{TP+FN} \\ FPR = \frac{FP}{TN+FP} \end{align}$

ROC与AUC曲线.png

ROC曲线中，对角线对应于“随机猜想”，而点(0,1)则对应于将所有正例排在所有反例之前的理性模型。

现实任务通常是利用有限个测试样例来绘制ROC图，此时仅能获得有限个（真正例率，假正例率）坐标轴，无法产生光滑的ROC曲线。

进行学习器的比较时，若一个学习器ROC曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者；若两个学习器的ROC曲线相交，则难以一般性地断言两者孰优孰劣。此时如果要进行比较，则较为合理的判断是比较ROC曲线下的妙计，即AUC。

(4)代价敏感错误率与代价曲线

在现实任务中，往往会遇到这样的情况：不同类型的错误所造成的后果不同。例如在医疗诊断中，错误把患者诊断为健康人与错误把患者诊断为患者，看起来都是犯了“一次错误”，但后者的影响是增加了仅一步检查的麻烦，前者的后果却可能是丧失了拯救生命的最佳时机。为权衡不同类型错误所造成的不同损失，可为错误赋予”非均等代价“。

以二分类任务为例，我们可根据任务的领域知识设定一个“代价矩阵”(cost matrix),其中 $cost_{ij}$ 表示将第i类样本预测为第j类样本的代价。一般来说， $cost_{ii}= 0$ ，若将第0类样本判为第1类所造成的损失更大，则 $cost_{01} > cost_{10}$ ；损失程度相差越大， $cost_{01}$ 与 $cost_{10}$ 值的差别越大。

二分类代价矩阵.png

前面所介绍的一些性能度量，它们大都隐式地假设了均等代价，错误率是直接计算“错误次数”，并没有考虑不同错误会造成不同的后果。在非均等情况下，我们所希望的不再是简单地最小化错误次数，而是希望最小化“总体代价”，若将混合矩阵第0类做为正例，第1类做为反例，令 $D^+,D^-$ 分别代表样例集D的正例子集合反例子集，则“代价敏感”(cost-sentive)错误率为
$E(f;D;cost) = \frac{1}{m}\Bigg(\sum_{x_i \in D^+} I (f(x_i) \ne y_i)*cost_{01} + \sum_{x_i \in D^+} I (f(x_i) \ne y_i)*cost_{10} \Bigg)$

在非均等代价下，ROC曲线不能直接反映出学习器的期望总体代价，而“代价曲线”(cost curve)则可达到目的。代价曲线的横轴是取值为[0,1]，的正例概率代价
$P(+)cost = \frac{p*cost_{01}}{p*cost_{01}+(1-p)cost_{10}}$
其中p是样本为正例的概率，纵轴是取值为[0,1]的归一化代价
$cost_norm =\frac{FRN*p*cost_{01} + FPR*(1-p)*cost_{10}}{p*cost_{01}+(1-p)cost_{10}}$

其中FNR是假正例率，FPR = 1 - TPR假反例率。代价曲线的绘制如下：ROC曲线上的每一点对应了代价平面上的一条线段，设ROC曲线上的点的坐标为坐标为(FPR,TPR)，则可相应计算出FNR，然后在代价平面上绘制一条从(0,FPR),到(1,FNR)曲线，线段下的面积即表示该条件下的期望总代价，如此将ROC曲线上的每个点转化为代价平面上的一条线段，染个取所有线段的下界，围成的面积即为所有条件下学习器的期望总代价。

代价曲线与期望总体代价.png

四、偏差与方差

对学习算法除了通过估计其泛化性能，我们往往还需要了解它“为什么”具有这样的性能，“偏差-方差分解”(bias-variance decomposition)是解释学习算法泛化性能的一种重要工具。

令 $y_D$ 表示x在数据集中的标记， $y$ 为x的真实标记， $f(x;D)$ 为训练D上学得的模型f在x上的预测输出。学习算法的期望项为
$\bar f(x) = E_D[f(x;D)]$
使用样本数相同的不同训练集产生的方差为
$var(x)=E_D[\big(f(x;D)-\bar f(x)\big)^2]$
期望输出与真实标记的差别称为偏差(bias)，即
$bias^2(x) = (\bar f(x) - y)^2$

为便于讨论，假设噪声期望为0，即 $E_D(y_D-y)=0$ ，通过简单的多项式展开合并，可对算法的期望泛化误差分解
$E(f;D) = bias^2(x)+var(x)+\epsilon^2$
也就是说，泛化误差可分解为偏差、方差与噪声之和。

偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学算法本身的拟合能力。方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响；噪声则表达了再当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。泛化性能时由学习算法的能力，数据的充分性以及学习的难度所共同决定的，给定学习任务，为了取得好的泛化性能，则需使偏差教小，即能充分拟合数据，并且使方差较小，即使得数据扰动产生的影响小。

泛化误差与偏差、方差的关系.png

一般来说，偏差和方差是有冲突的，这称为偏差-方差窘境。给定学习任务，假设我们能控制学习算法的训练程度，则在训练不足时，学习器的拟合能力不够强，训练数据的扰动不足以使学习器产生显著变化，此时偏差主导了泛化错误率。随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据发生的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率；在训练程度充足后，学习器拟合能力已非常强了，训练数据发生轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特征被学习到了，则发生过拟合。