本小节为线性分类的第三小节，主要推导了线性判别分析算法，也就是Fisher算法。Fisher算法的主要思想是：{ 类内小，类间大。}这有点类似于，软件过程里的松耦合，高内聚的思想。这个思想转换成数学语言也就是，同一类数据之间的方差要小，不同类数据之间的均值的差距要大。那么，我们对数据的描述如下所示：

$\begin{equation} X=(x_1, x_2, \cdots, x_N)^T= \begin{pmatrix} x_1^T \\ x_2^T \\ \vdots\\ x_N^T \\ \end{pmatrix} = \begin{pmatrix} x_{11} & x_{12} & \dots & x_{1p}\\ x_{21} & x_{32} & \dots & x_{2p}\\ \vdots & \vdots & \ddots & \vdots\\ x_{N1} & x_{N2} & \dots & x_{Np}\\ \end{pmatrix}_{N\times P} \end{equation}$

$\begin{equation} Y= \begin{pmatrix} y_1 \\ y_2 \\ \vdots\\ y_N \\ \end{pmatrix}_{N\times 1} \end{equation}$

那么，我们的数据集可以记为$\left{ (x_i,y_i) \right}{i=1}^N $，其中，$ x_i \in \mathbb{R}^p $，$ y_i\in{+1,-1} $，且$ {y=+1} $为$ C_1 $类，且$ {y=-1} $为$ C_2 $类。那么，$ X{c_1}

$被定义为$ \left{ x_i

y_i=+1 \right}

$，$ X_{c_2}

$被定义为$ \left{ x_i

y_i=-1 \right}

$。所以，很显然可以得到$

X_{c_1}

=N_1

$，$

X_{c_2}

=N_2

$，并且$ N_1+N_2=N$。

Fisher线性判别分析}

$\begin{figure}[H] \centering \includegraphics[width=.55\textwidth]{微信图片_20191031095624.png} \caption{Fisher线性判别分析模型图} \label{fig:my_label_1} \end{figure}$

在左图中，我们设置了两个投影方向，很显然上面那个投影方向可以更好的将两个点之间分开。我们可以在投影方向上找一个点作为两个类别的分界点，也就是阈值(Threshhold)。首先，我们先引入一个有关投影算法的小知识。

投影算法}

首先，我们需要设定一个投影向量 $w$ ，为了保险起见，对这个投影向量 $w$ 作出约束，令 $||w||=1$ 。那么，在空间中的一个数据点，也就是一个向量，在投影向量上的投影长度可以表述为：

$\begin{equation} x_i\cdot w = |x_i||w|\cos{\theta}=|x_i|\cos{\theta}=\triangle \end{equation}$

Fisher判别分析的损失函数表达式}

在这个部分，主要是要得出Fisher判别分析的损失函数表达式求法。对于，投影的平均值和方差，我们可以分别表述为:

$\begin{gather} \Bar{z}=\frac{1}{N}\sum_{i=1}^{N}z_i = \frac{1}{N}\sum_{i=1}^{N}w^Tx_i \\ S_z=\frac{1}{N}\sum_{i=1}^N(z_i-\Bar{z})(z_i-\Bar{z})^T \end{gather}$

那么对于第一类分类点 $X_{c_1}$ 和第二类分类点 $X_{c_2}$ 可以表述为：

$\begin{equation} C_1:\qquad \Bar{z_1}= \frac{1}{N_1}\sum_{i=1}^{N_1}w^Tx_i \qquad S_1 =\frac{1}{N_1}\sum_{i=1}^N(z_i-\Bar{z_1})(z_i-\Bar{z_1})^T \end{equation}$

$\begin{equation} C_2:\qquad \Bar{z_2}= \frac{1}{N_2}\sum_{i=1}^{N_2}w^Tx_i \qquad S_2 =\frac{1}{N_2}\sum_{i=1}^N(z_i-\Bar{z_2})(z_i-\Bar{z_2})^T \end{equation}$

那么类间的距离我们可以定义为： $(\Bar{z_1}-\Bar{z_2})^2$ , 类内的距离被我们定义为 $S_1+S_2$ 。那么我们的目标函数Target Function $\mathcal{J}(w)$ ，可以被定义为:

$\begin{equation} \mathcal{J}(w) = \frac{(\Bar{z_1}-\Bar{z_2})^2}{S_1+S_2} \end{equation}$

因为，我们的目的是使方差越小越好，均值之间的差越大越好。

损失函数表达式的化简}

$(\Bar{z_1}-\Bar{z_2})^2$ }

分子的化简过程如下所示：

$\begin{equation} \begin{split} (\Bar{z_1}-\Bar{z_2})^2 = & \left( \frac{1}{N_1}\sum_{i=1}^{N_1}w^Tx_i - \frac{1}{N_2}\sum_{i=1}^{N_2}w^Tx_i \right)^2 \\ = & \left( w^T(\frac{1}{N_1}\sum_{i=1}^{N_1}x_i - \frac{1}{N_2}\sum_{i=1}^{N_2}x_i ) \right)^2 \\ = & \left( w^T(\Bar{X}_{c_1} - \Bar{X}_{c_2}) \right)^2 \\ = & w^T(\Bar{X}_{c_1} - \Bar{X}_{c_2})(\Bar{X}_{c_1} - \Bar{X}_{c_2})^Tw \\ \end{split} \end{equation}$

