第3章
线性模型

3.1 线性回归

式（3.1）中的系数 是为了化简后续推导.有时也会乘上 以计算均方误差（mean square rror），由于“平均误差”和“误差和”在优化过程中只相差一个常数，不影响优化结果，因此在后续讨论中省略这一系数.

解答

由于

线性回归问题可以转化为如下形式：

下标LS表示least square.

其中， 1 _m ∈ ^m 为元素全为1、长度为 m 的向量，当其维数可由其他变量推导而得时会省略下标.因此， 1 _m b 为长度为 m 、元素均为 b 的向量.‖·| ₂ 表示向量的L ₂ 范数，是向量中各元素平方和的开方.有

解答

1. 针对式（3.3）中线性回归模型的目标函数进行优化，将目标函数写为

目标函数关于优化变量 w ， b 的偏导反映了目标函数随优化变量变化的趋势.当偏导为0时，目标函数达到极值点.对于线性回归问题，能够证明目标函数是关于 w ， b 的凸函数，因此偏导为0的解等价于模型的最优解.计算目标函数 h （ w ， b ）关于 w ， b 的偏导：

联立以下方程组，求解使偏导为0的 w ， b ：

首先在式（3.7）的第二个等式中用 w 表示 b ，有

然后将其代入式（3.7）的第一个等式，有

再进行化简，得到 w 的最优解 ，

最后将 代入式（3.8），得到

根据上述推导，可使用数据集 D 直接表示线性回归模型的最优解 和 这类能够直接计算得到而无须迭代优化的解也称为闭式解（closed form solution）.

偏移 是使用最优解 进行回归后预测值和目标之间 残差 的平均值.结合第2小题 的含义，参考式（3.12）.

习题注释 本小题主要考查对线性回归模型推导的理解.在求解过程中，需要理解为什么通过设置偏导为0得到最优解，同时也要注意需要联立关于 w 和 b 的偏导为0的等式.矩阵形式的闭式解更加紧凑，也能够作为后续其他模型推导的基础.矩阵的求导方式可参考文献[1].

2. 给定线性回归模型的最优解 和 ，对所有 m 个训练样例进行拟合，将针对矩阵 X 中所有样例的拟合结果（ f （ x _i ）组成的 m 维向量）记为 f （ X ），有

求解线性模型最优解的另一种方法为将偏移 b 和权重 w 合并.令 ，同时令 ，有 这一方法简化了求解过程，将针对两个变量的优化问题转化为针对 的优化.在后续分析中，将看到这一方法与本题独立求解 w 和 b 的区别.

式（3.12）可分解为两项：

1） 是对所有标记数值的求和，因此第一项首先计算数据集中 m 个样例对应标记的均值 将均值 复制了 m 份.因此，在对训练样例进行拟合时，是在标记均值 的基础上进行预测.

2） 计算了样例矩阵中所有样例属性之和， 为 m 个训练样例的均值 将属性均值复制 m 份，得到一个由均值构成的 m × d 的矩阵.因此，在第二项中，首先对训练集中的 m 个样例进行中心化（即 ），然后针对中心化后的样例矩阵 使用权重 进行进一步预测.

结合式（3.11）可以发现，引入偏移项 b ，使得在预测过程中显式考虑了数据的中心化.因此，也可以通过数据的中心化过程，去除优化变量 b .

上述过程中， 为最优权重.也可以把其闭式解代入进行分析.首先引入一些中间变量.若 I _m 为大小为 m × m 的单位矩阵，定义 H = I _m - 矩阵用于对数据进行中心化，具体而言，

HH = H 也表示当对数据做一次或者多次中心化操作时会得到相同的结果.

式（3.13）用 HX 实现将原始数据 X 减去各属性的均值，对数据做中心化操作.容易验证， H 是投影矩阵，具有 H ^⊥ = H 的性质，且 HH = H ，因此，可以使用矩阵 H 对 和 的表达式进行化简.有

式（3.12）（对训练样例的拟合结果）可以化简为

定义中间变量 P = HX （ X ^⊥ HX ） ^-1 （ HX ） ^⊥ ，可验证 P 也是投影矩阵，具有 PP = P 的性质.因此，线性回归模型对于训练样例的拟合值相当于把其真实值 y 投影到由 HX 列向量张成的一个空间中 ^{[ 2 ]} ，如图3.2b所示.

