LDA的建模和分类面

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

\[\begin{align} \label{eq:lda-prob} 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)} \\ &= \frac{f_k(\mathbf{x}) \pi_k}{\sum_{l=1}^K f_l(\mathbf{x}) \pi_l} \end{align}\]

LDA/QDA模型的基本假设是likelihood \(X\vert G\)符合高斯分布，即：

\[f_k(\mathbf{x}) = \frac{1}{(2\pi)^{p/2} | \Sigma_k |^{1/2}} e^{-\frac{1}{2}(\mathbf{x}-\boldsymbol{\mu}_k)^T \Sigma_k^{-1} (\mathbf{x}-\boldsymbol{\mu}_k)}\]

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

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

\[\begin{align} \label{eq:lda-boundary} \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} \\ &= \log \frac{\pi_k}{\pi_l} - \frac{1}{2}(\boldsymbol{\mu}_k + \boldsymbol{\mu}_l)^T \Sigma^{-1} (\boldsymbol{\mu}_k - \boldsymbol{\mu}_l) + \mathbf{x}^T\Sigma^{-1}(\boldsymbol{\mu}_k - \boldsymbol{\mu}_l) \end{align}\]

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

\[\delta_k^{LDA}(\mathbf{x}) = \mathbf{x}^T\Sigma^{-1}\boldsymbol{\mu}_k - \frac{1}{2} \boldsymbol{\mu}_k^T \Sigma^{-1} \boldsymbol{\mu}_k + \log \pi_k\]

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

\[\begin{equation} \label{eq:qda-discriminant} \delta_k^{QDA}(\mathbf{x}) = -\frac{1}{2} \log |\Sigma_k| - \frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^T \Sigma_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) + \log \pi_k \end{equation}\]

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

参数估计和分类

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

\[G(x) = \operatorname{argmax}\limits_k \delta_k(x)\]

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

\[\hat{\pi} = N_k / N\] \[\hat{\boldsymbol{\mu}}_k = \sum_{g_k = k} \mathbf{x}_i / N_k\] \[\hat{\Sigma} = \sum_{k=1}^K \sum_{g_i = k} \frac{(\mathbf{x}_i - \hat{\boldsymbol{\mu}}_k) (\mathbf{x}_i - \hat{\boldsymbol{\mu}}_k)^T} {N-K}\]

其中\(N_k\)是第\(k\)类的样本数量

Fisher降维

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

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

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

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

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

\[\begin{equation} \label{eq:sphere-projection} \mathbf{x}^{*} \gets D^{-1/2} U^T\mathbf{x} \end{equation}\]

可得：

\[\begin{align*} \Sigma^{*} &= \mathrm{E}\left[ (\mathbf{x}^{*} -\boldsymbol{\mu}^{*}) (\mathbf{x}^{*} -\boldsymbol{\mu}^{*})^T \right] \\ &= D^{-1/2}U^T \mathrm{E}\left[ (\mathbf{x} -\boldsymbol{\mu}) (\mathbf{x} -\boldsymbol{\mu})^T \right] U D^{-1/2} \\ &= D^{-1/2}U^T \Sigma U D^{-1/2} \\ &= D^{-1/2} U^T (UDU^T) UD^{-1/2} \\ &= I \end{align*}\]

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

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

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

降维

由上一节我们看到，通过球形化样本，将数据投射到一个新的空间，在这个空间中，协方差矩阵\(\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}-\boldsymbol{\mu}_k)(\mathbf{x}_{ki}-\boldsymbol{\mu}_k)^T\)
  3. 计算中心点投影\(M^{*} = MW^{-1/2}\)（利用特征值分解\(W=UDU^T\)）
  4. 计算投影后的类间(between-class)协方差矩阵 \(B^{*}_{(p\times p)} = \sum_{k=1}^{K} (\mathbf{m}^{*}_k - \bar{\mathbf{m}}^{*})(\mathbf{m}^{*}_k - \bar{\mathbf{m}}^{*})^T\)， 其中\(\mathbf{m}^{*}_k\)表示\(M^{*}\)的第\(k\)行转置后得到的向量，\(\bar{m}^{*}_{j} = \frac{1}{K}\sum_{i=1}^K M_{ij}^{*}\)
  5. 计算\(B^{*}\)的特征值分解\(B^{*} = V^{*}D_B^{*} V^{*T}\)，\(V^{*}\)的各列向量\(\mathbf{v}_l^{*}\)就定义了(Fisher)最优的投影子空间（按对应特征值由大到小顺序排列）
  6. 得到原始样本的Fisher主元\(z_l = \mathbf{v}_l^T \mathbf{x}\)，其中\(\mathbf{v}_l = W^{-1/2}\mathbf{v}_l^{*}\)

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

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

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

\[maximize \quad \mathbf{a}^{*T} B^{*} \mathbf{a}^{*} \quad s.t. \quad \mathbf{a}^{*T} \mathbf{a}^{*} = 1\]

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

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

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

\[\begin{align*} &\max\limits_\mathbf{a} \mathbf{a}^T B \mathbf{a} \\ &\quad s.t. \quad \mathbf{a}^T W \mathbf{a} = 1 \end{align*}\]

或者等价的：

\[\max\limits_\mathbf{a} \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，由\(\ref{eq:lda-boundary}\)式，其分类面为：

\[\begin{align*} \log \frac{P(G=k|X=\mathbf{x})}{P(G=l|X=\mathbf{x})} &= \log \frac{\pi_k}{\pi_l} - \frac{1}{2}(\boldsymbol{\mu}_k + \boldsymbol{\mu}_l)^T \Sigma^{-1} (\boldsymbol{\mu}_k - \boldsymbol{\mu}_l) + \mathbf{x}^T\Sigma^{-1}(\boldsymbol{\mu}_k - \boldsymbol{\mu}_l) \\ &= \alpha_{k0} + \boldsymbol{\alpha}_{k}^T \mathbf{x} \end{align*}\]

相应的Logistic Regression的分类面：

\[\log \frac{P(G=k|X=\mathbf{x})}{P(G=l|X=\mathbf{x})} = \beta_{k0} + \boldsymbol{\beta}_k^T \mathbf{x}\]

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

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