基于Wasserstein距離概率分布模型的非線性降維

曹小鹿,辛云宏

(陜西師范大學 物理學與信息技術學院,西安 710119) (*通信作者電子郵箱xinyh@snnu.edu.cn)

基于Wasserstein距離概率分布模型的非線性降維

曹小鹿,辛云宏*

(陜西師范大學 物理學與信息技術學院,西安 710119) (*通信作者電子郵箱xinyh@snnu.edu.cn)

降維是大數據分析和可視化領域中的核心問題,其中基于概率分布模型的降維算法通過最優化高維數據模型和低維數據模型之間的代價函數來實現降維。這種策略的核心在于構建最能體現數據特征的概率分布模型?；诖?將Wasserstein距離引入降維,提出一個基于Wasserstein距離概率分布模型的非線性降維算法W-map。W-map模型在高維數據空間和其相關對應的低維數據空間建立相似的Wasserstein流,將降維轉化為最小運輸問題。在解決Wasserstein距離最小化的問題同時,依據數據的Wasserstein流模型在高維空間與其在低維空間相同的原則,尋找最匹配的低維數據投射。三組針對不同數據集的實驗結果表明W-map相對傳統概率分布模型可以產生正確性高且魯棒性好的高維數據降維可視化結果。

降維;Wasserstein距離;最小運輸問題;非線性方法;概率分布模型

0 引言

大數據不僅是指數據樣本量的龐大,也意味著數據特征維度的豐富。大數據給人們生活質量帶來的飛速提高不亞于其在數據處理上產生的挑戰。在人工智能和數據處理領域中,將包含多維特征向量的高維度的數據降低至易于計算且保留目標特征的低維度數據一直是一個核心議題。所謂數據降維是指通過線性或非線性映射方法將樣本從高維空間映射到低維空間,從而獲得高維數據的一個有意義的低維表示的過程[1]。尋找一個即適用于大數據又具有優良魯棒性的降維算法是解決維數災難和高維度信息贅余的有效戰略[2-3]。

數據降維算法根據對應數據類型的差異一般分為線性降維和非線性降維。線性降維是尋找高維數據在低維空間的線性投影的降維方法,如廣泛使用的主成分分析(Principal Component Analysis, PCA)[4]、線性判別分析(Linear Discriminant Analysis, LDA)[5]等；但此類方法無法準確高效地處理存在于流形曲面的非線性的數據。針對非線性結構的數據,產生了很多尋找非線性投射模型的非線性降維算法,如拉普拉斯特征映射(Laplacian Eigenmaps, LE)[6]、隨機鄰域嵌入(Stochastic Neighbor Embedding, SNE)[7]、t分布隨機鄰域嵌入(t-Stochastic Neighbor Embedding,t-SNE)[8]等。不同的算法在定義映射模型上有所差異。其中,建立可以表示數據內部隱藏的關聯結構的概率分布模型是數據降維和可視化的常用策略之一。在隨機鄰域嵌入 (Stochastic Neighbor Embedding, SNE)算法中,利用高維輸入數據間的相似關系構建的概率分布模型有效地將高維數據投影到了低維空間中。然而,這種局部特征算法存在嚴重的擁擠問題，即高維空間中的數據在投影至低維時,本來不相似的不同類別會重疊擁擠在低維空間的相同位置上。為了解決擁擠問題,t分布隨機鄰域嵌入(t-Stochastic Neighbor Embedding,t-SNE)算法在建立概率分布模型中使用到了長尾的t分布模型。在處理人工生成的一般規模的樣本時,這種概率分布模型可以在有效地進行數據降維同時呈現高質量且魯棒的數據可視化結果。但在面對現實世界中的高數量級別數據時,t-SNE算法的處理結果卻不盡如人愿。t-SNE算法在構建原始高維數據的分布模型時只保留了鄰近數據的相似度特征,使得其在不同類型的數據庫下的處理結果波動很大。在機器學習領域里,對于高數量級別數據的數據降維和可視化實現仍是一個挑戰。

以t-SNE算法為代表的概率分布模型降維算法在構建高維數據模型時都是參考單一的數據特征,如相似度、紋理特征、結構特征等,并且將其作為決定性特征。這種獨斷的建模使得后續的數據處理可視化不理想且容易受不同數據庫影響。因此,不僅限于一種特征的多種特征交叉建模機制是一種更準確有效的數據處理模型。

