前一阵子的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

参考

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

先来看下Elo算法。

1.介绍

Elo排名系统(Elo rating system)用于计算竞技比赛(比如:chess)的相对技能等级。它由 Arpad Elo创建。Elo系统(Elo system)的发明最初用于改善棋类排名系统,但后来也被用于多人竞技电子游戏:实况足球,等。

两个选手(player)在排名系统的不同,可以用来预测比赛结果。两个具有相同排名(rating)的选手相互竞争时,不管哪一方获胜都会得到相同的得分(score)。如果一个选手的排名(rating)比他的对手高100分,则得64%;如果差距是200分,那么排名高的选手的期望得分(expected score)应为76%。(可以理解为,获胜的机率更高)

一个选手的Elo rating由一个数字表示,它的增减依赖于排名选手间的比赛结果。在每场游戏后,获胜者将从失利方获得分数。胜者和败者间的排名的不同,决定着在一场比赛后总分数的获得和丢失。在高排名选手和低排名选手间的系列赛中,高排名的选手按理应会获得更多的胜利。如果高排名选手获胜,那么只会从低排名选手处获得很少的排名分(rating point)。然而,如果低排名选分爆冷获胜(upset win),可以获得许多排名分。低排名选手在平局的情况下也能从高排名选手处获得少量的得分。这意味着该排名系统是自动调整的(self-correcting)。长期来看,一个选手的排名如果太低,应比排名系统的预测做得更好,这样才能获得排名分,直到排名开始反映出他们真正的实力。

2.历史

Arpad Elo是大师级棋手,参加了美国国际象棋协会(USCF)。USCF原先使用由Kenneth Harkness一个数值排名系统,允许成员以分值的形式来记录他们的私人成绩,而非比赛的胜负场次。Harkness system 相当公平,但在一些情况下,会导致许多人认为是不准确的排名。为了USCF,Elo提出了一种新的基于统计学基础的系统。

Elo的核心假设是,每个选手在每场国际象棋上的表现水平是一个正态随机变量。尽管一个选手从这一场到下一场的表现或好或差,Elo假设每个选手的表现的均值随时间的变化很慢。Elo认为:一个选手的实力(true skill),就是选手表现(player’s performance)的随机变量的均值。

有必要做进一步假设,因为国际象棋的表现仍然是难以测量的。我们不能看到一连串的移动操作后就说:“该表现为2039分.” 比赛表现(Performance)只能从胜、平、负中看出。因此,如果一个选手赢下一场比赛,那么对于这场比赛来说,该选手比对手的表现的水平更高。相反的,如果选手失利,则认为表现的水平更低些。如果比赛平局,两个选手的水平相接近。

对比起胜或负,Elo没有精确指出两者在平局时的表现的接近程度。但他认为每个选手在表现上都有一个不同的标准差(standard deviation),他做了一个简化的假设。

为了简化计算,Elo提出了一种简单的方法来估计在模型中的变量(比如:每个选手的真实实力true skill)。计算相当简单,可以从表中进行,一个选手所期望获胜的场次,基于他的排名和对手排名决定。如果一个选手比所期望的得到更多获胜场次,他们的排名应向上调整,如果比期望的获胜场次较少,则向下调整得分。然而,这些调整与超出或少于期望胜场数的场次成线性比例。

从现代的角度看,Elo的简化版假设是没必要的,因为幂计算(power)并不昂贵,被广泛采用。再者,在简化版模型中,许多有效的估计技术很有名。最著名的有Mark Glickman,提出使用许多复杂的统计机制来估计相同的变量。另外,Elo system的计算简单性被证明是宝贵财富之一。有了便携计算器的帮助,一个选手可以计算接下来的正式发布的排名,误差在一分之内,从而帮助理解排名是公平的。

3. elo’s scheme的实现

USCF在1960年实施Elo的建议,该系统快速获得认可,比Harkness rating system更准,更公平。Elo的系统在1970年被世界国际象棋联盟(FIDE)采纳。Elo在1978年出版的《The Rating of Chessplayers,Past and Present》一书中详细描述了它的工作。

随后的统计测试已经表明,国际象棋的水平表现几乎不是正态分布。选手越弱,但获胜机率总是大于Elo模型的给出的预测机率。因此,USCF和一些国际象棋网站采用了基于logistic分布的公式。当在国际象棋中使用logistic分布时,已经发现了极大的统计异常现象。FIDE继续使用由Elo提出的排名差距表(rating difference table)。该表使用期望0, 标准差为2000/7进行计算.

在某种程度上,正态分布和logistic分布中的点,是在连续分布(a spectrum of distributions)上的任意点,它们都能良好工作。实际上,这些分布对许多不同的游戏都能良好运转。

3.1 不同的排名系统

短语”Elo rating“经常被用来表示由FIDE计算的一个选手的chess rating。然而,该用法是有冲突和混淆的,因为Elo的思想已经被许多组织采用:FIDE、ICC、FICS、PCA、Yahoo!Games。每个组织都有自己的实现,都不会按原始的Elo建议来实现。上述所有的ratings都可以认为是Elo ratings。

每个棋手由不同的组织授于的rating,比如:在2002年8月,Gregory Kaidanov具有FIDE rating: 2638分;具有USCF rating:2742分。注意,这些不同组织的Elo ratings不总是拿来直接对比的。例如,一个人可以有FIDE rating 2500分,而他的USCF rating可能接近2600分,ICC rating可能在(2500, 3100)分之间。

3.2 FIDE ratings

对于顶级选手,最重要的rating是FIDE rating。自2012年7月开始,FIDE每月更新顶级选手列表。

以下是2015年7月FIDE rating列表给出的统计:

  • 5323个选手具有active rating在2200-2299间,与候选大师(Candidate Master)的头衔相对应。
  • 2869个选手具有active rating在2300-2399间,与FIDE大师的头衔相对应
  • 1420个选手具有active rating在2400-2499间,大多数具有国际大师(International Master)或国际特级大师(International Grandmaster)称号。
  • 542个选手具有active rating在2500-2599间,它们具有国际特级大师(International Grandmaster)称号.
  • 187个选手具有active rating在2600-2699间,它们具有国际特级大师(International Grandmaster)称号。
  • 37个选手具有active rating在2700-2799间
  • 4个选手的rating超过2800.

FIDE rating的最高分为2882, Magnus Carlsen在2014年5月拿到。

3.3 表现排名(Performance rating)

表现排名分(Performance rating)是一个假设排名分,它只从一些赛事中产生。一些国际象棋组织使用”algorithm of 400”来计算表现排名(Performance rating)。根据该算法,表现排名(Performance rating)的计算根据下面的方式进行:

  • 1.对于每场胜利,你对手的rating加上400
  • 2.对于每次失利,你对手的rating减去400
  • 3.然后除以场次.

示例:2场胜利,2场失利

因而可以用以下的公式来表述:

例如:如果你击败了一个具有Elo rating=1000的选手,那么你的表现排名为:

如果你击败了两个Elo ratings=1000的选手,那么:

如果和一选手打平了,则:

这是一个简化版本,因为它没有采用K因子(该因子会在下面介绍),但它提供了一种简单的方式来获得PR(Performance Rating)的估计。

FIDE则通过下面公式的均值来计算performance rating:

对手排名平均值(Opponents’ Rating Average) + 排名差值(Rating Difference)

排名差值 (Rating Difference) $ d_p $基于一个选手的比赛得分百分数p,它被用作是在一个lookup table中的key值,其中p可以简单认为是取得得分的场数除以比赛场数。注意,最好的表现是800分。完整的表可以在FIDE handbook中找到。这里提供了一个简化版本的表。

p $d_p$
1.00 +800
0.99 +677
0.9 +366
0.8 +240
0.7 +149
0.6 +72
0.5 0
0.4 -72
0.3 −149
0.2 −240
0.1 −366
0.01 −677
0.00 −800

3.4 FIDE比赛类别

FIDE会根据选手的平均等级(average rating)将比赛分类。每个类别大多25个分值。类别1的平均等级分为2251-2275, 类别2的平均等级分为2276-2300等。对于女子比赛,类别则是更低的200, 因而类别1平均等级分为2051-2075等。最高级别的比赛是类别23,平均从2801-2825,为顶级的类别。

Category Minimum Maximum
14 2576 2600
15 2601 2625
16 2626 2650
17 2651 2675
18 2676 2700
19 2701 2725
20 2726 2750
21 2751 2775
22 2776 2800
23 2801 2825

3.5 实时排名(Live ratings)

FIDE每个月会更新它的rating列表。非官方的“Live ratings”会在每场比赛之间计算选手的ratings变化。这些Live ratings基于之前发布的FIDE ratings,因而,一个选手的Live rating和FIDE rating相对应。

3.6 USCF排名

  • 2400及以上:Senior Master
  • 2200-2399: National Master
    • 2200-2399, 300场比赛在2200分以上:Original Life Master
  • 2000–2199: Expert
  • 1800–1999: Class A
  • 1600–1799: Class B
  • 1400–1599: Class C
  • 1200–1399: Class D
  • 1000–1199: Class E
  • 800–999: Class F
  • 600–799: Class G
  • 400–599: Class H
  • 200–399: Class I
  • 0–199: Class J

总之,初学者在800分左右,中级选手在1600左右,职业选手在2400左右。

3.6.1 USCF使用的K因子

在USCF rating system中的K-factor, 可以通过将800除以该选手获得排名的有效场次$N_e$加上选手在比赛中完成的比赛场次m。

3.6.2 Rating底数(rating floors)

对于所有ratings,USCF维护着一个绝对的rating底数:100。这样,任何成员都不会在100分以下,不管他们的表现在USCF中是否受到过处罚。然而,各选手可以有更高的绝对rating底数,可以使用以下公式计算:

其中,$N_W$是获胜场次,$N_D$是平局场次,$ N_R $是选手完成三场或更好排名的赛事场次数目。

对于那些达到很高排名的有经验选手,会有更高的rating底数。这些更高的rating底数的存在,从ratings=1200开始到2100分,按100分递增(1200, 1300, 1400, …, 2100)。一个玩家的rating底数会采用它巅峰时的rating来计算,减去200分,接着下舍到最接近的rating底数上。例如,一个选手达到了一个peak rating=1464,它的rating floor=1464-200=1264, 向下舍入到1200. 在该模式下,只有Class C级别及以上的选手,具有更高的rating floor。所有其它的选手几乎都有floor=150。

比起上述标准的模式,还有两种方法来达到更高的rating floor。如果一个选手达成了Original Life Master的rating,它的rating floor会设置成2200. 该头衔是唯一的,不认可USCF头衔的其它组织会生成一个新的floor。对于rating在2000分以下的,在比赛中本不具备资格的选手,赢得2000美元及以上的现金奖,会提升选手的rating floor接近100分左右。例如,如果一个rating=1750的选手赢得4000美金,他会达到一个rating floor=1800。

4. 理论

成对比较(Pairwise comparisons)奠定了Elo rating方法的基础。

4.1 数学详解

表现(Performance)并不能被绝对化地衡量;它涉及到和其它选手比赛时的胜、负、平局。选手的排名(ratings)依赖于它们对手的排名,以及与他们的比赛结果。两个选手间排名的不同,决定了他们之间的期望得分的一个估计。对排名进行求平均和展开太过简单粗暴。Elo建议归一化排名(scaling ratings),因而在国际象棋中200个排名分的差异意味着,更强的选手会有一个接近0.75的期望得分(expected score:基本上是一个期望平均分),USCF初始会给普通的俱乐部选手1500排名分。

一个选手的期望得分(expected score),是他的获胜概率加上平局概率的一半。这样,期望得分=0.75就可以表示有75%的机会获胜,25%的机会失败,0%的机会平局。在另一个极端,它可以表示50%的机会获胜,0%的机会失败,50%的机会平局。平局的概率,在Elo的系统中未被指定。平局可以看成是一半获胜,一半失败(50% * 0.5)。

如果选手A具有排名分$R_A$,选手B具有排名分$R_B$,选手A的期望得分(expected score)的准确公式为(使用logistic曲线):

选手B的期望得分与选手A相类似:

也可以表示成:

其中,$ Q_A = 10^{R_A/400}$和 $ Q_B = 10^{R_B/400}$。注意,在后一个case中,两者使用相同分母。这意味着只需要通过学习分子,我们就能得到选手A的期望得分比选手B的期望得分大$ Q_A / Q_B$倍。每领先对手400排名分的优势,对比起对手的期望得分,该选手的期望得分会大10倍。注意,$ E_A + E_B = 1$,实际上,因为每个选手的真实实力是未知的,期望得分会使用选手的当前排名分来计算。

当一个选手的实际比赛得分超过他的期望得分,Elo系统会认为:该选手的排名过低了,需要向上调整。相似的,当一个选手的实际比赛得分低于他的期望分值时,该选手的排名分也会向下调整。Elo的原始观点是,一个选手高于或低于期望得分的量,成线性比例调整。每场比赛的最大可能调整,称为K因子(K-factor),对于Masters被设置成K=16, 对于较弱的选手设置成K=32.

假设选手A的期望得分为$E_A$,实际得分为$S_A$。排名更新公式为:

该更新会在每场比赛或锦标赛后,或者在合适的排名周期后被执行。举个例子:假设选手A具有rating=1613, 他会进行5轮的锦标赛。他输给了一个rating=1609的选手,和rating=1477的选手打平,分别战胜了rating=1388, 1586的选手,然后又输给了一个rating=1720的选手。该选手的实际得分为(0 + 0.5 + 1 + 1 + 0) = 2.5. 期望得分为:(0.51 + 0.69 + 0.79 + 0.54 + 0.35) = 2.88. 因此,该选手新的排名为(1613 + 32 *( 2.5 - 2.88)) = 1601, 假设使用K=32.

