費雪線性判別

在模式識別中，費雪線性判別（Fisher's linear discriminant）是一種線性判別方法，其意圖是在分類類別為c類時，將d維空間（樣品點是d維向量）中的數據點投影到c-1維空間上去，使得不同類的樣本點在這個空間上的投影儘量分離，同類的儘量緊湊。

## 兩類情況

在二類判別時，費雪線性判別將d維空間中的數據點投影到一條直線上去，使得不同類的樣本點在這條直線上的投影儘量分離，同類的樣本點在這條直線上儘量緊湊。假設有兩類樣本集$\mathcal{D}_1$的類別為ω1，樣本數為n1，$\mathcal{D}_2$的類別為ω2，樣本數為n2。定義樣本均值mi和類內散布Si。

$$\mathbf{m}_i=\frac{1}{n_i} \sum_{x\in \mathcal{D}_i} \mathbf{x},i=1,2$$

$$\mathbf{S}_i=\sum_{x\in \mathcal{D}_i} \left( \mathbf{x}-\mathbf{m}_i \right) \left(\mathbf{x}-\mathbf{m}_i \right)^t,i=1,2$$

投影直線的方向向量為w，樣本投影在直線上的值為y。則可得兩類樣本投影后的均值和類內散布為$\tilde{m}_i$和$\tilde{s}^2_i$，i=1,2。

$$y=\mathbf{w}^t\mathbf{x} \quad \tilde{m}_i=\mathbf{w}^t\mathbf{m}_i,i=1,2$$

$$\begin{align} <pre> \tilde{s}^2_i &=\sum_{y\in \mathcal{Y}_i} \left( y-\tilde{m}_i \right)^2\\ &=\sum_{x\in \mathcal{D}_i} \left( \mathbf{w}^t\mathbf{x}-\mathbf{w}^t\mathbf{m}_i \right)^2\\ &=\sum_{x\in \mathcal{D}_i} \mathbf{w}^t \left( \mathbf{x}-\mathbf{m}_i \right)\left( \mathbf{x}-\mathbf{m}_i \right)^t \mathbf{w}\\ &=\mathbf{w}^t \mathbf{S}_i \mathbf{w} </pre> \end{align}$$

要使不同類的樣本點的投影儘量分離，同類儘量緊湊，可以使兩類的投影的均值的差異儘量大，其方差的和儘量小，也就是要求$\frac{\left| \tilde{m}_1-\tilde{m}_2 \right|^2 }{\tilde{s}^2_1+\tilde{s}^2_2}$最大化。

$$\begin{align} <pre> \boldsymbol{J}(\mathbf{w}) &=\frac{\left| \tilde{m}_1-\tilde{m}_2 \right|^2 }{\tilde{s}^2_1+\tilde{s}^2_2} \\ &= \frac{ \left( \mathbf{w}^t\mathbf{m}_1-\mathbf{w}^t\mathbf{m}_2 \right)^2}{\mathbf{w}^t \mathbf{S}_1 \mathbf{w}+\mathbf{w}^t \mathbf{S}_2 \mathbf{w}} \\ &=\frac{\mathbf{w}^t \left( \mathbf{m}_1-\mathbf{m}_2 \right)\left( \mathbf{m}_1-\mathbf{m}_2 \right)^t \mathbf{w}} { \mathbf{w}^t \left( \mathbf{S}_1 + \mathbf{S}_2 \right) \mathbf{w} }\\ &=\frac{\mathbf{w}^t \mathbf{S_B} \mathbf{w}} {\mathbf{w}^t \mathbf{S_W} \mathbf{w}} \\ </pre> \end{align}$$

$$\mathbf{S_B}=\left( \mathbf{m}_1-\mathbf{m}_2 \right)\left( \mathbf{m}_1-\mathbf{m}_2 \right)^t, \mathbf{S_W}=\left( \mathbf{S}_1 + \mathbf{S}_2 \right)$$

可以證明當w滿足$\mathbf{S_B w}=\lambda \mathbf{S_W w}$，即w的方向與$\mathbf{S_W}^{-1} \left( \mathbf{m}_1-\mathbf{m}_2 \right)$相同時，J(w)取得最大值。剩下的問題就是如何求解閾值w0，也就是在這個一維空間中把兩類分開的那個點的位置。當J(w)超過w0就判決為某一類別ω，否則就判決為另一類別。然而目前並沒有一個通用的選取方法。

在兩個類別的分布是多元正態分布，且協方差矩陣相同時，根據貝葉斯決策理論，$\mathbf{w}=\mathbf{\Sigma}^{-1} \left( \mathbf{u}_1-\mathbf{u}_2 \right)$，並且w0是一個與w和先驗概率有關的常數。我們可以用樣本均值與樣本協方差去估計ui和Σ。更一般地說，如果我們對投影后的數據進行平滑，或用一維高斯函數進行擬合，ω0就位於使兩類的後驗概率相同的位置上。

## 多類情況

