我们来看下prod2vec作者Mihajlo Grbovic†等人提出的HDV《Hierarchical Neural Language Models for Joint Representation of Streaming Documents and their Content》中提出的新方法:

介绍

考虑为数据流中的文档学习分布式表示的问题。文档(documents)被表示成低维向量,与word tokens的分布式向量,使用两个embedded神经语言模型的层次结构框架,通过联合学习得到。特别的,我们会利用在streams中的文档内容,并使用一个语言模型来建模文档序列,另一个模型则建模在它们中的词序列。该模型(the models复数)会为word tokens和documents学习两者的连续向量表示,以便语义相近的documents和words在同一向量空间中更接近。我们讨论了该模型的扩展,通过进一步添加user layers到该结构中,就可以被应用于个性化推荐、以及社交关系挖掘中,这样可以学到用户的向量来表示私人偏好。我们在公共电影评分数据集MovieLens和Yahoo News三个月数据集上进行了验证。结果表明,提出的模型可以学到文档和word tokens的有效表示,效果要好于当前state-of-art的方法一大截。

3.层次化语言模型

本节中,提出的算法会对streaming documents和在它内的words进行联合建模,其中学到的documents和words向量表示会在一个共享的、低维的embedding空间内。该方法受[14]的启发。然而,与[13]的不同之处是,我们会利用steaming documents中的时序邻居(temporal neighborhood)。特别的,我们会建模一个特定文档的概率,会考虑上时序上更接近(temporally-close)的文档,另外还会考虑文档内容。

3.1 模型结构

我们假设,训练文档会以序列形式给定。例如,如果该文档是新闻文章,那么document序列可以是:用户根据阅读时间按前后顺序排列的新闻文章序列。更特别的,我们会假设,设置S个document序列的集合,每个序列包含了个文档,。接着,在一个stream 中的每个文档是一个由个词组成的序列,。我们的目标是,在同一个向量空间中同时学习streaming documents和language words的低维表示,并将每个document和word表示成D维的连续特征向量。如果我们假设,在训练语料中存在M个唯一的文档(doc),以及在词汇表中存在W个唯一的词(words),那么在训练期间,我们的目标是学习个模型参数。

图1: hierarchical模型结构,有两个embedded神经语言模型(橙色:左:文档向量;绿色/右:词向量)

一个文档序列的上下文和自然语言上下文,会使用提出的HDV方法进行建模,其中documents向量不光只看成是预测周围documents的单元,同时也看成是在它之间包含的word序列的全局上下文。该结构包含了两个embedded layers,如图1所示。upper layer可以学到一个文档序列的时序上下文,基于假设:在文档流(document stream)中时序更接近的文档在统计学上相互依赖性更强。我们注意到,时序不需要指文档的创建时间,而是用户阅读文档的时间,在我们的实验中使用该定义。bottom layer会建模word序列的上下文信息。最后,我们采用paragraph vectors的思想,将这两个layer进行连接,并将每个文档token看成是在该文档内所有词的一个全局上下文。

更正式的,给定文档序列集合S,hierarchical模型的目标函数是:最大化streaming data的log似然:

…(8)

其中,是权重,它会在文档序列的log似然、以及词序列的log似然的最小化之间做一个权衡(在实验中会设置),b是文档序列的训练上下文长度,c是词序列的训练上下文长度。在该特定架构中,我们对于下面的setence layer使用cbow模型,对于上层的document layer使用skip-gram模型。然而,我们注意到,两个模型的任一个可以被用于该hierarchy的任意层上,具体选择取决于目前手头的问题形态。

给定如图1的架构,基于当前文档,观察到某一周围文档的概率,可以使用下面的softmax函数定义:

…(9)

其中是文档d的输入和输出向量表示。更进一步,观察到一个词的概率不仅依赖于周围的词,也依赖于该词所属的文档。更准确的,概率被定义成:

…(10)

其中,的输出向量表示,其中是该上下文(包含指定的文档)的平均向量表示,定义如下:

…(11)

最后,我们通过复用等式(10)和(11)来替换合适的变量,定义了以一个相同方式在

3.2 模型变种

前面提到了一个典型结构,其中我们指定了在hirerachy上每一层的语言模型。然而,在真实应用中,我们会以一种更简单的方式来为不同目的区分语言模型。例如,一个新闻网站可能会对预测即时性感兴趣,即:对于个性化新闻信息流,一个用户在点击了一些其它新闻故事后接下去会阅读什么。接着,它可以使用直接的前馈模型来估计,即:给定了它的b个之前文档,在序列中第个文档的概率。或者,相同的,如果我们想建模哪个文档会在读取前面序列后被读取,我们可以使用前馈模型:它可以估计,它是给定前b个文档的第m个文档的概率。

另外,很方便扩展该描述,但也很容易具有超过两个layers。假设我们具有一个streaming documents的数据集,它面向一个不同的用户集合(例如:对每个文档我们希望知道哪个用户生成或阅读了该文档)。接着,我们可以构建更复杂的模型, 通过在document layer的顶部添加user layer来同时学习用户的分布式表示。在该setup中,一个用户向量可以看成是指定用户的steaming documents的一个全局上下文, 一个文档向量则看成是指定文档的words的一个全局上下文。更特殊的,我们可以预测一个文档,它基于周围文档和它的内容来预测一个文档,同时也只对某一指定用户。该变种模型,其中u是对于某一用户的一个指示变量。对于提升个性化服务来说,学习用户的向量表示是一个开放问题,其中个性化会降维到:在联合embedding空间中的最简单的最近邻搜索。

3.3 模型最优化

该模型使用SGA(随机梯度上升法),很适合大规模问题。然而,在(8)中的梯度的计算 与词汇size W成比例,梯度与训练的文档数M成比例。这在实例上很昂贵,因为W和M两者都可以很容易达到上百万的规模。

我们使用的一种有效替换方法是,hirarchical softmax,它可以将时间复杂度减小到,其中R是在文档序列中的总词汇数。为了计算等式(9)和等式(10)中的求和,我们并不用在每次梯度step期间评估每个不同词或文档,hirarchical softmax会使用两个二叉树,一棵树将不同文档作为叶子,另一棵树将不同的词作为叶子。对于每个叶子节点,从该根节点出发的路径(path)会有一个唯一分配,它使用二进制数字进行编码。为了构建一个树结构,通常用使用Huffman编码,其中,在数据集中更常见的文档(或词)会具有更短的编码。更准确的,hierarchical softmax表示在该序列中当前文档(或词)被观察到的概率,它作不二叉树的概率积,通过文档的Huffman编码如下:

…(12)

其中是编码中第l位的码,对应于,它是指定树路径中的第l个节点。每个二叉树的概率定义如下:

…(13)

其中是sigmoid函数,是节点的向量表示。它可以通过进行验证,因而概率分布的属性会被保留。我们可以以同样的方式计算。更进一步,我们相似地表示,但独立的Huffman树的构建会与词有关。

参考

我们来看下Bryan Perozzi的

1.介绍

网络表示的稀疏性,即是它的强项,也是它的弱项。稀疏性允许设计一些很有效的分立算法,但使它很难泛化到统计学习(statistical learning)中。在网络机器学习应用中(比如:网络分类、内容推荐、异常检测、缺失环节预测missing link prediction等),必须能处理这种稀疏性。

