在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，其中\(y \in \{ 0, 1\}\)表示用户点击行为的label。x也包含了类别型字段（比如：性别，位置）和连续型字段（比如：年龄）。每个类别型字段被表示成一个one-hot编码的向量，每个连续型字段用它原有的值进行表示，或者进行离散化one-hot编码表示。这样，每个实例可以被转换成(x,y)，其中 \(x = [x_{field_1}, x_{field_2}, .., x_{field_j}, ..., x_{field_m}]\)是一个多维向量，其中\(x_{field_j}\)是向量中的第j个字段。通常，x是高维且十分稀疏的。CTR预测的任务就是构建一个预测模型\(\hat{y} = CTR_{model}(x)\)来估计用户点击的概率。

2.1 DeepFM

图1

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

\[\hat{y} = sigmoid(y_{FM} + y_{DNN})\]

…(1)

其中\(\hat{y} \in (0, 1)\)是预测的CTR，\(y_{FM}\)是FM组件的输出，\(y_{DNN}\)是deep组件的输出。

2.1.1 FM组件

图2：FM组件架构

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

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

如图2所示，FM的输出是一个求和单元（Addition unit），以及多个内积单元：

\[y_{FM} = \langle w,x \rangle + \sum_{j_1=1}^{d} \sum_{j_2=j_1+1}^{d} \langle V_i,V_j \rangle x_{j_1} \cdot x_{j_2}\]

…(2)

其中 \(w \in R^d\), \(V_i \in R^k\)(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定义如下：

\[a^{(0)} = [e_1, e_2, ..., e_m]\]

…(3)

其中\(e_i\)是第i个field的embedding，m是field总数。接着，\(a^{(0)}\)被feed给DNN，forward处理如下：

\[a^{(l+1)} = \sigma(W^{(l)} a^{(l)} + b^{(l)})\]

…(4)

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

\[y_{DNN} = \sigma (w^{|H|+1} \cdot a^H + b^{|H|+1})\]

其中$|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

yahoo在2010年提出的《Learning to Blend Rankings: a Monotonic Transformation to Blend Rankings from Heterogeneous Domains》。

介绍

给定一个关于items的集合 \(X=\lbrace x_1, \cdots, x_n \rbrace\)，X的一个ranking是一个关于\([n]=\lbrace 1, \cdots, n \rbrace\)的排列。在l2r的领域中有大量研究[1,2,5,8,12]。然而，在许多应用中，我们需要将多个异构领域(heterogeneous domains)的关于items的rankings集成到一个关于在所有sets中所有items的单个ranking中，比如多种垂直搜索引擎(vertical search engine)：视频搜索、图片搜索、博客搜索等。例如，一个items集合可以是来自Web的文档集合，而另一个可以是来自一个垂直搜索引擎（比如：Blog或News搜索）的文档集合。将来自多个异构领域的rank lists进行合并是一个非平凡问题（non-trivial topic），因为：

• 1) 这些异构集合可以共享一些文档，但很可能也有许多非公共文档
• 2) 异构领域通常具有不同的features和feature-to-relevance相关性(correlations)

以问答网站（Yahoo! Answer）为例，尽管对于普通网站的text matching和click features可以被用于该domain的ranking中，使用这些独一无二的页面结构和用户反馈开发的features，比如：在Yahoo! Ansers中的点赞率(thumbs up ratings)和反馈总数(feedbacks)，在自有domain中的ranking上有大的用处。但Yahoo! Answers和普通网页文档共享的features在两个domains中的相关度上可能有非常不同的相关性。因此，需要使用一种跨domain的统一ranking function，以便在每个私有domain内更好地对文档进行排序，因此需要新的技术：将来自异构domains的文档融合(blend)到单个ranking list中。

我们想强调的是，该问题通常与rank aggregation问题[4,9]是相当不同的，RA问题需要在items的异构集合(homogeneous set)上将不同的rankings进行merge。

我们将来自多个异构域的rank lists进行集成(integration)定义为一个blending问题，将以如下方式将learning to blend rankings的问题进行公式化：

• a) 我们具有异构类型的items。每种类型的items在相应domain内都有一个rank order
• b) blending的训练数据的形式为：items sets和它相关的rankings的pairs，pair中的第一个属于items的某一类型(type)，第二者属于items的另一类型(type)。

最优组合排序(optimal combined rankings)是learning to blend的ground truth，可以以如下两个steps生成：

• 1) 为这些rankings中的每个item分配相关度标签，比如：Perfect, Excellent, Good, Fair, Bad (简写为：P/E/G/F/B)
• 2) 根据这些标签将ranking lists进行merge sort

