区别于话题模型的LDA (Latent Dirichlet Allocation)
二类LDA(Linear Discriminant Analysis)
| 二类 | 原空间D维 | 投影空间1维 |
|---|---|---|
| 点 | 向量$\mathbf{x}$ | 标量$y$ |
| 类中心 | 向量$\mathbf{m_k}$ | 标量$\mu_k$ |
如果原始特征数太多，想将D维特征降到只有1维，即这1维就能决定每个样例的类别。
记这个最佳的向量为$\mathbf w$ (D维)，那么样例$\mathbf x$ (D维)到$\mathbf w$上的投影表示为
$$y=\mathbf w^T\mathbf x$$
这里得到的$y$值不是0/1值，而是$\mathbf x$投影到$\mathbf w$上的点到原点的距离。
注意：这个式子并不是超平面，只是向量内积。
D维原空间
- 寻找每类样例的均值（中心点）
$\mathbf m_0=\frac{1}{N_0}\sum_{\mathbf x\in C_0}\mathbf x$
$\mathbf m_1=\frac{1}{N_1}\sum_{\mathbf x\in C_1}\mathbf x$ - 得到投影后，两类的中心
$\mu_0=w^T\mathbf m_0$
$\mu_1=w^T\mathbf m_1$ - 投影前的协方差
$S_0=\sum_{\mathbf x\in C_0}\mathbf{(x-m_0)(x-m_0)}^T$
$S_1=\sum_{\mathbf x\in C_1}\mathbf{(x-m_1)(x-m_1)}^T$ - 投影后的方差
$s_0^2=\sum_{y\in C_0}(y-\mu_0)^2$
$s_1^2=\sum_{y\in C_1}(y-\mu_1)^2$
目标值优化
使类间距尽可能大，类内部的距离尽可能小
$$max_w J(\mathbf{w})=\frac{(\mu_0-\mu_1)^2}{s_0^2+s_1^2}$$
分子化简
$(\mu_0-\mu_1)^2=\mathbf {(w^Tm_0-w^Tm_1)}^2$
$=\mathbf{w^T(m_0-m_1)(m_0-m_1)^Tw}$
$=\mathbf w^TS_B\mathbf w$
其中，$S_B$ 称为between-class covariance matrix
$S_B=\mathbf {(m_0-m_1)(m_0-m_1)}^T$分母化简
$s_k^2=\sum_{y\in C_k}(y-\mu_k)^2$
$=\sum_{\mathbf x\in C_k}\mathbf {(w^Tx-w^Tm_k)}^2$
$=\sum_{\mathbf x\in C_k}\mathbf {w^T(x-m_k)(x-m_k)}^T\mathbf w$
$=\mathbf w^T\{\sum_{\mathbf x\in C_k}\mathbf {(x-m_k)(x-m_k)}^T\}\mathbf w$
$=\mathbf w^TS_k\mathbf w$
其中，$S_k=\sum_{\mathbf x\in C_k}\mathbf {(x-m_k)(x-m_k)}^T$
$S_W$ 称为within-class convariance matrix
$S_W=S_0+S_1$
$=\sum_{\mathbf x\in C_0}\mathbf {(x-m_0)(x-m_0)}^T+\sum_{\mathbf x\in C_1}\mathbf {(x-m_1)(x-m_1)}^T$
改写后的目标值优化
$$J(\mathbf{w})=\frac{\mathbf w^TS_B\mathbf w}{\mathbf w^TS_W\mathbf w}$$
求解w
分子分母都是关于$\mathbf w$的二次形式，如果$\mathbf w$是解，那么$\alpha \mathbf w$也是解。因此固定分母为1，求分子的最大。
$$min_\mathbf w -\mathbf w^TS_B\mathbf w$$
$$s.t. \mathbf w^TS_W\mathbf w=1$$
解：
$L(\mathbf w)=-\mathbf w^TS_B\mathbf w+\lambda(\mathbf w^TS_W\mathbf w-1)=0$
$\frac{\partial L(\mathbf w)}{\partial \mathbf w}=2S_B\mathbf w-2\lambda S_W\mathbf w=0$
$S_B\mathbf w=\lambda S_W\mathbf w$
${S_W}^{-1}S_B\mathbf w=\lambda \mathbf w$
因为 $S_B=\mathbf {(m_0-m_1)(m_0-m_1)}^T$，
两边同时乘$w$，得 $S_B\mathbf w=\mathbf {(m_0-m_1)(m_0-m_1)}^T\mathbf w$
令$\lambda = \mathbf {(m_0-m_1)}^T\mathbf w$，而且这里的$\lambda$等同于拉格朗日中的$\lambda$，则此时$\mathbf w$已定，
$S_B\mathbf w=\mathbf {(m_0-m_1)}\lambda$，代入上式，得，
${S_W}^{-1}\mathbf {(m_0-m_1)}\lambda=\lambda \mathbf w$
${S_W}^{-1}\mathbf {(m_0-m_1)}=\mathbf w$
因此，只需要求出原始样本的均值和方差就可以求出最佳的方向，
$$\mathbf w={S_W}^{-1}(\mathbf m_0-\mathbf m_1)$$
实际求解过程中，对$S_W$进行奇异值分解，即$S_W=U\Sigma V^T$，$\Sigma$是一个实对角线矩阵，其对角线上的元素是$S_W$的奇异值。然后在有$S_W^{-1}=V\Sigma^{-1} U^T$得到$S_W^{-1}$
多类LDA
| 多类 | 原空间D维 | 投影空间d维 |
|---|---|---|
| 点 | 向量$\mathbf{x}$ | 向量$\mathbf y$ |
| 类中心 | 向量$\mathbf{m_k}$ | 向量$\mathbf{\mu_k}$ |
| 总中心 | 向量$\mathbf{m}$ | 向量$\mathbf{\mu}$ |
之前讨论的是如何将D维降到1维，现在类别多了，1维可能已经不满足要求。假设有K个类别，需要投影到d维空间。
$y_i=\mathbf {w_i}^T\mathbf x$， 其中$i=1,2,…,d$，$\mathbf {w_i}$可以称作基向量。
$\mathbf y=\mathbf W^T\mathbf x$，其中$W$的第$i$列为$w_i$
$\mathbf W$的维数$D\times d$
$D$维原空间
within-class convariance matirx
$S_W=\sum_{k=1}^{K}\sum_{\mathbf x\in C_k}\mathbf {(x-m_k)(x-m_k)}^T$
其中，$\mathbf {m_k}=\frac{1}{N_k}\sum_{\mathbf x\in C_k}\mathbf x$ ，$C_k$为$k$类数据子集
$S_W$的维数$D\times D$
total covariance matrix
$S_T=\sum_{\mathbf x\in C}\mathbf {(x-m)(x-m)}^T$
其中，$\mathbf m=\frac{1}{N}\sum_{\mathbf x\in C}\mathbf x$ ，$C$为数据全集
$S_T$的维数$D\times D$
between-class convariance matrix
$S_B$需一些改变，原来度量的是两个均值点的散列情况，现在度量的是每类均值点相对于样本中心的散列情况。
$S_B=\sum_{k=1}^KN_k\mathbf {(m_k-m)(m_k-m)}^T$
$S_B$的维数$D\times D$
对于多类问题，$S_T=S_W+S_B$；但对于二类问题，$S_T\neq S_W+S_B$，因为$S_B$的定义不同
$d$维投影空间
within-class convariance matirx
$S_W=\sum_{k=1}^K\sum_{\mathbf y\in C_k}\mathbf {(y-\mu_k)(y-\mu_k)}^T$
其中，$\mathbf {\mu_k}=\frac{1}{N_k}\sum_{\mathbf y\in C_k}\mathbf y$ ，$C_k$为$k$类数据子集
$S_W$的维数$d\times d$
between-class convariance matrix
$S_B=\sum_{k=1}^KN_k\mathbf{(\mu_k-\mu)(\mu_k-\mu)}^T$
其中，$\mathbf {\mu}=\frac{1}{N}\sum_{\mathbf y\in C}\mathbf y$ ，$C$为数据全集
$S_B$的维数$d\times d$
目标值优化
$$max_W\frac{tr(\mathbf W^TS_B\mathbf W)}{tr(\mathbf W^TS_W\mathbf W)}$$
通过广义特征值来求解，
$$S_W^{-1}S_B\mathbf W=\lambda \mathbf W$$
$\mathbf W$的闭式解释是$S_W^{-1}S_B$的前$d$个最大的特征值对应的特征向量，所组成的$N\times d$维的$\mathbf W$。
总结
LDA可以分类，也可以用于有监督的降维。
而PCA，ICA，manifold learning都属于无监督的降维。
Reference
- PRML
- 《机器学习》周志华
- http://www.cnblogs.com/jerrylead/archive/2011/04/21/2024384.html
- https://en.wikipedia.org/wiki/Linear_discriminant_analysis