本文引入了deep learning(非监督特征学习)技术来进行网络分析,DL已经在NLP上取得了成功。我们开发了一个算法(DeepWalk),它会通过建模一个关于短随机游走(short random walk)的流(stream),会学到一个关于图顶点(graph vertices)的社群表示(social representations)。社群表示是顶点的隐特征,它可以捕获相邻顶点间的相似度和社群关系。这些隐表示(latent representation)可以把社交关系使用相对少量的维度编码在连续特征空间中。DeepWalk可以看成是会将自然语言模型泛化来处理一个特殊的语言:它由一个随机生成的walk集合组成。这些自然语言模型被用于捕获人类语言中的语法和语义结构、以及逻辑类比。

图1

DeepWalk会将一个图作为输入,并生成一个隐表示作为它的输出。将我们的方法应用于Karate network上,结果如图1所示。图1a通过力导向(force-directed)的布局进行表示,图1b展示了我们使用2个隐维度的方法。除了显著的相似性外,我们注意到1b中线性可分的部分,对应于通过输入图1a的模块最大化(modularity maximization)的聚类(clusters): 通过顶点颜色区分。

为了演示DeepWalk在真实世界场景中的潜力,我们在多标签网络分类问题上评估了它的效果。在关系分类(relational classification)问题上,特征向量间的连结(links)与传统的独立同分布(i.i.d)假设冲突。解决该问题的技术通常使用近似推断技术(approximate inference )通过增加依赖信息来提升分类结果。我们通过增加图表示(representations of the graph)的标签独立性(label-independent)来解决。我们的表示(representation)质量不会因labeled vertices的选择而受影响,因而它们可以在任务间共享。

DeepWalk比其它用于创建社交维度(social dimension)隐表示方法要好,尤其是当labeled nodes很稀少时。我们的表示法的性能可能与最简单的分类器(LR)相当。我们的表示是可泛化的,可以结合任何分类方法(包含迭代型推断法)。DeepWalk可以完成上述所有,它是一个在线算法,可并行化。

本paper贡献:

  • 引入深度学习作为一个工具来分析图,来构建健壮的表示,很适合于统计建模。DeepWalk会学到在短随机游走(short random walks)内表示的结构化规律。
  • 我们对多个社交网络上使用我们的表示法,并在多标签分类上进行评估。我们发现可以极大提升存在标签稀疏性情况的分类效果,在Micro F1上可以提升5%-10%。在一些case中,即使只给了更少的60%的数据,DeepWalk的表示也可以胜出其它对手。
  • 我们展示了我们的算法的可扩展性,使用一个并行实现去构建web-scale图(比如:Youtube)的表示。另外,我们描述了小的变种,来构建一个流版本(streaming version)。

本paper的其余部分如下安排。在第2-3节,描述了在数据网络中的分类问题,以及如何与我们的工作相结合。在第4节,我们描述了DeepWalk算法。第5、6节描述实验以及实验结果。等

2.问题定义

问题:对一个社交网络的成员进行分类,分成成一或多个类(categories)。

更正式地表示:G=(V, E),其中V是网络的成员,E是它们的边,。给定一个部分标记的社交网络,属性, 其中S是每个属性向量的特征空间size,,其中是labels的集合。

在传统的机器学习分类设定中,我们的目标是学习一个假设函数H,它会将元素X映射到标签集合上。在我们的case中,我们可以利用关于样本依赖的显著信息,嵌入到G的结构中来完成更好的效果。

在学术上,这被称为是关系分类(relational classification)或者称为协作分类(collective classification)。关系分类的传统方法将该问题看成是在一个无向马尔可夫网络上做推断,接着使用迭代近似推断算法(比如:迭代型分类算法,Gibbs Sampling,或者 标记松弛法label relaxation)来计算给定网络结构下的标签后验分布。

我们提出了一个不同的方法来捕获网络拓朴信息。这种方法不再使用将标签空间进行混合作为特征空间的一部分,而是提出了一种无监督的方法,可以学到这样的特征:它能捕获与标签分布相独立的图结构。

结构化表示与标记任务间的分隔,可以避免重复错误,这常在迭代型方法中出现。另外,相同的表示可以被用于网络的多分类问题。

我们的目标是,学习,其中,d是隐维度(latent dimensions)是最小数目。这些低维度表示是distributed式表示的; 这意味着每个社交现象(social phenomena)可以通过维度的某个子集进行表示,每个维度只会对通该空间表示的社交概率的某个子集做出贡献。

使用这些结构化特征,我们可以增大属性空间来帮助分类决策。这些特征是通用的,可以被用于任何分类算法(包括迭代型方法)。然而,我们相信,这些特征的最大作用是,它们很容易与简单的机器学习算法集成。它们可以很适合地在现实网络中扩展,在第6节会介绍。

3.学习社交表示

我们使用以下的特征来探索社交表示学习(learning social representations):

  • 适配性(Adaptability):真实社交网络是不断演进的;新的社交关系不需要再次所有重复学习过程。
  • 社群意识(Community aware):隐维度间的距离可以作为评估网络成员的社交相似性的一个metric。这允许泛化到同质的网络中。
  • 低维(Low dimensional):当标记数据很少时,低维模型泛化更好,加速收敛和推断。
  • 连续(Continuous):我们需要隐表示来建模在连续空间中的部分社群成员关系(community membership)。除了提供一个关于社群关系的细微视图外,连续表示法具有在社群间的平滑决策边界,这可以允许更健壮的分类。

我们的方法满足这些需求,从一个短随机游走流中,使用语言建模上的优化技术来为顶点学到表示。这里,我们会复习下随机游走和语言建模,并描述两者如何结合来满足我们的需要。

3.1 随机游走

一个根顶点的随机游走的定义为:。它是一个随机过程,具有随机变量:是从顶点的邻节点上随机选中的顶点。随机游走已经被用于在内容推荐和社群发现领域的多个问题上作为一个相似度衡量方法。他们也是输出敏感算法(output sensitive algorithms)大类的基础,使用它们来及时计算局部社群结构信息,与输入图的size成次线性关系(sublinear)。

这种局部结构的连接特性,启发我们来使用一个短随机游走作为我们的基础工具来从一个网络中抽取信息。除了捕获社群信息外,在我们的算法中使用随机游走作为基础,能给我们带来其它两个特性。

  • 1.局部探索(local exploration)很容易并行化。多个随机游走者(random walkers)以不同线程、进程、机器可以并行探索同一个graph下的不同部分。
  • 2.依靠从短随机游走上获取信息,可以使它更能适应在图结构上的小变动,无需进行全局重新计算。我们可以迭代式地更新学到的模型,从变动区域上使用新的随机游走,它对整个graph是在时间上是次线性的。

3.2 连接:二八法则(power law)

已经选择在线随机游走作为我们的基础来捕获图结构,我们现在需要一个更适合的方法来捕获这种信息。如果一个连接图的度分布(degree distribution)遵循一个power law(scale-free),我们会观察到,出现在短随机游走上的哪个顶点的频次也是遵循power-law分布的。

图2

在自然语言中,词频会遵循一个相似的分布,其中,语言建模领域的技术可以对该分布行为作出解释。为了强调该相似性,如图2所示,我们展示了两个不同的power-law分布。第1个图来自在一个scale-free的graph上进行一系列短随机游走,第2个图来自关于英文wikipedia的10w篇文章的文本。

我们的工作的一个核心贡献是,用于建模自然语言的技术(其中,符号频次遵循power-low分布)可以被用于建模在网络中的社群结构。该节剩余部分将讨论语言建模,并将它迁移到我们的case中来学习顶点表示。

3.3 语言建模

语言建模的目标是,在语料中出现的一个指定词序列的似然。更正式地,给定一个词序列:

其中,(V是词汇表),我们想最大化在所有训练语料上的

在表征学习上的最近工作,主要使用概率神经网络来构建词的通用表示,可以扩展到语言建模范围之外。