以这种方式进行Blending可以最大化Discounted Cumulative Gain(DCG)，并且可以为这些rankings保留原排序（ordering）。

给定训练数据——组合排序（combined ranking）和在私有domain中的rankings，我们希望学到一种单调递增的转换（在私有domain上的ranking score），使得当使用关于(item sets, 相关rankings)的一个新pair时，我们可以使用转换后的ranking scores来生成一个combined ranking。

在本paper中，我们将该问题公式化成一个二次规划问题(quadratic programming problem)，并学习一个线性单调转换，使得在每个domain中的排序（rank order）保留，以及转换后的分值是可比的。

2.问题公式化

为了设计一个blending转换，我们假设：训练数据是一个包含了pairs\(\lbrace q_i \rbrace_{i=1}^Q\)的集合。在该工作中，我们主要关注以下场景：每个私有的ranking的order会在blending后保留。具有该constraint的Blending非常像归并排序（merge sorting）。

出于简洁性，假设我们只有两个rankings。考虑\(q_i\)，我们有：

\[R_1^i = \lbrace \langle d_{11}^i, r_{11}^i \rangle, \langle d_{12}^i, r_{12}^i \rangle, \cdots, \langle d_{1M}^i, r_{1M}^i \rangle \rbrace \\ R_2^i = \lbrace \langle d_{21}^i, r_{21}^i \rangle, \langle d_{22}^i, r_{22}^i \rangle, \cdots, \langle d_{2N}^i, r_{2N}^i \rangle \rbrace\]

其中，M和N分别是第一个set和第二个set的items数目，\(d_{1m}^i\)和\(d_{2n}^i\)是items。

在每个domain中的rank order为\(R_1^i\)和\(R_2^i\)，关于rankings的格式我们考虑两种situations：

• 1) 对于一个items集合，只有items的ranking
• 2) 对于一个items集合，每个item都有一个score，items的ranking通过items的scores引出，例如：ranking是通过对items的scores进行sorting获得的

给定一个关于item sets和它相关rankings的pair，我们可以区分三种cases：

• 两个sets都是situation 1)。我们需要学习一个transformation：它可以将一个set中的ranks与另一set的ranks相关联
• 一个set是situation 1)，另一个set是situation 2)。我们需要学习一个transformation：它可以将一个set中的ranks与另一个set中的scores相关联
• 两个sets都是situation 2)。我们需要学习一个transformation：它可以将两个sets中的scores进行校正(calibrate)

对于在situation 1)中的一个ranking \(r_{1m}^i\)或\(r_{2n}^i\)是它的rank的负数，而在situation 2)中是相应的score。因此，三种cases可以使用一个公式进行表述。

对于\(R_1^i\)和 \(R_2^i\)，我们有：

\[r_{11}^i \geq r_{12}^i \geq \cdots \geq r_{1M}^i \\ r_{21}^i \geq r_{22}^i \geq \cdots \geq r_{2N}^i\]

对应于\(R_1^i\)和\(R_2^i\)，我们也具有共M+N items的combined ranking（出于简洁，这里假设两个list间没有重叠items）：

\[R^i = \lbrace \cdots, d_{1m}^i, \cdots, d_{2n}^i, \cdots \rbrace\]

根据需要，来自两个list的items的原list顺序会被保留。

相应的，我们定义了\(\lbrace (m,n) 1 \leq m \leq M, m \leq n \leq N \rbrace\)两个子集：\(S_i^+\)对应于\(d_{1m}^i\)的rank高于\(d_{2n}^i\)的cases，\(S_i^-\)对应于\(d_{1m}^i\)的rank低于\(d_{2n}^i\)的cases，并定义了：

\[S^+= \bigcup\limits_{q_i \in Q} S_i^+, S^- = \bigcup_{q_i \in Q} S_i^-\]

核心问题是，如何从训练数据中自动化学习一个blending transformation。我们提出在\(R_2^i\)中对\(r_{2n}^i \ (n=1, \cdots, N)\)使用一个单调递增函数\(f(\cdot)\)，使得该blending可以基于\(r_{1m}^i\)和\(f(r_{2n}^i)\)。通过这样做，来自每个单独的ranking list的顺序(order)可以被自动保留。\(f(\cdot)\)的学习会最大程度地遵循editorial blending ranking。（假设我们具有X个rankings，\(X \geq 2\)。可以选择其中之一做为参照点，其余\(X-1\)个transformations会被学到）

3.算法

3.1 我们的算法

我们将transformation learning问题公式化成一个二次规划问题。

