基于費希爾信息度量的隨機近鄰嵌入算法

張亞紅，李玉鑑

基于費希爾信息度量的隨機近鄰嵌入算法

張亞紅，李玉鑑

（北京工業(yè)大學(xué)計算機學(xué)院，北京100124）

為提高文本分類的準(zhǔn)確率，提出了費希爾信息度量隨機近鄰嵌入算法（Fisher information metric based on stochastic neighbor embedding，F(xiàn)IMSNE）.首先，把文本的詞頻向量看作統(tǒng)計流形上的概率密度樣本點，利用費希爾信息度量計算樣本點之間的距離；然后，從信息幾何的觀點出發(fā)，對t分布隨機近鄰嵌入（t-stochastic neighbor embedding，t-SNE）進行改進，實現(xiàn)了新算法.真實文本數(shù)據(jù)集上的二維嵌入和分類實驗的結(jié)果表明:FIMSNE的性能在總體上優(yōu)于t-SNE、費希爾信息非參數(shù)嵌入（Fisher information nonparametric embedding，F(xiàn)INE）和主成分分析（principal components analysis，PCA）.

文本分類；統(tǒng)計流形；信息幾何；費希爾信息度量；t分布隨機近鄰嵌入

文本處理是機器學(xué)習(xí)的一個重要領(lǐng)域，其主要任務(wù)有文本分類和聚類［1-2］、信息抽?。?］、情感分析［4］等.其中文本分類在自然語言處理與理解、信息組織與管理、內(nèi)容信息過濾等領(lǐng)域都有著廣泛的應(yīng)用.在文本分類中，每個文檔通常用一組詞來表示，而文檔間的相似度通過詞頻向量的歐式度量描述.由于詞表的規(guī)模一般較大，大多上萬，因此文本處理所涉及的詞頻向量具有高維特性，往往需要降維.常用的降維方法是主成分分析（principal components analysis，PCA），但PCA是一種線性降維方法，對非線性數(shù)據(jù)的降維效果不理想.

t分布隨機近鄰嵌入（t-stochastic neighborembedding，t-SNE）［5］作為一種非線性數(shù)據(jù)降維方法，能夠把數(shù)據(jù)嵌入到維數(shù)更低的空間.其基本思想是在高維樣本空間把2個樣本的相似度通過高斯核函數(shù)定義為它們的聯(lián)合概率，在低維空間把其嵌入樣本的相似度通過t分布核函數(shù)定義為相應(yīng)的聯(lián)合概率，目標(biāo)是要求嵌入空間與原輸入空間具有盡可能接近的聯(lián)合概率分布，以達到在嵌入空間保持流形結(jié)構(gòu)的目的.大量實驗結(jié)果［5］表明:t-SNE在復(fù)雜數(shù)據(jù)可視化方面的性能優(yōu)于 LLE［6］、Isomap［7］、Laplacian Eigenmaps［8］等流形學(xué)習(xí)算法.

t-SNE通過高斯核函數(shù)計算高維樣本的聯(lián)合概率時，需要用到歐氏距離來度量樣本之間遠近關(guān)系.然而，假設(shè)樣本分布在一個統(tǒng)計流形上，利用歐氏距離來表示樣本之間的遠近關(guān)系可能并不合適.事實上，基于統(tǒng)計流形來對數(shù)據(jù)進行建模已被應(yīng)用于人臉識別［9］、紋理切割［10］、圖像分析［11］和聚類［12］等領(lǐng)域.當(dāng)樣本被看作統(tǒng)計流形上的點時，一種更好的替代方法是從信息幾何的觀點出發(fā)，利用費希爾信息度量計算任意2個樣本之間的距離［13-14］.

本文假設(shè)所有樣本數(shù)據(jù)位于一個統(tǒng)計流形上，將高維樣本數(shù)據(jù)表達為概率密度，利用費希爾信息度量來定義2個概率密度之間的距離，通過改進t-SNE，提出了費希爾信息度量隨機近鄰嵌入算法（Fisher information metric based on stochastic neighbor embedding，F(xiàn)IMSNE）.最后，在真實文本數(shù)據(jù)集上，驗證了FIMSNE對文本嵌入和分類的有效性.

