我们来看下standford的Aditya Grover的《node2vec: Scalable Feature Learning for Networks》。

1.介绍

node2vec是一种半监督算法,用于在网络中的可扩展特征学习。受之前NLP中工作[21]的启发,我们会使用SGD对一个定制的基于图的(graph-based)目标函数进行优化。直觉上,该方法会返回特征表示,对于在d维空间内的节点,会对它们的网络邻节点的似然进行最大化。我们使用2-order的随机游走来为顶点生成(抽样)网络邻节点。

我们的关键贡献是,为一个顶点的网络邻节点定义了一个灵活的概念。通过选择一个合适的概念,node2vec可以学到网络表示,它们可以基于现在的网络角色,或者属于的社群来进行组织。我们通过开发一个有偏的随机游走(biased random walks)的族谱,它可以有效探索一个给定顶点的邻居分布。结果算法很灵活,提供可调参数给我们以对搜索空间进行控制,而不是之前的方法[24,28]进行严格搜索(rigid search)。相应的,我们的方法可以建模网络等价物。参数管理着我们的搜索策略,具有一个直观解释,会让walk朝着不同的网络搜索策略进行偏移。这些参数在一个半监督学习中,只使用很小比例的带标注数据(labeled data)就可以直接学到。

我们也展示了单独节点的特征表示如何被扩展成节点对(pairs of nodes。比如:边)。为了生成边的特征表示,我们将将学到的特征表示与简单的二元操作相组合。这种组合(compositionality)将node2vec引入到关于节点(或者是边)的预测任务上。

我们的试验集中在两个关于网络的公共预测任务上:一个多标签分类任务,其中每个节点被分配一或多个标签;一个链接预测任务,其中给定一个节点对,预测该边是否存在。我们将node2vec与state-of-art的特征学习方法[24,28]进行对比。并从现实中不同领域中的网络进行实验,比如社交网络,信息网络,以及系统生物学网络。对比起state-of-art的方法,实验演示了nod2vec在多标签分类上要好26.7%,在链接预测的任务上要好12.6%。该算法展示了有竞争力的效果,即使只有10%的带标签数据,对于噪声或缺失边的情况下一样健壮。计算上,node2vec的主要过程是并行化的,它可以扩展到带有数百万节点的大网络上,只需要几个小时的计算量

该paper主要贡献是:

  • 1.提出了nod2vec,一种用于网络特征学习的高效的扩展算法,可以通过一种显著的network-aware,neighborhood preserving objectives,使用SGD方法进行高效优化。
  • 2.我们展示了node2vec如何适应在网络科学中已确立的准则,提供了在发现表示上的灵活性,并有不同的等价物。
  • 3.我们基于neighborhood preserving objectives,扩展了node2vec以及其它特征学习方法,将节点扩展到节点对,来基于边的预测任务。
  • 4.在多个真实数据集上,在多标签分类和链接预测上评估node2vec。

2.

在NLP的表征学习的最近进展上,有新方法对离散目标(比如:词)进行特征学习。特别的,Skip-gram模型是目标就是学习连续的特征向量,通过优化一个(neighborhood preserving likelihood objective). 该算法的处理如下:扫描一个文档的词,对于每个词,它的目标是将它进行嵌入,以便该词的特征可以预测邻近词(例如:在一些上下文窗口中的词)。词的特征表示通过使用SGD、negative sampling对likelihood objective进行优化学习得到。skip-gram目标函数是基于分布式假设:有相似上下文的词,趋向于具有相近的意思。也就是说,相似的词趋向于出现在具有相似词邻居的上下文内。

受skip-gram模型的启发,最近的研究确立了一种网络的类比法,将一个网络表示成一个“文档(document)”。相同的方法是,一个有序的词序列,节点序列需要从底层网络上进行采样,将一个网络转化成一个有序的节点序列。然而,对于节点来说,存在许多可能的抽样策略,会从而学到不同的特征表示。事实上,正如我们展示的,对于所有网络和所有预测任务来说,没有明确可胜出的抽样策略可以适用所有场景。以前的方法的主要缺点是,在从一个网络上进行抽样节点时缺乏灵活性。我们的算法node2vec克服了该限制,通过设计一种灵活的目标函数,它不会绑定一个特定的抽样策略,提供参数来调节探索的搜索空间(见第3节)。

最终,对于基于节点和基于边的预测任务,存在许多监督特征学习方法[15,17,31,39]。这些架构直接最小化loss function,使用多层非线性转换来产生更高的accuracy,但扩展开销高,因为训练时间长。

3.特征学习框架

我们将网络特征学习看成是一个极大似然优化问题。给定一个网络。我们的分析是普适性的,可以应用于任何有向(无向)、加权(不加权)的网络。假设:是映射函数,将节点映射到特征表示。这里的d是特征表示的维度。f是一个size为的参数矩阵。对于每个源节点(srouce node),我们定义了作为节点u的一个网络邻节点,它通过邻节点采样策略S来生成。

我们扩展了Skip-Gram架构来处理该网络。我们对下面的目标函数进行最优化,它会基于它的特征表示,对一个节点u的一个网络邻节点的log概率进行最大化,f给定:

…(1)

为了让最优化变得可处理,我出做出了两个标准假设:

  • 条件独立性。我们通过假设:给定源节点的特征表示,观察到一个邻节点的似然,与观察到其它邻节点是独立的:
  • 特征空间的对称性。一个源节点和它的邻节点在特征空间中具有对称性的相互影响。因而,我们建模每个(源节点-邻节点)pair的条件似然建模成一个softmax unit,它由它们的特征点积进行参数化:

有了以上假设,等式一的目标可以简化为:

…(2)

每个节点的分区函数:,对于大网络来说计算开销很大,我们可以使用负采样[22]来对它做近似。我们使用SGA(ascent)对等式(2)进行优化.

基于skip-gram的特征学习方法,最早源自于NLP上下文学习。文本本身是线性的,一个邻词可以很自然地使用一个在连续词汇上的滑动窗口进行定义。而对于网络,是非线性的,因而需要更丰富。为了解决这一点,我们提出了一个随机过程,它会对给定源节点u抽样许多不同的邻节点。不局限于它的立即邻节点(immediate neighbors),具体取决于抽样策略S,有不同的结构。

3.1 经典搜索策略

图1

我们将对一个源节点的邻节点进行抽样的问题看成是一种局部搜索(local search)。图1展示了一个图,其中,给定一个源节点u,我们的目标是生成(抽样)它的邻节点。重要的是,为了比较不同的抽样策略S,我们将邻节点集合的size限制为k个节点,接着为单个节点u抽样多个集合。总体上,有两种极限抽样策略来生成k个节点的邻节点集合

  • 广度优化抽样(BFS:Breadth-first Sampling): 邻节点被限制到关于源节点的立即领节点上(immediate neighbors)。例如:在图1中,对于一个邻节点的size为 k=3, BFS抽样的节点为:
  • 深度优化抽样(DFS:Depth-first Sampling):邻节点包含了从源节点开始在增加的距离上按顺序抽样的节点。在图1中,DFS抽样

BFS和DFS表示了根据搜索空间进行探索的两种极限情况。

特别的,在网络上的节点的预测任务通常会是两种类型相似度的混合(shuffle):同质(homophily)等价 和结构(structural)等价。在同质假设下,节点高度交错连接,并且属于同网络聚类或社群,在embedding上更紧密(例如:图1中的节点和u属于相同的网络社群)。相反的,结构等价假设下,在网络上具有相似结构角色的节点,应该在embedding上更紧密(例如:节点u和在图1上分演扮演着相应社群中心的角色)。更重要的是,不同于同质等价,结构等价不强调连通性;在网络中的节点可以离得很远,但它们仍具有相近的网络结构角色。在真实世界中,这些等价概念并是排斥的;网络通常具有两者的行为。

我们观察到,BFS和DFS的策略在处理表示时扮演着重要角色,它影响着上述两种等价。特别的,BFS抽样的邻节点会导致embedding与结构等价更紧密。直觉上,我们注意到,为了探明结构等价,通常会对局部邻节点进行精准的描述。例如,基于网络角色(桥接:bridges、中心:hubs)的结构等价可以通过观察每个节点的立即节点(immediate neighborhoods)观察到。通过将搜索限制到邻近节点,BFS达到了这种characterization, 并且获得了关于每个节点的邻近点的微观视角。另外,在BFS中,在抽样邻节点上的节点趋向于重复多次。这很重要,对于。