该更新过程是排名的核心,被使用在:FIDE, USCF, Yahoo! Games, ICC, FICS。 然而,每个组织都会采用不同的方式来处理自身排名中的不确定特性,尤其是新人的排名,以及处理排名的膨胀和通缩问题。新的选手会被分配临时排名,它们比已经确立的排名调整起来更剧烈。

这些排名系统所使用的方式也会被用到其它竞技比赛排名上——例如,国际足球比赛。Elo rating也可以应用在没有平局(只有胜负)的游戏中。

4.2 数学要点

Elo有三个主要的数据要点:正确的曲线,正确的K因子,临时周期的简单计算。

更精确的分布模型

USCF最早采用的是正态分布。它们发现实际结果与此并不太准确,尤其是对更低排名的选手。于是切换到logistic分布模型,USCF发现会提供更好的拟合。FIDE也使用logistic分布的近似。

更精确的K因子

第二个注意点是使用正确的K因子。国际象棋统计学家Jeff Sonas认为:在Elo中使用的原始的K=10(对于2400分以上的选手)是不准确的。如果K因子系数设置过大,排名会对最近少量的赛事过于敏感,每场比赛后大量分值会被交换。如果K值设置过小,则敏感度最低,该系统则不能对一个选手表现出的实际水平快速做出变化。

Elo的原始K因子估计,没有利用大数据量和统计证据。Sonas则指出:K因子=24(对于2400分以上的排名选手)更准确,即可以对将来表现做预测,也对现有表现更敏感。

固定的国际象棋网站基于排名范围来避免三个级别的K因子的交错。例如,除了当选手与临时选手比赛的情况之外,ICC会采用全局的K=32。USCF则根据三个主要的排名范围来调整K因子:

  • 小于2100以下的选手:K因子=32
  • (2100,2400)区间的选手:K因子=24
  • 大于2400的选手:K因子=16

FIDE则使用另外一套。详见wiki.

4.3 实际注意事项

游戏活跃度 vs. 排位保护

在一些情况下,排名系统会阻止那些希望保护排名的玩家的比赛活跃度。为了阻止玩家长期在高排位上,2012年,由英国特级大师John Nunn提出了一个提议来选择国际象棋世界冠军预选赛的要求:需包含一个活跃奖分(activity bonus),还应该结合排名。

在象棋世界之外,为担心选手躲避竞争来保护他们的排名,威世智(Wizards of the Coast)游戏公司在<万智牌:Magic: the Gathering>游戏比赛中放弃了Elo系统,采用了它们自己设置的“Planeswalker Points”。

选择匹配

一个更微妙的注意点关于配对问题(pairing)。当选手可以选择他的对手时,他们可以选择失败概率小些的对手,以便获胜。特别是2800分以上的选手,他们可以选择低风险的对手,包括:选择通过电脑可知在某种程度上可大概率战胜的;选择被高估的对手;或避免与排名差不多、保持头衔的强劲对手交锋。在选择高估对手的类别(category)中,排名系统的新进入者可能只参加过50场比赛,理论上他们会在临时分上被高估。当已排名玩家vs一个新进入排名玩家获胜时,ICC通过分配一个更低的K因子,从而对该问题会做补偿。

因此,Elo ratings online仍采用了一个有用机制来提供一个基于对手排名的排名。它总体上是可信的,然而,仍存在至少超过两个的主要问题:引擎滥用(engine abuse),选择性配对对手。

ICC最近也引入了自动匹配排名(“auto-pair”),它基于随机配对(random pairing),每次连续获胜,可以确保匹配到一个统计学上更难的对手:他也连续赢了x场比赛。因为潜在涉及到上百个选手,这会创建一些充满激烈竞争的主要大型Swiss赛事的挑战,全胜者将遭遇全胜者。该方法会为高排名选手的匹配最大化风险,例如,他将面对排名3000以下的选手的激烈对抗。它本身是一个分隔的排名系统,在1分(“1-minute”)和 5分(“5-minute”)的rating类别之下。最高排名达到2500是相当罕见的。

排名分膨胀(rating inflation)/通缩(deflation)

在排名系统中所有选手的平均排名分的增加或减少,通常被称为“排名膨胀(rating inflation)”或”排名通缩(rating deflation)”。例如,如果存在膨胀,一个当前排名分2500,实际上意味着少于之前的历史排名分为2500, 对于通缩反之亦然。当存在膨胀或通缩时,使用排名分来比较不同时代的选手是相当困难的。

通常认为,至少在顶级水平上,当前排名分是膨胀的。正如2009年9月 Nigel Short 所说:“最近的ChessBase上由Jeff Sonas所写的关于排名分膨胀的文章指出:我在1980年代的排名分在现在的水平近似2750分。”(注:Short在1980的最高排名分是1988年的2665分,相当于世界第三。而当他做出该评论时,2665分只够排第65名,而2750分则只能排第10位。在2012年的FIDE排行榜上,2665只够排第86位,而2750分只够排第13位)

有人曾提议:整体排名分的增加会影响更高的实力。国际象棋电脑的到来,可以对过往象棋大师的绝对实力,基于他们的历史战绩做出一定程度的目标评测,但这也是对选手的位置变动像电脑般的一个衡量,而非仅仅是他们有多强的一个衡量。

排名分超过2700的人数在增加。在1979年左右,只有一个选手(Anatoly Karpov)有这么高的排名分。在1992年,只有8位选手能达到2700分。而在1994年增加到了15个,2009年增加到了33个,2012年增加到了44个。当前的精英选手的benchmark需要超过2800分。

造成膨胀的一个可能原因是:排名分底数(rating floor),它长期被设置在2200分,如果一个选手掉分超过它,他们会被排行榜移除。结果,在水平低于该底数下的选手,只能当他们被高估时才会出现在排行榜上,他们会造成给排名分池子注入(feed)得分。在2000年,top 100的平均排位分是2644. 而2012年,它增加到2703.

在一个纯粹的Elo系统中,每个比赛都会产生排名分的等价交换。如果获胜方获得N个排名分,失败方则丢掉N个排名分。当比赛被进行和排名时,这会阻止得分新进入或离开该系统。然而,排名分低的新选手会进入该系统,而高排名分的有经验选手也会退出该系统。因此,一个长期运行的严格进行等价交换的系统会导致排名分通缩(rating deflation)

在1995年,USCF承认,一些年轻的选手,比排名系统所跟踪的提升得更多。结果,有稳定排名分的选手开始从对阵这些年轻未排名的选手上丢掉排分名。一些更年长的已排名选手很沮丧,认为这种排分不公平,其中一些因此退出了国际象棋。

与通缩对抗