\[min \sum\limits_{k=1}^K \zeta_k^2\]

服从：

\[r_{1m}^i \geq f(r_{2n}^i) - \zeta_k \ \ \ (m,n) \in S_i^+, \\ f(r_{2n}^i) \geq r_{1m}^i - \zeta_k \ \ \ (m,n) \in S_i^-, \\ \zeta_k \geq 0\]

其中：

• K是来自\(S_i^+\)和\(S_i^-, i=1, \cdots, Q\) 两者的items的总数目。

如果假设\(f(\cdot)\)是线性的，并且形式为：\(f(x)=\alpha x + \beta\)，上述问题将变为：

\[\underset {\alpha, \beta, \zeta_k}{min} \sum\limits_{k=1}^K \zeta_k^2 + \lambda_1 \alpha^2 + \lambda_2 \beta^2\]

…(1)

满足：

\[r_{1m}^i \geq \alpha r_{2n}^i + \beta - \zeta_k \ \ \ (m,n) \in S_i^+, \\ \alpha r_{2n}^i + \beta \geq r_{1m}^i - \zeta_k \ \ \ (m,n) \in S_i^-, \\ \zeta_k \geq 0, \alpha \geq 0\]

通过求解以上QP问题，我们可以获取该线性变换（linear transformation）的一个\((\alpha, \beta)\) （相同的\((\alpha, \beta)\)可以被应用到所有queries上）

如果query的分类信息足够，我们也可以为每个query length、或者每种类型的queries学习一个\((\alpha, \beta)\)。在等式(1)中的constraints会给定相同的权重，它可以进行调整来为更重要的constraints提供更高的weights。其它非线性单调变换在将来的工作中会进行探索。

等式(1)演示了两个domains的思想。该算法可以轻易地扩展到blend超过两个的rankings上。给定来自X domains的ranking lists，选择其中一个作为参照点，其余X-1的转换\((\alpha_1, \beta_1), \cdots, (\alpha_{X-1}, \beta_{X-1})\)。该QP问题的constraints会涉及到来自任意两个domains的item sets的所有pairs，例如：该问题将变为：

\[\underset{\alpha_v, \beta_v, \zeta_k}{min} \sum_{k=1}^{K} \zeta_k^2 + \lambda_{1,1} \alpha_1^2 + \lambda_{1,2} \beta_1^2 + \cdots + \lambda_{X-1,1} \alpha_{X-1}^2 + \lambda_{X-1,2} \beta_{X-1}^2\]

符合：

\[\alpha_u r_{um}^i + \beta_u \geq \alpha_v r_{vn}^i + \beta_v - \zeta_k \ \ \ (m,n) \in \underset{u, v_i}{S^+}, \\ \alpha_v r_{vn}^i + \beta_v \geq \alpha_u r_{um}^i + \beta_u - \zeta_k \ \ \ (m,n) \in \underset{u, v_i}{S^-}, \\ r_{1m}^i \geq \alpha_u r_{um}^i + \beta_u - \zeta_k \ \ \ (m,n) \in \underset{1,u_i}{S^+}, \\ \alpha_u r_{um}^i + \beta_u \geq r_{1m}^i - \zeta_k \ \ \ (m,n) \in \underset{1, u_i}{S^-}, \\ \zeta_k \geq 0, \alpha_v \geq 0, u, v = 1, \cdots, X-1\]

4.实验

4.1 数据

我们对提出的算法进行了评估，所使用数据为：使用web搜索结果与Yahoo！Answers domain产生的垂直搜索结果进行blending。1300个queries从一个商业搜索引擎的query logs中抽样得到，800个queries被用于训练，500个用于validation。对于每个query，我们具有两个集合的文档：普通web文档、Yahoo! Answers文档。每个文档会被5种label之一进行标记(label)：Perfect、Excellent、Good、Fair和Bad，以相关度的递减序排列。我们在每个domain上具有预生成的ranking functions，并于rank score \(r_{1m}^i\)或\(r_{2n}^i\)可以通过在每个domain上对相应domain的文档使用ranking function生成。给定\(R_1^i\)和\(R_2^i\)，QP问题的constrains可以通过应用merge-sort到两个rank lists上进行构建，并在web文档和Answers文档间保留paired score perference。

4.2 实验

为了评估提出的算法，我们只关注\(f(\cdot)\)是线性变换的简单case，例如：\(f(x)=\alpha x + \beta\)。使用800个queries来学习transformation和500个queries用于validation。

Baseline方法

我们对比的该baseline是Naive blending方法，其中\(r_{1m}^i\)和\(r_{2n}^i\)的scores直接拿来比较进行排序。

