机器学习: 线性判别分析（LDA）

一、简介

线性判别分析( Linear Discriminant Analysis,简称LDA)是一种经典的线性学习方法,在二分类问题上因为最早由 Fisher,1936提出,亦称“ Fisher判别分析。严格来说LDA与Fisher判别分析稍有不同。前者假设了各类样本的协方差矩阵相同且满秩。

LDA 的思想非常朴素: 给定训练样法将样例投影到一条使得同 样例的投影点尽可能接近、 异类样例投影点尽可能能远离;在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别. 如下图所示。

若此时我们使用PCA，我们会得到不可分状况，就是蓝色与绿色样本点都混在一起，详见主成分分析(PCA)。

一、两类LDA的情况

可以看见，跟主成分分析(PCA) 一样，LDA事实上也可以看作一种降维方法。那PCA和LDA有什么区别呢？

(1) PCA是无监督的（即不需要类标辅助来进行寻找用来降维的变换矩阵W），而LDA则需要类标来寻找用于降维的变换矩阵W）
(2) 两者的目标也不一样，PCA想要的是所有点与点之间尽可能地分开，而LDA想要寻找样本类间距离最大和类内距离最小的投影矩阵。

我们首先讨论数据集只有两种类别的情况，然后将其推广到多类别的情况。

我们令$X_i,{\mu }_i,{\sum }_i$分别表示第i类样本的集合，均值向量和协方差矩阵。设样本的维度是d，我们使用$\mathbf{w}\in R^{d\times 1}$将样本映射到一维空间（直线上）。

现在使同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小（类比d=1时，样本方差越近则样本点约集中，现在d != 1, 需令其协方差尽可能小），也就是${\mathbf{w}}^{\mathrm{T}}{\mathbf{\Sigma }}_0\mathbf{w}+{\mathbf{w}}^{\mathrm{T}}{\mathbf{\Sigma }}_1\mathbf{w}$尽可能小（投影点的协方差可以将分量展开，可验证确实为此公式）。另外我们希望不同类的样本投影尽可能远离，可以让类中心之间的距离尽可能大，即 ${\Vert {\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_0-{\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_1\Vert }_2^2$ 尽可能大.同时考虑二者，则可得到欲最大化的目标

J = ∥ w T μ 0 − w T μ 1 ∥ 2 2 w T Σ 0 w + w T Σ 1 w = w T ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w w T ( Σ 0 + Σ 1 ) w

$$\begin{aligned} J &=\frac{\left\|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\mu}_{0}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\mu}_{1}\right\|_{2}^{2}}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\Sigma}_{0} \boldsymbol{w}+\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\Sigma}_{1} \boldsymbol{w}} \\ &=\frac{\boldsymbol{w}^{\mathrm{T}}\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)^{\mathrm{T}} \boldsymbol{w}}{\boldsymbol{w}^{\mathrm{T}}\left(\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1}\right) \boldsymbol{w}} \end{aligned}$$ J​=wTΣ0​w+wTΣ1​w∥∥​wTμ0​−wTμ1​∥∥​22​​=wT(Σ0​+Σ1​)wwT(μ0​−μ1​)(μ0​−μ1​)Tw​​

定义类内散度矩阵${\mathbf{S}}_{\mathbf{w}}$（w是指within-class scatter matrix)
S w = Σ 0 + Σ 1 = ∑ x ∈ X 0 ( x − μ 0 ) ( x − μ 0 ) T + ∑ x ∈ X 1 ( x − μ 1 ) ( x − μ 1 ) T

$$\begin{aligned} \mathbf{S}_{w} &=\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1} \\ &=\sum_{\boldsymbol{x} \in X_{0}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{0}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{0}\right)^{\mathrm{T}}+\sum_{\boldsymbol{x} \in X_{1}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{1}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{1}\right)^{\mathrm{T}} \end{aligned}$$ Sw​​=Σ0​+Σ1​=x∈X0​∑​(x−μ0​)(x−μ0​)T+x∈X1​∑​(x−μ1​)(x−μ1​)T​