在本paper中,我们使用一个语言建模的泛化版本、结合短随机游走的一个流(stream)来探索图。这些游走可以被认为是在一个特殊语言中的短句、短段落。直接类比是,给定在随机游走中所有访问过的前节点,估计观察顶点的似然。

我们的目标是学习一个隐表示,它不仅仅是节点共现的一个概率分布,而且我们引入了一个映射函数 。该映射函数表示与在图中每个顶点v相关的隐社交表示。(实际上,我们通过一个的自由参数矩阵来表示,它可以在之后作为我们的服务)。接着该问题是,估计以下似然:

…(1)

然而,随机游走长度的增长,计算该目标函数会变得不可行。

在自然语言中的最近实验是,开始转变预测问题。首先,它不同使用上下文来预测一个缺失的词(word),而是使用一个词来预测它的上下文。第二,上下文由给定词的右侧和左侧组成。最后,它在该问题上会移除顺序限制。作为替代,该模型需要最大化出现在该上下文中的任何词的概率,无需知道与给定词间的偏移。

用顶点表示建模的优化问题,如下:

…(2)

我们发现这些条件放宽,特别适合于社交表征学习。首先,顺序无关性假设可以更好捕获由随机游走提供的“邻近度(nearness)”。另外,该relaxation通过一次只为一个顶点构建小模型对于加速训练时间相当有用。

对等式(2)的优化问题进行求解来构建表示,可以捕获在顶点间的局部图结构的共享相似度。具有相同邻节点的顶点可以获取相似的表征(encoding cocitation similarity),允许在机器学习任务上进行泛化。

通过组合截短的随机游走和自然语言建模,我们会对该方法公式化,它可以满足所有我们期待的特性。该方法可以生成社交网络的表征,具有低维、连续空间的特性。它的表示会对社群的隐形式进行编码,因为该方法会输出有用的中间表征,可以用来更改网络拓朴。

4.方法

在本节中,我们讨论算法的主要构成。

4.1 总览

在任何语言建模算法中,只需要一个语料和词汇表V。DeepWalk会考虑短截断的随机游走的一个集合作为它的语料,图顶点作为它的词汇表()。其中,它有利于知道在训练之前的随机游走上顶点的词频表V和频次分布。

4.2 算法:DeepWalk

该算法包含了两个主要部分:

  • 1.随机游走生成器
  • 2.一个更新过程

随机游走生成器会使用一个图G,并且均匀地抽样出一个随机顶点作为随机游走的根节点(root)。一个游走会均匀从最后访问的顶点的邻节点进行抽样,直到到达最大长度(t)。在我们的实验中,随机游走的长度设置是固定的,但是对于随机游走来说没有限制一定要用相同长度。这些游走会重启(restart)(例如:一个传送点(teleport)的概率会返回到它的root),但我们的初步结构不会展示使用重启(restarts)的任何优点。实际上,我们的实现指定了在每个顶点上进行随机游走的数目()和长度(t)。

算法一

在算法1中的3-9展示了我们算法的核心。外层的循环指定了次数,,即我们在每个顶点上启动随机游走的数目。我们认为每个迭代会生成一个对数据的”通路(pass)”,并在该pass期间为每个节点抽样一个walk。在每个pass的开头,我们生成了一个随机顺序来遍历这些顶点。这不是必需的,但可以加速随机梯度下降(SGD)的收敛。

在内层循环中,我们会迭代图的所有顶点。对于每个顶点,我们会生成一个随机游走 ,接着使用它来更新我们的表征represntations(第7行)。我们使用SkipGram算法来更新这些表征,以适应在等式2中的目标函数。

4.2.1 SkipGram

SkipGram是一个语言模型,在一个句子中,它会最大化在同一窗口w中词之间的共现率。

图3: 补充

算法2会迭代在窗口w内出现的随机游走中的所有可能排列(collocations)(第1-2行)。for-each操作中,我们会将每个顶点映射到它的当前表征向量中(见图3b)。给定的表示,我们可以最大化在该walk中的邻节点的概率(第3行)。我们可以有多种分类器选择来学到在walk中这样的后验分布。例如,使用LR建模前面的问题,可以生成一个海量的标签(上百万或数十亿),它等于词汇表数。这样的模型需要大量计算资源,可能会占用整个计算集群。为了加速训练时间,可以使用Hierarchical Softmax来近似概率分布。

算法2

4.2.2 Hierarchical Softmax

给定,计算第3行中是不可行的。计算分区函数(正归化因子)很昂贵。如果我们将顶点设计成一棵二叉树的叶子节点,预测问题就转化成了最大化在树中一条指定路径上的概率(见图3c)。如果到顶点的路径通过一个树节点序列表示,其中:,那么:

现在,可以通过一个二分类器进行建模,该值被分配给节点的父节点。这可以减少计算的计算复杂度:从

我们可以进一步加速训练过程,通过分配更短的路径给在随机游走中的频繁顶点。Huffman编码常用于减小在树中频繁顶点的访问次数。

4.2.3 最优化

模型参数集是,其中每个的size都是。随机梯度下降(SGD)被用于最优化这些参数(算法2第4行)。导数的估计使用BP算法。SGD的learning rate 在训练开始处初始化设置为2.5%,接着随着见过的顶点数进行线性递减。

4.3 并行化(Parallelizability)

如图2所示,在社交网络上的随机游走中,顶点的频率分布与语言中的字分布遵循power law。这会产生一个关于不频繁顶点的长尾,因此,对有影响的更新在本质上很稀疏。这允许我们使用并行版本的ASGD(asynchronous version of stochastic gradient descent),在多个worker上。假定:我们的更新是稀疏的,我们不需要一个锁来访问模型的共享参数,那么ASGD将会达到一个收敛的最优rate。其中我们在单机上使用多线程进行实验,它可以演示这种技术是高度可扩展的,可以用于大规模机器学习上。图4展示了并行的DeepWalk。它展示了处理BLOGCATELOG和Flickr网络的加速与我们增加workers数是一致的(图4a)。也展示了相对于顺序版本的DeepWalk,预测效果并没有损失(图4b)。

图4

4.4 算法变种

我们提出的方法还有一些变种。可能是你感兴趣的。

4.4.1 Streaming

其中一个有意思的变种是streaming方法,它没需知道整个graph就可以实现。在该变种中,从一个图出发的小游走,直接传到表示学习编码上,模型是直接更新的。该学习过程的一些修改是必须的。首先,使用一个衰减的learning rate不再可能。相反地,我们会初始化learning rate ,我们不必构建一个参数树。如果V的基数是已经的(可以限定),我们可以构建Hierachical Softmax tree来最大化值。当顶点被首先看到时,它们会被被分配给余下叶子之一。如果我们能估计顶点频率的一个先验,我们也可以仍使用Huffman编码来减小频繁节点的访问次数。

4.4.2 非随机游走

一些图是作为一系列元素行为的一个副产品被创建的。(例如:用户在一个网站上的导航)。当一个图通过这样的非随机游走方式创起家时,我们可以使用该过程来直接feed该建模阶段。以这种方式抽样的图不仅能捕获与网络结构相关的信息,也能捕获在该路径进行反向的频率。

我们认为,该变种也包括语言建模问题。句子可以看成是通过一个合理设计的语言网络上的一些特定游走,像SkipGram的语言模型可以被设计用来捕获这种行为。

该方法可以结合streaming变种来在连续演化网络上训练特征,无需显式构建整个网络。使用该技术维护表示,可以允许web-scale分类,无需处理一个web-scale规模的graph。

5.实验设计

略.

YouTube是一个社交网络,用户共享流行的视频。这里的labels表示viewers的群组,它们喜欢相同的视频类目(比如:动作 和 摔跤)

