一、概述
流形學(xué)習(xí)(Manifold Learning)是指通過(guò)從高維采樣數(shù)據(jù)中恢復(fù)低維流形結(jié)構(gòu)派阱,即找到高維空間中的低維流形诬留,并求出相應(yīng)的嵌入映射,以實(shí)現(xiàn)降維或者數(shù)據(jù)可視化。拿地球舉例來(lái)說(shuō)就是地球的表面可以認(rèn)為是一個(gè)二維平面被塞到了三維空間中文兑,那么歐氏距離(Euclidean Distance)就只能在短距離內(nèi)成立盒刚,在較遠(yuǎn)的距離就不再成立:
再舉一個(gè)例子,在下圖中可以認(rèn)為一個(gè)二維平面被扭曲放入一個(gè)三維空間中绿贞,在很小的距離內(nèi)歐式舉例是成立的:
而如果距離太遠(yuǎn)的話則可能歐氏距離就不成立因块,如下圖所示,黑點(diǎn)到藍(lán)點(diǎn)的歐氏距離比到紅點(diǎn)的歐氏距離更小籍铁,但是從數(shù)據(jù)分布上來(lái)看黑點(diǎn)和紅點(diǎn)更加相似一些涡上,這時(shí)歐式距離就沒(méi)有意義了:
對(duì)于上面的例子,流形學(xué)習(xí)要做的就是學(xué)習(xí)數(shù)據(jù)在低維空間的表示形式拒名,通俗來(lái)說(shuō)吩愧,就是將上圖中的數(shù)據(jù)“展開”:
這樣的數(shù)據(jù)顯然更容易用來(lái)進(jìn)行聚類或者其他的監(jiān)督學(xué)習(xí)方法。接下來(lái)的部分介紹幾種流形學(xué)習(xí)的方法增显。
二雁佳、Locally Linear Embedding(LLE)
Locally Linear Embedding(LLE)是一種非線性降維算法,可以使降維后的數(shù)據(jù)保持比較好的原有的流形結(jié)構(gòu)同云。
如下圖甘穿,我們?cè)诟呔S空間中有許多樣本,表示與之間的關(guān)系梢杭,LLE中我們認(rèn)為一個(gè)樣本可以由它的鄰近的點(diǎn)以做weighted sum即來(lái)得到:
使用梯度下降法來(lái)進(jìn)行求解所有的温兼,在進(jìn)行求解是我們希望的是能與越接近越好,因此損失函數(shù)如下:
接下來(lái)要做的是利用來(lái)求解降維后的結(jié)果武契,假設(shè)與其鄰接的樣本之間也滿足weighted sum的關(guān)系:
同樣使用梯度下降法來(lái)求解募判,需要注意的是這里要固定,把看做未知來(lái)求解咒唆。使用的損失函數(shù)如下:
需要注意一點(diǎn)就是使用LLE這種方式進(jìn)行降維不像PCA或者自編碼器一類方法有一個(gè)明確的function届垫,降維的結(jié)果完全是根據(jù)憑空生成的點(diǎn)。
在使用LLE進(jìn)行降維時(shí)全释,選擇鄰域內(nèi)的幾個(gè)點(diǎn)是一個(gè)可以調(diào)整的超參數(shù)装处,選用過(guò)少或過(guò)多的點(diǎn)效果都不會(huì)太好,選擇過(guò)多鄰居的局限性在于這樣會(huì)考慮進(jìn)一些距離較遠(yuǎn)的點(diǎn)浸船,而歐氏距離在遠(yuǎn)距離的效果不太好妄迁。下圖展示了不同數(shù)量的鄰近點(diǎn)的效果:
三、Laplacian Eigenmaps
- 簡(jiǎn)介
拉普拉斯特征映射(Laplacian Eigenmaps)是一種基于圖的降維算法李命,依賴于平滑性假設(shè)(Smoothness Assumption)登淘,其希望降維后的點(diǎn)(圖中有邊相連的點(diǎn))在降維后的空間中能夠相互接近,從而保持其原有的數(shù)據(jù)結(jié)構(gòu)封字。
- 圖的構(gòu)建
具體地黔州,假定在高維空間中有下圖的數(shù)據(jù)點(diǎn)耍鬓,則兩個(gè)紅色數(shù)據(jù)點(diǎn)之間的距離使用歐氏距離來(lái)度量的話是沒(méi)有意義的,數(shù)據(jù)點(diǎn)之間在流形中的距離才可以表明其相似的程度流妻。
使用拉普拉斯特征映射的方法首先需要構(gòu)建一張圖牲蜀,構(gòu)建的方法就是將相似度高的點(diǎn)之間連一條邊,可以設(shè)置一個(gè)閾值绅这,每個(gè)點(diǎn)與其相似度達(dá)到閾值的點(diǎn)之間連接一條邊涣达,邊的權(quán)重就是相似度,也可以將每個(gè)點(diǎn)與固定個(gè)最相似的點(diǎn)連接起來(lái)君躺。相似度可以采用徑向基函數(shù)或者余弦相似度等等峭判。
按照上述方法我們可以得到數(shù)據(jù)的鄰接矩陣和一張圖开缎。鄰接矩陣(是數(shù)據(jù)的總數(shù))棕叫,鄰接矩陣的元素就是數(shù)據(jù)點(diǎn)與的相似度,即:
得到的圖如下:
兩個(gè)數(shù)據(jù)點(diǎn)在流形中的距離可以用圖中的距離來(lái)近似:
- 類比半監(jiān)督學(xué)習(xí)
參考以下鏈接中平滑性假設(shè)基于圖的方法這一部分:半監(jiān)督學(xué)習(xí)|深度學(xué)習(xí)(李宏毅)(九)
在半監(jiān)督學(xué)習(xí)平滑性假設(shè)基于圖的方法中奕删,通過(guò)給損失函數(shù)添加一個(gè)正則化項(xiàng)可以利用無(wú)標(biāo)簽數(shù)據(jù)進(jìn)行半監(jiān)督學(xué)習(xí)俺泣,用來(lái)評(píng)估標(biāo)簽的相關(guān)性,這個(gè)正則化項(xiàng)為:
上式中是維的向量完残,和分別是有標(biāo)簽和無(wú)標(biāo)簽數(shù)據(jù)的數(shù)量伏钠,。
另外谨设,叫做圖的拉普拉斯矩陣(Graph Laplacian)熟掂。就是上述鄰接矩陣,是圖的度矩陣扎拣,這是一個(gè)對(duì)角矩陣():
這個(gè)正則項(xiàng)表明如果兩個(gè)數(shù)據(jù)點(diǎn)相連赴肚,則有值,那么和趨近于相同二蓝;如果兩個(gè)數(shù)據(jù)點(diǎn)不相連誉券,則為,那么和是否相同就無(wú)所謂刊愚。
加上正則化項(xiàng)以后損失函數(shù)變?yōu)椋?/p>
- Laplacian Eigenmaps
Laplacian Eigenmaps的方法類似于上述平滑性假設(shè)基于圖的半監(jiān)督學(xué)習(xí)方法踊跟,我們期望將高維數(shù)據(jù)降維成維空間的數(shù)據(jù),首先要按上述方法構(gòu)建一張圖并且得到鄰接矩陣鸥诽,因此設(shè)計(jì)損失函數(shù)如下:
降維后的數(shù)據(jù)記作商玫,是維的列向量,現(xiàn)做推導(dǎo)如下:
這里僅僅對(duì)進(jìn)行最小化是不可行的牡借,必須進(jìn)行一些限制决帖。因?yàn)槿绻覀冊(cè)O(shè)置,則就可以始終為最小值蓖捶。如果降維的結(jié)果的維度為地回,則我們需要限制,這是為了防止已經(jīng)被塞進(jìn)高維空間的流形再被塞進(jìn)更低維的空間中。
對(duì)降維后的數(shù)據(jù)再進(jìn)行聚類就是譜聚類(Spectral Clustering)算法刻像。
這里的拉普拉斯特征圖的降維方法可以參考以下更詳細(xì)的講解:譜聚類|機(jī)器學(xué)習(xí)推導(dǎo)系列(二十)畅买。
四、T-distributed Stochastic Neighbor Embedding(-SNE)
- 上述方法的問(wèn)題
在上面描述的鄰域嵌入方法中存在的問(wèn)題是细睡,在重建低維空間中的表示時(shí)只考慮了讓較高相似度的樣本點(diǎn)要盡可能地接近谷羞,而沒(méi)有考慮讓低相似度的樣本點(diǎn)要盡可能地遠(yuǎn),這樣會(huì)導(dǎo)致不同類別的樣本點(diǎn)會(huì)集中在一起溜徙,也就是擁擠問(wèn)題湃缎。下圖展示了使用LLE處理MNIST和COIL-20數(shù)據(jù)集時(shí)的效果,COIL-20是一個(gè)圖片數(shù)據(jù)集蠢壹,里面的樣本是某件物品(玩具車嗓违、杯子等)旋轉(zhuǎn)不同角度拍下的照片:
可以看到不同類別的樣本被擠到了一起,這就是上述問(wèn)題導(dǎo)致的結(jié)果图贸。
- t-SNE
假設(shè)需要將數(shù)據(jù)降維成蹂季,t-SNE的做法首先需要計(jì)算每一個(gè)樣本點(diǎn)對(duì)其他樣本點(diǎn)的歸一化的相似度,這里歸一化的目的是為了保證和下面的都是概率分布疏日,從而能夠應(yīng)用KL散度偿洁,計(jì)算方法如下:
對(duì)降維后的數(shù)據(jù)也需要計(jì)算每一個(gè)樣本點(diǎn)對(duì)其他樣本點(diǎn)的歸一化的相似度,計(jì)算方法如下:
我們的目標(biāo)就是讓這兩個(gè)分布越接近越好沟优,兩個(gè)分布接近程度的度量應(yīng)使用KL散度涕滋,因此優(yōu)化的目標(biāo)函數(shù)為:
在求解時(shí)使用梯度下降對(duì)微分即可。需要說(shuō)明的是t-SNE是對(duì)所有的數(shù)據(jù)進(jìn)行計(jì)算相似度挠阁,如果維度過(guò)高則會(huì)需要巨大的計(jì)算量宾肺,因此通常的做法是先使用PCA等方法進(jìn)行降維然后再使用t-SNE繼續(xù)降維,比如先使用PCA降到50維鹃唯,再使用t-SNE繼降到2維爱榕。
同時(shí)需要說(shuō)明的是t-SNE降維后,如果一個(gè)新的數(shù)據(jù)進(jìn)來(lái)坡慌,我們無(wú)法獲得該數(shù)據(jù)的降維表示黔酥,因此t-SNE不適用于train-test的模式,這種方法通常用于數(shù)據(jù)的可視化洪橘。
- 相似度的度量
對(duì)于的相似度的度量選用徑向基函數(shù)(公式省略了):
t-SNE是從SNE算法上改進(jìn)而來(lái)跪者,對(duì)于降維后的數(shù)據(jù)SNE選用徑向基函數(shù):
而t-SNE選用t分布:
選用上述相似度度量也就可以避免擁擠問(wèn)題,原因使用下面的圖來(lái)說(shuō)明熄求。在下圖中橫軸表示兩個(gè)樣本點(diǎn)的距離渣玲,縱軸表示概率分布。在優(yōu)化時(shí)我們會(huì)讓原來(lái)的數(shù)據(jù)的概率與降維后的數(shù)據(jù)的概率相等弟晚,可見(jiàn)如果原來(lái)的數(shù)據(jù)中的兩個(gè)樣本點(diǎn)距離很近時(shí)忘衍,在降維后的數(shù)據(jù)中距離也會(huì)很近逾苫,而如果原來(lái)的數(shù)據(jù)中的兩個(gè)樣本點(diǎn)距離很遠(yuǎn),則在降維后的數(shù)據(jù)中其距離會(huì)被拉伸地更遠(yuǎn):
- 效果
下圖展示了t-SNE在MNIST和COIL-20數(shù)據(jù)集上的效果:
可以看到t-SNE取得了一個(gè)比較直觀的可視化效果枚钓,不同類別的樣本被區(qū)分地很明顯铅搓。