由于当发生膨胀和通缩时所产生的巨大差异,为了与通缩对抗,大多数Elo ratings的实现都具有一个机制来向该系统注入得分,以保证一直能维持相当的排名分。FIDE具有两种通货澎涨解决机制。第一种,在“排名分底数(ratings floor)”下的表现不会被跟踪,因而,一个实力在底数之下的选以可能会被低估或高估,从不会被正确排名。第二种,已排名选手和高排名选手具有一个更低的K因子。新选手具有K=30, 在30场比赛后会下降到K=15, 当达到2400时K=10.

美国的当前系统,包含了一个获奖分机制,它会将排名分feed给系统,以便跟踪未提升的选手,为不同的选手设置不同的K值。在挪威所使用的方法,在初段和高段间会不同,对于年轻选手使用一个更大的K因子,当他们的表现得分超出预期时会有100%增强排名分。

在美国的排分名底数(rating floors),可保证一个选手从不会掉到特定下限以下。这也可以与通缩对抗,但USCF排名委员会主题已经对该方法不满,因为它不会feed进额外的分数来提升用户的排名分。对于这些排名分底数的一种可能动机是,与堆沙袋(sandbagging)对抗。例如:故意降低排名分以符合更低级别的比赛和奖金。

电脑排名

从2005-06年开始,人机象棋比赛已经演示过,象棋电脑可以击败强大的人类选手(深蓝vs.卡斯帕罗夫)。然而,电脑的排名分很难量化。他们参加锦标赛的比赛过少,很难给电脑或软件引擎一个精确的排名分。对于象棋引擎,排名分一定程度上依赖于在上面运行的程序。

一些排名分的确定,参见:Chess engine § Ratings

5.国际象棋外的用例

Elo rating system被用于国际象棋比赛中。为了符合参加职业象棋比赛,选手必须具备Elo排名分至少1600分,也可以完成50场或更多场与职业选手的比赛。

美国高校足球从1998到2013年也使用Elo方法来作为它们的BCS(大碗杯冠军系列赛)的评分系统,之后BCS被CFP(高校足球季后赛)取代。今日美国(USA Today)的Jeff Sagarin发布了大多数美国运动的队伍排名,包括高校足球的Elo系统排名分。BCS的运作者使用它的Elo排名分作为公式的一部分来决定BCS国家冠军赛的年度入围者。在2014年的CFP中也有效使用了该排名系统;参加CFP中的队伍和它相应的比赛通过选择委员会来选择。

除了英国之外,国家Scrabble组织都使用正态分布的Elo ratings。北美Scrabble选手联盟有最多的排名人数,在2011年有2000个人左右。Lexulous也使用Elo系统。

流行的FIBS( First Internet Backgammon Server)会基于一个修改版的Elo系统计算ratings。新选手会被分配一个1500的排名分,最好的人机排名可以超过2000分。相似的公式也被一些其它的西洋双陆棋(backgammon)网站采用,比如:Play65, DailyGammon, GoldToken和VogClub。VogClub的新选手排名分为1600.

欧洲围棋联盟(European Go Federation)采用一个基于Elo的排名系统,初始由捷克围棋联盟提出。

在其它的运动中,也会采用Elo算法。通常非官方,没有体育管理部门背书。世界足球Elo排名会对男子国家足球队进行排名。在2016年,美职棒大职盟(MLB)也采用了Elo排名,接着是Baseball Prospectus。Baseball Prospectus也做了基于Elo的蒙特卡罗胜率模拟,来预测哪个队伍会进入到季后赛。在2014年,在Box Score之外,一个叫SB Nation的网站,引入了一个Elo排名系统来对国际棒球进行排名。

另外一些基于Elo的有:FIFA女子世界排名,基于Elo算法的一个简单版本,其中FIFA使用elo的官方排名系统来对足球女子国家队进行排名。

在2015年,Nate Silver,和Reuben Fischer-Baum为NBA的队伍和2014赛季引入了Elo ratings。在2014的FiveThirtyEight网站上,为美国职业足球大联盟创建了基于Elo的排名系统,以及胜率预测。

英国 Korfball(荷兰式篮球)协会也基于Elo排名来决定2011/12赛季的杯赛的不利因素。

NHL(美国冰球联盟)也开发了基于Elo的排名分。冰球的Elo评估一个选手在两方面的整体水平:在力量、进攻、点球情况下的得分和防守。

Rugbyleagueratings.com使用Elo排名系统来对橄榄球联盟队伍进行排名。

许多在线游戏也使用Elo排名来对pvp(player-vs.-player)进行排名。从2005年开始,《黄金寺( Golden Tee Live )》就使用基于Elo的排名。新选手2100分,顶级选手超过3000分。在《激战(Guild Wars)》中,Elo的排名被用于记录通过两队对战的得失排名分。初始的K值为30,但在2007年改为5, 在2009年改成15. 《魔兽世界( World of Warcraft )》以前也使用Elo排名系统作为竞技场玩家和队伍的排名比较,现在则使用与Microsoft’s TrueSkill相类似的系统。《CS:GO》使用Elo系统来评估玩家在比赛获胜后增加的实力等级。MOBA游戏《英雄联盟LOL》在第二个赛季前使用Elo排名系统。等等。。。

其它用处

Elo排名系统被用于生物学上。

关于Mark Zuckerberg的《社交网络》电影中,Eduardo Saverin在Mark的宿舍楼编写了Elo排名的数学公式。在该场景后,Elo系统用于对女生的吸引力进行排名。(尽管电影中的方程式有些小错误)

参考

我们先来看下Google Inc的paper:Wide & Deep Learning for Recommender Systems。

一、介绍

推荐系统可以看成是一个搜索排序系统,其中输入的query是一个用户和上下文的集合,输出是一个item列表。给定一个query,推荐任务就是在数据库中找到相关的items,接着基于目标(比如:点击or购买)去对items进行排序。

推荐系统与常见的搜索排序问题相同的一个挑战是,同时满足Memorization和Generalization。Memorization可以宽泛地定义成学到items或features的共现率,并利用(exploiting)这种在历史数据中的相关关系(correlation)。Generalization则基于相关关系的转移,并探索(explores)在过往很少或从不出现的新的特征组合。基于Memorization的推荐系统通常更局部化(topical),将items与执行相应动作的users直接相关。而基于Generalization的推荐则更趋向于推荐多样化的items。在本papers中,我们主要关注Google Play Stores的推荐问题,方法本身可用于其它场景。

对于工业界大规模的在线推荐和排序系统,常用的线性模型(比如:logistic regression)被广泛使用,因为它的简单性、可扩展性以及可解释性。模型通常在使用one-hot编码的二值化的稀疏特征上。例如,二值化特征”user_installed_app=netflix”,如果用户安装了Netflix,则具有特征值1. 通过在稀疏特征上使用cross-product transformation可以有效地达到Memorization,比如AND(user_installed_app=netflix, impression_app=pandora),如果用户安装了Netflix,接着曝光了Pandora,那么它的值是1. 这可以解释一个特征对(feature pair)的共现率与目标label间的相关关系。Generalization可以通过使用更少的粒度来进行添加,例如:AND(user_installed_category=video, impression_category=music),但人工的特征工程通常是必需的。cross-product transformation的一个限制是,不能泛化到那些在训练数据上没有出现过的query-item特征对。

