楚永贺 基于流形学习的词嵌入
新闻来源:IR实验室       发布时间:2017/12/11 0:00:01

基于流形学习的词嵌入

主讲人:楚永贺  

1流形学习

1.1流形的数学定义

1851Riemann在博士论文中提出了流形的概念,Whiteny1936年提出了微分流形的概念进一步加深了人们对流形的认识,随后研究人员将流形的概念引入到拓扑学,几何学中,当前流形学习在模式识别,计算机视觉,机器学习中具有重要的作用。接下来我们对流形给出严格的数学定义。

首先我们介绍拓扑空间的概念。

对于一个非空集合集合中的某些子集族,如果满足如下性质:

1) 都是中的元素;

2)有限元素的并运算在具有封闭性;

3)有限元素的交运算在具有封闭性;

这时我们称是非空集合的一个拓扑, 构成一个拓扑空间

同胚映射

假设是两个拓扑空间,之间存在一个函数映射关系,称为同胚映射,则这个同胚映射满足以下性质:

1满足双射的性质(满射和单射);

2满足连续的特点。(存在反函数);

3的反函数也是连续的;

当两个拓扑空间之间存在同胚映射时,我们此时称这两个拓扑空间同胚。

微分流形

微分流形也可以称为光滑流形,是几何学以及拓扑学中的重要概念,微分流形是一种具备微分结构的拓扑流形。

我们通过实际的例子展示流形的存在,如1所示:

(a)Punched sphere

 

(b)Helix

 

(c)Gaussian randomly sampled

 

(d)Swiss roll

1 手工流形例子

 

1.2流形学习简介

流形学习的思想在降维算法中得到广泛的关注开始于2000年发表在Science上的具有重要影响力的三篇论文[1,2,3]Roweis等人[1]2000年发表在Science关于流形学习的文章引起了研究人员的广泛关注,近年来研究人员对流形学习进行了深入研究,使得流形学习在理论和应用上都得到了很大的发展。

流形学习旨在保持高维数据空间的几何结构,即通过降维算法将高维数据映射到低维空间时,高维数据空间的几何结构在低维空间得到了保持,Daniel等人[2]在感知学的基础上研究了人类感知与存在于高维数据中的低维流形之间的关联,Daniel等人[2]通过研究发现我们人类的感知以流形的形式存在。我们通过人脸图像(图1所示)作为例子来展示人类视觉感知中流形的存在,当我们看到人脸图像在光线,尺度,旋转,光照强度等因素发生改变时,这时我们的视觉高维空间就会产生一个低维的非线性流形结构,这一研究从生物学角度为流形学习提供了重要的依据。

人的大脑感知自然界的同类事物,往往只记录其本质的变化。例如:人脸的表情、位置变化,不同的类别分布在大脑不同的低维流形上。具体实例如图1所示:

2268-1-med

2人类视觉感知中的流形

1.3基于流形学习的降维算法

1.3.1局部线性嵌入[1]LLE

LLE算法的基本思想上是数据样本点由局部邻域的数据点来线性表示从而得到一个低维坐标。LLE算法可以分为三个步骤,第一步计算高维空间中数据样本个近邻点。第二根据第一步求取的近邻点对数据线性重构并计算重构权值矩阵.

重构误差函数可表示为:

     1.1 

利用拉格朗日乘子法在的约束条件下,求的最小值,即:

                   1.2

用上式对求导并令其为0,则

其中,维全1列向量。

第三步,根据第二步得到的权值矩阵,低维数据样本同样由相应的个近邻点重建,目标函数可以表示为:

 

                 1.3

公式(1.3)中,公式(1.3)受两个两个条件的约束:。其中维单位矩阵,为单位矩阵的第列,我们对进行特征值分解,得到对应的最小个非零特征值为个非零特征值对应的特征向量为,则LLE算法的低维坐标可表示为

