线性判别分析（Linear Discriminat Analysis）

线性判别分析（Linear Discriminat Analysis）

PCA找寻的投影向量力求找到使得特征点方差较大（也就是说散的比较开），与PCA所找寻的投影向量不同，LAD所找寻的投影向量具有下面两种特性：

1. 映射后不同类数据之间的中心点（均值点）相距较远
2. 映射后同类数据之间方差较小（分布比较集中）

类似于一种聚类分析，但是却是一种监督学习算法。而PCA属于一种无监督学习算法。

那么将LDA的主轴与PCA的主轴画出如下：

可以看出实际上数据在映射在 LDA 的主轴上可分性更高。

在下面的正文中的一些数学符号的表示：

$$\begin{array}{rl}L& :\text{ number of classes }\\ n_i& :\text{ number of samples in class }i\\ n& :\text{ number of all samples }\\ x_{\ell }^{(i)}& :\text{ the }\ell \text{ -th sample in class }i\\ P_i& :\text{ the prior probability of class }i\end{array}$$

类间分散矩阵（Between-class Scatter Matrix）

那么所有的样本点 $x_{\ell }^{(i)}$ 在方向 $e$ 上的投影为：

$$\left\{e^T{x}_1^{(1)},\dots ,e^T{x}_{n_1}^{(1)},e^T{x}_1^{(2)},\dots ,e^T{x}_{n_2}^{(2)},\dots ,e^T{x}_{\ell }^{(i)},\dots ,e^T{x}_1^{(L)},\dots ,e^T{x}_{n_L}^{(L)}\right\}$$

投影之后的中心点为：

$$m_i=\frac{1}{n_i}\sum _{\ell =1}^{n_i}{\mathbf{e}}^T{\mathbf{x}}_{\ell }^{(i)}={\mathbf{e}}^T\left\{\frac{1}{n_i}\sum _{\ell =1}^{n_i}{\mathbf{x}}_{\ell }^{(i)}\right\}={\mathbf{e}}^T{\mathbf{m}}_i$$

其中 ${\mathbf{m}}_i=\frac{1}{n_i}{\sum }_{\ell =1}^{n_i}{\mathbf{x}}_{\ell }^{(i)}$ 实际上就是投影之前的中心，所以投影之后的中心则是原数据中心得投影。

那么不同类中心之间的平方距离（欧氏距离）：

$$\begin{array}{rl}& \frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j\left|\left|m_i-m_j\right|\right|\\ =& \frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j(m_i-m_j)(m_i-m_j{)}^T\\ =& \frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j(e^T{\mathbf{m}}_i-e^T{\mathbf{m}}_j)(e^T{\mathbf{m}}_i-e^T{\mathbf{m}}_j{)}^T\\ =& \frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j{e}^T({\mathbf{m}}_i-{\mathbf{m}}_j)({\mathbf{m}}_i-{\mathbf{m}}_j{)}^{T}e\\ =& e^T\underset{S_b^{LDA}}{\underbrace{\left(\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j\left({\mathbf{m}}_i-{\mathbf{m}}_j\right){\left({\mathbf{m}}_i-{\mathbf{m}}_j\right)}^T\right)}}e\end{array}$$

其中 $S_b^{LDA}$ 代表了类间分散矩阵（Between-class Scatter Matrix），其中下标 $b$ 代表的 between。

加入每一类的比例是认为这个距离也就是说拉的有多开，跟这两类数据的占比有关。

下面要证明：

$$S_b^{LDA}=\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j\left({\mathbf{m}}_i-{\mathbf{m}}_j\right){\left({\mathbf{m}}_i-{\mathbf{m}}_j\right)}^T=\sum _{i=1}^L{P}_i\left({\mathbf{m}}_i-\mathbf{m}\right){\left({\mathbf{m}}_i-\mathbf{m}\right)}^T$$

其中 $\mathbf{m}$ 代表了全部样本点的中心（均值）：

$$\mathbf{m}=\frac{1}{n}\sum _{i=1}^L\sum _{\ell =1}^{n_i}{\mathbf{x}}_{\ell }^{(i)}$$

直接换项不容易，所以这里将两边进行整理转换然后使得转换后等式相等。

先进行左边的等式转换：