1　統(tǒng)計流形及費希爾信息度量估計

連續(xù)統(tǒng)計模型M是一簇定義在集合X上的概率密度函數(shù)，以θ=［θ1，θ2，…，θn］為參數(shù)集，具有下面的形式:

式中p（x|θ）滿足條件

對于離散情況，只需將式（1）中的∫p（x|θ）dx=1替換為Σp（x|θ）=1即可.

當(dāng)將統(tǒng)計模型M同費希爾信息度量關(guān)聯(lián)時，M可稱為統(tǒng)計流形.費希爾信息度量是一種定義在統(tǒng)計流形M上的二元函數(shù).不妨設(shè)任意2個概率密度p1（x）=p（x|θ1）與p2（x）=p（x|θ2），它們之間的費希爾信息度量在本質(zhì)上是計算p1和p2在M上的最短路徑，可以定義為

式中:θ=θ（β）為一條在M上連接p1和p2的路徑［13，15］；I（θ）為費希爾信息矩陣，定義為

顯然，利用式（2）計算p1和p2之間的費希爾信息度量比較困難，因此需要近似方法估計.一種有效的方法是借助費希爾信息度量和海林格距離（Hellinger distance）間的關(guān)系［15-16］，即式中DH（p1，p2）為p1和p2間海林格距離.對于連續(xù)概率密度p1和p2，海林格距離定義為對于離散的概率密度p1=（p11，p21，…，pk1）和p2=（p12，p22，…，pk2），海林格距離定義為

由式（3）可知當(dāng)p1→p2時

因此可利用海林格距離來估算p1和p2間的費希爾信息度量.

給定一統(tǒng)計流形M=｛p1，p2，…，pL｝，那么對任意的pi和pj，它們之間的費希爾信息度量可以通過在一個無向加權(quán)完全圖G=（V，E，W）的最短路徑來估計.其中，頂點集V=M=｛p1，p2，…，pL｝，邊集E=｛（pi，pj）|pi∈V，pj∈V｝，邊的權(quán)重集合W=｛wij=2DH（pi，pj）|pi∈V，pj∈V｝.于是，對于圖 G中的任意2個頂點pi和pj，連接它們的一條路徑可以表示為｛（p（1）=pi，p（2）），（p（2），p（3）），… ，（p（c-1），p（c）=pj）｝.而在統(tǒng)計模型M中，pi和pj之間的費希爾信息度量可以估計為

式中:p（1）=pi；p（c）=pj；c≤L-1.

2　t分布隨機近鄰嵌入框架

數(shù)據(jù)嵌入方法是一種把高維有限樣本集合X=｛x1，x2，…，xn｝?R RD在低維空間進行約簡表示的方法.不妨把低維表示的結(jié)果寫成Y=｛y1，y2，…，yn｝?R Rd，其中d?D.如果用simX（xi，xj）表示xi與xj之間的相似性度量，simY（yi，yj）表示yi與yj之間的相似性度量，dist（·，·）衡量simX與simY間的不匹配度，則數(shù)據(jù)嵌入效果的好壞可以用下面的目標(biāo)函數(shù)［17］刻畫:

式中J的值越小表示低維嵌入的效果越好.一種優(yōu)化J的策略是把它看作低維嵌入坐標(biāo)｛yi｝ni=1的函數(shù)；另一種方法是先定義映射函數(shù)Y=Fμ（X），再把J看作參數(shù)μ的函數(shù).特別地，當(dāng)J是連續(xù)函數(shù)時，常使用梯度下降法來求解.

t分布隨機近鄰嵌入（t-stochastic neighbor embedding，t-SNE）是一種結(jié)合概率分析的數(shù)據(jù)嵌入方法.這種方法在高維樣本空間中使用高斯核函數(shù)把相似性度量simX（xi，xj）定義為選擇xi和xj的聯(lián)合概率

