线性判别分析
定义
线性判别分析既可以处理二分类问题, 同时也可以用来做有监督的数据降维.
两类问题(基于贝叶斯方法)
贝叶斯准则回顾
按照贝叶斯公式可知，后验概率正比于似然函数和先验概率的乘积
[math]\displaystyle{ P(y|x) \varpropto P(x|y)P(y) }[/math]
给定输入样本，后验概率最大的类别就是贝叶斯准则下预测的输出.
对于二分类问题, 贝叶斯准则可以简化为判断决策函数的大于零或者小于零。 决策函数是不同类别后验概率的对数似然比。
[math]\displaystyle{ f(x) = logP(x|y=1) - logP(x|y=2) + logP(y=1) - logP(y=2) }[/math]
如果正负样本的数量相同，或者正负类别的先验概率相等，那么决策函数可以进一步简化为，
[math]\displaystyle{ f(x) = logP(x|y=1) - logP(x|y=2) }[/math]
二次判别分析(高斯假设)
假设正负样本采样于不同的高斯分布，
[math]\displaystyle{ P(x|y=1) = N\left(x\left|\mu _1\right.,\Sigma _1\right), }[/math]
[math]\displaystyle{ P(x|y=2) = N\left(x\left|\mu _2\right.,\Sigma _2\right). }[/math]
将以上的分布函数带入到二分类的决策函数中,可以得到二次判别分析的决策函数
[math]\displaystyle{ f_{QDA}(x) = x^T\left(\Sigma _2^{-1}-\Sigma _1^{-1}\right)x - \left(\mu _2^T\Sigma _2^{-1}-\mu _1^T\Sigma _1^{-1}\right)x+\left(\log \left|\Sigma _2\right|-\log |\Sigma _1|+\mu _2^T\Sigma _2^{-1}\mu _2-\mu _1^T\Sigma _1^{-1}\mu _1\right) }[/math]
可以看出, 二次判别分析的决策函数是关于输入特征(or 变量的)二次函数. 从左到右, 决策函数中的三项分别对应着,二次项,一次项和常数项.
线性判别分析(高斯假设+同方差假设)
如果进一步假设, 正负样本的方差相同, 那么二次判别分析就退化为线性判别分析. 在二次判别分析的基础上, 令 [math]\displaystyle{ \Sigma_1 = \Sigma_2 = \Sigma }[/math], 可以很容易得到线性判别分析的决策函数.
[math]\displaystyle{ f_{LDA}(x) = - \left(\mu _2^T\Sigma^{-1}-\mu _1^T\Sigma^{-1}\right)x+\left(\mu _2^T\Sigma^{-1}\mu _2-\mu _1^T\Sigma^{-1}\mu _1\right) }[/math]
可以看出， 因为方差相同的假设， 二次项从原来的决策函数中消失了， 最高次项是线性的. 这也是该方法被称为线性判别分析的原因.
多类问题(Fisher判别分析)
K近邻方法与监督降维
解决多分类问题的一种简单的方式是K近邻投票. K近邻的基本假设是:相邻的样本应该有相同的类别标签. 但是如果训练数据密度不够,那么这个假设的可靠性就会降低,直接导致分类的效果下降. 另外,最近邻搜索的计算和存储成本随着样本的维度线性增长， 当数据维度很高时，对于很多实际应用(实时跟踪或者识别; 有内存限制的设备如手机,相机,等), K近邻方法的成本都过高.
为了解决以上两个问题,一般会用监督降维的方法提取低维的,更有判别力的特征. 这样做,一方面能够提高K近邻方法的效果, 另外一方面会降低成本.
一种监督降维方法--Fisher判别分析
Fisher判别分析就是一种能够达到上述效果的监督降维方法. Fisher判别分析通过同时最小化类内差(同一类别内部样本之间差异), 并且最大化类间差(不同类别样本之间的差异)，获得更加有判别力的低维特征， 以及从高维到低维的线性投影。如果类别数量是K, 那么高维数据将会被投影到K-1的低维空间. 当K=2, 也就是二分类问题时, Fisher判别分析等价于线性判别分析(贝叶斯方法+高斯+同方差假设).
具体推导
具体来说, 假设样本数量是n, 降维之前样本的集合为 [math]\displaystyle{ \{x_1, x_2, ... , x_n \}, x_i\in \mathbb{R}^D }[/math], 他们对应的类别标签是 [math]\displaystyle{ \{y_1, y_2, ... , y_n \}, y_i\in \mathbb{N} }[/math]. 降维之后的样本集合为 [math]\displaystyle{ \{u_1, u_2, ... , u_n \}, u_i\in \mathbb{R}^d }[/math]. 通过一个未知的(待学习的)线性投影 [math]\displaystyle{ W \in \mathbb{R}^{d\times D } }[/math] , 原有的高维数据被映射到对应的低维表示。在新的低维空间中， 类内差 [math]\displaystyle{ \sigma_w }[/math] 被缩小， 类间差 [math]\displaystyle{ \sigma_b }[/math] 被放大. 这里的下标分别是within和between的首字母. 类内差和类间差可以通过如下公式计算,
[math]\displaystyle{ \sigma_w = \sum _{y_i= y_j} \left\|u_i-u_j\|^2\right. }[/math]
[math]\displaystyle{ \sigma_b = \sum _{y_i\neq y_j} \left\|u_i-u_j\|^2\right. }[/math]
考虑到低维表示是原始高维数据的线性投影, 也就是 [math]\displaystyle{ u_i = W x_i }[/math], 将这个线性投影带入到类内差以及类间差的计算公式中可以得到,
[math]\displaystyle{ \sigma_w = trace(S_w W^T W), \quad where~~ S_w = \sum _{y_i = y_j} (x_i-x_j)^T(x_i-x_j) }[/math]
[math]\displaystyle{ \sigma_b = trace(S_b W^T W) , \quad where~~ S_b = \sum _{y_i \neq y_j} (x_i-x_j)^T(x_i-x_j) }[/math]
我们的目标是缩小类内差并且增加类间差. 考虑到, 1)类内差和类间差非负 2)假设类内差不等于零(也就是说类内协方差差矩阵[math]\displaystyle{ S_w }[/math]所有特征值大于0. 一般来说,在样本充足且原始数据维度不是很高的情况下,这个假设成立), 缩小类内差以及增大类间差的双目标可以统一到一个目标函数中, 也就是如下目标函数
[math]\displaystyle{ \underset{W}{\max } \frac{\sigma _b}{\sigma _w} }[/math]
可以证明以上问题的最优解是矩阵[math]\displaystyle{ S_w^{-1} S_b }[/math]的前[math]\displaystyle{ d }[/math]个特征向量组成的线性投影矩阵. 每一个特征向量将原始高维数据投影到低维空间相对应的维度.