LDA简介

末蓝、 2022-11-15 11:36 254阅读 0赞

注：最近在看LDA，其实之前也看过，也了解过LDA，但是最近想要追根溯源，想去看看LD的发展的路径，所以决定从头开始看LDA。

### LDA简介 ###

*  问题描述
 *   *  算法求解

这篇博客中介绍的LDA是最原始的，Fisher的论文(The use of multiple measurements in taxonomic problems)中介绍的，此处介绍一下这篇论文中针对LDA的求解方法以及思路。

# 问题描述 #

Fisher最初引入LDA是为了解决二分类问题，在论文中用的例子是比较经典的鸢尾花的分类问题。说是有三类鸢尾花，每个鸢尾花对应有四个特征，要给鸢尾花们进行分类。但是论文中在讲述算法的时候还是去解决的二分类问题，也就是去区分两类鸢尾花。此处我们先把四个特征用 x 1 , x 2 , x 3 , x 4 x\_1,x\_2,x\_3,x\_4 x1,x2,x3,x4来表示，开篇提出的思路就是能否找到一个线性函数 X = λ 1 x 1 + λ 2 x 2 + λ 3 x 3 + λ 4 x 4 X=\\lambda\_1 x\_1+\\lambda\_2 x\_2+\\lambda\_3 x\_3+\\lambda\_4 x\_4 X=λ1x1\+λ2x2\+λ3x3\+λ4x4，该线性函数能够最大化类的均值之间的差别(the difference between the specific means)和类内标准差(the standard deviations within species)的比值。

## 算法求解 ##

首先，我们将两个不同种类的鸢尾花的均值之间的差记作 d 1 , d 2 , d 3 , d 4 d\_1,d\_2,d\_3,d\_4 d1,d2,d3,d4，这四个均值之间的差在用前面提到的线性函数作用后得到 D = λ 1 d 1 + λ 2 d 2 + λ 3 d 3 + λ 4 d 4 D=\\lambda\_1 d\_1+\\lambda\_2 d\_2+\\lambda\_3 d\_3+\\lambda\_4 d\_4 D=λ1d1\+λ2d2\+λ3d3\+λ4d4，之后我们就要来定义类内标准差了，此处虽然说的是标准差，但是用的其实还是协方差阵。此处记为 S S S，S有如下结构：  
 S = \[ S 11 S 12 S 13 S 14 S 12 S 22 S 23 S 24 S 13 S 23 S 33 S 34 S 14 S 24 S 34 S 44 \] S= \\begin\{bmatrix\} S\_\{11\} & S\_\{12\} & S\_\{13\} & S\_\{14\} \\\\ S\_\{12\} & S\_\{22\} & S\_\{23\} & S\_\{24\} \\\\ S\_\{13\} & S\_\{23\} & S\_\{33\} & S\_\{34\} \\\\ S\_\{14\} & S\_\{24\} & S\_\{34\} & S\_\{44\} \\end\{bmatrix\} S=⎣⎢⎢⎡S11S12S13S14S12S22S23S24S13S23S33S34S14S24S34S44⎦⎥⎥⎤  
注意上面这个矩阵是协方差阵，是对称矩阵，所以我就把对称部分标记为同一个 S i j S\_\{ij\} Sij了。所以我们最终的目标就是要最大化  
 D 2 W \\frac\{D^2\}\{W\} WD2  
其中， W = y T S y , y = \[ λ 1 , λ 2 , λ 3 , λ 4 \] T W=y^TSy,y=\[\\lambda\_1,\\lambda\_2,\\lambda\_3,\\lambda\_4\]^T W=yTSy,y=\[λ1,λ2,λ3,λ4\]T。上面那个优化目标，就是之后在LDA问题中会一直提到的Fisher准则，对于该优化目标的求解，Fisher并没有用广义特征值问题去求解，而是用的求导的方法：  
 D W 2 \{ 2 W ∂ D ∂ y − D ∂ W ∂ y \} = 0 ; \\frac\{D\}\{W^2\}\\\{2W\\frac\{\\partial D\}\{\\partial y\}-D\\frac\{\\partial W\}\{\\partial y\}\\\}=0; W2D\{ 2W∂y∂D−D∂y∂W\}=0;  