$$\begin{array}{rl}{S}_b^{LDA}& =\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j\left({\mathbf{m}}_i-{\mathbf{m}}_j\right){\left({\mathbf{m}}_i-{\mathbf{m}}_j\right)}^T\\ & =\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j\left({\mathbf{m}}_i{\mathbf{m}}_i^T-{\mathbf{m}}_i{\mathbf{m}}_j^T-{\mathbf{m}}_j{\mathbf{m}}_i^T+{\mathbf{m}}_j{\mathbf{m}}_j^T\right)\\ & =\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j{\mathbf{m}}_i{\mathbf{m}}_i^T-\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j{\mathbf{m}}_i{\mathbf{m}}_j^T-\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j{\mathbf{m}}_j{\mathbf{m}}_i^T+\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j{\mathbf{m}}_j{\mathbf{m}}_j^T\\ & =\frac{1}{2}\sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T\left(\sum _{j=1}^L{P}_j\right)-\frac{1}{2}\left(\sum _{i=1}^L{P}_i{\mathbf{m}}_i\right)\left(\sum _{j=1}^L{P}_j{\mathbf{m}}_j^T\right)-\frac{1}{2}\left(\sum _{j=1}^L{P}_j{\mathbf{m}}_j\right)\left(\sum _{i=1}^L{P}_i{\mathbf{m}}_i^T\right)+\frac{1}{2}\left(\sum _{i=1}^L{P}_i\right)\sum _{j=1}^L{P}_j{\mathbf{m}}_j{\mathbf{m}}_j^T\end{array}$$

其中所有概率相加为一：

$$\left(\sum _{j=1}^L{P}_j\right)=\left(\sum _{i=1}^L{P}_i\right)=1$$

同时：

$$\begin{array}{rl}{P}_i{\mathbf{m}}_i& =\frac{n_i}{n}\frac{x_1^{(i)}+x_2^{(i)}+\cdots +x_{n_i}^{(n)}}{n_i}\\ & =\frac{1}{n}\left\{x_1^{(i)}+x_2^{(i)}+\cdots +x_{n_i}^{(n)}\right\}\end{array}$$

那么：

$$\begin{array}{rl}\sum _{i=1}^L{P}_i{\mathbf{m}}_i& =\sum _{i=1}^L\frac{1}{n}\left\{x_1^{(i)}+x_2^{(i)}+\cdots +x_{n_i}^{(n)}\right\}\\ & =\frac{1}{n}\left\{x_1^{(1)}+\cdots +x_{n_1}^{(1)}+x_1^{(2)}+\cdots +x_{n_2}^{(2)}+\cdots +x_1^{(i)}+\cdots +x_{n_i}^{(i)}\right\}\\ & =\frac{1}{n}\sum _{i=1}^L\sum _{\ell =1}^{n_i}{\mathbf{x}}_{\ell }^{(i)}=\mathbf{m}\end{array}$$

所以做如下改写：

$$\begin{array}{rl}{S}_b^{LDA}& =\frac{1}{2}\sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T\left(\sum _{j=1}^L{P}_j\right)-\frac{1}{2}\left(\sum _{i=1}^L{P}_i{\mathbf{m}}_i\right)\left(\sum _{j=1}^L{P}_j{\mathbf{m}}_j^T\right)-\frac{1}{2}\left(\sum _{j=1}^L{P}_j{\mathbf{m}}_j\right)\left(\sum _{i=1}^L{P}_i{\mathbf{m}}_i^T\right)+\frac{1}{2}\left(\sum _{i=1}^L{P}_i\right)\sum _{j=1}^L{P}_j{\mathbf{m}}_j{\mathbf{m}}_j^T\\ & =\frac{1}{2}\sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T-\frac{1}{2}\mathbf{m}{\mathbf{m}}^T-\frac{1}{2}\mathbf{m}{\mathbf{m}}^T+\frac{1}{2}\sum _{j=1}^L{P}_j{\mathbf{m}}_j{\mathbf{m}}_j^T\\ & =\sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T-\mathbf{m}{\mathbf{m}}^T\end{array}$$

现在进行右边的等式转换：

$$\begin{array}{rl}& \sum _{i=1}^L{P}_i\left({\mathbf{m}}_i-\mathbf{m}\right){\left({\mathbf{m}}_i-\mathbf{m}\right)}^T\\ =& \sum _{1=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T-\sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}^T-\sum _{i=1}^L{P}_i\mathbf{m}{\mathbf{m}}_i^T+\sum _{i=1}^L{P}_i\mathbf{m}{\mathbf{m}}^T\\ =& \sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T-\left(\sum _{i=1}^L{P}_i{\mathbf{m}}_i\right){\mathbf{m}}^T-\mathbf{m}\left(\sum _{i=1}^L{P}_i{\mathbf{m}}_i^T\right)+\left(\sum _{i=1}^L{P}_i\right)\mathbf{m}{\mathbf{m}}^T\\ =& \sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T-\mathbf{m}{\mathbf{m}}^T-\mathbf{m}{\mathbf{m}}^T+\mathbf{m}{\mathbf{m}}^T\\ =& \sum _{i=1}^L{P}_i{\mathbf{m}}_i{\mathbf{m}}_i^T-\mathbf{m}{\mathbf{m}}^T\end{array}$$

所以两者相等。即：
$$S_b^{LDA}=\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j\left({\mathbf{m}}_i-{\mathbf{m}}_j\right){\left({\mathbf{m}}_i-{\mathbf{m}}_j\right)}^T=\sum _{i=1}^L{P}_i\left({\mathbf{m}}_i-\mathbf{m}\right){\left({\mathbf{m}}_i-\mathbf{m}\right)}^T$$

