本文转载自机器学习原创文章分享平台SigAI（ID：SIGAICN）

下面先看这张图：

▲图片来自于SIGAICN

图的左半部分列出了常用的机器学习算法与它们之间的演化关系，分为有监督学习，无监督学习，强化学习3大类。右半部分列出了典型算法的总结比较，包括算法的核心点如类型，预测函数，求解的目标函数，求解算法。

理解和记忆这张图，对你系统化的掌握机器学习与深度学习会非常有帮助！

我们知道，整个机器学习算法可以分为有监督学习，无监督学习，强化学习3大类。除此之外还有半监督学习，但我们可以把它归到有监督学习中。算法的演变与发展大多在各个类的内部进行，但也可能会出现大类间的交叉，如深度强化学习就是深度神经网络与强化学习技术的结合。

根据样本数据是否带有标签值（label），可以将机器学习算法分成有监督学习和无监督学习两类。如果要识别26个英文字母图像，我们要将每张图像和它是哪个字符即其所属的类型对应起来，这个类型就是标签值。

有监督学习（supervised learning）的样本数据带有标签值，它从训练样本中学习得到一个模型，然后用这个模型对新的样本进行预测推断。它的样本由输入值x与标签值y组成：

其中x为样本的特征向量，是模型的输入值；y为标签值，是模型的输出值。标签值可以是整数也可以是实数，还可以是向量。有监督学习的目标是给定训练样本集，根据它确定映射函数：

确定这个函数的依据是函数能够很好的解释训练样本，让函数输出值f(x)与样本真实标签值y之间的误差最小化，或者让训练样本集的对数似然函数最大化。这里的训练样本数是有限的，而样本所有可能的取值集合在很多情况下是一个无限集，因此只能从中选取一部分样本参与训练。

日常生活中的很多机器学习应用，如垃圾邮件分类，手写文字识别，人脸识别，语音识别等都是有监督学习。这类问题需要先收集训练样本，对样本进行进行标注，用标注好的训练样本训模型，然后根据模型对新的样本进行预测。

无监督学习（unsupervised learning）对没有标签的样本进行分析，发现样本集的结构或者分布规律。无监督学习的典型代表是聚类和数据降维。

强化学习是一类特殊的机器学习算法，它根据输入数据确定要执行的动作，在这里。输入数据是环境参数。和有监督学习算法类似，这里也有训练过程中。在训练时，对于正确的动作做出奖励，对错误的动作做出惩罚，训练完成之后就用得到的模型进行预测。

在有监督学习算法中，我们列出了5个分支：

分别是决策树，贝叶斯，线性模型，kNN，LDA（线性判别分析），集成学习。LDA也可以归类到线性模型中，但因为它是一种有监督的投影技术，我们单独列出。

决策树是一种基于规则的方法，它的规则是通过训练样本学习得到的，典型的代表是ID3，C4.5，以及分类与回归树。

集成学习是机器学习中一类重要的算法，它通过将多个简单的模型进行集成，得到一个更强大的模型，简单的模型称为弱学习器。决策树与集成学习算法相结合，诞生了随机森林，Boosting这两类算法（事实上，Boosting算法的弱学习器不仅可以用决策树，还可以用其他算法）。

线性模型是最大的一个分支，从它最后衍生除了一些复杂的非线性模型。如果用于分类问题，最简单的线性模型是线性回归，加上L2和L1正则化项之后，分别得到岭回归和LASSO回归。对于分类问题，最简单的是感知器模型，从它衍生出了支持向量机，logistic回归，神经网络3大分支。而神经网络又衍生出了各种不同的结构。包括自动编码器，受限玻尔兹曼机，卷积神经网络，循环神经网络，生成对抗网络等。当然，还有其他一些类型的神经网络，因为使用很少，所以在这里不列出。

kNN算法基于模板匹配的思想，是最简单的一种机器学习算法，它依赖于距离定义，而距离同样可以由机器学习而得到，这就是距离度量学习。

贝叶斯也是有监督学习算法中的一个大分支，最简单的是贝叶斯分类器，更复杂的有贝叶斯网络。而贝叶斯分类器又有朴素贝叶斯和正态贝叶斯两种实现。