基于上述中心化矩阵的定义，线性回归也可以写为对中心化之后的数据求解权重 w 的过程（中心化之后可以忽略偏移 b 的影响）.

图3.2修改自文献[2].

对于线性模型进行投影这一几何角度，也可以从线性模型目标函数的角度进行理解.使用 w ^* 表示最优权重， f （ X ）可以表示为

其中， 为由 m 个样例的第 i 个特征组成的向量，所有 d 维特征构成了 d 个长度为 m 的基向量.线性回归即寻找一组权重 w ^* ，基于基向量张成的空间对训练样例进行拟合，使预测残差平方和最小.

3. 给定线性回归模型的最优解 和 ，对测试样例 x ^* 使用 f （ x ^* ）进行预测：

这一过程可以表示为首先使用训练集中的样例均值 对测试样例 x ^* 进行中心化，得到 ，然后以 为基础再使用最优权重 对中心化后的测试样例 进行预测.

4. 考虑 w 的最优解，并使用中心化矩阵 HX 表示，有

其中，矩阵（（ HX ） ^⊥ （ HX ））的大小为 d × d ，因此当维数较高时，一方面会造成矩阵求逆代价过大，另一方面会使得矩阵的可逆性不一定能被满足.

5. 图3.1b中的数据明显呈二次趋势.因此，针对样例 x 构建如下线性回归模型：

可以用解方程的思路理解矩阵的可逆性.线性回归相当于使用给定观测值的 m 个样例构成 m 个等式，共具有 d +1个未知数.当等式的数目大于未知数的数目（ m ＞ d +1）时，优化所有等式的残差之和；而当等式的数目小于未知数的数目（ m ＜ d +1）时，可以找到多个解都满足这些方程.因此，一般需要通过增加一些约束（如考虑较平滑的模型）来在这些解中进行选择.

相当于针对变换之后的特征 x =（ x ² ， x ）基于参数 w 进行回归，虽然 x 中存在 x 的平方项，但由于 x 固定，目标函数针对回归模型参数 w =（ w ₁ ， w ₂ ）仍是线性模型.

6. 首先考虑二分类问题，对于正类和负类，通过设定两个类别的标记为 y ₊ =1和 y _- =-1进行线性回归，通过 f （ x ）= w ^⊥ x + b 进行预测，则正类示例的预测 f （ x ）趋于1而负类示例的预测 f （ x ）趋于-1，因此可使用 f （ x ）的正负进行类别的判断，即

当 w ^⊥ x + b =0时可随机将示例预测为某个类别.

此外，也可将两个类别的标记设置为 y ₊ =1和 y _- =0，此时可以将用以区分不同类别的阈值设置为0.5，或辅以联系函数（link function）对预测输出 f （ x ）进行转换，并限制其在指定范围内.例如，当 f （ x ）∈[0，1]时可以用其表示预测类别的后验概率.

这一种思路将在对数几率回归中进一步讨论.

对于多分类问题，假设有 N 个类别，如果直接使用不同的数值表示不同的类别，则潜在地假设了类别之间的“序”关系.如对于三分类问题，将类别的标记设置为{1，2，3}，则假设了对于类别标记第三类大于第二类，第二类大于第一类.由于标记之间并无“序”关系，因此可以设计one-hot编码来对分类任务进行建模.对于第 n 类，设置标记 y =[0，…，0，1，0，…，0]，即在 N 维标记向量中，只有第 n 个元素为1，其余元素均为0.综上，可构建 N 个分类器 W =（ w ₁ ，…， w _N ）∈ ^{d × N} ，以及 b =（ b ₁ ，…， b _N ）∈ ^N ，使 f （ x ）= W ^⊥ x + b 接近 y .其中 反映了模型预测样例为第 n 类的置信度，置信度越高，一般而言样例属于第 n 类的概率也越大.

习题注释 本题主要考查对线性回归思想的理解，将线性回归视为对预测置信度的近似，即可将线性回归模型推广到分类场景.而在分类场景中，通过设置不同类型的“回归”标记，模型会有不同的性质.对于多分类问题，可通过使用类别标记编码的方法将线性回归模型直接用于线性分类，保持了模型的简单特性.通过设置“回归”标记的取值，线性回归的求解可与线性判别分析（linear discriminative analysis）的求解等价 ^{[ 3 ]} .线性回归在分类问题的应用将在第6章习题6.5中进一步讨论.

