基于费希尔信息度量的随机近邻嵌入算法-张亚红.pdf

《基于费希尔信息度量的随机近邻嵌入算法-张亚红.pdf》由会员分享，可在线阅读，更多相关《基于费希尔信息度量的随机近邻嵌入算法-张亚红.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第42卷第6期2016年6月北京工业大学学报JOURNAL OF BEIJING UNIVERSITY OF TECHNOLOGYVol.42 No.6Jun. 2016基于费希尔信息度量的随机近邻嵌入算法张亚红,李玉鑑(北京工业大学计算机学院,北京 100124)摘 要:为提高文本分类的准确率,提出了费希尔信息度量随机近邻嵌入算法(Fisher information metric based onstochastic neighbor embedding, FIMSNE).首先,把文本的词频向量看作统计流形上的概率密度样本点,利用费希尔信息度量计算样本点之间的距离;然后,从信息几何的观点出

2、发,对t分布随机近邻嵌入(t-stochastic neighborembedding, t-SNE)进行改进,实现了新算法.真实文本数据集上的二维嵌入和分类实验的结果表明:FIMSNE的性能在总体上优于t-SNE、费希尔信息非参数嵌入(Fisher information nonparametric embedding,FINE)和主成分分析(principal components analysis,PCA).关键词:文本分类;统计流形;信息几何;费希尔信息度量; t分布随机近邻嵌入中图分类号: TP 391文献标志码: A文章编号: 0254 -0037(2016)06 -0862 -0

3、8doi: 10.11936/ bjutxb2015090037收稿日期: 2015-09-15基金项目:国家自然科学基金资助项目(61175004);北京市自然科学基金资助项目(4112009);高等学校博士学科点专项科研基金资助项目(20121103110029)作者简介:张亚红(1987 ),女,博士研究生,主要从事模式识别、机器学习、深度学习方面的研究, E-mail: plahpu Fisher Information Metric Based on Stochastic Neighbor EmbeddingZHANG Yahong, LI Yujian(College of Com

4、puter Science, Beijing University of Technology, Beijing 100124, China)Abstract: To improve the classification accuracy of text classification, Fisher information metric based onstochastic neighbor embedding (FIMSNE) was proposed. In this paper, text word frequency vectors weretaken as probabilistic

5、 density functions that were points on a statistical manifold, and their distances weredefined by Fisher information metric. From the view of information geometry, t-stochastic neighborembedding (t-SNE) was improved to FIMSNE. That FIMSNE outperforms t-SNE, Fisher informationnonparametric embedding

6、(FINE) and principal components analysis (PCA) in the whole was verifiedwith 2D-embedding and classification task to real text dataset.Key words: text classification; statistical manifold; information geometry; Fisher information metric;t-stochastic neighbor embedding文本处理是机器学习的一个重要领域,其主要任务有文本分类和聚类1-

7、2、信息抽取3、情感分析4等.其中文本分类在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都有着广泛的应用.在文本分类中,每个文档通常用一组词来表示,而文档间的相似度通过词频向量的欧式度量描述.由于词表的规模一般较大,大多上万,因此文本处理所涉及的词频向量具有高维特性,往往需要降维.常用的降维方法是主成分分析( principalcomponents analysis, PCA),但PCA是一种线性降维方法,对非线性数据的降维效果不理想.t分布随机近邻嵌入( t-stochastic neighbor 第6期张亚红,等:基于费希尔信息度量的随机近邻嵌入算法embedding,t-SNE

8、)5作为一种非线性数据降维方法,能够把数据嵌入到维数更低的空间.其基本思想是在高维样本空间把2个样本的相似度通过高斯核函数定义为它们的联合概率,在低维空间把其嵌入样本的相似度通过t分布核函数定义为相应的联合概率,目标是要求嵌入空间与原输入空间具有尽可能接近的联合概率分布,以达到在嵌入空间保持流形结构的目的.大量实验结果5表明:t-SNE在复杂数据可视化方面的性能优于LLE6、Isomap7、Laplacian Eigenmaps8等流形学习算法.t-SNE通过高斯核函数计算高维样本的联合概率时,需要用到欧氏距离来度量样本之间远近关系.然而,假设样本分布在一个统计流形上,利用欧氏距离来表示样本之

