[读书笔记-西瓜书] 线性判别分析：LDA

线性判别分析（Linear Discriminant Analysis, LDA）又称Fisher判别分析，是一种数据降维的方法，主要思想是使属于同一类的投影点距离尽可能地接近（类内方差小），不同类的中心点距离尽可能地远（类间中点距离大）。

LDA就是模识课上黄老板讲的Fisher判别，名字不同而已。思想也很简单，计算也不复杂。首先定义一些变量：

$$x_i：i类数据的训练样本$$

$$\mu_i：i类数据的均值向量$$

$$\Sigma_i：i类数据的协方差矩阵$$

投影到直线$w$上后，样本中心（均值）所在的投影就变为$w^T\mu_i$，协方差变为$w^T\Sigma_i w$，推一下协方差：

展开协方差的定义：$\Sigma_i=\sum_{j=1}^n(x_j-u_i)^2$

变换后的协方差定义：$\Sigma’i=\sum{j=1}^n(w^Tx_j-w^Tu_i)^2$

则有：
$$
\Sigma’i=\sum{j=1}^n(w^Tx_j-w^Tu_i)^2=\sum_{j=1}^n(w^T(x_j-u_i))^2
$$

$$=\sum_{j=1}^nw^T(x_j-u_i)(w^T(x_j-u_i))^T$$

$$=\sum_{j=1}^nw^T(x_j-u_i)(x_j-u_i)^Tw$$

$$=w^T\sum_{j=1}^n(x_j-u_i)^2w$$

$$=w^T\Sigma_iw$$

用变换后的协方差作为衡量类内点的“集中”程度，我们尽可能想让这个值小。于是第一个目标可以用这个值逼近。

为了叙述方便，现在假设分类任务是二分类，分别是0、1类。第二个目标类间距离可以直接比较类内中点之间的距离测度，定义类间距为中点的Euclidean Distance平方：$Dis(0,1)=|w^T\mu_0-w^T\mu_1|^2$来衡量。我们希望这个值尽可能大

定义：$S_w’=\Sigma’_0+\Sigma’_1$，$S_b’=Dis(0,1)$。

同时考虑上述两个指标，于是做商合成一个目标函数（突然想起自己的paper里也搞过这种设计）：

$$J=\dfrac{S_b’}{S_w’}=\dfrac{|w^T\mu_0w-w^T\mu_1|^2}{w^T\Sigma_0w+w^T\Sigma_1w}$$

$$=\dfrac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w}$$

目标即为通过调整$w$最大化$J$，$S’_b$和$S’_w$的比值称为“广义瑞利商”。由于分子和分布都是关于$w$的二次项，因此解只与$w$的方向有关。方程等价于优化下式：

$$\min_w -w^TS’_bw$$

$$st.\ w^TS’_ww=1$$

这是个带约束的极值求解问题，可以用高数中学过的拉格朗日乘数法解决，构造拉格朗日函数：

$$L(w)=-w^TS’_bw+\lambda(w^TS’_ww-1)$$
令上式的导数得0，即可得：
$$w=S_w’^{-1}(\mu_0-\mu_1)$$
问题转换成求解$S’_w$的逆。注意该阵通常情况下不可逆，原因是数据维数和数据条目数通常是不匹配，就是说数据集并不能确定地体现数据的分布情况。

书上介绍的实际是PCA方法，直接给$S’_w$进行SVD分解，得到$S’_w=U\Sigma V^T$，于是$S_w’^{-1}=(U\Sigma V^T)^{-1}=V\Sigma^{-1}U^T$。

最终我们可推得：

$$w=V\Sigma^{-1}U^T(\mu_0-\mu_1)$$