二、线性模型

线性模型（LinearModel）是机器学习中应用最广泛的模型，指通过样本特征的线性组合来进行预测的模型．给定一个𝐷维样本，其线性组合函数为

其中为𝐷维的权重向量，𝑏为偏置．上一章中介绍的线性回归就是典型的线性模型，直接用𝑓(𝒙;𝒘)来预测输出目标𝑦=𝑓(𝒙;𝒘)．

在分类问题中，由于输出目标𝑦是一些离散的标签，而𝑓(𝒙;𝒘)的值域为实数，因此无法直接用𝑓(𝒙;𝒘)来进行预测，需要引入一个非线性的决策函数 （Decision Function）𝑔(⋅)来预测输出目标

 其中𝑓(𝒙;𝒘)也称为判别函数（DiscriminantFunction）．

 对于二分类问题，𝑔(⋅)可以是符号函数（SignFunction），定义为

当𝑓(𝒙;𝒘) = 0时不进行预测．公式(3.5)定义了一个典型的二分类问题的决策函数，其结构如图3.1所示．

在本章，我们主要介绍四种不同线性分类模型：Logistic回归、Softmax回归、 感知器和支持向量机，这些模型的区别主要在于使用了不同的损失函数．

2.1 线性判别函数和决策边界

从公式(3.3)可知，一个线性分类模型（Linear Classification Model）或线性分类器（Linear Classifier），是由一个（或多个）线性的判别函数𝑓(𝒙;𝒘) = 𝒘𝒙 +𝑏和非线性的决策函数𝑔(⋅)组成．我们首先考虑二分类的情况，然后再扩展到多分类的情况．

2.1.1 二分类

二分类（Binary Classification）问题的类别标签𝑦只有两种取值，通常可以设为{+1,−1}或{0,1}．在二分类问题中，常用正例（PositiveSample）和负例（Negative Sample）来分别表示属于类别+1和−1的样本．

在二分类问题中，我们只需要一个线性判别函数𝑓(𝒙;𝒘) = 𝒘𝒙+𝑏．特征空间中所有满足𝑓(𝒙;𝒘) = 0的点组成一个分割超平面（Hyperplane），称为决策边界（Decision Boundary）或决策平面（Decision Surface）． 决策边界将特征空间一分为二，划分成两个区域，每个区域对应一个类别． 所谓“线性分类模型”就是指其决策边界是线性超平面．在特征空间中， 决策平面与权重向量𝒘正交．特征空间中每个样本点到决策平面的有向距离 （Signed Distance）为

𝛾也可以看作点𝒙在𝒘方向上的投影．

图3.2给出了一个二分类问题的线性决策边界示例，其中样本特征向量𝒙 = [𝑥1, 𝑥2]，权重向量𝒘 = [𝑤1,𝑤2]．

给定𝑁个样本的训练集，其中 ∈ {+1,−1}，线性模型试图学习到参数𝒘∗，使得对于每个样本尽量满足

上面两个公式也可以合并，即参数𝒘∗尽量满足

定义3.1 两类线性可分：对于训练集 ，如果存在权重向量𝒘∗，对所有样本都满足𝑦𝑓(𝒙;𝒘∗)>0，那么训练集𝒟是线性可分的．

为了学习参数𝒘，我们需要定义合适的损失函数以及优化方法．对于二分类问题，最直接的损失函数为0-1损失函数，即

其中𝐼(⋅)为指示函数．但0-1损失函数的数学性质不好，其关于𝒘的导数为0，从而导致无法优化𝒘．

2.1.2 多分类

多分类（Multi-class Classification）问题是指分类的类别数𝐶大于2．多分 类一般需要多个线性判别函数，但设计这些判别函数有很多种方式．

假设一个多分类问题的类别为{1,2,⋯,𝐶}，常用的方式有以下三种：

1）“一对其余”方式：把多分类问题转换为𝐶个“一对其余”的二分类问题．这种方式共需要𝐶个判别函数，其中第𝑐个判别函数𝑓𝑐是将类别𝑐的样本和不属于类别𝑐的样本分开．

2）“一对一”方式：把多分类问题转换为𝐶(𝐶−1)/2个“一对一”的二分 类问题．这种方式共需要𝐶(𝐶−1)/2个判别函数，其中第(𝑖,𝑗)个判别函数是把类 别𝑖和类别𝑗的样本分开．

3）“argmax”方式：这是一种改进的“一对其余”方式，共需要𝐶个判别函数

对于样本，如果存在一个类别c，相对于所有的其他类有，那么𝒙属于类别𝑐． “argmax”方式的预测函数定义为