6.实验

6.1.3 YouTube

详见paper.

参考

DeepWalk: Online Learning of Social Representations

1.介绍

对于词(words)的分布式组成语义的算法开发是一个长期存在的开放性难题。最近几年的算法有:将word vectors映射到sentence vectors(包括recursive networks, recurrent networks, convolutional networks,以及recursive-convolutional方法)。所有的这些方法会生成句子表示,传给一个监督式任务,依赖一个class label来对组成权重(composition weights)做BP算法。因而,这些方法能学到高质量句子表示,但只能对自己的特定任务进行调整。paragraph vector是另一种方法,它通过引入一个分布式句子索引作为模型的一部分,以非监督式学习进行句子表示。

本文中,我们考虑了另一种loss function,可以用于任何组成操作(composition operator)上。考虑以下的问题:是否存在一个任务,它对应的loss允许我们学习高度泛化的句子表示?受使用word vector学习的启发,我们提出了一个目标函数,它从句子级别上抽象了skip-gram模型。也就是说,它不再使用单个word来预测它的上下文,我们会encode一个句子。因而,任何组成操作(composition operator)都适用于一个句子编码器(sentence encoder),只是目标函数被修改了而已。图1展示了该模型,我们会调用我们的skip-thoughts模型和向量。

图1: skip-thoughts模型。给定一个tuple(),表示book中的第i个句子,被编码并尝试重构前一个句子和下一个句子。在本例中,输入的句子三元组:I got back home. I could see the cat on the steps. This was strange. 未绑定箭头被连接到encoder output上。颜色表示哪个component共享参数。(与skip-gram有点像)

表1: BookCorpus dataset的统计信息

我们的模型依赖于一个关于连续文本的训练语料。我们选择使用一个小说集合BookCorpus dataset来训练我们的模型。这些书由未出版的作者编写。该dataset具有6种不同的种类:Romance, Fantasy, Science fiction , Teen等。表1高亮了该语料的统计。伴随着故事,书包含着对话,感情(emotion)和广泛的字符交叉。另外,训练集的量很大,不会偏向于任何特定领域或应用。表2展示了该语料中句子的最近邻。该结果展示了skip-thought vectors精确地捕获了编码后的句子的语义和结构。

表2: 在每个样本中,第一个句子是一个query,而第二个句子是它的最近邻。通过从语料中随机抽取5w个句子中,通过计算cosine相似度进行最近邻分数排序。

我们以新的setting评估了我们的向量:在学到skip-thoughts后,冻结模型,使用encoder作为一个泛化的特征抽取器(generic feature extractor)以用于特定任务。在我们的实验中,我们考虑了8个任务:句义相关性,段落检测,图像句子排序以及其它5个标准的分类benchmarks。在这些实验中,我们抽取了skip-thought向量,并训练了线性模型来评估它的表示(representations),没有任何额外的参数fine-tuning。结果说明,skip-thoughts提出的泛化表示对所有任务都很robust。

一个难点是,这样的实验会构建一个足够大的词汇表来编码句子。例如,一个从wikipedia文章中的句子可能包含了与我们的词汇表高度不一样的名词。为了解决这个问题,我们学到了一个mapping:从一个模型传递给另一个模型。通过使用cbow模型预训练好的word2vec表示,我们学到了这样的一个线性映射:将在word2vec空间中的一个词映射到encoder词汇表空间中的一个词上。学到的该mapping会使用所有单词,它们共享相同的词汇表。在训练后,出现在word2vec中的任何word,可以在encoder word embedding空间中获得一个vector。

2.方法

2.1 引入skip-ghought vectors

我们使用encoder-decoder模型框架来对待skip-thoughts。也就是说,一个encoder会将words映射到一个句子向量(sentence vector)上,一个decoder会用于生成周围的句子。在该setting中,一个encoder被用于将一个英文句子映射到一个向量。decoder接着根据该向量来生成一个关于源英文句子(source sentence)的翻译(translation)。已经探索了许多encoder-decoder pair选择,包括:ConvNet-RNN,RNN-RNN,LSTM-LSTM。源句子表示(source sentence representation)也可以通过使用一个attention机制来动态变化,用于说明任何时候只有相关的才用于翻译(translation)。在我们的模型中,我们使用一个带GRU activations的RNN encoder,以及一个conditional GRU的RNN decoder。该模型组合近似等同于神经机器翻译中的RNN encoder-decoder【11】。GRU展示了在序列建模任务中效果比LSTM要好,并且更简单。GRU units只有两个gates,不需要使用一个cell。而我们的模型则使用RNN,只要能在它之上进行BP算法,任何encoder和decoder可以被使用。

假设我们给定了一个句子的tuple:。假设表示了句子中的第t个word,表示它的word embedding。我们将模型描述成三部分:encoder,decoder,目标函数。

Encoder:假设是句子中的words,其中N表示在句子中的words数目。在每个step中,encoder会产生一个hidden state:,它可以解释成序列的表示(representation)。hidden state:可以表示整个句子。

为了encode一个句子,我们对下面的等式进行迭代(这里去掉了下标i):

… (1)

… (2)

… (3)

…(4)

其中 是在时间t提出的状态更新,是update gate,是reset gate()表示一个component-wise product。两个update gates会采用0到1间的值。

Decoder: decoder是一个神经语言模型,它的条件是encoder output 。该计算与encoder相似,除了我们引入了矩阵,以及C,它们被用于偏置由句子向量计算得到的update gate,reset gate和hidden state。一个decoder会被用于下一个句子,而第二个decoder被用于前一句子。Separate参数被用于每个decoder,除了词汇矩阵V,它的权重矩阵会连接decoder的hidden state,以便计算在词上的一个分布。我们在下一个句子上描述decoder,通过一个在前一句子上的类似计算得到。假设表示decoder在时间t的hidden state。对下面的等式进行迭代(丢掉下标i+1):

…(5)

…(6)

…(7)

…(8)

给定,单词的概率给出了前(t-1) words,encoder vector为:

…(9)

其中,表示V的行,对应于word 。对于前面句子可以做一个类似的计算。

目标函数。给定一个tuple ,目标优化为:

…(10)

总的目标函数是对所有这样的training tuples进行求和。

2.2 词汇表膨胀

现在,我们会描述如何将我们的encoder的词汇表扩展到那些在训练期间未见过的词上。假设我们有个被训练的模型引入了词表示(word representations),假设表示了RNN的词向量空间。我们假设词汇表更大。我们的目标是构建一个mapping f: ,它由一个矩阵W进行参数化,比如:,其中。受[15]的启发,它会学到在词空间转移之间的线性映射,我们为矩阵W求解一个非正则的L2线性回归loss。这样,对于编码中的句子,任何来自的词可以被映射到

3 实验

在我们的实验中,我们在BookCorpus dataset上评估了我们的encoder作为一个通用的feature extractor的性能。实验setup如下:

  • 使用学到的encoder作为一个feature extractor,抽取所有句子的skip-thought vectors
  • 如果该任务涉及到计算句子对(pairs of sentences)之间的分数,会计算pairs间的component-wise features。
  • 在抽取的features上训练一个线性分类器,在skip-thoughts模型中没有任何额外的fine-tuning或者backpropagation。

我们限定在线性分类器主要出于两个原因。第一个是为了直接评估计算向量的representation quality。如果使用非线性模型可能会获得额外的性能增益,但这超出了我们的目标。再者,它可以允许更好地分析学到的representations的优点和缺点。第二个原因是,重现(reproducibility)很简单。

3.1 训练细节

