LDA与QDA

LDA原理推导

image-20200502144229237.png

image-20200502144240844.png

image-20200502144247468.png

image-20200502144300358.png

image-20200502144313763.png

image-20200502144320311.png

LDA 学习的Bayes解决方案

一般地，对于多分类问题，假设有 $C$ 个判别函数 $g_c(x): c = 1,...,C$

如果满足
$g_c(x) > g_i(x), \forall i\not=c.$
则将 $x$ 判别为 $c$ 类

判别函数可以替换为任意一个单调函数
$g_c(x) = \ln P(x|c) + \ln P(c)$
对于二分类问题，可以定义如下形式的决策函数与判别函数
$g(x) = g_i(x) - g_j(x) \\ \delta(x) = \left \{ \begin{array}{l} i & g(x)>0 \\ j & g(x) \leq 0 \end{array} \right.$
具体地有
$g_1(x) = P(1|x) - P(0|x) \\ g_1(x) = \ln P(1|x) - \ln P(0|x) = \ln \frac{P(x|1)}{P(x|0)}+\ln \frac{P(1)}{P(0)}$

QDA学习

如果 $P(x|c)$ 服从多元正态分布
$P(x|c) = \frac{1}{(2\pi)^{d/2}|\Sigma_c|^{1/2}}\exp{[-\frac{1}{2}(x -\mu_c)^T\Sigma_c^{-1}{(x - \mu_c)}]}$
其中 $x = (x_1, ...,x_d)^T,\mu_c={(\mu_{c1},...,\mu_{cd})}^T$ ， $\Sigma_{d \times d}$ 是一个协方差矩阵， $|\Sigma_c|$ 是协方差矩阵的行列式

则决策函数可以表示为：
$g_c(x) = \ln P(x,c) = -\frac{1}{2}(x -\mu_c)^T\Sigma_c^{-1}{(x - \mu_c)} - \frac{d}{2}\ln 2\pi - \frac{1}{2} \ln |\Sigma_c| + \ln P(c)$
得出quadratic discriminant analysis(QDA)二次判别的数学模型

对于二分类问题，可以导出相应的判别函数
$\delta(x) = \left \{ \begin{array}{l} 1 & g_1(x)>g_0(x) \\ 0 & g_1(x) \leq g_0(x) \end{array} \right.$
推广到多类，决策函数和判别函数可表示为：
$g_c(x) = \ln P(x,c) = -\frac{1}{2}(x -\mu_c)^T\Sigma_c^{-1}{(x - \mu_c)} - \frac{d}{2}\ln 2\pi - \frac{1}{2} \ln |\Sigma_c| + \ln P(c)\\ \delta(x) = c \times \mathbb I_{[\arg max (g_c(x)) = c]}, c = {1,...,C}$
用极大似然估计表示：
$\hat{g_c}(x) = \ln P(x,c) = -\frac{1}{2}(x -\hat\mu_c)^T\hat \Sigma_c^{-1}{(x - \hat \mu_c)} - \frac{d}{2}\ln 2\pi - \frac{1}{2} \ln |\hat\Sigma_c| + \ln P(c)\\ \hat\mu_c = \frac{1}{n_c}\Sigma_{i=1}^{n_c}x_{ci}\\ \hat\Sigma_c = \frac{1}{n_c}\Sigma_{i=1}^{n_c}(x -\hat\mu_c)^T(x - \hat \mu_c)$
特别地：
- 若 $\Sigma_c = \sigma^2I$ (不同类别的实例具有相同的标准协方差矩阵)
  $g_c(x) = -\frac{||x - \mu_c||^2}{2\sigma^2}+\ln P(c) \\ ||x - \mu_c||^2 = (x -\mu_c)^T{(x - \mu_c)} = x^Tx - 2\mu^T_cx + \mu^T_c\mu_c$
  得到决策函数
  $g_c(x) = w_c^Tx + w_{c0}\\ w_c = \frac{\mu_c}{\sigma^2} \\ w_{c0} = -\frac{1}{2\sigma^2}\mu^T_c\mu_c + \ln P(c)$
  - $x^Tx$ 对不同类的决策函数贡献相同，因此略去
  决策面为
  $g_i(x) = g_j(x),i \not =j \in {1,..,C}\\ w^T(x - x_0) = 0$
  令决策函数相等，化为空间平面的标准形式，通过待定系数解出 $w$ 和 $x_0$
  
  其中
  $w = \mu_i - \mu_j \\ x_0 = \frac{1}{2}(\mu_i + \mu_j) - \frac{\sigma^2}{||\mu_i - \mu_j||^2}\ln \frac{P(i)}{P(j)}(\mu_i - \mu_j)$
  - 若 $P(i) = P(j)$ ，那么 $x_0 = \frac{1}{2}(\mu_i + \mu_j)$
  - 对于二分类问题，QDA得到的决策边界与LDA边界一致
- 若 $\Sigma_c = \Sigma$ （不同类别的实例具有相同的协方差矩阵）
  $g_c(x) = -\frac{1}{2}(x -\mu_c)^T\Sigma_c^{-1}{(x - \mu_c)} - \frac{d}{2}\ln 2\pi - \frac{1}{2} \ln |\Sigma_c| + \ln P(c) \\$
  得到决策函数
  $g_c(x) = w_c^Tx + w_{c0}\\ w_c = \Sigma^{-1}{\mu_c}\\ w_{c0} = -\frac{1}{2}\mu^T_c\Sigma^{-1}\mu_c + \ln P(c)$
  决策面为
  $w^T_c(x - x_0) = 0\\ x_0 = \frac{1}{2}(\mu_i + \mu_j) - \frac{(\mu_i - \mu_j)}{(\mu_i - \mu_j)^T\Sigma^{-1}(\mu_i - \mu_j)}\ln \frac{P(i)}{P(j)}$
- 若 $\Sigma_c$ 任意(不同类别实例具有不同的协方差矩阵)
  
  得到决策函数
  $g_c(x) = x^TW_cx + w^T_cx + w_{c0}$
  其中
  $W_c = -\frac{1}{2}\Sigma_c^{-1}\\ w_c = \Sigma_{c}^{-1}\mu_c\\ w_{c0} = -\frac{1}{2}\mu_{c}^T\Sigma_{c}^{-1} - \frac{1}{2}\ln|\Sigma_c| + \ln P(c)$
$x^TW_cx$ 对不同类的决策函数贡献不同，不能略去，则决策函数的变化导致决策面成为超二次曲面
QDA和LDA的总结

image-20200502114428774.png

The plot shows decision boundaries for Linear Discriminant Analysis and Quadratic Discriminant Analysis. The bottom row demonstrates that Linear Discriminant Analysis can only learn linear boundaries（variances are similar among classes and there are not enough data to accurately estimate the variances）, while Quadratic Discriminant Analysis can learn quadratic boundaries and is therefore more flexible(variances are very different between classes and there are enough observations to accurately estimate the variances).

LDA的优缺点
- 优点：
  1. 降维过程中可以使用类别的先验知识经验
  2. LDA在样本分类信息依赖均值而非方差
- 缺点：
  1. LDA不适合对非高斯分布样本进行降维
  2. LDA最多降1维，LDA的改进算法可以解决多维降维的问题
  3. LDA在样本分类信息依赖方差而非均值时，降维效果不好
  4. LDA可能过度拟合数据

多分类问题

OvO v.s. OvR

image-20200502120946434.png
1. OvO训练更多的分类器，存储开销和测试时间开销比OvR大
2. OvR每次训练需要利用全部训练样例，训练开销比OvO更大
ECOC编码
1. 编码：对N个类别做M次划分，每次划分将一部分作为正类，一部分作为反类，从而形成一个二分类训练集；一共产生M个分类器
2. 解码：M个分类器分别对测试样本进行预测，组成一个编码。将预测编码与每个类别各自的编码进行比较，返回距离最小的类别作为最终预测结果
- 任意两个类别之间的编码距离越远，纠错能力越强，然而在码长较长时难以有效地确定最优编码

image-20200424094640859.png

海明距离：
$L_{Heming} = \Sigma_i\mathbb I _{\hat{f_i}(C) \not = f_i(C)}$
欧氏距离：
$L_{Euclid} = \sqrt{\Sigma_i(\hat{f_i}(C) - f_i(C))^2}$

参考材料

personal.psu.edu/jol2/course/stat597e/notes2/lda.pdf

机器学习周志华