前一阵子的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系统用于对女生的吸引力进行排名。(尽管电影中的方程式有些小错误)

参考

microsoft在2016年提出了MV-DNN结构:《A Multi-View Deep Learning Approach for Cross Domain User Modeling in Recommendation Systems》。我们来看下该paper。

介绍

为了解决CF和CB的诸多限制,我们提出了利用user features和item features的推荐方法。为了构建user features,不同于许多user profile-based的方法,我们提出了从浏览记录、搜索历史中抽取丰富特征来建模用户的兴趣。依赖的假设是:用户的历史在线动作会影响用户的背景(background)和偏好(preference),因此提出了一种关于用户会对哪些items和topics感兴趣的更精确看法。例如,一个用户做出的许多查询和网页访问都与婴儿有关,那么她很可能是一个新生儿的母亲。有了这些丰富的在线行为,推荐相关items可以更有效率和有效果。

在我们的工作中,我们提出了一种新的deep learning方法,它扩展了DSSM(Deep Structured Semantic Models),它将users和items映射到一个共享语义空间中,并推荐那些在映射空间中与该用户具有最大相似度的items。为了达到该目的,我们的模型会对users和items进行投影,每一者都通过一个丰富的特征集表示,通过非线性转换层映射到一个完全共享的隐语义空间中,其中user的mapping以及该用户喜欢的items的mappings间的相似度会最大化。这允放该模型学习感兴趣的mappings:比如,访问了fifa.com的用户可能会读取关于世界杯相关的新闻文章、或喜欢关于PC or XBox足球游戏。用户侧的丰富特征可以允许建模用户的行为,从而克服在content-based推荐中的限制。它也可以有效解决用户的冷启动问题,因为模型允许我们从queries和相关推荐items(比如音乐)上捕获用户兴趣,即使它们没有使用音乐服务的历史记录。我们的deep learning模型具有一个ranking-based objective函数,它会将正样本(用户喜欢的items)的排序比负样本的更高。该ranking-based objective对于推荐系统更好。

另外,我们扩展了原始的DSSM模型(它被称为是single-view DNN),因为它从来自单个域的user-features 和items学习模型。我们将新模型命名为“Multi-View DNN”。在文献中,multi-view learning是一个比较成熟的领域,它可以从相互不共享的公共特征空间的数据中进行学习。我们将MV-DNN看成了在multi-view learning setup中一种通用的Deeplearning方法。特别的,在我们的数据集中有News、Apps和Movie/TV logs,我们不需要为这种不同域(domain)构建独立模型,它们可以将user features映射到相同域(domain)的item features上,我们会构建一个新的multi-view模型,它会为在隐空间中的user features发现一个单一映射,可以从所有域中使用items的特征进行联合优化。MV-DNN会利用多个跨域数据来学习一个更好的用户表示(user representation),也会利用全域的用户偏好数据使用以一种规则的方式解决数据稀疏性问题。

3.数据集描述

这部分会介绍数据集。我们描述了数据收集过程,以及每个数据集的特征表示,以及一些基础的数据统计。

在该研究中会使用4个数据集,它们从microsoft的产品中收集,包含:

  • (1) Bing Web vertical搜索引擎日志
  • (2) Bing News vertical的新闻文章浏览历史
  • (3) Windows AppStore的App下载日志
  • (4) XBox的Movie/TV观看日志

所有日志的收集从2013-12 〜 2014 6月,包含了英语系国家:美国、加拿大、英国。

(用户特征: user features):我们从Bings收集了用户的搜索queries和它们的点击urls来形成用户特征。queries首先会被归一化、获取词干、接着将它们split成unigram特征,urls会被简写成domain-level(例如:www.linkedin.com)来减小特征空间。我们接着使用TF-IDF得分来保持最流行和重要(no-trivial)特征。整体上,我们选择了300w的unigram特征和500k的domain特征,来产生一个总长度为3500w的用户特征向量

(新闻特征:News Features):我们收集了从Bing News vertical的新闻文章点击。每个News Item通过三部分特征表示。第一部分是,使用字符tri-gram表示编码的标题特征。第二部分是,使用二值特征编码的News的top-level类目(比如:娱乐)特征。第三部分是,每篇文章的命名实体,使用一个NLP parser抽取得到,同样使用tri-gram进行编码。这会产生一个包含10w维的特征向量

(APP特征):用户APP的下载历史,来自windows AppStore日志。每个App的标题使用字符tri-gram表示,会以二值形式组合上类目特征(比如:游戏)。对于APP描述常变化的特性,我们决定不包含这些特征。这一部分会产生一个5w维的特征向量

(Movie/TV Features):对于Xbox日志,我们为每个XBox用户收集了Movie/TV观看历史。每个item的标题和描述,会组合成文本特征,接着使用字符型tri-gram编码。该genre也使用二值特征编码。这一部分会产生5w维特征向量