为了引入skip-thought vectors,我们在我们的book corpus上训练了两个独立的模型。一个是带有2400维的unidirectional encoder,它常被称为uni-skip。另一个是一个bidirectional model,forward和backward每个各1200维。该模型包含了两个encoder,它们具有不同的参数:一个encoder会给出正确顺序的句子,另一个会给出逆序的句子。输出接着被拼接形成一个2400维的向量。我们将该模型称为bi-skip。对于训练,我们会初始化所有的recurrent矩阵:进行正交初始化。non-recurrent weights则从一个[-0.1, 0.1]的均匀分布上进行初始化。使用mini-batches的size=128, 如果参数向量的norm超过10, 梯度会被裁减(clip)。我们使用Adam算法进行optimization。模型会被训练两周。另外作为一个额外的试验,我们使用一个组合模型导出了试验结果,包含了uni-skip和bi-skip,会生成4800维的向量。我们称该模型为combine-skip。

在被模型被训练后,我们接着使用词汇扩展,将word embedding映射到RNN encoder空间上。会使用公开提供的CBOW word vectors[2]。被训练的skip-thought会有一个词汇size=20000个词。在从CBOW模型中移除多个word样本后,会产生一个词汇size=930911个词。这样,即使被训练的skip-thoughts模型具有20000个词,在词汇表扩展后,我们可以对930991个可能的词进行成功编码。

由于我们的目标是将skip-thoughts作为一个通用的feature extractor进行评估,我们将文本预处理保持最低水平。当编码新句子时,除了基本的tokenization,不会有额外的预处理。这样做可以测试我们的vectors的健壮性。作为一个额外的baseline,我们也会考虑来自uni-skip模型学到的word vectors的平均(mean)。我们将该baseline称为bow。这会决定着在BookCorpus上训练的标准baseline的效果。

3.2 语义相关性

3.3 段落检测

3.4 Image-sentence ranking

3.5 Classification benchmarks

3.6 skip-thoughts可视化

t-sne.

参考

Convolutional Neural Networks for Sentence Classification

我们来看下yahoo的《Product Recommendations at Scale》中提出的prod2vec方法:

1.介绍

世界上许多人在每天都会浏览email收件箱,大多数时间会与它们的通讯录进行联系,还有一部分时间用于账单确认,读取新信息,以及跟踪购买( tracking purchases)。为了对这种流量进行商业化,email客户端通常会在原生email内容的边上以图片的形式展示广告。说服用户切出”email模式”(即连续处理邮件任务),进入一个新模式让人们愿意去点广告是个挑战。通过有效的个性化和定向(targeting),目标是为单个用户发现与他最匹配的广告展示给他,因而广告需要高度相关,以克服用户只关注email任务的倾向。除了获得财务收益外,为每个消费者的口味量身定制的广告也能改善用户体验,可以增加用户的忠诚度和用户粘性。

对于广告定向(ad targeting),收件箱emails仍未被充分进行explored & exploited。最新研究表明,只有10%的收件量表示是人类生成(非机器生成)的emails。这之外的90%流量中,超过22%表示与在线电商有关。假设整体流量中大部分是有商业目的的,定向广告的一种流行形式是电邮重定位(MRT: mail retargeting),其中,广告主会对之前从特定商业网站(web domain)上接收过邮件的用户进行定向。这些电子邮件对于广告定向来说很重要,它们会给出用户感兴趣的相应商品的一个大图(broad picture)进行展示。最新paper[14]利用聚类方法来生成MRT规则,展示了这样的规则比由人类专家生成的要更精准。

图一:Yahoo Mail中的商品推荐

然而,为了超出MRT规则之外,用户和商业网站的交互,广告商需要更多数据(比如:购买过的商品名和价格,通常是email邮件的一部分)。email客户端与商业网络能很好结合,对电子邮件格式进行标准化,产生的schemas通过schema.org社区进行维护。越来越多的商业网站使用标准schemas,email客户端可以提供更个性化的用户通知,比如:包裹跟踪(package tracking)和 航班详情(flight details)。另外,email receipt extraction带来了赚钱机会,基于客户的购买历史将商品广告带给用户。有了从多个商业email domain上的购买数据,比起其它基于单一商业email domain来说,可以更好地将email provider放置到在唯一的位置上,以便能构建更好的推荐系统。特别的,不同于商业网站可以做出这样的推荐:“买了X的顾客,也会买Y”,email providers可以做出这样的推荐:“从生产商V1处购买了X的顾客,也会从生产商V2处购买Y”,允许更强大和更有效的定向解决方案。

在本paper中,我们为Yahoo Mail提供了一种end-to-end的商品广告开发方案。工作包含了开发一个商品级别的购买预测算法,能扩展到数百万的用户和商品。出于该目的,我们提出了一种方法,使用一个神经语言模型,将它应用到用户购买时间序列上,从而将商品嵌入到real-valued,低维的向量空间中。作为结果,具有相近上下文的商品(它们相邻近的购买行为)可以映射到在embedding空间中更接近的地方。关于下一个要购买的商品,为了做出有意义和更多样的建议,我们会进一步将商品向量进行聚类,并建模聚类间的转移概率。来自可能的聚类在向量空间中更接近的商品,会被用于形成最终推荐。

商品预测模型会使用一个大规模的购买数据集进行训练,由2900w用户的2.8亿购买行为组成,涉及210w个唯一的商品。该模型会在一个held-out month上进行评估,其中,我们在收益率(yield rate)上测试了推荐的有效性。另外,我们会评估一些baseline方法,包含展示流行商品给所有用户,以不同用户分组(称为:分群(cohorts),由用户性别、年龄、地域)展示流行商品,以及展示在一个用户最近购买商品之后历史最常购买的商品。为了减轻冷启动问题,在用户的分群(cohort)中的流行商品会被用于补足那些早期没有购买行为的用户的推荐。

3.方法

本节中,我们描述了该商品推荐任务的方法论。为了解决该任务,我们提出了从历史日志中使用自然语言模型学习在低维空间中的表示。商品推荐可以通过最简单的最近邻搜索得到。

更特别的,给定从N个用户中获取的email receipt日志的一个集合S,其中用户的日志为 被定义成一个关于M个receipts的连续序列,每个email recept 包含了个购买的商品,我们的目标是发现每个商品p的D维实数表示,以便相似的商品可以在向量空间中更近的位置。

我们提供了一些方法来学习商品表示。首先提出了prod2vec方法,它会考虑所有已经购买的商品。接着提出了新的bagged-prod2vec方法,它会考虑在email receipts中一起罗列被购买的一些商品,它们会产生更好、更有用的商品表示。最终,我们会利用上学到的representations来分别表示一个prod2prod和user2prod的推荐模型。

3.1 低维商品embeddings

图二:prod2vec skip-gram模型

prod2vec:prod2vec模型会将一个购买序列看成是一个“句子”,在这个序列中的商品看成是“词”。详见图2, 更特殊的,prod2vec使用skip-gram模型来学习商品表示,通过以下的最大化目标函数:

…(3.1)

其中,来自相同email receipt的商品可以是任意顺序。概率表示:给定当前商品,观察到一个邻近商品的概率,使用softmax函数进行定义如下:

…(3.2)

其中,。。。。

图3: bagged-prod2vec模型更新

bagged-prod2vec:为了对多个商品同时购买的行为做出解释,我们提出了一个修改版本的skip-gram模型,它引入了一个概念:购物袋(shopping bag)。如图3所示,该模型会在email receipts级别进行操作,而非在商品级别。通过对email序列s上的一个修改版目标函数进行最大化,来学习商品向量表示:

…(3.3)

