深度学习知识点汇总-机器学习基础（8）

2.8 LDA的算法原理和算法步骤

输入：数据集 $D={(\boldsymbol x_1,\boldsymbol y_1),(\boldsymbol x_2,\boldsymbol y_2),...,(\boldsymbol x_m,\boldsymbol y_m)}$ ，其中样本 $\boldsymbol x_i$ 是 $n$ 维向量， $\boldsymbol y_i \in {0, 1}$ ，降维后的目标维度 $d$ 。

定义以下符号:

$N_j(j=0,1)$ 为第 $j$ 类样本个数；
$X_j(j=0,1)$ 为第 $j$ 类样本的集合；
$u_j(j=0,1)$ 为第 $j$ 类样本的均值向量；
$\boldsymbol \sigma_j(j=0,1)$ 为第 $j$ 类样本的协方差矩阵。

其中
$u_j = \frac{1}{N_j} \sum_{\boldsymbol x\epsilon X_j}\boldsymbol x \\ \boldsymbol \sigma_j = \sum_{\boldsymbol x\epsilon X_j}(\boldsymbol x-u_j)(\boldsymbol x-u_j)^T$

假设投影直线是向量 $\boldsymbol w$ ，对任意样本 $\boldsymbol x_i$ ，它在直线 $w$ 上的投影为 $\boldsymbol w^T x_i$ ，两个类别的中心点 $u_0$ , $u_1$ 在直线 $w$ 的投影分别为 $\boldsymbol w^Tu_0$ 、 $\boldsymbol w^Tu_1$ 。

LDA的目标

类间距离尽量大。两类别的数据中心间的距离 $| \boldsymbol w^Tu_0 - \boldsymbol w^Tu_1 |^2_2$ 尽量大
类内距离尽量小。同类样本投影点的协方差 $\boldsymbol w^T \boldsymbol \sigma_0 \boldsymbol w$ 、 $\boldsymbol w^T \boldsymbol \sigma_1 \boldsymbol w$ 尽量小。

定义类内散度矩阵
$S_w = \boldsymbol \sigma_0 + \boldsymbol \sigma_1 = \sum_{\boldsymbol x\epsilon X_0}(\boldsymbol x-u_0)(\boldsymbol x-u_0)^T + \sum_{\boldsymbol x\epsilon X_1}(\boldsymbol x-u_1)(\boldsymbol x-u_1)^T$

类间散度矩阵 $S_b = (u_0 - u_1)(u_0 - u_1)^T$

据上分析，优化目标为
$\mathop{\arg\max}_\boldsymbol w J(\boldsymbol w) = \frac{| \boldsymbol w^Tu_0 - \boldsymbol w^Tu_1 |^2_2}{\boldsymbol w^T \boldsymbol \sigma_0\boldsymbol w + \boldsymbol w^T \boldsymbol \sigma_1\boldsymbol w} = \frac{\boldsymbol w^T(u_0-u_1)(u_0-u_1)^T\boldsymbol w}{\boldsymbol w^T(\boldsymbol \sigma_0 + \boldsymbol \sigma_1)\boldsymbol w} = \frac{\boldsymbol w^TS_b\boldsymbol w}{\boldsymbol w^TS_w\boldsymbol w}$