Embedding-based的模型,比如因子分解机(FM)或深度神经网络,只需要很少的特征工程,通过为每个query和item特征对(pair)学到一个低维的dense embedding vector,可以泛化到之前未见过的query-item特征对,。然而,当底层的query-item矩阵很稀疏和高秩(high-rank)时(比如,用户具有特殊偏好或很少出现的items),很难为query-item pair学到有效的低维表示。在这种情况下,大多数query-item pairs之间是没有交互的,但对于所有的query-item pairs来说,dense embeddings会导致非零的预测,这样会过拟合(over-generalize),并生成不相关的推荐。另一方面,使用交叉特征转换(cross-product features transformations)的线性模型可以使用更少的参数就能记住(memorize)这些“异常规则(exception rules)”。(embedding 优点:泛化,缺点:稀疏时)

在本文中,我们提出了Wide&Deep learning框架来在同一个模型中达到Memorization 和 Generalization,通过联合训练一个如图一所示的线性模型组件和一个神经网络组件。

本文的主要贡献:

  • Wide & Deep 学习框架,可以用于联合训练带embeddings的feed-forward神经网络,以及对于稀疏输入的常用推荐系统所使用的带特征转换的线性模型。
  • Wide & Deep推荐系统的实现和评估在Google Play上已经产品化,这个app store具有数十亿的活跃用户、以及上百万的app。
  • 开源,在Tensorflow上提供了一个高级API

思想很简单,我们展示了Wide & Deep框架,它极大地提升了App的获得率(acquisition rate)并且同时满足training和serving的速度要求。

推荐系统总览

app推荐系统如图二所示。一个query,它包含着许多用户和上下文特征,当一个用户访问app store时生成。推荐系统会返回一个app列表(曝光:impressions),用户在此之上会执行特定的动作(点击:click或购买:purchase)。这些用户动作,伴随着queries和impressions,会以日志的形式记录下来。

由于在数据库中有超过百万的app,对于在serving延迟条件之内(通常为O(10)ms)的每一个query,尽可能得对每一个app进行评分是相当困难。因此,上述第一步收到一个query的过程是检索(retrieval)。检索系统会返回一个最匹配query的item的短列表,通常使用机器学习模型和人工定义规则来达到。在数量减至候选池后,排序系统(ranking system)会通过它们的得分对所有items进行排序。得分通常是$ P(y|x) $,对于给定的特征x,一个用户的动作标签y,包括用户特征(比如:国家,语言,人口属性信息),上下文特征(比如:设备,天的小时,周的天),曝光特征(比如:app age, app的历史统计信息)。在本文中,我们只关注在排序系统中使用Wide & Deep 学习框架。

3. Wide & Deep Learning

3.1 Wide组件

wide组件是一个泛化的线性模型,形式为:$ y=w^Tx+b $,如图1(左)所示。y是预测,$ x = [x_1, x_2, …, x_d] $是d维的特征向量, $ w = [w_1, w_2,…, w_d] $是模型参数,其中b为bias。特征集包括原始的输入特征和转换后的特征,一个最重要的转换是,cross-product transformation。它可以定义成:

…(1)

其中$c_{ki}$为一个boolean变量,如果第i个特征是第k个变换$\phi_k$的一部分,那么为1; 否则为0.对于二值特征,一个cross-product transformation(比如:”AND(gender=female, language=en)”)只能当组成特征(“gender=female” 和 “language=en”)都为1时才会为1, 否则为0. 这会捕获二值特征间的交叉,为通用的线性模型添加非线性。

3.2 Deep组件

Deep组件是一个前馈神经网络(feed-forward NN),如图1(右)所示。对于类别型特征,原始的输入是特征字符串(比如:”language=en”)。这些稀疏的,高维的类别型特征会首先被转换成一个低维的、dense的、real-valued的向量,通常叫做“embedding vector”。embedding的维度通常是O(10)到O(100)的阶。该embedding vectors被随机初始化,接着最小化最终的loss的方式训练得到该值。这些低维的dense embedding vectors接着通过前向传递被feed给神经网络的隐层。特别地,每个隐层都会执行以下的计算:

…(2)

其中,l是层数,f是激活函数(通常为ReLUs),$a^{(l)}, b^{(l)}和W^{(l)}$分别是第l层的activations, bias,以及weights。

3.3 Wide & Deep模型的联合训练

Wide组件和Deep组件组合在一起,对它们的输入日志进行一个加权求和来做为预测,它会被feed给一个常见的logistic loss function来进行联合训练。注意,联合训练(joint training)和集成训练(ensemble)有明显的区别。在ensemble中,每个独立的模型会单独训练,相互并不知道,只有在预测时会组合在一起。相反地,联合训练(joint training)会同时优化所有参数,通过将wide组件和deep组件在训练时进行加权求和的方式进行。这也暗示了模型的size:对于一个ensemble,因为训练是不联合的,每个独立的模型size需要更大些(例如:更多的特征和转换)来达到合理的精度。而对于联合训练(joint training),wide组件只需要一小部分的cross-product特征转换即可,而非一个full-size的wide模型

一个Wide&Deep模型的联合训练,通过对梯度进行后向传播算法、SGD优化来完成。在试验中,我们使用FTRL算法,使用L1正则做为Wide组件的优化器,对Deep组件使用AdaGrad。

组合模型如图一(中)所示。对于一个logistic regression问题,模型的预测为:

…(3)

其中Y是二分类的label,$ \sigma(·) $是sigmoid function, $ \phi(x) $是对原始特征x做cross product transformations,b是bias项。$w_{wide}$是所有wide模型权重向量,$w_{deep}$是应用在最终激活函数$a^{(l_f)}$上的权重。

4.系统实现

app推荐的pipeline实现包含了三个stage:数据生成,模型训练,模型serving。如图3所示。

4.1 数据生成

在这一阶段,用户和app的曝光数据在一定时间内被用于生成训练数据。每个样本对应于一个曝光。label为app的获得率(acquisition):如果曝光的app被下载则为1, 否则为0.

词汇表(Vocabularies),它是一个关于将类别特征字符串映射到integer ID上的表,也在该阶段生成。该系统会为所有的string特征计算ID空间,它们至少出现过一个最小的次数。连续的real-valued特征被归一化到[0, 1],通过将一个特征值x映射到它的累积分布函数$P(X <= x)$,除以$n_q$的分位数。对于第i个分位数(quantiles),归一化值为:$ \frac{i-1}{n_q-1}$。分位数边界在数据生成阶段计算。

4.2 模型训练

