机器学习算法地图2021版

为了帮助大家理清机器学习的知识脉络，建立整体的知识结构，2018年SIGAI推出过机器学习算法地图，纸质版和电子版的阅读量超过10万。两年之后，我们对算法地图进行了优化升级，使得它的结构更为合理清晰，内容更为简洁。下面先看算法地图2021版的整图

为了让整图更简洁，我们将强化学习移出了这张图，后面如有精力，会制作强化学习算法地图。另外，深度学习算法有专门的算法地图。图中涉及到的机器学习算法包括

有监督学习，进一步细分为分类问题，回归问题，数据降维问题，距离度量学习

无监督学习，进一步细分为数据降维问题，距离度量学习，聚类问题

概率图模型，进一步细分为有向图模型，无向图模型

数据生成问题

自动化机器学习，这里只列出了贝叶斯优化

下面我们分类介绍，帮助大家理清各种算法之间的联系，以及演化关系。

贝叶斯分类器家族

贝叶斯分类器是最简单的分类模型之一，也是一种生成式模型。它直接用贝叶斯公式算出样本属于每个类的后验概率

然后取后验概率最大的那个类作为分类结果

贝叶斯分类器要知道每类样本所服从的概率分布。对于这个问题，这里衍生出了两种贝叶斯分类器实现：朴素贝叶斯分类器，正态贝叶斯分类器。前者假设每个类的样本的特征向量的每个分量相互独立

后者假设每类 样本的特征向量服从多维正态分布

无论是哪种贝叶斯分类器，训练时模型的参数都通过最大似然估计得到。贝叶斯分类器可以看做是贝叶斯网络的简单特例，后者可以实现多个变量之间的因果推理。因此，从贝叶斯分类器衍生出了概率有向图模型-贝叶斯网络。

决策树家族

决策树是机器学习中枝繁叶茂的大家族。它用一组嵌套的判定规则实现分类和回归，是最符合人类直观思维的机器学习模型，具有非常好的可解释性。

决策树的这组判定规则是通过学习得到的，而不是人工制定的。具体的，递归地创建树（树天然是一种递归结构），建立每个非叶子节点的关键是寻找最佳判定规则。决策树有3种典型的实现，分别是

ID3

C4.5

CART

它们的主要区别在于训练时寻找最佳分裂阈值（判定规则）所用的指标不同。另外，CART不仅可以用于分类问题，也可以用于回归问题。ID3使用的是信息增益指标

C4.5使用的是信息增益率指标。对于分类问题，CART使用的是Gini不纯度指标

实现时进行了简化，变为下面的值

对于回归问题，CART使用的是回归误差下降值指标，简化之后为

决策树还与集成学习算法实现了完美结合，诞生出了随机森林、Boosting算法两类经典算法，前者至今还被广泛使用，后者当年在视觉目标检测中名噪一时。

KNN与距离度量学习算法家族

KNN算法是基于实例的机器学习算法，预测时将待预测样本直接与训练样本集进行比较，得到结果。它既可以用于分类问题，也可以用于回归问题。KNN算法的实现依赖于距离函数，除了我们常用的欧氏距离、曼哈顿距离等距离定义，我们还可以用机器学习的方式来确定一个距离函数-可谓是一切皆可学习！具体的，是学习一个距离度量矩阵。

由此引申出了距离度量学习家族，它曾经是种重要的机器学习算法存在，至今还发挥着重要的作用。这里列出了典型的3种实现，分别是

LMNN

ITML

NCA

LMNN是一种有监督的距离度量学习算法，它的目标是：确保每个样本的最近的若干个邻居样本都是自己的同类样本，而不同类的样本离它尽可能远。前者是“拉”，将同类样本拉近；后者是“推”，将不同类样本推远。如下图所示

因此目标函数是拉函数与推函数的加权和

ITML就是一种基于信息论的方法，算法使用了信息论中的KL散度，因此得名。这是一种有监督的局部度量学习算法。ITML的优化目标是在保证同类样本距离相近，不同类样本之间距离远的约束条件下，迫使度量矩阵所代表的正态分布接近于某一先验概率分布。目标函数为