為保證保留原始數據的多種有效特征結構,本文提出一種基于Wasserstein距離的數據降維算法。Wasserstein距離[9],也稱為陸地移動距離,最早作為衡量直方圖差異的測量方式在計算機視覺領域被引入，其定義為解決最小運輸問題中將一個概率分布搬運到另一個分布所需要的最小消耗。此消耗由運輸過程中所產生的“地面距離”部分和“所占比”部分同時決定。這樣的定義使得Wasserstein距離能夠更完整地保存數據的多種有效特征結構。Wasserstein距離也應用于機器學習和信號處理的其他方面。Chazel等[10]提出將歐氏距離替換為Wasserstein距離的圖形處理算法。同時,Solomon等[11]提出將Wasserstein距離引入三維網格模型的顯著度計算中。到目前為止,Wasserstein距離還沒有被應用于數據降維和可視化領域。

本文將Wasserstein距離引入降維,提出了一種基于Wasserstein距離嵌入式模型的降維算法W-map(Wasserstein Embedding method)。該方法利用Wasserstein距離對高維數據建立同時保留相似度和數據結構特征的概率分布模型,接著在低維空間隨機建立一個表示,在保證高維和低維數據具有相同Wasserstein距離性質的原則下,構建最優化的低維投射。

1 W-map

W-map將降維問題轉化成最小運輸問題,在高維空間構建了原始數據的Wasserstein距離模型,用以尋找低維空間中有著相同Wasserstein距離模型的數據,引入代價函數來引導最匹配的低維數據。流程如圖1所示。

圖1 W-map算法流程

1.1 Wasserstein 概率分布模型

Wasserstein距離分為兩個部分:“地面距離”部分和“所占比”部分。在運輸問題中,對于兩個概率分布的Wasserstein 距離定義為:

(1)

其中:{fij}即為從i分布到j分布的“所占比”部分,又稱為數據表面的Wasserstein流,用來展示不同運輸平面的消耗;dij是i分布到j分布的“地面距離”,對于W-map最核心的是建立一個相關低維表示的分布,使這個分布的與原始分布具有較小的差異性,最終達到擁有一樣的表面Wasserstein流。在高維數據中,本文假設“所占比”的計算是基于數據分類,當兩個數據點的概率分布屬于同一類時,其傳輸表面的消耗就最低。根據此理論理解,本文定義分布模型高維空間中所占比可根據高斯核函數的計算公式如下:

f(xi,xj)=exp(‖xi-xj‖2/σ2)

(2)

其中:xi為原始高維數據集上的第i個數據點;fij為第i個分布和第j個分布被投射至再生核希爾伯特空間(Reproducing Kernel Hilbert Space, RKHS)中的兩個點的距離,當兩個分布在投射中處于近鄰位置,即屬于同一個類別,fij的值將會非常小。

同理,低維空間中的所占比的計算公式如下:

F(yi,yj)=exp(‖yi-yj‖2/σ2)

(3)

其中:yi為降維后構造出的低維數據集上的第i個數據點。“地面距離”部分dij可以有效度量兩個分布的相似性,通過測地距離、歐氏距離、KL(Kullback-Leibler)熵等不同的相似度度量公式計算得出。隨著分布的性質不同,計算方法不同。

基于Wasserstein距離的概率分布模型的建立結合了“地面距離”部分和“所占比”部分,將高維和低維的數據分布以Wasserstein距離模型有效地整合在一個便于分析的系統中。在高維數據空間中,定義xj是xi的近鄰點,其相關的概率分布可表示為概率分布:

(4)

其中:d(xi,xj)為“地面距離”部分,是xj和xi之間的相似度度量;g是人工設定的對于近鄰點的大概范圍限定,在低維概率分布中也有相似的范圍限定參數。低維的概率分布定義為:

(5)

其中:yi是原始數據xi在低維分布空間的對應投射。本文參考在t-SNE算法中的t分布函數的模型使用來增加不同分布之間的投射距離,以避免“擁擠問題”。在對比了歐氏距離的測地距離的效果后,因為其效果差異并不大,這里的相似度度量d(xi,xj)選擇使用計算量相對小的歐氏距離。

1.2 代價函數

在建立好概率分布函數后,需要一個成本函數來衡量建立的低維分布和高維原始分布之間的差異來引導低維分布的修正。當分布P和分布Q中的數據Wasserstein流相似時,低維數據空間中的數據集Y可用來體現原始高維數據集X的特征。在W-map中,使用KL散度(KL divergence)[12]來計算其成本函數如下:

(6)

在不斷縮小分布差異的過程中,可以尋找到與原始數據分布pij最匹配低維數據分布qij,從而確定其在低維的投影數據集。

1.3 優化策略

在利用隨機梯度下降法(Stochastic Gradient Descent, SGD)求得成本函數的最小值的過程中,面對小樣本量數據集W-map可以快速得到結果,但當數據集樣本量增大到一定范圍,計算時間就加長了許多。為了解決這個問題,引入交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)進行優化。

算法1 W-map算法。

輸入 高維數據集X={x1,x2,…,xn}。

輸出 低維數據集Y={y1,y2,…,yn}。