9、间的远近关系可能并不合适.事实上,基于统计流形来对数据进行建模已被应用于人脸识别9、纹理切割10、图像分析11和聚类12等领域.当样本被看作统计流形上的点时,一种更好的替代方法是从信息几何的观点出发,利用费希尔信息度量计算任意2个样本之间的距离13-14.本文假设所有样本数据位于一个统计流形上,将高维样本数据表达为概率密度,利用费希尔信息度量来定义2个概率密度之间的距离,通过改进t-SNE,提出了费希尔信息度量随机近邻嵌入算法(Fisher information metric based on stochastic neighborembedding, FIMSNE).最后,在真实文本数据集

10、上,验证了FIMSNE对文本嵌入和分类的有效性.1 统计流形及费希尔信息度量估计连续统计模型M是一簇定义在集合X上的概率密度函数,以兹 = 兹1,兹2, ,兹n为参数集,具有下面的形式:M = p(x|兹) |兹沂 专哿 Rn式中p(x|兹)满足条件p(x | 兹) 逸 0,坌 x 沂 X乙p(x | 兹)dx = 1 (1)对于离散情况,只需将式(1)中的乙p(x | 兹)dx = 1替换为移 p(x|兹) =1即可.当将统计模型M同费希尔信息度量关联时, M可称为统计流形.费希尔信息度量是一种定义在统计流形M上的二元函数.不妨设任意2个概率密度p1(x) = p(x|兹1)与p2(x) =

11、 p(x|兹2),它们之间的费希尔信息度量在本质上是计算p1和p2在M上的最短路径,可以定义为DF(p1,p2) = DF(兹1,兹2) =min兹( ):兹(0) = 兹1兹(1) = 兹2乙1 (0 d兹d )茁 TI(兹 () d兹d )茁 d茁 (2)式中:兹 = 兹(茁)为一条在M上连接p1和p2的路径13,15; I(兹)为费希尔信息矩阵,定义为Iij(兹) = - (E 鄣鄣兹ilb p(x|兹 ) () 鄣鄣兹jlb p(x|兹 ) )显然,利用式(2)计算p1和p2之间的费希尔信息度量比较困难,因此需要近似方法估计.一种有效的方法是借助费希尔信息度量和海林格距离(Hellin

12、ger distance)间的关系15-16,即DH(p1,p2) = 12 DF(p1,p2) + 庄(DF(p1,p2)3)(3)式中DH(p1,p2)为p1和p2间海林格距离.对于连续概率密度p1和p2,海林格距离定义为DH(p1,p2) = 12 乙( dp1 - dp2)2对于离散的概率密度p1 = (p11,p21, ,pk1)和p2 =(p12,p22, ,pk2),海林格距离定义为DH(p1,p2) = 12移 ki =1( pi1 - pi2)2由式(3)可知当p1寅 p2时DF(p1,p2)抑 2DH(p1,p2)因此可利用海林格距离来估算p1和p2间的费希尔信息度量.给定

13、一统计流形M = p1,p2, ,pL,那么对任意的pi和pj,它们之间的费希尔信息度量可以通过在一个无向加权完全图G = (V,E,W)的最短路径来估计.其中,顶点集V = M = p1,p2, ,pL,边集E = (pi,pj) | pi 沂 V,pj 沂 V,边的权重集合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).而在统计模型M中, pi和pj之间的费希尔信息度量可以估计为DF(pi,pj)抑 min

