[Note]ESL-4.3-Linear Discriminant Analysis

LDA的建模和分类面

现有分类$G$和随机变量$X$，LDA的思想就是根据后验概率$P(G|X)$对分类面进行线性建模。由贝叶斯公式，得到

$$\begin{array}{}\text{(1)}& P(G=k|X=\mathbf{x})& =\frac{P(X=\mathbf{x}|G=k)\cdot P(G=k)}{\sum _{l=1}^{K}P(X=\mathbf{x}|G=k)\cdot P(G=k)}\text{(2)}& & =\frac{f_k(\mathbf{x}){\pi }_k}{\sum _{l=1}^K{f}_l(\mathbf{x}){\pi }_l}\end{array}$$

LDA/QDA模型的基本假设是likelihood $X|G$符合高斯分布，即：

$$f_k(\mathbf{x})=\frac{1}{(2\pi {)}^{p/2}|{\mathrm{\Sigma }}_k{|}^{1/2}}{e}^{-\frac{1}{2}(\mathbf{x}-{\mathit{\mu }}_k{)}^T{\mathrm{\Sigma }}_k^{-1}(\mathbf{x}-{\mathit{\mu }}_k)}$$

对于LDA而言，其假设所有类的协方差矩阵都相等，即${\mathrm{\Sigma }}_k=\mathrm{\Sigma }\mathrm{\forall }k$，而QDA则没有这样的假设。

下面我们考察LDA的分类面（decision boundary）：

$$\begin{array}{}\text{(3)}& \log \frac{P(G=k|X=\mathbf{x})}{P(G=l|X=\mathbf{x})}& =\log \frac{f_k(\mathbf{x})}{f_l(\mathbf{x})}+\log \frac{{\pi }_k}{{\pi }_l}\text{(4)}& & =\log \frac{{\pi }_k}{{\pi }_l}-\frac{1}{2}({\mathit{\mu }}_k+{\mathit{\mu }}_l{)}^T{\mathrm{\Sigma }}^{-1}({\mathit{\mu }}_k-{\mathit{\mu }}_l)+{\mathbf{x}}^T{\mathrm{\Sigma }}^{-1}({\mathit{\mu }}_k-{\mathit{\mu }}_l)\end{array}$$

可见这是$\mathbf{x}$的线性函数，即LDA中的『Linear』。由此得到线性判别函数为：

$${\delta }_k^{LDA}(\mathbf{x})={\mathbf{x}}^T{\mathrm{\Sigma }}^{-1}{\mathit{\mu }}_k-\frac{1}{2}{\mathit{\mu }}_k^T{\mathrm{\Sigma }}^{-1}{\mathit{\mu }}_k+\log {\pi }_k$$

相应的，QDA的判别函数为：

$$\begin{array}{}\text{(5)}& {\delta }_k^{QDA}(\mathbf{x})=-\frac{1}{2}\log |{\mathrm{\Sigma }}_k|-\frac{1}{2}(\mathbf{x}-{\mathit{\mu }}_k{)}^T{\mathrm{\Sigma }}_k^{-1}(\mathbf{x}-{\mathit{\mu }}_k)+\log {\pi }_k\end{array}$$

注意到这是$\mathbf{x}$的二次函数，即QDA中的『Quadratic』。

参数估计和分类

最后分类，很显然应该将样本归入判别函数较大的那一类去：

$$G(x)={\mathrm{argmax}}_k{\delta }_k(x)$$

当然判别函数中相关的参数需要通过样本来估计，无偏估计为：

$$\hat{\pi }=N_k/N$$ $${\hat{\mathit{\mu }}}_k=\sum _{g_k=k}{\mathbf{x}}_i/N_k$$ $$\hat{\mathrm{\Sigma }}=\sum _{k=1}^K\sum _{g_i=k}\frac{({\mathbf{x}}_i-{\hat{\mathit{\mu }}}_k)({\mathbf{x}}_i-{\hat{\mathit{\mu }}}_k{)}^T}{N-K}$$

其中$N_k$是第$k$类的样本数量

Fisher降维

我发现网上大部分笔记对这一节都没有深入介绍，当然书上这部分也的确写得不是很直观。我尽可能做一份详细的注解，方便后来同学理解。

这一节所有的大写$X$表示一个$N\times p$的矩阵，$N$是样本点的个数，$p$是样本维数。

基于协方差的投影变换（样本球形化）