如果假设服从正态分布，目标函数为

与LMNN类似，NCA同样与k近邻算法有关。其优化目标是使得每个样本的同类样本被k近邻算法正确分类的概率最大化，以此构造目标函数。这是一种有监督的局部度量学习算法。样本对邻居概率定义通过softmax归一化进行计算

在对样本点进行分类时，如果采用这些邻接作为其标签值，则可以计算出样本点被正确分类的概率。样本点被正确的分类的概率是它所有同类样本成为其邻居的概率之和

NCA的优化目标是所有样本的上述概率之和

这种思想与后面将要介绍的SNE算法有些类似。

集成学习算法家族

集成学习是机器学习中一类重要的存在，它源于一个朴实的思想：三个臭皮匠，赛过诸葛亮。如果每个机器学习模型很弱，我们把它们联合起来使用，集体做决策，很有可能就可以提升预测精度！即根据多个弱学习器构造一个强学习器。集成学习有两个重要的实现套路，分别是

Bagging

Boosting

前者对训练样本集进行采样，每次用采样得到的训练集训练一个机器学习模型。预测时，对于分类问题，将这些模型的据测结果进行投票，得到分类结果。对于回归问题，用它们的均值作为回归结果。如果弱学习器是决策树，那就叫随机森林。随机森林在实现时不光对训练样本进行随机抽样，用抽样得到的样本集训练每一棵决策树，另外还对特征向量的分量进行了抽样，用于训练决策树的每个内部节点。将一片树放在一起，那当然叫森林！

后者依次训练每个弱学习器，后一个弱学习器与前一个学习器相关。这里又有两种实现套路

AdaBoost算法

GBDT

AdaBoost算法为样本设置权重，每次迭代时构造不同的训练样本集，依次训练每个弱学习器，用前向差分的方式拟合强学习器，是广义加法模型与各种损失函数相结合的产物。

AdaBoost算法有4种典型的实现（这里不考虑多分类问题），分别是

离散型AdaBoost

实数型AdaBoost

LogitBoost

Gentle型AdaBoost

离散型AdaBoost是最基本的AdaBoost算法实现，它为训练样本、弱学习器设置了权重，原则是：关注之前被错分的样本即被前面的弱学习器错分的样本权重大，准确率高的弱分类器有更大的权重。

实数型AdaBoost算法弱分类器的输出值是实数值，它是向量到实数的映射。这个实数的绝对值可以看作是置信度，它的值越大，样本被判定为正样本的可信度越高。

无论是离散型还是实数型AdaBoost，都是求解指数损失函数的最小值问题，将之前迭代已经得到的强分类器看作为常数。

广义加性模型没有限定损失函数的具体类型，离散型和实数型AdaBoost采用的是指数损失函数。如果把logistic回归的损失函数应用于此模型，可以得到LogitBoost算法。LogitBoost用牛顿法优化logistic回归的对数似然函数。

Gentle型AdaBoost的弱分类器是回归函数。

梯度提升算法是另外一种提升算法，它是广义加法模型与最速下降法相结合的产物。这类算法将学习器的输出值看作变量，计算损失函数对它的导数，用最速下降法进行迭代。结合加法模型，使得学习器每次更新时拟合最速下降法的迭代步长，从而得到最终的学习器。

这里损失函数对强学习器输出值的偏导数该怎么算，要依赖于具体的损失函数和弱学习器类型。对于回归问题，可以使用均方误差，也可以使用Huber损失。

对于二分类问题，通常使用logistic回归的对数似然函数作为损失函数。强分类器的预测函数为对数似然比。多分类问题可以使用softmax回归，损失函数为交叉熵。

由此也可以看出，梯度提升算法与线性回归，logistic回归，softmax回归是有密切的联系的。对梯度提升算法进一步改进，又出现了XGBoost算法，LightGBM算法。

