局部敏感判別分析

論文《Locality Sensitive Discriminant Analysis 》

論文地址：http://www.ijcai.org/Proceedings/07/Papers/113.pdf

這篇論文發表於07年，算是比較早的一篇論文，之所以拿這篇論文來講，主要原因是這篇文章的idea極其簡單，數學公式的推導極富美感，最後實驗效果也不錯。個人最近想基於這篇論文做一些工作，所以在這裡對其做一個簡單的介紹與回顧。

首先說說這篇論文的作者蔡登，蔡登現在是浙江大學的教授，博士學位在美國的伊利諾伊香檳獲得，這篇論文應該是其讀博士期間發表的。下面是計算機科學Top Scientists H-index排名（中國），排名前十都是國內非常知名的計算機大牛，蔡登排名第7位，其影響力可見一斑。

演算法主要思想

局部敏感判別分析演算法（LSDA）屬於流行學習演算法，其主要思想是通過最大化每個局部區域中不同類的邊緣，即使高維數據近鄰中的同類樣本投影到低維空間中更近，同時使不同類的樣本彼此遠離，從而使高維數據在低緯空間中具有更強的可分性。如下圖所示：(a)圖代表原始空間中的樣本分布，不同顏色代表不同的類別，(b)中紅色代表類樣本，作者以此構造了一個類內圖（within-class graph），(c)代表不同類樣本，同樣的，作者構造了一個類間圖(between-class graph),(d)代表嵌入到低維流行空間之後的樣本，可以發現，同類樣本在低維空間中更近，不同類樣本彼此遠離。

具體地，上面說到的類間圖和類內圖可以由下面的式子表示：

為了達到低維空間中同類樣本更近，不同類的樣本更遠的目的，作者構造了下面的兩個目標函數：

其中的min針對的是同類樣本，max針對的是不同類樣本，現在的問題是怎麼同時優化兩個目標函數，作者首先將兩個目標函數展開，有：

可以加一個約束項

這個時候最小化(min)的目標函數便可以轉換成：

這個目標函數等價於：

這個時候便可以將這一項與最大化(max)的目標函數整合，於是有：

這個目標函數可以轉變成求解特徵值問題，很容易得到最終的解：

實驗結果

作者在兩組人臉識別數據集上面做了實驗，都取得了最好的結果：

具體的實驗設置可以參見論文，作者在自己的個人主頁上也公布了源碼，有興趣的可以跑跑實驗。