第三章线性模型 | BeZer0 Space

一、基本形式

给定由个属性描述的示例，其中是在第个属性上的取值，线性模型（linear model） 就是学习一个通过属性的线性组合来进行预测的函数：

一般用向量形式写成：

非线性模型（nonlinear model） 可在线性模型的基础上引入层级结构或高维映射得到。线性模型具备较好的解释性。

二、线性回归

给定数据集，其中。线性回归（linear regression） 是学习一个线性模型以尽可能准确地预测实值输出标记。

线性回归试图学得：

要确定和，可以使均方误差最小：

均方误差对应了欧氏距离（Euclidean distance），基于均方误差最小化来进行模型求解的方法称为最小二乘法（least square method）。在线性回归中，最小二乘法就是找一条直线，使得所有样本到支线上的欧式距离之和最小。

求解和使最小化的过程，称为线性回归模型的最小二乘参数估计（parameter estimation）。可将分别对和求导，得到：

然后令上两个式子为 0 可得到和最优解的闭式（closed-form） 解：

其中为的均值。

若考虑样本的个属性，此时需要学习：

这称为多元线性回归（multivariate linear regression）。

同样可以利用最小二乘法来进行估计，令，数据集表示为一个大小的矩阵，其中每行对应一个示例，该行前个元素对应于示例的个属性，最后一个元素恒置为 1 ：

把标记写成向量形式：，则有：

令，对求导得：

由矩阵微分公式：，可得：

令上式为 0 ，可得最优解的闭式解，当为满秩矩阵（full-rank matrix） 或正定矩阵（positive definite matrix） 时，可得：

令，则最终学得的多元线性回归模型为：

当不满秩时，可解出多个，它们都能使均方误差最小化，选择哪一个解作为输出，将由学习算法的归纳偏好决定，常见做法是引入正则化（regularization） 项。

对于简单的线性模型，可以将模型预测值逼近的衍生物，例如可将输出标记的对数作为线性模型逼近的目标：

这就是对数线性回归（log-linear regression），虽然该式形式上仍是线性回归，但实质上已是在求取输入控件到输出空间的非线性函数映射，如图，该函数可将线性回归模型的预测值与真实标签联系起来。

还可考虑单调可微函数：

这样得到的模型成为广义线性模型（generalized linear model），其中函数称为联系函数（link function）。

三、对数几率回归

考虑二分类任务，其输出标记，需要将线性回归模型产生的预测值（实值）转换为离散值，最理想的是阶跃函数（unit-step function）：

从图中可以看出，单位阶跃函数不连续，因此不能直接使用，于是可以找到一些替代函数（surrogate function），这些函数单调可微，如对数几率函数（logistic function）：

将对数几率函数作为，得：

恒等变形：

若将视为样本作为正例的可能性，则是其反例可能性，两者比值：

称为几率（odds），反映了作为正例的相对可能性，对几率取对数则得到对数几率（log odds, 亦称 logit）：

由此可看出，式（3.18）实际上是在用线性回归模型的预测结果去逼近真是标记的对数几率，因此对应的模型称为对数几率回归（logistic regression，亦称 logit regression）。

下面来确定式（3.18）中的和，若将式（3.18）中的视为类后验概率估计，则式（3.19）可重写为：

显然有：

于是，可以通过极大似然法（maximum likelihood method） 来估计和。给定数据集，对率回归模型最大化对然似然（log-likelihood）：

即令每个样本属于其真实标记的概率越大越好。为便于讨论，令，则可简写为。再令，则上式中的似然项可重写为：

将式（3.26）带入（3.25），并根据式（3.23）和（3.24）可知，最大化式（3.25）等价于最小化：

式（3.27）是关于的高阶可导连续凸函数，根据凸优化理论，经典的数值优化算法如梯度下降法（gradient descent method）、牛顿法（Newton method） 等都可求得其最优解，于是就得到：

以牛顿法为例，其第轮迭代解的更新公式为：

其中关于的一阶、二阶导数分别为：

四、线性判别分析