梯度提升法将损失函数进行泰勒展开，然后用最速下降法求解。XGBoost的做法类似，它是牛顿法与加法模型相结合的产物。XGBoost将损失函数泰勒展开到2阶，采用牛顿法求解，弱学习器拟合的是牛顿法的步长。同时它还加入了正则化项，损失函数定义为

集成学习要求弱学习器是非线性的，且实现简单，因此选择了决策树作为弱学习器。

线性模型家族

线性模型恐怕是机器学习中最大的一个家族，从它衍生出了支持向量机，神经网络这两类分别三十年河东，三十年河西，引领机器学习进程的重要算法。

首先考虑回归问题，最基本的是线性回归。它的预测函数为

训练的目标是最小化均方误差

如果加上L2正则化项， 就得到了岭回归

如果加上L1正则化项，就得到了LASSO回归

这是线性模型家族的第1个分支，更大的分支是分类问题。首先是与数据降维算法的结合，诞生了线性判别分析（LDA），我们再稍后会细讲。另外就是一个在机器学习历史上具有重要启发性意义的线性分类器算法：感知器算法。

感知器算法的目标函数为

此损失函数的意义为对于每个训练样本，如果预测正确即与标签值同号，则会有一个负的损失，否则有一个正的损失。这里的目标是将损失最小化。

感知器算法的第一个进化结果是支持向量机，它是最大化分类间隔的线性分类器（这里不考虑核函数）。想法其实很简单：为了得到好的泛化性能，分类平面应该不偏向于任何一类，并且离两个类的样本都尽可能的远。

支持向量机训练时的优化目标是

加上核函数之后，支持向量机可以解决复杂的非线性分类问题。

第2条进化路线是logistic回归，想法同样很简单：用logistic函数直接预测出样本属于正样本的概率

训练时采用最大似然估计，目标函数是交叉熵（伯努利分布的交叉熵），对数似然函数为

logistic回归简单，当年得到了广泛的应用，但是它只能解决二分类问题。对它进行扩展，用类似的方法可以计算出样本输入每个类的概率，这就是softmax回归

训练时同样采用最大似然估计，等价于最小化交叉熵

这是两个多项分布的交叉熵。

logistic回归是如此的弱，以至于它不能处理简单的异或问题-它不能解决那些不是线性可分的问题。于是出现了另外一条进化路线，也是现在的大杀器：人工神经网络。对于全连接神经网络（多层感知器模型，MLP），如果采用logistic激活函数，人工神经网络的单个神经元就是logistic回归，也就是说神经网络是由多个logistic回归模型复合构成的。

由此，我们让这一家族的机器学习模型有了处理非线性问题的能力。如果最后一个层使用softmax回归层，神经网络可以预测出样本属于每个类的概率，解决多分类问题。

人工神经网络现在以深度学习的身份自居，从它派生出了各种神经网络结构

CNN

RNN

GNN

自动编码器

RBM

深度生成模型

首先想到的是如何处理图像这样的数据，神经网络与图像处理中的卷积运算结合，出现了卷积神经网络（CNN）。之前的卷积核是人工设计的，而卷积神经网络中的卷积核是通过学习得到。这样，我们可以有效的处理2维空间，或者更高维空间的数据。用于图像分类，目标检测，图像分割等问题时，卷积神经网络衍生出了众多的结构。

既然有空间，那就有时间，在机器学习领域，我们经常需要处理时间序列问题，这需要神经网络具有记忆能力，由此诞生了循环神经网络（RNN）。这种神经网络会保存上一个时刻的某些数据，用作下一个时刻的输入数据，从而实现了记忆功能。在语音识别、自然语言处理等时间序列预测问题上，循环神经网络取得了成功。

计算机系的同学一定对图不陌生，数据结构里花了大量的篇幅介绍这种数据结构。现实生活中的很多问题也可以用图来进行建模，比如社交网络中各个人之间的关系；知识图谱中的知识结构图。于是我们又想到了把神经网络与图结合起来，诞生了图神经网络（GNN）这种结构。

神经网络与编码器-解码器结构相结合，诞生了自动编码器这种神经网络，这是一种无监督的神经网络结构。它的训练目标是最小化重构误差。

