? 本文在我的上一篇博文 機器學習-特征選擇(降維) 線性判別式分析(LDA) ?的基礎上進一步介紹核Fisher LDA算法。

? 之前我們介紹的LDA或者Fisher LDA都是線性模型，該模型簡單，對噪音的魯棒性較好，不容易過擬合，但是，簡單模型的表達能力會弱一些，為了增加LDA算法的表達能力，我們可以將數據投影到非線性的方向上去。為了達到這個目的，我們可以先將數據非線性的投影到一個特征空間F內，然后在這個F空間內計算Fisher 線性判別式,達到降維的目的。

? 首先介紹一下核函數的概念：

? 如果F空間的維數非常高甚至是無窮維數，那么單純的只是將原數據投影到F空間就是一個很大的計算量。但是，我們可以并不顯式的進行數據的投影，而只是計算原數據的點乘：(Φ?(x)·Φ?(y)).如果我們可以快速高效的計算出點乘來，那么我們可以無須將原數據投影到F空間就解決問題(關于這一點，Andrew Ng的講義中舉過一些例子，詳見附錄1)。我們使用Mercer核：k(x,y)=(Φ?(x)·Φ?(y))，可以選擇高斯徑向基函數核(Gaussian RBF)：k(x,y)=exp(-|x-y| ² /c)，或者多項式核：k(x,y)=(x·y) ^d ，或者S形核：tanh(kx·y-δ),其中c,d和δ都是正的常數。

? 我們用Φ表示一個投影到F特征空間的映射函數，為了得到F空間內的Fisher線性判別式，我們需要最大化：?

? ?? ? ? 式子-1

? 其中ω ∈F空間，而S _B ^Φ 和S _W ^Φ 分別為：

??

? 我們需要將式子-1轉換成一個只含有點乘的形式，這樣的話我們就可以只使用核函數來表達式子-1了。

? 我們知道，任意F空間內的解ω都可以由投影到F空間內的原數據組合得到：

? ?? ? 式子-2

? 根據式子-2，以及m _i ^Φ 的定義，我們能夠得到：

? ?? ? ? 式子-3

? 其中：

? 根據式子-3和S _B ^Φ 的定義，式子-1中的分子可以寫為：

?? ? ? 式子-4

? 其中 .

? 根據式子-2和m _i ^Φ 的定義，式子-1中的分母可以寫為：

?? ? ? 式子-5

? 其中 ,K _j 是一個l*l _j 的矩陣： ,I是單位矩陣，l _lj 是所有項都是1/l _j 的矩陣。

? 由式子-4和式子-5可以得到，我們只需要最大化

?? ? 式子-6?

? 與Fisher LDA一樣，最大化式子-6的解為N ^-1 M矩陣的最大的特征值對應的特征向量。

? 原數據在ω的投影為：

??

? 附錄1 . Andrew Ng關于核函數可能比先將數據投影到F空間，然后再點乘計算復雜度更小的例子：

? 我們考慮核函數K(x,z)=(x ^T z) ²

? 其中x和z都是N維向量，如果直接計算上式(核函數)，則計算復雜度為O(N)，亦即和數據的維數是線性的關系。

? 接下來看一下首先將數據投影到新空間，然后計算K(x,z)的過程和計算復雜度，首先重新表達K(x,z)：

??

? 然后 將數據x和z利用Φ(·)投影到新空間，亦即：

??

? 最后計算K(x,z)= ??Φ(x)*Φ(z)。我們可以看到，計算Φ(·)的復雜度為O(N ² ).

? 所以，在有些情況下，K(x,z)本身可能比較容易計算，而Φ(·)的計算量反而可能會更大。

? 參考文獻 ：

?? [1]? Fisher Discriminant Analysis with Kernals . Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhadr Scholkopf, Klaus-Robert Muller.

? [2]? Fisher Linear Discriminant Analysis . Max Welling.

? [3] CS229 Lecture notes, Part 5, Support Vector Machine . Andrew Ng.

??

機器學習-核Fisher LDA算法