Spectral hashing

Weiss, Yair, Antonio Torralba, and Rob Fergus. "Spectral hashing." Advances in neural information processing systems. 2009.

隨著網路的發展，我們可以收集成千上萬的data來形成training sets，但是，在這麼大量的資料底下，有兩個問題便被提了出來

(1)如何儲存如此大量的資料
(2)如何快速的找到相似的物件

Salakhutdinov and Hinton提出了一個semantic hashing 的概念，也就是說，每一個物件被表達成一串的compact binary code，這這些code依照一個基準建構，也就是說，相似物件必須有要相似的compact binary code，另外一方面，我們也需要可以快速的計算這一串compact binary code 。在這樣的情況下，尋找相似物件的問題便可以被簡化成尋找Hamming distance小的物件了。

在這樣的情況下，我們可以知道有三個條件必須被滿足

(1.)快速的計算compact binary code 
(2.)code的長度不能太長
(3.)相似的物件必須要具備有相似的code

在考慮 2. 3這兩個條件的情況下，我們實際上可以把問題轉換成以下的格式

其中y是我們所需要的code，而W則是指n個point的affinity matrix

我們可以發現minimizing指的正是第三個條件
而subject to 則是為了確保第二個條件


但是，實際上，這樣的問題可以被映射到graph partitioning，一個NP-HARD的問題


接著，我們可以將上式改寫













這依然是很難的問題!

因此，我們退而求其次，將第一個條件，也就是必須是0或1這個條件去除


如此這般，我們就可以簡單的得到一組答案，也就是具有最小eigenvalue的那組eigenvector(不包括0那組)

但這樣只能解決在training sets裡的資料，另外一方面的問題是，我們該如何搞定out of sample

實際上，我們選擇找到一個eigenfunction 



以下是spectral hashing的演算法

 (1) Finding the principal components of the data using PCA.

(2) Calculating the k smallest single-dimension analytical eigenfunctions of Lp using a
rectangular approximation along every PCA direction. This is done by evaluating
the k smallest eigenvalues for each direction using (equation 4), thus creating a list

of dk eigenvalues, and then sorting this list to find the k smallest eigenvalues.

(3) Thresholding the analytical eigenfunctions at zero, to obtain binary codes.



Result