自动编码器又出现了一些变种，包括去噪自动编码器，稀疏自动编码器，收缩自动编码器，以及后面将要介绍的变分自动编码器。

去噪自动编码器对自动编码器的主要改进是在训练样本中加入随机噪声，重构的目标是不带噪声的样本数据，用自动编码器学习得到的模型重构出来的数据可以去除这种噪声，获得没有被噪声污染过的数据，这也意味着自动编码器能从有噪声的数据学习出特征。

稀疏自动编码器的主要改进在于训练时的目标函数中加入了稀疏性惩罚项，使得编码器的输出向量中各个分量的值尽可能接近于0，得到稀疏的编码结果。这里用KL散度作为稀疏性惩罚项，假设神经元是否活跃服从伯努利分布。

收缩自动编码器对自动编码器的改进是训练时在损失函数中加上正则化项，使得编码器函数的导数尽可能小。

前面介绍的神经网络都是确定性的，每个神经元的输出值可以根据输入值唯一确定，存在确定函数关系。神经网络还可以和概率论相结合，使得它具有随机性。在这种模型中，神经网络的输出值是随机的而不是确定的，即它们的值服从某种概率分布。如果采用玻尔兹曼分布，且神经网络的结构是一个二部图，就得到了受限玻尔兹曼机（RBM）。

可见变量与隐变量的联合概率为

模型的参数通过最大似然估计得到。

我们还可以把多个RBM堆叠起来使用，实现逐级的特征抽取。这样就得到了深度玻尔兹曼机（DBM）。在这种结构中，各个层都是无向的。

也可以将RBM与贝叶斯网络（概率有向图模型，将在后面介绍）结合起来，得到深信度网络DBN。在这种结构中，顶部的层是RBM，是无向的；底部的层是贝叶斯网络，是有向的。

神经网络与生成数据生成模型（更准确的说是概率分布变换）相结合，诞生了深度生成模型，典型代表是变分自动编码器（VAE），以及生成对抗网络（GAN），在后面会进一步介绍。

数据降维算法家族

神经降维算法也是机器学习中中的一个庞大家族，其目标是将向量变换到低维空间，以达到某种目标，比如变换到2-3维空间之后我们可以方便地进行可视化，人类能直观看到的是不超过3维的空间。

线性判别分析（LDA）是数据降维与线性模型相结合的产物，是有监督的数据降维算法。它的目标是将向量朝着最大化类间差异，最小化类内差异的方向投影

其优化的目标为

LDA是一种线性降维算法，与核函数相结合，诞生了KLDA算法。

PCA（主成分分析）是最简单和经典的数据降维算法，它的目标是最小化重构误差。这是一种无监督的降维算法，朝着数据变化的主要方向投影。

其优化的目标为

PCA也是一种线性降维算法，它与核函数结合，诞生了KPCA算法。

多维缩放（MDS）是一种非线性降维算法，它直接计算样本在低维空间中的坐标。经典的MDS计算任意两个样本点之间的距离，使得投影到低维空间之后能够尽量保持这种距离。其优化的目标为

流形学习是一类非线性的降维算法，它假设样本在高维空间中的分布位于一个低维流形（比如3维空间中的2维曲面）附近，里有这一假设进行降维。它的典型实现有LLE，拉普拉斯特征映射，局部保持投影，等距映射，SNE，t-SEN，LargeVis等。

局部线性嵌入（LLE）将高维数据投影到低维空间中，并保持数据点之间的局部线性关系。其核心思想是每个点都可以由与它相邻的多个点的线性组合来近似重构，投影到低维空间之后要保持这种线性重构关系，即有相同的重构系数。其优化的目标为

拉普拉斯特征映射是流形学习与图论相结合的产物，更准确的说是和谱图理论结合。它为样本点构造带权重的图，然后计算图的拉普拉斯矩，对该矩阵进行特征值分解得到投影变换结果。这个结果对应于将样本点投影到低维空间，且保持样本点在高维空间中的相对距离信息。它的优化目标为