LLE算法作为经典的流形学习算法很好的保持了数据样本的局部线性结构,能够有效揭示高维数据的非线性结构的特性,图3给出了LLE算法应用于Twin Peaks S-curvePunctured Sphere 数据的示例图。

 

                         3 LLE 的示例图

LLE算法的优点

(1) LLE算法可以学习任意维数的低维流形.

(2) LLE算法中的待定参数很少, K d.

(3) LLE算法中每个点的近邻权值在平移, 旋转,伸缩变换下是保持不变的.

(4) LLE算法有解析的整体最优解,不需迭代.

(5) LLE算法归结为稀疏矩阵特征值计算, 计算复杂度相对较小, 容易执行.

LLE算法的缺点

(1) LLE算法要求所学习的流形只能是不闭合的且在局部是线性的.

(2) LLE算法要求样本在流形上是稠密采样的.

(3) LLE算法中的参数 K, d 有过多的选择.

(4) LLE算法对样本中的噪音很敏感.

(5) 对于新样本的映射需要重新计算。

1.3.2等距映射[3]ISOMAP

等距映射算法是在多尺度变换的基础上提出的,ISOMAP算法利用测地线距离替代MDS[4]算法中的欧氏距离,从而获取数据的全局几何结构,力求数据样本的内在流形结构,ISOMAP算法利用最短路径获取数据样本间的距离,然后利用MDS算法得到一个有效的低维坐标,因此ISOMAP 算法可以看做是MDS算法的进一步扩展。ISOMAP算法可以分为三个步骤:第一步,构建邻域图,计算高维空间中数据样本点与其他数据样本点的欧氏距离,然后利用邻近的方式构建邻域图。第二步,构建测地线距离矩阵,利用Dijkstra 算法计算任意两个数据点间的测地线距离,然后计算测地线距离矩阵。第三步,计算低维坐标,利用MDS算法,记,其中为单位矩阵,为全1向量,的最大的个特征值为个特征值对应的特征向量为,则投影变换矩阵可以表示为,所求的低维坐标为

ISOMAP算法不同于LLE算法,ISOMAP算法保持了全局意义上的点对距离,因此,ISOMAP算法是一个全局的降维算法,ISOMAP算法在计算数据点之间的距离时考虑了数据的局部结构的信息,因此ISOMAP算法具备揭示数据样本内在流形结构的能力。

4 Isomap 算法的例子

 

Isomap算法的特点

(1) Isomap是非线性的, 适用于学习内部平坦的低维流形, 不适于学习有较大内在曲率的流形。

 (2) Isomap算法中有两个待定参数K, d

 (3) Isomap算法计算图上两点间的最短距离, 执行起来比较慢。

 

1.3.3拉普拉斯特征映射[5]LE

拉普拉斯特征映射算法将谱图理论应用到降维算法中,LE算法的基本思想是在高维空间中离得比较近的点那么在低维空间中也应该离得比较近。LE算法首先构建数据样本的邻接图通过热核函数计算数据样本点间的权重关系,进而得到一个邻接权值矩阵。LE算法在高维数据样本邻接图结构不变的情况下通过变换得到一个低维坐标表示。LE算法的目标函数可以表示为:LE算法可以分为三步,第一步,计算高维数据空间给定数据点个最近邻点,进一步构建一个无向图的节点表示个数据样本点与它的邻近数据样本点之间的近邻关系。第二步,利用热核函数计算权值,其中为一个可以调节的参数。在计算中,我们可以假设,则。第三步,定义,为拉普拉斯特征矩阵,为对角矩阵,为数据样本的个数。我们对进行特征值分解,得到对应的最小个非零特征值为个非零特征值对应的特征向量为,则LE算法的低维坐标可表示为

5 Laplacian Eigenmap算法的例子如图

 

Laplacian Eigenmap算法的特点:

(1) LE算法是局部的非线性方法。

(2) LE算法与谱图理论有很紧密的联系。

(3) LE算法中有两个参数 k,d

(4 ) LE算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解。

(5) LE算法使原空间中离得很近的点在低维空间也离得很近, 可以用于聚类。