商品是从邻近的email receipt 上观察到商品的概率,,给定从第m个email receipt的第k-th个商品,到一个商品的概率:

每个P的定义使用softmax(3.2)。注意在(3.3)中的第三个求和会随着receipts进行,因而,从相同的email receipt中得到的items在训练期间不会相互预测。另外,为了捕获商品购买的时序特性(temporal aspects),我们提出了使用有向语言模型,我们只使用未来的商品(future product)作为上下文。该修改版允许我们学习商品embeddings来预测将来的购买行为。

learning:该模型使用SGA( stochastic gradient ascent)进行最优化,很适合大规模问题。然而,在(3.1)和(3.3)中的梯度计算,很适合词汇size P,实际任务中,计算开销会随着P的增大而变得很昂贵,很容易达到上百万的商品。另一方面,我们使用negative sampling方法,它能显著减小计算复杂度。

3.2 prod-2-prod预测模型

在学习了低维商品表示后,我们考虑了来预测下一商品的购买概率的一些方法。

prod2vec-topK:给定一个购买商品,该方法会为所有在词汇表中的商品计算cosine相似度,并推荐最相似商品的top K

prod2vec-cluster:为了能做出更多样化(diverse)的推荐,我们考虑将相似商品分组成聚类,从与之前购买商品相关的聚类中推荐商品。我们应用K-means聚类算法来在hadoop FS上实现,将商品基于cosine相似度进行聚类。我们假设:在从聚类上进行一个购买后、再从任意第C个聚类中进行一次购买的行为,符合一个多项式分布(multinomial distribution),其中是从聚类中进行一次购买后、接着从聚类中进行一次购买的概率。为了估计参数,对于每个i和j,我们采用一个最大似然方法:

…(3.4)

  • count of ci purchases: c_i购买的数目
  • # of times ci purchase was followed by cj: c_i购买后跟c_j的次数

为了给一个购买过的商品p推荐一个新商品,我们首先标识了p属于哪个聚类(例如: )。接着,我们会对所有聚类,通过值进行排序,然后考虑取与聚类top相关的聚类中的top个商品。最后,从top聚类中的商品通过与p计算cosine相似度进行重排序,取top K进行推荐。

3.3 User-to-product预测模型

除了prod2prod预测外,大多数推荐引擎允许user-to-product方式的预测,为一个用户进行推荐通常会考虑历史购买、或(和)兴趣,使用其它数据源:用户在线行为、社交行为等。在本节中,我们提出了一个新方法来同时学习商品的向量表示、以及给定一个用户,发现在joint embedding space发现K个最近商品的用户推荐。

user2vec:受paragraph2vec算法的启发,user2vec模型会同时学习商品和用户的特征表示,它会将用户当成是一个“全局上下文”。这样的模型如图4所示。训练数据集来自于用户购买序列S,它会包含和其它已购商品(通过购买时间序排列),,其中表示用户购买的items数目。在训练期间,用户向量会被更新,来预测从他的email receipts中的商品,其中,学到的product vectors会预测在上下文中的其它商品。出于表示的简洁性,在下面,我们会表示no-bagged版本的模型,注意,使用bagged版本进行扩展也很方便。

图4: 对用户的User embeddings,进行产品预测

更特殊的,user2vec的目标函数是,最大化所有购买序列的集合S上的似然:

…(3.5)

其中,c是第n个用户的购买序列上下文长度。被定义为使用一个softmax函数:

…(3.6)

其中的输出向量表示,是商品上下文的平均向量表示,包含了相应的,定义如下:

…(3.7)

其中,是p的输入向量表示。相似的,概率定义如下:

…(3.8)

其中的输出向量表示,是用户的所有商品平均输入向量表示的平均:

…(3.9)

user2vec模型的一个主要优点是,商品推荐是基于该用户的购买历史进行量身定制的。然而,缺点是,该需要需要非常频繁地进行更新,不同于product-to-product方法,它可以长期是相关的,而user-to-product推荐需要经常变化来对最近购买行为做出解释。

4.实验及其它

略,详见paper.

4.4 推荐预测商品

我们对推荐商品给用户进行实验,比较以下算法:

  • 1) prod2vec-topK:使用数据集进行训练,其中,商品向量通过对购买序列s通过极大似然估计进行学习。给定一个商品,通过向量空间计算cosine相似度选择topK个相似商品。
  • 2) bagged-prod2vec-topK:使用进行训练,其中商品向量通过email序列s通过极大似然估计进行学习。对于给定商品,通过选择在结合向量空间计算cosine相似度选择topK个相似商品。
  • 3) bagged-prod2vec-cluster: 与bagged-prod2vec模型的训练类似,接着将商品向量聚类成C个聚类,并计算它们间的转移概率。接着标识出属于哪个聚类(例如:),我们根据的转移概率对各聚类进行排序,取出top个聚类,然后聚出这些top聚类的商品通过计算与的cosine相似度进行排序,其中每个聚类的top 被用于推荐()。 bagged-prod2vec-cluster与 bagged-prod2vec的预测结果如表2所示。可以看到聚类方法多样性更好。
  • 4) user2vec:使用进行训练,其中商品向量和用户向量通过极大似然估计进行学习。给定一个用户,通过计算用户向量与所有商品向量的cosine相似度,检索出top K近邻商品。
  • 5) co-purchase:对于每个购买pair:,计算频率,其中,商品在商品之后立即购买。接着,给商品的推荐通过频率进行排序,取topK商品。

表2: 潜水呼吸管(cressi supernova dry snorkel)的商品推荐

在第天之前,由于用户具有多个商品的购买行为,为了在这一天选择最好的K个商品,各种独立的预测( separate predictions)必须达成一致。为了达到该目的,我们提出了时间衰减的推荐评分scoring,在根据最高得分选择top K个商品之后使用。更特别的,给定用户在天前的商品购买行为以及它们的时间戳(timestamps):,对于每个商品,我们会根据相似得分检索top K个推荐,产生集合,其中sim表示cosine相似度。接着,我们为每个推荐商品计算一个衰减得分(decayed score):

其中是当前天与产生推荐的商品购买时间的差,其中是衰减因子。最终,按照衰减评分降序,并取topK个商品作为第天的推荐。

表1:通过bagged-prod2vec模型生成的商品推荐示例

训练细节:神经语言模型会使用一台96GB RAM内存的24core机器。embedding space的维度被设置成d=300, 上下文neighborhood size为5. 最后每个向量更新中使用10 negative samples。与[24]的方法相似,最频繁的商品和用户在训练期间会进行子抽样(subsampled)。为了展示该语言模型的效果,表1给出了使用bagged-prod2vec推荐的样例,可以看到邻居商品与query商品高度相关。(例如:“despicable me 卑鄙的我(动画电影)”,该模型会检索到相似卡通片)

评估细节: 与流行商品的accruracy如何测量类似,我们假设每个用户有一个K=20不同商品推荐。对于天的预测,会基于先前天的购买进行预测,我们不会考虑在该天期间发生的购买行为来更新第天的预测。

结果:我们评估了decay factors不同值所对应的prod2vec表现。 在图9中,我们展示了在测试数据(往前看1,3,7,15,30天)上的预测准确率。初始的prod2vec预测会基于在训练数据集最后用户购买。该结果展示了不同预测对于产生推荐准确率提升的预测的折扣,decay factor=0.9是一个最优选择。

9.png

图9: 不同decay值的prod2vec accuracy

参考

关于fastText,有两篇paper需要看下,见下面的参考。如果你的目的是用来训练词向量,可以查看paper 1. 如果是用来进行文本分类,参考paper 2.

第1为《Enriching Word Vectors with Subword Information》:使用subword的信息来增强词向量。