评估metrics

我们上报了广泛使用的相度度指标：Discounted Cumulaive Gain(DCG)。对于一个N个文档的ranked list（N被设置成10, 或者实验中的1），我们使用以下的DCG变种：

\[DCG_N = \sum\limits_{i=1}^N \frac{G_i}{log_2(i+1)}\]

其中\(G_i\)表示在position i上分配的label的weights（比如：10表示Perfect match，7表示Excellent match, 3表示Good match等），相关度越高，DCG的值越高。我们使用DCG来表示：在testing queries的集合上的DCG值的平均。

在我们的应用中，目标是将Yahoo! Ansers的文档blend到web rank list中。我们上报了DCG1和DCG10, 如表1中的web rank list和blended list。我们的方法可以观察到有1.18% DCG10和0.9% DCG1增益。两者在统计上都是很大的提升。在我们的应用中，\(\lambda_1, \lambda_2\)的选择不会极大影响我们的实验，我们在实验中使用\(\lambda_1=1, \lambda_2=10\)。该Naive blending方法不会达到任何DCG的提升。这表明，从异构域的rank scores不能直接比较，需要一个blending算法。

也需要计算pair-wise error rate，（例如：item sets的pairs百分比，不能被正确rank）。换句话说，该error rate会衡量在QP问题中有多少constraints不能被满瞳。表2上报了error rate。学到的线性变换给出了一个35%的error rate。因此，我们会研究optimal DCG，螃蟹烧开吃测评发票merge-sort策略获取。

Blending的上界

merge-sort的思想是，两个ranking lists可以被认为是最好的DCG10(它可以通过blending获取)，例如：一个blending算法可以达到的上界。我们的测试数据中，最好的DCG 10是7.06. 因此，还有提升的空间。第5节会讨论将来的研究方法。

5.相关工作

最近几年，ranking问题被多次表示成一个监督机器学习问题。这些l2r方法可以组合不同类型的features来训练ranking functions。ranking的问题可以被看成是从pair-wise的偏好数据中学习一个ranking function。该思想是，最小化在训练数据中的矛盾对的数目。例如，RankSVM会使用SVM来学习ranking function。RankNet则使用神经网络来梯度下降来获取一个ranking function。RankBoost则使用boosting从一个弱ranking functions集合中来构建一个高效的ranking function。。。

受[10]的启发，我们的算法将一个pairwise ranking问题看成是一个二次规划问题。

6.略

参考

• 1.http://yichang-cs.com/yahoo/cikm10_blending.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所示。算法会采用一个矩阵\(M_{in}^{V \times D}\)，它包含了每个输入词的词表示；以及一个矩阵\(M_{out}^{V \times D}\)，它包含了每个输出词的词表示。每个词被表示为一个D维浮点数组，对应于两个矩阵的某一行。这些矩阵会在训练期间被更新。在图1中，我们选取一个目标词，以及围绕该目标词的N个输入上下文词组成的集合来做示例描述。该算法会在第2-3行上迭代N个输入词。在第6行的循环中，我们选取正样本（第8行的target word），以及一个随机负样本（第10行）。第13-15行为对应选中的输入词和正/负样本计算目标函数的梯度。第17-20行会对\(M_{out}[正/负样本]\)和\(M_{in}[输入上下文]\)中的条目进行更新。伪代码只展示了单个线程；在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算法中没有被利用。例如，我们可以很容易看到，对于多个输入词的更新，在模型中会使用相同目标词\(W_out^t\)。通过一次只进行单个更新，该位置信息会丢失，该算法会执行一系列level-1 BLAS操作[1]的点乘（dot-products），它受内存量（memory-bandwidth）限制。下面我们会展示，将这些操作batch成一个level-3 BLAS调用[1]，可以有效地利用计算能力和现代多核架构的指令集。

我们以2-steps的形式利用位置(locality)信息。受图1的启发，该图左侧展示了原始word2vec的并行化scheme。注意，我们通过给定输入词\(w_{in}^i\)、以及目标词\(w_{out}^t\)、同时还有K个负样本\(\lbrace w_{out}^1, ..., w_{out}^K\rbrace\)来计算词向量。我们不再一次只计算一个更新，而是将这些点乘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$的概率来给定：

\[P(p_1 > p_2 | s_1, s_2) = \Phi(\frac{s_1-s_2}{\sqrt{2}*\beta})\]

