机构名称：
¥ 1.0
在许多情况下，对对象进行排名或排序是一个自然问题。从数学上讲，这项任务相当于从有限集合中找到“好的”排列，或者更一般地，从好的排列分布中抽样。这可能出奇地困难。例如，假设我们观察到一组成对的相互作用，如竞争、偏好或冲突，每个相互作用都表明一个对象的排名高于另一个对象，我们的目标是将它们从最强到最弱进行排序。类似地，我们可能想要重建节点加入不断增长的网络的顺序 [1,2]，例如在一场流行病中，接触追踪表明一个人感染了另一个人。在这种情况下，找到一个排列，使排序“错误”的违规数量最少，是 NP 难的，也就是说，这是计算机科学中最难的优化问题之一 [3]。即使存在与所有观察到的相互作用一致的排列，计算这种排列的数量或计算给定对象的平均位置也是#P-完全的[4,5]。因此，所有这些问题被认为在最坏情况下会花费指数时间。成对比较可以表示为有向图G，其边（i，j）表示i≺j，即i“击败”j，因此可能排名高于j。我们假设一个生成模型：给定一个真实排列π，我们以概率P（G |π）[6]观察到G。如果所有排列都是先验相等的，并且如果我们以概率f（πi，πj）独立地观察到每个i≺j，则后验具有以下形式
排列、排名和部分的信念传播......
主要关键词
相关文件推荐
