从Elo Rating System谈到层次分析法

1. Elo Rating System

Elo Rating System对于很多人来说比较陌生，根据wikipedia上的解释：Elo评分系统是一种用于计算对抗比赛（例如象棋对弈）中对手双方技能水平的方法，它由Arpad Elo创建。(The Elo rating system is a method for calculating the relative skill levels of players in competitor-versus-competitor games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor.）。大家如果看过电影《社交网络》（The Social Network）的话，一定记得爱德华在玻璃窗上写给扎克伯格的，用以评价学校女生的算法——那就是Elo评分系统。Elo目前在许多国际比赛中用以进行选手（或者团队）的世界排名（电影中用作对女生进行评分，可以理解为两个女性在比拼谁更漂亮，尽管她们不一定愿意参加这个”比赛“）。

(1)  Elo Rating System的基本概念

对于一次有结果的双人（也可以是两个团队）对抗性比赛，对某方而言，结果无非三个：赢、平局、输。将比赛结果量化成积分的话，需要为每个结果赋予对应的分数值：赢+1，平+0.5，输+0。如果直接按照这种比赛结果进行积分的累计计算，显然是不公平的。如果某人参加比赛的次数较多，或者本身的积分较高，如果得分较低的选手赢了得分较高的选手，那么他获取的积分应该更高才对。这就是EOL Rating System提出的初衷。

Elo Rating System以两个选手（rated player）在存量比分上的差异作为比赛结果的预测因子（Predictor）,它是一个可以实现自我更正的系统（self-correcting）。Elo Rating System基于以下几个方面的假设：

H1：选手的最终比分成绩是一个服从正太分布的随机变量（Normal Distribution Random Variable ）

H2 : 一位选手比赛成绩的均值是他真正实力（True Skill）的表现；

H3 : 选手的实力评价完全由比赛的结果来判定；在象棋比赛中，我们不能够因为其中一参赛者走了一步很精彩的而认为这个选手的实力高，因为这是完全不可量化的，我们只能够根据比赛的结果来判定。换句话说，选手之间实力的差异程度可以通过比分的差异来判定。

对于两位选手A和B，假设他们的积分分别是Ra和Rb（电影中给每个女孩的基础得分是1400）。那么A和B进行比赛的得分期望是：

其中有：

，因此，对于上面的两条公式，我们也可以理解为是对双方实力的比例进行概率化，分界点是0.5，上述的完整公式也可以在连续下表述成：

（PS：越看这条公式越是觉得它漂亮，充分体现了以前研究生一位老师说过的话：跟跑得慢的人一起跑，跑得快也是慢，跟跑得快的人一起跑，跑得慢也是快。）

在实际操作当中，由于选手的期望实力是未知的，我们通常采用选手的现有积分作计算其期望积分。如果一个选手在一次比赛中超越了它的期望成绩，那么Elo系统就认为这个选手的实力被低估了，应该往上调整，同理，如果低于期望值，那么Elo系统就会降低这位选手的评分。假设，对于一位选手A，他的期望低分是Ea，而实际得分是Sa，则根据Elo的线性调整建议，两位选手得分的更新策略是：

其中，K是一个调整步长，可根据选手的分级水平进行设定。Elo在国际象棋中，建议Master级的K=16，一般级别的K=32。举个例子，现在两个选手，A和B，他们的积分分别是Ra=1600，Rb=1530，他们进行比赛，结果B赢了，则比赛后，A和B的积分计算步骤如下（假设K=32，win+1，lose0 draw 0.5）：

结果是：Ra=1619.18，Rb=1510.82。由于这次A和B的得分是比较接近的，所以输赢的分配是较为均等，我们如果将A的本来领先优势扩大的话，如果跟B连续进行比赛，那么他赢得比赛得到的加分趋势如下——

2. 层次分析法（Analytic Hierarchy  Process，AHP）

人在决策时，通常都需要考虑多个因素。层次分析法（Analytic Hierarchy  Process, AHP),这是一种定性和定量相结合的、系统化的、层次化的分析方法，他根据决策因素的影响结果进行决策，与人们对某一复杂决策问题的思维、判断过程大体一致。

层次分析法的基本步骤：

（1） 建立层次结构模型

—— 一般需要三个层，最上面为目标层，最下面为方案层，中间为准则层/指标层

（旅游决策案例，下面会用这个图作为举例）

有时候，某一个方案的决策并不是需要考虑所有的准侧，诸如此类，如果上层的每个因素都支配着下一层的所有因素，或被下一层所有因素影响，称为完全层次结构，否则称为不完全层次结构。

（2）构建 成对比较矩阵

构建成对比较矩阵的目的在于将某一层的因素对上一层某一个因素相对影响程度进行量化处理。例如在上述案例中，准则层A对于目标层Z的影响就需要构建准则层对目标层的成对对比矩阵——构建成对比较矩阵的目的在于确定下层所有元素对上层的归一化权重w。