費雪線性判別在面對二類判別時，將兩類樣本向一條直線投影，也就是將數據從d維空間向1維空間投影。這樣在面對c個類的判別時，所要做就是將數據從d維空間向c-1維空間投影。這就需要推廣投影方程、類間散布矩陣SB和類內散布矩陣SW。從d維空間向c-1維空間的投影是通過c-1投影方程進行的：

$$y_i=\mathbf{w}^t_i \mathbf{x},\mathbf{x}\in \mathcal{D}_i \quad i=1,\ldots,c-1$$

這裡的$\mathcal{D}_i$為第i類的樣本集。設$\mathbf{y}=[y_1,y_2,\ldots,y_{c-1}]^t \quad \mathbf{W}=[w_1,w_2,\ldots,w_{c-1}]$，c-1個方程可以更簡練地表達：

$$\mathbf{y}=\mathbf{W}^t \mathbf{x},\mathbf{y}\in \mathcal{Y}_i \quad i=1,\ldots,c-1$$

這裡的$\mathcal{Y}_i$為第i類的樣本的投影向量集。類間散布矩陣SB和類內散布矩陣SW可以由總體散布矩陣ST和總體均值向量m推導得到：

$$\mathbf{m}=\frac{1}{n} \sum_{\mathbf{x}} \mathbf{x}=\frac{1}{n} \sum_{i=1}^c n_i\mathbf{m}_i \qquad \mathbf{S}_T=\sum_{\mathbf{x}}(\mathbf{x}-\mathbf{m})(\mathbf{x}-\mathbf{m})^t$$

$$\begin{align} \mathbf{S}_T & = \sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{x}-\mathbf{m}_i+\mathbf{m}_i-\mathbf{m})(\mathbf{x}-\mathbf{m}_i+\mathbf{m}_i-\mathbf{m})^t \\ & = \sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{x}-\mathbf{m}_i)(\mathbf{x}-\mathbf{m}_i)^t+\sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{m}_i-\mathbf{m})(\mathbf{m}_i-\mathbf{m})^T \\ \end{align}$$

由此定義類間散布矩陣SB和類內散布矩陣SW：

$$\mathbf{S}_W=\sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{x}-\mathbf{m}_i)(\mathbf{x}-\mathbf{m}_i)^t \quad \mathbf{S_B}=\sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{m}_i-\mathbf{m})(\mathbf{m}_i-\mathbf{m})^T$$

$$\mathbf{S}_T=\mathbf{S}_W+\mathbf{S_B}$$

那麼樣本數據的投影向量的類間散布矩陣$\widetilde{\mathbf{S}}_\mathbf{B}$和類內散布矩陣$\widetilde{\mathbf{S}}_\mathbf{W}$：即為：

$$\widetilde{\mathbf{S}}_\mathbf{B}=\sum_{i=1}^{c} \sum_{\mathbf{y} \in \mathcal{Y}_i}(\widetilde{\mathbf{m}}_i-\widetilde{\mathbf{m}})(\widetilde{\mathbf{m}}_i-\widetilde{\mathbf{m}})^T=\mathbf{W}^t \mathbf{S_B} \mathbf{W}$$

$$\widetilde{\mathbf{S}}_\mathbf{W}=\sum_{i=1}^{c} \sum_{\mathbf{y} \in \mathcal{Y}_i}(\mathbf{y}-\widetilde{\mathbf{m}}_i)(\mathbf{y}-\widetilde{\mathbf{m}}_i)^t=\mathbf{W}^t \mathbf{S_W} \mathbf{W}$$

與兩類情況類似，要找到某一W使得類內散布儘量小，類間散布儘量大。但這裡的類內散布和類間散布不再是一個值，而是一個矩陣。矩陣的行列式是矩陣的特徵值的乘積，也就是數據在各個主要方向的方差的積，相當於類別散布超橢球體的體積的平方。故使用行列式來度量散布，這樣判別函數即為$\boldsymbol{J}(\mathbf{w})=\frac{|\widetilde{\mathbf{S}}_\mathbf{B}|}{|\widetilde{\mathbf{S}}_\mathbf{W}|}=\frac{|\mathbf{W}^t \mathbf{S_B} \mathbf{W}|}{|\mathbf{W}^t \mathbf{S_W} \mathbf{W}|}$

可以證明，當W的列向量wi是$\mathbf{S_B}\mathbf{w}_i=\mathbf{\lambda}_i \mathbf{S_W}\mathbf{w}_i$的廣義特徵向量時，可以使得J(w)最大。因為SB中c個秩為1或0的矩陣相加，而且其中只有c-1個矩陣是相互獨立的。所以SB的秩最多為c-1。所以最多只有c-1個特徵向量是非零的。

## 應用

### 人臉識別

在人臉識別中，每一個人臉圖像具有大量的像素點。LDA主要用來將特徵減少到一個可以處理的數目在進行分類。每一個新的維度都是原先像素值的線性組合，這就構成了一個模板。這樣獲得的線性組合被稱為Fisher faces,而通過主成分分析獲得的則稱為特徵臉。