在我们的神经网络框架中,user features被映射到user view上,其余被映射到不同的item views上。出于训练目的,每个user view会被匹配到一个item view上,它包含了用户的完整集合。为了这样做,我们对登陆用户的每个user-item view pair, 以及基于id间交叉做了抽样。这会为每个user-item view pair产生不同数目的用户。表1描述了在该paper中的一些统计。

4. 用于建模用户的DSSM

DSSM的引入是为了增强在搜索上下文中的query document matching。

图1 DSSM深度结构语义模型

DSSM的典型结构如图1所示。到DNN的输入(原始文本特征)是一个高维向量,例如,在一个query或一个文档中的terms原始数目(没有归一化)。接着DSSM会将该输入传给两个神经网络,两者都有各自不同的输入,会将它们映射到在一个共享语义空间中的语义向量中。对于网页文档排序,DSSM会计算一个query和一个document间的相关得分(对应两个语义向量间的cosine相似度),并通过相似得分进行文档排序。

更正式的,如果x表示输入的term向量,y表示输出向量,表示内部的hidden layers,表示第i个权重矩阵,表示第i个bias term,我们有:

…(1)

其中,我们使用tanh函数作为在output layer和hidden layers 上的activation函数:

…(2)

在一个query Q和一个document D间的语义相关得分,接着通过R进行measure:

…(3)

其中,各自是query和document的语义向量。在Web搜索中,给定query,document会通过它们的语义相关得分进行排序。

