我们来看下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)质量不会因带label顶点(labeled vertices)的选择而受影响,因而它们可以在任务间共享。

DeepWalk比其它用于创建社交维度(social dimension)隐表示方法要好,尤其是当带label的节点(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

《Web Metasearch: Rank vs. Score Based Rank Aggregation Methods》提出了rank fusion的问题。

1.介绍

rank fusion的问题是,给定多个judges的独立ranking偏好(一个ranking是一个items集合的线性顺序),计算一个“一致的(consensus)”ranking。该ranking fusion问题出现在许多情况下,一个著名的场景是metasearch:metasearch会处理由多个search engines对于一个给定query所返回的多个result lists组合,其中,在result list中的每个item对于各自的search engine是有序的,并且有一个相关分值。

搜索引擎们会帮助人们定位与用户信息相关的信息,但仍有一些不足:

  • i) 检索web数据是一个耗时的任务。由于web内容变化很快,每个search engine必须在覆盖率(coverage)间做个trade-off,例如,web文档的数据会与整个web以及更新频率(例如,在完整数据库的后续re-indexing间发生的时间)有关。
  • ii) 有许多信息源
  • iii) 对于一些搜索引擎,广告商付费越多,在search results上的rank会越高,这被称为:“pay-for-placement”,这在precesion上会有平均损失
  • iv) search engines会有作弊(spamming)

由于上述这些限制,必须引入metasearch engines来提升检索效果。

ranking fusion的理想场景是,每个judge(search engine)给出对所有alternative items一个完整顺序。不幸的是,在metasearch中这不太现实,有两个原因:

  • i) search engines的coverage是不同的
  • ii) search engines会限制访问top 100 or 1000个ranked items

因此,rank aggregation必须可以处理具有有限数目个entires的每个ranking。当然,如果rankings间没有重叠项,。。。设计ranking fusion的一个挑战是,当在每个ranking中的top 几百个/上午个items间存在有限个重合项(但non-trivial)。

。。。

2.ranking fusion方法

对于rank-ordered lists进行合并,存在许多方法。最基础的,他们会使用来自ranked lists中已经提供的信息。在大多数情史中,策略依赖于以下信息:

  • i) 顺序排序(irdinal rank):rank list中的一个item分配一个顺序
  • ii) 得分(score):在rank list中分配给每个item的得分

在score-based方法中,items会根据rank lists中的scores进地rank,或者对这些scores做一些转换(transformation)[1,4,8,9,12,13,17,18];而在rank-based方法中,items会根据rank lists中的rank重新排序,或者对这些ranks做一些转换[1,7,12,19]。另一种正交去重的rank fusion方法则依赖于训练数据(比如:Bayes-fuse方法[1],或者线性组合方法[17],或者偏好rank组合方法[8])。基它一些方法基于ranked items的内容。

2.1 前提

首先看一些基本定义。假设:

  • U是一个items集合,称为“universe”。
  • 是一个rank list,它与U有关,是关于子集的一个排序,例如:,对于每个是在S上的顺序关系.

如果 出现在中,写成表示i的position或rank。我们假设,通过对每个分配一个唯一的id,没有对普适性有损失。

。。。

2.2 Fusion方法

本节中,我们将讲述分析的ranking fusion方法。考虑一个包含了n个rankings的集合。假设:

  • U表示在中的items的union,例如:
  • 表示ranking(被称为fused ranking或fused rank list),它是一个rank fusion方法应用到在R中的rank lists之后得到的结果。

为了彻底说明,它足够决定分值(称为:fused score)(对于每个item ),因为会根据的值递减进行排序。我们认为:

  • 如果两个fused ranking 相等的(equal),则:
  • 如果等价的(equivalent),那么对于,有(他们具有相同的顺序)

当然,equality意味着equivalence,但反过来不成立。

2.2.1 线性组合

Fox[9]提出的ranking fusion方法基于对每个item的归一化得分(normalised score)采用不加权(unweighted)的min, max或sum。另外,Lee[12]解决了rank取代score的case。两种方法如下:

从[9,12]的测试结果看,CombMNZ被认为是最好的ranking fusion方法,它的效果要稍好于CombSUM。根据Lee的实验,CombMNZ基于该事实:“不同搜索引擎返回(return)相似的相关文档集合,但检索(retrieve)不同的不相关文档集合”。确实,CombMNZ组合函数会对常见文档进行大的加权。

。。。

2.2.1.1 Borda Count