接下来说无监督学习，它可以分为数据降维算法和聚类算法两大类。演变关系如下图所示：

无监督的降维算法可以分为线性降维和非线性降维两大类。前者的典型代表是主成分分析（PCA），通过使用核技术，可以把它扩展为非线性的版本。流形学习是非线性降维技术的典型实现，代表性的算法有局部线性嵌入（LLE），拉普拉斯特征映射，等距映射，局部保持投影，它们都基于流形假设。流形假设不仅在降维算法中有用，在半监督学习、聚类算法中同样有使用。

聚类算法可以分为层次距离，基于质心的聚类，基于概率分布的距离，基于密度的聚类，基于图的聚类这几种类型。它们从不同的角度定义簇（cluster）。基于质心的聚类典型代表是k均值算法。基于概率分布的聚类典型代表是EM算法。基于密度的聚类典型代表是DBSCAN算法，OPTICS算法，Mean shift算法。基于图的聚类典型代表是谱聚类算法。

强化学习是机器学习中的一个特殊分支，用于决策、控制问题。这类算法的演变关系如下图所示：

整个强化学习的理论模型可以抽象成马尔可夫决策过程。核心任务是求解使得回报最大的策略。如果直接用动态规划求解，则有策略迭代和价值迭代两类算法。他们都要求有精确的环境模型，即状态转移概率和奖励函数。如果做不到这一点，只能采用随机算法，典型的代表是蒙特卡罗算法和时序差分算法。强化学习与深度学习相结合，诞生了深度强化学习算法，典型代表是深度Q网络（DQN）以及策略梯度算法（策略梯度算法不仅可用神经网络作为策略函数的近似，还可以用其他函数）。

下面我们来分别介绍每种算法的核心知识点以及它们之间的关系。

01 有监督学习

先看有监督学习算法，它是当前实际应用中使用最广的机器学习算法。进一步可以分为分类问题与回归问题两大类。前面说过，有监督学习算法的预测函数为：

即根据输入数据x预测出输出数据y。如果y是整数的类别编号，则称为分类问题；如果y是实数值，则为回归问题。

1. 贝叶斯分类器

分类问题中样本的特征向量取值x与样本所属类型y具有因果关系。因为样本属于类型y，所以具有特征值x。分类器要做的则相反，是在已知样本的特征向量为x的条件下反推样本所属的类别y。根据贝叶斯公式有：

只要知道特征向量的概率分布p(x)，每一类出现的概率p(y)，以及每一类样本的条件概率p(x|y)，就可以计算出样本属于每一类的概率p(y|x)。如果只要确定类别，比较样本属于每一类的概率的大小，找出该值最大的那一类即可。因此可以忽略p(x)，因为它对所有类都是一样的。简化后分类器的判别函数为：

训练时的目标是确定p(x|y)的参数，一般使用最大似然估计。如果假设样本特征向量的各个分量之间相互独立，则称为朴素贝叶斯分类器。如果假设特征向量x服从多维正态分布，则称为正态贝叶斯分类器。正态贝叶斯分类器的预测函数为：

贝叶斯分类器是一种生成模型，是非线性模型，它天然的支持多分类问题。下图是正态贝叶斯分类器对异或问题的分类结果（来自SIGAI云端实验室）：

2. 决策树家族

决策树是基于规则的方法，它用一组嵌套的规则进行预测，在树的每个决策节点处，根据判断结果进入一个分支，反复执行这种操作直到到达叶子节点，得到决策结果。决策树的这些规则通过训练得到，而不是人工制定的。下图是决策树的一个例子：

决策树是一种判别模型，也是非线性模型，天然支持多类分类问题。它既可以用于分类问题，也可以用于回归问题，具有很好的解释性，符合人类的思维习惯。常用的决策树有ID3，C4.5，分类与回归树（CART）等。

分类树对应的映射函数是多维空间的分段线性划分，即用平行于各个坐标轴的超平面对空间进行切分；回归树的映射函数是一个分段常数函数。决策树是分段线性函数但不是线性函数，它具有非线性建模的能力。只要划分的足够细，分段常数函数可以逼近闭区间上任意函数到任意指定精度，因此决策树在理论上可以对任意复杂度的数据进行分类或者回归。

