———— 善不由外来兮，名不可以虚作。

线性分类 (Linear Classification)

在前几篇文章中总结了监督学习中的线性回归问题，现在开始进入线性分类章节。分类问题可以看做线性问题的延伸。回归问题的目标是将输入变量  映射到另一个空间并得到一个具体数值，而分类问题的目标则是输⼊变量  同样通过某种映射得到在另一个空间对应的值，然后将  划分到  个离散的类别  中的某⼀类。对于线性回归问题只讨论了回归目标值为单个变量的情况，实际上也有多目标的回归问题，但原理类似；同样地，分类问题也有多分类问题，但最常见的情况是，各类别互相不想交，因此每个输⼊被分到唯⼀的⼀个类别中。我们只讨论这种情况。

分类与回归最大的区别就是实现的任务不同，在确定了对应的分类函数以后，输⼊空间就可以划分为不同的决策区域 (decision region)，它的边界被称为决策边界 (decision boundary) 或者决策⾯ (decision surface)。如果决策⾯是输⼊向量  的线性函数，那么它也是  维输⼊空间中的  维超平⾯。如果数据集可以被线性决策⾯精确地分类，那么我们说这个数据集是线性可分的 (linearly separable)。

为了确定决策边界，我们需要构造判别函数 (discriminant function)，把向量  分到具体的类别中。更一般地，我们把分类问题划分为推断 (inference) 和决策 (decision) 两个阶段。在推断阶段，我们使用训练数据学习  的模型，然后在决策阶段根据这些条件概率进行最优的分类。条件概率实际上代表的是参数模型，我们使用训练数据优化参数，对于类别  而言计算的是其后验概率，所以这种模型也是判别式模型 (discriminative model)；另一种方法是，我们先对类条件密度  和先验概率  建模，然后使用贝叶斯定理计算

实际上等价于对联合概率分布  建模，然后归一化得到联合概率，这种方法又称为生成式模型 (generative model)。

对于回归问题来说，⽬标向量  是⼀个实数向量，它的值就是我们想要预测的结果。在分类问题中，尤其是深度学习的分类问题，表示类别的标签一般采用 one-hot 编码形式，对于一个包含  个类别的分类问题，我们构造一个  的向量，如果结果属于第  类  ，那我们就将对应的第  个元素置一，其余位置置零。如目标变量  就表示在一个四分类问题中表示第二个种类的标签。

对于直接使用判别函数的模型，输入向量可以被直接映射为类别，在线性分类问题中使用很多，我们先讨论这种情形。

1. 线性判别函数 (Linear Discriminant Function)

与线性回归相似，一种最简单的模型就是直接用一个线性函数进行分类，首先考虑二分类的情形，我们构造一个输入向量的线性函数  ，对于输入向量  ，如果  ，那么就被分到  类，否则分到  类。此时决策面由  确定。对于任意两个在决策面上的点  和  ，有  ，所以向量  正交于决策面。对于任意一点  ，在  方向上的投影代表了原点到决策面的垂直距离，即

可见  和  分别决定了决策面的方向和位置。对于任意一点  ，我们将其投影至决策面上的一点  ，这样我们就可以将其写成两个向量之和的形式

在两边同乘  并加上  ，由于  在决策面上，因此可以得到  ，如下图所示。

关于多分类的线性判别函数，我们可以引入一个由  个线性判别函数组成的  类判别函数  ，对于任意一点  ，如果对于所有的  都有 ，那么就把它分到  ，此时  与  的决策面为  ，对应于一个  维超平面，形式为  ，具有二分类决策面类似的性质。并且这样的决策区域都是单连通且凸的。考虑决策区域  内任意两点  ，这两点连成的线段上的任意一点  都可以表示成

其中  ，根据线性函数的基本性质，很容易得出  也属于  。

这种线性判别函数与最简单的线性回归形式基本类似，所以我们先考虑用最小平方训练模型，将所有偏置和参数向量聚集在一起，有  ，其中  代表  个种类的参数，  是所有偏置项，  是  个训练集数据的矩阵， 是目标向量矩阵，平方和误差函数可以写成 

使用解析法可以计算出  ，其中  是  的伪逆矩阵，  ，  是训练数据的均值向量，  。多⽬标变量的最⼩平⽅解有⼀个性质，如果训练集⾥的每个⽬标向量都满⾜某个线性限制

其中  和  为常数，那么对于任何  值，模型的预测也满⾜同样的限制，即

将解析解直接代入，可得

其中  由公式 (6) 的一阶导置零求得。对公式 (8) 两边都乘以  并且根据  可得结果为  ，证明公式 (7) 成立。

最⼩平⽅法对于离群点缺乏鲁棒性，而且由于最⼩平⽅法对应于⾼斯条件分布假设下的最⼤似然法，多目标向量显然不是服从一个高斯分布，线性分类模型需要使用其他方法训练参数。

2. Fisher 分类器 (Fisher Linear Discriminant)

如果从维度降低的⾓度考察线性分类模型，对于二分类问题，可以看做针对输入向量  在一维空间的投影