设某一层有n个元素，用A表示，对比该层所有元素的相对重要性程度，得到：

A就被称为成对比较矩阵。其中aij的值是两两比较的结果，即该层某个元素对应上一层目标因素的相对重要性，其中，满足：

（即该矩阵为一个正互反阵，满足a>0）

矩阵中的值是两两比较的结果，比较时取的尺度通常是1-9，对比的标准如下：

2,4,6,8表示第 个因素相对于第 个因素的影响介于上述两个相邻等级之间。旅游地点选择问题的两两对比结果如下：

成对对比矩阵：

根据旅游问题的层次结构模型，该决策问题共有6个成对对比矩阵：

1个5阶的：准则层对目标层；
5个3阶的：决策层对准则层；

上述得出的成对比较矩阵只是一个层对上层某一因素相对重要性在内部结果，下面进行的步骤关键是将这个对内的矩阵转化成对外的权重

一致阵与非一致阵

所谓的一致阵，是指对于上述的成对比较矩阵中，满足：，则称这个成对比较矩阵为一致阵，一致阵有以下的性质：

1 ) .  aij=1/aji ;

2 ) .  A的转置也是一致阵；

3 ）. A的各行成比例，则rank(A)=1

4  ). A的最大特征根（值）为n，其余n-1个特征根为0

5 ）.A的任一列（行）都是对应于特征根n的特征向量

定理：n阶互反矩阵A的最大特征值，当且仅当时，互反矩阵A才是一致性矩阵。

在将成对比较矩阵转化为权重之前，需要做一致性检验：

如果一个成对对比矩阵式一致性阵的话，则用特征根n对应的归一化特征向量W={w1,w2....wn}，其中wi表示下层第i个因素对上层某个因素影响程度的权值。
成对比较矩阵是非一致性矩阵的时候，那么就采用最大特征值对应的特征向量的归一化结果来作为权重向量W,则：
这样确定权重的方法称为特征根法
从特征值的变化来看，当比n大得多的时候，矩阵A的一致性程度就会越来越低（对于成对比较矩阵而言，就是各个要素之间相互评比的不一致程度较高），此时用使用最大特征根值对应的特征向量作为被比较因素对上层某因素影响程度的权重向量，其一致性程度越大引起的误判就越大。因而，我们需要用为一致性矩阵时的，对比 数值的大小来衡量A的不一致程度，定义一致性指标如下：

（其中n为对角线元素的和，也称为A的特征根之和）上面定义的CI（一致性指标）是一个绝对数指标，我们有一个客观标准来判定CI究竟是否可以接受。采用的方法是随机一致性指标RI来进行比较，通常随机一致性指标的值如下（随机构造500个成对比较矩阵，计算其平均CI）：

一般，当一致性比率

则认为成对比较矩阵的不一致性程度在容许范围之内，可以采用其归一化特征向量作为权重向量，否则要重新构造成对比较矩阵，对原始的矩阵加以调整。

（3）层次总排序及一致性检验

确定某一层所有因素对于总目标相对重要性的排序权重过程，称为层次总排序。

其实也就是确定每个决策方案对于总目标的影响程度，当已经完成某个下层对上层单一因素的影响后，应对总体某层的作用作总体评判。

从最高层到最低层。设：

计算B层的层次总排序：实质就是从纵向计算一个决策方案的总目标权重，然后衡量那个方案对总目标的权重结果较大。

层次总排序的一致性检验：设B层B1，B2......Bn对上层（A层）因素Aj的一致性指标为CIj，则层次总排序的一致性比率为：

当CR<0.1时，我们认为层次总排序通过一致性检验。

到此，根据最下层方案层的层次总排序结果做出最后决策。

层次分析法的优点和局限性：

优点：

系统性：将研究的对象作为一个系统，按照分解、比较、综合判断的方法进行决策，符合人的基本思维习惯。
实用性：将定性和定量方法结合起来，这种方法也让决策者和决策者能够相互沟通；
简洁性：整个方法的逻辑易于理解，计算也十分方便。

不足：

只能在备选方案中选择一个方案，无法拟合出最优方案
从建立层次模型到成对比较矩阵，整个过程人为因素影响很大，这就使得结果难以让所有决策者接受
该方法中的比较、判断以及结果的计算过程较为粗糙，不适合精度较高的问题。

3. 总结

将这两个方法放在一起谈，主要原因是两个方法都涉及到对一个因素进行对比的情况：在Elo系统中，我们是根据每个胜利者的期望进行对比计算，而在AHP中，则是通过定性的方法对比同一个层内各因素的相对重要性，各有优缺点。而从AHP中，学到的一个很重要的思维就是将一个系统内部的关系转化为对外的权重表现时，可以采用特征根的方法来解决。看来理解线性代数的物理含义和实际含义非常重要。

从Elo Rating System谈到层次分析法的相关教程结束。