14、c,p(1),p(2), ,p(c)移 c-1k =12DH(p(k),p(k +1)(4)式中:p(1) = pi; p(c) = pj;c臆 L -1.2 t分布随机近邻嵌入框架数据嵌入方法是一种把高维有限样本集合X =368北 京 工 业 大 学 学 报2016年x1,x2, ,xn奂 RD在低维空间进行约简表示的方法.不妨把低维表示的结果写成Y = y1,y2, ,yn奂 Rd,其中d垲 D.如果用simX(xi,xj)表示xi与xj之间的相似性度量, simY(yi,yj)表示yi与yj之间的相似性度量, dist( , )衡量simX与simY间的不匹配度,则数据嵌入效果的好坏可以

15、用下面的目标函数17刻画:J(X,Y) = 移ni =1移 nj =1dist(simX(xi,xj),simY(yi,yj)(5)式中J的值越小表示低维嵌入的效果越好.一种优化J的策略是把它看作低维嵌入坐标yini =1的函数;另一种方法是先定义映射函数Y = F滋(X),再把J看作参数滋的函数.特别地,当J是连续函数时,常使用梯度下降法来求解.t分布随机近邻嵌入( t-stochastic neighborembedding, t-SNE)是一种结合概率分析的数据嵌入方法.这种方法在高维样本空间中使用高斯核函数把相似性度量simX(xi,xj)定义为选择xi和xj的联合概率rij = si

16、mX(xi,xj) = exp( - 椰 xi - xj椰2 / (2滓2)移 nk屹 lexp( - 椰 xk - xl椰 2 /2(滓2)(6)式中:滓是高斯核函数的方差;R = (rij)为高维样本相似度矩阵.同时, t-SNE在低维嵌入空间中使用自由度为1的t分布核函数把simY(yi,yj)定义为选择yi和yj的联合概率qij = simY(yi,yj) = (1 + 椰 yi -yj椰2) -1移 nk屹 l(1 + 椰 yk -yl椰 2) -1(7)式中Q = (qij)称为低维嵌入相似度矩阵.为了得到最佳的嵌入向量, t-SNE要求R与Q尽可能匹配,并把匹配的目标函数定义为K

17、L散度Jt - SNE(X,Y) = KL(R椰 Q) = 移ni =1移 nj =1rijlb rijqij(8)于是,最佳嵌入向量Y*可以通过梯度下降方法最小化Jt - SNE(X,Y)得到.需要说明的是, t-SNE在嵌入空间中用t分布核函数构造随机近邻概率,这是因为t分布是一种典型的重尾分布,使得嵌入数据间距离更大,有效缓解了使用高斯核函数构造随机近邻概率“挤压”低维流形的缺点5.3 费希尔信息度量随机近邻嵌入给定高维空间的样本集X = x1,x2, ,xn奂RD, t-SNE采用xi和xj的欧式距离通过高斯核函数来计算xi和xj的相似度,但其计算本质仍然依赖于欧式距离.而且通常来说,

18、高维空间的欧式距离并不能真实地反映数据在流形上的距离.而一个更为恰当的假设是这些数据位于一个统计流形上,整个数据集为流形上的一簇概率分布函数p(x;兹i),i =1, ,n,其中不同的参数兹i表示不同的样本.再根据第一部分的描述,通过由海林格距离逼近的费希尔信息度量(如式(4)所示)来对样本间的相似性进行建模.因此,本文从信息几何的观点出发,对t-SNE进行改进,采用基于费希尔信息度量的高斯核函数来计算样本的相似度,即rij = exp( -DF(pi,pj)2 / (2滓2)移 nk屹 lexp( - DF(pk,pl) / (2滓2)(9)提出了一种面向概率密度样本的数据嵌入方法,命名为F

19、IMSNE.FIMSNE的计算过程(如算法1所示)可以概括如下:首先针对每一个样本xi利用非参数化的密度估计算法,比如核方法和k紧邻方法,来计算样本的概率密度pi18 -19,并根据式(4)计算任意2个概率密度间的费希尔信息度量DF(pi,pj);接下来利用式(9)计算高维样本间的相似度矩阵R,并在初始化低维嵌入Y0 = y1,y2, ,yn奂 Rd的基础上利用式(7)计算低维嵌入相似度矩阵Q构造目标函数J(如式(8)所示);把J看作低维嵌入坐标yini =1的函数利用快速梯度下降方法得到最佳的低维嵌入向量Y* 沂 Rd 伊 n.值得说明的是算法在更新操作中使用了动量项琢(t)来减少迭代次数,

20、而且在嵌入坐标yini =1变得有条理前保持动量项琢(t)取较小的值时效果更好.与t-SNE类似,FIMSNE的计算复杂度为O(n2),其中n为数据集大小,这使得它无法直接应用于大数据集处理.算法1 FIMSNE输入:高维样本集合X = x1,x2, ,xn,嵌入维数d1) for i =1 to n do2) 计算xi概率密度pi3) end for4)计算DF(pi,pj)5)根据DF(pi,pj)计算R = (rij)468 第6期张亚红,等:基于费希尔信息度量的随机近邻嵌入算法6)根据标准正态分布N(0,10 -4I)初始化Y0 = y1,y2, ,yn7) for t =1 to m