1)

建立高維空間數據X={x1,x2,…,xn}的概率分布模型pij(式(4))

2)

初始化低維空間數據Y={y1,y2,…,yn}

3)

Fort=1 toTdo

計算低維空間投射qij(式(5))

計算對應的低維空間的Wasserstein流(式(3))

計算成本函數C(式(6))

利用SGD更新Fij

Forn=1 toNdo

計算成本函數C(式(6))

利用SGD更新qij

End

End

4)

低維數據可視化Y={y1,y2,…,yn}

2 實驗

本文是用了三個數據集來檢驗本文提出的降維方法的可視化結果,其中的一個數據庫是人工生成數據庫,下載于http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html,用來生成Brokenswiss的數據庫；另外兩個數據集為手寫體MNIST數據集[13]以及圖片數據集Caltech-101[14]。

人工生成的Brokenswiss數據集,用同種顏色標記同類別的數據點,數據點分布坐標位置如圖2所示。

選取另外五種經典概率分布模型降維算法和W-map進行對比,可視化結果如圖3所示。由圖3可得出,比起會產生類間疊加和錯誤分類的PCA、Charting[15]和Probabilistic PCA、SNE、t-SNE和W-map都可以得到較正確的降維可視化結果。SNE的可視化結果相對t-SNE和W-map來說,同類數據更松散,類間界限更模糊；但W-map的可視化結果類間界限更清晰,同時解決了t-SNE產生的同類數據類內斷裂問題。這是由于W-map綜合了利用Wasserstein距離結合相似度和結構兩種特征來進行建模,使得類內不間斷且更可視化效果更緊密,類間分離清晰。

為了更好地分析數據,對其進行Tamp;C度量分析[16],所得的信度值如圖4所示。圖4中k為數據點的相鄰數據點個數,與另外五種算法相比，在Brokenswiss數據集中W-map算法擁有更高的可信度,能夠在不改變數據原始結構的前提下更準確地將原始高維數據投射到低維空間中。

圖2 Brokenswiss數據集

圖3 數據集Brokenswiss的降維可視化結果比較

圖4 Brokenswiss數據集上各算法可信度測量值

MNIST 數據集包含10個類別的60 000張手寫數據,隨機選取其中得5 000個樣本進行測試,可視化的結果如圖5所示,10種類別使用不同的幾何圖形標價,包括菱形、正方形、三角形、交叉、黑點等。從圖5中可以看出,在面對數量級大的顯示數據集MNIST時,相對于PCA、Probabilistic PCA、Charting、SNE，t-SNE和W-map可以產生正確性更高的可視化結果；相對于t-SNE的可視化結果,W-map的類間界限更加清晰。

Caltech101數據集包含102類別的9 000多個樣本,其類別豐富,包含從動物到飛機到花朵等都包含在內的102種食物圖片。隨機從中選取15個類別的多個樣本進行降維,同種類別的數據在可視化結果中使用相同顏色標定。從圖6中可以看出,在復雜多類別的大樣本數據集下,SNE和t-SNE在多種數據集中,魯棒性較差,其降維已經無法產生清晰的可視化結果；本文算法W-map在Caltech101數據集中可視化結果顯示,同類別的數據點集合沒有因為混雜其他類別數據點的斑點出現,能夠產生正確性高且魯棒性強的降維結果。

通過五種降維算法在以上三組的數據集的驗證,說明在大多數數據集下,W-map的性能優于現有的降維算法。

圖5 數據集手寫集MNIST的降維可視化結果對比

圖6 數據集Caltech101的降維可視化結果對比

3 結語

本文提出了一種新基于Wasserstein距離的建立概率分布模型的降維方法W-map。不同于其他概率分布模型的降維方法Probabilistic PCA、Charting、SNE和t-SNE,W-map引入Wasserstein距離來保留數據除了局部的結構特征相似度以外的結構信息。通過對PCA、Probabilistic PCA、Charting、SNE、t-SNE和W-map方法的比較,發現在大部分數據集上概率分布模型的降維方法都可以產生較好的可視化結果,但對比其他算法,W-map的有效度、信賴性綜合較好較穩定。然而,還需要進一步改進W-map,使得其能更好地適應更高位更大數量級的現實數據,同時還可以引入p-Wasserstein距離來進行升級建模。

References)

[1] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323.

[2] GOTTLIEB L A, KONTOROVICH A, KRAUTHGAMER R. Adaptive metric dimensionality reduction[J]. Theoretical Computer Science, 2016, 620: 105-118.

[3] 田守財, 孫喜利, 路永鋼. 基于最近鄰的隨機非線性降維[J]. 計算機應用, 2016, 36(2): 377-381. (TIAN S C, SUN X L, LU Y G. Stochastic nonlinear dimensionality reduction based on nearest neighbors[J]. Journal of Computer Applications, 2016, 36(2): 377-381.)

