我正在阅读一篇名为Unsupervised Rank Aggregation with Domain-Specific Experience 的论文,在 2.1 节中,他们讨论了列表的两个排列之间的距离。此距离度量的一些示例是 Kendall Tau 距离和 Spearman Footrule 距离。此距离度量可能具有的属性是右不变性。在论文中,如果度量具有此属性,则意味着它不依赖于对象的索引方式。
这部分让我感到困惑,因为我并不真正理解对象的等级和对象的索引之间的区别。如果一个对象在一个排名列表中,它的索引是否与其排名直接相关?此外,他们提到 Kendall Tau 距离是右不变的,但它的公式表明它取决于对象 i 和 j 的索引。那么,在秩聚合的上下文中究竟什么是右不变性。
您正在排名的对象以列表的形式到达算法,而您汇总的排名作为作用于列表的排列到达算法。列表的顺序/输入列表中对象的索引应该无关紧要:算法应该以相同的方式对对象进行排序(分配相同的新索引),而不管原始排序(忽略原始指数)。新索引对应于等级并且很重要。旧索引(在对象列表和输入排名中)是输入表示的产物,必须小心以确保它们被忽略。说输入列表中对象的索引无关紧要与说改组输入列表不会改变算法的输出相同。由于您聚合的排名由输入列表的排列表示,因此通过某种排列对输入列表进行混洗需要您将所有排名置换乘以混洗置换的倒数,以获得相同的对象实际排名. 由于所有这些新洗牌的排名排列仍然代表相同的排名,
关于 Kendall tau 距离的右不变性:考虑公式2(x - 3) + 6 - 2x
。这看起来取决于您选择的数字x
,但实际上它始终为零,因此实际上并非如此。对于 Kendall tau 来说也是如此:它是正确不变的可能不是很明显(对我来说当然不是很明显);您可能需要坐下来用数学方法向自己证明这一点。(如果他们甚至不参考证明,如果你仔细想想,我认为这实际上是非常微不足道的,但这不是我的领域,如果没有铅笔和纸,我不会得到它。)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句