虽然上述方法能够处理多个类别，但可将线性模型对每一类别的预测过程分解，即在此设定下，模型对 N 个类别进行独立预测，而不考虑类别之间的关联性.最终判定时，可通过比较各类别置信度，选择置信度最高的类别作为所预测的类别.

岭回归见教材11.4节.

解答

1. 岭回归问题闭式解的推导过程类似原始线性回归（习题3.2第1小题）.定义岭回归的目标函数：

针对模型变量 w 求偏导，并令偏导为0：

则有

同理，有

X ^⊥ HX 为半正定矩阵.

对比岭回归和原始线性回归的解，能够发现这两个模型的权重 w 有所不同，偏移项 b 的形式是一致的（取值依赖于 w 的最优解）.在岭回归的最优解中，主要的区别在于式（3.26）在矩阵求逆的过程中增加了2 λ I _d .新增的这一项能够避免矩阵的特征值趋于0，使得 X ^⊥ HX +2 λ I _d 矩阵的特征值至少大于2 λ ，从而便于对矩阵求逆.岭回归模型也能够看作具有高斯先验的线性回归模型，在本书第7章习题中将进一步讨论.

在线性回归模型中，正则化一般只用于权重 w 而不施加于偏移项 b .观察线性回归模型对于训练样例和测试样例的预测结果，偏移项 b 刻画了残差的均值，当对样例进行中心化之后，目标函数中将不包含 b .因此，一般保留 b 的实际语义，使 b 能够直接刻画一种“截距”，而不对 b 进行大小的约束.从这一处理也能够看出，在求解岭回归模型的过程中，将偏移项并入权重项合并求解和单独求解得到的结果有所不同.

习题注释 本小题考查岭回归闭式解的求解，并展示正则化对闭式解的影响.实际应用中，正则化 Ω （·）一般用于对模型的复杂度进行约束，防止过拟合.除了本例所示的 外，也可以将 Ω 设置为其他的范数，例如L ₁ 范数， ，即权重 w 各元素绝对值之和.使用L ₁ 范数进行正则化能够使权重 w 的元素稀疏（有大量元素为0）.

2. 对公式的证明直接利用矩阵的性质.由于

即

左右两边各乘上相同的矩阵：

即

请注意上述公式中 XX ^⊥ ∈ ^{m × m} ， X ^⊥ X ∈ ^{d × d} .其中 d 为样例特征维数，而 m 为训练集示例数目.式（3.31）主要改变了求逆矩阵的规模.

通过观察线性回归的闭式解（式（3.10）），能够发现其中具有 d × d 矩阵的求逆操作.因此将线性回归模型用于高维数数据时，在模型的闭式解计算过程中，矩阵求逆步骤具有较大的计算开销.而通过本小题的结论，可知这一 d × d 矩阵求逆操作能够进行转化，等价变换为针对 m × m 矩阵求逆的过程.因此，当训练集样例数目 m 小于样例特征维数 d 时，使用该公式可以显著地降低矩阵求逆开销.

习题注释 本小题一方面考查对矩阵乘法和相关性质的掌握，另一方面考查是否能够基于本小题的结论和线性回归的求解过程进行关联.基于本小题的结论，当数据集中示例的数目 m 和维数 d 有不同的关系时，将使用不同的方法进行闭式解求解，从而降低计算开销.而对这一性质的应用类似于对线性回归 对偶 形式的推导，因此可将本小题的解答与本书第6章习题6.5中支持向量机使用原问题（primal problem）或对偶问题（dual problem）求解的选择进行关联.

此外，在对本小题进行解答时，也应该意识到虽然可直接由样例的输入得到最优的线性分类器参数，但在某些场景中需要进行大规模计算.若针对高维大数据（ d 较大， m 较大），则闭式解计算开销很难化简.在实际过程中，也会使用其他矩阵分解方法或迭代优化方法（如梯度下降法）对线性回归进行求解.在本书第11章习题11.3中有进一步讨论.

3. 根据线性回归与岭回归闭式解公式实现以下函数：

@表示矩阵乘法运算.

式（3.14）

式（3.26）

根据上述函数对“boston”数据集进行预测，完整结果可参考linear_regression_solution.py.