下图是决策树进行空间划分的一个例子。在这里有红色和蓝色两类训练样本，用下面两条平行于坐标轴的直线可以将这两类样本分开（来自SIGAI云端实验室）：

这个划分方案对应的决策树如下图所示：

对于分类与回归树，训练每个节点时的目标是要让Gini不纯度最小化，这等价于让下面的值最大化：

决策树训练求解时采用了枚举搜索和贪婪法的思想，找到的不一定是结构最优的树。如果想要了解决策树的原理，请阅读SIGAI之前的公众号文章“理解决策树”。

3. kNN算法

kNN算法基于以下思想：要确定一个样本的类别，可以计算它与所有训练样本的距离，然后找出和该样本最接近的k个样本，统计这些样本的类别进行投票，票数最多的那个类就是分类结果。因为直接比较样本和训练样本的距离，kNN算法也被称为基于实例的算法，这实际上是一种模板匹配的思想。

下图是使用k近邻思想进行分类的一个例子：

在上图中有红色和绿色两类样本。对于待分类样本即图中的黑色点，我们寻找离该样本最近的一部分训练样本，在图中是以这个矩形样本为圆心的某一圆范围内的所有样本。然后统计这些样本所属的类别，在这里红色点有12个，圆形有2个，因此把这个样本判定为红色这一类。上面的例子是二分类的情况，我们可以推广到多类，k近邻算法天然支持多类分类问题，它是一种判别模型，也是非线性模型。下图是kNN算法对异或问题的分类结果（来自SIGAI云端实验室）：

kNN算法依赖于样本距离值，常用的距离有欧氏距离，Mahalanobis距离等。这些距离定义中的参数可以通过学习得到，如Mahalanobis距离中的矩阵S，这称为距离度量学习。

4. 线性模型家族

线性模型的预测函数是线性函数，既可以用于分类问题，也可以用于回归问题，这是机器学习算法中的一个庞大家族。从线性模型中衍生出了多种机器学习算法，对于回归问题问题，有岭回归，LASSO回归；对于分类问题，有支持向量机，logistic回归，softmax回归，人工神经网络（多层感知器模型），以及后续的各种深度神经网络。

对于分类问题，线性模型的预测函数为：

其中sgn是符号函数。最简单的线性分类器是感知器算法，它甚至无法解决经典的异或问题，不具有太多的实用价值。

对于回归问题，线性模型的预测函数为：

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

可以证明，这是一个凸优化问题，可以得到全局极小值。求解时可以采用梯度下降法或者牛顿法。

岭回归是线性回归的L2正则化版本，训练时求解的问题为：

如果系数，这个问题是一个严格凸优化问题，可用用梯度下降法，牛顿法求解。

LASSO回归是线性回归的L1正则化版本，训练时求解的问题为：

同样的，这是一个凸优化问题，可以用梯度下降法和牛顿法求解。

线性判别分析（LDA）是一种有监督的线性投影技术，它寻找向低维空间的投影矩阵W，样本的特征向量x经过投影之后得到的新向量y：

投影的目标是同一类样投影后的结果向量差异尽可能小，不同类的样本差异尽可能大。直观来看，就是经过这个投影之后同一类的样本进来聚集在一起，不同类的样本尽可能离得远。下图是这种投影的示意图：

训练时的求解目标是最大化类间差异与类内差异的比值：

最后归结为求解矩阵的特征值和特征向量：

如果我们要将向量投影到c-1维，则挑选出最大的c-1个特征值以及它们对应的特征向量，组成矩阵W。线性判别分析不能直接用于分类问题，它只是完成投影，投影之后还需要用其他算法进行分类，如kNN。下图是LDA降维之后用最小距离分类器分类的结果：

从这张图可以看出，决策面是直线。LDA是一种线性模型，也是判别模型，只能用于分类问题。

logistic回归即对数几率回归，它的名字虽然叫“回归”，但却是一种用于二分类问题的分类算法，它用sigmoid函数估计出样本属于某一类的概率。这种算法可以看做是对线性分类器的改进。

