3.4 Fisher线性判别

3.4.1 概述

出发点

• 应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题

• 在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通

• 因此，降低维数有时就会成为处理实际问题的关键

问题描述

• 考虑把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维

• 然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别

• 但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开

Fisher判别方法所要解决的基本问题，就是如何根据实际情况找到一条最好的、最易于分类的投影线

3.4.2 降维的数学原理

从d维空间降到一维空间的一般数学变换方法：

• 设有一集合$\Gamma$包含N个d维样本$x_1,x_2,\dots,x_N$，其中$N_1$个属于$\omega_1$类的样本记为子集$\Gamma_1$，$N_2$个属于$\omega_2$类的样本记为子集$\Gamma_2$，若对$x_n$的分量做线性组合可得标量：

$$y_n = \boldsymbol{w}^T\boldsymbol{x}_n,\ \ n=1,2,\dots,N$$

• 这样可以得到N个一维样本$y_n$组成的集合，且可以分为两个子集$\Gamma_1,\Gamma_2$
• 这里关心的是$\boldsymbol{w}$的方向，即样本投影的方向，而具体的值并不重要，只是一个比例因子
• 所以，抽象到数学层面，本质就是寻找最好的变换向量$\boldsymbol{w}^*$

3.4.3 Fisher准则

一、Fisher准则中的基本参量

在高维空间X中：

• 各样本的均值向量$\boldsymbol{m}_i$

$$\boldsymbol{m}_i = \frac{1}{N_i}\sum_{x\in \Gamma_i}x,\ \ i=1,2$$

• 样本类内离散度矩阵$S_i$和总样本类内离散度矩阵$S_w$

$$\begin{align} S_i &= \sum_{x\in\Gamma_i}(x-\boldsymbol{m}_i)(x-\boldsymbol{m}_i)^T,\ \ i=1,2 \nonumber \\ S_w &= S_1 + S_2 \nonumber \end{align}$$

• 样本类间离散度矩阵$S_b$，$S_b$是一个对称半正定矩阵

$$S_b = (\boldsymbol{m}_1-\boldsymbol{m}_2)(\boldsymbol{m}_1-\boldsymbol{m}_2)^T$$

在一维空间Y中：

• 各类样本的均值$\widetilde{m}_i$

$$\widetilde{m}_i = \frac{1}{N_i}\sum_{y \in \Gamma_i}y,\ \ i=1,2$$

• 样本类内离散度$\widetilde{S}_i^2$和总样本类内离散度$\widetilde{S}_w$

$$\begin{align} \widetilde{S}_i^2 &= \sum_{y\in \Gamma_i}(y-\widetilde{m}_i)^2,\ \ i=1,2\nonumber \\ \widetilde{S}_w &= \widetilde{S}_1^2 + \widetilde{S}_2^2 \end{align}$$

我们希望投影后，在一维Y空间中各类样本尽可能分得开些，同时各类样本内部尽量密集，实际上就是

• 两类之间的均值相差越大越好

• 类内的离散度越小越好

3.4.3 Fisher准则函数的定义

Fisher准则函数定义为：

$$J_F(\boldsymbol{w}) = \frac{(\widetilde{m}_1 - \widetilde{m}_2)^2}{\widetilde{S}_1^2 + \widetilde{S}_2^2}$$

而其中，样本均值可以写为：

$$\begin{align} \widetilde{m}_i &= \frac{1}{N_i}\sum_{y \in \Gamma_i}y \nonumber \\ &= \frac{1}{N_i}\sum_{x\in\Gamma_i}\boldsymbol{w}^Tx \nonumber \\ &= \boldsymbol{w}^T\left(\frac{1}{N_i}\sum_{x\in\Gamma_i}x\right) \nonumber \\ &= \boldsymbol{w}^T\boldsymbol{m}_i \nonumber \end{align}$$

则准则函数的分子可以写为：

$$\begin{align} (\widetilde{m}_1 - \widetilde{m}_2)^2 &= (\boldsymbol{w}^T\boldsymbol{m}_1 - \boldsymbol{w}^T\boldsymbol{m}_2)^2 \nonumber \\ &=(\boldsymbol{w}^T\boldsymbol{m}_1 - \boldsymbol{w}^T\boldsymbol{m}_2)(\boldsymbol{w}^T\boldsymbol{m}_1 - \boldsymbol{w}^T\boldsymbol{m}_2)^T \nonumber \\ &= (\boldsymbol{w}^T\boldsymbol{m}_1 - \boldsymbol{w}^T\boldsymbol{m}_2)(\boldsymbol{m}_1^T\boldsymbol{w} - \boldsymbol{m}_2^T\boldsymbol{w}) \nonumber \\ &=\boldsymbol{w}^T(\boldsymbol{m}_1-\boldsymbol{m}_2)(\boldsymbol{m}_1-\boldsymbol{m}_2)^T\boldsymbol{w} \nonumber \\ &=\boldsymbol{w}^TS_b\boldsymbol{w} \end{align}$$

而由于

$$\begin{align} \widetilde{S}_i^2 &= \sum_{y\in \Gamma_i}(y-\widetilde{m}_i)^2 \nonumber \\ &= \sum_{x\in\Gamma_i}(\boldsymbol{w}^Tx-\boldsymbol{w}^T\boldsymbol{m}_i)^2 \nonumber \\ &= \boldsymbol{w}^T\left[\sum_{x\in\Gamma_i}(x-\boldsymbol{m}_i)(x-\boldsymbol{m}_i)^T\right]\boldsymbol{w} \nonumber \\ &= \boldsymbol{w}^TS_i\boldsymbol{w} \nonumber \end{align}$$