3.2 node2vec

基于上述观察,我们设计了一种灵活的邻节点抽样策略,它允许我们在BFS和DFS间进行平衡。我们通过开发一种灵活的有偏随机游走(biased random wolk)过程,它可以以BFS和DFS的方式来探索邻节点。

3.2.1 随机游走

给定一个源节点u,我们进行模拟一个固定长度为l的随机游走。表示在walk中的第i个节点,从起点开始。节点通过下面的方式生成:

其中是未归一化的节点v和x间的转移概率,而Z是归一化常量。

3.2.2 搜索偏差

对我们的随机游走进行bias的最简单方法是,基于一个静态边权重(例如: )来抽样下一个节点(无权重图则)。然而,该种情况不能解释网络结构,并指导搜索过程来探索不同类型的网络邻居。另外,不同于BFS和DFS两个极端,我们的随机游走会兼容两者。真实网络中通常也是两者混合。

图2: 在node2vec中的随机游走过程说明。该walk会从t到v进行转移,并在node v准备出去的下一步进行评估。边的labels表示搜索的bias

我们定义了一个2阶随机游走,它具有两个参数p和q来指导walk:考虑到一个随机游走,它穿过边(t,v),现在留在节点v上(图2)。该walk需要决定,在下一步它会评估在边(v,x)上由v产生的转移概率。我们设置未归一化转移概率为,其中:

其中,表示在节点t和x上的最短路径距离。注意,必须是{0, 1, 2}其中之一,因而,两个参数都是必须的,可以充分指导该walk。

直觉上,参数p和q控制着该walk从起始节点u进行探索和离开邻节点的快慢。特别的,该参数允许我们的搜索过程(近似)在BFS和DFS间进行插值,从而影响不同节点等价的紧密关系。

返回(Return)参数:p。参数p控制着在walk中立即访问一个节点的似然。将它设置成一个高值(> max(q,1)),可以确保我们在下两步内对一个已经访问节点进行抽样的可能性变得很小。(除非在walk内的下一个节点没有其它邻居)。这种策略鼓励适度探索,避免在抽样时存在二跳内重复(2-hop redundancy)。另一方面,如果p很小(<min(q,1)),它将导致该walk会回溯(backtrack)一个step(见图2),并且这会让该walk“局部”上保持与起始节点u的接近。

入出(In-out)参数:q。参数q允许搜索在“inward”和”outward”节点间区分。回到图2, 如果q>1, 随机游走会偏向于更接近节点t的节点。这样的walk会根据在walk中各自的起始节点获得一个关于底层graph的局部视图,近似的BFS行为感觉上我们的抽样在一个小的局部内的节点组成。

作为对比,如果 q < 1, 该walk更趋向于访问那些离节点t更远的节点。这样的行为受DFS影响,它会鼓励outward探索。然而,这里的一个基本不同是,我们在随机游走框架内完成DFS-like的探索。因而,被抽中的节点不需要对到给定节点u的距离进行增加才行,反过来,我们受益于对随机游走的回溯预处理和优秀的采样效率。注意,通过将设置成关于一个在walk t内前继节点的函数,随机游走是2阶markovian。

随机游走的好处。比起纯BFS/DFS方法,随机游走有许多好处。随机游走在时间和空间需求上的计算很高效。在图中为每个节点存储它的立即邻节点的空间复杂度为。对于二阶随机游走,会存储在每个节点的邻节点间的交叉连接,这会引发一个空间复杂度为,其中是该graph的平均度,它通常对于现实网络来说很小。比起经典的基于搜索的抽样策略,随机游走的其它核心优点是它的时间复杂度。特别是,通过引入在抽样生成过程中的图连通性,随机游走提供了一个很便利的机制,通过复用跨不同源节点间的样本,来增加有效抽样率。通过模拟一个长度l>k的随机游走,得益于随机游走的马尔可夫性,我们可以为l-k个节点一次生成k个样本。因而,每个样本的有效复杂度为。例如,在图1中,我们抽样一个长度为l=6的随机游走 {},它会产生,以及。注意,在整个过程中,样本复用可能引入一些bias。然而,我们观察到它可以极大提升效率。

3.2.3 node2vec算法

算法1

node2vec的伪代码,详见算法一。在任何随机游走中,由于起始节点u的选择,会有一个隐式偏差(implicit bias)。由于我们为所有节点学习表示,我们会为每个节点通过模拟r个固定长度为l的随机游走来对该bias进行补偿(offset)。在该walk的每一个step,会基于转移概率进行抽样。对于二阶马尔可夫链,转移概率可以被预计算好,因而,当模拟随机游走时,节点的抽样可以很有效地在O(1)时使用alias sampling完成。node2vec的三个阶段(phases),即:预处理计算转移概率、随机游走模拟、使用SGD进行优化,是按顺序进行的。每个phase可以并行化和异步执行,从而做到node2vec整体可扩展性。 node2vec的一个实现:http://snap.stanford.edu/node2

3.3 学习边特征

node2vec算法提供了一个半监督方法来学习网络中节点的丰富特征表示。然而,我们通常对涉及节点对(pairs of nodes)的预测任务感兴趣,而非单个节点。例如,在链接预测上,我们在网络中的两个节点间预测一个链接是否存在。由于我们的随机游走在底层网络上天然地基于节点间的连通结构,我们可以使用一个bootstrap方法来将它们扩展到节点对的特征表示,而非单个节点的特征表示。

给定两个节点u和v,我们定义了一个二元操作o,在相应的特征向量f(u)和f(v),为了生成一个表示g(u,v),比如:,其中是pair(u,v)的表示的size。我们希望我们的操作对于任意节点对可以进行定义,即使一条边在pair间不存在,因为这样做可以使表示对于连接预测有用,我们的测试集包含了true edges和false edges(不存在)。我们对于操作符o的一些选择,以便,由表1归纳的。

实验

node2vec: Scalable Feature Learning for Networks

yahoo japan在kdd 2017的《Embedding-based News Recommendation for Millions of Users》提出了关于新闻推荐的一些方法:

#

理解文章内容和用户偏好,对于做出有效新闻推荐来说很必要。而基于ID的方法,比如:CF和低秩因子分解,也可以做出推荐,但它们不适用于新闻推荐,因为候选文章会快速超期,在短时内被更新的替代。Word-based方法,常用于信息检索,是很好的候选方法,但它们只与用户历史动作的”queries”同义相关。该paper提出了一种embedding-based方法,它使用分布式表示,以一个3-step end-to-end的方式进行:

  • i) 基于一个denoising autoencoder的变种生成文章的分布式表示
  • ii) 使用一个RNN,将用户浏览历史作为输入序列,生成用户表示
  • iii) 基于内积(inner-product)操作为用户匹配(match)和列出(list)对应文章,并考虑上系统性能。

提出的方法在Yahoo! Japan的主页上的历史访问数据进行评估和实验,并表现良好。我们基于实验结果,在我们实际的新闻分发系统上实现了它,并比较它的在线效果。CTR的提升有23%,总时长(total duration)提升了10%,对比起常用的方法。我们提出的方法已经开放给所有用户,并每天提供推荐给超过1000w个人用户,每月访问次数超10亿。

1.介绍

对于用户来说,读取所有存在的文章的新闻分布是不可能的,这受限于时间。因而,用户喜欢新闻服务可以选择性地提供文章。这种选择通常由编辑人工完成,所选故事的公共集合会在传统媒体上(比如:电视新闻节目、报纸)被提供给用户。然而,在互联网上,我们可以使用以下信息:user ID cookies、单个用户的个性化阅读文章等等,从而对用户进行标识来更好地选择文章。

ID-based方法,比如CF或低秩因子分解,可以很好地做出推荐。然而,[22]建议,这样的方法不适合于新闻推荐,因为候选文章很快会过时。因而,新闻推荐需要有三个关键点:

  • 理解文章内容
  • 理解用户偏好
  • 基于内容和偏好为用户列出挑选的文章

另外,在现实中能快速响应扩展性和噪声并做出推荐很重要[14]。应用也需要在数百ms内返回响应给每个用户。

覆盖上面三个关键点的一个baseline实现如下。一篇文章被看成是关于它的文本的一个词集合(words collection)。一个用户可以看成是他/她浏览的多篇文章的一个词集合(words collection)。该实现会使用文章集和它的浏览历史之间的词共现作为特征来学习点击概率。

