比如在下面這張圖中，雖然在原始資料中，
每一張圖片是64*64 pixel，
如果用row feature來表示的話，我們會有4096維的資料，
但是其實我們可以用三個維度(也就是上下、左右、光線角度)
來表示data
傳統的降維技巧包括了PCA跟MDS，
他們都實做簡單、計算快速、並且能確實發現在高維之下的線性子空間投影
但是實際上，我們可能會遇到非線性的情況，
例如在下圖A的例子中，
資料非線性的分布在一個我們稱為"二維瑞士捲"的子空間上
圖A中的兩個點，即便他們在二維瑞士捲上的距離異常的遙遠，
但是在真正的空間中，可能會詐欺似的靠近，
在這種情況下，PCA跟MDS都會失敗
這篇paper設法解決這個問題，我們設法設法找到兩點之間的真實距離
而方法的核心是如何計算在原始空間中遙遠的兩點的真實距離
大致上來說，
距離較近的兩點，我們直接使用原始空間的距離當作距離，
而對於距離遙遠的兩點，我們使用類似於shortest path的方法來處理
藉由加總path上的short hops的距離，來估計真正的距離。
首先，我們先決定哪些點是靠近的兩點，並且將那些點的距離代入原始空間的距離
並且在圖上將他們連線
在這裡我們有兩個'方法，第一個是取一個固定的半徑，只取在半徑內的
而第二個則是建立K-NN graph
第二步，我們計算all pair shortest path，並以此做維兩點之間的真正距離
第三步，我們設法利用這些距離的資料，在低維度的空間中找到合理的映射
式子如上，其中前項是我們計算出來的distance matrix，後項是在映射的子空間中，我們所得到的距離
沒有留言:
張貼留言