图3.3中给出了使用完整训练数据集和基于50个训练样例得到的原始线性回归和岭回归模型在测试集上的MSE.可以看出，当训练样例较多时（如图3.3a所示），原始线性回归能取得较好的效果，岭回归在不同的权重参数 λ 下反而会有更大的MSE；而当训练样例较少时，两个方法的测试集MSE都会增大很多，说明拟合效果下降，此时若 λ 较大，岭回归的MSE低于原始线性回归，说明较低复杂度的模型在训练样例少这一情况下能够取得较好的拟合效果.

习题注释 本小题旨在使用线性回归的闭式解对实际回归问题进行求解，并使用MSE进行回归模型的评价.实验中探究了一般线性回归和岭回归的不同，以及不同的岭回归正则化权重 λ 对预测结果的影响.本书将在第11章进一步探讨正则化对模型的影响.

3.2 对数几率回归

解答

1. 考虑将偏移项 b _n 并入分类器权重中以简化符号.设 ，将多分类问题的 N -1个对数几率转化为如下形式：

其中， β _n =（ w _n ， b _n ）.由于后验概率具有归一化性质， 1，因此得到

且

极大似然估计法使用最大化似然函数作为准则估计模型参数，这一方法在教材7.2节有进一步介绍.

针对上述后验概率的定义，得到对于 m 个样本的似然函数：

式（3.40）中使用了指示函数I（·），即

通过最小化负对数似然，得到对率回归的多分类扩展：

2. 为求解线性分类器，计算式（3.42）对第 n 类分类器 β _n 的梯度：

其中， 如需要求解针对 w _n 和 b _n 的梯度，则可用链式法则进一步计算.给定梯度后，可使用梯度下降等迭代式优化方法对目标函数进行优化，求解最优线性模型参数.可以验证式（3.42）针对 β _n 是高阶平滑的凸函数，因此除了使用梯度下降方法进行参数优化以外，也可以使用利用二阶信息的牛顿法，以进行更快的收敛率求解.

优化方法见教材附录B.

习题注释 本小题考查对对率回归模型的理解，并讨论如何将对率回归的思想应用于多分类问题.由于不同类别后验概率之和为1，因此只需要使用线性分类器预测 N -1个线性分类器对前 N -1个类别和第 N 个类别的对数似然即可.针对多分类问题，也可以直接使用softmax算子构建类别后验概率，在本书第12章习题12.7中将对这一方法做进一步的说明.

3.3 线性判别分析

为便于与后续习题中LDA的其他变种相区分，且基于教材3.4节的旁注，本题中将教材中介绍的线性判别分析模型称为FDA.

X _i 为第 i 类示例的集合 .

m _i 为第 i 类样本的数量.

解答

1. 首先分析tr（ W ^⊥ S _w W ）.由于迹运算的线性性质，有tr（ W ^⊥ S _w W ）= 对于第 i 类，可得到

其中， X _i 为第 i 类示例的集合，式（3.48）源于矩阵迹与其F范数之间的关系.因此， 表示第 i 类样例在投影空间（ W ^⊥ x ）中与其类中心（ W ^⊥ μ _i ）的距离之和，即第 i 类样例的类内散度.tr（ W ^⊥ S _w W ）为各类类内散度之和.同理，tr（ W ^⊥ S _b W ）表示在投影空间中各类中心（ W ^⊥ μ _i ）和全局样例中心（ W ^⊥ μ ）距离的加权和，即类间散度.

习题注释 本小题考查FDA的多类扩展中目标函数的含义，不同于二分类，当处理 N 类时由于使用矩阵进行投影，类内和类间散度均扩展为矩阵形式，并将矩阵的迹转化为标量用于目标函数中.需要理解迹运算的含义，且多类情况下类内和类间散度的定义均考虑了投影空间中的散度情况，和二分类情况下的目标一致.Wang等人 ^{[ 4 ]} 从图的角度给出了FDA目标函数的解释.

2. 基于所定义的类内和类间散度，教材中定义FDA的优化目标为

即使用矩阵的迹将投影后样例的散度转换为标量，通过优化投影矩阵 W 来最大化类间散度并最小化类内散度.式（3.49）也被称为trace ratio问题，但求解过程较为复杂，一般需要使用迭代方法求解 ^{[ 4 ]} .因此，为化简求解过程，考虑对式（3.49）进行近似，将其转化为