对于常规的一些词向量模型,它们将词汇表中每个词表示成一个不同的向量,在训练中会忽略词形。这对于一些大词汇量、许多罕见字、且词形丰富的语言来说(比如:Turkish语 或 Finnish语),是个很大限制,很难使用这些模型训练到较好的词级别(word-level)的向量。fastText是一种基于skip-gram模型的新扩展,它会使用subword的信息,将每个词被表示成一个字符级n-gram词袋(a bag of character n-grams)。每个向量表示与每个字符级n-gram相关联,而词(word)则可以看成是这些n-gram向量表示的求和(sum)。fastText在大语料上训练很快。

1.介绍

在NLP领域学习词的连续表示(continuous representations)已经有一段历史了(rumelhart et al., 1988)。这些表示通常来自于大型无标记语料来使用共现统计获得(Deerwester et al., 1990)。大部分工作称为“分布式语义(distributional semantics)”,已经研究了这些方法的属性(turney et al.,2010..)。在神经网络社区,Collobert和Weston(2008)提出了使用一个前馈网络来学习word embeddings,它通过基于一个词的左前两词和右后两词来预测中心词。最近,Mikolov(2013b)提出了一种简单的log-bilinear模型来高效学习大规模语料的连续表示。

通过一个不同的向量(distinct vector)来表示词汇表中的每个词,不需要参数共享。特别的,它们忽略了词的内部结构,对于词型丰富的语言( morphologically rich languages)来说,比如Turkish语 和 Finnish语,这是个重要的限制。这些语言包含了许多罕见词,使得很难学习很好的word-level representations。在本paper中,我们提出了为character n-grams学习词表示,并将words表示成n-gram vectors的求和(sum)。我们的主要贡献是对Mikolov的skip-gram做了一个扩展,让它能解释subword information。我们在五种语言上(它们具有不同的词型)评估了该模型,展示了我们的方法的好处。

2.相关工作

形态学词表示(Morphological word representations): 最近几年提出了不少方法,将形态学信息插入到词向量中。为了更好地建模罕见字,Alexandrescu和Kirchhoff(2006)引入了因子化的自然语言模型,其中词被表示成关于特征的集合。这些特征可以包含形态学信息,该技术被成功应用于形态学丰富的语言中,比如:Turkish(Sak 2010)。最近,一些相关的工作提出了不同复合函数来从词素(morphemes)生成词表示。这些不同的方法依赖于词的一个形态学解耦,但我们的方法不会。相似的,Chen(2015)介绍了一个方法来联合学习中文词和字符的embeddings。Soricut(2015)提出了将形态相似的词限制到具有相似表示。Soricut(2015)描述了一个方法来学习形态学转移的向量表示,允许通过应用规则来获取对未登陆词的表示。Cotterell(2015)则在形态学标注的数据上学习词表示。与我们的方法最接近的是Schutze(1993),它通过SVD来学习字符级4-grams的表示,并通过对4-gram representations进行求和来生成词表示。

NLP的字符级特征(Character level features):与我们工作相关的另一个研究领域是,NLP的字符级模型,它直接从字符序列中学习表示。这种模型的最高级方法是RNN,应用到语言建模(Mikolov 2012)、文本归一化(Chrupala, 2014),、词性标注(Ling.2015)、parsing(Ballesterors.2015)。该模型的另一个家族是在字符上训练的CNN,它可以被应用到:词性标注(Santos,2014)、情感分析(dos Santos.2014)、文本分类(zhang.2015)、语言建模(Kim.2016)。(Sperr.2013)提出了基于受限波尔茨曼机的语言模型,其中词被编码成字符级别n-grams的一个集合。最后,在机器翻译中的最近工作也提出了使用subword units来获取罕见词的表示。(Sennrich.2016)

3.模型

本节中,我们提出了一个模型来学习representations来解释词形。

1.1 通用模型

先简单回顾下(Mikolov et al.,2013b)提出的continuous skip-gram模型,给定一个size=W的词汇表,其中词通过它的索引进行表示 ,目标是为每个词w学习一个向量表示。受分布式假设的启发,这些表示被训练来预测在一个给定词的上下文中出现的词。更正式的,给定一个大型训练语料,一个词序列: ,它的skip-gram模型的目标函数是最大化log似然:

其中,上下文表示在词周围词的索引集合,给定,预测观察到的概率。使用一个scoring函数s,可以将(word,context)pair映射到一个R空间的分值上:

该问题也可分解为多个二分类问题,目标是预测对应的是否出现。对于位置t的词,以及上下文c,我们可以得到negative log-likelihood:

其中是一个从词汇表抽样出的负样本集合。logistic loss函数,我们可以获得相应的目标函数:

和上下文词采用标量积:$ s(w_t,w_c)=u_{w_t}^{T}v_{w_c} $

1.2 Subword模型

由于每个词会使用一个不同的向量表示,skip-gram模型会忽视词的内部结构。在本部分,我们接着提出一个不同的scoring函数 s,将subword信息考虑进行。给定一个词w,我们定义在w上出现的n-gram集合为:$ G_w\subset{1,…,G} $.我们将一个向量表示与每个n-gram g相关联。我们可以通过对这些n-gram的向量进行求和来表示一个词。我们获得一个scoring函数:

对于词w,它的n-gram集合中总是包含着它,也可以为每个词学到一个向量表示。n-gram集合也是词汇表的一个超集(superset)。需要注意的是,对于共享相同的字序列(sequence of characters)的一个词和一个n-gram,会分配不同的向量给它们。例如,单词”as”和出现在词”paste”中的bigram “as”,会分配给不同的向量。这种简单模型允许在不同的词之间共享representations,从而对一些罕见词学到可靠的向量表示。

1.3 n-gram字典

上述模型很简单,并在的定义上留下了设计选择的空间。在本paper中,我们采用了一个非常简单的scheme:所有n-gram的长度在[3,6]范围内. 可以使用n-gram的不同集合,例如前缀和后缀。同时,也添加一个特殊字符做为词的开头和结尾,这样就可以区分前缀和后缀。

为了限定模型的内存,使用一个hashing函数,将n-gram映射到[1,K]上。下面,我们使用的K等于200w。在结尾处,一个词可以被表示成在词典中的索引,以及它的n-gram的hash值。为了提升模型效率,我们不会使用n-gram来表示在词汇表中最频繁的P个词。P的选择需要权衡,值越小表示计算代价越高,但性能越好。当P=W时,我们的模型就是skip-gram模型。

1.4 试验

数据集和baseline:将新模型与word2vec的cbow和skip-gram相比较。数据集:5种语言的Wikipedia数据。三种size:小(50M tokens),中(200M tokens),完整。训练使用的epoch为:5.

其它参数:negative-sample: 5, rejection threshold: $ 10^{-4} $, window-size: 5, min-count:5.

  • 小数据集:100维, 中数据集:200维,完整数据集:300维.
  • skip-gram baseline learning-rate: 0.025; CBOW: 0.05, 新模型:0.05

对于英文语料,新模型的训练速度比skip-gram慢1.5倍。

人肉相似度判断

评估向量的质量:计算人肉判断(human judgement)与向量表示之间的cosine相似度之间的Spearman rank相关系数

使用的数据集:

  • 英文:使用 WS353 (Finkelstein et al.2001)以及 RW (Luong et al.2013)
  • 德文:Gur65, Gur350,ZG222(Gurevych, 2005; Zesch and Gurevych, 2006)
  • 法文:RG65(Joubarne and Inkpen, 2011)
  • 西班牙文:WS353(Hassan and Mihalcea, 2009)