式中:σ是高斯核函數(shù)的方差；R=（rij）為高維樣本相似度矩陣.

同時，t-SNE在低維嵌入空間中使用自由度為1的t分布核函數(shù)把simY（yi，yj）定義為選擇yi和yj的聯(lián)合概率

式中Q=（qij）稱為低維嵌入相似度矩陣.

為了得到最佳的嵌入向量，t-SNE要求R與Q盡可能匹配，并把匹配的目標(biāo)函數(shù)定義為KL散度

于是，最佳嵌入向量Y*可以通過梯度下降方法最小化Jt-SNE（X，Y）得到.需要說明的是，t-SNE在嵌入空間中用t分布核函數(shù)構(gòu)造隨機近鄰概率，這是因為t分布是一種典型的重尾分布，使得嵌入數(shù)據(jù)間距離更大，有效緩解了使用高斯核函數(shù)構(gòu)造隨機近鄰概率“擠壓”低維流形的缺點［5］.

3　費希爾信息度量隨機近鄰嵌入

給定高維空間的樣本集X=｛x1，x2，…，xn｝?RRD，t-SNE采用xi和xj的歐式距離通過高斯核函數(shù)來計算xi和xj的相似度，但其計算本質(zhì)仍然依賴于歐式距離.而且通常來說，高維空間的歐式距離并不能真實地反映數(shù)據(jù)在流形上的距離.而一個更為恰當(dāng)?shù)募僭O(shè)是這些數(shù)據(jù)位于一個統(tǒng)計流形上，整個數(shù)據(jù)集為流形上的一簇概率分布函數(shù)｛p（x；θi），i=1，…，n｝，其中不同的參數(shù)θi表示不同的樣本.再根據(jù)第一部分的描述，通過由海林格距離逼近的費希爾信息度量（如式（4）所示）來對樣本間的相似性進行建模.因此，本文從信息幾何的觀點出發(fā)，對t-SNE進行改進，采用基于費希爾信息度量的高斯核函數(shù)來計算樣本的相似度，即

提出了一種面向概率密度樣本的數(shù)據(jù)嵌入方法，命名為FIMSNE.

FIMSNE的計算過程（如算法1所示）可以概括如下:首先針對每一個樣本xi利用非參數(shù)化的密度估計算法，比如核方法和k緊鄰方法，來計算樣本的概率密度pi［18-19］，并根據(jù)式（4）計算任意2個概率密度間的費希爾信息度量 ^DF（pi，pj）；接下來利用式（9）計算高維樣本間的相似度矩陣R，并在初始化低維嵌入Y0=｛y1，y2，… ，yn｝?R Rd的基礎(chǔ)上利用式（7）計算低維嵌入相似度矩陣Q構(gòu)造目標(biāo)函數(shù)J（如式（8）所示）；把J看作低維嵌入坐標(biāo)的函數(shù)利用快速梯度下降方法得到最佳的低維嵌入向量Y*∈R Rd×n.值得說明的是算法在更新操作中使用了動量項α（t）來減少迭代次數(shù)，而且在嵌入坐標(biāo)變得有條理前保持動量項α（t）取較小的值時效果更好.與t-SNE類似，F(xiàn)IMSNE的計算復(fù)雜度為O（n2），其中n為數(shù)據(jù)集大小，這使得它無法直接應(yīng)用于大數(shù)據(jù)集處理.

算法1FIMSNE

輸入:高維樣本集合X=｛x1，x2，…，xn｝，嵌入維數(shù)d

1）for i=1 to n do

2）計算xi概率密度pi

3）end for

6）根據(jù)標(biāo)準(zhǔn)正態(tài)分布N（0，10-4I）初始化Y0=｛y1，y2，…，yn｝

7）for t=1 to maxepoch do

8）搖搖計算低維嵌入相似度矩陣Q=（qij）

11）end for

輸出:X的d維歐式嵌入Y*∈R Rd×n

4　實驗分析

