碗系列锦标赛 (BCS) 是 NCAA 大学美式橄榄球联赛的一个评分体系, 它被设计用来确定哪些队伍被邀请参加哪个系列的比赛。BCS 已经因为它给 NCAA 的每支队伍所打的分数而名声在外, 而且可能不是个好名声。这些评分有两个来源一一人以及计算机。人这一 方面的输人数据来自于教练和媒体; 计算机方面的输人则来自于 6 个计算机数学模型中给出。2001 赛季和 2003 赛季的 BCS 评分被体育迷和分析家认为是最具争议性的, 而且大多数人都已经熟知 BCS 选拔体系与某次季后赛结果存在冲突的瑕疵，这些人中甚至还包括了美国总统。

原始的梅西评分方法

在 1997 年, 当时还是布鲁菲尔德学院（Bluefield College）的一名本科生的肯尼斯 - 梅西, 提出了一种对大学美式橄榄球队进行排名的方法。 他利用了数学理论中的最小二乘法写成了一篇获奖论文, 我们称这种方法为梅西法。梅西此后成为了卡森-纽曼学院的一名数学教授, 而且现在仍然在改进他的体育排名模型。梅西教授已经提出了多个评分方法, 其中之一 被碗系列锦标赛（BCS）体系用于确定 NCAA 美式橄榄球季后赛的分组。由于我们并不清楚 BCS 所使用的梅西法的细节, 因而此处将描述我们已经了解了全部细节的那个梅西法, 即他在论文中所描述的那一个。

梅西的主要思路

梅西最小二乘法最根本的思路可以总结为一个理想化的方程 $$ r_i-r_j=y_k, $$

式中, $y_k$ 是比赛 $k$ 中获胜方所取得的优势; 而 $r_i$ 和 $r_j$ 分别为队伍 $i$ 和 $j$ 的评分。换而言之, 两支队伍的评分 $r_i$ 和 $r_j$ 之间的差值完美地预测了这两队进行比赛时获胜方的优势。

任何一个评分体系所要达到的目的, 是为一个具有 $n$ 支队伍且至今已总共进行了 $m$ 场 联赛的联盟中的每支队伍赋予一个评分。当然, 我们并不知道这些队伍的评分 $r_i$, 但是我 们确实知道谁和谁进行了比赛, 而获胜方的优势又是多少。因此, 对每一场比赛 $k$, 都对 应有一个上述形式的方程, 由此产生了一个包含 $n$ 个末知数的 $m$ 个线性方程的系统, 可 写为 $X r=y$ 系数矩阵 $X$ 中的每一行都几乎全部为 0 , 只是在位置 $i$ 上有一个 1 , 而在位置 $j$ 上有一个 $-1$, 这意味着队伍 $i$ 在这场比赛中击败了队伍 $j$ 。因此, $X_{m \times n}$ 是一个非常稀疏的矩阵。向量 $\boldsymbol{y}_{m \times 1}$ 是表示获胜方优势的右向量, 而 $r_{n \times 1}$ 是未知的评分向量。通常来说, $m>n$, 因此该线性系统是一个高度超定且矛盾的系统。不过这并不是说就无法对它进行求解, 因为由正规方程组（normal equations) $\boldsymbol{X}^{\top} \boldsymbol{X r}=X^{\top} \boldsymbol{y}$ 可以得到一个最小二乘解。这个最小二乘向量一一即正规方程组的解一一 (从方差的最小化的意义上而言）是原方程组 $X r=y$ 中评分向量 $r$ 的最佳线性无偏估计。 梅西发现, 由于 $\boldsymbol{X}$ 本身的结构上的特点, 使用系数矩阵 $M=X^{\top} X$ 更为有利。实际上, $M$ 根本不用计算就能得到, 因为我们有如下事实, 即该矩阵的对角元素 $M_{i i}$ 就是队伍 $i$ 所 完成的比赛场次的总数, 而非对角元素 $M_{i j}(i \neq j)$ 就是队伍 $i$ 与队伍 $j$ 对阵场数的相反数。通过类似的便捷方法, 还可以根据累计分差来获得正规方程组的右侧项 $\boldsymbol{X}^{\mathrm{T}} \boldsymbol{y}$ 。右向量 $X^{\top} \boldsymbol{y}$ 的第 $i$ 个元素是队伍 $i$ 在赛季中进行的所有比赛中的分差之和, 我们由此定义 $p=$ $\boldsymbol{X}^{\mathrm{T}} \boldsymbol{y}$ 。因此, 梅西的最小二乘系统就变为 $$ M r=p, $$ 式中, $M_{n \times n}$ 是上述的梅西矩阵; $r_{n \times 1}$ 是末知评分构成的向量; 而 $p_{n \times 1}$ 是表示累积分差的右向量。

梅西矩阵 $M$ 具有几点值得注意的性质。第一, $M$ 的大小比 $\boldsymbol{X}$ 要小得多。实际上, 它是一个 $n$ 阶对称方阵; 第二, 它是一个对角优势的 M-矩阵; 第三, 它每行的元素和为 0 , 因此 $\boldsymbol{M}$ 的各列是线性相关的。这带来了一个小问题, 即由于 $\operatorname{rank}(\boldsymbol{M})<n$, 线性系统 $M r=p$ 不具有唯一解。梅西在该问题中用于避开这一麻烦的解决方法, 是在 $\boldsymbol{M}$ 中任选一行, 以全 1 行来代替它, 并将 $p$ 中的对应元素设为 0 。这一做法在该线性系统中增加了一个约束, 它要求评分的总和必须为 0 , 而由此也得到了一个满秩的系数矩阵。在马尔可夫链稳态向量的直接求解法中也使用了类似的技巧, 。经过行调整后的新系统记为 $\overline{\boldsymbol{M}} \boldsymbol{r}=\overline{\boldsymbol{p}}$。

在范例上应用梅西评分法

现在我们为下面5 支队伍来产生梅西评分。

每支队伍都正好与其余各队比赛了 1 次, 因此 $M$ 的非对角元素都是 $-1$, 而对角元素都是 4。但为了保证 $\boldsymbol{M}$ 满秩（并因此获得唯一的最小二乘解), 我们使用梅西在参考文献中给出的技巧, 用所有评分之和等于 0 的这一约束来代替最后一行。因此, 梅西最小二乘系统 $\bar{M} r=\bar{p}$ 为 $$ \left(\begin{array}{ccccc} 4 & -1 & -1 & -1 & -1 \\ -1 & 4 & -1 & -1 & -1 \\ -1 & -1 & 4 & -1 & -1 \\ -1 & -1 & -1 & 4 & -1 \\ 1 & 1 & 1 & 1 & 1 \end{array}\right)\left(\begin{array}{l} r_1 \\ r_2 \\ r_3 \\ r_4 \\ r_5 \end{array}\right)=\left(\begin{array}{r} -124 \\ 91 \\ -40 \\ -17 \\ 0 \end{array}\right) \text {, } $$ 它给出了如下表所示的梅西评分和排名列表。