因此分母可以写成：

$$\begin{align} \widetilde{S}_1^2 + \widetilde{S}_2^2 &= \boldsymbol{w}^T(S_1 + S_2)\boldsymbol{w} \nonumber \\ &= \boldsymbol{w}^TS_w\boldsymbol{w} \end{align}$$

将上述各式带回$J_F(\boldsymbol{w})$，可得：

$$J_F(\boldsymbol{w}) = \frac{\boldsymbol{w}^TS_b\boldsymbol{w}}{\boldsymbol{w}^TS_w\boldsymbol{w}}$$

3.4.4 最佳变换向量求解

由于需要使得均值之差（即分子）尽可能大，同时使得样本内离散度（即分母）尽可能小，故实际上就是要使得准则函数尽可能的大

要求使得准则函数取极大值时的$\boldsymbol{w}^*$，可以采用拉格朗日乘数法求解：

拉格朗日乘数法

基本思想是将等式约束条件下的最优化问题转化为无约束条件下的最优化问题

问题： 设目标函数为

$$y = f(x),\ x=(x_1,x_2,\dots,x_n)$$

求其在$m\ (m<n)$个约束条件

$$g_k(x) = 0,\ k=1,2,\dots,m$$

下的极值

描述： 引进函数

$$L(x,\lambda_1,\lambda_2,\dots,\lambda_m) = f(x) + \sum_{k=1}^{m}\lambda_kg_k(x)$$

其中$\lambda_k,\ k=1,2,\dots,m$为待定常数，将$L$当作$m+n$个变量$x_1,x_2,\dots,x_n$和$\lambda_1,\lambda_2,\dots,\lambda_m$的无约束的函数，对其求一阶偏导数可得稳定点所需要的方程：

$$\frac{\partial L}{\partial x_i} = 0,\ i=1,2,\dots,n \\ g_k = 0,\ k=1,2,\dots,m$$

令分母等于非零常数，即：

$$\boldsymbol{w}^TS_w\boldsymbol{w}=c\neq0$$

则定义拉格朗日函数为：

$$L(\boldsymbol{w},\lambda) = \boldsymbol{w}^TS_b\boldsymbol{w}-\lambda(\boldsymbol{w}^TS_w\boldsymbol{w}-c)$$

对$\boldsymbol{w}^*$求偏导，可得：

$$\frac{\partial L(\boldsymbol{w},\lambda)}{\partial \boldsymbol{w}}= 2(S_b\boldsymbol{w}-\lambda S_w\boldsymbol{w})$$

令偏导数为0，有：

$$\begin{align} & S_b \boldsymbol{w}^*-\lambda S_w\boldsymbol{w}^*=0 \nonumber \\ & S_b\boldsymbol{w}^*=\lambda S_w \boldsymbol{w}^* \nonumber \end{align}$$

由于$S_w$非奇异，因此存在逆矩阵，可得：

$$S_w^{-1}S_b\boldsymbol{w}^* = \lambda \boldsymbol{w}^*$$

此时本质即为求矩阵$S_w^{-1}S_b$的特征值问题，将$S_b=(\boldsymbol{m}_1-\boldsymbol{m}_2)(\boldsymbol{m}_1-\boldsymbol{m}_2)^T$代入上式，可将$S_b\boldsymbol{w}^*$写为：

$$\begin{align} S_b\boldsymbol{w}^* &= (\boldsymbol{m}_1-\boldsymbol{m}_2)(\boldsymbol{m}_1-\boldsymbol{m}_2)^T\boldsymbol{w}^* \nonumber\\ &=(\boldsymbol{m}_1-\boldsymbol{m}_2)R \end{align}$$

其中$R=(\boldsymbol{m}_1-\boldsymbol{m}_2)^T\boldsymbol{w}^*$为一标量，因此$S_b\boldsymbol{w}^*$总是在向量$(\boldsymbol{m}_1-\boldsymbol{m}_2)$的方向上，故$\lambda \boldsymbol{w}^*$可以写成：

$$\begin{align} \lambda \boldsymbol{w}^* &= S_w^{-1}(S_b\boldsymbol{w}^*) \nonumber \\ &= S_w^{-1}(\boldsymbol{m}_1-\boldsymbol{m}_2)R \nonumber \end{align}$$

从而有：

$$\boldsymbol{w}^* = \frac{R}{\lambda}S_w^{-1}(\boldsymbol{m}_1-\boldsymbol{m}_2)$$

由于只需要找最佳投影方向，因此可以忽略比例因子，有：

$$\boldsymbol{w}^* = S_w^{-1}(\boldsymbol{m}_1-\boldsymbol{m}_2)$$

其中，$S_w^{-1}$为高维空间中的总样本类内离散度矩阵的逆矩阵，$\boldsymbol{m}_i$为高维空间中各样本的均值向量

3.4.5 基于最佳变换向量$\boldsymbol{m}^*$的投影

$\boldsymbol{w}^*$是使Fisher准则函数$J_F(\boldsymbol{w})$取极大值时的解，也就是d维X空间到一维Y空间的最佳投影方向。有了$\boldsymbol{w}^*$，就可以把d维样本X投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向$\boldsymbol{w}^*$相对于Fisher准则函数$J_F(\boldsymbol{w})$是最好的。

利用Fisher准则，就可以将d维分类问题转化为一维分类问题，然后，只要确定一个阈值T，将投影点$y_n$与T相比较，即可进行分类判别。