3.2.1 常见的监督学习算法
本节详细介绍几种常见的监督学习算法。上述介绍中，监督学习是指利用一组已知标签的样本来调整模型的参数，使其达到所要求性能的过程。在监督学习中，一个训练样本代表一个实例，每个实例都是由一个输入对象（通常为矢量）和一个期望的输出值（也称为监督信号）组成的。
常见的监督学习算法有决策树、逻辑回归、支持向量机、神经网络等。
1.决策树
决策树（Decision Tree）是一种基本的分类与回归算法。本节只介绍分类决策树。在分类问题中，基于特征对实例进行分类的过程，可以认为是if-else的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。举一个简单的例子，在邮件系统中，我们需要做一个分类功能，将所有邮件分成需及时处理的邮件，无聊时阅读的邮件，垃圾邮件。
那么，如果发送邮件域名地址包含Serverless.cn，我们就认为它是需要及时处理的邮件；在其余邮件中如果内容字数大于100，就将其作为无聊时阅读的邮件；剩下的全部邮件当作垃圾邮件。这样，简单的决策树就构造完成了。该决策树的流程如图3-4所示。
图3-4 邮件决策树流程
图3-4中，决策树包含一个根节点、若干个内部节点和若干个叶子节点，其中根节点包含样本全集，叶子节点对应决策结果（需及时处理的邮件、无聊时阅读的邮件、垃圾邮件），其他每个节点对应一个属性（如内容字数大于100）。每个非叶子节点包含的样本集合根据属性测试结果被划分到子节点。从根节点到每个叶子节点的路径对应一个判定测试序列。
而现实中的数据量往往是很大的，数据特征也并非两个，且无法判断当前节点该用什么特征，这时候决策树的构造算法应运而生。构造算法会递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类。这个过程对应着对特征空间的划分，也对应着决策树的构建。
以邮件系统决策树的构造为例，是否可以将“内容字数大于100”这个特征作为第一个分裂节点呢？发送邮件域名中包含Serverless.cn的邮件中内容字数可能大于100也可能小于100，用“内容字数大于100”先来决定该邮件属于“无聊时阅读的邮件”或者“垃圾邮件”都可能错过需要及时处理的邮件，导致分类错误率提高。而当在“内容字数大于100”特征下的每个节点里都判断一次“发送邮件域名中包含Serverless.cn”，分类错误率将明显小于直接通过“内容字数大于100”进行分类的错误率。所以，在满足一定树深度的前提下，递归地将节点进行分裂，得到所有可能的节点情况，找到最小的错误率，也就找到了当下最合理的分类。
经典的决策树构造算法有ID3、C4.5和CART（Classification And Regression Tree），分别用不同的方法判断节点的分裂，如熵、信息增益等。决策树的优点是计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据；缺点是可能产生过度匹配问题。
2.逻辑回归
（1）逻辑回归基本表达式
在决策树小节讨论的邮件分类，实际上是一个分类问题。分类问题遍布在现实生活的方方面面，比如银行通过一系列数据判断某贷款是否有风险，医院通过血液、彩超、心电图等数据判断病患是否属于某种疾病等。在以上例子中预测的都是二值变量，如贷款无风险和有风险、患有某种疾病和没有患这个疾病。这里将二值类别分别定义为正类（Positive Class）和负类（Negative Class）。那么，如何解决这类问题呢？本节介绍一个原理简单却是二分类问题中最流行的机器学习方法——逻辑回归（Logistic Regression）。
逻辑回归虽然被称为回归，但其实际上是分类模型，并常用于二分类问题。逻辑回归因其简单、可并行化、可解释性强而在工业界得到广泛应用。逻辑回归包含如下几个步骤。
·寻找预测函数；
·构造损失函数；
·损失函数最小化。
在逻辑回归算法中，第一步是寻找预测函数，即对于在多维空间存在的样本点，用特征的线性组合（特征加权）去拟合空间中点的分布和轨迹。假设一份有监督训练数据集（X, Y），X表示特征，x为X的一个子集，Y表示标签，θ表示该某一特征对应的权重，得到一个简单的线性模型公式：
这样的线性模型可以拟合数据点，但无法做出分类，如图3-5所示。
图3-5 线性回归对数据点的拟合
在逻辑回归的二分类场景中，将正类用1替代，负类用0替代，且通常使用sigmoid函数对线性回归的结果进行处理，使得线性回归的所有数值在0到1之间。sigmoid的函数公式如下：
图3-6 sigmoid函数
sigmoid函数是一个漂亮的S形，值域在0到1之间。当z=0时，它的值刚好为0.5；当z为正无穷大时，它的值无限接近1；反之，值无限接近0。sigmoid函数如图3-6所示。
在sigmoid函数里，代入线性回归公式就可以得到如下基本的逻辑回归算法表达式：
在逻辑回归算法中，还需要定义一个阈值来确定当前的分类结果。如阈值设置为0.5，那么当结果大于0.5的时候，判断样本为正类；小于0.5时，判断样本为负类。
逻辑回归算法的优点是计算代价不高，易于理解和实现，同样其缺点也是比较明显的，包括容易欠拟合、分类精度可能不高等。下面介绍如何使逻辑回归算法的损失函数最小化。
（2）逻辑回归算法训练
有了模型的预测函数，模型的权重还需要通过训练得到，而训练的关键莫过于损失函数训练，因为它决定了模型权重拟合数据的方向。在决策树中，我们用熵、信息增益等来判断节点分裂的时机，在逻辑回归中也需要一个方法来判断模型是否训练完成，即是如何拟合逻辑回归中模型的参数θ。
机器学习中有许多损失函数，如对数损失、平方差损失、hinge损失等。逻辑回归中常用对数损失函数。对数损失函数表达式如下：
其代价函数（Cost Function）表达式如下：
其中，y的取值是0和1，逻辑回归的预测函数取值在0到1之间，损失函数Loss越小，就表示逻辑回归的预测函数越接近数据集标注y，即模型的权重随着训练逐渐拟合数据。显然，逻辑回归算法的优化目标就是最小化损失函数。
在机器学习中，常用梯度下降法（Gradient Descent）、牛顿法等优化方法来使得模型权重达到最优。在逻辑回归中，常用的优化方法是梯度下降法。梯度下降又叫作最速梯度下降，是一种迭代求解的方法，通过在每一步选取使目标函数变化最快的一个方向调整参数的值来逼近最优值。目标函数变化最快的方向即目标函数的梯度方向（即对目标函数的求导结果），求导公式如下：
最终权重的更新公式为：
沿梯度负方向选择一个较小的步长可以保证损失函数是减小的。另外，逻辑回归的损失函数是凸函数，可以保证算法找到的局部最优值同时是全局最优值。
3.支持向量机
支持向量机（Support Vector Machine，SVM）和逻辑回归一样，也是用于分类的一种算法。它的基本模型是定义在特征空间的间隔最大的线性分类器。SVM可以分为很多种，如线性支持向量机、近似线性支持向量机、非线性支持向量机。
（1）线性支持向量机
一个分类模型不仅可将不同类别的样本分隔开，还要以比较大的置信度来分隔这些样本，这样才能使绝大部分样本被分开。比如当通过一个平面将两个类别的样本分开，如果这些样本是线性可分（或者近似线性可分），那么这样的平面有很多，但如果加上以最大的置信度将这些样本分开，那么这样的平面只有一个。怎么才能找到这样的平面呢？这就需要用到SVM算法了。
间隔最大化指找到距离分隔平面最近的点，并且使得距离平面最近的点尽可能地距离平面最远。这样，每一个样本就都能够以比较大的置信度被分隔开，算法的分类预测能力也就越好。显然，SVM算法的关键所在，就是找到使得间隔最大的分隔超平面（如果特征是高维度的，我们称这样的平面为超平面）。
如图3-7所示，假设一个超平面可以将所有的样本分为两类，位于左侧的样本为一类，值为+1，而位于右侧的样本为另外一类，值为-1。假设存在函数：
对于正侧的数据，有xwT+b≥1。其中，至少有一个点xi能使得f(xi)=1，这个点被称为最近点。对于负侧的数据，有xwT+b≤-1。其中，至少有一个点xi能使得f(xi)=-1，这个点被称为最近点。于是，将上面两个约束条件合并为：yi f(xi)=yi(xwT+b)≥1，其中yi是点xi对应的分类值（-1或者1，这也是将二分类类别不定义为0和1的原因，即为了方便公式的转换）。超平面函数是xwT+b=0。
图3-7 支持向量机分隔超平面
SVM的优化目标是最大化样本点到分离超平面的最小间隔，以此构建算法的目标函数。通过转换，目标函数公式为：
其中，y为分类类别，w和b为权重，x为样本点。于是，只需要求得最优w和b就能找到间隔最大分离超平面。求解w和b的过程是凸二次规划问题。凸二次规划问题是指目标函数是一个需要最大化或最小化多个变量的二次函数，且它是一个凸函数，约束函数为仿射函数（满足f(x)=ax+b，a和x均为n维向量）。一般地，求解凸二次规划问题可以利用对偶算法，即引入拉格朗日算子。利用拉格朗日对偶性将原始问题的最优解问题转化为拉格朗日对偶问题，求出对应的参数w和b，从而找到这样的间隔最大超平面，进而利用该平面完成样本分类。最终可以将目标函数转换为如下公式：
可见，使用拉格朗日和KKT条件后，求w、b的问题变成了求拉格朗日乘子ai的问题。ai可以直接应用到分类器中，并且支持数据集非线性情况。
（2）其他支持向量机
当数据集并不是严格线性可分时，即满足绝大部分样本点线性可分，极少部分异常，也就是说存在部分样本不能满足约束条件，此时我们可以引入松弛因子。这样，这些样本点到超平面的距离加上松弛因子Sigma，就能保证被超平面分隔开来。这类SVM叫作近似线性支持向量机。
而当数据集不是线性可分的，即不能通过前面的线性模型对数据集进行分类，我们就需要用到非线性支持向量机。在数据集不是线性可分的情况下，我们必须想办法使这些样本特征符合线性模型，这样才能通过线性模型对这些样本进行分类。这就要用到核函数。核函数的功能就是将低维特征空间映射到高维特征空间。在高维特征空间，这些样本经过转化后变得线性可分。这样，在高维特征空间，我们就能够利用线性模型来解决数据集分类问题。利用核函数解决非线性问题的SVM叫作非线性支持向量机。
4.神经网络
神经网络方面的研究很早就出现了，今天“神经网络”已是一个相当大、多学科交叉的技术领域。相关学科对神经网络的定义不同，这里采用目前使用最广泛的定义，即神经网络是由具有适应性的、简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界体所做出的交互反应。从组成来看，神经网络最基本的组成成分为神经元，这也对应了神经网络一词中的“神经”，而“网络”顾名思义就是由这些神经元组成的广泛并行互连的网络。
神经网络的提出也是得益于生物神经网络的思考，模拟的是生物大脑的网络处理方式。在生物神经网络中，每个神经元互连。当神经元接收到外部输入，且电位较高时，神经元处于兴奋状态，会向其他神经元传递化学物质。
1943年，McCulloch和Pitts将上述描述抽象为图3-8所示的简单模型，这就是沿用至今的M-P神经元模型。神经元接收到来自其他神经元传递来的输入信号（这些输入信号通过带权重的连接进行传递）。神经元接收到的输入值和神经元的阈值进行对比，通过激活函数产生神经元的输出。
图3-8 M-P神经元模型
假设神经元电位高于某个阈值时会处于兴奋状态，则对于每个神经元，我们可以通过将神经元输入线性组合，减去该阈值来作为函数变量的函数，最终量化其是否处于兴奋状态。这个函数被称为激活函数。理想的激活函数应当是阶跃函数，因为阶跃函数能够将输入值映射为0或1，这两个输出结果很好地对应了“兴奋”与“抑制”状态。但是由于阶跃函数具有不连续、不光滑等不太友好的数学性质，会导致后期最优解问题变得棘手，故神经网络中的激活函数不采用阶跃函数，而是采用Sigmoid函数，如图3-9所示。
图3-9 神经网络中的激活函数
将多个神经元按一定的层次结构连接起来，就得到了神经网络。它是一种包含多个参数的模型，比如10个神经元两两连接，则有100个参数需要学习（每个神经元有9个连接权以及1个阈值），若将每个神经元看作一个函数，则整个神经网络就是由这些函数相互嵌套而成的。
基于神经网络衍生出目前最常用、最流行的几种网络结构：全连接神经网络、卷积神经网络（Convolutional Neural Network，CNN）、循环神经网络（Recurrent Neural Network，RNN）。它们都具有不同的连接规则。
（1）全连接神经网络
首先介绍全连接神经网络的结构。
在介绍全连接神经网络前，先介绍一下它的前身：感知机（Perceptron）。感知机是由两层神经元组成的一个简单模型，但只有输出层是M-P神经元（即只有输出层神经元进行激活函数处理，也被称为功能神经元）；输入层只是接收外界信号（样本属性）并传递给输出层（输入层的神经元个数等于样本的属性数目），而没有激活函数。这样，感知机与之前线性模型中的对数几率回归的思想基本是一样的，都是通过对属性加权与另一个常数求和，再使用Sigmoid函数将输出值压缩到0～1之间，从而解决分类问题。不同的是，感知机的输出层可以有多个神经元，从而可以解决多分类问题。
实际上，感知机的学习能力非常有限，只有一层功能神经元，只能解决部分线性可分问题。对于线性可分问题，感知机一定会收敛并找到一个适当的权重。但是对于非线性可分问题，感知机学习过程将发生震荡，权重难以稳定。对于这类非线性可分问题，考虑使用多层神经元，即在感知机的输入层和输出层之间再加入一层神经元，这层神经元被称为隐藏层。
一般情况下，常见的神经元是图3-10所示的层级结构。每层神经元都与下一层神经元相互连接，同层神经元之间互不连接，这样的网络结构被称为全连接神经网络。在全连接神经网络中，输入层接收外界数据的输入，隐藏层对输入数据进行处理、加工，输出层对隐藏层的数据进行处理、加工，并输出最终结果。连接每个神经元之间的“线”被称作“连接权”，即模型的权重。神经网络学习过程中根据训练数据来调整权重，即神经网络学到的东西都蕴含在权重中。
综上所述，全连接神经网络具备的特点非常明显：每一层是全连接层，即每一层的每个神经元与上一层所有神经元都有连接。
接着介绍神经网络的训练算法。
神经网络学习到的东西都包含在权重里，那么权重取什么值合适呢？这里以全连接神经网络为例介绍神经网络的训练算法：反向传播算法（Back Propagation，BP）。它是迄今为止最成功、最主流的神经网络学习算法，不管是TensorFlow、PyTorch还是Caffe等框架都是使用反向传播算法进行训练的。
图3-10 全连接神经网络
图3-11给出了反向传播算法的工作流程。对于每个训练样本，反向传播算法执行以下操作：先进行前向传播，将输入样本传到网络的输入层，隐藏层依次计算，并得到输出层的输出结果；然后计算输出层神经元的误差，将误差反向传递到隐藏层神经元，计算出所有隐藏层的误差，将误差对权重和偏置求偏导，计算出所有的梯度；最后根据隐藏层神经元的梯度对权重和偏置进行调整。这个过程迭代进行，直到达到某个停止条件，如训练误差低于某个阈值，或者模型精度高于某个阈值。
图3-11 全连接神经网络的反向传播算法
（2）卷积神经网络
卷积神经网络是一类包含卷积计算且具有深度结构的前馈神经网络（Feedforward Neural Network），是深度学习的代表算法之一。卷积神经网络具有表征学习（Representation Learning）能力，能够按其阶层结构对输入信息进行平移不变分类（Shift-invariant Classi-fication），因此也被称为“平移不变人工神经网络（Shift-Invariant Artificial Neural Network，SIANN）”。
卷积神经网络的研究始于20世纪80～90年代。时间延迟网络和LeNet-5是最早出现的卷积神经网络。21世纪后，随着深度学习理论的提出和数值计算设备的改进，卷积神经网络得到了快速发展，并被应用于计算机视觉、自然语言处理等领域。卷积神经网络仿造生物的视知觉（Visual Perception）机制构建，可以进行监督学习和非监督学习。其隐藏层内的卷积核参数共享和层间连接的稀疏性使得卷积神经网络能够以较小的计算量对格点化（Grid-like Topology）特征，例如像素和音频特征进行学习并得到稳定的效果，且对数据没有额外的特征工程（Feature Engineering）要求。
常规的卷积神经网络是由若干卷积计算层、采样层、全连接层组成的，其中卷积层是卷积神经网络最重要的层，也是“卷积神经网络”名字的由来。
图3-12为基于卷积神经网络的手写数字识别任务。其中，网络输入为像素为32×32的手写数字图像，输出为识别到的结果，多个卷积层和池化层对输入数据进行处理，最后由连接层输出。可以发现，卷积神经网络的层结构和全连接神经网络的层结构有很大不同。全连接神经网络每层神经元是一维结构，也就是排成一条线的样子；而卷积神经网络每层神经元是三维结构，也就是排成一个长方体的样子，有宽度、高度和深度。
每个卷积层包含多个特征映射（Feature Map）。每个特征映射是一个由多个神经元构成的“平面”，并通过卷积滤波器提取特征。在图3-12中，第一个卷积层是由6个特征映射组成的，每个特征映射是28×28的神经元矩阵，其中的每个神经元负责从5×5的区域通过滤波器提取输入数据的局部特征，即当前的28×28神经元矩阵都是由输入层的5×5区域计算得到的。这个5×5区域也叫作神经元的感受野（Receptive Field）。
采样层也叫作池化层（Pooling Layer）。其作用是基于局部相关性原理进行下采样，从而在减少数据量的同时保留有用的信息。例如在图3-12中，第一个采样层有6个14×14的特征映射，其中每个神经元都和上一层的2×2区域相连，并计算输出。采样层中没有需要学习的参数，同时可将上一层的输出特征映射大小降低，从而达到减少后续网络参数量的作用。通过若干层卷积层和采样层的组合，图3-12中的卷积神经网络将原始的图像映射成了120维的特征向量，最后由84个神经元组成的连接层和输出层完成识别任务。
综上所述，卷积神经网络具有的特点非常明显。卷积层：相当于滤镜，将图片进行分块，对每一块进行特征处理，从而提取特征；池化层：通过对提取的高维特征进行降维；连接层：对空间排列的特征转化成一维的向量。卷积神经网络常用的场景有目标检测、图像分类、语义分割等。
图3-12 基于卷积神经网络的手写数字识别任务
（3）循环神经网络
循环神经网络是一类以序列数据为输入，在序列的演进方向进行递归且所有节点（循环单元）链式连接的递归神经网络（Recursive Neural Network）。
循环神经网络的研究始于20世纪80～90年代，并在21世纪初发展为深度学习算法之一。其中，双向循环神经网络（Bidirectional RNN，Bi-RNN）和长短期记忆网络（Long Short-Term Memory network，LSTM）是常见的循环神经网络。循环神经网络具有记忆性、参数共享且图灵完备（Turing Completeness，指具有无限存储能力）等特点，因此在对序列的非线性特征进行学习时具有一定优势。循环神经网络在自然语言处理（Natural Language Processing，NLP），例如语音识别、语言建模、机器翻译等领域有广泛应用，也被用于各类时间序列预报。结合卷积神经网络构建的循环神经网络可以处理包含序列输入的计算机视觉问题。
循环神经网络的单个神经元模型如图3-13所示。与以往的神经元相比，它包含一个反馈输入。如果将其按照时间变化展开可以看到，循环神经网络单个神经元类似一系列权值共享前馈神经元的依次连接，连接后同传统神经元相同随着时间的变化输入和输出会发生变化，不同的是循环神经网络上一时刻神经元的历史信息会通过权值与下一时刻的神经元相连接，这样循环神经网络在t时刻的输入与输出的映射参考了t时刻之前所有输入数据对网络的影响，形成了反馈网络结构。虽然反馈结构的循环神经网络能够参考背景信息，但常见的信号所需要参考的背景信息与目标信息时间相隔可能非常大，理论上循环神经网络可以参考当时时刻之前任意时间范围内的背景信息，但实际应用过程中对于较长时间间隔的背景信息通常无法参考。
上述提到的较长时间间隔的背景信息之所以无法参考，原因主要在于网络训练时需要计算代价函数梯度，而梯度计算与神经元之间连接的权值密切相关，在训练过程中很容易造成梯度爆炸或者梯度消失。常见的网络训练算法以反向传播算法或者实时递归学习算法为主。随着时间推移数据量逐步增加以及网络隐藏层神经元自身循环问题，这些算法的误差在按照时间反向传播时会产生误差指数式增长或者梯度消失问题。由于时间延迟越来越长，参考的信号也越来越多，这样权值数量也会出现激增，最终很小的误差经过大量的权值加和之后出现指数式增长，以至于无法训练或者训练时间过长。梯度消失问题指网络刚开始输入的具有参考价值的数据，随着时间推移新输入网络的数据会取代网络先前的隐藏层参数导致最初的有效信息逐步被“忘记”，如果以颜色深浅代表数据信息的有用程度，那么随着时间推移数据信息的有用性将逐步淡化。这两种问题都会导致网络模型产生缺陷，无法参考时间间隔较长的序列状态，最终在分类识别类似的应用中仍旧无法获得好的实践效果。
图3-13 循环神经网络
综上所述，循环神经网络具有的特点非常明显：中间层的输出作为输入和下一个样本数据一起作为输入，也叫循环层；具有记忆样本之间相关联系的能力。循环神经网络常见的应用场景为文本填充、语音识别等。