该方法有一些实际优点。它可以快速响应最新趋势,因为模型很简单,可以很快进行学习和更新。优先级的估计可以使用已经存在的搜索引擎和词的倒排索引进行快速计算。

出于这些原因,我们的之前版本实现基于该方法。然而,有一些要点可能会对推荐质量有负面影响。

第一个是词的表征(representation of words)。当一个词只当成一个feature使用时,两个具有相同意思的词会被看成是完全不同的feature。该问题会趋向于出现在在新闻文章中当两个提供者对于相同的事件提交文章时。

第二个问题是,浏览历史的处理。浏览历史在该方法中被处理看一个集合(set)。然而,他们实际上是一个序列,浏览的顺序应能表示用户兴趣的转移。我们也必须注意,用户在历史长度上分别很大的,从私人浏览,到那些每小时多次访问。

基于深度学习的方法已经在多个领域取得效果。词的分布式表示可以捕获语义信息。RNN已经为处理不同长度的输入序列提供了有效结果【9,15,17】。

如果我们使用一个RNN来构建一个深度模型来估计用户和文章间的兴趣度,另一方面,很难满足在实时系统中的响应限制。该paper提出了一个embedding-based方法,它使用一个在3-step end-to-end中使用分布式表示的方法,基于相关性和重复性,来为每个用户表示文章列表中的每篇文章。

  • 基于一个denoising autoencoder的变种来生成文章的分布式表示
  • 通过使用一个RNN,使用浏览历史作为输入序列,来生成用户表示
  • 为每个用户基于用户-文章的内积,根据相关性和文章间的去重性,来匹配和列出文章

我们的方法的关键点是估计文章-用户间(article-user)的相关性。我们可以在用户访问足够时间之前,计算文章表示和用户表示。当一个用户访问我们的服务时,我们只选择他/她的表示,它计算候选文章和该表示间的内积。我们的方法可以表达包含在用户浏览历史中的复杂关系,并能满足实时性限制。

提出的方法被用到新闻分发服务中。我们比较了我们的方法和其它方法,结果表明,提出的方法要好于常用方法,不管是在实时服务上还是静态实验数据上,缺点是,增加了学习时间,模型更新延迟,但都在允许范围内。

2.服务和处理流

在该paper中讨论的方法被用在Yahoo!Japan上。第6节描述的在线实验也在该页上进行。

图1: Yahoo!Japan在移动端的主页示例。该paper讨论了关于个性化模块中的文章的方法

图1展示了一个我们的服务的实物,可以在May 2015复现。在顶部header有一个搜索窗口和其它服务的链接。中间部分,称为“Topics module”,提供了在主要新闻上通过人工专家为读者群精心挑选的的6篇文章。底部,称为“个性化模块(Personalized module)”,提供了许多文章和广告,它们对于用户是个性化的。在个性化模块中的用户,可以随着他们的滚动看尽可能多的文章。典型的读者基本上会浏览20篇文章。该paper描述了个性化文章提供的最优化。

会执行5个过程来为数百万用户进行个性化选择文章。

  • Identify:通过用户之前的历史行为计算获取user features
  • Matching:使用user features抽取匹配上的文章
  • Ranking: 以特定优先级对文章列表重排序
  • De-duplication:去重,移除包含相似信息的文章
  • Advertising: 如果有必要,插入广告

从用户发起请求到展示文章,这些过程必须在数百ms内完成,因为文章是经常变化的。事实上,在我们服务中的所有文章,超过24小时就失去了新鲜度,每天会发表上万的新文章,同样的,相同数目的老文章会因为超期被移除。因而,每个过程都会采用较经计算开销的方法,它会使用预计算好的文章的分布式表示(第3节描述)和用户表示(第4节)。

我们使用一个用户的分布式向量和候选文章向量间的内积,来匹配相关性和选择满意的候选。我们会决定排序的优先顺序,通过考虑额外因子,比如:PV的期望数目,每篇文章的新鲜度,以及匹配的相关度。我们会以贪婪的方式基于分布式表示的cosine相似度去复相似文章。当带有更高优先级的文章的cosine相似度的最大值,超出一定阀值时,我们会跳过该文章。在真实新闻分发服务中这是一个重要的过程,因为相似文章在排序时具有相似的分数。如果相似文章的展示相互挨着,用户满意度会下降,因为在展示时缺少多样性。广告也很重要,但许多研究表明广告与用户满意度间的关系,这里我们省略这一块的讨论。

3.文章表示

第1节介绍了一种使用words作为一篇文章的features的方法,它在特定的关于抽取和去重的cases中不一定能工作良好。这一节会描述一种方法来将文章表示成分布式表示。我们提出了之前的一种方法[12]。

3.1 生成方法

我们的方法会基于一个denoising autoencoder,并使用弱监督的方法来生成分布式表示向量。常见的denosing autoencoder可以公式化:

其中是原始input vector,是加噪声混淆分布(corrupting distribution)。stochastically corrupted vector, ,从中获取。隐表示,h,从映射穿过该网络,它包含了一个激活函数,,参数矩阵W,参数向量b。在相同的方式下,reconstructed vector,y, 也从h映射,带有参数。使用一个loss函数,,我们学习这些参数来最小化y和x的reconstruction errors。

h通常被用于一个对应于x的向量表示。然而,h只持有x的信息。我们希望解释,如果更相似时,两个表示向量的内积 更大。为了达到该目的,我们使用了一个三元组,,作为训练的输入,并修改了目标函数,来维持他们的类目相似性:

其中,, 以至于具有相同或相似的类目,具有不同的类目。在等式(1)中的h满足该属性,。这意味着,这是一篇与其它文章都不相似的文章。该概念,是一个关于文章相似度的罚项函数,它对应于类别相似度(categorical similarity),其中是一个用于权衡的超参数。图2提供了该方法的一个总览。

图2: 文章三元组有encoder

我们使用elementwise sigmoid 函数,作为,elementwsie cross entropy为,masking noise为。我们训练该模型,,通过使用mini-batch SGD进行最优化。

我们在应用阶段(application phase)通过使用常数衰减来构建,在训练阶段(training phase)则使用stochastic corruption作为替代:

其中,p是训练阶段的corruption rate。因而,h是应用时唯一确定的。乘以(1-p)对于将输入分布均衡到在middle layer中的每个神经元有影响,在masking noise和没有该noise间进行学习(待)。

我们使用在上述三个应用中生成的h作为文章的表示:

  • (i) 可作为user-state函数的输入
  • (ii) 可以衡量user和article间匹配的相关度
  • (iii) 衡量在去重时文章间的相似度

4.用户表示

本节描述了通过用户浏览历史进行计算用户偏好的多种方法。首先,我们对问题进行公式化,并生成一个简单的基于word的baseline方法。接着描述使用文章的分布式表示的一些方法。

4.1 概念

假设:A是关于文章的所有集合。元素的表示依赖于该京城。在4.2节中,a是一个描述的word-based方法的稀疏向量,向量中的每个元素对应于词汇表中的每个词。然而,在4.3节和4.4节中,a是一个关于文章的分布式向量表示。

浏览(Browse)意味着用户访问一篇文章的URL。假设是用户的浏览历史。

会话(Session)意味着用户访问推荐服务并在推荐列表中点击某篇文章。

当用户u点击在我们的推荐服务中的一篇文章时(发生一次会话),他/她会立即访问被点文章的URL(发生一次浏览)。这样,对于浏览之间,从不会超过一个session;因此,该session被称为。然而,用户u也可以不经过我们的服务而访问一篇文章的URL,例如:通过一次Web search。因此,并不总是存在。

由于一个session会对应提供给u的列表,我们通过一个文章列表来表示一个session: 是推荐列表位置的集合,它实际上对应于在该session中屏幕上的展示位置。假设:是点击位置,而是非点击位置。尽管P, , 取决于u和t, 我们会忽略这些下标以简化概念。图3展示了这些概念间的关系。

图3: 浏览历史和session

假设是user state,它取决于等等,表示在浏览之后u的即时偏好。假设:是user state 与文章 a间的相关度,它表示了用户u在时间t上对于文章a的兴趣强度。我们的目标是,构建user-state function:以及相关度函数:,它们需满足下面属性:

…(2)