LDA 也是一种对数据进行降维的方法，与 PCA 不同的是，LDA 是一种有监督的数据降维方法。

PCA 存在局限性，例如两组本来可分的数据，降维后在新的空间中不可分。

LDA 降维的目标：将带有标签的数据降维，须满足三个条件：

尽可能多的保留样本信息；

寻找使样本尽可能好分的投影方向；

投影后使同类样本尽可能接近，不同类样本尽可能远离；

1. 优化目标

线性，指将数据点投影到直线上，直线表达式为：

表示样本向量，如果投影到一条直线上就是一个特征向量或者多个特征向量构成的矩阵。为投影后的样本点。

首先考虑两类样本的情况，将数据投影到直线上，则两类样本的中心在直线上的投影分别为和，其中表示第类样本的均值，若将所有的样本点都投影到直线上，则两类样本的协方差分别为和，投影后同类样本协方差矩阵的计算步骤如下：

其中用到了公式：。

上式中间部分是同类样本投影前的协方差矩阵。故可以发现若投影前的协方差矩阵为，则投影后的协方差矩阵为。

要使得同类样例的投影点尽可能接近，可以让同类样本点的协方差矩阵尽可能小，即尽可能小；要使得异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大，即尽可能大。于是得到最大化的优化目标：

其中表示欧几里得范数，。

2. 协方差与样本分布的关系

要使得同类样例的投影点尽可能接近，可以让同类样本点的协方差矩阵尽可能小，即尽可能小；要使得异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大，即尽可能大。

为什么协方差矩阵可以反映出样本或样例点之间的距离关系？首先来看协方差和方差的公式：

可以发现两者非常相似。已知方差可以用来度量数据的离散程度，越大，表示数据距离离样本中心越远，数据就越离散，方差也就越大。同样的，对于协方差来说，和越大，表示数据距离样本中心越远，数据分布就越分散，协方差也就越大。因此上述观点成立。

3. 类间散度矩阵

类间散度矩阵就是协方差矩阵乘以样本数目，其作用基本与协方差矩阵一致。

对于两类样本来说：

其中表示协方差矩阵，表示样本数目。

对于多类问题来说：

其中表示类别数目，表示所有样本的均值向量。

如果只使用类间散度矩阵一个约束条件来对数据进行降维，即让类间的样本投影尽可能远离，参考 PCA 的降维过程：

不同的是，为了保证类间的样本投影后尽可能远离，我们应该选择特征值最大的特征向量代表的方向做投影。这样才能保证不同类样本投影之后方差尽可能大，尽可能远离。

4. 类内散度矩阵

对于两类问题来说：

对于多类问题来说：

其中表示第类样本的协方差矩阵。所以表示类样本协方差矩阵之和。

如果只是用类内散度矩阵一个约束条件来对数据进行降维，即让类内的样本投影尽可能接近，参考 PCA 的将为过程：

不同的是，为了保证类内的样本投影后尽可能接近，我们应该选择特征值最小的特征向量代表的方向做投影。这样才能保证同类样本投影之后方差尽可能小，尽可能接近。

5. 优化

定义了类内散度矩阵和类间散度矩阵后，可以将优化目标转换为：

即与的广义瑞利商。

接下来确定，注意上式的分子和分母都是关于的二次项，因此上式的解与的长度无关，只与其方向有关。令，则上式等价于：

使用拉格朗日乘子法，上式等价于：

可以看到上式转化为一个求特征值和特征向量的问题。是要求解的特征向量，这就验证了之前所说的式子中的就是特征向量构成的矩阵。

但是此时仍有一个问题，那就是通常是不可逆的，因此有以下方法解决：

令，其中是一个特别小的数，从而使得可逆；

先使用 PCA 降维，使得降维后的数据上可逆，然后再使用 LDA 。

五、多分类学习

二分类的方法可以推广至多分类任务，简单来说就是对多分类任务拆分为多个二分类任务。最经典的拆分策略有一对一（One vs. One, OvO），一对其余（One vs. Rest，OvR; One vs. All, OvA）和多对多（Many vs. Many, MvM）。