為了說明FIMSNE的性能，本文把它與t-SNE、FINE［14］和PCA分別進行了文本嵌入和文本分類的實驗比較分析.所用的實驗數(shù)據(jù)包括3個語料庫: 20Newsgroups［20］、TDT2［21-22］和Reuters21578［23］.實驗數(shù)據(jù)的說明詳見4.1節(jié)，文本嵌入的實驗詳見4.2節(jié)，文本分類的實驗詳見4.3節(jié).

在文本處理中，文檔一般被表示成詞數(shù)向量的形式:x=（t1，… ，ti，… ，tU），其中ti為第i個詞項出現(xiàn)在該文檔的次數(shù)，U表示整個文檔集的總詞項數(shù).在本文的實驗中首先將詞數(shù)向量x轉(zhuǎn)化成多項分布的形式

表1　搖算法的參數(shù)設(shè)置Table 1　搖Parameter setting for the experiments

4.1搖實驗數(shù)據(jù)集

20Newsgroups包括了20個不同領(lǐng)域的新聞組，每個新聞組對應(yīng)一個主題；TDT2語料庫包括2個新聞專線、2個廣播節(jié)目和2個電視節(jié)目共30種不同類目的文檔；Reuters21578包括了1987年出現(xiàn)在路透通訊社的50類文檔集，其中前30類文檔包含的樣本數(shù)達98%.根據(jù)3個語料庫中建議的訓(xùn)練和測試索引，同時為了排除樣本分布不均勻的影響，本文隨機均勻選擇了6個數(shù)據(jù)集來進行實驗，這些數(shù)據(jù)集的基本統(tǒng)計信息如表2所示.需要指出的是，sub20News4和sub4Reuters只選擇了原數(shù)據(jù)集中包含樣本數(shù)最多的前4類樣本，而sub10Reuters和sub30Reuters則分別選擇了Reuters21578中包含樣本數(shù)最多的前10類和30類的樣本.

表2　搖實驗數(shù)據(jù)集的信息描述Table 2　搖Text datasets and their statistics

4.2文本嵌入

利用 FIMSNE、t-SNE、FINE和 PCA分別將sub20News4、subTDT2和 sub10Reuters的高維樣本（包括訓(xùn)練和測試樣本）嵌入到二維空間，圖1～3是實驗得到的嵌入結(jié)果，其中不同的顏色表示數(shù)據(jù)集中不同的類別.從圖1～3中不難看出:FIMSNE的嵌入結(jié)果略好于t-SNE，而且它們都大體揭示了文檔集中不同類別的自然幾何分離狀況，盡管在sub20news4上的不同類別存在部分重疊，在subTDT2上也存在一些孤立點.FINE在sub20New4上的嵌入結(jié)果能夠在一定程度上揭示4個類別的自然分離，但是在其他文檔集上的嵌入結(jié)果卻很不理想.而在PCA的嵌入結(jié)果中不同類別的樣本相互交疊在一起，幾乎無法展示相互分離的狀況.因此，F(xiàn)IMSNE在數(shù)據(jù)的可視化方面比t-SNE、FINE和PCA更有優(yōu)勢.

4.3文本分類

首先應(yīng)用FIMSNE、t-SNE、FINE和PCA把表2中6個數(shù)據(jù)集嵌入到d=｛2，5，10，15，20，25，30，35，40，45，50｝等低維空間（這是因為當(dāng)嵌入維數(shù)大于40后，F(xiàn)IMSNE、t-SNE和FINE的分類準(zhǔn)確率基本趨于穩(wěn)定），然后通過線性核SVM在低維空間對這些數(shù)據(jù)集進行分類，最后根據(jù)10次分類實驗得到的平均準(zhǔn)確率繪制圖4.