局部保持投影同样使用了谱图理论。过最好的保持一个数据集的邻居结构信息来构造投影映射，其思路和拉普拉斯特征映射类似，区别在于不是直接得到投影结果而是求解投影矩阵。它的优化目标为

等距映射是微分几何中测地线与MDS相结合的产物，其思想与MDS相同，不同的是不直接计算高维空间中两个样本点之间的欧氏距离，而是计算它们之间的测地距离。测地线源自于大地测量学，是地球上任意两点之间在球面上的最短路径。在三维空间中两点之间的最短距离是它们之间线段的长度，但如果要沿着地球表面走，最短距离就是测地线的长度，因为我们不能从地球内部穿过去。这里的测地线就是球面上两点之间大圆上劣弧的长度。算法计算任意两个样本之间的测地距离，然后根据这个距离构造距离矩阵。最后通过距离矩阵求解优化问题完成数据的降维，降维之后的数据保留了原始数据点之间的距离信息。算法优化的目标为

SNE是流形学习与信息论相结合的产物。基于如下思想：在高维空间中距离很近的点投影到低维空间中之后也要保持这种近邻关系，在这里距离通过概率体现。为此，用KL散度衡量高维空间和低维空间中样本点邻居概率分布的差距，目标函数为

t-SNE是对SNE的改进，采用了对称的概率计算公式，另外在低维空间中计算样本点之间的概率时使用t分布代替了正态分布。LargeVis是对t-SNE的进一步改进。

概率图模型家族

概率图模型是机器学中难以理解的一类算法，它是图论与概率论相结合的产物，故此而得名。如果是无向图，称为概率无向图模型；如果是有向图，称为概率有向图模型。

概率有向图的结构是有向无环图，图的顶点表示随机变量，边表示随机变量之间的因果关系即条件概率，从而实现因果推理。概率有向图的典型代表是贝叶斯网络。HMM（隐马尔可夫模型）可以看做是贝叶斯网络的特例。与RBM结合，还诞生了DBN这种结构。

在HMM中，节点分为隐变量与可见变量两种类型，后者的值通常是未知的，隐变量与可见变量随着时间线的演化形成一个贝叶斯网络。

无向图模型的顶点同样是随机变量，但边不表示条件概率，而是各变量直接的概率依赖关系。

概率无向图的典型代表是条件随机场，它对给定可见变量时隐变量的条件概率建模。实际应用中出现的比较多的是线性链条件随机场，它的隐变量是线性链表结构。

聚类算法家族

聚类是无监督学习的典型代表，也是机器学习中非常庞大的一个家族。在这里我们分为下面几种聚类算法

层次聚类算法

基于质心的聚类/k均值算法

高斯混合模型+EM算法

基于密度的聚类

谱聚类

层次聚类非常简单，初始时每个样本各为一个簇，将反复对最近的两个簇进行合并，最后形成一棵树结构。

K均值算法是实际应用中使用最广泛的聚类算法之一。算法将每个样本划分到离它最近的那个类中心所代表的类，而类中心的确定又依赖于样本的划分方案。算法求解的优化问题为

基于概率分布的聚类算法假设每个簇的样本服从相同的概率分布，这是一种生成模型。经常使用的是多维正态分布，如果服从这种分布，则为高斯混合模型，求解时一般采用EM算法。

基于密度的聚类算法的核心思想是根据样本点某一邻域内的邻居数定义样本空间的密度，这类算法可以找出空间中形状不规则的簇，并且不用指定簇的数量。算法的核心是计算每一点处的密度值，以及根据密度来定义簇。其典型代表是DBSCAN算法，OPTICS算法，以及Mean shift算法。

DBSCAN算法可以有效的处理噪声，发现任意形状的簇。它将簇定义为样本点密集的区域，算法从一个种子样本开始，持续向密集的区域生长，直至到达边界。

OPTICS算法是对DBSCAN算法的改进，对参数更不敏感。它不直接生成簇，而是对样本进行排序，从这个排序可以得到各种邻域半径和密度阈值时的聚类结果。

