曹小鹿,辛云宏

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

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

曹小鹿,辛云宏*

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

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

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

0 引言

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

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

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

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

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

1 W-map

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

圖1 W-map算法流程

1.1 Wasserstein 概率分布模型

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

(1)

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

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

(2)

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

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

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

(3)

其中:yi為降維后構(gòu)造出的低維數(shù)據(jù)集上的第i個數(shù)據(jù)點?！暗孛婢嚯x”部分dij可以有效度量兩個分布的相似性,通過測地距離、歐氏距離、KL(Kullback-Leibler)熵等不同的相似度度量公式計算得出。隨著分布的性質(zhì)不同,計算方法不同。

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

(4)

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

(5)

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

1.2 代價函數(shù)

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

(6)

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

1.3 優(yōu)化策略

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

算法1 W-map算法。

輸入 高維數(shù)據(jù)集X={x1,x2,…,xn}。

輸出 低維數(shù)據(jù)集Y={y1,y2,…,yn}。

1)

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

2)

初始化低維空間數(shù)據(jù)Y={y1,y2,…,yn}

3)

Fort=1 toTdo

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

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

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

利用SGD更新Fij

Forn=1 toNdo

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

利用SGD更新qij

End

End

4)

低維數(shù)據(jù)可視化Y={y1,y2,…,yn}

2 實驗

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

人工生成的Brokenswiss數(shù)據(jù)集,用同種顏色標(biāo)記同類別的數(shù)據(jù)點,數(shù)據(jù)點分布坐標(biāo)位置如圖2所示。

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

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

圖2 Brokenswiss數(shù)據(jù)集

圖3 數(shù)據(jù)集Brokenswiss的降維可視化結(jié)果比較

圖4 Brokenswiss數(shù)據(jù)集上各算法可信度測量值

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

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

通過五種降維算法在以上三組的數(shù)據(jù)集的驗證,說明在大多數(shù)數(shù)據(jù)集下,W-map的性能優(yōu)于現(xiàn)有的降維算法。

圖5 數(shù)據(jù)集手寫集MNIST的降維可視化結(jié)果對比

圖6 數(shù)據(jù)集Caltech101的降維可視化結(jié)果對比

3 結(jié)語

本文提出了一種新基于Wasserstein距離的建立概率分布模型的降維方法W-map。不同于其他概率分布模型的降維方法Probabilistic PCA、Charting、SNE和t-SNE,W-map引入Wasserstein距離來保留數(shù)據(jù)除了局部的結(jié)構(gòu)特征相似度以外的結(jié)構(gòu)信息。通過對PCA、Probabilistic PCA、Charting、SNE、t-SNE和W-map方法的比較,發(fā)現(xiàn)在大部分數(shù)據(jù)集上概率分布模型的降維方法都可以產(chǎn)生較好的可視化結(jié)果,但對比其他算法,W-map的有效度、信賴性綜合較好較穩(wěn)定。然而,還需要進一步改進W-map,使得其能更好地適應(yīng)更高位更大數(shù)量級的現(xiàn)實數(shù)據(jù),同時還可以引入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]. 計算機應(yīng)用, 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。

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

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

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.