Fisher线性判别推导

这篇文章中，我将主要以三种方式对$Fisher$判别的结果与最优解以及对应取值进行详细的推导。需要一定的多元函数微分、线性代数基础或凸优化基础。我将以不同知识背景对原问题进行解释与推导，得出正确结果。

问题重述

我们的优化目标函数为：
$$
\max J(w) = \frac{w^TS_bw}{w^TS_ww}
$$

其中 $S_b$ 描述了类间关系，$S_w$ 描述的是类内关系。我们希望让类间间距尽可能远，类内关系尽可能紧密，因此我们希望 $w^TS_bw$ 尽可能大，$w^TS_ww$ 尽可能小。因此最终的优化函数按上图所示。

1. 拉格朗日乘子法

网上大部分方式都是这种证明方法，在这里做出解释并提出疑问。

我们设 $w^TS_w{w} = c$，则原问题变成了：
$$
\max \quad J(w) = w^TS_bw, \quad s.t: w^TS_ww = c
$$
运用拉格朗日乘子法：
$$
L(w, \lambda) = w^TS_bw - \lambda (w^TS_ww - c)
$$
求极值偏导为0：
$$
\frac{\partial L(w,\lambda)}{\partial w}=2S_bw-2\lambda S_ww=0
$$
则：
$$
S_b w = \lambda S_w w\to (S_w^{-1}S_b)w=\lambda w
$$
从而：
$$
\lambda w=S_w^{-1}S_b w=S_w^{-1}(m_1-m_2)(m_1-m_2)^Tw=S_w^{-1}(m_1-m_2)R
$$
所以当取到最优值时：
$$
{w}^*=\frac R\lambda S_w^{-1}(m_1-m_2)
$$
$w$ 的方向与 $S_w^{-1}(m_1-m_2)$ 是一致的。

但我也有部分疑惑：

1. $w^TS_ww = c$ 前提的设置是否有严谨的数学依据，能够保证最后得到的是最优解。
2. $(S_w^{-1}S_b)w=\lambda w$ 只能告诉我们 $w$ 是一个特征向量。但为什么求解后的 $w$ 是唯一的？根据这个式子得出的 $w$ 应该是任意特征向量都成立，但事实只有一个是解。

2. 直接求导法

事实上对于求极值问题，我们第一想法应该就是求导然后求极值。这个方法便按照这个思路直接进行求解。
$$
\frac{\partial J}{\partial w} = \frac{S_bw * (w^TS_ww) - (w^TS_bw) * S_ww}{(w^TS_ww)^2}=0
$$
我们设 $w^TS_bw = R_1, w^TS_ww=R_2$ ，其中 $R_1, R_2$ 为实数。则当取到极值的时候：
$$
S_bw*R_2 = R_1 * S_ww
$$

$$
\frac{R_1}{R_2}w=(S_w^{-1}S_b)w
$$

我们注意到$J = R_1 / R_2$
$$
(S_w^{-1}S_b)w=J(w)*w
$$
通过线性代数的知识，我们可以得到：

1. $J$ 应该是 $S_w^{-1}S_b$ 的一个特征值。
2. 此时 $w$ 应该是对应特征值的特征向量。

因为我们的目标是：
$$
\max J(w)
$$
因此我们不难得出：
$$
\max \quad J(w) = \max{\lambda_1, \lambda_2, \dots,\lambda_k}
$$

$$
w = v_{argmax{\lambda_1, \lambda_2, \dots,\lambda_k}}
$$

所以我们得出结论：

1. 目标函数 $\max J$ 是 $S_w^{-1}S_b$ 的最大特征值。
2. 取最优值时 $w$ 应该是对应最大特征值的特征向量。

$w$ 的方向可以按照第一种方法进行求解。直接求导法很好地解答了 为什么结果 $w$ 的方向一定是唯一的，因为——最优结果就是最大特征值。

3. 从$w^TSw$含义入手验证上述结果

让我们首先来看下 $w^TSw$ 的性质（回顾线性代数相关知识）：
$$
w^TSw = w^T(Sw) = a \in R
$$
所以我们不妨设：
$$
w^TSw = w^T(Sw) = w^T \mu w = \mu w^Tw=\mu k, \quad u \in R,v \in R
$$
所以 $w^TSw$ 实际上就是对 $k = ||w||_2^2=w^Tw$ 的一种缩放。其中 $\mu$ 为 $S$ 一特征值 （$\mu = \frac{w^TSw}{w^Tw}$）。

接下来让我们回到原问题，其可以转化为：
$$
\max J = \frac{w^TS_bw}{w^TS_ww} = \frac{\mu_b k}{\mu_w k} = \frac{\mu_b}{\mu_w}
$$
即目标函数转化为两矩阵 $S_b, S_w$ 特征值比值的最大值。

在方法2中，我们得到的结果是 $S_w^{-1}S_b$ 的最大特征值。而：
$$
\max \lambda = \max (\lambda_w^{-1} \lambda_b) = \max \frac{\lambda_b}{\lambda_w} = \frac{\mu_b}{\mu_w}
$$
因此我们进一步验证了方法2的结果是正确的——答案是 $S_w^{-1}S_b$ 的最大特征值。

4. 抛砖引玉：对偶法

首先给出参考连接：非线性规划：拉格朗日对偶 - 知乎 (zhihu.com)。鸣谢 $zdc$ 的帮助。

首先介绍拉格朗日对偶。设原问题为：

$$
(L)\min_x \quad f_0(x)
$$

$$
s.t.\quad f_i(x)\leq0,i=1,2,\ldots,m;\quad h_j(x)=0,j=1,2,\ldots,p
$$

从而构造拉格朗日函数：
$$
L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{i=1}^p\nu_ih_i(x),
$$
其对偶形式（$inf$ 符号表示取下确界。）：
$$
\max g(\lambda,\nu)=\inf_{x}L(x,\lambda,\nu)
\ s.t:\lambda \geq 0
$$
我们的为似乎也可以转化成对偶再求解。还要验证原问题与对偶问题的最优解是否相同。目前我还没有完整的思路，在这里给大家抛砖引玉吧。