从式$\text{(5)}$我们发现，如果协方差阵${\mathrm{\Sigma }}_k$是一个单位矩阵的话，那么$\mathbf{x}$属于哪一类就仅仅取决于它和每一类中心点${\mathit{\mu }}_k$的距离$\Vert \mathbf{x}-{\mathit{\mu }}_k{\Vert }_2^2$了。于是很自然的想法是，能不能通过对样本投影，使得${\mathrm{\Sigma }}_k=I$呢？简化的，对于LDA而言，既然所有类的协方差矩阵相同，那么同样的投影变换是否可以施加给所有的$\mathbf{x}$，使得$\mathrm{\Sigma }=I$？

答案是肯定的，我们知道协方差矩阵$\mathrm{\Sigma }$是对称正定矩阵，有特征值分解${\mathrm{\Sigma }}_{(p\times p)}=UD{U}^T$，且特征值$d_l>0$。对样本做如下变换：

$$\begin{array}{}\text{(6)}& {\mathbf{x}}^{\ast }\leftarrow D^{-1/2}{U}^T\mathbf{x}\end{array}$$

可得：

$$\begin{array}{rl}{\mathrm{\Sigma }}^{\ast }& =\mathrm{E}[({\mathbf{x}}^{\ast }-{\mathit{\mu }}^{\ast })({\mathbf{x}}^{\ast }-{\mathit{\mu }}^{\ast }{)}^T]\\ & =D^{-1/2}{U}^T\mathrm{E}[(\mathbf{x}-\mathit{\mu })(\mathbf{x}-\mathit{\mu }{)}^T]U{D}^{-1/2}\\ & =D^{-1/2}{U}^T\mathrm{\Sigma }U{D}^{-1/2}\\ & =D^{-1/2}{U}^T(UD{U}^T)U{D}^{-1/2}\\ & =I\end{array}$$

这样，给定一个新样本$\mathbf{x}$，LDA就可以通过如下两步计算进行分类：

1. 对输入样本球形化（sphere）：${\mathbf{x}}^{\ast }\leftarrow D^{-1/2}{U}^T\mathbf{x}$
2. 在新的空间中，计算${\mathbf{x}}^{\ast }$和各类中心点${\mathit{\mu }}_k^{\ast }$的欧几里德距离（2-范数），并把它归入与之距离最小的那个类（注意还需乘上先验${\pi }_k$）

第1步之所以被称作『球形化』，是因为协方差矩阵$\mathrm{\Sigma }$定义了一个椭球（的焦距），当$\mathrm{\Sigma }=I$时就是一个球形。

降维

由上一节我们看到，通过球形化样本，将数据投射到一个新的空间，在这个空间中，协方差矩阵$\mathrm{\Sigma }=I$，对新样本的分类仅取决于每个类的中心点。这就意味着我们其实只需要$K$个点就能保留所有的分类信息。

进一步的，这$K$个点组成了一个$K-1$维的仿射空间，通过向这个空间投影，我们可以用$K-1$维表示样本的分类信息。

那么接下来的问题是，能不能进一步降维到$L<K-1$呢？

Fisher的回答是，只要投影后各类中心点尽可能地散开，那这就是一个好的降维方法。而所谓『尽可能地散开』就是『variance尽可能大』的意思。

基于这个思想，Fisher提出了以下投影方法：

1. 计算每个类的中心点，得到中心点矩阵$M_{(K\times p)}$
2. 计算类内(within-class)的协方差矩阵$W_{(p\times p)}=\sum _{k=1}^K\sum _{i=1}^{N_k}({\mathbf{x}}_{ki}-{\mathit{\mu }}_k)({\mathbf{x}}_{ki}-{\mathit{\mu }}_k{)}^T$
3. 计算中心点投影$M^{\ast }=M{W}^{-1/2}$（利用特征值分解$W=UD{U}^T$）
4. 计算投影后的类间(between-class)协方差矩阵 $B_{(p\times p)}^{\ast }=\sum _{k=1}^K({\mathbf{m}}_k^{\ast }-{\overline{\mathbf{m}}}^{\ast })({\mathbf{m}}_k^{\ast }-{\overline{\mathbf{m}}}^{\ast }{)}^T$， 其中${\mathbf{m}}_k^{\ast }$表示$M^{\ast }$的第$k$行转置后得到的向量，${\overline{m}}_j^{\ast }=\frac{1}{K}\sum _{i=1}^K{M}_{ij}^{\ast }$
5. 计算$B^{\ast }$的特征值分解$B^{\ast }=V^{\ast }{D}_B^{\ast }{V}^{\ast T}$，$V^{\ast }$的各列向量${\mathbf{v}}_l^{\ast }$就定义了(Fisher)最优的投影子空间（按对应特征值由大到小顺序排列）
6. 得到原始样本的Fisher主元$z_l={\mathbf{v}}_l^T\mathbf{x}$，其中${\mathbf{v}}_l=W^{-1/2}{\mathbf{v}}_l^{\ast }$

