线性判别分析

线性判别分析（Linear Discriminant Analysis，LDA）亦称 Fisher 判别分析。其基本思想是：将训练样本投影到低维超平面上，使得同类的样例尽可能近，不同类的样例尽可能远。在对新样本进行分类时，将其投影到同样的超平面上，再根据投影点的位置来确定新样本的类别。

给定的数据集

D={(x1,y1),(x2,y2),⋯ ,(xN,yN)}D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),\cdots,(\mathbf x_N,y_N)\}

包含 NN 个样本，pp 个特征。其中，第 ii 个样本的特征向量为 xi=(xi1,xi2,⋯ ,xip)T\mathbf x_i=(x_{i1},x_{i2},\cdots,x_{ip})^T 。目标变量 yi∈{c1,c2,⋯ ,cK}y_i\in \{c_1,c_2,\cdots,c_K\} 。

二分类

我们先定义NkN_k为第 kk 类样本的个数

∑k=1KNk=N\sum_{k=1}^KN_k=N

Xk\mathcal X_k为第 kk 类样本的特征集合

Xk={x∣y=ck, (x,y)∈D}\mathcal X_k=\{\mathbf x | y=c_k,\ (\mathbf x,y)\in D \}

μk\mu_k为第 kk 类样本均值向量

μk=1Nk∑x∈Xkx\mu_k=\frac{1}{N_k}\sum_{\mathbf x\in \mathcal X_k}\mathbf x

Σk\Sigma_k为第 kk 类样本协方差矩阵

Σk=1Nk∑x∈Xk(x−μk)(x−μk)T\Sigma_k=\frac{1}{N_k}\sum_{\mathbf x\in \mathcal X_k}(\mathbf x-\mu_k)(\mathbf x-\mu_k)^T

首先从比较简单的二分类为例 y∈{0,1}y\in \{0,1\}，若将数据投影到直线 w\mathbf w 上，则对任意一点 x\mathbf x，它在直线 w\mathbf w 的投影为 wTx\mathbf w^T\mathbf x [1]。

  • LDA需要让不同类别的数据的类别中心之间的距离尽可能的大，也就是要最大化 ∥wTμ0−wTμ1∥22\|\mathbf w^T\mu_0 -\mathbf w^T\mu_1\|_2^2；
  • 同时希望同一种类别数据的投影点尽可能的接近，也就是要同类样本投影点的方差最小化 wTΣ0w+wTΣ1w\mathbf w^T\Sigma_0\mathbf w+\mathbf w^T\Sigma_1\mathbf w。

综上所述，我们的优化目标为：

max⁡w∥wTμ0−wTμ1∥22wTΣ0w+wTΣ1w\max_{\mathbf w}\frac{\|\mathbf w^T\mu_0 -\mathbf w^T\mu_1\|_2^2}{\mathbf w^T\Sigma_0\mathbf w+\mathbf w^T\Sigma_1\mathbf w}

目标函数

J(w)=∥wTμ0−wTμ1∥22wTΣ0w+wTΣ1w=wT(μ0−μ1)(μ0−μ1)TwTwT(Σ0+Σ1)w\begin{aligned} J(\mathbf w)&=\frac{\|\mathbf w^T\mu_0 -\mathbf w^T\mu_1\|_2^2}{\mathbf w^T\Sigma_0\mathbf w+\mathbf w^T\Sigma_1\mathbf w} \\ &=\frac{\mathbf w^T(\mu_0 -\mu_1)(\mu_0 -\mu_1)^T\mathbf w^T}{\mathbf w^T(\Sigma_0+\Sigma_1)\mathbf w } \end{aligned}

其中，SwS_w为类内散度矩阵（within-class scatter matrix）

Sw=Σ0+Σ1S_w=\Sigma_0+\Sigma_1

SbS_b为类间散度矩阵(between-class scaltter matrix)

Sb=(μ0−μ1)(μ0−μ1)TS_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T

目标函数重写为

J(w)=wTSbwwTSwwJ(\mathbf w)=\frac{\mathbf w^TS_b\mathbf w}{\mathbf w^TS_w\mathbf w}