我们在试验中使用的模型结构如图4所示。在训练期间,我们的输入层接受训练数据和词汇表的输入,一起为一个label生成sparse和dense特征。wide组件包含了用户安装app和曝光app的cross-product tansformation。对于模型的deep组件,会为每个类别型特征学到一个32维的embedding向量。我们将所有embeddings联接起来形成dense features,产生一个接近1200维的dense vector。联接向量接着输入到3个ReLU层,以及最终的logistic输出单元。

Wide & Deep模型在超过5000亿的样本上进行训练。每一时刻有新的训练数据集到达时,模型需要重新训练。然而,每次从头到尾重新训练的计算开销很大,数据到达和模型更新后serving间的延迟较大。为了解决该问题,我们实现了一个warm-starting系统,它会使用前一个模型的embeddings和线性模型权重来初始化一个新的模型。

在将模型加载到模型服务器上之前,需要做模型的演习,以便确保它不会在serving的真实环境上出现问题。我们在经验上会验证模型质量,对比前一模型做心智检查(sanity check)。

4.3 模型Serving

一旦模型被训练和验证后,我们会将它加载到模型服务器上。对于每个请求,服务器会从app检索系统上接收到一个app候选集,以及用户特征来从高到低排序,接着将app按顺序展示给用户。得分的计算通过在Wide&Deep模型上运行一个前向推断传递(forward inference pass)来计算。

为了在10ms的级别服务每个请求,我们使用多线程并行来优化性能,运行运行更小的batches,而不是在单个batch inference step中为所有的候选app进行scoring。

5.试验结果

为了在真实的推荐系统上评估Wide & Deep learning的效果,我们运行了在线试验,并在两部分进行系统评测:app获得率(app acquisitions)和serving性能。

5.1 App Acquisitions

我们在一个A/B testing框架上做了3周的试验。对于控制组,1%的用户被随机选中,推荐由之前版本的排序系统生成,它是一个高度优化的wide-only logistic regression模型,具有丰富的cross-product特征转换。对于试验组,随机选中1%的用户,使用相同的特征进行训练。如表1所示,Wide & Deep模型在app store的主页上提升了app acquisition rate,对比控制组,有+3.9%的提升。另一个分组只使用deep组件,使用相同的神经网络模型,具有+1%的增益。

除了在线试验,我们也展示了在held-out离线数据上的AUC。其中Wide & Deep具有更高的离线AUC,在线也更好。一个可能的原因是,曝光和点击在离线数据集上是确定的,而在线系统通过混合generalization和memorization,从新的生户响应学到,生成新的探索推荐。

5.2 Serving Performance

Serving时具有高的吞吐率(throughout)和低延时是很有挑战性的。在高峰期,我们的推荐服务每秒处理1000w个app得分。单个线程上,在单个batch上为所有的候选得进行scoring会花费31ms。我们实现了多线程,并会将每个batch分割到更小的size上,它会将客户端的延迟的延迟减小到14ms上,所图2所示。

6.Tensorflow

只需要3步,即可以使用tf.estimator API来配置一个wide,deep或者Wide&Deep:

  • 1.选中wide组件的特征:选中你想用的稀疏的base特征列和交叉列特征列
  • 2.选择deep组件的特征:选择连续型的列,对于每个类别型列的embedding维,以及隐层的size。
  • 将它们放置到一个Wide&Deep模型中(DNNLinearCombinedClassifier)

关于更详细的操作,示例代码在:/tensorflow/tensorflow/examples/learn/wide_n_deep_tutorial.py,具体详见tensorflow tutorial。

参考

youtube的基于深度学习的推荐系统,主要分成两大部分:

一、候选生成

将推荐当成是一个多分类问题,预测问题为:视频库V,有上百万的视频,某用户U,在上下文C上,在时间t时的观看行为$w_t$,刚好是某个视频i.

其中u表示一个高维的(user,context)pair的“embedding”, v表示每个候选视频的emdedding。在该假设中,一个emdedding可以简化成一个稀疏实体的映射(视频,用户等各有一个),映射到一个N维的dense vector中。深度神经网络的任务是:学到user embeddings: u,作为用户历史和上下文的函数,这在使用一个softmax分类器对视频进行判别时有用。

使用隐式反馈(观看行为)来训练模型,其中,用户完成一个视频可以认为是一个正例。

Efficient Extreme Multiclass

为了有效地训练这样一个上百万分类的模型,我们采用的技术是:从后台分布中对负例采样(sample negative classes),接着通过按权重重要性加权(importance weighting)纠正这些样本。对于每个样本,为true-label和negative-label,学习目标是最小化cross-entropy loss。实际中,会抽样上千个负样本,这种方法可以比传统的softmax快100倍。另一个可选的方法是:hierarchical softmax,但这里我们不去做对比。

在提供服务的阶段(serving time),我们需要计算最可能的N个分类(视频),以便选中其中的top N,来展现给用户。对上百w级的item进行打分,会在10ms左右的延迟内完成。之前的Youtube系统靠hashing技术[24]解决,和这里描述的分类器使用相类似的技术。由于在serving time时并不需要对softmax输出层校准(calibrated)likelihoods,打分问题(scoring problem)可以缩减至在点乘空间中的最近邻搜索问题,可以使用[12]中提供的库来完成。我们发现,在最近邻搜索算法上做A/B test效果并不特别明显。

1.1 模型架构

受语言模型中的CBOW(continuous bag of words)的启发,我们为固定视频库中的每个视频学到了高维emdeddings,并将它们的emdeddings作为输入前馈(feed)给一个前馈神经网络。用户的观看历史,被表示成一个关于稀疏视频id的可变长的序列,这些id通过embeddings技术被映射到一个dense vector表示中。该网络需要固定大小的dense inputs,在不同策略中(sum, component-wise max,等),对emdeddings的简单平均(simply averaging)效果最好。最重要的,emdeddings会和其它一些模型参数,通过普通的梯度下降后向传播更新即可学到。特征被级联到一个很宽的第一层上(wide first layer),后面跟着许多层的完全连接的ReLU层[6]。图3展示了整体架构,带有下面将要描述的额外的非视频观看特征(no-video watch features)。

1.2 多种信号

使用深度神经网络作为普通的矩阵分解,其中一个关键优点是,任何连续的特征和类别特征都可以很方便地加进模型中。搜索历史的处理,可以与观看历史的处理方式相类似 – 每一个查询(query)可以tokenized化成1-gram和2-gram,每一个token都可被嵌入。一旦求平均,用户的tokenized化的嵌入式query,代表了一个总结型的稠密搜索历史(summarized dense search history)。人口统计学特征(Demographic features),对于新用户的推荐很重要。用户的地域和设备信息(device),都可以被嵌入和串联。简单的二元特征和连续特征,比如用户性别,登陆态,年龄,都可以归一化到[0,1]上的实数值,直接输入到该网络。

“样本年龄”特征(”Example Age” Feature)