1.4 LLE, Isomap, LE 有效的原因

(1) 它们都是非参数的方法,不需要对流形的很多的参数假设。

(2) 它们是非线性的方法,都基于流形的内在几何结构,更能体现现实中数据的本质。

(3) 它们的求解简单,都转化为求解特征值问题,而不需要用迭代算法。

1.5流形学习问题探讨

(1) 对嵌入映射或者低维流形作出某种特定的假设, 或者以保持高维数据的某种性质不变为目标。

(2) 将问题转化为求解优化问题。

(3) 提供有效的算法。

1.5流形学习的应用

 (1) 数据可视化。

 (2) 人脸图像,手写数字图像。

 (3) 高维时间序列分析、自然语言处理,文本分类,词嵌入等领域。

 

2 基于流形学习的词嵌入

文献[6]《《Word Re-Embedding via Manifold Dimensionality Retention》》发表于EMNLP2017,上述文献指出:词嵌入方法利用语料库中的词共现将词映射为向量的形式来恢复欧氏度量空间,但是这种词嵌入方式低估了离得比较近的单词的相似性,高估了离得比较远的单词的相似性。针对当前词嵌入存在的上述问题,文献[6]提出了基于流形学习维度保持的词重新嵌入方法。该方法将流形学习的思想引入到词嵌入的预训练,在词嵌入阶段,利用流形学习构建单词的邻域结构,通过词嵌入方法将单词映射到新的欧氏空间使得单词之间的邻域结构得到保持。

文献通过例子展示了所提方法的有效性,在WS353[7]中单词之间的相似性定性指标为:

                        QQ截图20171015165453

6 WS353指标单词之间的相似性

6给出了利用WS353指标得到的shorewoodland之间的相似性,physicsporoton之间的相似性。

文献[6]利用Glove42B,300维的词嵌入方法计算图6中单词之间的cosine相似性却得到了与图6单词之间相似性相反的结果如图7所示:

 

QQ截图20171015164919

7 Glove方法单词之间的相似性

文献[6]利用流形学习中的局部线性嵌入方法对Glove进行修改后得到单词之间的cosine相似性得到的单词之间相似性的结果如图8所示:

QQ截图20171015165632

8基于流形学习的单词之间的相似性

通过图6、图7、图8我们可以看到图6是单词之间的实际相似性,在利用Glove词嵌入方法时得到了与实际相似性相反的结果,通过将流形学习引入到Glove方法中对Glove方法进行改进得到的单词之间的相似性与单词之间的实际相似性相吻合。

2.1 相关工作

Hashimoto等人[8]指出词嵌入和流形学习分别使用词共现和高维特征恢复欧式度量,Hashimoto等人同样将流形学习引入到词嵌入中,文献[8]和文献[6]方法不同的是,文献[6]起初从一个已经训练好的词嵌入空间开始通过学习数据间的几何结构从而提高词嵌入的效果,文献[6]不使用流形学习来降低维度,而是在两个同等维度的坐标系之间进行变换。文献[6]和文献[8]方法的不同点如图9所示:

 

QQ截图20171128173754

9 文献[6]和文献[8]方法对比

2.2 基于流形学习的词嵌入模型[6]

a 从始的嵌入空间开始,矢量按词频排序,从这个空间中选择一个样本窗口用于学习流形。

b 使用LLE算法[1]将流形学习模型拟合到所选样本,在这个阶段保持词向量原维度的情况下对词向量重新训练。

c 从原始空间中选择任意的测试词向量。

d 所得到的拟合模型作为一种变换,用于将测试向量转换成一个存在于新的重新嵌入空间中的向量。具体模型如图10所示:

 

QQ截图20171128174816

10基于流形学习的词嵌入模型[5]

2.3 算法流程

(1)在基于单词频率排序的样本集中选取一个样本子集。

(2)利用流形学习方法LLE选取词向量XK近邻点构建X的邻域结构,同时最小化误差函数:

 