以及类间散度矩阵${\mathbf{S}}_{\mathbf{b}}$（b是指between-class scatter matrix)

$${\mathbf{S}}_b=\left({\mathbf{\mu }}_0-{\mathbf{\mu }}_1\right){\left({\mathbf{\mu }}_0-{\mathbf{\mu }}_1\right)}^{\mathrm{T}}$$

因此我们的目标转化为以下形式，又称${\mathbf{S}}_{\mathbf{b}},{\mathbf{S}}_{\mathbf{w}}$的广义瑞利商（generalized Rayleigh quotient）

$$J=\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_b\mathbf{w}}{{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathbf{w}}$$

因为上式中分子分母都是关于$\mathbf{w}$的二次型，所以目标值域$\mathbf{w}$的方向相关。我们令${\mathrm{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathbf{w}$,此时可以使用拉格朗日乘子法求$\mathbf{w}$，如下所示：

min ⁡ w − w T S b w  s.t.  w T S w w = 1

$$\begin{array}{ll} \min _{w} & -\boldsymbol{w}^{\mathrm{T}} \mathbf{S}_{b} \boldsymbol{w} \\ \text { s.t. } & \boldsymbol{w}^{\mathrm{T}} \mathbf{S}_{w} \boldsymbol{w}=1 \end{array}$$ minw​ s.t. ​−wTSb​wwTSw​w=1​

$${\mathbf{S}}_b\mathbf{w}=\lambda {\mathbf{S}}_w\mathbf{w}$$

此处求解待补充，建议查看《南瓜书PumpkinBook》

一、多类LDA的情况

现在我们将其推广到多类的情形，并且讨论不仅仅时映射到一维空间的情况（即降维）。

设类别的数目为N，且第i类示例数为$m_i$，总样本数量为m。由于此时存在多个类，我们不能再用类均值投影点的差值使得类中心之间的距离尽可能大。此时转换一个思路，如果说我们的映射能够使得所有样本点之间都尽量的远离（也就是全局的协方差尽可能大），但类内的样本点都尽可能大靠拢（也就是类内样本点的协方差尽可能小），那么此时就相当于类与类之间的样本点会远离（否则全局协方差不可能是大的）。

因此，我们定义全局散度矩阵

S t = ∑ i = 1 m ( x i − μ ) ( x i − μ ) T

$$\begin{aligned} \mathbf{S}_{t} &=\sum_{i=1}^{m}\left(\boldsymbol{x}_{i}-\boldsymbol{\mu}\right)\left(\boldsymbol{x}_{i}-\boldsymbol{\mu}\right)^{\mathrm{T}} \end{aligned}$$ St​​=i=1∑m​(xi​−μ)(xi​−μ)T​

其中$\mu$是所有样本的均值向量。

类内矩阵散度${\mathbf{S}}_{\mathbf{w}}$跟原来的定义一致，原来是两个，现在是N个。

$${\mathbf{S}}_w=\sum _{i=1}^N{\mathbf{S}}_{w_i}$$
$${\mathbf{S}}_{w_i}=\sum _{\mathbf{x}\in X_i}\left(\mathbf{x}-{\mathbf{\mu }}_i\right){\left(\dot{\mathbf{x}}-{\mathbf{\mu }}_i\right)}^{\mathrm{T}}$$

由此推导的类间矩阵散度${\mathbf{S}}_{\mathbf{b}}$为
S b = S t − S w = ∑ i = 1 m ( x i − μ ) ( x i − μ ) T − ∑ i = 1 N ∑ x ∈ X i ( x − μ i ) ( x − μ i ) T = ∑ i = 1 N ( ∑ x ∈ X i ( ( x − μ ) ( x − μ ) T − ( x − μ i ) ( x − μ i ) T ) ) = ∑ i = 1 N ( ∑ x ∈ X i ( ( x − μ ) ( x T − μ T ) − ( x − μ i ) ( x T − μ i T ) ) ) = ∑ i = 1 N ( ∑ x ∈ X i ( x x T − x μ T − μ x T + μ μ T − x x T + x μ i T + μ i x T − μ i μ i T ) ) = ∑ i = 1 N ( ∑ x ∈ X i ( − x μ T − μ x T + μ μ T + x μ i T + μ i x T − μ i μ i T ) ) = ∑ i = 1 N ( − ∑ x ∈ X i x μ T − ∑ x ∈ X i μ x T + ∑ x ∈ X i μ μ T + ∑ x ∈ X i x μ i T + ∑ x ∈ X i μ i x T − ∑ x ∈ X i μ i μ i T ) = ∑ i = 1 N ( − m i μ i μ T − m i μ μ i T + m i μ μ T + m i μ i μ i T + m i μ i μ i T − m i μ i μ i T ) = ∑ i = 1 N ( − m i μ i μ T − m i μ μ i T + m i μ μ T + m i μ i μ i T ) = ∑ i = 1 N m i ( − μ i μ T − μ μ i T + μ μ T + μ i μ i T ) = ∑ i = 1 N m i ( μ i − μ ) ( μ i − μ ) T

$$\begin{aligned} \mathbf{S}_b &= \mathbf{S}_t - \mathbf{S}_w \\ &= \sum_{i=1}^m(\boldsymbol x_i-\boldsymbol\mu)(\boldsymbol x_i-\boldsymbol\mu)^{\mathrm{T}}-\sum_{i=1}^N\sum_{\boldsymbol x\in X_i}(\boldsymbol x-\boldsymbol\mu_i)(\boldsymbol x-\boldsymbol\mu_i)^{\mathrm{T}} \\ &= \sum_{i=1}^N\left(\sum{\boldsymbol x\in X_i}\left((\boldsymbol x-\boldsymbol\mu)(\boldsymbol x-\boldsymbol\mu)^{\mathrm{T}}-(\boldsymbol x-\boldsymbol\mu_i)(\boldsymbol x-\boldsymbol\mu_i)^{\mathrm{T}}\right)\right) \\ &= \sum_{i=1}^N\left(\sum_{\boldsymbol x\in X_i}\left((\boldsymbol x-\boldsymbol\mu)(\boldsymbol x^{\mathrm{T}}-\boldsymbol\mu^{\mathrm{T}})-(\boldsymbol x-\boldsymbol\mu_i)(\boldsymbol x^{\mathrm{T}}-\boldsymbol\mu_i^{\mathrm{T}})\right)\right) \\ &= \sum_{i=1}^N\left(\sum_{\boldsymbol x\in X_i}\left(\boldsymbol x\boldsymbol x^{\mathrm{T}} - \boldsymbol x\boldsymbol\mu^{\mathrm{T}}-\boldsymbol\mu\boldsymbol x^{\mathrm{T}}+\boldsymbol\mu\boldsymbol\mu^{\mathrm{T}}-\boldsymbol x\boldsymbol x^{\mathrm{T}}+\boldsymbol x\boldsymbol\mu_i^{\mathrm{T}}+\boldsymbol\mu_i\boldsymbol x^{\mathrm{T}}-\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}\right)\right) \\ &= \sum_{i=1}^N\left(\sum_{\boldsymbol x\in X_i}\left(- \boldsymbol x\boldsymbol\mu^{\mathrm{T}}-\boldsymbol\mu\boldsymbol x^{\mathrm{T}}+\boldsymbol\mu\boldsymbol\mu^{\mathrm{T}}+\boldsymbol x\boldsymbol\mu_i^{\mathrm{T}}+\boldsymbol\mu_i\boldsymbol x^{\mathrm{T}}-\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}\right)\right) \\ &= \sum_{i=1}^N\left(-\sum_{\boldsymbol x\in X_i}\boldsymbol x\boldsymbol\mu^{\mathrm{T}}-\sum_{\boldsymbol x\in X_i}\boldsymbol\mu\boldsymbol x^{\mathrm{T}}+\sum_{\boldsymbol x\in X_i}\boldsymbol\mu\boldsymbol\mu^{\mathrm{T}}+\sum_{\boldsymbol x\in X_i}\boldsymbol x\boldsymbol\mu_i^{\mathrm{T}}+\sum_{\boldsymbol x\in X_i}\boldsymbol\mu_i\boldsymbol x^{\mathrm{T}}-\sum_{\boldsymbol x\in X_i}\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}\right) \\ &= \sum_{i=1}^N\left(-m_i\boldsymbol\mu_i\boldsymbol\mu^{\mathrm{T}}-m_i\boldsymbol\mu\boldsymbol\mu_i^{\mathrm{T}}+m_i\boldsymbol\mu\boldsymbol\mu^{\mathrm{T}}+m_i\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}+m_i\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}-m_i\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}\right) \\ &= \sum_{i=1}^N\left(-m_i\boldsymbol\mu_i\boldsymbol\mu^{\mathrm{T}}-m_i\boldsymbol\mu\boldsymbol\mu_i^{\mathrm{T}}+m_i\boldsymbol\mu\boldsymbol\mu^{\mathrm{T}}+m_i\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}\right) \\ &= \sum_{i=1}^Nm_i\left(-\boldsymbol\mu_i\boldsymbol\mu^{\mathrm{T}}-\boldsymbol\mu\boldsymbol\mu_i^{\mathrm{T}}+\boldsymbol\mu\boldsymbol\mu^{\mathrm{T}}+\boldsymbol\mu_i\boldsymbol\mu_i^{\mathrm{T}}\right) \\ &= \sum_{i=1}^N m_i(\boldsymbol\mu_i-\boldsymbol\mu)(\boldsymbol\mu_i-\boldsymbol\mu)^{\mathrm{T}} \end{aligned}$$ Sb​​=St​−Sw​=i=1∑m​(xi​−μ)(xi​−μ)T−i=1∑N​x∈Xi​∑​(x−μi​)(x−μi​)T=i=1∑N​(∑x∈Xi​((x−μ)(x−μ)T−(x−μi​)(x−μi​)T))=i=1∑N​(x∈Xi​∑​((x−μ)(xT−μT)−(x−μi​)(xT−μiT​)))=i=1∑N​(x∈Xi​∑​(xxT−xμT−μxT+μμT−xxT+xμiT​+μi​xT−μi​μiT​))=i=1∑N​(x∈Xi​∑​(−xμT−μxT+μμT+xμiT​+μi​xT−μi​μiT​))=i=1∑N​(−x∈Xi​∑​xμT−x∈Xi​∑​μxT+x∈Xi​∑​μμT+x∈Xi​∑​xμiT​+x∈Xi​∑​μi​xT−x∈Xi​∑​μi​μiT​)=i=1∑N​(−mi​μi​μT−mi​μμiT​+mi​μμT+mi​μi​μiT​+mi​μi​μiT​−mi​μi​μiT​)=i=1∑N​(−mi​μi​μT−mi​μμiT​+mi​μμT+mi​μi​μiT​)=i=1∑N​mi​(−μi​μT−μμiT​+μμT+μi​μiT​)=i=1∑N​mi​(μi​−μ)(μi​−μ)T​