根據(jù)圖4（a）～（f）可知，隨著嵌入維數(shù)d的增大，F(xiàn)IMSNE、t-SNE、FINE和PCA的分類準(zhǔn)確率都基本呈上升趨勢.顯然，F(xiàn)IMSNE的分類正確率在總體上最高，除了在sub20News4上當(dāng)維數(shù)d＞10時的分類效果差于 FINE外，在其他情況下都比FINE高，在幾乎所有情況下都比t-SNE高（除了圖4（f）d=2的情況外），在絕大部分情況下都比PCA高（除了圖4（a）d=45、50，圖4（e）d=45、50和圖4（f）d=50的情況外），而且在嵌入維數(shù)d≤20的情況下明顯優(yōu)于FINE（除了圖4（a）d=15、20的情況外）和PCA.此外，F(xiàn)IMSNE在數(shù)據(jù)集sub4Reuters上的分類正確率平均比t-SNE和FINE高5%以上，在數(shù)據(jù)集sub10Reuters和sub30Reuters上的分類正確率平均比 FINE高15%以上，在數(shù)據(jù)集sub20News上的分類正確率平均比t-SNE、FINE和PCA高10%～40%.由此可見，F(xiàn)IMSNE對文本降維后分類的效果優(yōu)于t-SNE、FINE和PCA，只需較低嵌入維數(shù)就可以達到同樣的分類性能.

最后需要說明的是當(dāng)嵌入維數(shù) d＞10時，F(xiàn)IMSNE和t-SNE的分類準(zhǔn)確率趨于穩(wěn)定，這是因為FINSNE是基于t-SNE的改進，而t-SNE的關(guān)鍵技術(shù)在于緩解使用高斯核函數(shù)構(gòu)造隨機近鄰概率“擠壓”低維流形的缺點［5，24-25］，當(dāng)嵌入維數(shù)較大時，比如10，那么流形的擁擠程度一定遠低于嵌入維數(shù)為2時的流形，所以FIMSNE和t-SNE隨著嵌入維數(shù)的增大并沒有提高分類準(zhǔn)確率.

5　結(jié)論

1）將樣本的概率密度作為統(tǒng)計流形上的點來處理，采用費希爾信息度量計算樣本之間的距離.通過改進t-SNE，提出了一種面向概率密度樣本的數(shù)據(jù)嵌入方法——FIMSNE.

2）真實文本數(shù)據(jù)的2維嵌入實驗證實了FIMSNE能夠成功揭示不同類別的自然分離.

3）多種不同維數(shù)的嵌入分類實驗表明FIMSNE在總體上明顯優(yōu)于t-SNE、FINE和PCA的性能.

4）除了文本分類，F(xiàn)IMSNE作為一種有效的數(shù)據(jù)嵌入方法也可應(yīng)用于其他的模式分類和信息可視化任務(wù)中.

［1］CALADO P，CRISTO M，MOURA E，et al.Combining link-based and content-based methods for Web document classification［C］∥ Procofthe12thInternational Conference on Information and Knowledge Management. New York:ACM，2003:394-401.

［2］XU W，LIU X，GONG Y.Document clustering based on non-negative matrix factorization［C］∥The 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM，2003:267-273.

［3］BANKO M，CAFARELLA M J，SODERLAND S，et al. Open information extraction for the Web［C］∥Proc of the 20thInternationalJointConferencesonArtificial Intelligence.San Francisco:Morgan Kaufmann，2007: 2670-2676.

［4］PANG B，LEE L.Opinion mining and sentiment analysis［J］.Foundations and Trends in Information Retrieval，2008，2（1）:459-526.

［5］MAATEN L，HINTON G.Visualizing data using t-SNE［J］.Machine Learning，2008，9（3）:2579-2605.

［6］ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290（5）:2323-2326.

［7］TENENBAUM J B，DE SILVA V，LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290（5）:2319-2323.

［8］BELKIN M，NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering［J］.Advances in Neural Information Processing Systems，2002，14（6）:585-591.

［9］LEE S M，ABBOTT A L，ARAMAN P A.Dimensionality reduction and clustering on statistical manifolds［C］∥IEEEConferenceonComputerVisionandPattern Recognition.Minneapolis:IEEE，2007:1-7.

［10］ARANDJELOVIC O，SHAKHNAROVICH G，F(xiàn)ISHER J，et al.Face recognition with image sets using manifold density divergence［C］∥IEEE Conference on Computer Vision and Pattern Recognition.New York:IEEE，2005: 581-588.