梅西评分法的高级特性

对于这个微型的数据集而言, 以上的结果是合理的, 但对于梅西法, 则还有更多东西可说 。实际上, 还有两个向量应当提及。梅西从总的评分向量 $\boldsymbol{r}$ 中创造了两个新的向量, 即评分之和, 即 $r_i=o_i+d_i$ 。梅西通过一些巧妙的代数运算将 $\boldsymbol{o}$ 和 $d$ 从 $\boldsymbol{r}$ 中抽取出来。但是, 要了解他所使用的代数方法, 我们还需要一些额外的记法。右向量 $p$ 的第 $i$ 个元素 $p_i$ 中保存 了队伍 $i$ 在该赛季所进行的所有比赛的累计分差, 现在将其分解为 $p=f-a$ 。向量 $f$ 为 “得 分” 向量, 记录了每支队伍在整个赛季中所获得的总得分, 而向量 $a$ 称为 “失分” 向量, 它 记录了每支队伍在整个赛季中所丢掉的分数之和。要理解梅西求取 $\boldsymbol{o}$ 和 $d$ 的方法, 我们还需 要进行另一个分解。梅西系数矩阵 $M$ 可以被分解为 $M=T-P$, 其中, $T$ 是一个对角阵, 记录了每支队伍所进行的比赛总数, 而 $\boldsymbol{P}$ 是一个非对角阵, 记录了赛季中所有队伍之间捉对斯杀的场数。我们从原始的梅西最小二乘系统 $M r=p$ 开始, 并通过一系列的替换来 说明这两个新向量 $\boldsymbol{o}$ 和 $d$ 是如何推得的。 $$ \begin{aligned} M r &=p \\ (T-p) r &=p \\ (T-p)(o+d) &=p \\ T o-P o+T d-P d &=p \\ T o-P o+T d-P d &=f-a_{\circ} \end{aligned} $$ 现在, 上述的最后一个方程可以被分为两个独立的方程。 $$ T o-P d=f \text { 和 } P o-T d=a \text { 。 } $$ 左边的方程 $T o-P d=f$ 说明, 一支队伍在整个赛季中所得的总分数, 可以通过将该队的 进攻评分与比赛场数相乘, 再减去对手的防守评分的总和而得到。继续对左边的方程进行 替换, 我们就可以更加接近于解出这两个新的评分向量 $o$ 和 $d$ 。 $$ \begin{aligned} T o-P d &=f \\ T(r-d)-P d &=f \\ (T+P) d &=T r-f_{\circ} \end{aligned} $$ 注意上述最后一行中的右侧项 $\boldsymbol{T r}-\boldsymbol{f}$ 是一个由常值构成的向量, 因为 $\boldsymbol{r}$ 已经得到了。因此, (给定 $r$ 时) 求解 $d$ 的梅西线性系统为 $$ (T+P) d=T r-f_{\circ} $$ 最后, 一旦 $r$ 和 $d$ 都已得到, $o$ 可以通过 $r=o+d$ 来求得。

梅西评分法的总结

以下是描述体育队伍排名的梅西法时所使用的符号。

资料来源