“一对其余”方式和“一对一”方式都存在一个缺陷：特征空间中会存在一些难以确定类别的区域，而“argmax”方式很好地解决了这个问题．图3.3给出了用这三种方式进行多分类的示例，其中红色直线表示判别函数𝑓(⋅) = 0的直线，不同颜色的区域表示预测的三个类别的区域（𝜔1、𝜔2和𝜔3）和难以确定类别的区域（‘?’）．在“argmax”方式中，相邻两类𝑖和𝑗的决策边界实际上是由 决定，其法向量为𝒘𝑖 −𝒘𝑗．

定义3.2 多类线性可分：对于训练集，如果存在𝐶个权重向量,⋯,，使得第𝑐(1 ≤ 𝑐 ≤ 𝐶)类的所有样本都满足, ∀≠ ，那么训练集𝒟是线性可分的

从上面定义可知，如果数据集是多类线性可分的，那么一定存在一个“argmax” 方式的线性分类器可以将它们正确分开．

2.2 Logistic回归

Logistic 回归（Logistic Regression，LR）是一种常用的处理二分类问题的线性模型．在本节中，我们采用𝑦∈{0,1}以符合Logistic回归的描述习惯．

为了解决连续的线性函数不适合进行分类的问题，我们引入非线性函数𝑔∶ →(0,1)来预测类别标签的后验概率𝑝(𝑦=1|𝒙)．

其中𝑔(⋅)通常称为激活函数（ActivationFunction），其作用是把线性函数的值域从实数区间“挤压”到了(0,1)之间，可以用来表示概率．在统计文献中，𝑔(⋅)的逆函数(⋅)也称为联系函数.（LinkFunction）

在Logistic回归中，我们使用Logistic函数来作为激活函数． 标签𝑦=1的后验概率为

为简单起见，这里和分别为𝐷+1维的增广特征向量和增广权重向量．

标签𝑦=0的后验概率为

将公式(3.14)进行变换后得到

 

其中为样本𝒙为正反例后验概率的比值，称为几率（Odds），几率的对数称为对数几率（LogOdds，或Logit）.公式(3.17)中等号的左边是线性函数， 这样Logistic回归可以看作预测值为“标签的对数几率”的线性回归模型．因此， Logistic回归也称为对数几率回归（LogitRegression）．

图3.4给出了使用线性回归和Logistic回归来解决一维数据的二分类问题的示例

2.2.1 参数学习

Logistic 回归采用交叉熵作为损失函数，并使用梯度下降法来对参数进行优化．

给定𝑁个训练样本，用Logistic回归模型对每个样本进行预测，输出其标签为1的后验概率，记为，

由于 ∈ {0,1}，样本(,)的真实条件概率可以表示为

使用交叉熵损失函数，其风险函数为

风险函数ℛ(𝒘)关于参数𝒘的偏导数为

采用梯度下降法，Logistic回归的训练过程为：初始化 ← 0，然后通过下式来迭代更新参数：

其中𝛼是学习率，是当参数为时，Logistic回归模型的输出．

从公式(3.23)可知，风险函数ℛ(𝒘)是关于参数𝒘的连续可导的凸函数．因此除了梯度下降法之外，Logistic回归还可以用高阶的优化方法（比如牛顿法） 来进行优化．

2.3 Softmax回归

Softmax回归（Softmax Regression），也称为多项（Multinomial）或多类 （Multi-Class）的Logistic回归，是Logistic回归在多分类问题上的推广.

对于多类问题，类别标签𝑦∈{1,2,⋯,𝐶}可以有𝐶个取值．给定一个样本𝒙，Softmax回归预测的属于类别𝑐的条件概率为

其中是第𝑐类的权重向量．

Softmax回归的决策函数可以表示为

与Logistic回归的关系当类别数𝐶=2时，Softmax回归的决策函数为

其中𝐼(⋅)是指示函数．对比公式(3.5)中的二分类决策函数，可以发现二分类中的权重向量．

向量表示 公式(3.29)用向量形式可以写为

其中是由𝐶个类的权重向量组成的矩阵，为𝐶维的全1向量，∈为所有类别的预测条件概率组成的向量，第𝑐维的值是第𝑐类的预测条件概率．

2.3.1 参数学习

给定𝑁个训练样本，Softmax回归使用交叉熵损失函数来学习最优的参数矩阵𝑾．

为了方便起见，我们用𝐶维的one-hot向量𝒚 ∈来表示类别标签．对于类别𝑐，其向量表示为

 其中𝐼(⋅)是指示函数．

采用交叉熵损失函数，Softmax回归模型的风险函数为