这些数据集中的一些词不会在训练数据中出现,对于CBOW方法和skip-gram baseline方法,我们不能获取这些词的向量表示。因此,我们决定排序包含这些词的pairs进行评测。我们在表1中上报了OOV比率。需要注意,我们的方法和baseline共享着相同的词汇表,因此,在相同训练集中的不同方法的结果是可以比较的。另一方面,不同训练语料上的结果是不可比较的,因为词汇表并不相同(具有不同的OOV rates)。

表1:

我们注意到,使用subword信息的新模型的效果在大多数数据集上的效果要好。我们也观察到,字符n-grams的效果,在德文上远比英文、西班牙文上好。一点也不令人吃惊,因为德文的字形更丰富。数据集越小,区别越重要。在RW英文数据集(罕见词数据集)上,新方法效要比baseline要好。

词类比任务(Word analogy)

使用Mikolov et al.(2013a)提出的:句法:syntactic(en-syn),以及语义:semantic(en-sem)来评测,数据集使用cs-all(Svoboda and Brychcin (2016), for Czech, 捷克文)。一些包含words的questions不会在训练语料中出来,我们会排除这些questions,并上报oov rate。所有的方法在相同数据上进行训练,因此可比较。我们上报了表1中的不同模型。我们观察到,字形(morphological)信息对于syntactic任务有极大的帮助,新方法在en-syn上效果要比baseline好。相反的,它在小数据集的semantic任务上,效果有所下降。第二,对于捷克文,一个字形丰富的语言,使用subword信息可以很强地提升效果(对比baseline)。

2.高效文本分类tricks

Mikolov等在中提到了多种高效文本分类的tricks,并提出了fastText。它的分类速度快,又不失精准。在标准多核CPU上训练,超过10亿词上只需要10分钟左右;而对50w的句子,在312K个分类上进行分类,1分钟之内即可完成。听上去有些小激动。

对应paper的研究主要是基于:有名标签预测(namely tag prediction), 情感分析(sentiment analysis),这两个领域做出的。

2.1 模型架构

baseline: 对于句子分类,简单又有效的baseline为:BOW向量 + 一个线性分类器(LR或SVM)。

线性分类器不会共享特征和分类间的参数。对于输出空间很大,但某些类上的训练样本很少的上下文上,这种方法的泛化能力受限。常用的解决方法是,将线性分类器分解为低秩矩阵(Schutze, 1992; Mikolov et al., 2013),或者使用多层神经网络(Collobert and Weston, 2008;Zhang et al., 2015)

图3展示了简单线性模型的秩约束(rank constraint)。第一个权重矩阵A,是一个在words上的look-up table。词向量被平均成一个文本向量,然后输入(feed)到一个线性分类器。文本向量是一个隐变量,它可以尽可能被复用。该架构与Mikolov提出的CBOW模型相似,中间的word被一个label所取代。我们使用softmax函数f来计算在预定义分类上的概率分布。对于N个文档的集合,目标是在这些类上最小化负log-likelihood:

其中xn是第n个文档的归一化的bag of features,yn是label,A和B是权重矩阵。该模型可以在多核CPU上使用SGD和一个线性衰减的learning_rate进行异步训练。

Hierarchical softmax

由于类的数目相当大,计算线性分类器的开销很大。计算复杂度是O(kh),其中k是类的个数,h是文本向量的维度。为了在运行时提升,可以使用基于Huffman树的Hierarchical softmax,具体可以详见另一篇。在训练期,它的计算复杂度下降到O(hlog2(k)).

当在测试阶段时,当查询最可能的分类时,Hierarchical softmax也很有优势。每个节点与一个概率相关,该概率表示从根节点到该节点上路径的概率。如果节点的深度为l+1,相应的父节点为:n1, n2, …, nl,概率为:

这意味着一个节点的概率总是比它的父节点要低。搜索某一深度的该树时,以及在叶子间跟踪最大概率,允许我们抛弃掉所有小概率的分枝。实际上,我们观察到在测试时,复杂度降到O(hlog2(k))。该方法会进一步扩展到使用binary heap来计算top T个target,开销为O(log(T))。

N-gram features

BOW与词序无关,显式采用该顺序的计算开销通常很大。作为替代,我们使用bag-of-n-grams作为额外的特征来捕获一些关于局部词序的部分信息(partial information)。这在惯例上很有效(Wang and Manning, 2012).

我们使用hashing trick(Weinberger et al., 2009),以及Mikolov et al.(2011)中相同的hashing function,以及10M的bins(如果我们只使用bigrams,否则可能100M),来维持一个快速的、内存高效的n-gram映射。

2.2 实验评测

fastText在两个不同的任务上进行评测。首先,会比较在情感分析(sentiment analysis)问题上的文本分类器。模型的实现可以使用Vowpal Wabbit library,但实际上使用的定制版本要比它快2-5x倍。

情感分析(Sentiment analysis)

数据集与baseline。使用8份由Zhang et al. (2015)提供的相同的数据集以及评测约定。使用Zhang et al. (2015)提供的n-gram和TF-IDF做为baselines。以及Zhang and LeCun (2015)提出的字符级卷积模型(char-CNN), (Xiao and Cho, 2016)提出的字符级卷积RNN模型(char-CRNN), Conneau et al. (2016)提出的极深卷积网络(VDCNN)。我们另外采用了Tang et al. (2015)的评测约定,上报了我们的方法以及他们的两种方法 (Conv-GRNN 和 LSTM-GRNN).

结果:使用10个隐单元,fastText迭代5轮(epochs),learning_rate为{0.05, 0.1, 0.25, 0.5}。在该任务上,添加bigram信息可以提升1-4%的效果。整体的accuracy比char-CNN和char-CRNN稍好一些,比VDCNN略差些。注意,可以使用更多的n-gram可以(略微)提升accuracy,例如:使用trigrams,在Sogou语料上的效果可以提升到97.1%。最终,下图展示了我们的方法与Tang et al. (2015)的比较。在验证集上调整超参数,并观察到:使用n-gram为5-gram时,会达到最佳性能。不同于Tang的方法,fastText不会使用pre-trained word-embeddings,据说在accuarcy上可以有1%的提升。

在训练时间上: char-CNN 和 VDCNN在NVIDIA Tesla K40 GPU训练,fastText的模型在使用20线程的CPU上训练。对于char-CNN,使用最新的CUDA实现,可以有10x的速度提升。fastText则可以在1分钟内完成训练。。。

标签预测

数据集和baselines: 采用YFCC100M数据集(Thomee et al., 2016),包含了100M的图片,带说明(captions),标题(titles),以及标签(tags)。我们只关注title和caption(不使用图片)来预测tags。将出现次数少于100次的words/tags进行移除,将数据分割成训练集/验证集/测试集。训练集包含大于9000W的样本(1.5B的tokens),验证集93W的样本,测试集54W的样本。词汇表的size为30W左右,有31W左右是唯一的tags。我们发布了一个脚本来重新创建该数据集。

我们使用一个基于频率的方法作为baseline,来预测最频繁的标签。我们也比较了Tagspace(Weston et al.,2014)的方法,它与我们的模型相类似,但基于Wsabie model of Weston et al. (2011)。Tagspace模型使用卷积进行描述,我们使用它的线性版本作为baseline。

结果与训练时间:上表为fastText与baseline的比较。比较了fastText 5轮的迭代,与两种隐层size(50, 100)的Tagspace算法。两种模型的隐层size都是小值时,在accuracy上效果相似,但如果增加bigram,会有极大的提升。在测试时,tagspace需要为所有类计算分值,这会相当慢,当类数目很大时(本例中为:300K),fastText的inference则会很快!

参考