预测函数为：

其中为线性映射权向量，由训练算法确定。训练时的优化目标是最大化对数似然函数：

这是一个凸优化问题，可以得到全局最优解，求解时可以采用梯度下降法或者牛顿法。分类时的判断规则为：

logistic回归是一种判别模型，也是线性模型，它只支持二分类问题。下图是用logistic回归进行分类的结果（来自SIGAI云端实验室）：

从上图可以看到，分界面是一条直线，这也说明了它是一个线性模型。

logistic回归只能用于二分类问题，将它进行推广可以得到处理多类分类问题的softmax回归。softmax回归按照下面的公式估计一个样本属于每一类的概率：

模型的输出为一个k维向量，其元素之和为1，每一个分量为样本属于该类的概率。训练时的损失函数定义为：

上式是对logistic回归损失函数的推广。这个损失函数是凸函数，可以采用梯度下降法求解。Softmax回归是一种判别模型，也是线性模型，它支持多分类问题。

5. 支持向量机

支持向量机是对线性分类器的改进，加上了最大化分类间隔的约束，另外还使用了核技术，通过非线性核解决非线性问题。一般情况下，给定一组训练样本可以得到不止一个可行的线性分类器，下图就是一个例子：

在上图中两条直线都可以将两类样本分开。问题是：在多个可行的线性分类器中，什么样的分类器是好的？为了得到好的泛化性能，分类平面应该不偏向于任何一类，并且离两个类的样本都尽可能的远。这种最大化分类间隔的目标就是支持向量机的基本思想。支持向量机在训练时优化的目标是让训练样本尽量分类正确，而且决策面离两类样本尽可能远。原问题带有太多的不等式约束，一般转化为对偶问题求解，使用拉格朗日对偶，加上核函数之后，优化的对偶问题为：

预测函数为：

这是一个凸优化问题，可以得到全局最优解，求解时一般采用SMO算法，这是一种分治法，每次挑选出两个变量进行优化，对这两个变量的优化问题求公式解。优化变量的选择使用了KKT条件。

支持向量机是一种判别模型，既支持分类问题，也支持回归问题，如果使用非线性核，则是一种非线性模型，这从它的预测函数也可以看出来。标准的支持向量机只能解决二分类问题，通过多个二分类器组合，可以解决多分类问题，另外一种思路是直接构造多类的损失函数来解决多分类问题。下图是用支持向量机对异或问题进行分类的结果（来自SIGAI云端实验室）：

6. 神经网络

人工神经网络是一种仿生方法，受启发于人脑的神经网络。从数学上看，它本质上是一个多层复合函数。如果使用sigmoid作为激活函数，它的单个神经元就是logistic回归。假设神经网络的输入是n维向量x，输出是m维向量y，它实现了如向量到向量的映射：

将这个函数记为：

神经网络第层的变换写成矩阵和向量形式为：

如果采用欧氏距离，训练时的优化目标为：

这不是一个凸优化问题，因此不能保证得到全局极小值。可以采用梯度下降法求解，因为是一个复合函数，需要对各层的权重与偏置求导，采用了反向传播算法，它从多元函数求导的链式法则导出。误差项的计算公式为，对于输出层：

对于隐含层：

根据误差项可以得到权重和偏置的梯度值：

然后用梯度下降法更新。神经网络是一个判别模型，并且是非线性模型，它既支持分类问题，也支持回归问题，并且支持多分类问题。下图是用神经网络对异或问题的分类结果（来自SIGAI云端实验室）：

7. 深度神经网络家族

深度神经网络是对多层感知器模型的进一步发展，它可以完成自动的特征提取，端到端的训练，是深度学习的核心技术。可以分为自动编码器，受限玻尔兹曼机，卷积神经网络，循环神经网络，生成对抗网络这几种类型。

自动编码器用一个单层或者多层神经网络对输入数据进行映射，得到输出向量，作为从输入数据提取出的特征。在这种框架中，神经网络的前半部分称为编码器，用于从原始输入数据中提取特征；后半部分称为解码器，训练时根据提取的特征重构原始数据，它只