惯例上,每个word w通过一个one-hot词向量表示,其它维度对应于词汇表size。然而,词汇表size经常在现实中非常大,one-hot向量的词表示会让模型学习开销很大。因此,DSSM使用word hashing layer通过一个letter-trigram向量来表示一个词。例如:给定一个词(web),在添加了词边界符号后(#web#),该词被分割成ngram序列(#we, web, eb#)。接着,该词被表示成一个关于letter-trigrams的count vector。例如,web的letter-trigram表示为:

在图1中,第一层 matrix 表示letter-trigram矩阵,它从一个term-vector转移到它的letter-trigram count vector上,无需学习。尽管英文words的总数目会增长得相当大,去重后的英文letter-trigrams的总数目通常是有限的。因此,它可以泛化到在训练数据中那些未见过的新词上。

在训练中,假设一个query与该query下被点击的documents相关,DSSM的参数(例如:权重矩阵),可以使用该信号被训练。例如,给定一个query后一个document的后验概率,可以从两者间的语义相关分数中会通过一个softmax函数进行估计:

…(4)

其中是softmax的一个平滑因子,它通常会在一个held-out数据集上进行经验型设置。D表示要排序的候选文档集合。理想的,D应包含所有可能的文档。实际上,对于(query, clicked-document) pair,可以使用表示,其中:

  • Q表示一个query
  • 表示点击的文档,
  • 来表示: N个随机选中的未点击文档
  • D: 包含和N个随机选中的未点击文档来近似D

在训练中,模型参数被估计成:给定queries,被点击文档的极大似然:

…(5)

其中,表示神经网络的参数集。

5.MV-DNN

DSSM可以看成是一个multi-learning框架,其中它会将两种不同的数据视图映射到一个共享视图(shared view)中。在某种程度上,它可以被看成是:在一个更通用的setting中来学习两个不同views间的一个共享mapping。

图2: 多域推荐(multiple domain recommendation)的MV-DNN。它使用一个DNN来将高维稀疏特征(例如:users, News, App的原始特征)映射成低维dense特征到一个联合语义空间中(joint semantic space)。第一个hidden layer,有50k units,会完成word hashing。word-hashed features接着通过多个非线性投影投影层被投影。最后一层的activities会形成在语义空间中的特征。注意,在该图中的输入特征维度x(5M和3M)被假设成:每个view可以有任意的特征数。详见文本。

在该工作中,我们提出了一个DSSM的扩展,它具有对数据的多个views,我们称之为Multi-view DNN。在该setting中,我们具有v+1个views,一个主视图(pivot view)称为,其它v个辅助视图(auxiliary views)为:。每个具有它自己的输入域。每个view也具有它自己的非线性映射层 ,它会将转换到共享语义空间上。训练数据包含了一个样本集合。第j个样本具有主view 的一个实例,以及一个活动辅助视图,其中a是在sample j中active view的索引。所有其它视图输入被设置为0向量(0 vectors)。该学习目标是(objects)是为每个view(比如:相似的求和)发现一个线性映射,以便最大化相似度(在主视图 mapping以及其它视图 mapping间的语义空间的相似度)的求和。公式为:

…(6)

MV-DNN的结构如图2所示。在我们的推荐系统设置中,我们将设置为user features的主视图,并为各种不同的想推荐的items类型创建了辅助视图。

该目标函数是意图是,为users features尝试找到单个mapping(),可以将users features转换到一个空间中,它与该用户在不同视图/域中所喜欢的所有其它items相匹配(match)。该方法会共享参数,并允许该域(domains)即使没有足够信息也能学习较好的mapping(通过其它带有足够信息的domains数据来学)。

如果假设具有相似新闻文章品味的用户,同时也在其它域(domains)上有相似品味,这意味着这些domains可以从通过News domain学到的user mapping上受益。如果该假设是合法的,那么从任意domain上的样本都可以帮助将相似用户在所有domains上进行更准确的分群。经验结果表明,在该domains上的假设是合理的,我们会在实验章节再做描述。

5.1 训练MV-DNN

MV-DNN可以使用SGD进行训练。实际上,每个训练样本会包含一个输入对(inputs pairs),一个用于用户视图(user view),一个用于其它数据视图。因此,尽管事实上在我们的模型只有一个用户视图(user view),通常采用N个用户特征文件会更方便,每个对应于一个item feature file,其中N是user-item view pairs的总数目。在算法1中,我们会描述训练MV-DNN的高级过程。当各自对所有进行求导时,我们会得到两个非零导数 ,它允许我们应用与DSSM相同的梯度更新规则【9】,使用来取代q,使用来取代d。

算法1

5.2 MV-DNN的优点

尽管MV-DNN是从原始的DSSM框架进行扩展而来的,但它具有许多独特的特性比前者更优。首先,原始的DSSM模型用于相同特征维度size的query view和document view的,使用相同的表示(representation)进行预处理(例如:letter tri-gram)。这在特征组合阶段会有巨大限制。由于推荐系统的差异性,很可能user view和item view会有不同的输入特征。同时,许多类型的特征不能使用letter trigram进行最优表示。例如,URL domain feature通常包含了前缀和后缀,(比如:www, com, org),它们会被映射到相同的特征上(如果使用了letter tri-gram)。实际上,我们已经发现,当输入原始文本很短时(例如:原始DSSM模型中的query text和document title),该letter tri-gram表示很理想,但如果建模包含了大量queries和url domains的用户级别特征(user level features)就会变得不合适。新的MV-DNN会移除该限制,来包含类别型特征(比如:电影类型和app类目,地理特征:比如国家和区域),也可以包含原始文本特征(用户输入侧使用1-grams或2-grams来表示)。

第二,MV-DNN可以扩展到许多不同的domains上,原始DSSM框加做不到。通过在每个user-item view pair上执行pair-wise训练(如算法1描述所示),我们的模型可以很方便的采用view pairs的新集合,在训练过程中的任意阶段,它包含了完全独立的users和items集合;例如:添加来自Xbox games的一个新数据集。通过在每个训练迭代过程中选择user-view pairs,我们的模型事实上可以收敛到一个最优的user view embedding上,它通过所有的item views训练得到。注意,尽管理论上我们在不同的item-views上具有不同的user sets,在我们的实验期间,考虑便利性和特征归一化的方便,我们会选择在所有views上保持相同集合的用户。

6.数据降维

实际上,提出的深度学习方法通常需要为user view处理高维特征空间中的海量训练样本。为了扩展系统,我们提出了许多降维技术来减少在user view上特征数。接着,我们提出了一个思想来压缩(compact)和总结(summarize)用户训练样本,它可以将训练数据的数目减少到与users数目成线性倍数上。

6.1 top features

对于user features,一种简单的降维方法是,选择top-k个最常用的特征。。。。

6.2 K-means

6.3 LSH

6.4 减小训练样本数

每个view的训练样本包含了一个关于 pairs集合(表示:)。实际上,一个user可能会喜欢许多items,它们有时候会造成训练数据非常大。例如,在我们的新闻推荐数据集上,大概有10亿pairs数目,这会造成训练过程非常慢(当使用最优的GPU实现时)。

为了解决该问题,我们会压缩训练数据,以便它对于每个user每个view都可以包含单个训练样本。特别的,压缩版的训练样本包含了user features 与一个用户在该view中所喜欢的所有items的平均分的 features组成的pairs。

实验

详见paper。

参考

microsoft在2013年提出了DSSM结构:《Learning Deep Structured Semantic Models for Web Search using Clickthrough Data》。我们来看下该paper。

介绍

主要基于在IR上的隐语义模型的两点扩展。第一是以监督方式利用点击数据来学习隐语义模型【10】。第二是引入深度学习方法进行语义建模。

2.1 隐语义模型和点击数据的使用

对于query-document matching来说,在IR社区中使用隐语义模型是一个长期存在的研究主题。流行的模型可以分为两大类:线性投影模型和生成主题模型。

IR领域最著名的线性投影模型是LSA。通过在一个document-term矩阵上使用SVD,一个document(或一个query)可以映射成一个低维概念向量(conecpt vector):,其中A是投影矩阵。在文档搜索中,在一个query和一个document间的相关分(可以通过term向量分别表示为Q和D),根据投影矩阵A, 被认为是与概念向量间的cosine相似度得分成比例:

…(1)

除了隐语义模型,在被点击的query-document pairs上训练的转换模型(translation models)也提供了一种语义匹配的方法[9】。不像隐语义模型,翻译模型可以直接通过在一个document中的一个term和在一个query中的一个term间的转换关系(translation relationships)。最近研究表明,大量的点击数据用户训练,该方法可以非常高效。我们在实验中也进行了比较。

2.2 deep learning

3.DSSM

3.1 DNN用于计算语义特征

图1: DSSM图示。它使用一个DNN将高维稀疏文本特征投影到在语义空间中的低维dense特征。第一个hidden layer具有30k units,会完成word hashing。word-hashed features接着通过多个非线性投影层进行投影,在DNN中的最后一层的activities会形成在语义空间中的特征

通常我们开发的DNN结构,用于将原始文本特征(raw text features)映射到在一个语义空间中的特征(如图1所示)。DNN的输入(raw text features)是一个高维term vector,例如:在query中的terms的原始数目,或者一个没有归一化的文档,DNN输出是在一个低维语义特征空间中的一个concept vector。该DNN模型可以以如下方式用于网页文档排序(Web document ranking):

  • 1) 将term vectors映射到它们相应的语义concept vectors上
  • 2) 计算一个document和一个query间相关分,作为他们相应的语义concept vectors的cosine相似度 等式(3)和(5)