线性判别函数等价于我们在  上设置⼀个阈值，然后把  的样本分为  类，把其余的样本分为  类。 但是⼀维投影会造成相当多的信息丢失，因此在原始  维空间能够完美分离的样本在⼀维空间中可能会相互重叠。Fisher 分类器提出的思想是最⼤化⼀个函数，能够让类均值的投影分开得较⼤，同时让每个类别内部的⽅差较⼩，从⽽最⼩化类别的重叠。仍然考虑上述二分类问题，包含  个  类的点和  个  类的点，两类的均值分别为  ，最简单的度量类间区分程度的⽅式就是类别均值投影之后的距离。取单位长度向量  并向其投影，取下式的最大值即可

其中  ，是类别  的均值投影。但是如下图所示，当投影到一维空间时，就有了⼀定程度的重叠。如果类概率分布的协⽅差矩阵与对角化矩阵差距较⼤，即类内方差在各个方向上差异较大，那么这种问题就会出现。如下图左图所示

我们将投影在一维空间的类  的类内方差记作

我们把整个数据集的总的类内方差定义为  ，Fisher 准则根据类间⽅差和类内⽅差的⽐值定义，即

分别用  和  表示类间 (between-class) 协方差矩阵和类内 (within-class) 协方差矩阵。对公式 (12) 求导，发现  取极大值的条件为

考虑只是一维投影，因此我们只关心  的方向，忽略标量因子  和  ，而  总是在  的方向上，对公式 (13) 两侧同乘以  ，可得

如上图右图就是最大化类间方差与类内方差比值的结果。如果类内协⽅差矩阵是各向同性的，即各个方向方差一致，协方差为正实数与单位矩阵相乘，从⽽  正⽐于单位矩阵，那么  正⽐于类均值的差。

最⼩平⽅⽅法确定线性判别函数的⽬标是使模型的预测尽可能地与⽬标值接近。相反，Fisher 判别准则的⽬标是使输出空间的类别有最⼤的区分度。这两种方法也并非毫无关系，我们可以通过修改目标向量建立二者的联系，对于⼆分类问题，Fisher 准则可以看成最⼩平⽅的⼀个特例。对于  类，我们令其目标值为  ，而  类为  ，  分别为类别  数据点的个数，此时平方误差函数可以写成

令  关于  和  的导数为零，得

先求解公式 (16)，可得偏置表达式

其中  ，将这两个式子以及公式 (18) 代入 (17) 通过繁琐但并不复杂的运算，可得

仍然可以得到与公式 (14) 类似的结果，因为最小二乘法的计算本就包含了类内方差的因子，我们只不过通过构造目标值引入类间方差从而得到 Fisher 分类器的结果。

3. 感知器算法 (Perceptron Algorithm)

线性判别模型的另⼀个例⼦是感知器算法 (perceptron algorithm)，它对应⼀个⼆分类模型，输⼊向量  ⾸先使⽤⼀个固定的⾮线性变换得到⼀个特征向量  ，然后被⽤于构造⼀个线性模型，形式为

其中非线性激活函数  是一个阶梯函数，形式为

向量  通常包含⼀个偏置分量  。我们仍可以使用误差最小化来确定感知器的参数  ，可以将误分类的数据作为误差函数，但这样做会使误差函数变为  的分段常函数，无法正常使用梯度下降算法。考虑其他的误差函数，根据二分类的线性判别函数，我们可以寻找一个权向量  使得对  类都有  ，对于  类有  ，同时由于目标值正好异号，可以利用所有误分类的模式构造如下误差函数

对这个误差函数使⽤随机梯度下降算法，权向量  的变化为

其中  是学习率参数，  是迭代次数。如果我们将  乘以⼀个常数，那么感知器函数  不变，因此我们可令学习率参数  等于 1 ⽽不失⼀般性。我们对训练模式进⾏循环处理，对于每个数据点  计算感知器函数，如果模式正确分类，那么权向量保持不变，⽽如果模式被错误分类，那么对于类别  ，我们把向量  加到当前权向量  的估计值上， ⽽对于类别  ，我们从  中减掉向量  。在线性判别函数一节中已经讲过，参数  实际上决定了决策界面的方向，感知器算法的迭代过程可以看做是将决策面朝着错误分类数据点的移动，如下图所示

如果我们考虑感知器学习算法中⼀次权值更新的效果，可以看到，⼀个误分类模式对于误差函数的贡献会逐渐减⼩，如下

当然，这并不表明其他的误分类数据点对于误差函数的贡献会减⼩。此外，权向量的改变会使得某些之前正确分类的样本变为误分类。因此感知器学习规则并不保证在每个阶段都会减⼩整体的误差函数。如果数据点确实线性可分，那么感知器算法在经过一定迭代步骤一定可以找到精确解，但是所需要的步骤往往很大，并且在达到收敛状态之前，我们不能够区分不可分问题与缓慢收敛问题。即使数据集是线性可分的，也可能有多个解，并且最终收敛的解依赖于参数的初始化以及数据点出现的顺序。而对于线性不可分的数据集，感知器算法永远不会收敛。

本文讲述了三种线性分类的判别函数，下篇文章将从概率的角度观察分类问题。