其中为样本𝒙(𝑛)在每个类别的后验概率． 

风险函数ℛ(𝑾)关于𝑾的梯度为

证明. 计算公式(3.40)中的梯度，关键在于计算每个样本的损失函数 关于参数𝑾 的梯度，其中需要用到的两个导数公式为 

1） 若𝒚=softmax(𝒛)，则 ．

2） 若，则 为第𝑐列为𝒙，其余为0的矩阵．

 根据链式法则，关于𝒘𝑐的偏导数为

公式(3.50)也可以表示为非向量形式，即

其中𝐼(⋅)是指示函数． 

根据公式(3.50)可以得到

采用梯度下降法，Softmax回归的训练过程为：初始化 ←0，然后通过下式进行迭代更新：

 其中𝛼是学习率， 是当参数为𝑾𝑡时，Softmax回归模型的输出．

要注意的是，Softmax回归中使用的𝐶个权重向量是冗余的，即对所有的权重向量都减去一个同样的向量𝒗，不改变其输出结果．因此，Softmax回归往往需要使用正则化来约束其参数．此外，我们还可以利用这个特性来避免计算Softmax函数时在数值计算上溢出问题．

2.4 感知器

感知器是对生物神经元的简单数学模拟，有与生物神经元相对应的部件，如 权重（突触）、偏置（阈值）及激活函数（细胞体），输出为+1或−1．

感知器是一种简单的两类线性分类模型，其分类准则与公式(3.5)相同，即

2.4.1 参数学习

给定𝑁个样本的训练集：，其中 ∈ {+1,−1}，感知器学习算法试图找到一组参数𝒘∗，使得对于每个样本(𝒙(𝑛),𝑦(𝑛))有

感知器的学习算法是一种错误驱动的在线学习算法．先初始化一个权重向量𝒘←0（通常是全零向量），然后每次分错一个样本(𝒙,𝑦) 时，即<0，就用这个样本来更新权重．

具体的感知器参数学习策略如算法3.1所示.

根据感知器的学习策略，可以反推出感知器的损失函数为

采用随机梯度下降，其每次更新的梯度为

图3.5给出了感知器参数学习的更新过程，其中红色实心点为正例，蓝色空心点为负例．黑色箭头表示当前的权重向量，红色虚线箭头表示权重的更新方向．

2.4.3 感知器的收敛性

当数据集是两类线性可分时， 对于训练集，其中𝒙(𝑛)为样本的增广特征向量， ∈ {−1,1}，那么存在一个正的常数𝛾(𝛾 > 0)和权重向量𝒘∗，并且‖𝒘∗‖ = 1，对所有𝑛都满足≥ 𝛾．

定理3.1 感知器收敛性：给定训练集，令𝑅是训练集中最大的特征向量的模，即

如果训练集𝒟线性可分，两类感知器的参数学习算法3.1的权重更新次数不超过

虽然感知器在线性可分的数据上可以保证收敛，但其存在以下不足：

1） 在数据集线性可分时，感知器虽然可以找到一个超平面把两类数据分开，但并不能保证其泛化能力．

2） 感知器对样本顺序比较敏感．每次迭代的顺序不一致时，找到的分割超平面也往往不一致． 3） 如果训练集不是线性可分的，就永远不会收敛．

2.4.3 参数平均感知器

根据定理3.1，如果训练数据是线性可分的，那么感知器可以找到一个判别函数来分割不同类的数据．如果间隔𝛾越大，收敛越快．但是感知器并不能保证找到的判别函数是最优的（比如泛化能力高），这样可能导致过拟合．

感知器学习到的权重向量和训练样本的顺序相关．在迭代次序上排在后面的错误样本比前面的错误样本，对最终的权重向量影响更大．比如有1000个训练样本，在迭代100个样本后，感知器已经学习到一个很好的权重向量．在接下 来的899个样本上都预测正确，也没有更新权重向量．但是，在最后第1000个样本时预测错误，并更新了权重．这次更新可能反而使得权重向量变差．

为了提高感知器的鲁棒性和泛化能力，我们可以将在感知器学习过程中的所有𝐾个权重向量保存起来， 并赋予每个权重向量一个置信系数（1 ≤𝑘 ≤ 𝐾）．最终的分类结果通过这𝐾个不同权重的感知器投票决定，这个模型也称为投票感知器（VotedPerceptron）

令为第𝑘次更新权重时的迭代次数（即训练过的样本数量），为下次权重更新时的迭代次数，则权重的置信系数设置为从到之间间隔的迭代次数，即 =−．置信系数越大，说明权重在之后的训练过程中正确分类样本的数量越多，越值得信赖．