上式就是广义瑞利商。要取得最大值，只需对目标函数求导并等于0，可得到等式

Sbw(wTSww)=Sww(wTSbw)S_b\mathbf w(\mathbf w^TS_w\mathbf w)=S_w\mathbf w(\mathbf w^TS_b\mathbf w)

重新代入目标函数可知

Sw−1Sbw=λwS_w^{-1}S_b\mathbf w=\lambda\mathbf w

这是一个特征值分解问题，我们目标函数的最大化就对应了矩阵 Sw−1SbS_w^{-1}S_b 的最大特征值，而投影方向就是这个特征值对应的特征向量。

多分类

可以将 LDA 推广到多分类任务中，目标变量 yi∈{c1,c2,⋯ ,cK}y_i\in \{c_1,c_2,\cdots,c_K\} 。

定义类内散度矩阵（within-class scatter matrix）

Sw=∑k=1KΣkS_w=\sum_{k=1}^K\Sigma_k

类间散度矩阵(between-class scaltter matrix)

Sb=∑k=1KNk(μk−μ)(μk−μ)TS_b=\sum_{k=1}^KN_k(\mu_k-\mu)(\mu_k-\mu)^T

其中 μ\mu 为所有样本均值向量

μ=1N∑i=1Nx\mu=\frac{1}{N}\sum_{i=1}^N\mathbf x

常见的最大化目标函数为

J(W)=tr(WTSbW)tr(WTSwW)J(W)=\frac{\text{tr}(W^TS_bW)}{\text{tr}(W^TS_wW)}

对目标函数求导并等于0，可得到等式

tr(WTSwW)SbW=tr(WTSbW)SwW\text{tr}(W^TS_wW)S_bW=\text{tr}(W^TS_bW)S_wW

重新代入目标函数可知

SbW=λSwWS_bW=\lambda S_wW

WW 的闭式解则是 Sw−1SbS_w^{-1}S_b 的 K一1K 一 1 个最大广义特征值所对应的特征向量组成的矩阵。

由于WW是一个利用了样本的类别得到的投影矩阵，则多分类 LDA 将样本投影到 K−1K-1 维空间，K−1K-1 通常远小子数据原有的特征数。于是，可通过这个投影来减小样本点的维数，且投影过程中使用了类别信息，因此 LDA也常被视为一种经典的监督降维技术。

二次判别分析

下面来介绍以概率的角度来实现线性判别分析的方法。我们的目的就是求在输入为 x\mathbf x 的情况下分类为 ckc_k 的概率最大的分类：

y^=arg⁡max⁡ckP(y=ck∣x)\hat y=\arg\max_{c_k} \mathbb P(y=c_k|\mathbf x)

利用贝叶斯定理，类别 ckc_k 的条件概率为

P(y=ck∣x)=P(x∣y=ck)P(y=ck)P(x)\mathbb P(y=c_k|\mathbf x)=\frac{\mathbb P(\mathbf x|y=c_k)\mathbb P(y=c_k)}{\mathbb P(\mathbf x)}

假设我们的每个类别服从高斯分布

P(x∣y=ck)=1(2π)pdet⁡Σkexp⁡(−12(x−μk)TΣk−1(x−μk))\mathbb P(\mathbf x|y=c_k)=\frac{1}{\sqrt{(2\pi)^p\det\Sigma_k}}\exp\left(-\frac{1}{2}(\mathbf x-\mathbf\mu_k)^T\Sigma^{-1}_k(\mathbf x-\mathbf\mu_k)\right)

其中，协方差矩阵Σk\Sigma_k 为对称阵。

决策边界：为方便计算，我们取对数条件概率进行比较。对任意两个类别csc_s和ctc_t，取

δ(x)=ln⁡P(y=cs∣x)−ln⁡P(y=ct∣x)\delta(\mathbf x)=\ln\mathbb P(y=c_s|\mathbf x)-\ln\mathbb P(y=c_t|\mathbf x)

输出比较结果

