無監(jiān)督學習-鄰域嵌入方法|深度學習（李宏毅）（十八）

一、概述

流形學習（Manifold Learning）是指通過從高維采樣數(shù)據(jù)中恢復低維流形結構，即找到高維空間中的低維流形，并求出相應的嵌入映射，以實現(xiàn)降維或者數(shù)據(jù)可視化。拿地球舉例來說就是地球的表面可以認為是一個二維平面被塞到了三維空間中，那么歐氏距離（Euclidean Distance）就只能在短距離內成立，在較遠的距離就不再成立：

地球

再舉一個例子，在下圖中可以認為一個二維平面被扭曲放入一個三維空間中，在很小的距離內歐式舉例是成立的：

短距離

而如果距離太遠的話則可能歐氏距離就不成立，如下圖所示，黑點到藍點的歐氏距離比到紅點的歐氏距離更小，但是從數(shù)據(jù)分布上來看黑點和紅點更加相似一些，這時歐式距離就沒有意義了：

遠距離

對于上面的例子，流形學習要做的就是學習數(shù)據(jù)在低維空間的表示形式，通俗來說，就是將上圖中的數(shù)據(jù)“展開”：

數(shù)據(jù)

這樣的數(shù)據(jù)顯然更容易用來進行聚類或者其他的監(jiān)督學習方法。接下來的部分介紹幾種流形學習的方法。

二、Locally Linear Embedding（LLE）

Locally Linear Embedding（LLE）是一種非線性降維算法，可以使降維后的數(shù)據(jù)保持比較好的原有的流形結構。

如下圖，我們在高維空間中有許多樣本，w_{ij}表示x^i與x^j之間的關系，LLE中我們認為一個樣本x^i可以由它的鄰近的點x^j以w_{ij}做weighted sum即\sum _{j}w_{ij}x^{j}來得到：

原數(shù)據(jù)

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

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

接下來要做的是利用w_{ij}來求解降維后的結果z^i，假設z^i與其鄰接的樣本z^j之間也滿足weighted sum的關系：

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

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

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

需要注意一點就是使用LLE這種方式進行降維不像PCA或者自編碼器一類方法有一個明確的function，降維的結果完全是根據(jù)w_{ij}憑空生成的點。

在使用LLE進行降維時，選擇鄰域內的幾個點是一個可以調整的超參數(shù)，選用過少或過多的點效果都不會太好，選擇過多鄰居的局限性在于這樣會考慮進一些距離較遠的點，而歐氏距離在遠距離的效果不太好。下圖展示了不同數(shù)量的鄰近點的效果：

效果

三、Laplacian Eigenmaps

  1. 簡介

拉普拉斯特征映射（Laplacian Eigenmaps）是一種基于圖的降維算法，依賴于平滑性假設（Smoothness Assumption），其希望降維后的點（圖中有邊相連的點）在降維后的空間中能夠相互接近，從而保持其原有的數(shù)據(jù)結構。

  1. 圖的構建

具體地，假定在高維空間中有下圖的數(shù)據(jù)點，則兩個紅色數(shù)據(jù)點之間的距離使用歐氏距離來度量的話是沒有意義的，數(shù)據(jù)點之間在流形中的距離才可以表明其相似的程度。

數(shù)據(jù)

使用拉普拉斯特征映射的方法首先需要構建一張圖，構建的方法就是將相似度高的點之間連一條邊，可以設置一個閾值，每個點與其相似度達到閾值的點之間連接一條邊，邊的權重就是相似度，也可以將每個點與固定k個最相似的點連接起來。相似度可以采用徑向基函數(shù)或者余弦相似度等等。

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

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

得到的圖如下：

圖

兩個數(shù)據(jù)點在流形中的距離可以用圖中的距離來近似：

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

參考以下鏈接中平滑性假設基于圖的方法這一部分：半監(jiān)督學習|深度學習（李宏毅）（九）

在半監(jiān)督學習平滑性假設基于圖的方法中，通過給損失函數(shù)添加一個正則化項S可以利用無標簽數(shù)據(jù)進行半監(jiān)督學習，S用來評估標簽的相關性，這個正則化項為：

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

上式中y是R+U維的向量，R和U分別是有標簽和無標簽數(shù)據(jù)的數(shù)量，y=\begin{bmatrix} \cdots & y^{i} & \cdots & y^{j} & \cdots \end{bmatrix}^{T}。