事实上，依照严格的协方差定义，应该是要在求和项前除以样本数，但周老师的书里面都没有除以样本数。但从目标公式来看，这并不影响$\mathbf{w}$求解的准确性。但在有些资料里面类间散度矩阵定义为$$\sum _{i=1}^N({\mathbf{\mu }}_i-\mathbf{\mu })({\mathbf{\mu }}_i-\mathbf{\mu }{)}^{\mathrm{T}}$$

三、LDA用于降维

上面的情况都是使用$\mathbf{w}$将样本映射到一维空间。也就是把样本直接降到了一维。

我们看到在以下公式中，
$${\mathbf{S}}_b\mathbf{w}=\lambda {\mathbf{S}}_w\mathbf{w}$$

$\mathbf{w}$其实是可看成矩阵${\mathbf{S}}_w^{-1}{\mathbf{S}}_b$的最大特征向量，而对于${\mathbf{S}}_w^{-1}{\mathbf{S}}_b\in R^{d\times d}$，其特征向量不止一个。

因此，若设$\mathbf{W}=\left({\mathbf{w}}_1,{\mathbf{w}}_2,\dots ,{\mathbf{w}}_i,\dots ,{\mathbf{w}}_{N-1}\right)\in {\mathbb{R}}^{d\times (N-1)}$