OvO 方式对个元素的数据集会生成个分类器，在测试阶段将新样本提交给所有的分类器即可得到最终分类的结果。

OvR 方式是每次将一个类别的样例作为正例，其余类别作为反例来训练个分类器，测试时若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果；若有多个分类器预测为正类，则通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果。

从上述两种方法可以发现，前者空间开销更大，后者时间开销更大。这是因为前者训练的分类器个数更多，后者每次训练时用到的样本个数更多。

MvM 方法是每次将若干类作为正类，若干类作为反类，因此该方法的构造需要有特殊的设计。一种常用的方法为：纠错输出码（Error Correcting Output Codes, ECOC），该方法是将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。ECOC 工作过程主要分为两步：

编码：对 N 个类别做 M 次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集；这样一共产生 M 个训练集，可训练出 M 个分类器。

解码：M 个分类器分别对测试样本进行预测，这些预测标记组成一个编码。将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果。

类别划分通过编码矩阵（coding matrix）指定。编码矩阵有多种形式，常见的主要有二元码和三元码。前者将每个类别分别指定为正类和反类，后者在正、反类之外，还可指定停用类。在图（a）中，分类器将类和类的样例作为正例，将类和类的样例作为反例；在图（b）中，分类器将类和类的样例作为正例，类作为反例。在解码阶段，各分类器的预测结果联合起来形成了测试示例的编码，该编码与各类所对应的编码进行比较，将距离最小的编码所对应的类别作为预测结果。例如图（a）中，若基于欧氏距离，预测结果将是。

之所以叫纠错输出码，是因为在测试阶段，ECOC 编码器对分类器的错误有一定的容忍与修正能力。例如图（a）所示，测试样例的正确预测编码为（-1,+1,+1,-1,+1），假设在预测时分类器出错导致编码为（-1,-1,+1,-1,+1），但是基于该分类仍能正确得出分类结果。一般来说，对同一个学习任务，ECOC 编码越长，纠错能力越强，但同时也意味着所需训练的分类器越多，各方开销会增大。另一方面，对有限类别数，可能的组合数目是有限的，这就限定了码长的范围。

六、类别不平衡问题

类别不平衡（class-imbalance） 就是指分类任务中不同类别的训练样例数目差别很大的情况。本节假设正类样例较少，反类样例较多。

从线性分类器的角度讨论，使用对新样本进行分类时，事实上是再用预测出的值与一个阈值（通常为 0.5）比较。实际上表达了正例的可能性，几率则反映了正例可能性与反例可能性之比值，阈值设置为 0.5 表明分类器认为而这可能性相同，即分类器决策规则为：

然而当二者树木不同时，令分别表示正例数目和反例数目，则观测几率是，由于通常假设训练集是真实样本总体的无偏采样（表示采样的数据很好的代表了真是样本的情况），因此观测几率代表了真实几率。于是，只要分类器的预测几率高于观测几率就应该判定为正例，即：

为将式 3.49 转换为式 3.50 ，则令：

这就是类别不平衡学习的一个基本策略——再缩放（rescaling），再平衡（rebalance）。该方法也是代价敏感学习（cost-sensitive learning） 的基础。这个方法的重要前提是：训练集是真是样本总体的无偏采样，但是这个假设往往不成立。因此有另外三种方法：

直接对训练集里的反类样例进行欠采样（undersampling），即去除一些反例使得正、反例数目接近；

对训练集里的正类样例进行过采样（oversampling），即增加一些正例使得正、反例数目接近；

阈值移动（threshold-moving），直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将上式嵌入到决策过程中。

需要注意的是，过采样法不能简单地对初始样例样本进行重复采样，否则会导致过拟合。一种代表性的算法为 SMOTE ，通过对训练集里的正例进行插值来生成额外的正例。欠采样法若随机丢弃反例，则可能丢失部分重要信息。一种代表性的算法为EasyEnsemble，利用集成学习机制，将反例划分为若干个集合供不同学习器使用，这样对每个学习起来看完成了欠采样，但在全局来看并未丢失信息。