我们考虑下:请求量很大的真实新闻分发系统的受限响应时间,必须是一个简单函数,并能快速计算。对于所有用户,以及所有文章,由于候选文章会很频繁更新,对相关得分进行预计算是不可能的。因此,有必要在很短的时间内计算它(从访问我们的服务页面到推荐列表到被展示)。然而,我们具有足够多的时间来计算user state function:(从浏览一些文章页面到下一次session发生)。

我们的受限相关函数(restrict relevance function):,表示一个简单的内积关系,,出于这些原因,只有对user state function: 来最小化目标函数:

…(3)

其中是logistic sigmoid function。等式4.1是等式(2)的一个宽松版本。实际上,在点击率上存在一个bias,具体取决于文章的展示位置,我们使用以下包含bias项的目标函数,来纠正这种影响。尽管是一个通过学习决定的参数,它的描述在下面会被忽略,因为它是该模型的一个公共项。

4.2 Word-based模型

我们引入第1节所述的word-based模型作为baseline。

回顾下baseline实现的三个steps。

  • 一篇文章通过它的文本中的词集合进行表示
  • 一个用户通过他/她浏览过的文章所包含的词集合表示
  • 用户与文章间的相关度通过关于在两者间的词共现数的一个线性函数表示

如果文件表示为a,用户函数为F,V是词汇表,定义如下:

…(4)

其中是x中的第v个元素。接着,相关函数变为一个关于参数简单线性模型:

该模型有两个缺点,略。

4.3 Decaying Model

我们引入了一个简单模型来解决上述缺点。模型的两点改变是:

  • 它会使用由第3节构建的分布式表示作为表示向量,而非纯BOW表示。
  • 它会使用根据浏览历史的加权平均,而非最大值。更特别的,我们会增加最近浏览在权重,减小前些天浏览的权重。

总之,可以表示为:

其中,是一个参数向量,它与具有相同维度,是两个向量的elementwise乘法,其中是一个标量,它是一个用于表示时间衰减的超参数。如果是1, 就是简单的平均,无需考虑浏览次序。训练参数只有,它与baseline模型相似。

4.4 Recurrent Models

4.4.1 simple Recurrent Unit.

尽管decaying model要比word-based model要好,它有局限性,与频次、以及受指数衰减限制的遗忘影响成线性关系。

更常见的,由前一state,和前一浏览决定:

因而,我们会尝试使用一个RNN来学习该函数。一个简单的RNN可以公式化为:

其中是激活函数;因而,我们后续使用双曲正切函数:。训练参数是个方阵,bias vector为b,初始state vector ,其中是公共初始值,并不依赖于u。

我们通过end-to-end minibatch SGD的方式对等式 4.1的目标函数进行学习。然而,当输入序列过长时,简单的RNN很难学习,因为会存在梯度消失和爆炸问题。额外的结构被绑定到hidden layer上,以便减轻该问题。

下一部分会介绍使用这些结构的两个模型。

4.4.2 LSTM Unit

LSTM是一种解决梯度消失和爆炸问题的结构。我们可以将LSTM模型公式化为:

其中,是elementwise logistic sigmoid函数,是一个hidden memory state。图4是LSTM模型的一个网络结构。

图4

center flows是从输入(浏览过的文章)到输出(user state)的最重要的flows。输入,,被编码中从文章向量空间到hidden空间(等式5),会合并之前的hidden state(等式6),并编码成文章向量空间(等式7,等式8)作为user state。

另外,该unit具有三个gates,称为input gate(),forget gate(),output gate(go_t)。我们假设每个gate都会各尽其职。input gate会过滤掉不必要的输入来构建一个user state,比如:由突然兴趣造成的。forget gate表示用户在兴趣上的下降。它可以表示比指数衰减(exponential decay)更复杂的forget影响。output gate会过滤掉在下一个session中不关注的成分。

训练参数是权重矩阵,bias向量b,初始化state vectors ,其中是不依赖于u的公共初始化值。

4.4.3 Gated Recurrent Unit(GRU)

是另一种避免梯度消失和爆炸的方法。公式如下:

更准确的,该模型使用一个GRU layer和一个fully connected layer来构建,因为等式(1) 在原始GRU配置中不包含。图5展示了GRU-based模型的结构。

图5

除了省略了一些键头,该结构与LSTM-based模型相似。然而,等式(6)和等式(9)有一个重要的不同点。gate会扮演在LSTM-based模型的两个gates的角色:

…(12)

等式11对于非常长的输入序列具有一个较大值;等式(12)从不会超过该常数。因此,我们认为GRU-based模型比LSTM-based模型能更好地解决梯度爆炸问题。

LSTm-based模型在训练时偶尔会失败,归因于我没在实验中没有使用梯度裁减(gradient clipping)从而造成梯度爆炸。然而,GRU-based模型不需要任何前置处理,不会造成梯度爆炸。

5.实验

5.1 训练数据集

首先,抽样了接近1200w的用户,它们在2016年1月到9月间,在Yahoo!Japan主页上有点击文章的动作。我们会为每个用户抽取一个超过两周时间的日志,随机包含至少一次点击。该抽取方法被用于减轻在特定时间内流行文章的影响。

最后产生的结果,在训练数据中,会有16600w个session,10亿次浏览,200w唯一的文章。我们也创建了相同时期内另一个数据集,并使用它作为验证集来最优化参数。

5.2 测试集

抽样了50w sessions,在2016年10月,用户点击文章超过位置20. 我们为每个session抽取前两周的浏览日志。我们使用位置1到20的文章数据来进行评估,忽略是否实际在屏幕中显示过。这基于我们timeline-based UI的观察。用户会从顶划到底,当点击一篇文章时趋向于离开我们的服务。这就是说,如果我们只使用实际展示的数据进行evaluation,安排实际展示按逆序的方式,进行不成比例地评估也佳。

5.3 离线Metrics

AUC、MRR、nDCG

5.5 结果

参考

http://sci-hub.tw/10.1145/3097983.3098108

在google提出的deep-wide模型之后,华为实验室的人提出了一个DeepFM模型:

1.介绍

现有的模型基本都是偏向于这么几类:低阶特征交叉、高阶特征交叉、或者依赖特征工程。DeepFM可以以一种端到端(end-to-end)的方式来学习特征交叉,无需在原始特征之上做特征工程。deepfm可以归结为:

  • 提出了一种新的NN模型:DeepFM(图1),它集成了FM和DNN的架构。它即可以像FM那样建模低阶特征交叉,也可以像DNN那样建模高阶特征交叉。不同于Wide&Deep模型,DeepFM可以进行端到端训练,无需任何特征工程。
  • DeepFM的wide part和deep part,与Wide&Deep模型不同的是,它可以很有效地进行训练,共享相同的输入以及embedding vector。在Wide&Deep方法中,输入向量(input vector)的size可能很大,因为需要为wide部分人工设计pairwise型特征交叉,复杂度增长很快。
  • DeepFM在benchmark数据上和商业数据上都进行了评测,对现有模型可以有效进行提升。

2.方法

假设训练数据包含了n个样本(x, y),其中x是一个m-fields的数据记录,通常涉及到一个(user,item)的pair,其中表示用户点击行为的label。x也包含了类别型字段(比如:性别,位置)和连续型字段(比如:年龄)。每个类别型字段被表示成一个one-hot编码的向量,每个连续型字段用它原有的值进行表示,或者进行离散化one-hot编码表示。这样,每个实例可以被转换成(x,y),其中 是一个多维向量,其中是向量中的第j个字段。通常,x是高维且十分稀疏的。CTR预测的任务就是构建一个预测模型来估计用户点击的概率。

2.1 DeepFM

图1

我们的目标是同时学到低阶和高阶特征交叉。为此,我们提出了基于NN的FM(DeepFM)。如图1所示,DeepFM包含了两个组件:FM组件和Deep组件,它们共享相同的输入。对于feature i,使用作为权重来衡量1阶的重要性,隐向量用于衡量feature i与其它特征交叉的影响。所有的参数,包括,以及网络参数会进行joint training:

…(1)

其中是预测的CTR,是FM组件的输出,是deep组件的输出。

2.1.1 FM组件

图2:FM组件架构

FM组件是一个因子分解机,它可以学到推荐系统的交叉特征。除了特征间的线性交叉(1阶)外,FM还可以将pairwise(2阶)特征交叉建模成各自特征隐向量的内积。