我对以上步骤做一些说明：

• 第2步计算$M^{\ast }=M{W}^{-1/2}$，根据我们上一节的描述$\text{(6)}$，这个变换将中心点投影到一个新的子空间${\mathbf{m}}^{\ast }\leftarrow D^{-1/2}{U}^T\mathbf{m}$，在这个空间中，类内(within-class)样本的协方差$W^{\ast }=I$

• 第5步计算$B^{\ast }$的特征向量，按对应特征值从大到小其实是以下优化目标的解（可参考PCA）

$$maximize{\mathbf{a}}^{\ast T}{B}^{\ast }{\mathbf{a}}^{\ast }s.t.{\mathbf{a}}^{\ast T}{\mathbf{a}}^{\ast }=1$$

• 第4步我们把投影变换展开，可得$B^{\ast }=D^{-1/2}{U}^T[\sum _{k=1}^K({\mathbf{m}}_k-\overline{\mathbf{m}})({\mathbf{m}}_k-\overline{\mathbf{m}}{)}^T]U{D}^{-1/2}=W^{1/2}B{W}^{-1/2}$，定义$\mathbf{a}=W^{1/2}{\mathbf{a}}^{\ast }$，有${\mathbf{a}}^{\ast T}{B}^{\ast }{\mathbf{a}}^{\ast }={\mathbf{a}}^{T}B\mathbf{a}$，这也就是第6步中的${\mathbf{v}}_l=W^{-1/2}{\mathbf{v}}_l^{\ast }$

• 另外以上所谓的『协方差矩阵』并不是严格意义上的『样本协方差矩阵』。由于我们只对最优化解感兴趣，协方差前面乘以的常数并不影响最终结果。

综上我们可以总结得到，Fisher变换是在解如下优化问题：

$$\begin{array}{rl}& \underset{\mathbf{a}}{max}{\mathbf{a}}^{T}B\mathbf{a}\\ & s.t.{\mathbf{a}}^{T}W\mathbf{a}=1\end{array}$$

或者等价的：

$$\underset{\mathbf{a}}{max}\frac{{\mathbf{a}}^{T}B\mathbf{a}}{{\mathbf{a}}^{T}W\mathbf{a}}$$

即，使得降维后样本的类间(between-class)方差尽可能地大，而类内(with-class)方差尽可能地小。

LDA和Logistic Regression的比较

这一节我们比较一下Linear Discriminent Analysis和Logistic Regression。对于LDA，由$\text{3}$式，其分类面为：

$$\begin{array}{rl}\log \frac{P(G=k|X=\mathbf{x})}{P(G=l|X=\mathbf{x})}& =\log \frac{{\pi }_k}{{\pi }_l}-\frac{1}{2}({\mathit{\mu }}_k+{\mathit{\mu }}_l{)}^T{\mathrm{\Sigma }}^{-1}({\mathit{\mu }}_k-{\mathit{\mu }}_l)+{\mathbf{x}}^T{\mathrm{\Sigma }}^{-1}({\mathit{\mu }}_k-{\mathit{\mu }}_l)\\ & ={\alpha }_{k0}+{\mathit{\alpha }}_k^T\mathbf{x}\end{array}$$

相应的Logistic Regression的分类面：

$$\log \frac{P(G=k|X=\mathbf{x})}{P(G=l|X=\mathbf{x})}={\beta }_{k0}+{\mathit{\beta }}_k^T\mathbf{x}$$

可见两者实质是一样的。但对于参数估计而言，LDA估计的是高斯分布下的均值和方差。从这点看，LR的假设更弱，因而也更general一些。

另外由$\text{1}$式，可知LDA的优化目标其实是联合分布$P(G=k,X=\mathbf{x})$（分母上的边缘分布可看作常数），而LR是直接优化后验$P(G=k|X=\mathbf{x})$