那么我们有

{ tr ⁡ ( W T S b W ) = ∑ i = 1 N − 1 w i T S b w i tr ⁡ ( W T S w W ) = ∑ i = 1 N − 1 w i T S w w i \left\{

$$\begin{aligned} \operatorname{tr}\left(\mathbf{W}^{\mathrm{T}} \mathbf{S}_{b} \mathbf{W}\right) &=\sum_{i=1}^{N-1} \boldsymbol{w}_{i}^{\mathrm{T}} \mathbf{S}_{b} \boldsymbol{w}_{i} \\ \operatorname{tr}\left(\mathbf{W}^{\mathrm{T}} \mathbf{S}_{w} \mathbf{W}\right) &=\sum_{i=1}^{N-1} \boldsymbol{w}_{i}^{\mathrm{T}} \mathbf{S}_{w} \boldsymbol{w}_{i} \end{aligned}$$ \right. ⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​tr(WTSb​W)tr(WTSw​W)​=i=1∑N−1​wiT​Sb​wi​=i=1∑N−1​wiT​Sw​wi​​

同样地，我们希望这些映射仍能满足类间距离尽可能大，类内距离尽可能小，因此有

$$\underset{\mathbf{W}}{\max }\frac{{\sum }_{i=1}^{N-1}{\mathbf{w}}_i^{\mathrm{T}}\mathbf{S}b{\mathbf{w}}_i}{{\sum }_{i=1}^{N-1}{\mathbf{w}}_i^{\mathrm{T}}{\mathbf{S}}_w{\mathbf{w}}_i}$$

也就是
$$\underset{\mathbf{W}}{\max }\frac{\mathrm{tr}({\mathbf{W}}^{\mathrm{T}}{\mathbf{S}}_b\mathbf{W})}{\mathrm{tr}({\mathbf{W}}^{\mathrm{T}}\mathbf{S}w\mathbf{W})}$$

此时仍根据拉格朗日乘子法求解
$${\mathbf{S}}_b\mathbf{W}=\lambda {\mathbf{S}}_w\mathbf{W}$$

$\mathbf{W}$的闭式解则是${\mathbf{S}}_w^{-1}{\mathbf{S}}_b$的N-1个最大广义特征值所对应的特征向量组成的矩阵.（为什么这里是N-1个仍待探究）

问题：${\mathbf{S}}_w^{-1}$并不总是存在的

在实践中,${\mathbf{S}}_w^{-1}$通常是退化的,比如数据是具有大维度d的图像向量,而数据集的大小小于d。

此时我们通常先对数据进行一个PCA，来降低数据的维度。

然后进行一个LDA，使得测试数据更容易进行分类，准确率更高。

我们称y为Most Expressive Features (MEF)：使用PCA得到的特征(投影)。我们称z为Most Discriminating Features (MDF)利用LDA获得的特征(投影)。

四、PCA和LDA的区别

(1)当训练集较小时，PCA的表现优于LDA。
(2)当样本数量较大且对每一类具有代表性时，LDA的表现往往优于PCA。

参考资料

[1] 《机器学习》周志华
[2]《南瓜书PumpkinBook》