上面的求导用到了一个重要的矩阵微分公式： ∂ x T A x ∂ x = A x + A T x \\frac\{\\partial x^TAx\}\{\\partial x\}=Ax+A^Tx ∂x∂xTAx=Ax\+ATx，其中 x x x为向量，此处需要注意 W W W为对称矩阵，所以有个系数2。  
将上面的式子移项之后就得到  
 1 2 ∂ W ∂ y = W D ∂ D ∂ y , \\frac\{1\}\{2\}\\frac\{\\partial W\}\{\\partial y\}=\\frac\{W\}\{D\}\\frac\{\\partial D\}\{\\partial y\}, 21∂y∂W=DW∂y∂D,  
此时注意， S D \\frac\{S\}\{D\} DS是一个常数，所以把上面的式子展开就得到  
 S 11 λ 1 + S 12 λ 2 + S 13 λ 3 + S 14 λ 4 = d 1 , S 12 λ 1 + S 22 λ 2 + S 23 λ 3 + S 24 λ 4 = d 2 , S 13 λ 1 + S 23 λ 2 + S 33 λ 3 + S 34 λ 4 = d 3 , S 14 λ 1 + S 24 λ 2 + S 34 λ 3 + S 44 λ 4 = d 4 . S\_\{11\}\\lambda\_1+S\_\{12\}\\lambda\_2+S\_\{13\}\\lambda\_3+S\_\{14\}\\lambda\_4=d\_1,\\\\ S\_\{12\}\\lambda\_1+S\_\{22\}\\lambda\_2+S\_\{23\}\\lambda\_3+S\_\{24\}\\lambda\_4=d\_2,\\\\ S\_\{13\}\\lambda\_1+S\_\{23\}\\lambda\_2+S\_\{33\}\\lambda\_3+S\_\{34\}\\lambda\_4=d\_3,\\\\ S\_\{14\}\\lambda\_1+S\_\{24\}\\lambda\_2+S\_\{34\}\\lambda\_3+S\_\{44\}\\lambda\_4=d\_4. S11λ1\+S12λ2\+S13λ3\+S14λ4=d1,S12λ1\+S22λ2\+S23λ3\+S24λ4=d2,S13λ1\+S23λ2\+S33λ3\+S34λ4=d3,S14λ1\+S24λ2\+S34λ3\+S44λ4=d4.  
上面的展开中，舍去了一些常数倍，所以最终得到的 y y y的方向是正确的的，但是大小会跟真实结果相差一个倍数，其实无所谓了，反正最后会标准化。  
其实上面的那个方程组我们可以写成矩阵的形式：  
 S y = \[ d 1 , d 2 , d 3 , d 4 \] T , Sy=\[d\_1,d\_2,d\_3,d\_4\]^T, Sy=\[d1,d2,d3,d4\]T,  
当 S S S为正定矩阵时，我们就可以得到 y = S − 1 \[ d 1 , d 2 , d 3 , d 4 \] T y=S^\{-1\}\[d\_1,d\_2,d\_3,d\_4\]^T y=S−1\[d1,d2,d3,d4\]T，所以我们就求得了线性函数的系数。  
所以到这里，LDA算法就可以求解出来了，上面求得的 y y y就是Fisher最优投影轴，样本在投影到这个方向上后，能够使得类内散度最小，而类间散度最大。  
在这篇文献中，只给出了求解一个最优投影轴的方向，如果想求解多个的话，没有给出方法，当然后面有文献给出了具体的方法。  
这篇文献后面还给出了一些实验来对算法进行解释，这里就不提供了。之后文献也对算法进行了分析，但是我没看懂，以后看懂了再来添加吧。