Borda的方法[2,14]是一个基于ranks的voting方法,例如,一个candidate出现在每个voter的ranked list中,则会为相应的ranks分配一个weight。计算上非常简单,因为实现是线性的。Borda Count (BC)方法在rank fusion问题中被引入,并以如下方式运转。每个voter会对一个关于c个candidates的固定集合以偏好顺序进行rank。对于每个voter,会给top ranked candidate为c分,第二个ranked candidate会得到c-1分,以此类推。在unranked candidates间则均匀分配剩余得分。candidates会以总分(total points)的递减顺序进行rank。正式的,该方法与以下过程等价:对于每个item 以及rank list ,Borda归一化权重为(定义1)。fused rank list 根据Borda score 的顺序排序,其中在中的一个item 被定义为:

…(6)

相应的,BC等价于CombSUM方法组合上Borda rank normalisation,(例如:)。Aslam[1]也考虑过一种Weighted Borda Count,其中,在对归一化Borda weights求和的部分,会使用这些weights的一个线性组合。

2.2.2 Markovchain-based方法

[7]中提出一种关于rank fusion的有意思的方法,它基于Markov chains实现。一个系统的一个(齐次:homogeneous)Markov chain可以通过一个状态集以及一个的非负随机矩阵M(例如:每行的求和为1)来指定。该系统从S中的某个状态开始,并在每个step时会从一个state转移到另一个state。转移(transition)通过矩阵M来指导:在每个step上,如果系统从状态i移到状态j的概率为。如果给定当前状态作为概率分布,下一状态的概率分布通过表示当前状态的该vector与M相乘得到。总之,系统的起始状态(start state)根据在S上的一些分布x被选中。在m个steps后,该系统的状态会根据进行分布。在一些条件下,不需要考虑起始分布x,该系统最终会达到一个唯一确定点(状态分布不再变化)。该分布称为“稳态分布(stationary distribution)”。该分布可以通过M的左主特征向量(principal left eigenvector)y给出,例如:。实际上,一个简单的power-iteration算法可以快速获得关于y的一个合理近似。y中的entries定义了在S上的一个天然顺序。我们称这样的顺序为M的马尔可夫序(Markov chain ordering)

对rank fusion问题使用Markov chains如下所示。状态集合S对应于待排序(rank)的所有candidates的list(例如:在中的所有items的集合)。在M中的转移概率在某种程度上依赖于是在M上的Markov chain ordering。下面,[7]提出了了一些Markov chains(MC):

  • : 如果当前state为item i,那么,下一state从对应rank >= item i的所有items j的multiset中均匀选中,例如,从multiset 中均匀选中下一state。

  • :如果当前state为item i,下一state的挑选过程如下:首先从所有包含i的中均匀选中一个ranking ,接着从集合中均匀选中一个item j

  • :如果当前state为item i,下一state的挑选过程如下:首先从包含i的所有中均匀选择一个ranking ,接着均匀选择通过排序的一个item j。如果那么跳到j,否则留在i;

  • :如果当前state为item i,下一state挑选过程如下:首先从S中均匀选中一个item j。如果对于会同时对i和j进行排序的lists 中的大多数都成立,那么跳到j,否则留在i。

注意,Markov chain方法确实只依赖于ranks间的比较,即不考虑scores也不考虑hits。下面是一个示例。

示例1.考虑以下在S={1,2,3}中的三个items的rankings .

图1

它可以展示成关于的转移矩阵,分别为:

图2

下面,我们会为matrix entries展示一些示例计算。记住是给定当前state(item i)到下一state(item j)的概率。

  • 是2/6. 确实,(rank<=item 1的case:1; 1,3; 1,2,3)。因此,在中均匀选中某一元素的概率为1/6, 选中item 3的概率为2/6.

  • 是5/18. 均匀选择一个包含item 2的rank list的概率为1/3. 如果被选中,那么。因此,选中item 1的概率为1/2. 相似的,并且。因此,

  • 是2/9. 均匀选中一个包含item 2的概率为1/3. 在一个rank list范围内均匀选择一个item的概率也为1/3. 由于, 因此

图3

  • 是1/3. 均匀选中在S中一个item的概率为1/3. 另外,考虑图3中的表:在上表中的每个entry 是满足的lists的count数(例如,有多少rankings满足:item j的rank比item i要好)。由于存在三个lists,因此majority的阀值是2. 指的是:给定item 2, 在下一step之后我们仍停留在item 2上的概率。由于分别是2、 0、 2, 三种情况中有两种会从item 2进行转移,另一种仍会停留在item 2上。相应的是1/3.

