机器算法验证 - 验证排序算法的正确性 - 吾爱随笔录

验证排序算法的正确性

机器算法验证相关性排行游戏

2022-04-09 19:32:28

Stats noob 正在研究一种用于在锦标赛中对玩家进行排名的算法。

我有一组测试玩家，每个玩家都有一个“技能”值。我的算法模拟了一场“锦标赛”，其中玩家以某种顺序（例如瑞士配对）相互对抗（1v1）。在比赛结束时，我有每个玩家的排名。

例如，样本数据集可能类似于：

Name | Tournament Rank | "True" Rank
Alex |        5        |      7
John |        1        |      2
Mike |        3        |      1
...

所以约翰赢得了比赛，尽管他是那里的第二好球员，而迈克实际上是最好的球员，但由于运气或其他原因碰巧获得了第三名。

考虑到每个玩家的“真实”技能和他们在锦标赛中的排名，我如何才能最好地量化我的锦标赛算法在对每个人进行排名时的表现如何？例如，我希望能够说出诸如“使用这组输入参数，我的锦标赛模拟器比使用其他输入参数集更准确地放置人员 10%”之类的话

（奖金问题：）

此外，对我来说，可以说比确切排名更重要的是玩家处于正确的玩家“桶”中。例如，如果我将结果分成 5 个部分（前 20%、第 60-80 个百分位数等），我需要我的锦标赛算法来可靠地将人们放入他们应得的存储桶中。你会做不同的事情吗？比上面检查人们如何最终进入桶的正确性？

1个回答

如果我理解正确，你想要的是一个衡量来比较潜在的真实排名和预测排名（即锦标赛排名或模拟排名），其中是一些输入的函数参数。 $\pi$ $\sigma$ $\sigma$

在统计文献中，有许多用于排名的距离函数。我将在下面列出其中的一些。设和和的行列（例如，和在您的示例中）。Kendall 距离定义为 Spearman 距离定义为 Spearman 脚尺距离定义为 $\pi(i)$ $\sigma(i)$ $i$ $\pi$ $\sigma$ $\pi(``\text{John}")=2$ $\sigma(``\text{John}")=1$

K (π, σ) = # {(i, j) | π (i) > π (j) and σ (i) < σ (j)} .

$K(\pi,\sigma) = \# \lbrace \; (i,j) \, \vert \, \pi(i)>\pi(j) \text{ and } \sigma(i)<\sigma(j) \; \rbrace \, .$

S (π, σ) = \sum_{i} {(π (i) - σ (i))}^{2} .

$S(\pi,\sigma) = \sum_i \left( \pi(i) - \sigma(i)\right)^2 \, .$

F (π, σ) = \sum_{i} | π (i) - σ (i) | .

$F(\pi,\sigma) = \sum_i \lvert \pi(i) - \sigma(i)\rvert \, .$ 这是三个广泛使用的排名距离函数。您可以将距离视为预测排名相对于真实排名所遭受的损失，因此距离越小越好。如果您需要准确度（越大越好）而不是损失，这些距离可以很容易地归一化为不同类型的排名相关系数。

关于奖金问题：

我认为有很多不同的方法可以做到这一点。例如，将真实排名中的项目分成几组后，可以使用C-index来衡量预测排名的表现。在多方排序研究中，常用C-index。它是AUC（ROC曲线下面积）的一种延伸。您可以查看本文的第 4 节，其中简要介绍了 C-index。

其它你可能感兴趣的问题

上一篇豪斯曼检验 - 错误结论下一篇在 R 中验证聚类分析