…(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 $, 其中：

\[\Delta = \alpha \beta \sqrt{\pi} (\frac{y+1}{2} - \Phi(\frac{s1-s2}{\sqrt{2} \beta}))\]

其中，$\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）可知，我们获得其先验分布为：

\[p(s|r,A) = \frac{P(r|s,A) p(s) }{p(r|A)}\]

…(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的概率被建模成：

\[P(r| \lbrace t1, ..., t_k \rbrace) = P(t_{r_{(1)}} > t_{r_{(2)}} >... > t_{r_{(k)}})\]

也就是说，表现的顺序决定了比赛结果的顺序。如果允许平局，获胜结果$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}）进行计算。

\[p(s | r, A) = \int_{-\infty}^{\infty}...\int_{-\infty}^{\infty}dp dt.\]

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

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

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

\[p(v_k) = \prod_{f \in F_{v_k}} m_{f \rightarrow v_k}(v_k)\]

…(3)

\[m_{f \rightarrow v_j}(v_j) = \int ... \int f(v) \prod_{i \neq j} m_{v_i \rightarrow f}(v_i) dv_{ \backslash j}\]

…(4)

\[m_{v_k \rightarrow f}(v_k) = \prod _{\hat{f} \in F_{v_k} \backslash {f}} m_{\hat{f} \rightarrow v_k} (v_k)\]

…(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)得到：

\[\hat{p}(d_i) = \hat{m}_{f \rightarrow d_i}(d_i) \cdot m_{d_i \rightarrow f}(d_i) \Leftrightarrow \hat{m}_{f \rightarrow d_i}(d_i) = \frac{\hat{p}(d_i)}{m_{d_i \rightarrow f}}(d_i)\]

…(6)

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

\[V_{I(\cdot > \epsilon)}(t, \epsilon) := \frac{N(t-\epsilon)}{\Phi(t-\epsilon)}, W_{I(\cdot > \epsilon)}(t, \epsilon) := V_{I(\cdot > \epsilon)}(t, \epsilon) \cdot (V_{I(\cdot > \epsilon)}(t, \epsilon) + t - \epsilon)\] \[V_{I(\cdot > \epsilon)}(t, \epsilon) := \frac{N(-\epsilon - t) - N(\epsilon -t)}{\Phi(\epsilon -t) - \Phi(-\epsilon -t) }\] \[V_{I(\cdot > \epsilon)}(t, \epsilon) := V_{I(\cdot > \epsilon)}^2(t, \epsilon) + \frac{(\epsilon -t) \cdot N(\epsilon -t) + ( \epsilon + t) N(\epsilon +t )}{\Phi(\epsilon -t) - \Phi(-\epsilon -t)}\]

表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$与平局的概率相关联：

\[draw-probability = \Phi(\frac{\epsilon}{\sqrt{n_1+n+2}}\beta) - \Phi(\frac{-\epsilon}{\sqrt{n_1+n_2}\beta}) = 2 \Phi(\frac{\epsilon}{\sqrt{n_1+n_2}\beta}) - 1\]

其中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 $，

\[q_{draw}(\beta^2, \mu_i, \mu_j, \sigma_i, \sigma_j) := \sqrt{\frac{2\beta^2}{2\beta^2 + \sigma_i^2 + \sigma_j^2}} \cdot exp(-\frac{(\mu_i - \mu_j)^2}{2 (2\beta^2 + \sigma_i^2 + \sigma_j^2)})\]

…(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

参考

• 0.microsoft TrueSkill paper

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

\[PR=\frac{w+400 + x+400 +y-400 + z-400}{4}\] \[=\frac{w+x+y+z+400(2) - 400(2)}{4}\]

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

\[PR=\frac{\sum{所有对手的ratings} + 400 * (Wins-Losses)}{Games}\]

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

\[PR=\frac{1000+400*(1)}{1}=1400\]

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

\[PR=\frac{2000+400*(2)}{2}=1400\]

如果和一选手打平了，则：

\[PR=\frac{1000+400*(0)}{1}=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。

\[K=\frac{800}{N_e + m}\]

3.6.2 Rating底数（rating floors）

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

\[AF = min (100 + 4 N_w + 2 N_D + N_R, 150)\]

其中，$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曲线）：

\[E_A=\frac{1}{1+10^{(R_B-R_A)/400}}\]

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

\[E_B=\frac{1}{1+10^{(R_A-R_B)/400}}\]

也可以表示成：

\[E_A = \frac {Q_A}{Q_A + Q_B}\]

和

\[E_B = \frac {Q_B}{Q_A + Q_B}\]

其中，$ 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$。排名更新公式为：

\[R'_A=R_A + K (S_A - E_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系统用于对女生的吸引力进行排名。（尽管电影中的方程式有些小错误）

参考

• 0.Elo ranking system