类内分散矩阵（Within-class Scatter Matrix）

全部类的方差之和为：

$$\begin{array}{rl}& \sum _{i=1}^L{P}_i\sum _{\ell =1}^{n_i}{\left(e^T{x}_{\ell }^{(i)}-m_i\right)}^2\\ =& \sum _{i=1}^L{P}_i\sum _{l=1}^{n_i}{\left(e^T{x}_l^{(i)}-e^T{\mathbf{m}}_i\right)}^2\\ =& \sum _{i=1}^L{P}_i\sum _{l=1}^{n_i}\left(e^T{x}_l^{(i)}-e^T{\mathbf{m}}_i\right){\left(e^T{x}_l^{(i)}-e^T{\mathbf{m}}_i\right)}^T\\ =& e^T\left\{\underset{{\mathbf{S}}_w^{LDA}}{\underbrace{\sum _{i=1}^L{P}_i\sum _{l=1}^{n_i}\left(x_i^{(i)}-{\mathbf{m}}_i\right){\left(x_i^{(i)}-{\mathbf{m}}_i\right)}^T}}\right\}e\end{array}$$

其中 ${\mathbf{S}}_w^{LDA}$ 代表了类间分散矩阵（Within-class Scatter Matrix），其中下标 $w$ 代表的 within。

$${\mathbf{S}}_w^{LDA}=\sum _{i=1}^L{P}_i\sum _{\ell =1}^{n_i}\left({\mathbf{x}}_{\ell }^{(i)}-{\mathbf{m}}_i\right){\left({\mathbf{x}}_{\ell }^{(i)}-{\mathbf{m}}_i\right)}^T$$

希望类（组）间距离越大越好：

$$\frac{1}{2}\sum _{i=1}^L\sum _{j=1}^L{P}_i{P}_j{\left(m_i-m_j\right)}^2=e^T\left(\sum _{i=1}^L{P}_i\left({\mathbf{m}}_i-\mathbf{m}\right){\left({\mathbf{m}}_i-\mathbf{m}\right)}^T\right)e=e^T{\mathbf{S}}_b^{LDA}e$$

希望类（组）间距离越小越好：

$$\sum _{i=1}^L{P}_i\sum _{\ell =1}^{n_i}{\left(e^T{x}_{\ell }^{(i)}-m_i\right)}^2=e^T\left(\sum _{i=1}^L{P}_i\sum _{\ell =1}^{n_i}\left(x_{\ell }^{(i)}-m_i\right){\left(x_{\ell }^{(i)}-m_i\right)}^T\right)e=e^T{\mathbf{S}}_w^{LDA}e$$

所以两个不能分开来看，所以选择目标函数的表示为：

$$e=\arg \underset{e\in R^d}{\max }\frac{e^T{S}_b^{LDA}e}{e^T{S}_w^{LDA}e}$$

来保证分子最大，分母最小，也就是说 组间距离/组内距离 越大越好。

现在引入一个概念：Rayleigh Quotient

$$r(e)=\frac{e^T{S}_b^{LDA}e}{e^T{S}_w^{LDA}e}$$

那么凸最优解，就是求导为零：

$$\begin{array}{rl}\nabla r(\mathbf{e})& =\frac{1}{{\left({\mathbf{e}}^T{\mathbf{S}}_w^{LDA}\mathbf{e}\right)}^2}\left\{\left({\mathbf{e}}^T{\mathbf{S}}_w^{LDA}\mathbf{e}\right)\left(2{\mathbf{S}}_b^{LDA}\mathbf{e}\right)-\left({\mathbf{e}}^T{\mathbf{S}}_b^{LDA}\mathbf{e}\right)\left(2{\mathbf{S}}_w^{LDA}\mathbf{e}\right)\right\}=0\\ & =\frac{1}{e^T{S}_w^{LDA}e}\left\{\underset{0}{\underbrace{1\cdot 2S_b^{LDA}e-\frac{e^T{S}_b^{LDA}e}{e^T{S}_w^{LDA}e}2S_W^{LDA}e}}\right\}\end{array}$$

也就是说

$$S_b^{LDA}e=\frac{e^T{S}_b^{LDA}e}{e^T{S}_w^{LDA}e}{S}_w^{LDA}e=r(e)S_w^{LDA}e$$

这是一种广义特征值问题（generalized eigenvalue problem），即：

$${\mathbf{S}}_b^{LDA}\mathbf{e}=\lambda {\mathbf{S}}_w^{LDA}\mathbf{e}$$

这里的特征向量不在是原来的特征向量而是原来的特征向量乘以一个矩阵，所以是在求 ${\mathbf{S}}_b^{LDA}$ 的广义特征值 $\lambda$ 。

工程上的解法是，做如下转换：

$$\text{pinv}({\mathbf{S}}_w^{LDA}){\mathbf{S}}_b^{LDA}\mathbf{e}=\lambda \mathbf{e}$$

然后使用特征值求解方法。