YouTube上,每秒都有许多视频上传上来。推荐这些最新上传的新鲜(“fresh”)内容,对于YouTube产品来说相当重要。我们一致观察到:用户喜欢新鲜内容,尽管并非相关。除了简单的推荐用户想看的新视频所带来的一次传播效果外,还存在着关键的病毒式的二次传播现象。

机器学习系统经常展示出对过往内容的一个隐式偏差(implicit bias),因为它们通常是基于历史样本的训练,来预测将来的行为。视频流行度的分布是高度不稳定的,但是由推荐系统生成的在视频库上的多项分布(multinomial distribution),将影响在多周训练窗口上的平均观看似然。为了纠正这一点,我们将训练样本的age,作为一个训练特征。在serving time时,该特征被置为0(或者为一个微小的负数),反映出模型在训练窗口的最末尾正在做预测。

图4展示了该方法在选择视频上的效果。

图4: 对于一个给定的视频[26],使用样本age作为特征训练的模型能够精准表示数据的上传时间和与时间相关的流行度间的关系。如果没有该特征,模型将会预测在训练窗口上的近似平均似然(baseline)。

1.3 Label和Context选择

需要重点强调的是,推荐(recommendation)通常涉及到求解一个替找问题(surrogate problem),并将结果转换成一个特殊上下文。一个经典的示例是,如果能准确预测rating,会产生有效的电影推荐[2]。我们已经发现,这种代理学习问题(surrogate learning problem)在A/B testing上很重要,但很难在离线试验中进行衡量。

训练样本需要从所有YouTube观看行为(即使嵌入在别的网站上)上生成,而非仅仅只使用我们生成的推荐的观看行为。否则,新内容将很难浮现出来,推荐系统在探索(exploitation)上将过度偏差。如果用户正通过别的方法探索发现视频,而非使用我们的推荐,我们希望能够快速通过协同过滤传播该发现给他人。 一个核心点是,提升live metrics的目的是为每个用户生成一个固定数目的训练样本,有效地在loss function上对我们的用户做平等的加权。这可以防止一少部分高活跃度用户主宰着loss

一定程度上这与我们的直觉相反,必须注意:为防止模型利用网站布局,以及代理问题的过拟合,不要告诉分类器信息(withhold information from the classifier)。可以考虑将一个样本看成是用户已经发起的一个查询query: “taylor swift”。由于我们的问题是预测下一个要看的视频。通过给定该信息,分类器将会预测要观看的最可能的视频,是那些出现在相应搜索结果页中关于”taylor swift”的视频。一点也不惊奇的是,如果重新生成用户最新的搜索页作为主页推荐,效果会很差。通过抛弃顺序信息,使用无顺序的词袋(bag of tokens)表示搜索query,该分类器不再直接认识到label的来源。

视频的自然消费模式,通常会导致非常不对称的co-watch概率。连播电视剧(Episodic series)通常被按顺序观看,用户经常发现,对于同一个流派(genre)中的艺术家们(artists),在关注更小众的之前,会从最广为流行的开始。因此我们发现对于预测用户的下一次观看行为上有着更好的效果,而非去预测一个随机held-out观看(a randomly held-out watch)(见图5)。许多协同过滤系统隐式地选择标签和上下文,通过hold-out一个随机item,然后通过用户历史观看中的其它item来预测它(5a)。这会泄露将来的信息(future information),并忽略任何不对称的消费模式(asymmetric consumption patterns)。相反的,我们通过选择一个随机观看(a random watch),然后“回滚(rollback)”一个用户的历史,只输入用户在hold-out label的watch之前(5b)的动作。

图5: 选择labels和输入上下文给模型,在离线评估时很有挑战性,但对真实的效果有巨大提升。这里,实心事件•表示网络的输入特征,而空心事件◦表示排除在外。我们发现,预测一个将来的观看(5b),在A/B test中效果更好。在(5b)中,样本的age通过$ t_{max}-t_N $来表示,其中t_max是训练数据中观察到的最大时间。

1.4 特征和深度的试验

如图6所示,添加特征和深度,可以极大提升在holdout data上的precision。在这些试验中,1M的视频量,和1M的搜索tokens,被嵌入到256个float值上,每个都在一个最大的bag-size:50个最近的watches和50个最近的searches。softmax层输出一个在1M个视频classes、256维的多项分布(可以看成是一个独立的output video emdedding)。这些模型被训练,直接覆盖所有的YouTube用户,对应在数据上的多个epochs上。网络结构按一个公共的”tower”模式,在网络的底部是最宽的,每个后继的隐层,将单元数二等分(与图3相同)。深度为0的网络,是一个有效的线性因式分解模型,它的效果与以往的系统很相似。增加宽度(width)和深度(depth),直到增量的效果越来越小,收敛越来越难:

  • Depth 0: 一个线性层,可简单地将串联层转换成与softmax相匹配的256维.
  • Depth 1: 256 ReLU
  • Depth 2: 512 ReLU -> 256 ReLU
  • Depth 3: 1024 ReLU -> 512 ReLU -> 256 ReLU
  • Depth 4: 2048 ReLU -> 1024 ReLU -> 512 ReLU -> 256 ReLU

二、Ranking

Ranking的主要作用是,针对指定的UI,使用曝光数据来特化和校正候选预测(specialized and calibrate candidate predictions)。例如,用户通常会观看一个probability值较高的视频,但不大可能去点击指定主页上缩略图的曝光。在Ranking时,我们会访问许多描述视频的特征、以及视频与用户关系的特征,因为在候选集生成阶段,只有一小部分的视频被打过分,而非上百w的视频。Ranking对于聚合不同的候选源很重要,因为每个源的得分不能直接对比。

我们使用一个与候选生成阶段相似的架构的深度神经网络,它会使用logistic regression(图7)为每个视频的曝光分配一个独立的值。视频的列表接着会通过该分值进行排序,并返回给用户。我们最终的ranking objective会基于线上的A/B testing结果进行调整,但总体上是一个关于每次曝光的期望观看时长(expected watch time)的简单函数。根据ctr的排序通常会促进视频期诈现象:用户不会播放完整(标题党:点击诱惑”clickbait”),而观看时长(watch time)可以捕获更好的参与度(engagement)[13,25]。

图7: 深度ranking网络架构,描绘了嵌入的类别特征(单值和多值类别都存在),与归一化的连续特征的embeddings和powers共享。所有的层都是完全连接的。惯例上,成百上千的特征都可以输入到网络中。

2.1 特征表示

我们的特征,与传统的类别特征分类,以及连续型/普通特征相互隔离开来。类别型特征,在基数上变化多样–一些是二元的(比如:用户是否登陆),而其它一些则可能有上百万种可能的值(比如:用户最新的搜索query)。特征会根据它们是否是单值(“univalent”),或者多值集合(“multivalent”),再做进一步分割。关于单值类别特征的一个示例是:被打过分的曝光视频id;而相应的多值特征可能是一批(a bag of)关于该用户已经观看过的N个视频id。我们也会根据特征是否描述了item的属性(“impression”)或者user/context的属性(”query”),将特征进行分类。Query特征在每次请求时被计算一次,而impression特征则会为每个评过分的item计算。