可以看出，相比于式（3.49），式（3.50）将迹运算和商运算换了位置，先将散度矩阵相除（与类内散度的逆矩阵相乘），然后再通过迹运算获得标量目标函数，因此被称为ratio trace问题.可以证明，式（3.50）的最优解满足如下广义特征值问题 ^{[ 5 ]} ：

对于二分类问题，trace ratio和ratio trace问题的解保持一致，但在多分类问题中有所区别：ratio trace问题具有闭式解，而trace ratio问题求解复杂，但后者一般情况下降维效果更好.FDA的两种求解思路在文献[6]中有进一步的讨论.除使用矩阵的迹之外，使用矩阵行列式也能够将矩阵散度转化为标量，因此，也可使用如下目标函数：

其中，|·|表示矩阵的行列式.式（3.52）和式（3.50）的最优解相同，均可通过求解广义特征值问题获得 ^{[ 7 ]} .

|·|等同于det（·），均可计算矩阵的行列式.

3. 确定投影维数等价于确定投影矩阵 W 的秩.考虑多类FDA的求解，针对如式（3.51）的广义特征值问题，投影矩阵的最优解为 因此，有

因此，可通过求解rank（ S _b ）估计rank（ W ）.对于矩阵 S _b 可以进行如下分解：

类间散度矩阵 S _b 可写为矩阵 H ∈ ^{d × N} 的乘积形式，即 S _b = HH ^⊥ .根据矩阵的秩的性质，有rank（ S _b ）=rank（ H ）.而对于矩阵 H ，有rank（ H ）≤min{ d ， N }.根据全局均值 μ 的定义，可验证矩阵 H 的所有列可通过加权使其和为0，且其中任意一列可以表示为其他列的线性组合 . 因此，由于矩阵的列有相关性，矩阵 H 的秩不超过 N -1 . 综上，有rank（ W ）≤ N -1，投影后空间的维数不超过 N -1.

习题注释 本题考查对多分类FDA的理解、最优解的性质，以及根据矩阵秩的特性分析出投影矩阵 W 的性质.因此在FDA的多分类优化过程中，直接将投影矩阵大小设置为 d ×（ N -1）即可，分配更多的列并不能增强FDA的能力.

对矩阵 S _b 的秩进行求解，也可以将 S _b 看作 N 个秩为1的矩阵之和，因此有rank（ W ）≤ N ，而由于全局均值 μ 占用了一个自由度，因此最终矩阵的秩不超过 N -1.也可以类比一般的线性分类器的判别过程，如习题3.4中所示，对于 N 个类别，只需要计算出样例和 N -1个类别之间的关系，在给定的全局约束的情况下即可推导出其和第 N 类的关系.因此 N -1个分类器足以处理 N 分类问题.

解答

1. 证明：式（3.55）中构建了瑞利商和特征值之间的关系，因此首先对 n × n 矩阵 A 进行特征值分解，即

其中 λ _i 为矩阵的特征值，而 ξ _i ≠ 0 为矩阵的特征向量.考虑到特征向量之间的正交性，{ ξ ₁ ， ξ ₂ ，…， ξ _n }构成一组单位正交基，从而存在一组 使得

代入瑞利商的定义，可得

可见瑞利商是矩阵 A 的特征值的加权平均，所以

2. 证明：针对广义瑞利商，基于第1小题的结论，对式（3.56）进行转化.利用特征值分解对大小为 n × n 的矩阵 B 进行对角化，可得

其中 P 为特征向量构成的正交矩阵， Λ 为对角矩阵，对角线元素为相应特征值（正数）.于是，

其中

根据前一小题的结论可得

对比式（3.56），还需要证明若 λ 是 C 的特征值，那么其也是 B ^-1 A 的特征值.考虑特征多项式，使用det（·）表示矩阵的行列式可得

矩阵行列式具有如下性质：det（ A ^⊥ ）=det（ A ），det（ AB ）=det（ A ）det（ B ）.

C 与 B ^-1 A 有相同的特征值，所以

将FDA的目标函数代入结论，可得

本题也可使用拉格朗日乘子法进行证明.在第2小题中利用了第1小题的结论，但需要证明 C 与 B ^-1 A 有相同的特征值（基于特征多项式、矩阵相似等）.另外，需要注意对于矩阵乘法而言，并没有与 类似的等式条件.