最终,关于rank set R的fused rank list 是在上的Markov chain ordering。它可以被展示成的所有4种情况。

参考

Joseph A. Konstan教授(coursera.明大.推荐系统课程)在2005年《Improving Recommendation Lists Through Topic Diversification》中提出了主题多样性。虽然这篇paper比较老,但比较经典,值得一看:

1.介绍

推荐系统的目标是:基于用户过往偏好、历史购买、人口统计学信息(demographic information),提供用户关于他们可能喜欢的产品的推荐。大多数成功的系统会利用CF(collaborative filtering),许多商业系统(Amazon.com)利用这些技术来提供个性化推荐列表给他们的顾客。

尽管state-of-the art CF系统的accuracy很出色,实际中已经发现:一些可能的结果会影响用户满意度。在Amazon.com上,许多推荐看起出在内容上很“相似(similar)”。例如,顾客已经购买了许多关于赫尔曼·黑塞(Hermann Hesse)的诗集,可能会获得这样的推荐列表:其中所有top-5的条目都只包含了该作者的书。当纯粹考虑accuracy时,所有这些推荐看起来都是出色的,因为该用户很明显喜欢赫尔曼·黑塞写的书。另一方面,假设,该活跃用户在赫尔曼·黑塞之外还有其它兴趣,比如:历史小说以及世界游行方面的书,那么该item推荐集合就看起来较差了,缺乏多样性。

传统上,推荐系统项目会关注于使用precision/recall 或者MAE等metrics来优化accuracy。现在的一些研究开始关注pure accuracy之外的点,真实用户体验是必不可少的。

1.1 贡献

我们通过关于真实用户满意度,而非pure accuracy,来解决之前提到的不足。主要贡献如下:

  • 主题多样性(topic diversification):我们提出了一种方法,根据该活跃用户的完整范围的兴趣,来平衡top-N推荐列表。我们的新方法会同时考虑:suggestions给出的accuracy,以及在特定主题上的用户兴趣范围。主题多样性的分析包含:user-based CF和item-based CF.
  • Intra-list相似度指标(similarity metric):
  • accuracy vs. satisfaction:

2.CF

3.评估指标

为了判断推荐系统的质量和效果,评估指标是必要的。许多评价只关注于accuracy并忽略了其它因素,例如:推荐的novelty(新奇)和serendipity(意外发现),以及推荐列表items的diversity。

以下给出了一些流行的指标。

3.1 Accuracy Metrics

Accuracy metrics主要有两个:

第1, 为了判断单个预测的accuracy(例如:对于商品的预测的accuracy ratings 有多偏离)。这些指标特别适合于,预测会随商品被展示的任务(比如:annotation in context)

3.1.1 MAE

3.1.2 RECALL/Precision

3.2 Accuracy之外

尽管accuracy指标很重要,还有其它不能被捕获的用户满意度特性。non-accuracy metrics与主流的研究兴趣相距较远。

3.2.1 覆盖度(Coverage)

在所有non-accuracy评估指标上,coverage是最常见的。coverage指的是:对于要预测的问题域(problem domain)中元素(elements)部分的百分比。

3.2.2 Noverlty和Serendipity

一些推荐器会生成高度精准的结果,但在实际中没啥用(例如:在食品杂货店中给顾客推荐香焦)。尽管高度精准,注意,几乎每人都喜欢和购买香焦。因此,他们的推荐看起来太过明显,对顾客没啥太多帮助。

Novelty和serendipity指标可以衡量推荐的”非显而易见性(non-obviousness)”,避免“随机选取(cherry picking)[12]”。对于serendipity的一些简单measure,可以采用推荐items的平均流行度。分值越低表示越高的senrendipity。

3.3 Intra-List Similarity

我们提出一个新指标,它的目的是捕获一个list的diversity。这里,diversity指的是所有类型的特性,例如:genre、author、以及其它的有辩识度的特性。基于一个任意函数(arbitrary function):,来衡量在商品间的相似度,我们将的推荐列表的intra-list similarity定义如下:

…(5)

分值越高表示越低的diversity。我们会在后面涉及到的关于ILS的一个令人感兴趣的数学特性:排列不敏感(permutation-insensitivity),例如:是关于在的所有排列的对称分组(symetric group):

…(6)

这里,通过在一个top-N list 上对推荐的位置进行简单重设置,不会影响的intra-list similarity。

4.topic diversification