另外L=D-W，叫做圖的拉普拉斯矩陣（Graph Laplacian）。W就是上述鄰接矩陣，D是圖的度矩陣，這是一個對角矩陣（d_{i,i}=\sum_{j=1}^{n}w_{i,j}）:

圖的度矩陣

這個正則項表明如果兩個數(shù)據(jù)點相連，則w_{i,j}有值，那么y^i和y^j趨近于相同；如果兩個數(shù)據(jù)點不相連，則w_{i,j}為0，那么y^i和y^j是否相同就無所謂。

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

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

  1. Laplacian Eigenmaps

Laplacian Eigenmaps的方法類似于上述平滑性假設基于圖的半監(jiān)督學習方法，我們期望將高維數(shù)據(jù)x降維成m維空間的數(shù)據(jù)z，首先要按上述方法構建一張圖并且得到鄰接矩陣W_{n\times n}，因此設計損失函數(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^i是m維的列向量，現(xiàn)做推導如下：

\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)

這里僅僅對S進行最小化是不可行的，必須進行一些限制。因為如果我們設置z^i=0，則S就可以始終為最小值0。如果降維的結果的維度為M，則我們需要限制span\left \{z^{1},z^{2},\cdots ,z^{N}\right \}=R^{M}，這是為了防止已經(jīng)被塞進高維空間的流形再被塞進更低維的空間中。

對降維后的數(shù)據(jù)再進行聚類就是譜聚類（Spectral Clustering）算法。

這里的拉普拉斯特征圖的降維方法可以參考以下更詳細的講解：譜聚類|機器學習推導系列（二十）。

四、T-distributed Stochastic Neighbor Embedding（-SNE）

  1. 上述方法的問題

在上面描述的鄰域嵌入方法中存在的問題是，在重建低維空間中的表示時只考慮了讓較高相似度的樣本點要盡可能地接近，而沒有考慮讓低相似度的樣本點要盡可能地遠，這樣會導致不同類別的樣本點會集中在一起，也就是擁擠問題。下圖展示了使用LLE處理MNIST和COIL-20數(shù)據(jù)集時的效果，COIL-20是一個圖片數(shù)據(jù)集，里面的樣本是某件物品（玩具車、杯子等）旋轉不同角度拍下的照片：

LLE

可以看到不同類別的樣本被擠到了一起，這就是上述問題導致的結果。

  1. t-SNE

假設需要將數(shù)據(jù)x降維成z，t-SNE的做法首先需要計算每一個樣本點對其他樣本點的歸一化的相似度，這里歸一化的目的是為了保證P和下面的Q都是概率分布，從而能夠應用KL散度，計算方法如下：

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

對降維后的數(shù)據(jù)也需要計算每一個樣本點對其他樣本點的歸一化的相似度，計算方法如下：

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

我們的目標就是讓這兩個分布越接近越好，兩個分布接近程度的度量應使用KL散度，因此優(yōu)化的目標函數(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})}

在求解時使用梯度下降對z微分即可。需要說明的是t-SNE是對所有的數(shù)據(jù)進行計算相似度，如果維度過高則會需要巨大的計算量，因此通常的做法是先使用PCA等方法進行降維然后再使用t-SNE繼續(xù)降維，比如先使用PCA降到50維，再使用t-SNE繼降到2維。

同時需要說明的是t-SNE降維后，如果一個新的數(shù)據(jù)進來，我們無法獲得該數(shù)據(jù)的降維表示，因此t-SNE不適用于train-test的模式，這種方法通常用于數(shù)據(jù)的可視化。

  1. 相似度的度量

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

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

t-SNE是從SNE算法上改進而來，對于降維后的數(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}}

選用上述相似度度量也就可以避免擁擠問題，原因使用下面的圖來說明。在下圖中橫軸表示兩個樣本點的距離，縱軸表示概率分布。在優(yōu)化時我們會讓原來的數(shù)據(jù)的概率與降維后的數(shù)據(jù)的概率相等，可見如果原來的數(shù)據(jù)中的兩個樣本點距離很近時，在降維后的數(shù)據(jù)中距離也會很近，而如果原來的數(shù)據(jù)中的兩個樣本點距離很遠，則在降維后的數(shù)據(jù)中其距離會被拉伸地更遠：

擁擠問題
  1. 效果

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

效果

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

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容