解答

1. 在LDA中，对某个样例的分类基于给定样例 x 下类别的后验概率 p （ y | x ）.基于贝叶斯公式，后验概率正比于类别先验概率 p （ y ）和类别条件概率（似然） p （ x | y ）的乘积.最大化类别后验概率等价于最大化对数转化后的后验概率，基于先验和似然的分解，代入对应的概率分布，得到以下形式：

基于式（3.73），当已知类别先验 π _n 以及各类别条件（高斯）分布的参数（ μ _y ， Σ ）时，首先计算 ，其次从中找出最大 δ _n （ x ）所对应的类别，用此类别作为LDA预测的类别.

可以看出， δ _n （ x ）一定程度上反映了样例 x 预测为 n 类的置信度，置信度越高，则 δ _n （ x ）越大.且 δ _n （ x ）可以分解为

因此，LDA中类别置信度的计算是关于样例 x 的线性函数，和线性分类器置信度的计算方法类似.

习题注释 本小题中LDA的判别方法和贝叶斯最优决策论相关，更多内容将在本书第7章中讨论.可以看出，LDA通过对类别的先验、似然建模，推导出后验概率.若假设不同类别的类别条件概率均为高斯分布，且类别之间共享协方差矩阵，则以最大后验概率为目标推导出的类别预测函数 δ _n 是关于样例 x 的线性函数，而LDA中“线性”的含义即源于此.

2. 上述准则中，假设模型参数已知.模型的参数主要包括类别先验、类别均值以及协方差矩阵.这些参数可以使用训练样例估计的统计量替代.如果某样例 x 被预测为第2类，需要满足第2类的置信度大于第1类，即 δ ₂ （ x ）＞ δ ₁ （ x ）.代入参数估计值，化简整理可得

可以看出，不等号的左边是关于 x 的线性变换，即令权重为 ，对 x 进行置信度计算，得到的结果和不等号右边的常数阈值进行比较.如果大于阈值，则预测为第2类，否则为第1类.

考虑一个特殊的场景，即两个类别的样例数目相等 m ₁ = m ₂ ，且类别协方差矩阵（的估计）为单位矩阵 此时，上述判别公式化简为

两类样例数目相同时， 为所有样例中心，这一操作也可视为中心化 .

因此，在判别过程中，样例 x 和类别均值的中心 同时在类别均值之差 的方向上投影，并比较投影之后的样例是否“跨过”类别中心投影.换句话说，可将类别中心投影想象为一个阈值，若样例投影超过类别中心投影，距离原点更远，则样例被预测为第2类，否则被预测为第1类.这一过程在图3.4a中展示，其中绿色的点为投影之前的样例，黄色的点为其投影之后的表示.

在 且 这一条件下，该准则和使用归一化之后的cosine相似度相同.

如果进一步施加约束，限制类别中心的估计为归一化向量，即 ，则判别公式可转化为对样例与类别中心相似度的判断：

其中， 通过内积定义了样例 x 和类别中心 之间的相似度，若样例和某个类别中心非常相似，则将样例预测为对应的类别.在这一特殊情况下，对样例类别的判别转化为对样例和类别中心之间距离的计算.这一类型的分类器也称为最近类中心分类器（Nearest Class Mean，NCM） ^{[ 8 ]} ，如图3.4b所示.当协方差矩阵 非单位矩阵时，上述过程将转化为先使用协方差矩阵对样例进行投影，然后在投影之后的空间中计算相似度.

准确地说，是使用矩阵 对样例进行投影.

习题注释 本小题考查在LDA的实现中使用经验估计值代替LDA中的各项参数.同时针对LDA在两类情况下的判别能力，考查其判别过程的“线性”特性和几何意义.

3. 首先化简 ：

对目标函数关于 β ₀ 和 β 分别求导并令其导数等于0，可得

将 y 的值代入式（3.79），得 将 β ₀ 和 y 代入式（3.80），注意到 m = m ₁ + m ₂ ，得

因为 的方向均与 的方向相同，所以

从而

习题注释 本小题考查LDA和线性回归之间的关系.通过设置类别标记数值，LDA的求解和线性回归的求解保持一致.这与习题3.2的第6小题中的结论一致，即线性回归可通过设置标记的形式实现对线性分类问题的求解.

解答