acurracy指标的一个主要问题是,它不能捕获更宽泛的用户满意度,会隐藏在已存在系统中的一些明显缺陷。例如,推荐出一个非常相似items的列表(比如:对于一个很少使用的用户,根据author、genre、topic推出),尽管该列表的平均accuracy可能很高。

该问题在之前被其它研究者觉察过,由Ali[1]创造了新词“投资组合效应(portfolio effect)”。我们相信:item-based CF系统特别容易受该效应的影响。从item-based TV recommender TiVo[1]、以及Amazon.com recommender的个性化体验都是item-based。例如,这篇paper的作者只获得了关于Heinlein的书籍推荐,另一个则抱怨推荐的书籍全是Tolkien的写作。

在用户满意户上的负面分歧的原因暗示着,“protfolio effects”是很好理解的,已经在经济学界被广泛研究,术语为“边际收益递减规律(law of diminishing marginal returns)【30】”。该规律描述了饱和效应(saturation effects):当商品p被不断地获得(acquired)或消费(consumed)时,它的增量效用(incremental utility)会稳定的递减。例如,假设你被提供了你喜欢的酒。假设:表示你愿意为该商品支付的价格。假设你被提供了第二杯特别的酒,你趋向于花费的的金额会越来越少,(例如:p_1 > p_2)。以此类推:

我们提出了一种方法“topic diversification”来处理该问题,并便推荐列表更多样化,更有用。我们的方法是现有算法的一个扩展,可以被应用到top推荐列表上。

4.1 Taxonomy-based Similarity指标

函数:,表示在两个商品集合之间的相似度,这构成了topic diversification的一个必要部分。对于taxonomy-driven filtering[33],我们使用我们的指标对实例化,尽管其它content-based similarity measures可能看起来也适合。在商品集合间的相似度计算指标基于他们的分类(classification)得到。每个商品属于一或多个分类,它们以分类的taxonomies进行层次化排列,以机器可读的方式描述了这些商品。

classification taxonomies存在不同领域。Amazon.com为books/DVSs/CDs/电子产品等制作了非常大的taxonomies。图1表示一个sample taxonomy。另外,在Amazon.com上的所有商品的内容描述与它们的domain taxonomies相关。特征化的主题可以包含:author、genre、audience。

图1

4.2 topic diversification算法

算法1展示了完整的topic diversification算法。

算法1

函数表示新的推荐列表,它由使用topic diversification产生。对于每个list entry ,我们从候选商品集中收集了这些商品b,它们不会出现在在中的位置上,并使用集合来计算相似度,它包含了所有新推荐的前导rank z。

根据以逆序方式对所有商品b进行排序(sorting),我们可以获得不相似rank(dissimilarity rank) 。该rank接着会使用原始推荐rank 根据多样化因子进行合并,生成最终rank 。因子定义了dissimilarity rank 应用在总体输出上的影响(impact)。大的喜欢多样性(diversification)胜过的原始相关顺序,而较低的生成的推荐列表与原始rank 更接近。对于实验分析,我们使用diversification因子:

注意,有序的input lists 必须是大于最终的top-N list。对于我们的后续实验,我们会使用top-50 input lists来产生最终的top-10推荐。

4.3 推荐依赖

为了实验topic diversification,我们假设:推荐商品,和它们的内容描述一起,会产生一个相互影响,它会被现有方法所忽略:通常,对于推荐列表的items来说,只有相关度加权排序(relevance weight ordering) 必须保持,假设没有其它依赖。

在topic diversification的case中,推荐相互依赖意味着:一个item b与之前推荐间的当前dissimilarity rank,会扮演一个重要角色,可能影响新的ranking。

4.4 渗透压(Osmotic Pressure)类比

dissimilarity效应与分子生物学上的渗透压和选择性渗透(selective permeability)相类似。将商品(它来自兴趣的特定领域)稳定插入到推荐列表中,等价于:从来自一个特定物质的分子通过细胞膜传到细胞质中。随着浓度(它属于膜的选择性通透性)的增加,来自其它物质d的分子b的压力会上升。对于一个给定主题,当压力(pressure)足够高时,它最好的商品可能“散开(diffuse)“到推荐列表中,尽管他们的原始排序(original rank)可能不如来自流行域(prevailing domain)。相应的,对于的压力会下降,为另一个压力上升的domain铺路。

这里的topic diversification类似于细胞膜的选择性渗透性,它允许细胞来将细胞质的内部组成维持在所需要级别上。

参考