线性模型是最基础的机器学习模型之一。本文先从线性回归任务开始，接着讨论分类和多分类问题。
0 线性模型概述
给定由d个属性描述的示例\mathbf{x}=(x_1;x_2;\dots;x_d)，其中x_i为\mathbf{x}在第i个属性上的取值，线性模型（Linear Model）试图学得一个通过属性的线性组合来进行预测的函数，即
\begin{aligned}
f(\mathbf{x}) &=\mathbf{w}^{\top}\mathbf{x}+b\\
& =w_1x_1+w_2x_2+\cdots+w_dx_d+b
\end{aligned}其中权重\mathbf{w}=(w_1;w_2;\dots;w_d)。线性模型形式简单、易于建模，但却蕴涵着机器学习中一些重要的基本思想：许多功能更为强大的非线性模型（Nonlinear Model）可在线性模型的基础上通过引入层级结构或高维映射而得；此外，由于\mathbf{w}直观表达了各属性在预测中的重要性，因此线性模型有很好的可解释性（Comprehensibility）。
1 线性回归
给定数据集D=\{(\mathbf{x_1},y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_m,y_m)\}，其中\mathbf{x}_i=(x_{i1};x_{i2};\dots;x_{id}),\ y_i\in \mathbb{R}，线性回归（Linear Regression）试图学得一个线性模型以尽可能准确地预测实值输出标记。
1.1 一元线性回归
首先只考虑一种最简单的情形——输入属性的数目只有1个，即一元线性回归。此时可忽略关于属性的下标，即将表示简化为D=\{(x_i,y_i)\}_{i=1}^m，其中x_i\in \mathbb{R}。有时输入的属性值并不能直接被学习模型所用，需要进行相应的处理，对于连续值的属性，一般都可以被学习器所用，有时会根据具体的情形作相应的预处理，例如归一化等；对于离散值的属性，可作如下处理：
- 若属性值之间存在“序（Order）关系”，则可将其转化为连续值。例如，“身高”属性的取值“高”“中等”“矮”可转化为数值
\{1, 0.5, 0.0\} - 若属性值之间不存在“序关系”，假定有
k个属性值，则通常将其转化为k维向量的形式。例如，“性别”属性的取值“男”“女”可转化为二维向量\{(1,0),(0,1)\}。
一元线性回归试图学得
\begin{aligned}
f(x_i)=wx_i+b\ \text{ s.t. }\ f(x_i)\simeq y_i
\end{aligned}确定w,b的关键在于如何衡量f(x),y之间的差别，均方误差（如2.3所述）是回归任务中最常用的性能度量之一，因此可试图让均方误差最小化，即
\begin{aligned}
(w^*,b^*) &= \underset{(w,b)}{\arg\min} \sum\limits_{i=1}^m (f(x_i)-y_i)^2 \\
&=\underset{(w,b)}{\arg\min} \sum\limits_{i=1}^m (y_i-wx_i-b)^2
\end{aligned}均方误差有非常好的几何意义，它对应了常用的欧氏距离（Euclidean Distance）。基于均方误差最小化来进行模型求解的方法称为最小二乘法（Least Square Method），在线性回归中，最小二乘法即为试图找到一条直线，使所有样本到直线上的欧氏距离之和最小。
令E_{(w,b)}=\sum\limits_{i=1}^m(y_i-wx_i-b)^2，求解w,b使得E_{(w,b)}最小化的过程称为线性回归模型的最小二乘参数估计（Parameter Estimation）。可将E_{(w,b)}分别对w,b求导，得
\begin{aligned}
\frac{\partial E_{(w,b)}}{\partial w} &= 2\left(w\sum\limits_{i=1}^m x_i^2-\sum\limits_{i=1}^m \left (y_i-b\right )x_i\right )\\
\frac{\partial E_{(w,b)}}{\partial b} &= 2\left (mb-\sum\limits_{i=1}^m \left (y_i-wx_i\right )\right)
\end{aligned}令上两式\dfrac{\partial E_{(w,b)}}{\partial w}=0,\ \dfrac{\partial E_{(w,b)}}{\partial b}=0，可得w,b最优解的闭式（Closed-form）解
\begin{aligned}
w &= \frac{\sum\limits_{i=1}^m y_i(x_i-\bar x)}{\sum\limits_{i=1}^m x_i^2-\dfrac{1}{m}\left (\sum\limits_{i=1}^m x_i\right )^2} \\
b &= \frac{1}{m}\sum\limits_{i=1}^m (y_i-wx_i)
\end{aligned}其中\bar x=\sum\limits_{i=1}^m x_i为x的均值。
1.2 多元线性回归
更一般的情形为多元线性回归（Multivariate Linear Regression），如本章开头的数据集D，样本由d个属性描述。多元线性回归试图学得：
\begin{aligned}
f(\mathbf{x}_i)=\mathbf{w}^{\top}\mathbf{x}_i+b\ \text{ s.t. }\ f(\mathbf{x}_i)\simeq y_i
\end{aligned}类似地，可用最小二乘法对\mathbf{w},b进行估计。为便于讨论，此处将\mathbf{w},b吸收入向量形式\hat \mathbf{w}=(\mathbf{w};b)，相应的，将数据集D表示为一个m\times (d+1)大小的矩阵\mathbf{X}，其中每行对应于一个示例，该行前d个元素对应于示例的d个属性值，最后一个元素恒置为1，即
\begin{aligned}
\mathbf{X}=\begin{pmatrix}
x_{11} & x_{12} & \cdots & x_{1d} & 1 \\
x_{21} & x_{22} & \cdots & x_{2d} & 1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
x_{m1} & x_{m2} & \cdots & x_{md} & 1
\end{pmatrix} = \begin{pmatrix}
\mathbf{x}_1^\top & 1 \\
\mathbf{x}_2^\top & 1 \\
\vdots & \vdots \\
\mathbf{x}_m^\top & 1
\end{pmatrix}
\end{aligned}易得
\begin{aligned}
\mathbf{X}\hat \mathbf{w}=\begin{pmatrix}
x_{11} & x_{12} & \cdots & x_{1d} & 1 \\
x_{21} & x_{22} & \cdots & x_{2d} & 1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
x_{m1} & x_{m2} & \cdots & x_{md} & 1
\end{pmatrix} \begin{pmatrix}
w_1 \\
w_2 \\
\vdots \\
w_d \\
b
\end{pmatrix}=\begin{pmatrix}
w_1x_{11}+w_2x_{12}+\cdots+w_dx_{1d}+b \\
w_1x_{21}+w_2x_{22}+\cdots+w_dx_{2d}+b \\
\vdots \\
w_1x_{m1}+w_2x_{m2}+\cdots+w_dx_{md}+b
\end{pmatrix}=\begin{pmatrix}
f(\mathbf{x}_1) \\
f(\mathbf{x}_2) \\
\vdots \\
f(\mathbf{x}_m)
\end{pmatrix}
\end{aligned}再将标记也表示为向量形式\mathbf{y}=(y_1;y_2;\cdots;y_m)，类似于一元线性回归参数估计，有
\begin{aligned}
\hat \mathbf{w}^*=\underset{\hat \mathbf{w}}{\arg \min} (\mathbf{y}-\mathbf{X}\hat \mathbf{w})^\top (\mathbf{y}-\mathbf{X}\hat \mathbf{w})
\end{aligned}令E_{\hat \mathbf{w}}=(\mathbf{y}-\mathbf{X}\hat\mathbf{w})^\top (\mathbf{y}-\mathbf{X}\hat \mathbf{w})，对\hat \mathbf{w}求导可得
\begin{aligned}
\frac{\partial E_{\hat \mathbf{w}}}{\partial \hat \mathbf{w}}=2\mathbf{X}^\top (\mathbf{X}\hat \mathbf{w}-\mathbf{y})
\end{aligned}令上式\dfrac{\partial E_{\hat \mathbf{w}}}{\partial \hat \mathbf{w}}=0，可得\hat \mathbf{w}最优解的闭式解，但由于涉及矩阵逆的计算，比单变量情形要复杂一些（矩阵的行列式不等于0时才可求逆）。当\mathbf{X}^\top\mathbf{X}为满秩矩阵（Full-rank Matrix）或正定矩阵（Positive Definite Matrix）时，解该方程可得
\begin{aligned}
\hat \mathbf{w}^*=(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top\mathbf{y}
\end{aligned}令\hat \mathbf{x}_i=(\mathbf{x}_i,1)，则最终学得的多元线性回归模型为
\begin{aligned}
f(\hat \mathbf{x}_i)=\hat \mathbf{x}_i^\top (\mathbf{X}^\top\mathbf{X})^{-1} \mathbf{X}^\top\mathbf{y}
\end{aligned}然而现实任务中\mathbf{X}^\top\mathbf{X}往往不是满秩矩阵，此时存在多个解，至于选择哪一个解作为输出，将由学习算法的归纳偏好决定，常见的做法是引入正则化（Regularization）项。
1.3 广义线性模型
原始的线性模型y=\mathbf{w}^\top \mathbf{w} + b表示模型预测值线性变化地逼近真实标记y。但很多时候真实标记为y的衍生物，例如在指数尺度上变化\ln y，如下所示：
\begin{aligned}
\ln y = \mathbf{w}^\top \mathbf{x}+b
\end{aligned}此时衍生的线性模型称为对数线性回归（Log-Linear Regression），实际上是在试图让\text{e}^{\mathbf{w}^\top \mathbf{x}+b}逼近y。形式上仍是线性回归，但实质上已是在求取输入空间到输出空间的非线性函数映射。如图所示，在几何上相当于将指数曲线投影在一条直线上，：
更一般地，考虑所有y的衍生物的情形，就得到了广义线性模型（Generalized Linear Model）：
\begin{aligned}
y = g^{-1}(\mathbf{w}^\top \mathbf{x}+b)
\end{aligned}其中单调可微函数g(\cdot)称为联系函数（Link Function），对数线性回归即为g(\cdot)=\ln (\cdot)时的特例。
2 逻辑斯蒂回归
回归的本质是通过输入的属性值得到一个预测值。利用广义线性模型的特征，可以通过一个联系函数，将预测值转化为离散值从而进行分类。对于二分类任务，其输出标记y\in \{0,1\}，而线性回归模型产生的预测值为实值，需将实值映射为0/1值，故最理想的即为单位跃阶函数（Unit-Step Function）：预测值大于0判正例，小于0判反例，为临界值0则可任意判别，如下所示
\begin{aligned}
y=\left\{\begin{matrix}
0, & z\lt 0 \\
0.5, & z=0 \\
1, & z \gt 0
\end{matrix}\right.
\end{aligned}
但显然单位跃阶函数不连续，无法直接作为g^{-1}(\cdot)，故需要寻找能在一定程度上近似单位阶跃函数的替代函数（Surrogate Function），并希望其单调可微。对数几率函数（Logistic Function）经常作为这样一种常用的替代函数，如下所示
\begin{aligned}
y=\frac{1}{1+\text{e}^{-z}}
\end{aligned}对数几率函数是最典型的Sigmoid函数（S型函数），是任意阶可导的凸函数。将对数几率函数作为g^{-1}(\cdot)代入广义线性模型表达式，可得
\begin{aligned}
y=\frac{1}{1+\text{e}^{-(\mathbf{w}^\top \mathbf{x}+b)}}
\end{aligned}可进一步变形为
\begin{aligned}
\ln \frac{y}{1-y}=\mathbf{w}^\top \mathbf{x}+b
\end{aligned}若将y视为样本\mathbf{x}作为正例的可能性，则1-y为其反例可能性，两者的比值\dfrac{y}{1-y}称为几率（Odds），反映了\mathbf{x}作为正例的相对可能性。对几率取对数得\ln \dfrac{y}{1-y}，称为对数几率（Log Odds，亦称Logit）。
上式实际上使用线性回归模型的预测结果器逼近真实标记的对数几率，因此该模型称为对数几率回归（Logistic Regression，逻辑斯蒂回归）。注意尽管名字为“回归”，实际却是一种分类学习方法，根据近似概率预测“类别”。
【拓展1】确定对数几率回归表达式中\mathbf{w},b的方法：若将y视为类后验概率估计p(y=1\mid \mathbf{x})，则表达式可重写为
\begin{aligned}
\ln \frac{p(y=1\mid \mathbf{x})}{p(y=0\mid \mathbf{x})}=\mathbf{w}^\top \mathbf{x}+b
\end{aligned}显然有
\begin{aligned}
p(y=1\mid \mathbf{x}) &= \frac{\text{e}^{\mathbf{w}^\top \mathbf{x}+b}}{1+\text{e}^{\mathbf{w}^\top \mathbf{x}+b}}\\
p(y=0\mid \mathbf{x}) &= \frac{1}{1+\text{e}^{\mathbf{w}^\top \mathbf{x}+b}}
\end{aligned}故可通过极大似然法（Maximum Likelihood Method）来估计\mathbf{w},b。给定数据集\{(\mathbf{x}_i,y_i)\}_{i=1}^m，对数几率回归模型最大化对数似然（Log-Likelihood）即令每个样本属于其真实标记的概率越大越好（即尽量使所有样本出现真实值的概率乘积最大），表达式如下
\begin{aligned}
\mathcal{l}(\mathbf{w},b)=\sum\limits_{i=1}^m \ln p(y_i \mid \mathbf{x}_i;\mathbf{w},b)
\end{aligned}为便于讨论，令\mathbf{\beta}=(\mathbf{w};b),\ \hat \mathbf{x}=(\mathbf{x};1)，则\mathbf{\beta}^\top \hat \mathbf{x}=\mathbf{w}^\top \mathbf{x}+b。再令p_1(\hat \mathbf{x};\mathbf{\beta})=p(y=1\mid \hat\mathbf{x};\mathbf{\beta}),\ p_0(\hat \mathbf{x};\mathbf{\beta})=p(y=0\mid \hat\mathbf{x};\mathbf{\beta})=1-p_1(\hat \mathbf{x};\mathbf{\beta})，则最大化式中的似然项p(y_i \mid \mathbf{x}_i;\mathbf{w},b)可重写为
\begin{aligned}
p(y_i \mid \mathbf{x}_i;\mathbf{w},b)=y_ip_1(\hat \mathbf{x};\mathbf{\beta})+(1-y_i)p_0(\hat \mathbf{x};\mathbf{\beta})
\end{aligned}将所有衍生、简化、重写后的项代入前式，可得最大化前式等价于最小化下式
\begin{aligned}
\mathcal{l}(\mathbf{\beta})=\sum\limits_{i=1}^m (-y_i\mathbf{\beta}^\top \hat \mathbf{x}_i+\ln (1+\text{e}^{\mathbf{\beta}^\top \hat \mathbf{x}_i}))
\end{aligned}该式是关于\mathbf{\beta}的高阶可导连续凸函数，根据凸优化理论，经典的数值优化算法如梯度下降法（Gradient Descent Method）、牛顿法（Newton Method）等都可求得其最优解，故可得
\begin{aligned}
\mathbf{\beta}^*=\underset{\mathbf{\beta}}{\arg \min} \mathcal{l}(\mathbf{\beta})
\end{aligned}【拓展2】梯度下降法在感知机、BP神经网络等模型里的应用详见后续篇章，此处以牛顿法为例，其第t+1轮迭代解的更新公式为
\begin{aligned}
\mathbf{\beta}^{t+1}=\mathbf{\beta}^t \left ( -\frac{\partial^2\mathcal{l}(\mathbf{\beta})}{\partial \mathbf{\beta} \partial \mathbf{\beta}^\top} \right ) ^{-1}\frac{\partial\mathcal{l}(\mathbf{\beta})}{\partial \mathbf{\beta}}
\end{aligned}其中关于\mathbf{\beta}的一阶、二阶导数分别为
\begin{aligned}
\frac{\partial\mathcal{l}(\mathbf{\beta})}{\partial \mathbf{\beta}} &= -\sum\limits_{i=1}^m \hat \mathbf{x}_i(y_i-p_1(\hat \mathbf{x}_i;\mathbf{\beta}))\\
\frac{\partial^2\mathcal{l}(\mathbf{\beta})}{\partial \mathbf{\beta} \partial \mathbf{\beta}^\top} &= \sum\limits_{i=1}^m \hat \mathbf{x}_i \hat \mathbf{x}_i^\top p_1(\hat \mathbf{x}_i; \mathbf{\beta})(1-p_1(\hat \mathbf{x}_i; \mathbf{\beta}))
\end{aligned}3 线性判别分析
线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的线性学习方法，在二分类问题上类似于Fisher判别分析（主要区别为LDA假设了各类样本的协方差矩阵相同且满秩）。基本思想为：给定训练样例集，将训练样本投影到一条直线上，使得同类样例投影点尽可能接近，异类样例投影点尽可能远；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别。如图所示：
给定数据集D=\{(\mathbf{x}_i,y_i)\}_{i=1}^m,\ y_i \in \{0,1\}，令X_i,\mathbf{\mu}_i,\mathbf{\Sigma}_i分别表示第i\in \{0,1\}类示例的集合、均值向量、协方差矩阵。若将数据投影到直线\mathbf{w}上，则两类样本的中心在直线上的投影分别为\mathbf{w}^\top\mathbf{\mu}_0,\mathbf{w}^\top\mathbf{\mu}_1；若将所有样本点都投影到直线上，则两类样本的协方差分别为\mathbf{w}^\top \mathbf{\Sigma}_0\mathbf{w},\mathbf{w}^\top \mathbf{\Sigma}_1\mathbf{w}。由于直线是一维空间，故\mathbf{w}^\top\mathbf{\mu}_0,\mathbf{w}^\top\mathbf{\mu}_1,\mathbf{w}^\top \mathbf{\Sigma}_0\mathbf{w},\mathbf{w}^\top \mathbf{\Sigma}_1\mathbf{w}\in \mathbb{R}。
欲使同类样例投影点尽可能接近、异类样例投影点尽可能远离，可以让同类样例投影点的协方差之和\mathbf{w}^\top \mathbf{\Sigma}_0\mathbf{w}+\mathbf{w}^\top \mathbf{\Sigma}_1\mathbf{w}尽可能小、类中心之间的距离\left \| \mathbf{w}^\top\mathbf{\mu}_0-\mathbf{w}^\top\mathbf{\mu}_1 \right \| _2^2尽可能大。同时考虑二者，则可得到欲最大化的目标
\begin{aligned}
J &= \frac{\left \| \mathbf{w}^\top\mathbf{\mu}_0-\mathbf{w}^\top\mathbf{\mu}_1 \right \| _2^2}{\mathbf{w}^\top \mathbf{\Sigma}_0\mathbf{w}+\mathbf{w}^\top \mathbf{\Sigma}_1\mathbf{w}}\\
&= \frac{\mathbf{w}^\top(\mathbf{\mu}_0-\mathbf{\mu}_1)(\mathbf{\mu}_0-\mathbf{\mu}_1)^\top\mathbf{w}}{\mathbf{w}^\top(\mathbf{\Sigma}_0+\mathbf{\Sigma}_1)\mathbf{w}}
\end{aligned}LDA定义了两个散度矩阵：
- 类内散度矩阵（Within-Class Scatter Matrix）：越小越好
\begin{aligned}
\mathbf{S}_\text{w} &=\mathbf{\Sigma}_0+\mathbf{\Sigma}_1\\
&=\sum\limits_{\mathbf{x} \in X_0} (\mathbf{x}-\mathbf{\mu}_0)(\mathbf{x}-\mathbf{\mu}_0)^\top + \sum\limits_{\mathbf{x}\in X_1}(\mathbf{x}-\mathbf{\mu}_1)^\top
\end{aligned}- 类间散度矩阵（Between-Class Scatter Matrix)：越大越好
\begin{aligned}
\mathbf{S}_\text{b} &=(\mathbf{\mu}_0-\mathbf{\mu}_1)(\mathbf{\mu}_0-\mathbf{\mu}_1)^\top
\end{aligned}则可改写得LDA欲最大化的目标，即\mathbf{S}_\text{w},\mathbf{S}_\text{b}的广义瑞利商（Generalized Rayleigh Quotient），如下所示
\begin{aligned}
J &= \frac{\mathbf{w}^\top\mathbf{S}_\text{b}\mathbf{w}}{\mathbf{w}^\top\mathbf{S}_\text{w}\mathbf{w}}
\end{aligned}从而将分类问题转化为最优化求解\mathbf{w}的问题。当求解出\mathbf{w}后，对新的样本进行分类时，只需将该样本点投影到这条直线上，根据与各个类别的中心值进行比较，从而判定出新样本与哪个类别距离最近。求解\mathbf{w}的方法如下：观察广义瑞利商表达式发现分子分母都是关于\mathbf{w}的二次项，故其解与\mathbf{w}的长度无关，只与其方向有关。不失一般性，令\mathbf{w}^\top\mathbf{S}_\text{w}\mathbf{w}=1，则最大化原式等价于
\begin{aligned}
\min\limits_{\mathbf{w}} -\mathbf{w}^\top\mathbf{S}_\text{b}\mathbf{w}\ \text{ s.t. }\ \mathbf{w}^\top\mathbf{S}_\text{w}\mathbf{w}=1
\end{aligned}由拉格朗日乘子法，则上式等价于
\begin{aligned}
\mathbf{S}_\text{b}\mathbf{w}=\lambda\mathbf{S}_\text{w}\mathbf{w}
\end{aligned}其中\lambda为拉格朗日乘子。注意到\mathbf{S}_\text{b}\mathbf{w}的方向恒为\mathbf{\mu}_0-\mathbf{\mu}_1，不妨令
\begin{aligned}
\mathbf{S}_\text{b}\mathbf{w}=\lambda(\mathbf{\mu}_0-\mathbf{\mu}_1)
\end{aligned}代入即可解得
\begin{aligned}
\mathbf{w}=\mathbf{S}_\text{w}^{-1}(\mathbf{\mu}_0-\mathbf{\mu}_1)
\end{aligned}考虑到数值解的稳定性，在实践中一般是通过对\mathbf{S}_\text{w}进行奇异值分解来进行求逆，即令\mathbf{S}_\text{w}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^\top，其中实对角矩阵\mathbf{\Sigma}的对角线上的元素为\mathbf{S}_\text{w}的奇异值，然后即可求得\mathbf{S}_\text{w}^{-1}=\mathbf{V}\mathbf{\Sigma}^{-1}\mathbf{U}^\top。
值得一提的是，LDA可从贝叶斯决策理论的角度来阐释，并可证明，当两类数据同先验、满足高斯分布且协方差相等时，LDA可达到最优分类。
【拓展】可将LDA推广至多分类任务中。假定存在N个类，且第i类示例数为m_i。首先定义全局散度矩阵，其中\mathbf{\mu}为所有示例的均值向量：
\begin{aligned}
\mathbf{S}_\text{t} &= \mathbf{S}_\text{b}+\mathbf{S}_\text{w}\\
&= \sum\limits_{i=1}^m(\mathbf{x}_i-\mathbf{\mu})(\mathbf{x}_i-\mathbf{\mu})^\top
\end{aligned}将类内散度矩阵重定义为每个类别的散度矩阵之和：
\begin{aligned}
\mathbf{S}_\text{w} &= \sum\limits_{i=1}^m \mathbf{S}_{\text{w}_i},\ \mathbf{S}_{\text{w}_i}=\sum\limits_{\mathbf{x}\in X_i}(\mathbf{x}_i-\mathbf{\mu}_i)(\mathbf{x}_i-\mathbf{\mu}_i)^\top
\end{aligned}故可求得重定义后的类间散度矩阵：
\begin{aligned}
\mathbf{S}_\text{b} &= \mathbf{S}_\text{t}-\mathbf{S}_\text{w}\\
&= \sum\limits_{i=1}^N m_i(\mathbf{\mu}_i-\mathbf{\mu})(\mathbf{\mu}_i-\mathbf{\mu})^\top
\end{aligned}显然，多分类LDA有多种实现方法：使用\mathbf{S}_\text{t},\mathbf{S}_\text{w},\mathbf{S}_\text{b}三者中任意两个即可。常见的一种实现是采用优化目标
\begin{aligned}
\max\limits_{\mathbf{W}} \frac{\text{tr}(\mathbf{W}^\top\mathbf{S}_{\text{b}}\mathbf{W})}{\text{tr}(\mathbf{W}^\top\mathbf{S}_{\text{w}}\mathbf{W})}
\end{aligned}其中\mathbf{W} \in \mathbb{R}^{d\times (N-1)}，\text{tr}(\cdot)表示矩阵的迹（Trace），该式可通过如下广义特征值问题求解：
\mathbf{S}_{\text{b}}\mathbf{W}=\lambda\mathbf{S}_{\text{w}}\mathbf{W}\mathbf{W}的闭式解则是\mathbf{S}_{\text{w}}^{-1}\mathbf{S}_{\text{b}}的N-1个最大广义特征值所对应的特征向量组成的矩阵。
若将\mathbf{W}视为一个投影矩阵，则多分类LDA将样本投影到N-1维空间，N-1通常远小于数据原有的属性数。于是，可通过这个投影来减小样本点的维数，且投影过程中使用了类别信息，因此LDA也常被视为一种经典的监督降维技术。
4 多分类学习
现实中经常遇到不只两个类别的分类问题，即多分类问题。给定数据集D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_m,y_m)\}，假定其中有N个真实类别，即y_i\in \{C_1,C_2,\dots,C_N\}，在这种情形下，常运用“拆分”的策略，通过多个二分类学习器来解决多分类问题，即将多分类问题拆解为多个二分类问题，训练出多个二分类学习器，最后将多个分类结果进行集成得出结论。分类学习器常称为分类器（Classifier）。
最经典的三种拆分策略及其思想如下：
- “一对一”（One vs. One，OvO）：将这
N个类别进行两两配对（一个正类C_i和一个反类C_j），从而产生\dfrac{N(N-1)}2个二分类学习器；在测试阶段，将新样本放入所有的二分类学习器中测试，得出N(N-1)个结果，最终通过投票产生最终的分类结果。 - “一对其余”（One vs. Rest，OvR）：每次取出一个类作为正类，剩余的所有类别作为一个新的反类，从而产生
N个二分类学习器；在测试阶段，得出N个结果，若仅有一个学习器预测为正类，则对应的类标作为最终分类结果。- 从分类器的数量上看，OvO的存储开销和测试时间开销通常比OvR大。但在训练时，OvR的每个分类器均使用全部训练样例，而OvO的每个分类器仅用到两个类的样例，因此，在类别很多时，OvO的训练时间开销通常比OvR更小。至于预测性能，则取决于具体的数据分布，在多数情形下两者差不多。
- “多对多”（Many vs. Many，MvM）：每次取若干个类作为正类，若干个类作为反类（OvO和OvR是MvM的特例）。最常用的MvM技术是纠错输出码（Error Correcting Output Codes，ECOC）将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。
ECOC工作过程主要分为两步：
- 编码：对
N个类别进行M次正类-反类划分，产生M个训练集，可训练出M个分类器。 - 解码（位于测试阶段）：
M个分类器分别对测试样本进行预测，这些预测标记组成一个新的编码。将这个预测编码与每个类别各自的编码进行比较，最终通过计算海明距离或欧式距离选择距离最小的类别作为最终分类结果。
类别划分通过编码矩阵（Coding Matrix）指定，常见的形式有二元码（将每个类别分别指定为正类和反类）和三元码（在正、反类之外，还可指定不参与计算的“停用类”），如下图所示（其中白色为正例，黑色为反例，无数值的为“停用类”）：
5 类别不平衡问题
类别不平衡（Class-Imbanlance）指的是分类问题中不同类别的训练样本相差悬殊的情况（本节中假设反例数量远超正例，例如反例有998个，而正例只有2个），即使原始问题中不同类别的训练样例数目相当，在使用OvR、MvM策略后产生的二分类任务仍可能出现类别不平衡现象，因此有必要了解类别不平衡性处理的基本方法。
再使用线性分类器y=\mathbf{w}^\top \mathbf{x}+b对新样本\mathbf{x}进行分类时，事实上是在用预测出的y值与一个阈值进行比较，y实际上表达了正例的可能性，几率\dfrac{y}{1-y}则反映了正例可能性与反例可能性之比值。通常将该阈值设为0.5，此时恰表明分类器认为真实正、反例可能性相同，即分类器决策规则为
\begin{aligned}
\text{if }\ \frac{y}{1-y}\gt 1\ \text{ then\ Positive}
\end{aligned}然而当训练集中正、反例的数目不同时，令m^+,m^-分别表示正、反例数目，则观测几率为\dfrac{m^+}{m^-}，由于通常假设训练集是真实样本总体的无偏采样，因此观测几率就代表了真实几率。故理论上只要分类器的预测几率高于观测几率就应判定为正例，即
\begin{aligned}
\text{if }\ \frac{y}{1-y}\gt \frac{m^+}{m^-}\ \text{ then\ Positive}
\end{aligned}然而分类器是基于\dfrac{y}{1-y}\gt 1进行决策，因此，需对其预测值进行调整，使其在基于\dfrac{y}{1-y}\gt 1决策时，实际是在执行\dfrac{y}{1-y}\gt \frac{m^+}{m^-}。方法非常简单，只需令
\begin{aligned}
\frac{y'}{1-y'}= \frac{y}{1-y}\times \frac{m^-}{m^+}
\end{aligned}这就是类别不平衡学习的一种基本策略——再缩放（Rescaling，再平衡，Rebalance）。由于现有技术无法十分有效地基于训练集观测几率推断真实几率，一般使用以下3类具体做法：
- 欠采样（Undersampling，下采样，Downsampling）：直接去除训练集里的一些反类样例（较多的那类），使得正、反例数目接近，然后再进行学习。
- 时间开销相对较小；随意丢弃反例可能会丢失一些重要信息
- 常见算法：EasyEnsemble（利用集成学习机制，将反例划分为若干个集合供不同学习器使用。这样对每个学习器都进行了欠采样，但全局上不会丢失重要信息）
- 过采样（Oversampling，上采样，Upsampling）：往训练集里增加一些正类样例（较少的那类），使得正、反例数目接近，然后再进行学习。
- 时间开销相对较大；不能简单地对初始正例样本进行重复采样，否则会招致严重的过拟合
- 常见算法：SMOTE（对训练集里的正例进行插值来产生额外的正例）
- 直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将如前所述的式子嵌入到其决策过程中，称为阈值移动（Threshold-Moving）。
再缩放是代价敏感学习（Cost-sensitive Learning）的基础（详见“模型的评估与选择”篇之“代价敏感错误率与代价曲线”）。