1. 和对率回归相比，LDA的假设更强.LDA假设类别条件概率服从高斯分布，并且各类共享协方差矩阵，从而使对数几率为线性函数；而对率回归仅假设对数几率为线性函数，未对类别条件概率进行假设.因此，当样例分布为高斯分布时，LDA的假设满足数据分布，能够得到更好的建模结果，而在一般的情况下，若类别条件分布不服从高斯分布，则LDA的效果可能不如对率回归.

也可以从优化的角度对比二者的差异.当假设类别条件分布为高斯分布时，通过极大似然估计得到的协方差矩阵即为样例协方差矩阵，所以两种方法实际上均可看作通过极大似然估计进行求解，而对率回归需要进行迭代优化.但是由于LDA需要计算样例均值与协方差，因此其对离群点更为敏感，对率回归更为稳健.

习题注释 本小题考查LDA与对率回归的差异，二者均得到线性分类器，但在思路上有重要不同.通过本小题的解答也可关联机器学习中的生成式模型（generative model）和判别式模型（discriminative model）.生成式模型通过对类别的先验和条件概率进行假设，得到示例和标记的联合分布.一般当生成式模型的假设满足样例的真实情况时会有更好的效果，且生成式模型能够得到示例和标记的联合分布，因此对示例的建模和对信息的刻画更加完整；而判别式模型直接对后验概率进行假设，模型表现会更加稳健.LDA为生成式模型，而对率回归为判别式模型.

2. 使用和习题3.7的第1小题类似的方式，最大化后验概率，得到

所以 是关于示例 x 的一个二次函数.这一做法被称为二次判别分析（Quadratic Discriminant Analysis，QDA）.类似地，可以验证，在QDA的假设下得到的分界面为二次曲面，其结果如图3.5所示.

习题注释 本小题考查对LDA假设的理解.若没有所有类别共享协方差矩阵这一假设，则关于示例 x 的预测方式为一个二次的平面，从而LDA扩展为二次判别分析（QDA）.

3.4 多分类学习

解答

1. 假设每个类别的数量为 m _i ， i =1，2，…， N ，则

对于OvO策略，训练过程中，将第 i 类与第 j 类两两匹配成多个二分类问题，总训练时间复杂度为

O （ m _i + m _j ）表示训练时间开销与 m _i + m _j 有关.

对于OvR策略，共有 N 个子问题，每一个子问题中包含所有 m 个样本，总训练时间复杂度为

从上述分析中可以看出，若训练时间复杂度只与输入算法的训练数据量有关，则两个策略模型的训练时间复杂度基本一致.OvO策略中将类别进行两两分类的子任务有 N （ N -1） / 2个，但每一个子任务的分类样本量较少，仅包含两个类的样例；OvR只训练 N 个分类器，但每一个分类器都用到了整个数据集，样本量和所有训练数据量一致.而在测试过程中，OvO的存储开销和测试时间开销通常比OvR更大.

在实际应用中，训练时间复杂度还会受到算法优化与执行效率等其他因素的影响.

2. 两类分类方法的判别结果如图3.6所示.在OvO中，可能存在某一区域（绿色区域），其中多个分类器的投票相等.而在OVR中，可能存在某一区域（绿色区域）被所有分类器判断为负类，同时也存在部分区域（灰色区域）被多个分类器预测为正类.因此，在这些判别较为模糊的场景中，一般也联合分类器的置信度进行最终的预测.

图3.6修改自文献[10].

3. OvR中的每一个子分类器在训练过程中存在类别不平衡（class-imbalance）问题，由于负类包含其余所有类别，因此正类样例相比于负类样例少了很多.但一般不需要为每个模型专门引入不平衡机制，因为在多个子分类器构建过程中，每一个类遭受的不平衡是对称的，每类均在某一个划分中作为小类（作为正类时示例相对较少），同时也在多个划分中作为大类（作为负类时示例相对较多），最终综合预测时这些不平衡性的影响会互相抵消.

解答

1. 至少可以纠正 个分类器的错误；表3.1中纠错码的最小海明距离为4；当两个分类器预测出错时，该编码可能无法纠错，比如当最终的编码结果为（0，0，1，1，1，1，1，1）时，它到 C ₁ 和 C ₂ 的海明距离均为2.