y^st={cs,if δ≤0ct,otherwise\hat y_{st}=\begin{cases} c_s, &\text{if }\delta\leq0 \\ c_t, &\text{otherwise} \end{cases}

决策边界为 δ(x)=0\delta(\mathbf x)=0，即

ln⁡P(y=cs∣x)=ln⁡P(y=ct∣x)\ln\mathbb P(y=c_s|\mathbf x)=\ln\mathbb P(y=c_t|\mathbf x)

我们先来化简下对数概率

ln⁡P(y=ck∣x)=ln⁡P(x∣y=ck)+ln⁡P(y=ck)−ln⁡P(x)=−12(x−μk)TΣk−1(x−μk)−12ln⁡(det⁡Σk−1)+ln⁡P(y=ck)+const=−12xTΣk−1x+μkTΣk−1x−12μkTΣk−1μk+ln⁡P(y=ck)−12ln⁡(det⁡Σk−1)+const=xTAkx+wkTx+bk+const\begin{aligned} \ln\mathbb P(y=c_k|\mathbf x)&=\ln\mathbb P(\mathbf x|y=c_k)+\ln\mathbb P(y=c_k)-\ln\mathbb P(\mathbf x) \\ &=-\frac{1}{2}(\mathbf x-\mathbf \mu_k)^T\Sigma^{-1}_k(\mathbf x-\mathbf \mu_k)-\frac{1}{2}\ln(\det\Sigma^{-1}_k) +\ln\mathbb P(y=c_k)+\text{const}\\ &=-\frac{1}{2}\mathbf x^T\Sigma^{-1}_k\mathbf x+\mathbf \mu_k^T\Sigma^{-1}_k\mathbf x-\frac{1}{2}\mu_k^T\Sigma^{-1}_k\mu_k+\ln\mathbb P(y=c_k)-\frac{1}{2}\ln(\det\Sigma^{-1}_k) +\text{const}\\ &=\mathbf x^TA_k\mathbf x+\mathbf w_k^T\mathbf x+b_k+\text{const} \end{aligned}

其中

Ak=−12Σk−1,wkT=μkTΣk−1,bk=−12μkTΣk−1μk+ln⁡P(y=ck)−12ln⁡(det⁡Σk−1)A_k=-\frac{1}{2}\Sigma^{-1}_k,\quad\mathbf w_k^T =\mu_k^T\Sigma^{-1}_k,\quad b_k =-\frac{1}{2}\mu_k^T\Sigma^{-1}_k\mu_k+\ln\mathbb P(y=c_k)-\frac{1}{2}\ln(\det\Sigma^{-1}_k)

可以看到，上式是一个关于 x\mathbf x 的二次函数

  • 当类别的协方差矩阵不同时，生成的决策边界也是二次型的，称为二次判别分析(Quadratic Discriminant Analysis, QDA)
  • 当类别的协方差矩阵相同时，决策边界将会消除二次项，变成关于 x\mathbf x 的线性函数，于是得到了线性判别分析。

实际应用中我们不知道高斯分布的参数，我们需要用我们的训练数据去估计它们。LDA使用估计协方差矩阵的加权平均值作为公共协方差矩阵，其中权重是类别中的样本量：

Σ^=∑k=1KNkΣkN\hat\Sigma=\frac{\sum_{k=1}^KN_k\Sigma_k}{N}

如果 LDA中的协方差矩阵是单位阵 Σ=I\Sigma=I并且先验概率相等，则LDA只需对比与类中心的欧几里得距离

ln⁡P(y=ck∣x)∝−12(x−μk)T(x−μk)=−12∥x−μk∥22\ln\mathbb P(y=c_k|\mathbf x)\propto -\frac{1}{2}(\mathbf x-\mathbf \mu_k)^T(\mathbf x-\mathbf \mu_k)=-\frac{1}{2}\|\mathbf x-\mathbf \mu_k\|_2^2

如果 LDA中的协方差矩阵非单位阵并且先验概率相等，则为马氏距离

ln⁡P(y=ck∣x)∝−12(x−μk)TΣk−1(x−μk)\ln\mathbb P(y=c_k|\mathbf x)\propto -\frac{1}{2}(\mathbf x-\mathbf \mu_k)^T\Sigma^{-1}_k(\mathbf x-\mathbf \mu_k)

  1. 超平面几何知识 ↩︎