［11］SRIVASTAVA A，JERMYN I H，JOSHI S.Riemannian analysis of probability density functions with applications in vision［C］∥IEEE Conference on Computer Vision and Pattern Recognition.New York:IEEE，2007:1-8.

［12］SALOJARVIJ，KASKIS，SINKKONENJ. Discriminative clustering in fisher metrics［C］∥Proc Int Conf Artificial Neural Networks and Neural Information Processing.Berlin:Springer，2003:161-164.

［13］AMARSI S I.Methods of information geometry［M］.New York:American Mathematical，2007:25-45.

［14］CARTER K M.RAICH R，F(xiàn)INN W G，et al.Fine: fisher information nonparametric embedding［J］.IEEE TransactionsonPatternAnalysisandMachine Intelligence，2009，31（11）:2093-2098.

［15］KASS R E，VOS P W.Geometrical foundations of asymptotic inference［M］.New York:John Wiley& Sons，2011:65-82.

［16］NIKULIN M S.Hellinger distance［EB/OL］.［2011-02-07］.https:∥www.encyclopediaofmath.org/index. php/Hellinger_distance.

［17］BUNTEK，BIEHLM，HAMMERB.Ageneral framework for dimensionality reducing data visualization usingexplicitmappingfunctions［J］.Neural Computation，2012，24（3）:771-804.

［18］CARTER K M.Dimensionality reduction on statistical manifolds［D］.Michigan:University of Michigan，2009.

［19］CARTER K，RAICH R，HERO A.Fine:information embedding fordocumentclassification［C］∥ IEEE International Conference on Acoustics，Speech and Signal Processing.New York:IEEE，2008:1861-1864.

［20］20Newsgroups［EB/OL］.［2008-06-14］.http:∥qwone.com/～jason/20Newsgroups/.

［21］HU X，ZHANG X，LU C，et al.Exploiting Wikipedia as external knowledge for document clustering［C］∥Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. NewYork:ACM，2009:389-396.

［22］ALLAN J.Introduction to topic detection and tracking［M］.Berlin:Springer，2002:1-16.

［23］Reuters-21578 text categorization collection［EB/OL］.［1999-02-16］.http:∥kdd.ics.uci.edu/databases/ reuters21578/reuters21578.html.

［24］MAATEN L，POSTMA E，HERIK H.Dimensionality reduction:a comparative review［J］.Journal of Machine Learning Research，2007，10（1）:1-35.

［25］MAATEN L.Learningaparametricembeddingby preserving localstructure［J］.JournalofMachine Learning Research，2009，5:384-391.

（責(zé)任編輯呂小紅）

Fisher Information Metric Based on Stochastic Neighbor Embedding

ZHANG Yahong，LI Yujian
（College of Computer Science，Beijing University of Technology，Beijing 100124，China）

To improve the classification accuracy of text classification，F(xiàn)isher information metric based on stochastic neighbor embedding（FIMSNE）was proposed.In this paper，text word frequency vectors were taken as probabilistic density functions that were points on a statistical manifold，and their distances were defined by Fisher information metric.From the view of information geometry，t-stochastic neighbor embedding（t-SNE）was improved to FIMSNE.That FIMSNE outperforms t-SNE，F(xiàn)isher information nonparametric embedding（FINE）and principal components analysis（PCA）in the whole was verified with 2D-embedding and classification task to real text dataset.

text classification；statistical manifold；information geometry；Fisher information metric；t-stochastic neighbor embedding

TP 391

A

0254-0037（2016）06-0862-08

10.11936/bjutxb2015090037

2015-09-15

國家自然科學(xué)基金資助項目（61175004）；北京市自然科學(xué)基金資助項目（4112009）；高等學(xué)校博士學(xué)科點專項科研基金資助項目（20121103110029）

張亞紅（1987—），女，博士研究生，主要從事模式識別、機器學(xué)習(xí)、深度學(xué)習(xí)方面的研究，E-mail:plahpu@163. com