21、axepoch do8) 计算低维嵌入相似度矩阵Q = (qij)9) 计算梯度鄣Jt - SNE鄣yi=4 移j(rij - qij)(yi -yj)(1 + 椰 yi - yj椰 2) -110) yti = yt -1i + 浊 鄣Jt - SNE鄣yi+ 琢(t) (yt -1i -yt -2i )11) end for输出:X的d维欧式嵌入Y* 沂 Rd 伊 n4 实验分析为了说明FIMSNE的性能,本文把它与t-SNE、FINE14和PCA分别进行了文本嵌入和文本分类的实验比较分析.所用的实验数据包括3个语料库:20Newsgroups20、TDT221 -22和Reuters21

22、57823.实验数据的说明详见4. 1节,文本嵌入的实验详见4. 2节,文本分类的实验详见4. 3节.在文本处理中,文档一般被表示成词数向量的形式: x = (t1, ,ti, ,tU),其中ti为第i个词项出现在该文档的次数, U表示整个文档集的总词项数.在本文的实验中首先将词数向量x转化成多项分布的形式x忆 (= t1T , , tiT , ,tU )T式中T = 移Uiti. t-SNE、FINE和PCA都直接以x忆作为输入,而在FIMSNE的计算过程中直接令样本的概率密度p(x) (= t1T , , tiT , ,tU )T . 4种算法的参数设置如表1所示.其中Prep为数据的困惑

23、度,取值区间通常设置为5, 505,用于估算方差参数滓; maxepoch为梯度下降算法的最大迭代次数;琢(t)为每次迭代的动量项,加快了优化和避免了差的局部最小值;为了便于比较,这里FIMSNE和t-SNE均采用参考文献5的默认设置,而且作者重复了已有算法的实验.表1 算法的参数设置Table 1 Parameter setting for the experiments算法参数FIMSNE Perp =30;maxpeoch =1 000; 琢(t) =0. 5,t 10时的分类效果差于FINE外,在其他情况下都比FINE高,在几乎所有情况下都比t-SNE高(除了图4(f) d =2的情况

24、外),在绝大部分情况下都比PCA高(除了图4(a) d =45、50,图4(e) d =45、50和图4(f) d =50的情况外),而且在嵌入维数d臆 20的情况下明显优于FINE(除了图4(a) d =15、20的情况外)和PCA.此外, FIMSNE在数据集sub4Reuters上的分类正确率平均比t-SNE和FINE高5%以上,在数据集sub10Reuters和sub30Reuters上的分类正确率平均比FINE高15%以上,在数据集sub20News上的分类正确率平均比t-SNE、FINE和PCA高10% 40%.由此可见, FIMSNE对文本降维后分类的效果优于t-SNE、FINE

25、和PCA,只需较低嵌入维数就可以达到同样的分类性能.最后需要说明的是当嵌入维数d 10时,FIMSNE和t-SNE的分类准确率趋于稳定,这是因为FINSNE是基于t-SNE的改进,而t-SNE的关键技术在于缓解使用高斯核函数构造随机近邻概率“挤压”低维流形的缺点5,24 -25,当嵌入维数较大时,比如10,那么流形的拥挤程度一定远低于嵌入维数为768北 京 工 业 大 学 学 报2016年图4 FIMSNE、t-SNE、FINE和PCA的低维嵌入的分类结果Fig.4 Classification rates for low-dimensional embedding using FIMSNE,

26、 t-SNE, FINE and PCA2时的流形,所以FIMSNE和t-SNE随着嵌入维数的增大并没有提高分类准确率.5 结论1)将样本的概率密度作为统计流形上的点来处理,采用费希尔信息度量计算样本之间的距离.通过改进t-SNE,提出了一种面向概率密度样本的数据嵌入方法 FIMSNE.2)真实文本数据的2维嵌入实验证实了FIMSNE能够成功揭示不同类别的自然分离.3)多种不同维数的嵌入分类实验表明FIMSNE在总体上明显优于t-SNE、FINE和PCA的性能.4)除了文本分类, FIMSNE作为一种有效的数据嵌入方法也可应用于其他的模式分类和信息可视化任务中.参考文献:1 CALADO P,

27、 CRISTO M, MOURA E, et al. Combininglink-based and content-based methods for Web documentclassification C 椅 Proc of the 12th InternationalConference on Information and Knowledge Management.New York: ACM, 2003: 394-401.2 XU W, LIU X, GONG Y. Document clustering based onnon-negative matrix factorizati

