無(wú)監(jiān)督學(xué)習(xí)-鄰域嵌入方法|深度學(xué)習(xí)(李宏毅)(十八)

一、概述

流形學(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)有意義了:

遠(yuǎn)距離

對(duì)于上面的例子,流形學(xué)習(xí)要做的就是學(xué)習(xí)數(shù)據(jù)在低維空間的表示形式拒名,通俗來(lái)說(shuō)吩愧,就是將上圖中的數(shù)據(jù)“展開”:

數(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空間中有許多樣本,w_{ij}表示x^ix^j之間的關(guān)系梢杭,LLE中我們認(rèn)為一個(gè)樣本x^i可以由它的鄰近的點(diǎn)x^jw_{ij}做weighted sum即\sum _{j}w_{ij}x^{j}來(lái)得到:

原數(shù)據(jù)

使用梯度下降法來(lái)進(jìn)行求解所有的w_{ij}温兼,在進(jìn)行求解是我們希望的是x^j能與\sum _{j}w_{ij}x^{j}越接近越好,因此損失函數(shù)如下:

\sum _{i}||x^{i}-\sum _{j}w_{ij}x^{j}||_{2}

接下來(lái)要做的是利用w_{ij}來(lái)求解降維后的結(jié)果z^i武契,假設(shè)z^i與其鄰接的樣本z^j之間也滿足weighted sum的關(guān)系:

降維后的數(shù)據(jù)

同樣使用梯度下降法來(lái)求解z^i募判,需要注意的是這里要固定w_{ij},把z^i看做未知來(lái)求解咒唆。使用的損失函數(shù)如下:

\sum _{i}||z^{i}-\sum _{j}w_{ij}z^{j}||_{2}

需要注意一點(diǎn)就是使用LLE這種方式進(jìn)行降維不像PCA或者自編碼器一類方法有一個(gè)明確的function届垫,降維的結(jié)果完全是根據(jù)w_{ij}憑空生成的點(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

  1. 簡(jiǎn)介

拉普拉斯特征映射(Laplacian Eigenmaps)是一種基于圖的降維算法李命,依賴于平滑性假設(shè)(Smoothness Assumption)登淘,其希望降維后的點(diǎn)(圖中有邊相連的點(diǎn))在降維后的空間中能夠相互接近,從而保持其原有的數(shù)據(jù)結(jié)構(gòu)封字。

  1. 圖的構(gòu)建

具體地黔州,假定在高維空間中有下圖的數(shù)據(jù)點(diǎn)耍鬓,則兩個(gè)紅色數(shù)據(jù)點(diǎn)之間的距離使用歐氏距離來(lái)度量的話是沒(méi)有意義的,數(shù)據(jù)點(diǎn)之間在流形中的距離才可以表明其相似的程度流妻。

數(shù)據(jù)

使用拉普拉斯特征映射的方法首先需要構(gòu)建一張圖牲蜀,構(gòu)建的方法就是將相似度高的點(diǎn)之間連一條邊,可以設(shè)置一個(gè)閾值绅这,每個(gè)點(diǎn)與其相似度達(dá)到閾值的點(diǎn)之間連接一條邊涣达,邊的權(quán)重就是相似度,也可以將每個(gè)點(diǎn)與固定k個(gè)最相似的點(diǎn)連接起來(lái)君躺。相似度可以采用徑向基函數(shù)或者余弦相似度等等峭判。

按照上述方法我們可以得到數(shù)據(jù)的鄰接矩陣和一張圖开缎。鄰接矩陣W_{n\times n}n是數(shù)據(jù)的總數(shù))棕叫,鄰接矩陣的元素w_{i,j}就是數(shù)據(jù)點(diǎn)x^{i}x^{j}的相似度,即:

w_{i,j}=\left\{\begin{matrix} similarity,\; if\; connected\\ 0,\; otherwise \end{matrix}\right.

得到的圖如下:

兩個(gè)數(shù)據(jù)點(diǎn)在流形中的距離可以用圖中的距離來(lái)近似:

距離
  1. 類比半監(jiān)督學(xué)習(xí)

參考以下鏈接中平滑性假設(shè)基于圖的方法這一部分:半監(jiān)督學(xué)習(xí)|深度學(xué)習(xí)(李宏毅)(九)

在半監(jiān)督學(xué)習(xí)平滑性假設(shè)基于圖的方法中奕删,通過(guò)給損失函數(shù)添加一個(gè)正則化項(xiàng)S可以利用無(wú)標(biāo)簽數(shù)據(jù)進(jìn)行半監(jiān)督學(xué)習(xí)俺泣,S用來(lái)評(píng)估標(biāo)簽的相關(guān)性,這個(gè)正則化項(xiàng)為:

S=\frac{1}{2}\sum _{i,j}w_{i,j}(y^{i}-y^{j})^{2}=y^{T}Ly

上式中yR+U維的向量完残,RU分別是有標(biāo)簽和無(wú)標(biāo)簽數(shù)據(jù)的數(shù)量伏钠,y=\begin{bmatrix} \cdots & y^{i} & \cdots & y^{j} & \cdots \end{bmatrix}^{T}

另外L=D-W谨设,叫做圖的拉普拉斯矩陣(Graph Laplacian)熟掂。W就是上述鄰接矩陣,D是圖的度矩陣扎拣,這是一個(gè)對(duì)角矩陣(d_{i,i}=\sum_{j=1}^{n}w_{i,j}):

圖的度矩陣

這個(gè)正則項(xiàng)表明如果兩個(gè)數(shù)據(jù)點(diǎn)相連赴肚,則w_{i,j}有值,那么y^iy^j趨近于相同二蓝;如果兩個(gè)數(shù)據(jù)點(diǎn)不相連誉券,則w_{i,j}0,那么y^iy^j是否相同就無(wú)所謂刊愚。

加上正則化項(xiàng)以后損失函數(shù)變?yōu)椋?/p>

L=\sum _{x^{r}}C(y^{r},\hat{y}^{r})+\lambda S

  1. Laplacian Eigenmaps

Laplacian Eigenmaps的方法類似于上述平滑性假設(shè)基于圖的半監(jiān)督學(xué)習(xí)方法踊跟,我們期望將高維數(shù)據(jù)x降維成m維空間的數(shù)據(jù)z,首先要按上述方法構(gòu)建一張圖并且得到鄰接矩陣W_{n\times n}鸥诽,因此設(shè)計(jì)損失函數(shù)如下:

S=\frac{1}{2}\sum _{i,j}w_{i,j}||z^{i}-z^{j}||_{2}=trace(Z^{T}LZ)

降維后的數(shù)據(jù)記作Z_{n\times m}商玫,z^im維的列向量,現(xiàn)做推導(dǎo)如下:

\sum _{i,j}w_{i,j}||z^{i}-z^{j}||_{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}||z^{i}-z^{j}||_{2}w_{i,j}\\ =\sum_{i=1}^{n}\sum_{j=1}^{n}((z^{i})^{T}z^{i}-2(z^{i})^{T}z^{j}+(z^{j})^{T}z^{j})w_{i,j}\\ =\sum_{i=1}^{n}(\sum_{j=1}^{n}w_{i,j})(z^{i})^{T}z^{i}+\sum_{j=1}^{n}(\sum_{i=1}^{n}w_{i,j})(z^{j})^{T}z^{j}-2\sum_{i=1}^{n}\sum_{j=1}^{n}(z^{i})^{T}z^{j}w_{i,j}\\ =2\sum_{i=1}^{N}d_{i,i}(z^{i})^{T}z^{i}-2\sum_{i=1}^{n}\sum_{j=1}^{n}(z^{i})^{T}z^{j}w_{i,j}\\ =2trace(Z^{T}DZ)-2trace(Z^{T}WZ)\\ =2trace[Z^{T}(D-W)Z]\\ =2trace(Z^{T}LZ)

這里僅僅對(duì)S進(jìn)行最小化是不可行的牡借,必須進(jìn)行一些限制决帖。因?yàn)槿绻覀冊(cè)O(shè)置z^i=0,則S就可以始終為最小值0蓖捶。如果降維的結(jié)果的維度為M地回,則我們需要限制span\left \{z^{1},z^{2},\cdots ,z^{N}\right \}=R^{M},這是為了防止已經(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)

  1. 上述方法的問(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)不同角度拍下的照片:

LLE

可以看到不同類別的樣本被擠到了一起,這就是上述問(wèn)題導(dǎo)致的結(jié)果图贸。

  1. t-SNE

假設(shè)需要將數(shù)據(jù)x降維成z蹂季,t-SNE的做法首先需要計(jì)算每一個(gè)樣本點(diǎn)對(duì)其他樣本點(diǎn)的歸一化的相似度,這里歸一化的目的是為了保證P和下面的Q都是概率分布疏日,從而能夠應(yīng)用KL散度偿洁,計(jì)算方法如下:

P(x^{j}|x^{i})=\frac{S(x^{i},x^{j})}{\sum _{k\neq i}S(x^{i},x^{k})}

對(duì)降維后的數(shù)據(jù)也需要計(jì)算每一個(gè)樣本點(diǎn)對(duì)其他樣本點(diǎn)的歸一化的相似度,計(jì)算方法如下:

Q(z^{j}|z^{i})=\frac{S^{'}(z^{i},z^{j})}{\sum _{k\neq i}S^{'}(z^{i},z^{k})}

我們的目標(biāo)就是讓這兩個(gè)分布越接近越好沟优,兩個(gè)分布接近程度的度量應(yīng)使用KL散度涕滋,因此優(yōu)化的目標(biāo)函數(shù)為:

L=\sum _{i}KL(P(*|x^{i})||Q(*|z^{i}))=\sum _{i}\sum _{j}P(x^{j}|x^{i})log\frac{P(x^{j}|x^{i})}{Q(z^{j}|z^{i})}

在求解時(shí)使用梯度下降對(duì)z微分即可。需要說(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ù)的可視化洪橘。

  1. 相似度的度量

對(duì)于x的相似度的度量選用徑向基函數(shù)(公式省略了\sigma):

S(x^{i},x^{j})=exp(-||x^{i}-x^{j}||_{2}^{2})

t-SNE是從SNE算法上改進(jìn)而來(lái)跪者,對(duì)于降維后的數(shù)據(jù)SNE選用徑向基函數(shù):

S^{'}(z^{i},z^{j})=exp(-||z^{i}-z^{j}||_{2}^{2})

而t-SNE選用t分布:

S^{'}(z^{i},z^{j})=\frac{1}{1+||z^{i}-z^{j}||_{2}^{2}}

選用上述相似度度量也就可以避免擁擠問(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):

擁擠問(wèn)題
  1. 效果

下圖展示了t-SNE在MNIST和COIL-20數(shù)據(jù)集上的效果:

效果

可以看到t-SNE取得了一個(gè)比較直觀的可視化效果枚钓,不同類別的樣本被區(qū)分地很明顯铅搓。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市搀捷,隨后出現(xiàn)的幾起案子星掰,更是在濱河造成了極大的恐慌,老刑警劉巖嫩舟,帶你破解...
    沈念sama閱讀 212,718評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件氢烘,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡家厌,警方通過(guò)查閱死者的電腦和手機(jī)播玖,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,683評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)像街,“玉大人黎棠,你說(shuō)我怎么就攤上這事晋渺×铮” “怎么了?”我有些...
    開封第一講書人閱讀 158,207評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵木西,是天一觀的道長(zhǎng)畴栖。 經(jīng)常有香客問(wèn)我,道長(zhǎng)八千,這世上最難降的妖魔是什么吗讶? 我笑而不...
    開封第一講書人閱讀 56,755評(píng)論 1 284
  • 正文 為了忘掉前任,我火速辦了婚禮恋捆,結(jié)果婚禮上照皆,老公的妹妹穿的比我還像新娘。我一直安慰自己沸停,他們只是感情好膜毁,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,862評(píng)論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著愤钾,像睡著了一般瘟滨。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上能颁,一...
    開封第一講書人閱讀 50,050評(píng)論 1 291
  • 那天杂瘸,我揣著相機(jī)與錄音,去河邊找鬼伙菊。 笑死败玉,一個(gè)胖子當(dāng)著我的面吹牛敌土,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播运翼,決...
    沈念sama閱讀 39,136評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼纯赎,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了南蹂?” 一聲冷哼從身側(cè)響起犬金,我...
    開封第一講書人閱讀 37,882評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎六剥,沒(méi)想到半個(gè)月后晚顷,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,330評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡疗疟,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,651評(píng)論 2 327
  • 正文 我和宋清朗相戀三年该默,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片策彤。...
    茶點(diǎn)故事閱讀 38,789評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡栓袖,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出店诗,到底是詐尸還是另有隱情裹刮,我是刑警寧澤,帶...
    沈念sama閱讀 34,477評(píng)論 4 333
  • 正文 年R本政府宣布庞瘸,位于F島的核電站捧弃,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏擦囊。R本人自食惡果不足惜违霞,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,135評(píng)論 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望瞬场。 院中可真熱鬧买鸽,春花似錦、人聲如沸贯被。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,864評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)刃榨。三九已至弹砚,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間枢希,已是汗流浹背桌吃。 一陣腳步聲響...
    開封第一講書人閱讀 32,099評(píng)論 1 267
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留苞轿,地道東北人茅诱。 一個(gè)月前我還...
    沈念sama閱讀 46,598評(píng)論 2 362
  • 正文 我出身青樓逗物,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親瑟俭。 傳聞我的和親對(duì)象是個(gè)殘疾皇子翎卓,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,697評(píng)論 2 351

推薦閱讀更多精彩內(nèi)容