这样，投票感知器的形式为

其中sgn(⋅)为符号函数．

投票感知器虽然提高了感知器的泛化能力，但是需要保存𝐾个权重向量． 在实际操作中会带来额外的开销．因此，常使用简化版本，通过使用“参数平均”的策略来减少投票感知器的参数数量，也叫作平均感知器 （Averaged Perceptron）．平均感知器的形式为

其中𝑇为迭代总回合数，𝒘为𝑇次迭代的平均权重向量．这个方法非常简单，只需要在算法3.1中增加一个𝒘，并且在每次迭代时都更新𝒘： 

但这个方法需要在处理每一个样本时都要更新．因为和都是稠密向量， 所以更新操作比较费时．为了提高迭代速度，有很多改进的方法，让这个更新只需要在错误预测发生时才进行更新． 

算法3.2给出了一个改进的平均感知器算法的训练过程

2.4.4 扩展到多分类

之前介绍的分类模型中，分类函数都是在输入𝒙的特征空间上．为了使得感知器可以处理更复杂的输出，我们引入一个构建在输入输出联合空间上的特征 函数𝜙(𝒙,𝒚)，将样本对(𝒙,𝒚)映射到一个特征向量空间．

在联合特征空间中，我们可以建立一个广义的感知器模型，

其中𝒘为权重向量，Gen(𝒙)表示输入𝒙所有的输出目标集合．

广义感知器模型一般用来处理结构化学习问题．当用广义感知器模型来处理𝐶分类问题时，𝒚∈为类别的one-hot向量表示．在𝐶分类问题中，一种常用的特征函数𝜙(𝒙,𝒚)是𝒙和𝒚的外积，即

其中vec(⋅)是向量化算子，𝜙(𝒙,𝒚)为(𝐷×𝐶)维的向量．

给定样本(𝒙,𝒚)，若𝒙∈，𝒚为第𝑐维为1的one-hot向量，则

广义感知器算法的训练过程如算法3.3所示． 

广义感知器的收敛性

广义感知器在满足广义线性可分条件时，也能够保证在有限步骤内收敛．广 义线性可分条件的定义如下：

定义3.3  广义线性可分： 对于训练集，如果存在一个正的常数𝛾(𝛾 > 0)和权重向量𝒘∗，并且‖𝒘∗‖ = 1，对所有𝑛都满足 ⟨𝒘∗,𝜙(𝒙(𝑛),𝒚(𝑛))⟩ − ⟨𝒘∗,𝜙(𝒙(𝑛),𝒚)⟩ ≥ 𝛾,𝒚 ≠ （ 为样本,的联合特征向量），那么训练集𝒟在联合特征向量空间中是线性可分的．

广义感知器的收敛性定义如下：

定理3.2  广义感知器收敛性：如果训练集是广义线性可分的，并令𝑅是所有样本中真实标签和错误标签在特征空间𝜙(𝒙,𝒚)最远的距离，即

那么广义感知器参数学习算法3.3的权重更新次数不超过．

2.5 支持向量机 

支持向量机（Support Vector Machine，SVM）是一个经典的二分类算法，其找到的分割超平面具有更好的鲁棒性，因此广泛使用在很多任务上，并表现出了很强优势．

给定一个二分类器数据集，其中 ∈ {+1,−1}，如果两类样本是线性可分的，即存在一个超平面

将两类样本分开，那么对于每个样本都有． 

数据集𝒟中每个样本𝒙(𝑛)到分割超平面的距离为：

我们定义间隔（Margin）𝛾为整个数据集𝐷中所有样本到分割超平面的最短距离： 

如果间隔𝛾越大，其分割超平面对两个数据集的划分越稳定，不容易受噪声等因素影响．支持向量机的目标是寻找一个超平面(𝒘∗,𝑏∗)使得𝛾最大，即

由于同时缩放𝒘→𝑘𝒘和𝑏→𝑘𝑏不会改变样本𝒙(𝑛)到分割超平面的距离， 我们可以限制‖𝒘‖⋅𝛾=1，则公式(3.85)等价于 

数据集中所有满足的样本点，都称为支持向量（Sup port Vector）

对于一个线性可分的数据集，其分割超平面有很多个，但是间隔最大的超平面是唯一的．图3.6给定了支持向量机的最大间隔分割超平面的示例，其中轮廓线加粗的样本点为支持向量．

2.5.1 参数学习

为了找到最大间隔分割超平面，将公式(3.86)的目标函数写为凸优化问题

使用拉格朗日乘数法， 公式(3.87)的拉格朗日函数为