当数据集是稀疏时,对比起过去的方法,它可以更有效地捕获2阶特征交叉。在之前的方法中,特征i和特征j的交叉的参数只有当两者都出现在同一数据记录时才能被训练。而在FM中,它可以通过隐向量的内积来衡量。由于这种灵活的设计,当只有i(或j)出来在数据记录中,FM也可以训练隐向量Vi(Vj)。因而,对于从未出来或很少出现在训练数据中的特征交叉,可以通过FM很好地学到。

如图2所示,FM的输出是一个求和单元(Addition unit),以及多个内积单元:

…(2)

其中 , (k给定)。求和单元反映了1阶特征的重要性,而内积单元则表示二阶特征交叉的影响。

2.1.2 Deep组件

图3:deep组件的架构

Deep组件是一个前馈神经网络,它用于学习高阶特征交叉。如图3所示,一个数据记录(即一个向量)被feed给NN。对比起图像和音频的神经网络输入数据(它们几乎都是continuous和dense的),CTR预测所需的输入相当不同(需要一个新的网络结构设计)。尤其是,ctr预测的原始特征输入向量通常是高度稀疏的,相当高维,类别型和连续型混杂,以fields进行分组(例如:性别、地域、年龄)。这暗示了:在进一步feed给第一个隐层(the first hidden layer)之前,需要一个embedding layer来将输入向量压缩成一个低维的、dense的实数值向量,否则该网络将很难训练。

图4:embedding layer的结构

图4高亮出从input-layer到embedding layer的子网络结构。我们指出了该网络结果的两个有趣的特征

  • 1) 当不同的field输入向量(input field vectors)的长度可以不同,他们的embeddings则具有相同的size(k)
  • 2) 在FM中的隐特征向量(V)现在作为网络的权重(weight)使用,它可以将input field vectors压缩到embedding vectors中。在[Zhang et al.2016]中,V由FM预训练得到,用于初始化。在DeepFM中,并不会这样做,FM模型是整个学习架构的一部分。这样,我们不需要由FM进行预训练,而是直接以end-to-end的方式进行joint train

embedding layer的output定义如下:

…(3)

其中是第i个field的embedding,m是field总数。接着,被feed给DNN,forward处理如下:

…(4)

其中l是layer的depth,是一个activation function。分别是第l层的output,模型weight,bias。之后,会生成一个dense型实数值特征向量(dense real-value feature vector),最后它会被feed给CTR预测用的sigmoid function:

其中$|H|$是hidden layer的数目。

需要指出的是,FM组件和Deep组件会共享相同的feature embedding,这会带来两个好处:

  • 1) 可以学到从原始特征的低阶交叉和高阶交叉
  • 2) 没必要像Wide&Deep模型那样对输入进行专门的特征工程

2.2 与其它NN关系

图5

这部分比较了CTR预测中,DeepFM与其它存在的deep模型。

FNN

如图5(左)所示,FNN是一个由FM初始化的前馈神经网络。FM预训练策略会产生两个限制:1) embedding参数完全受FM的影响 2) 由于预训练阶段引入的开销,效率会降低。另外,FNN只能捕获高阶特征交叉。

PNN

目标是捕获高阶特征交叉,PNN在embedding layer和第一个hidden layer间引入了一个product layer。根据不同类型的product操作,有三种变种:IPNN,OPNN,PNN,其中IPNN是基于向量内积,OPNN基于外积,PNN同时基于内积和外积。

为了让计算更有效率,作者提出了内积和外积的近似计算:1) 内积通过消除一些神经元来近似计算 2) 外积通过将m个k维feature vector压缩到一个k维vector来近似。然而,我们发现外积比内积的可靠性更差,因为外积的近似计算会丢失很多信息,让结果不稳定。尽管内积更可靠,它仍具有高的计算复杂度,因为product layer的输出连接到第一个hidden layer上的所有神经元(neuron)上。不同于PNN,DeepFM的product layer的output只连接到最后的output layer上(一个neuron)。与FNN类似,所有的PNN都会忽视低阶特征交叉。

Wide & Deep

Wide & Deep由Google提出,用于同时建模低阶和高阶特征交叉。它需要专家对wide部分的输入端进行特征工程(例如:用户安装的app和app推荐曝光的app间的交叉),相反地,DeepFM不需要专家知识,直接从输入的原始特征进行学习。

该模型的一个简单扩展是,通过FM替代LR。该扩展与DeepFM相似,但DeepFM会在FM组件和Deep组件间共享feature embedding。这种共享策略会影响低阶和高阶特征交叉的特征表示,可以更准备地进行建模。

总结

3.试验

数据集:

1) Criteo Dataset: 4500w用户点击记录。13个连续特征,26个类别型特征。 2) ) Company∗(华为) Dataset:收集了该公司App Store的游戏中心连续7天的用户点击记录数据进行训练,下一天数据进行预测。整体数据集有10亿记录。在该数据集中,有app特征(id,类别等),user特征(下载过的app等),context特征(操作时间)

Evaluation Metrics

AUC ((Area Under ROC))和 LogLoss(cross entropy)

具体见paper,不详述。

参考

https://arxiv.org/pdf/1703.04247.pdf

我们来看下intel提出的《Parallelizing Word2Vec in Multi-Core and Many-Core Architectures》。

介绍

word2vec是用于抽取词的低维向量表示的常用算法。包含Mikolov原版在内的state-of-art算法,都已经为多核CPU架构提供了并行化实现,但都基于使用”Hogwild” updates的vector-vector操作,它是内存使用密集型的(memory-bandwidth intensive),并且不能有效使用计算资源。在本paper中,我们提出了“HogBatch”,通过使用minibatching和negative sample sharing来改善在该算法中多种数据结构的复用,从而允许我们使用矩阵乘法操作来表示该问题。我们也探索了不同的技术来将word2vec在同一计算集群上的跨节点分布式计算,并演示了扩展至32个节点上很强的可扩展性。这种新算法特别适合于现代双核/多核架构,特别是intel最新的Knights Landing处理器,并允许我们以接近线性的方式跨多核和多节点扩展计算,并可以达到每秒处理数百万个词,这是目前已知的最快的word2vec实现。

1.从Hogwild到HogBatch

我们提到[5,6]有对word2vec和它的最优化问题的一个介绍。原始的Mikolov的word2vec实现使用Hogwild来并行化SGD。Hogwild是一个并行SGD算法,它会忽略在不同线程上模型更新间的冲突,并允许即使在发生冲突时也能更新处理。使用Hogwild SGD的word2vec的伪代码如图1所示。算法会采用一个矩阵,它包含了每个输入词的词表示;以及一个矩阵,它包含了每个输出词的词表示。每个词被表示为一个D维浮点数组,对应于两个矩阵的某一行。这些矩阵会在训练期间被更新。在图1中,我们选取一个目标词,以及围绕该目标词的N个输入上下文词组成的集合来做示例描述。该算法会在第2-3行上迭代N个输入词。在第6行的循环中,我们选取正样本(第8行的target word),以及一个随机负样本(第10行)。第13-15行为对应选中的输入词和正/负样本计算目标函数的梯度。第17-20行会对中的条目进行更新。伪代码只展示了单个线程;在Hogwild中,第2行的loop会进行线程并行化,在代码中无需任何额外的修改。

算法1

算法1会读取和更新对应于在第6行loop中每轮迭代上的input context和pos/neg words的矩阵M的条目(entries)。这意味着,在连续的迭代间存在一个潜在依赖——他们会发生碰到相同的词表示,从前一轮迭代到该轮迭代完成时,每轮迭代必须潜在等待更新。Hogwild会忽略这样的依赖,并忽略冲突以继续更新。理论上,对比起顺序运行,这会让算法的收敛率下降。然而,对于跨多线程更新不可能会是相同的词的这种情况,Hogwild方法已经得到验证能运行良好;对于大词汇表size,冲突相对较少发生,收敛通常不受影响。

图1: 原始word2vec(左)和我们的实现(右)的并行化schemes

1.1 共享内存并行:HogBatch

然而,原始的word2vec算法主要有两个缺点,极大影响运行时长(runtimes)。第一个是,由于多个线程可以更新相同缓存行(cache line): 它包含了一个特定的模型条目(model entry),这可能在跨多核时会有极大的cache lines冲突。这会导致较高的访问延时和在扩展性上极大的下降。第2个也是更重要的,模型中的大部分位置的更新在Hogwild算法中没有被利用。例如,我们可以很容易看到,对于多个输入词的更新,在模型中会使用相同目标词。通过一次只进行单个更新,该位置信息会丢失,该算法会执行一系列level-1 BLAS操作[1]的点乘(dot-products),它受内存量(memory-bandwidth)限制。下面我们会展示,将这些操作batch成一个level-3 BLAS调用[1],可以有效地利用计算能力和现代多核架构的指令集