QQ截图20171128200841

                (2.1)

(3)在公式(1)中如果不在邻域内则权重,权重W被用来通过邻域保持映射来构造样本X的新的嵌入Y,低维空间样本Y的误差函数可写为:

QQ截图20171128200849

           (2.2)

4)在步骤(c)和(d)中,为了变换任意向量x,首先通过最小化该函数从样本XxK个最近邻居构建权重:

QQ截图20171128200856

            (2.4)

(5)在公式(3)中如果不在邻域内则权重,利用权重与新的嵌入Yx转换为新的嵌入空间的y

QQ截图20171128200908

            (2.4)

3 实验结果

数据集:利用Glove模型训练词向量,将词向量作为原始的输入,Wikipedia 2014 + Gigaword 5 (6B tokens, 400K vocab, 50d, 100d, 200d, & 300d 向量), and Common Crawl (42B tokens, 1.9M vocab, 300d 向量)[9]

 

QQ截图20171015191610

QQ截图20171128201310

11: Accuracy on WS353 similarity task as a function of manifold dimensionality. (Space is

GloVe 42B 300d. Window start = 7000, LLE local neighbours =1000, Window length = 1001.)

QQ截图20171128201318

12: Accuracy on WS353 as a function ofwindow length. (GloVe 42B 300d, LLE local neighbours =1000. Manifold dimensions =300.)

QQ截图20171128201345

13: Accuracy on similarity tasks as a function of window start. (a) Original space GloVe 42B 300d, with WS353. (b) 42B 300d, with RG65. (c) 6B 300d, with WS353. (LLE local neighbours =1000, Window length = 1001, Manifold dimensionality = 300.)

5总结

文献[5]考虑到当前的词嵌入方法忽略了词与词之间的邻域结构信息,因此将流形学习的思想引入到词嵌入中对当前的词嵌入方法进行改进,通过文献展示的实验结果可以看到基于流形学习的词嵌入方法的有效性,在未来词嵌入的研究中可以尝试将流形学习的其他方法例如LLE,LE,MDS,ISOMAP等方法应用到表示学习。

[1] Roweis S T,  Saul L K.  Nonlinear  dimensionality  reduction  by  locally  linear embedding. Science, 2000, 290 (5500): 2323-2326.

[2] Seung H S, Lee D D. The manifold ways of perception. Science, 2000, 290 (5500): 2268-2269.

[3] TenenbaumJ.B , Silva V. de. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, pp. 2319--2323, 2000.

[4]Kruskal J B. Nonmetric multidimensional scaling: a numerical method. Psychometrika, 1964,29(2):115-129.

[5] Belkin M, Niyogi P, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp. 1373 –1396, 2003 . 

[6] Souleiman H,,Word Re-Embedding via Manifold Dimensionality Retention,Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP 2017) .

[7] Finkelstein L. 2001. Placing search in context: The concept revisited. In Proceedings of the 10th international conference on World Wide Web, pages 406–414. ACM.

[8] David Alvarez-Melis,Tommi S Jaakkola. Word embeddings as metric recovery in semantic spaces. Transactions of the Association for Computational Linguistics, 2016, 4:273–286.

[9] Jeffrey P, Richard S. Glove: Global vectors for word representation. In EMNLP(2014a),14: 1532–1543.

[10]Aur´ elien Bellet, Pascal Denis. Spectral Graph-Based Methods for Learning Word Embeddings, Transactions of the Association for Computational Linguistics, 20164:273–286

[11] Wei C, Luo SL,Discriminative locally document embedding: Learning a smooth affine map by approximation of the probabilistic generative structure of subspace,Knowle dge-Base d Systems,2017,121:41-57.

[12]Huh S,Discriminative Topic Modeling Based on Manifold Learning,ACM Transactions on Knowledge Discovery from Data (TKDD),2012,5(4):1-25.

[13]Tatsunori B. Hashimoto,David Alvarez-Melis.Word, graph and manifold embedding from Markov processes,arXiv :2015,1-13.