Table of Contents
Unsupervised Learning: Neighbor Embedding
今天要介紹的是一種非線性的降維方法，就是Neighbor Embedding
Manifold Learning
很多時候我們的樣本分佈可能在一個高維空間，但是樣本的分布點可能只是在低維空間裡面，被扭曲到高維空間中。像是地球表面就是一個Manifold，他是一個二維平面，卻被塞到三維空間裡
在Manifold中，只有距離很近的點可以使用歐式距離（Euclidean Distance)。Ｍanifold Learning 要做的就是把塞在高維空間的低維空間攤平。
Locally Linear Embedding
局部線性嵌入，Locally Linear Embedding，簡稱LLE
假設在原來的空間中，樣本點的分佈如下所示，我們關注 x^i 和它的鄰居x^j ，用 w_ij 來描述兩者的關係
假設每一個樣本點都是可以用它的neighbor做linear combination組合而成，那 w_ij 就是拿 x^j 去組合 x^i 時的權重weight，因此找點與點的關係 w_ij 這個問題就轉換成，找一組使得所有樣本點與周圍點線性組合的差距能夠最小的參數 w_ij
接下來就要做Dimension Reduction，把 x^j和 x^i 降維到z^j和 z^i，並且保持降維前後兩個點之間的關係 w_ij 是不變的
LLE的具体做法如下:
- 在原先的高維空間中找到 x^i 和 x^j 之間的關係 w_ij 以後就把它固定住
- 使 x^i 和 x^j 降維到新的低維空間上的 z^j和 z^i
- z^j和 z^i 需要minimize下面的式子:
- 即在原本的空間裡，x^i 可以由周圍點通過參數 w_ij 進行線性組合得到，則要求在降維後的空間裡， z^i 也可以用同樣的線性組合得到
實際上，LLE並沒有給出明確的降維函數，它沒有明確地告訴我們怎麼從x^i降維到z^i ，只是給出了降維前後的約束條件
在實際應用LLE的時候，對x^i來說，需要選擇合適的鄰居點數目K才會得到好的結果
下圖給出了原始paper中的實驗結果，K太小或太大得到的結果都不太好，注意到在原先的空間裡，只有距離很近的點之間的關係需要被保持住，如果K選的很大，就會選中一些由於空間扭曲才導致距離接近的點，而這些點的關係我們並不希望在降維後還能被保留
Laplacian Eigenmaps
另一種方法叫拉普拉斯特徵映射，Laplacian Eigenmaps
如果 x^i 和 x^j 在high density區域上是相近的，即相似度 w_ij 很大，則降 維後的 z^i 和 z^j 也需要很接近，總體來說就是讓下面的式子盡可能越小越好
注意，與LLE不同的是，這裡的 w_ij 表示x^i 和 x^j這兩點的相似度，上式也可以寫成
但光有上面這個式子是不夠的，假如令所有的z相等，比如令z^i=z^j=0，那上式就會直接停止更新
在semi-supervised中，如果所有label z^i 都設成一樣，會使得supervised部分的 ΣC(y^r,y^r（估計值）)變得很大，因此lost就會很大，但在這裡少了supervised的約束，因此我們需要給 z 一些額外的約束:
- 假設降維後 所處的空間為Ｍ維，則{z¹,z², … , z^N} =R^M ，我們希望降維後的 z 佔據整個M維的空間，而不希望它活在一個比M更低維的空間裡
- 最終解出來的 z 其實就是Graph Laplacian L 比較小的特徵值所對應的特徵向量
這也是Laplacian Eigenmaps名稱的由來，我們找的 就是Laplacian matrix的特徵向量 如果通過拉普拉斯特徵映射找到 之後再對其利用K-means做聚類，就叫做譜聚類(spectral clustering)
t-SNE
t-SNE，全稱為T-distributed Stochastic Neighbor Embedding，t分佈隨機鄰居嵌入
shortage of LLE
前面的方法只假設了相鄰的點要接近，卻㡪有假設不相近的點要分開
所以在MNIST使用LLE會遇到下圖的情形，它確實會把同一個class的點都聚集在一起，卻沒有辦法避免不同class的點重疊在一個區域，這就會導致依舊無法區分不同class的現象
COIL-20數據集包含了同一張圖片進行旋轉之後的不同形態，對其使用LLE降維後得到的結 果是，同一個圓圈代表同張圖像旋轉的不同姿態，但許多圓圈之間存在重疊
How t-SNE works
做t-SNE同樣要降維，在原來x的分佈空間上，我們需要計算所有 x^i 與 x^j 之間的相似度 S(x^i,x^j)
然後需要將其做歸一化: P(x^j|x^i)，即x^i 與 x^j的相似度佔所有與 x^i 相關的 相似度的比例
將x降維到z ，同樣可以計算相似度S’(z^i,z^j)，並作歸一化
注意，這裡的歸一化是有必要的，因為我們無法判斷在 x 和 z 所在的空間裡， S(x^i,x^j) 與S’(z^i,z^j) 的範圍是否是一致的，需要將其映射到一個統一的概率區間
我們希望找到的投影空間 z，可以讓 P(x^j|x^i) 和Q(z^j|z^i)的分佈越接近越好
How to use
t-SNE會計算所有樣本點之間的相似度，運算量會比較大，當數據量大的時候跑起來效率會比較低
常見的做法是對原先的空間用類似PCA的方法先做一次降維，然後用t-SNE對這個簡單降 維空間再做一次更深層次的降維，以期減少運算量
值得注意的是，t-SNE的式子無法對新的樣本點進行處理，一旦出現新的 x^i，就需要重新跑一遍該算法，所以t-SNE通常不是用來訓練模型的，他更適合用於估定數據的可視化
t-SNE常用於將固定的高維數據可視化到二維平面上
Conclusion
- LLE(Locally Linear Embedding)，局部線性嵌入算法，主要思想是降維前後，每個點與周圍鄰居的線性組合關係不變
- Laplacian Eigenmaps，拉普拉斯特徵映射，主要思想是在high density的區域，如果x^i、x^j 這兩個點相似度w_ij 高，則投影后的距離叫小
- t-SNE(t-distribution Stochastic Neighbor Embedding)，t分佈隨機鄰居嵌入，主要思想是，通過降維前後計算相似度由RBF function轉換為t-distribution，在聚集相似點的同時，拉開不相似點的距離，比較適合用在數據固定的可視化領域