我们以2-steps的形式利用位置(locality)信息。受图1的启发,该图左侧展示了原始word2vec的并行化scheme。注意,我们通过给定输入词、以及目标词、同时还有K个负样本来计算词向量。我们不再一次只计算一个更新,而是将这些点乘batch成一个矩阵向量乘法,一个level-2的BLAS操作[1],如图1左侧所示。然而,这不会带来巨大的性能提升。确实,共享输入词向量最可能来自于cache。为了将该操作转化成一个level-3 BLAS操作,我们也需要将(input context words)进行batch。这样做是有意义的(non-trivial),因为在原始word2vec实现中每个input word的负样本可能是不同的。我们因此提出“负样本共享(negative sample sharing)”作为策略,其中,我们跨一个关于input words的较小batch进行共享负样本。这样做允许我们将原始的基于乘法的点乘转换成一个matrix-matrix乘法调用(GEMM),如图1的右侧所示。在GEMM的终点,关于所有输入词、目标/样本词的所有词向量的模型更新,必须被写回。执行matrix-matrix乘法(GEMM)而非点乘,可以利用现代架构的所有计算资源,包含向量单元(vector units)和指令集(instruction set)特性,比如:在Intel AVX2指令集上的multiply-add指令。它允许我们极大地利用优化版的线性代数库。

对于跨GEMM调用的多线程,我们可以遵循”Hogwild”-style哲学——每个线程会执行它们在各自线程上独立的GEMM调用,我们允许线程间潜在的冲突——当在GEMM操作结速更新模型时。我们因此将该新的并行scheme命名为“HogBatch”。

其中,原始的word2vec会在每次点乘后执行模型更新(model updates),我们的HogBatch schema则会在执行模型更新前在单个GEMM调用中做多个点乘运算。需要重点关注的是,位置优化(locality optimization)是次要的,但很有用——我们可以降低模型的更新次数。这是因为GEMM操作会对在输出矩阵的单个条目上的更新做一个reduction(在registers/local cache级别);而在原始的word2vec sche中,这样对于相同条目的更新(例如,相同的输入词表示)会在不同时期发生,会有潜在的冲突发生。在第2节中,我们可以看到相应的结果,它展示了HogBatch比原始word2vec有一个更好的扩展。

1.2 分布式内存并行化

为了扩展word2vec,我们也探索了不同的技术来在同一计算集群的不同节点上将计算分布式化。必要的,我们为分布式计算采用数据并行化。由于篇幅受限,这里跳过细节,可以在完整paper中看到。

2.实验

我们比较了三种不同word2vec实现的性能:

  • 1) 原始google word2vec实现:它基于在共享内存系统上的Hogwild SGD https://code.google.com/archive/p/word2vec
  • 2) BIDMach:它在Nvidia GPU上word2vec的已经最佳性能实现 https://github.com/BIDData/BIDMach
  • 3) 我们的基于Intel架构的实现:包括:1.36-core Intel Xeon E5-2697 v4 Broadwell(BDW) CPUS 2.最新的Intel Xeon Phi 68-core Knights Landing(KNL)处理器。

我们在10亿词的bechmark[3]上训练,使用与BIDMatch相同的参数设置(dim=300, negative samples=5, window=5, sample=1e-4, vocab size=111,5011词)。我们在标准的词相似度bechmark WS-353[4]以及google word analogy benchmark[5]上评估了模型的accuracy。所有的实现都能达到相同的accuracy,由于篇幅限制,我们只展示了在吞吐量上的性能,测试单位:百万words/sec。更多实验细节可以完整paper上介绍。我们的实现:https://github.com/IntelLabs/pWord2Vec

图2:(a)原始word2vec和我们实现在一个Intel Broadwell CPU的所有线程上的可扩展性对比 (b) 在多台Intel Broadwell和Knights Landing节点上,我们的分布式word2vec;与BIDMach在N=1, 4个Nvidia Titan-X节点上的对比

图2展示了我们的算法与原始word2vec,在intel BDW和KNL处理器上跨多核扩展的吞吐量,单位:百万 words/sec。当扩展到多线程时(图2a),我们的算法达到接近线性加速,直到36个线程。作为对比,原始word2vec只能线性扩展到8个线程,接下去会慢很多。结果就是,原始word2vec接近1600w words/sec,而我们的实现接近5800w words/sec,这是原始word2vec的3.6X倍加速。更优的性能可以加强我们最优化的效果,有效利用多核计算资源,降低不必要的线程间通讯。当在多节点上扩展时(图2b),我们的分布式word2vec可以线性扩展到16个BDW节点或者8个KNL节点,并且能维持和原始word2vec相同的accuracy。随着节点数的增加,为了维持一个相当的accuracy,我们需要增加模型的同步频率(synchronization frequency)来消除收敛率的损失。然而,这会在扩展性上造成损失,并在32 BDW节点或16 KNL节点上导致一个次线性扩展(sub-linear scaling)。忽略这一点,我们的分布式word2vec可以达到1亿 words/sec的吞吐,只有1% accuracy的损失。据我所已,这是目前在该benchmark上最佳的性能。最终,表1总结了在不同架构上state-of-art实现的最佳表现。

表1 在不同架构上state-of-art实现的性能对比

3.结论

我们提出了一个高性能的word2vec算法”HogBatch”,它基于共享内存和分布式内存系统。该算法特别适合现代多核架构,尤其是Intel的KNL,在它之上我们发现了目前已知的最佳性能。我们的实现是公开并且通用的。

参考

  • 0.

前一阵子的AlphaGo和围棋很火,当时的AlphaGo在战胜kejie后排名世界第一;最近王者荣耀很火,它的排位赛机制中的内部匹配系统也十分令人诟病。不管是在围棋赛场,还是在多人竞技电子赛场上,排位系统是很重要的。常见的算法有:Elo,TrueSkill™。

Elo在上一篇已经介绍,再来看下TrueSkill算法。更详细情况可见MS的paper。

TrueSkill排名系统是一个为MS的Xbox Live平台开发的基于实力(skill)的排名系统。排名系统的目的是,标识和跟踪玩家在一场比赛中的实力,以便能将他们匹配到有竞争的比赛上(王者中有“质量局”一说,估计是这个意思)。TrueSkill排名系统只使用在一场比赛中所有队伍的最终战绩,来更新在游戏中的所有玩家的实力估计(排名)。

1.介绍

在竞技游戏和体育中,实力排名(Skill rating)主要有三个功能:首先,它可以让玩家能匹配到实力相当的玩家,产生更有趣、更公平的比赛。第二,排名向玩家和公众公开,以刺激关注度和竞技性。第三,排名可以被用于比赛资格。随着在线游戏的到来,对排名系统的关注度极大地提高,因为上百万玩家每天的在线体验的质量十分重要,危如累卵。

在1959年,Arpad Elo为国际象棋开发了一个基于统计学的排名系统,在1970年FIDE采纳了该排名。Elo系统背后的核心思想是,将可能的比赛结果建模成关于两个玩家的实力排名s1和s2的函数。在游戏中,每个玩家i的表现分$ p_i \sim N(p_i; s_i, \beta^{2}) $ ,符合正态分布,其中实力(skill)为$s_i$,相应的方差为$\beta^{2}$。玩家1的获胜概率,由他的表现分$p_1$超过对手的表现分$p_2$的概率来给定:

…(1)

其中$ \Phi$表示零均值单位方差的高斯分布的累积密度(查表法取值)。在游戏结束后,实力排名s1和s2会更新,以至于观察到的游戏结果变得更可能,并保持s1+s2=const常数(一人得分,另一人失分)。假如如果玩家1获胜则y=+1; 如果玩家2获胜则y=-1; 如果平局则y=0. 接着,生成的Elo(线性增长)会更新为:$ s1 \leftarrow s1 + y\Delta, s2 \leftarrow s2 - y \Delta $, 其中:

其中,$\alpha \beta \sqrt{\pi}$表示K因子, $ 0 < \alpha < 1$决定着新事实vs.老估计的权重。大多数当前使用Elo的变种都使用logistic分布(而非高斯分布),因为它对棋类数据提供了更好的拟合。从统计学的观点看,Elo系统解决了成对竞争数据(paired comparison data)的估计问题,高斯方差对应于Thurstone Case V模型,而logistic方差对应于Brad ley-Terry模型。