Mean Shift算法基于核密度估计技术，是一种寻找概率密度函数极值点的算法。它是核密度估计与梯度上升法相结合的产物。核密度估计用一组标准函数（称为核函数）的加权核来估计概率密度函数值，给定一组样本，核密度函数用根据这组样本点以及核函数计算出任意点处的概率密度函数值

这里将簇定义为样本密集的区域，因此需要找到概率密度函数的所有局部极大值点，这通过梯度上升法完成。核密度函数的梯度值具有下面优美的形式

谱聚类算法是谱图理论与聚类相结合的产物，同样用过对图的拉普拉斯矩阵进行特征值分解而实现聚类。它有两种典型的实现-RatioCut和NCut算法。它们求解的优化问题分别为

以及

谱聚类算法对很多实际问题可以取得非常好的效果。

自动化机器学习算法家族

自动化机器学习是近年来比较热的方向。这里只考虑如何自动确定算法的超参数，如果优化变量的维数不高，通常使用的是贝叶斯优化。

贝叶斯优化依赖于高斯过程回归。高斯过程（GP）用于对一组随着时间增长的随机向量进行建模，在任意时刻随机向量的所有子向量均服从高斯分布。高斯过程回归（GPR）对表达式未知的函数（黑盒函数）的一组函数值进行贝叶斯建模，给出函数值的概率分布。它假设这些函数值服从多维高斯分布，即是一个高斯过程。根据这个可以计算出任意点处的函数值的概率分布。

贝叶斯优化（BOA）的思路是首先生成一个初始候选解集合，然后根据这些点寻找下一个最有可能是极值的点，将该点加入集合中，重复这一步骤，直至迭代终止。

这里的关键问题是如何根据已经搜索的点确定下一个搜索点，通过高斯过程回归和采集函数实现。高斯过程回归根据已经搜索的点估计其他点处目标函数值的均值和方差。根据均值和方差构造出采集函数（acquisition function），是对每一点是函数极值可能性的估计，反映了该点值得搜索的程度。该函数的极值点即为下一个搜索点。

深度生成模型家族

数据生成模型是机器学习中一类特殊的存在，以生成图像、声音、文字等数据为目标，生成的数据服从某种未知的概率分布，具有随机性。以图像生成为例，假设要生成狗、汉堡、风景等图像。

算法通过对服从简单概率分布的随机变量进行变换而实现，使得变换后的结果服从我们想要的概率分布，这些变换结果就是我们要生成的样本。这里有两类典型的深度生成模型-生成对抗网络（GAN），以及变分自动编码器(VAE)。

GAN由一个生成模型和一个判别模型组成，是概率分布变换与神经网络相结合的产物。生成模型用于学习真实样本数据的概率分布，并直接生成符合这种分布的数据，实现分布变换函数；判别模型的任务是判断一个输入样本数据是真实样本还是由生成模型生成的，即对生成模型生成的样本进行评判，以指导生成模型的训练。在训练时，两个模型不断竞争，从而分别提高它们的生成能力和判别能力。

训练时的优化目标是

VAE是变分推断与自动编码器相结合的产物，故此而得名。整个系统遵循自动编码器的结构，由编码器和解码器构成。在训练时，编码器将训练样本映射成隐变量所服从的概率分布的参数，然后从此概率分布进行采样得到隐变量，解码器则将隐变量映射回样本变量，即进行重构。这种方法在标准自动编码器的基础上加入了随机性，从而保证可以输出带有随机性的数据。

训练时优化的目标为

对机器学习中数学知识的精彩讲解可阅读《机器学习的数学》，人民邮电出版社，雷明著。该书由一元函数微积分，线性代数与矩阵论，多元函数微积分，最优化方法，概率论，信息论，随机过程，图论8章构成，用最小的篇幅精准地覆盖了机器学习所需的数学知识，讲解清晰透彻。对本文所提及的绝大部分机器学习算法的详细讲解可以阅读《机器学习-原理、算法与应用》，清华大学出版社，雷明著。机器学习算法地图2021版高清图的下载地址为：

http://tensorinfinity.com/paper_235.html