特征工程(Feature Engineering)

我们通常在我们的排序模型中使用成百上千的特征,它们被分成类别型和连续型特征。尽管深度学习可以缓和手工建立特征工程的负担,但我们的原始数据天然就不能直接输入到前馈神经网络中。我们仍需要花费可观的工程资源来将用户和视频数据转换成有用的特征。最主要的挑战主要在:表示用户动作的临时顺序,以及如何将这些动作与被打分的视频曝光(impression)相关联。

我们观察到,最重要的信号是,那些描述一个用户与item本身、以及其它相似item的之前交互行为,这与广告排序(randing ads)上的经验相类似。例如,考虑用户的过往历史,以及上传被打分的频道-该用户从该频道观看了多少视频?该用户在该主题上观看一个视频的最近时间是何时?这些连续特征相当强大,它们描述了用户在相关item上的过往动作,因为它们在不同的item上泛化得很好。我们也发现,很重要,从候选生成阶段(Candidate generation)到排序阶段(Ranking)以特征的形式进行信息传递,比如:哪个源被指定给该视频候选?会分配什么分值?

描述过往视频曝光的频率的特征,对于在推荐中引入“搅动(churn)”很重要(连续的请求不会返回相同的列表)。如果一个用户最近被推荐了某个视频,但没有观看它,接着模型将自然地在下一页加载时降级该曝光(impression)。Serving即时曝光和观看历史,是一项工程壮举,超出了本paper的范围,对于产生响应式推荐至关重要。

类别特征embedding (embedding categorical features)

与候选生成阶段相类似,我们使用embeddings,将稀疏的类别型特征映射到dense表征上,更适合于神经网络。每个唯一的ID空间(视频库:”vocabulary”) 都具有一个单独学到的emdedding,它维度的递增与唯一值的数目的log成比例。这些库是简单的look-up table,在训练前由整个数据一次构建。非常大的基数ID空间(视频ID或者搜索query terms)被截断,通过只包含topN,在基于点击曝光的频率排序之后。Out-of-vocabulary的值,可以简单地映射到零嵌入上(zero embdding)。正如在候选生成阶段,多值类别特征的embeddings是被平均化的,在被输入到网络之前。

重要的是,相同ID空间的类别型特征,也共享着底层的embeddbings。例如,存着单个关于视频ID的全局embedding,供许多不同的特征使用(曝光的视频ID,该用户观看的最近视频ID,作为推荐系统”种子”的视频ID等等)。尽管共享emdedding,每个特征独自输入到网络中,因此,上面的层可以学到每个特征的特定表征(representation)。共享嵌入(sharing emdeddings)对于提升泛化、加速训练、及减小内存等相当重要。绝大多数模型参数都是在这些高基数(high-cardinality)的embedding空间中 - 例如,100w的ID,嵌入到32维的空间上,与2048个单元的宽完全连接层多7倍多的参数。

归一化连续特征(Normalizing Continuous Features)

众所周知,神经网络对于输入的归一化和分布是很敏感的[9],其它方法(比如:决策树ensembles)对于独立特征的缩放(scaling)是稳定的。我们发现,对连续特征进行合理的归一化,对于收敛来说很重要。连续特征x,具有分布f,被转换成x^,通过对值进行归一化,比如:特征平均地分布在[0,1)上使用累积分布,$ \hat{x}=\int_{-\infty}^{x}df $。该积分与特征值的分位数的线性插值相近似,在训练开始这,在所有数据上的单个pass中计算。

另外,原始的归一化特征$ \hat{x} $,我们也输入$ \hat{x}^2 $和$ \sqrt{\hat{x}} $,给网络更多有表现力的阶,通过允许它,很容易形成特征的super-linear和sub-linear function。我们发现:输入连续特征的阶,可以提升离线的accuracy。

2.2 对期望的观看时长建模

我们的目标是,给定训练样本:包含正例(曝光的视频被点击)和负例(曝光的视频没被点击),来预测期望的观看时间。正例可以解释成:该用户花费观看该视频的时间量。为了预测期望的观看时间,我们出于该目的,开发并使用加权logistic regression技术。

该模型的训练通过logistic regression和cross-entropy loss进行(图7)。然而,正例(被点的)的曝光,会由视频所观察到的观看时间进行加权。所有负例(未点击)的曝光,都使用单位加权。这种方式下,通过logistic regression学到的差异(odds)是:$ \frac{\sum{T_i}}{N-k} $,其中N是训练样本的数目,k是正例曝光的数目,Ti是第i个曝光的观看时间。假设,正例曝光很小(真实情况就这样),学到的差异(odds)近似为:$ ET $,其中P是点击概率,而E[T]是该曝光所期望的观看时间。由于P很小,该乘积近似为E[T]。为便于推理,我们使用指数函数e^x作为最终的激活函数,来产成这些odds,来近似估计期望的观看时长。

2.3 隐层的试验

表1展示了,我们在下一天的holdout数据上,使用不同的隐层配置所获得的结果。Value展示了每个配置(”加权,每用户的loss”),包括正例和负例,曝光展示给单个页内的某个用户。我们首先使用我们的模型对两种曝光进行打分。如果负例的曝光接受到更高的分值,那么我们会认为,正例的观看时长为:误预测的观看时长(mispredicted watch time)。加权的每用户loss,就是误预测的观看时间的总量,作为一个分数,在heldout曝光pair上的一个总观看时长。

这些结果展示了隐层的width的增加会提升效果,同样depth的增加也会。然而,服务器的CPU时间需要进行权衡下。该配置是一个1024-wide的ReLU,后面跟着一个512-wide的ReLU,再接一个256-wide的ReLU,会给我们最佳的结果,而允许我们在CPU预算范围内。

对于1024->512->256的模型,我们尝试只输入归一化连续特征,而不输入它们的powers,会增加0.2%的loss。相同的隐层配置,我们也训练了一个模型,其中正例和负例的加权相同。不令人惊讶,观看时间加权loss会增加4.1%之多。

表1:在基于观看时长加权的pairwise loss上,更深和更宽的隐ReLU层的效果

参考

- 0.Deep Neural Networks for YouTube Recommendations

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

第1为:使用subword信息来增强词向量。

1.模型:使用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.1 普通模型

先简单回顾下(Mikolov et al.,2013b)提出的continuous skip-gram模型:

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

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

其中N_t,c是一个从词汇表抽样出的负样本集合。logistic loss函数l:x -> log(1+e^-x),我们可以获得相应的目标函数:

wt和上下文词wc采用标量积:$ 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} $.我们将一个向量表示zg与每个n-gram g相关联。我们可以通过对这些n-gram的向量进行求和来表示一个词。我们获得一个scoring函数:

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

1.3 n-gram字典

将所有的n-gram使用一个length>=3, length<=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则会很快!

参考