在Elo系统中,一个玩家少于固定场次的比赛数(比如20场),那么他的排名将被看作是临时的(provisional)。该问题由Mark Glickman的Bayesian排名系统Glicko提出,该系统引入了将一个选手的实力建模成高斯置值分布(Gaussian belief distribution:均值为$ \mu $, 方差为$\sigma^2$)的思想。

实力排名系统的一个重要新应用是多人在线游戏(multiplayer online games),有利于创建如下的在线游戏体验:参与的玩家实力相当,令人享受,公平,刺激。多人在线游戏提供了以下的挑战:

  • 1.游戏结果通常涉及到玩家的队伍,而个人玩家的实力排名对将来后续的比赛安排(matchmaking)也是需要的。
  • 2.当超过两个玩家或队伍竞赛时,那么比赛结果是关于队伍或玩家的排列组合(permutation),而非仅仅是决出胜者和负者。

paper中介绍了一种新的排名系统:TrueSkill,它可以在一个principled Bayesian框架下解决这些挑战。我们将该模型表述成一个因子图(factor graph,第2节介绍),使用近似消息传递(第3节介绍)来推断每个选手实力的临界置信分布(marginal belief distribution)。在第4节会在由Bungie Studios生成的真实数据(Xbox Halo 2的beta测试期间)上进行实验。

2.排名因子图(Factor Graphs)

在一个游戏中,总体有n个选手 {1, …, n},在同一场比赛中有k只队伍参与竞技。队伍分配(team assignments)通过k个非重合的关于玩家总体的子集 $ A_j \in \lbrace 1, …, n \rbrace $,如果 $ i \neq j$, $A_i \bigcap A_j = \emptyset $。比赛结果 $ r := (r_1, …, r_k) \in \lbrace 1, …, k \rbrace $,每个队伍j都会有一个排名$r_j$,其中r=1表示获胜,而$r_i=r_j$表示平局的概率。排名从游戏的得分规则中生成。

给定实际玩家的实力s,以及队伍的分配$A := \lbrace A_1, …, A_k \rbrace$,我们对游戏结果r建模其可能概率:$P(r|s, A)$。从贝叶斯规则(Bayes’ rule)可知,我们获得其先验分布为:

…(2)

我们假设一个因子分解的高斯先验分布为:$p(s) := \prod_{i=1}^{n} N(s_i; \mu_i, \sigma^2)$。每个玩家i在游戏中的表现为: $ p_i \sim N(p_i; s_i, \beta^2)$,以实力$ s_i $为中心,具有方差为$\beta^2$。队伍j的表现$t_j$被建模成其队员的表现分的总和:$ t_j := \sum_{i \in A_j} p_i $。我们以排名的降序对队伍进行重排序:$r_{(1)} \leq r_{(2)} \leq … \leq r_{(k)}$。忽略平局,比赛结果r的概率被建模成:

也就是说,表现的顺序决定了比赛结果的顺序。如果允许平局,获胜结果$r_{(j)} < r_{(j+1)} $需要满足 $r_{(j)} < r_{(j+1)} + \epsilon $,那么平局结果 $r_{(j)} = r_{(j+1)} $ 需要满足 $ |r_{(j)} - r_{(j+1)} | \leq \epsilon $,其中$\epsilon > 0$是平局临界值,可以从平局的假设概率中计算而来。(见paper注1)

注意:”1与2打平”的传递关系,不能通过关系 $ | t_1 - t_2| \leq \epsilon$进行准确建模,它是不能传递的。如果$ | t_1 - t_2| \leq \epsilon$ 和 $ | t_2 - t_3| \leq \epsilon$,那么该模型会生成一个三个队伍的平局,尽管概率满足$ | t_1 - t_3| \leq \epsilon$

在每场游戏后,我们需要能报告实力的评估,因而使用在线学习的scheme涉及到:高斯密度过滤(Gaussian density filtering)。后验分布(posterior)近似是高斯分布,被用于下场比赛的先验分布(prior)。如果实力与期望差很多,可以引入高斯动态因子 $ N(s_{i,t+1}; s_{i,t}, \gamma^2) $,它会在后续的先验上产生一个额外的方差成分$\gamma^2$。

例如:一个游戏,k=3只队伍,队伍分配为 $ A_1 = \lbrace 1 \rbrace $, $ A_2=\lbrace 2,3 \rbrace $,$ A_3 = \lbrace 4 \rbrace $。进一步假设队伍1是获胜者,而队伍2和队伍3平局,例如:$ r := (1, 2, 2) $。我们将产生的联合分布表示为:$ p(s,p,t |r,A)$,因子图如图1所示。

图1: 一个TrueSkill因子图示例。有4种类型的变量:$s_i$表示所有选手的实力(skills),$p_i$表示所有玩家的表现(player performances),$ t_i $表示所有队伍的表现(team performances),$ d_j $表示队伍的表现差(team performance differences)。第一行因子对(乘:product)先验进行编码;剩下的因子的乘积表示游戏结果Team 1 > Team 2 = Team 3的似然。箭头表示最优的消息传递schedule:首先,所有的轻箭头消息自顶向底进行更新。接着,在队伍表现(差:difference)节点的schedule按数的顺序进行迭代。最终,通过自底向顶更新所有平局箭头消息来计算实力的后验。

因子图是一个二分图(bi-partite graph),由变量和因子节点组成,如图 1所示,对应于灰色圆圈和黑色方块。该函数由一个因子图表示————在我们的示例中,联合分布 $ p(s,p,t |r,A) $ ————由所有(潜在)函数的乘积组成,与每个因子相关。因子图的结构给定了因子间的依赖关系,这是有效推断算法的基础。回到贝叶斯规则(Bayes’ Rule)上,给定比赛结果r和队伍关系A,最关心的是关于实力的后验分布$p(s_i | r,A)$。$p(s_i | r, A)$从联合分布中(它集成了个人的表现{pi}以及队伍表现{ti})进行计算。

图2: 对于平局临界值$\epsilon$的不同值的近似临界值的更新规则。对于一个只有两只队伍参加的比赛,参数t表示胜负队伍表现的差值。在胜者列(左),t为负值表示一个意料之外的结果会导致一个较大的更新。在平局列(右),任何队伍表现的完全误差都是令人意外,会导致一个较大的更新。

3.近似消息传递(Approximate Message Passing)

在因子图公式中的和积算法(sum-product algorithm)会利用(exploits)图的稀疏连接结构,来通过消息传递(messgage passing)对单变量临界值(single-variable marginals)执行有效推断(ecient inference)。连续变量的消息传递通过下面的方程表示(直接符合分布率):

…(3)

…(4)

…(5)

其中$F_{v_k}$表示连接到变量$v_k$的因子集,而 $ v_{\backslash j} $则表示向量v除第j个元素外的其它成分。如果因子图是无环的(acyclic),那么消息可以被精确计算和表示,接着每个消息必须被计算一次,临界值 $ p(v_k) $可以借助等式(3)的消息进行计算。

从图1可以看到,TrueSkill因子图实际上是无环的,消息的主要部分可以被表示成1维的高斯分布。然而,等式(4)可以看到,从比较因子($I(\cdot > \epsilon) $)a或($ I(\cdot \leq \epsilon)$)到表现差$d_i$去的消息2和5并不是高斯分布的——实际上,真实的消息必须是(非高斯分布)因子本身。

根据期望传播算法(EP: Expectation Propagation),我们将这些消息作近似,通过将临界值$ p(d_i)$通过变化的矩匹配(moment matching)产生一个高斯分布$ \hat{p}(d_i) $,它与$ p(d_i) $具有相同的均值和方差。对于高斯分布,矩匹配会最小化KL散度。接着,我们利用(3)和(5)得到:

…(6)

表1给出了所有的更新方程,这些等式对于在TrueSkill因子图中的推断是必要的。top 4的行由标准的高斯积分产生。底部的规则是由上述的矩匹配(moment matching)产生。第4个函数是对一个(双倍)截断式高斯分布的均值和方差的加乘校正项:

表1: 对于缓存的临界值p(x)的更新方程、以及对于一个TrueSkill因子图中所有因子类型的消息$m_{f \rightarrow x}$。我们根据标准参数来表示高斯分布 $ N(\cdot; \mu, \sigma) $:准确率(precision) $ \pi := \delta^{-2} $,准确率调和平均(precision adjusted mean)$ \tau := \pi \mu $。以及关于该消息或从(6)获得的临界值的缺失的更新方程