[4] MIKA S, SCH?LKOPF B, SMOLA A, et al. Kernel PCA and de-noising in feature spaces[EB/OL]. [2017- 01- 10]. https://alex.smola.org/papers/1999/MikSchSmoMuletal99.pdf.

[5] HASTIE T, TIBSHIRANI R. Discriminant analysis by Gaussian mixtures[J]. Journal of the Royal Statistical Society, 1996, 58(1): 155-176.

[6] BELKIN M, NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003, 15(6): 1373-1396.

[7] HINTON G, ROWEIS S. Stochastic neighbor embedding[J]. Advances in Neural Information Processing Systems, 2002, 41(4): 833-840.

[8] VAN der MAATEN L, HINTON G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(2605): 2579-2605.

[9] LIPMAN Y, PUENTE J, DAUBECHIES I. Conformal Wasserstein distance: II. computational aspects and extensions[J]. Mathematics of Computation, 2011, 82(281): 331-381.

[10] CHAZAL F, COHEN-STEINER D, MéRIGOT Q. Geometric inference for probability measures[J]. Foundations of Computational Mathematics, 2011, 11(6): 733-751.

[11] SOLOMON J, DE GOES F, PEYRé G, et al. Convolutional Wasserstein distances: efficient optimal transportation on geometric domains[J]. ACM Transactions on Graphics 2015, 34(4): 513-526.

[12] VAN ERVEN T, HARREMOS P. Rényi divergence and Kullback-Leibler divergence[J]. IEEE Transactions on Information Theory, 2012, 60(7): 3797-3820.

[13] DE GOES F, COHEN-STEINER D, PIERRE A, et al. An optimal transport approach to robust reconstruction and simplification of 2D shapes [J]. Computer Graphics Forum, 2011, 30(5): 1593-1602.

[14] AJEESH S S, INDU M S, SHERLY E. Performance analysis of classification algorithms applied to Caltech101 image database[C]// Proceedings of the 2014 International Conference on Issues and Challenges in Intelligent Computing Techniques. Piscataway, NJ: IEEE, 2014: 693-696.

[15] BRAND M. Charting a manifold[EB/OL]. [2017- 01- 10]. https://papers.nips.cc/paper/2165-charting-a-manifold.pdf.

[16] MOKBEL B, LUEKS W, GISBRECHT A, et al. Visualizing the quality of dimensionality reduction[J]. Neurocomputing, 2013, 112(1): 109-123.

ProbabilisticdistributionmodelbasedonWassersteindistancefornonlineardimensionalityreduction

CAO Xiaolu, XIN Yunhong*

(SchoolofPhysicsandInformationTechnology,ShaanxiNormalUniversity,Xi’anShaanxi710119,China)

Dimensionality reduction plays an important role in big data analysis and visualization. Many dimensionality reduction techniques with probabilistic distribution models rely on the optimizaition of cost function between low-dimensional model distribution and high-dimensional real distribution. The key issue of this type of technology is to efficiently construct the probabilistic distribution model representing the feature of original high-dimensional dataset most. In this paper, Wasserstein distance was introduced to dimensionality reduction, and a novel method named Wasserstein Embedded Map (W-map) was presented for high-dimensional data reduction and visualization. W-map converts dimensionality reduction problem into optimal transportation problem by constructing the similar Wasserstein flow in the high-dimensional dataset and its corresponding low-dimensional representation, and then the best matched low-dimensional visualization was found by solving the optimal transportation problem of Wasserstein distance. Experimental results demonstrate that the presented method performs well in dimensionality reduction and visualization for high-dimensional data.

dimensionality reduction; Wasserstein distance; optimal transportation problem; nonlinear technique; probabilistic model

2017- 04- 18;

2017- 07- 04。

國家自然科學基金資助項目(11374199,11574192)。

曹小鹿(1993—), 女, 陜西西安人, 碩士研究生, 主要研究方向:數據降維與可視化、機器學習; 辛云宏(1967—), 男, 陜西西安人,教授, 博士, 主要研究方向:主要研究方向:數據降維與可視化、微弱光電檢測與處理、被動目標定位與跟蹤、多傳感器信息融合。

1001- 9081(2017)10- 2819- 04

10.11772/j.issn.1001- 9081.2017.10.2819

TP181

A

This work is partially supported by the National Natural Science Foundation of China (11374199, 11574192).

CAOXiaolu, born in 1993, M. S. candidate. Her research interests include dimensionality reduction and visualization, machine learning.

XINYunhong, born in 1967, Ph. D., professor. His research interests include dimensionality reduction and visualization, weak photoelectric detection and processing, passive target location and tracking, multisensory information fusion.