2. 好的纠错码应该满足以下两个条件：一是行分离（row separation），即不同类别编码之间的海明距离应该尽可能大，以保证纠错码可以尽可能纠正较多的分类器预测错误；二是列分离（column separation），即不同分类器编码之间的海明距离尽可能大，否则，意味着不同分类器的分类性能相近，因而可能会同时犯错，这会导致纠错码失效.与此同时，希望分类器的编码与其他分类器编码的反码（若编码为011，定义反码为100，即各位元素分别取反）的距离也足够大.对反码进行约束主要由于有些二分类学习器交换类别标记后训练出的模型是一样的（如教材第4章中的决策树模型、教材第6章中的支持向量机模型）.

通常而言， N 个分类一共可以形成2 ^N 个编码，去除其中一半的反码，剩余2 ^{N -1} 个编码，再去除全零或者全一的没有意义的编码，最终含有2 ^{N -1} -1个可用编码.

3. 一般而言，当类别数目 N 在3～7之间时，可以按照如下方式构造长为2 ^{N -1} -1的二元ECOC编码 ^{[ 9 ]} .首先，第一行中将所有编码元素全部置1；第二行中将2 ^{N -2} 个元素置0，剩余2 ^{N -2} -1个元素置1；第三行元素中，依次设置2 ^{N -3} ，2 ^{N -3} ，2 ^{N -3} ，2 ^{N -3} -1个元素为0，1，0，1；在第 i 行中，交替出现多组长度为2 ^N-i 的取值为0和1的编码.当类别数为4时，得到表3.2中码长为7的编码.

类别数目更多时的编码方案可参考文献[9].

若指定码长为8，第8位可编码为前7位中任意一位编码的补码.前7位编码的海明距离最小为4，加入第8位编码后，最小海明距离仍然为4，此为海明距离下的最优编码，如表3.3所示.

4. 在每一位编码上出错的概率相当意味着各个分类器的泛化性能相当，这意味着多分类转换为不同的二分类问题的难易程度相当，但这在现实问题中很难满足.有的二分类问题中，两个类别的重叠程度较低，则学出的分类器泛化性能更好；有的二分类问题中，两个类别的重叠程度较高，则学出的分类器泛化性能较差.在每一位编码上出错的概率独立即不同的分类器彼此间相互独立.如前所述， N 个分类只有2 ^{N -1} -1个编码可以用，因而当类别数较少时，可用编码数目过少，难以保证分类器之间的独立性；当类别数较多时，可用编码数目较多，更容易保证分类器之间的相对独立性.

参考文献

[1]PETERSEN K B, PEDERSEN M S.The matrix cookbook[EB/OL].Copenhagen:Technical University of Denmark, 2012[2022-03-27].http://www2.compute.dtu.dk/pubdb/pubs/3274-full.html.

[2]HASTIE T, TIBSHIRANI R, FRIEDMAN J.The elements of statistical learning:data mining, inference, and prediction[M].2nd ed.New York:Springer, 2009.

[3]YE J.Least squares linear discriminant analysis[C]//Proceedings of the 24th International Conference on Machine Learning(ICML).New York:ACM, 2007:1087-1093.

[4]WANG H, YAN S, XU D, et al.Trace ratio vs.ratio trace for dimensionality reduction[C]//Proceedings of the 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR).Cambridge:IEEE Computer Society, 2007:1-8.

[5]FUKUNAGA K.Introduction to statistical pattern recognition[M].Cambridge:Academic Press, 1990.

[6]JIA Y, NIE F, ZHANG C.Trace ratio problem revisited[J].IEEE Transactions on Neural Networks, 2009, 20(4):729-735.

[7]DUDA R O, HART P E, STORK D G.Pattern classification[M].2nd ed.Hoboken:Wiley, 2000.

[8]MENSINK T, VERBEEK J.PERRONNIN F, et al.Distance-based image classification:generalizing to new classes at near-zero cost[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11):2624-2637.

[9]DIETTERICH T G, BAKIRI G.Solving multiclass learning problems via error-correcting output codes[J].Journal of Artificial Intelligence Research, 1995, 2:263-286.

[10]CHRISTOPHER M B.Pattern recognition and machine learning[M].New York:Springer, 2006. zYtmK0A1JDaLHcRvxHNdPzdpNafQ2g3O++YaPN8289GXKTDKuH1ZrlIq3KLa531H