更正式的,如果我们将x表示成input term vector,y表示output vector,,表示中间的hidden layers,表示第i个weight matrix,表示第i个bias term,我们有:

…(3)

其中,我们使用tanh作为hidden layers和output layer的activation函数:

…(4)

在一个query Q和一个document D之间的语义相关得分,可以通过下面方式进行衡量:

…(5)

其中分别是query和document的是concept vectors。在web search领域,给定query,document可以通过它们的语义相关得分进行排序。

习惯上,term vector的size,可以被看成是在IR中原始的bag-of-words特征,等同于用于索引web document集合的字典表。字典的size通常非常大。因此,当使用term vector作为输入时,input layer的size对于inference和training来说无法想像。为了解决这个问题,我们开发了一个称为”word hashing”的方法来做为DNN的第一层,如图1的最低端所示。该layer只包含线性隐单元(linear hidden units),在其中有非常大size的权重矩阵不会被学习。在下面章节,我们描述了word hashing方法。

3.2 word hashing

这里描述的word hashing方法,目标是减少bag-of-words term vectors的维度。它基于字母型letter n-gram,该方法特别适合这个任务。给定一个词(比如:good),我们首先会添加起始结束标记(比如:#good#),接着,我们将该词切分成letter n-grams(例如,letter trigrams: #go, goo, ood, od#)。最终,该word会使用一个关于letter n-grams的向量进行表示。

表1

该方法存在的一个问题是冲突(collision),例如,两个不同的词可以具有相同的letter n-gram vector表示。表1展示了关于在两个字典表上word hashing的一些统计。对比起one-hot vector的原始size,word hashing允许我们使用更低维度来表示一个query和一个document。以40k个词的字典作为示例。每个word可以被表示成使用leter-trigrams的一个10306维向量,给定一个4-fold降维会有较少冲突。当该技术应用到一个更大词汇表上时会有更大降维。如表1所示,在500k-word的字典表里,使用letter trigrams通过一个30621维向量来表示每个词, 16-fold的降维会有一个冲突率为0.0044% (=22/5000000)

由于英文单词数目是无限的,而英文(或其它相似语言)中的letter n-grams通常是有限的。另外,word hashing可以将具有不同字形的相同词映射到在letter n-gram空间中比较接近的点上。更重要的,当在训练集中的一个未见词(unseen word)以word-based representation时总是会引起困难,而使用letter n-gram-based representation则不会。唯一的风险是冲突会随着表1中的量而增加。因而,letter n-gram-based word hashing对于out-of-vocabulary问题是健壮的,允许我们将DNN解法扩展到包含极大词表量的Web search任务中。我们会演示第4节中展示该技术的好处。

在我们的实验中,基于word hashing的letter n-gram可以被看成是一个固定的线性转换(例如:非适配的 non-adaptive),通过这种方式,在input layer上的一个term vector可以被投影到在下一layer上的一个letter n-gram vector上,如图1所示。由于letter n-gram vector具有更低的维度,DNN learning可以有效执行。

3.3 DSSM的学习

点击日志包含了一列queries和它对应的点击文档。我们假设一个query与该query对应点击的文档是相关的(至少部分上是)。受语音和nlp领域判别式训练方法的影响(discriminative),我们提出了一个监督式训练方法来学习我们的模型参数,例如:权重矩阵和bias vector 是DSSM的必要部分,因此学习目标是:给定queries,最大化点击文档的条件似然。

首先,我们会计算给定一个query,一个文档的后验概率,可以通过一个softmax函数:

…(6)

其中,是一个softmax的平滑因子,它会根据经验进行设置。D表示待排序的候选文档集合。理想情况下,D应包含所有可能的文档。实现上,对于每个(query, click-document) pair,可以通过来表示。其中:

  • Q是一个query
  • 是点击的文档
  • 表示4个随机选中的未点击文档。

在我们的学习中,当使用不同抽样策略来选择未点击文档时,我们不会观察到任何不同。

在训练阶段,估计的模型参数会对给定queries下的点击文档的似然做最大化。事实上,我们需要最小化以下的loss function:

…(7)

其中,表示网络的参数集,由于 对于是可微的,模型的训练使用基于梯度的数值优化算法。

3.4 实现细节

为了决定训练参数以及避免overfitting,我们可以将点击数据分割成不重合的两部分,称为training set和validation set。在我们的实验中,我们使用如图1的三个hidden layers。第一个hidden layer是word hashing layer,它包含了30k节点(如表1所示的letter-trigrams的size)。下二个hidden layers具有300个hidden nodes,output layer具有128个nodes。word hashing会基于一个固定的投影矩阵。相似度会基于128维的output layer进行measure。根据[20],我们会在范围为:间的uniform分布来初始化网络权重,其中fanin和fanout是input和output units的数目。经验上,我们可以通过做layer-wise预训练但没有观察到更好的效果。在训练阶段,我们会使用mini-batch SGD来最优化模型。每个mini-batch包含了1024个训练样本。我们观察到DNN训练通常会在整个训练数据的20 epochs内收敛。

实验

详见paper。

参考

PNN是上海交大Yanru Qu等人提出的:

一、介绍

使用在线广告中的CTR预估做为示例来建模和探索对应的metrics效果。该任务会构建一个预测模型来估计用户在给定上下文上点击一个特定广告的概率。

每个数据样本包含了多个field的类别数据,比如:User信息(City, Hour等),Publisher信息(Domain、Ad slot,等),以及广告信息(Ad creative ID, Campaign ID等)。所有这些信息都被表示成一个multi-field的类别型特征向量,其中每个field(比如:City)是一个one-hot编码的向量。这种field-wise one-hot编码表示可以产生高维且稀疏的特征。另外,field间还存在着局部依赖(local dependencies)和层级结果(hierarchical structures)。

他们探索了一个DNN模型来捕获在multi-field类别型数据中的高阶隐模式(high-order letent patterns)。并想出了product layer的想法来自动探索特征交叉。在FM中,特征交叉通过两个特征向量的内积(inner-product)来定义。

提出的deep-learning模型称为“PNN (Productbased Neural Network)”。在本部分,会详细介绍该模型以及它的两个变种:IPNN(Inner Product-based Neural Network)、OPNN(Outer Product-based Neural Network);其中IPNN具有一个inner-product layer,而OPNN则具有一个outer-product layer。

1.1 PNN

图1: PNN

PNN模型的结构如图1所示。从上到下看,PNN的输出是一个实数值 ,作为预测CTR:

…(1)

其中,是output layer的参数,是第二个hidden layer的output,是sigmoid激活函数:。其中,我们使用来表示第i个hidden layer的维度。

第二个hidden layer的输出为:

…(2)

其中是第一个hidden layer的输出。relu的定义为:

第一个hidden layer是fully_connected product layer。它的输入包含了线性信号和二阶信号的定义如下:

…(3)

其中所有的

接着,定义tensor的内积(inner product)操作:

…(4)

内积会首先对A, B进行element-wise乘积,接着对这些element-wise乘积进行求和得到一个标量(scalar)。之后,会分别通过z和p进行计算:

…(5)

其中是在product layer中的weights,它们的shapes分别由z和p决定。

通过引入一个”1”常量信号,product layer不仅能生成二阶信号p,也能管理线性信号z,如图1所示。更特殊地:

…(6)

…(7)

其中是field i的embedding vector。定义了pairwise特征交叉。通过为g设计不同的操作,我们的PNN模型具有不同的实现。在该paper中提出了两个PNN的变种:IPNN和OPNN。

field i的embedding vector:,是embedding layer的ouput:

…(8)

其中x是包含了多个field的输入特征向量,表示embedding layer的参数,是与第i个field进行fully_connected。

最后,会使用监督学习来最小化logloss:

…(9)

其中,y是ground truth(1为click,0为non-click),是我们模型在等式(1)中的预测CTR。

1.2 IPNN

基于内积的神经网络(IPNN)中,我们首先定义了pair-wise特征交叉作为向量内积:

有了常数信号”1”,线性信息z会被保留:

…(10)

对于二阶信号p,pairwise的内积项形成了一个二阶矩阵。回顾下公式(5)的定义,和向量内积的交换律,p和是对称的。

这样的pairwise连接扩展了神经网络的能力(capacity),但也极大地增了了复杂性。在这种情况下,在等式(3)中描述的的公式,具有的空间复杂度,其中和M是关于网络结构的超参数,N是input fields的数目。受FM的启发,我们提出矩阵因子分解(matrix factorization)的思想来减小复杂度。

通过引入假设,其中,我们可以将简化成:

…(11)

其中,出于便利,我们使用来表示一个特征向量通过来加权,例如,。以及我们也有

在第n个单个结点上进行1阶分解,我们给出了的完整形式:

…(12)

通过在公式(12)中的的reduction,的空间复杂度变成。总之,复杂度从二阶降至线性(对N)。这种公式对于一些中间结果可以复用。再者,矩阵操作更容易在GPU上加速。

更普通的,我们讨论了的K阶分解。我们应指出只对该假设进行一阶分解。总的矩阵分解方法可以来自:

…(13)

在这种情况下,。这种通用分解具有更弱的猜想,更具表现力,但会导至K倍的模型复杂度。

1.3 OPNN

向量的内积采用一对向量作为输入,并输出一个标量。不同于此,向量的外积(outer-product)采用一对向量,并生成一个矩阵,在该部分,我们讨论了OPNN。

在IPNN和OPNN间的唯一区别是,二次项p。在OPNN,我们定义了特征交叉:。这样对于在p中的每个元素,是一个方阵(square matrix)。

为了计算,空间复杂度是,时间复杂度也是。回顾下和M是网络结构的超参数,N是input fields的数目,实际上该实现很昂贵。为了减小复杂度,我们提出了superposition的思想。

通过element-wise superposition,我们可以通过一个大的step来减小复杂度。特别的,我们重新定义了p公式:

…(14)

其中变成对称的,这里的也应是对称的。回顾下公式(5) 。在这种情况下,空间复杂度变成了,时间复杂度也是.

对比起FNN,PNN具有一个product layer。如果移除product layer的了部分,PNN等同于FNN。有了内积操作,PNN与FM相当相似:如果没有hidden layer,并且output layer只是简单地使用weight=1进行求和,PNN等同于FM。受Net2Net的启发,我们首先训练了一个PNN来作为初始化,接着启动对整个网络的back propagation。产生的PNN至少和FNN或FM一样好。

总之,PNN使用product layers来探索特征交叉。向量积可以看成是一系列加法/乘法操作。内积和外积只是两种实现。事实上,我们可以定义更通用或复杂的product layers,来在探索特征交叉上获取PNN更好的capability。

类似于电路,加法就像是”OR”门,而乘法则像”AND”门,该product layer看起来是学习规则(rules)而非特征(features)。回顾计算机视觉方法,在图片上的象素是真实世界中的原始特征(raw features),在web应用中的类别型数据是人工特征(artificial features)具有更高级和丰富的含义。Logic在处理概念、领域、关系上是一个很强的工具。这样我们相信,在神经网络中引入product操作,对于建模multi-field categorical data方面会提升网络能力。

实验

详见paper。

参考

我们来看下criteo公司的Flavian Vasile提出的《Meta-Prod2Vec Product Embeddings Using Side-Information for Recommendation》:

1.介绍

Prod2Vec算法只使用由商品序列(product sequences)确立的局部商品共现信息来创建商品的distributed representations,但没有利用商品的元信息(metadata)。Prod2Vec的作者提出了一个算法扩展:以序列结构的方式利用上下文内容信息,但该方法只针对文本元信息,产生的结构是层次化的,因而会缺失一些side informations项。我们结合了在推荐上的工作,使用side information并提出了Meta-Prod2Vec,它是一个通用方法,可以以一种很简单高效的方法,来增加类别型(categorical) side information到Prod2vec模型中。将额外项信息作为side information的用法(例如:只在训练时提供),受推荐系统在实时打分时要保存的特征值数量限制的启发。这种情况下,只在训练时使用的metadata,当提升在线效果时,可以让内存占用量(memory footprint)保持常数(假设一个已经存在的推荐系统会使用item embeddings)。

在30Music的listening和playlists数据集的子集上,我们展示了我们的方法可以极大提升推荐系统的效果,实现开销和集成开销很小。

在第2节,我们会回顾相关工作。第3节,展示Meta-Prod2vec方法。第4节,展示实验实置和30Music数据集上的结果。第5节总结。

3.Meta-Prod2Vec

3.1 Prod2Vec

在Prod2Vec的paper[9]中,Grbovic等人提供了在从电子邮件的商品收据序列上使用Word2Vec算法。更正式的,结定一个商品序列的集合S: ,目标函数是发现一个D维的真实表示,以便相似的商品可以在产生的向量空间内更接近。

原算法(Word2Vec)原本是一个高度可扩展的预测模型,用于从文本中学习词向量,属于自然语言神经网络模型。在该领域大多数工作都是基于Distributional Hypothesis[27],它宣称在相同的上下文中出现的词更接近,即使意思不同。

该hypothesis可以被应用于更大的上下文中,比如:在线电商,音乐和媒体消费,这些服务的基础是CF算法。在CF设置中,服务的使用者(用户)被当成上下文使用,在该上下文中哪些商品共现过,从而在CF中产生经典的item 共现(co-occurence)方法。基于co-count的推荐方法和Word2Vec间的相似关系由Omer[16]确定;该作者展示了embedding方法的目标函数与矩阵分解(它包含了局部共现items的the Shifted Positive PMI)很接近,其中PMI表示Point-Wise Mutual Information:

其中是item频次,是i和j共现的次数,D是数据集的size,k是由负样本(negatives)与正样本(positives)的比率。

Prod2Vec Objective目标函数

在[23]中作者展示了Word2Vec的目标函数(与Prod2Vec相似),可以被重写成:给定目标商品(Word2Vec-SkipGram模型,通常在大数据集上表现很好),最小化加权交叉熵(期望和建模后的上下文商品的条件分布)。接着,条件分布的预测被建模成一个关于在目标商品和上下文商品向量间内积的softmax。

这里,是期望概率的交叉熵,表示基于输入商品和预测条件概率, 在输出空间J上看过的任何商品:

其中,表示商品i的输入频次,是商品对(product pair)(i,j)在训练数据中被观察到的频次数目。

图一: Prod2Vec架构

对于Prod2Vec产生的结构,如图1所示,使用一个只有单个hidden layer和一个softmax output layer的NN,位于中心窗口的所有商品的输入空间被训练成用于预测周围商品的值。

然而,由Prod2Vec生成的商品embeddings,只考虑了用户购买序列的信息,也就是局部共现信息(local co-occurrence information)。尽管这比在协同过滤(CF)中的全局共现频次更加丰富,它不会考虑其它类型的item信息(比如:item的metadata)。

例如,假设输入是关于已经被归好类商品的序列,标准的Prod2Vec embeddings不会建模以下的交互:

  • 给定关于商品p(属于类别c)的当前访问,下一个访问的商品更可能属于相同的类别c
  • 给定当前类别c,下一个更可能的访问类别是c,或者一个相关的类别(例如:在购买一件游泳衣后,很可能会有一个防晒油的购买行为,它们属于一个完全不同的商品类目,但相近)
  • 给定当前商品p,下一个类目更可能是c或者一个相关类目
  • 给定当前类别c,被访问的当前商品更可能是p或

前面提取,作者对Prod2Vec算法作为扩展,会同时考虑商品序列和商品文本信息。如果将该扩展方法应用于非文本元数据上,加上商品预列信息,该算法会建模商品元数据和商品id间的依赖,但不会将元数据序列和商品id序列连接在一起。

3.2 Meta-Prod2Vec

在第一节,已经有相关工作使用side information进行推荐,尤其是结合CF和CB的混合方法。在embeddings的方法中,最相关的工作是Doc2Vec模型,其中words和paragraph会进行联合训练(jointly),但只有paragraph embedding会被用于最终的任务中。

我们提出了相似的架构,在NN的输入空间和输出空间中同时包含side information,在嵌入的items和metadata间的交互相互独立进行参数化,如图2所示。

图二: Prod2Vec架构

Meta-Prod2Vec目标函数

Meta-Prod2Vec的loss扩展了Prod2Vec的loss,它会考虑4种涉及item元信息的额外交互项:

其中:M是元数据空间(例如:在30Music数据集中的artist ids),是正则参数。我们列出了新的交互项:

  • :给定输入商品的元信息M,所观察到的输入商品ids的条件概率 与 其预测的条件概率间的加权交叉熵。该side-information与其它三种类型不同,因为它会将item建模成关于它的metadata的函数。这是因为,在大多数情况下,该item的metadata与id更通用,可以部分解释指定id的observation。
  • : 给定输入商品的元信息M,所观察到的它的上下文商品id的条件概率 与 其预测的条件概率间的加权交叉熵. 一个架构是,正常的Word2vec loss被看成是,只有该交叉项与Doc2Vec模型提出的很接近,其中,我们可以使用一个更通用类型的item metadata来替代document id information。
  • : 给定输入商品I,它的上下文商品元信息值M的条件概率、与预测的条件概率 间的加权交叉熵。
  • : 给定输入商品的元信息M,它的上下文商品元信息值M的条件概率,与预测的条件概率 间的加权交叉熵。该模型会建模观察到的metadata序列,以及在它内表示关于metadata的Word2Vec-like的embedding。

总之,会分别对items序列和metadata序列的似然建模进行编码loss项。表示在给定元信息的情况下item id的条件似然,表示在item ids和metadata间的cross-item交叉项。如图3如示,我们展示了由Prod2Vec因子分解出的item matrix,以及另一个由Meta-Prod2Vec分解出的item matrix。

图三:将MetaProd2Vec看成是items和metadata扩展矩阵的矩阵分解

Meta-Prod2Vec的更通用等式,为4种类型的side information()引入了一个独立的

在第4节,我们将分析每种类型的side-information的相对重要性。当使用多种源的metadata时,每种源在全局loss中将具有它自己的项以及它自己的正则参数。

根据softmax正则因子,我们有机会将items的输出空间和metadata的输出空间选择是否进行独立开来。与在Word2Vec中使用的简化假设相似,这允许每个共现的商品对(product pairs)被可以被独立地进行预测(predicted)和拟合(fitted)(因此,给定一个输入商品,在输出商品集上添加一个隐式的相互排斥限制),我们在相同的空间中嵌入该商品和它的metadata,因此允许它们共享归一化限制(normalization constraint)。

Word2Vec算法的一个吸引点是它的可扩展性,它使用Negative Sampling loss在所有可能词的空间上近似原始softmax loss,可以只在正共现上使用抽样的少量负样本来拟合模型,最大化一个修改版本似然函数

其中:

其中,概率分布用于抽样负上下文样本,k是一个超参数,它指定了每个正样本对应的负样本的数目。side information loss项根据相同的公式进行计算,其中分别索引input/output空间。

在Meta-Prod2Vec中,将商品(products)和元信息(metadata)共同嵌入(co-embed)到loss中的影响是,对于任意正样本对(positive pair)潜在的负样本集合,会包含items和metadata值的联合。

最终对推荐系统的影响

由于共享embedding空间,用于Prod2Vec的训练算法保持不变。唯一一不同是,在新版本的训练对(training pairs)的生成阶段,原始item对会得到涉及metadata的额外pairs的协助。在线推荐系统中,假设我们增加一个涉及item embeddings的解决方案,在线系统不会增加任何改变(因为我们只在训练时使用metadata),对在线内存占用没有任何影响。

4.实验

如下。首先描述了评估任务设置,metrics和baselines。接着,我们报告了在30Music开放数据集上的实验。

4.1 Setup

我们评估了在事件预测任务(next event prediction task)上的推荐方法。我们考虑用户与items交叉的时间顺序序列。我们将每个序列分割成训练集、验证集、测试集。我们将拟合Prod2Vec和Meta-Prod2Vec模型的embedding,在每个用户序列的前n-2个元素上,在第n-1个元素上测试超参数效果,最终通过训练前n-1个items,并预测第n个item。

我们使用在训练序列中的最后一个item作为query item,我们使用下述的其中一种方法来推荐最相似的商品。

在第1节所示,由于技术限制,需要让内存占用保持常量,我们只在训练时对item的metadata感兴趣。因此,我们不会与将metadata直接用于预测时的方法做比较,比如:先前的基于内容的推荐(CB)embedding方法,用户和item被表示成item content embeddings的线性组合,其中商品通过关联的图片内容embeddings进行表示。

我们使用以下的评估metrics,对所有用户做平均:

  • K上的点击率(HR@K):如果测试商品出现在推荐商品的top K列表中,它就等于1/K。
  • Normalized Discounted Cumulative Gain(NDCG@K): 在推荐商品列表中,测试商品有更高的ranks。

使用上述metrics,我们比较了以下方法:

  • BestOf:top产品按它们的流行度进行检索。
  • CoCounts: 标准CF方法,它使用共现向量与其它items的cosine相似度。
  • Standalone Prod2Vec: 通过Word2Vec在商品序列上获取的向量进行cosine相似度计算得到推荐结果。
  • Standalone Meta-Prod2Vec: 它增强了Prod2Vec,使用item side information,并使用生成的商品embedding来计算cosine相似度。和Prod2Vec一样,目标是进一步解决冷启动问题。
  • Mix(Prod2Vec,CoCounts): 一个ensemble方法,它返回使用两者线性组合来返回top items。
  • Mix(Meta-Prod2Vec,CoCounts): 一个ensemble方法,, 它返回使用两者线性组合来返回top items。

4.2 数据集

30Music dataset:它从Last.fm API中抽取的一个关于listening和playlists的集合。在该数据集上,我们评估了关于推荐下一首歌预测的推荐方法。对于meta-prod2vec算法,我们利用track metadata,命名为artist信息。我们在一个100k用户sessions数据集的样本上运行实验,生成的vocabulary size为433k首歌和67k artists。

4.3 结果

见paper本身。

参考