28、onC 椅 The 26th AnnualInternational ACM SIGIR Conference on Research andDevelopment in Information Retrieval. New York: ACM,2003: 267-273.3 BANKO M, CAFARELLA M J, SODERLAND S, et al.Open information extraction for the WebC椅 Proc of the20th International Joint Conferences on ArtificialIntelligence. S

29、an Francisco: Morgan Kaufmann, 2007:2670-2676.4 PANG B, LEE L. Opinion mining and sentiment analysisJ. Foundations and Trends in Information Retrieval,2008, 2(1): 459-526.5 MAATEN L, HINTON G. Visualizing data using t-SNEJ. Machine Learning, 2008, 9(3): 2579-2605.6 ROWEIS S T, SAUL L K. Nonlinear di

30、mensionalityreduction by locally linear embeddingJ. Science, 2000,290(5): 2323-2326.7 TENENBAUM J B, DE SILVA V, LANGFORD J C. Aglobal geometric framework for nonlinear dimensionalityreductionJ. Science, 2000, 290(5): 2319-2323.8 BELKIN M, NIYOGI P. Laplacian eigenmaps and spectraltechniques for emb

31、edding and clusteringJ. Advances inNeural Information Processing Systems, 2002, 14 (6):868 第6期张亚红,等:基于费希尔信息度量的随机近邻嵌入算法585-591.9 LEE S M, ABBOTT A L, ARAMAN P A. Dimensionalityreduction and clustering on statistical manifolds C 椅IEEE Conference on Computer Vision and PatternRecognition. Minneapolis:

32、IEEE, 2007: 1-7.10 ARANDJELOVIC O, SHAKHNAROVICH G, FISHER J,et al. Face recognition with image sets using manifolddensity divergenceC 椅 IEEE Conference on ComputerVision and Pattern Recognition. New York: IEEE, 2005:581-588.11 SRIVASTAVA A, JERMYN I H, JOSHI S. Riemanniananalysis of probability den

33、sity functions with applicationsin visionC椅 IEEE Conference on Computer Vision andPattern Recognition. New York: IEEE, 2007: 1-8.12 SALOJARVI J, KASKI S, SINKKONEN J.Discriminative clustering in fisher metricsC椅 Proc IntConf Artificial Neural Networks and Neural InformationProcessing. Berlin: Spring

34、er, 2003: 161-164.13 AMARSI S I. Methods of information geometryM. NewYork: American Mathematical, 2007: 25-45.14 CARTER K M. RAICH R, FINN W G, et al. Fine:fisher information nonparametric embedding J. IEEETransactions on Pattern Analysis and MachineIntelligence, 2009, 31(11): 2093-2098.15 KASS R E

35、, VOS P W. Geometrical foundations ofasymptotic inference M. New York: John Wiley &Sons, 2011: 65-82.16 NIKULIN M S. Hellinger distanceEB/ OL. 2011-02-07. https: 椅 www. encyclopediaofmath. org/ index.php/ Hellinger distance.17 BUNTE K, BIEHL M, HAMMER B. A generalframework for dimensionality reducin

36、g data visualizationusing explicit mapping functions J . NeuralComputation, 2012, 24(3): 771-804.18 CARTER K M. Dimensionality reduction on statisticalmanifoldsD. Michigan: University of Michigan, 2009.19 CARTER K, RAICH R, HERO A. Fine: informationembedding for document classification C 椅 IEEEInter

37、national Conference on Acoustics, Speech and SignalProcessing. 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 asexternal knowledge for document clustering C 椅Proceedings of the 15th ACM

38、 SIGKDD InternationalConference on Knowledge Discovery and Data Mining.NewYork: ACM, 2009: 389-396.22 ALLAN J. Introduction to topic detection and trackingM. Berlin: Springer, 2002: 1-16.23 Reuters-21578 text categorization collection EB/ OL.1999-02-16. http:椅 kdd. ics. uci. edu/ databases/reuters21

39、578/ reuters21578. html.24 MAATEN L, POSTMA E, HERIK H. Dimensionalityreduction: a comparative reviewJ. Journal of MachineLearning Research, 2007, 10(1): 1-35.25 MAATEN L. Learning a parametric embedding bypreserving local structure J . Journal of MachineLearning Research, 2009, 5: 384-391.(责任编辑 吕小红)968