$S_1+S_2$ }

分母的化简过程如下所示：

$\begin{equation} \begin{split} S_1 = & \frac{1}{N_1}\sum_{i=1}^N(z_i-\Bar{z}_1)(z_i-\Bar{z}_1)^T \\ = & \frac{1}{N_1}\sum_{i=1}^N(w^Tx_i-\frac{1}{N_1}\sum_{i=1}^{N_1}w^Tx_i)(w^Tx_i-\frac{1}{N_1}\sum_{i=1}^{N_1}w^Tx_i)^T \\ = & w^T\frac{1}{N_1}\sum_{i=1}^N(x_i-\frac{1}{N_1}\sum_{i=1}^{N_1}x_i)(x_i-\frac{1}{N_1}\sum_{i=1}^{N_1}x_i)^Tw \\ = & w^TS_{c_1}w \\ \end{split} \end{equation}$

同理可得，

$\begin{equation} S_1 = w^TS_{c_2}w \end{equation}$

所以，

$\begin{equation} S_1+S_2=w^T(S_{c_1}+S_{c_2})w \end{equation}$

$\mathcal{J}(w)$ 的最简表达形式}

$\begin{equation} \mathcal{J}(w)=\frac{w^T(\Bar{X}_{c_1} - \Bar{X}_{c_2})(\Bar{X}_{c_1} - \Bar{X}_{c_2})^Tw}{w^T(S_{c_1}+S_{c_2})w} \end{equation}$

令 $S_b$ 为between-class类间方差， $S_w$ 为within-class，也就是类内方差。那么有

$\begin{equation} S_b = (\Bar{X}_{c_1} - \Bar{X}_{c_2})(\Bar{X}_{c_1} - \Bar{X}_{c_2})^T \qquad S_w = (S_{c_1}+S_{c_2}) \end{equation}$

于是，我们可以得到进一步化简的表达式；

$\begin{equation} \mathcal{J}(w)=\frac{w^TS_bw}{w^TS_ww} \end{equation}$

损失函数 $\mathcal{J}(w)$ 的梯度}

为了方便求导，我们令 $\mathcal{J}(w)=(w^TS_bw)(w^TS_ww)^{-1}$ 。

$\begin{equation} \begin{split} \frac{\partial \mathcal{J}(w)}{\partial w} = 2S_bw(w^TS_ww)^{-1} + & (-1)(w^TS_bw)(w^TS_ww)^{-2}(2)S_ww = 0 \\ S_bw(w^TS_ww)^{-1} = & (w^TS_bw)(w^TS_ww)^{-2}S_ww\\ \end{split} \end{equation}$

显然， $w$ 的维度是 $p\times 1$ ， $w^T$ 的维度是 $1 \times p$ ， $S_w$ 的维度是 $p\times p$ ，所以， $w^TS_ww$ 是一个实数，同理可得， $w^TS_ww$ 是一个实数所以，可以得到

$\begin{equation} \begin{split} S_bw = & (w^TS_bw)(w^TS_ww)^{-1}S_ww \\ S_bw = & \frac{(w^TS_bw)}{(w^TS_ww)}S_ww \end{split} \end{equation}$

我们主要是求得梯度的方向，大小不是很重要了。所以，我们可得

$\begin{equation} w = \frac{(w^TS_bw)}{(w^TS_ww)}S_b^{-1}S_ww \propto S_b^{-1}S_ww \end{equation}$

$\begin{equation} S_ww = (\Bar{X}_{c_1} - \Bar{X}_{c_2})(\Bar{X}_{c_1} - \Bar{X}_{c_2})^Tw \end{equation}$

而$(\Bar{X}{c_1} - \Bar{X}{c_2})^Tw$是一个实数，所以汇总可得

$\begin{equation} S_b^{-1}S_ww \propto S_w^{-1}(\Bar{X}_{c_1} - \Bar{X}_{c_2}) \end{equation}$

那么，我们就可以求得梯度的方向为$S_w^{-1}(\Bar{X}{c_1} - \Bar{X}{c_2}) $。如果，$ S_w^{-1} $是一个各向同性的对角矩阵，那么$ S^{-1}\propto I $。所以，$ w\propto (\Bar{X}{c_1} - \Bar{X}{c_2})$。既然，求得了梯度的方向，其实梯度的大小就不重要的。

Linear_Classification_03

2022年10月

Fisher线性判别分析}

投影算法}

Fisher判别分析的损失函数表达式}

损失函数表达式的化简}

$(\Bar{z_1}-\Bar{z_2})^2$ }

$S_1+S_2$ }

$\mathcal{J}(w)$ 的最简表达形式}

损失函数 $\mathcal{J}(w)$ 的梯度}

CATALOG

FEATURED TAGS

FRIENDS

Fisher线性判别分析}

投影算法}

Fisher判别分析的损失函数表达式}

损失函数表达式的化简}

(\Barz1−\Barz2)2(\Bar{z_1}-\Bar{z_2})^2}

S1+S2S_1+S_2}

J(w)\mathcal{J}(w)的最简表达形式}

损失函数J(w)\mathcal{J}(w)的梯度}

CATALOG

FEATURED TAGS

FRIENDS

$(\Bar{z_1}-\Bar{z_2})^2$ }

$S_1+S_2$ }

$\mathcal{J}(w)$ 的最简表达形式}

损失函数 $\mathcal{J}(w)$ 的梯度}