機器學習_學習筆記系列(76)：黑塞特徵映射(Hessian Eigenmaps)
前幾回我們介紹了一些有關流行學習的演算法像是ISOMAP、Locally Linear Embedding和Laplacian Eigenmaps，今天我們要來介紹一個新的演算法「Hessian Eigenmaps」
Hessian Eigenmaps
關於Hessian Eigenmaps其是由David Donoho和Carrie Grimes所提出的，其論文名稱叫做
Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
關於David Donoho他是Stanford統計系教授，對於降維方面的研究有相當大的貢獻，有興趣的人可以去看看他的work
回歸正題，Hessian Eigenmaps其又可以叫做Hessian Locally Linear Embedding，其概念就是改進原本的Locally Linear Embedding和Laplacian Eigenmaps。
而對於HLLE其對於我們的每個neighbor引入了一個概念
hessian-based quadratic form
去重建我們Locally Linear的結構。
對於其演算法，假使我們有一個資料集X∈R^(N×M)，有N筆資料、M個特徵，我們在一開始的時候一樣會用Ball Tree搭配KNN Search建立每筆資料的k個Neighbor，得到
接著我們一樣把每筆資料減掉平均值，然後用SVD拆解
然後一樣假使我們想降到d維空間，我們就取U的前d個最大的singular value所對應的eigenvector。
但是在這邊我們引入了hessian-based quadratic form的概念，所以我們會把我們得到的eigenvector展開成二次，也就是我們會建立一個新的矩陣Y_i
(*代表矩陣相對的地方相乘，而非dot)
所以說我們的矩陣Y_i總共會有1+d+(1+d)d/2個欄位。接下來我們會把Y_i做Gram-Schmidt正交化，所以我們會先對Y_i做factorization
然後將Q_i單位向量化
然後在這裡我們會取Q_i(unit)後面(1+d)d/2個欄位，也就是帶有二次項資訊的欄位，存入矩陣W_i
最後我們會將第i筆neighbor的資訊加到儲存global information的矩陣B裡面
I_i代表第i表資料neighbor的所對應的index。
最後我們會把所有N筆資料的結果累加起來，再對B做eigen decomposition後，將eigenvalue由大到小做排序，把第2到第2+d大的eigenvalue其所對應的eigenvector取出，就是我們資料降維後的矩陣
Example
接下來我們來看MNIST手寫辨識資料集用HLLE的效果
我們可以看到其對於數字0明顯的分得非常開， 對於其他數字，其一樣也有不錯的效果。
Python Sample Code:
Github:
Reference:
[1] Donoho, D. L., & Grimes, C. (2003). Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Sciences, 100(10), 5591–5596.