其中 ≥0,⋯, ≥ 0为拉格朗日乘数．计算Λ(𝒘,𝑏,𝜆)关于𝒘和𝑏的导数，并令其等于0，得到 

 

将公式(3.89)代入公式(3.88)，并利用公式(3.90)，得到拉格朗日对偶函数

支持向量机的主优化问题为凸优化问题，满足强对偶性，即主优化问题可以通过最大化对偶函数来求解．对偶函数Γ(𝜆)是一个凹函数，因此最大化对偶函数是一个凸优化问题，可以通过多种凸优化方法来进行求解，得到拉格朗日乘数的最优值𝜆∗．但由于其约束条件的数量为训练样本数量，一般的优化方法代价比较高，因此在实践中通常采用比较高效的优化方法，比如序列最小优化（Sequential Minimal Optimization，SMO）算法等．

根据KKT条件中的互补松弛条件，最优解满足．如果样本不在约束边界上， = 0，其约束失效；如果样本𝒙(𝑛)在约束边界上，≥ 0．这些在约束边界上的样本点称为支持向量（SupportVector），即离决策平面距离最近的点．

在计算出𝜆∗后，根据公式(3.89)计算出最优权重𝒘∗，最优偏置𝑏∗可以通过 任选一个支持向量(𝒙,𝑦)计算得到：

最优参数的支持向量机的决策函数为

支持向量机的决策函数只依赖于𝜆∗𝑛>0的样本点，即支持向量．

支持向量机的目标函数可以通过SMO等优化方法得到全局最优解，因此比其他分类器的学习效率更高．此外，支持向量机的决策函数只依赖于支持向量， 与训练样本总数无关，分类速度比较快． 

 2.5.2 核函数

支持向量机还有一个重要的优点是可以使用核函数（Kernel Function）隐式地将样本从原始特征空间映射到更高维的空间，并解决原始特征空间中的线性不可分问题．比如在一个变换后的特征空间𝜙中，支持向量机的决策函数为

其中𝑘(𝒙,𝒛) = 𝜙(𝒙)T𝜙(𝒛)为核函数．通常我们不需要显式地给出𝜙(𝒙)的具体形式，可以通过核技巧（Kernel Trick）来构造．比如以𝒙,𝒛∈为例，我们可以构造一个核函数：

来隐式地计算𝒙,𝒛在特征空间𝜙中的内积，其中 

(这样就从 变到了上)

2.5.3 软间隔

在支持向量机的优化问题中，约束条件比较严格．如果训练集中的样本在特征空间中不是线性可分的，就无法找到最优解．为了能够容忍部分不满足约束的样本，我们可以引入松弛变量（Slack Variable）𝜉，将优化问题变为

 其中参数𝐶 > 0用来控制间隔和松弛变量惩罚的平衡．引入松弛变量的间隔称为软间隔（SoftMargin）．公式(3.99)也可以表示为经验风险+正则化项的形式：

其中可以把看作损失函数，称为Hinge损失函数 （Hinge Loss Function），把 看作正则化项， 是正则化系数． 软间隔支持向量机的参数学习和原始支持向量机类似，其最终决策函数也只和支持向量有关，即满足的样本．

2.6 损失函数对比

上文介绍了三种二分类模型：Logistic回归、感知器和支持向量机．虽然它们的决策函数相同，但由于使用了不同的损失函数以及相应的优化方法，导致它们在实际任务上的表现存在一定的差异．

为了比较这些损失函数，我们统一定义类别标签𝑦 ∈ {+1,−1}，并定义 𝑓(𝒙;𝒘) = 𝒘T𝒙 + 𝑏．这样对于样本(𝒙,𝑦)，若𝑦𝑓(𝒙;𝒘) > 0，则分类正确；若 𝑦𝑓(𝒙;𝒘) < 0，则分类错误．这样，为了方便比较这些模型，我们可以将它们的损 失函数都表述为定义在𝑦𝑓(𝒙;𝒘)上的函数．

Logistic回归的损失函数可以改写为

 感知器的损失函数为

软间隔支持向量机的损失函数为 

 平方损失可以重写为

 图3.7给出了不同损失函数的对比．对于二分类来说，当𝑦𝑓(𝒙;𝒘) > 0时，分类器预测正确，并且𝑦𝑓(𝒙;𝒘)越大，模型的预测越正确；当𝑦𝑓(𝒙;𝒘)<0时，分类器预测错误，并且𝑦𝑓(𝒙;𝒘)越小，模型的预测越错误．因此，一个好的损失函数应该随着𝑦𝑓(𝒙;𝒘)的增大而减少．从图3.7中看出，除了平方损失，其他损失函数都 比较适合于二分类问题．