由于消息2和消息5是近似的,我们需要对所有消息在任意两个近似临界$\hat{p}(d_i)$的最短路径上进行迭代,直到该近似临界值几乎不再改变。产生的最优化的消息传递schedule可以在图1中发现。(箭头和大写)

4.试验和在线服务

4.1 Halo 2 Beta Test

为了评估TrueSkill算法的表现,我们在Bungie Studios的游戏Xbox Halo 2的beta测试阶段生成的游戏结果数据集上进行试验。数据集包含了成千上万的游戏结果,包含4种不同的游戏类型:8个玩家自由对抗(自由模型),4v4(小队模式), 1v1, 8v8(大队模式)。每个因子节点的平局临界$\epsilon$通过统计队伍间平局的比例(“期望平局概率”)进行设置,将平局临界$\epsilon$与平局的概率相关联:

其中n1和n2分别是两只队伍的玩家数目,可以与图1中的节点$ I(\cdot > \ epsilon)$或 $ I(|\cdot| \leq \epsilon)$相比较。表现的方差$ \beta^2 $和动态的方差 $ \gamma^2 $被设置成标准值(见下一节)。我们使用一个高斯表现分布(1)和 $ \alpha=0.07$在TrueSkill算法上与Elo作对比;这对应于Elo中的K因子等于24, 该值被认为是一个较好且稳定的动态值。当我们必须处理一个队伍的比赛时,或者超过两个队伍的比赛时,我们使用“决斗(duelling)”技巧:对于每个玩家,计算$ \Delta $,对比其它所有玩家,基于玩家的队伍结果、每个其它玩家的队伍结果、并执行一个$ \Delta $平均的更新。在最后一节描述的近似消息传递算法相当有效;在所有我们的实验中,排序算法的运行时在简单的Elo更新运行时的两倍以内。

预测表现(Predictive Performance) 下表表述了两种算法(列2和列3)的预测error(队伍在游戏之前以错误顺序被预测的比例)。该衡量很难被解释,因为排名(ranking)和比赛安排(matchmarking)会相互影响:依赖于所有玩家的(未知的)真实实力,最小的预测error可以达到最大50%。为了补偿该隐式的、未知的变量,我们在ELO和TrueSkill间安排了一个对比:让每个系统预测尽可能匹配的比赛,将它们应用在其它算法上。该算法会预测更多正确的比赛结果,能更好地匹配。对于TrueSkill,我们使用比赛安排标准(matchmaking criterion),对于Elo,我们使用在Elo得分中的差:$s_1 - s_2$。

匹配质量

排名系统的一个重要应用是,能够尽可能匹配到相似实力的玩家。为了比较Elo和TrueSkill在该任务上的能力,我们对比赛基于匹配质量(match quality)作划分,将两个系统应用到每场比赛上。如果匹配很好,那么很可能观察到平局。因而,我们可以画出平局的比例(所有可能的平局)在每个系统分配的匹配质量顺序上进行累积。在该图中,右侧可知,对于“自由模式(Free of All)”和1v1模式(Head to Head),TrueSkill比Elo更好。而在“4v4模式(Small Teams)”Elo比TrueSkill更好。这可能是因为额外的队伍表现模型(在该模式下大部分比赛是夺旗赛模式(Capture-the-Flag))的影响。

胜率(Win Probability)

一个排名系统的感观质量,可以通过获胜比例来衡量:如果获胜比例高,那么该玩家在该排名系统中分配太弱的对手是错误的(反之亦然)。在第二个试验中,我们处理了Halo 2数据集,但舍弃了那些没有达到一定匹配质量阈值的比赛。对于被选中的比赛,取决于每个玩家所玩的最低数目的比赛数,我们计算了每个玩家的获胜概率,来测量获胜概率与50%(最优获胜比例)的平均误差(越小越好)。产生的结果如图所示(在1v1模式下),它展示了TrueSkill模式下,每个参加了比较少比赛的玩家,会获得更公平的匹配(胜率在35%-64%)。

收敛性能(Convergence Properties)

最后,我们画出了两个典型的、在自由模式下(Free for All)两个最高排名的玩家的收敛轨迹:(实线:TrueSkill;虚线:Elo)。如上所见,TrueSkill会自动选择正确的learning rate,而Elo只会对目标实力做较慢的收敛。实际上,TrueSkill与信息论极限(information theoretic limit )更接近: nlog(n)位来编码n个玩家的排名。对于8个玩家的比赛,信息论极限是 $ log(n) / log(8) \approx 5$,每个玩家平均5场比赛,而这两位观察到的玩家的收敛约等于10场比赛!

4.2 Xbox 360 Live上的TrueSkill

微软的XBox Live主要是在线游戏服务。世界各地的玩家一起玩,他们具有不同的成百上千个头衔。在2005.9, XBox Live具有超过200w的订阅用户,在该服务上花费13亿个小时。新的改进版Xbox 360 Live服务使用TrueSkill算法来提供自动玩家排名(automatic player rating)和比赛安排(matchmaking)。该系统会每天处理成千上万的游戏比赛,使它成为贝叶斯推断(Bayesian inference)的最大应用。

在Xbox Live上,我们使用了一个数值范围,由先验$ \mu_0=25$和$ \delta_0^2=(25/3)^2$给定,对应于接近99%的正向实力概率。表现的方差由$\beta^2 = (\sigma_0/2)^2$给定,动态方差则选择$ \gamma^2 = (\sigma_0 / 100)^2 $。一个玩家i的TrueSkill实力,目前被表现为一个保守的实力估计,由低于1%的分位数$ \mu_i-3\delta_i$给定。该选择确保了排行榜(一个根据$\mu-3\delta得到的所有玩家列表$)的top榜单只可能被那些具有较高实力、更高确定度(certainty)的玩家占据,它们从$ 0=\mu_0 - 3 \delta_0$开始逐步建立。对玩家的成对比赛安排(Pairwise matchmaking),使用从相对最高可能的平均概率的平局概率派生而来的匹配质量准则来执行,取极限$ \epsilon \rightarrow 0 $,

…(7)

注意,比赛安排过程(matchmaking process)可以被看成是一个逐次实验设计(sequential experimental design)的过程。因为一个匹配质量由它的结果的不可预知性(unpredictability)决定,比赛安排和发现最有益匹配的目标是为了均衡(align)。

另一个吸引人的副产品是,我们有机会在成千上万的玩家上学习TrueSkill的运转。而我们只开始分析大量的结果数据,已经有一些有趣的观察结果。

  • 1.比赛随有效实力等级的数目的不同而不同。机遇型游戏(Games of chance)(例如:单场双陆棋比赛或UNO)具有更窄的实力分布,而凭实力取胜的游戏(Games of skill)(例如:半实况的竞速比赛)具有更宽的实力分布。
  • 2.比赛安排(Matchmaking)和实力展示(skill display)会对玩家产生一个反馈循环,玩家经常会看它们的实力估计作为表现的奖惩。一些玩家试图通过:不玩、小小选择对手、或者作弊来保护或提升它们的实力排名。
  • 3.如果是新玩家,通常会在最初的几场比赛时失利,总的实力分布会偏移到先验分布之下。而当实力会初始化重置后,我们发现更准的比赛安排的效果会消失。

5.结论

TrueSkill一是个全局部署Bayesian的实力排名系统,它基于在因子图的近似消息传递。比起Elo系统,它具有许多理论和实际的优点,并在实践中运行良好。

而我们主要关注TrueSkill算法,在因子图框架内可以开发许多更多有趣的模型。特别的,因子图公式可以被应用到受限制的分类模型族(the family of constraint classication models),它包含了更宽范围的多分类和排名算法。另外,作为对个人实体进行排名的替代,你可以使用特征向量来构建一个排名函数,例如,对于网页可以表述成bags-of-words。最终,我们计算运行一个关于棋类游戏的完全时间独立的EP分析,来对获得关于象棋大师的TrueSkill排名。

6.实现

trueskill的一个python实现:http://trueskill.org/

另外,MS还提供了一个在线模拟器,这个可以结合着去理解:http://boson.research.microsoft.com/trueskill/rankcalculator.aspx

关于TrueSkill的数学基础,详见:http://www.moserware.com/assets/computing-your-skill/The%20Math%20Behind%20TrueSkill.pdf

参考