A consensus set for the aggregation of partial rankings: the case of the Optimal Set of Bucket Orders Problem

📄 arXiv: 2502.13769v1 📥 PDF

作者: Juan A. Aledo, José A. Gámez, Alejandro Rosete

分类: cs.AI

发布日期: 2025-02-19

备注: 26 pages, 2 figures

💡 一句话要点

提出OSBOP方法，通过生成排序集合解决排序聚合问题，提升结果多样性和适应性。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 排序聚合 共识排序 桶排序 多样性 优化 机器学习 集合

📋 核心要点

  1. 传统排序聚合方法侧重于寻找单一共识排序，忽略了输入数据中的多样性。
  2. OSBOP旨在生成一个排序集合，每个排序代表一种共识，从而更好地捕捉输入偏好的多样性。
  3. 实验表明，OSBOP在不损失可解释性的前提下，显著提高了排序聚合的适应度。

📝 摘要（中文）

在排序聚合问题(RAP)中，解决方案通常是一个概括了一组输入排序的共识排序。不同的变体不仅在于用作输入和输出的排序类型，还在于用于评估所需输出排序质量的目标函数。相比之下，在一些机器学习任务(例如，子组发现)或多模态优化任务中，注意力集中在获得多个模型/结果，以解释输入数据或搜索空间中的多样性。因此，在本文中，我们建议提供一个排序集合作为RAP的解决方案，以更好地解释输入排序中表达的偏好。我们通过最优桶排序问题(OBOP)来例证我们的提议，OBOP是一种RAP，它包括找到一个概括了一组编码为优先级矩阵的输入排序的单一共识排序(带有并列)。为了解决这个问题，我们引入了最优桶排序集合问题(OSBOP)，它是OBOP的推广，旨在产生不是单个排序作为输出，而是一个共识排序集合。实验结果表明，通过提供一组共识排序，解决方案的适应度相对于原始OBOP显著提高，而不会失去可理解性。

🔬 方法详解

问题定义：论文旨在解决排序聚合问题（RAP），特别是最优桶排序问题（OBOP）。OBOP的痛点在于，它仅输出单一的共识排序，无法充分表达输入排序集合中可能存在的多种偏好模式。这种单一的共识排序在处理具有内在多样性的数据时表现不佳。

核心思路：论文的核心思路是将OBOP扩展到OSBOP，即最优桶排序集合问题。OSBOP不再寻找单一的最佳排序，而是寻找一个由多个排序组成的集合。每个排序都代表一种不同的共识，从而更好地捕捉输入数据的多样性。这种方法允许更灵活地表示和解释输入排序中的不同偏好。

技术框架：OSBOP的整体框架可以概括为：1）输入：一组排序，表示为优先级矩阵；2）算法：用于生成排序集合的算法（具体算法未在摘要中详细说明，属于未知信息）；3）输出：一个由多个共识排序组成的集合。每个排序都是一个桶排序，允许并列关系。算法的目标是最大化排序集合的适应度，即集合中的排序能够尽可能好地代表输入排序。

关键创新：关键创新在于从单一共识排序到排序集合的转变。这种转变使得能够更好地处理具有多样性偏好的排序聚合问题。与传统的OBOP相比，OSBOP能够提供更丰富、更具代表性的结果，从而更好地解释输入数据。

关键设计：摘要中没有提供关于具体算法和关键设计的详细信息。例如，如何定义排序集合的适应度函数，如何生成排序集合，以及如何控制集合的大小和多样性等细节都属于未知信息。这些细节需要在论文正文中查找。

🖼️ 关键图片

fig_0

📊 实验亮点

实验结果表明，通过提供一组共识排序，OSBOP的解决方案的适应度相对于原始OBOP显著提高。这意味着OSBOP能够更好地捕捉输入排序中的多样性偏好，从而提供更准确、更全面的排序聚合结果。具体的性能提升数据未在摘要中给出，属于未知信息。

🎯 应用场景

OSBOP方法可应用于推荐系统、子组发现、多模态优化等领域。在推荐系统中，可以为用户提供多个个性化排序列表，而不是单一的推荐列表。在子组发现中，可以识别多个具有不同特征的子组。在多模态优化中，可以找到多个局部最优解，从而更好地探索搜索空间。该方法能够提升结果的多样性和适应性，具有重要的实际应用价值。

📄 摘要（原文）

In rank aggregation problems (RAP), the solution is usually a consensus ranking that generalizes a set of input orderings. There are different variants that differ not only in terms of the type of rankings that are used as input and output, but also in terms of the objective function employed to evaluate the quality of the desired output ranking. In contrast, in some machine learning tasks (e.g. subgroup discovery) or multimodal optimization tasks, attention is devoted to obtaining several models/results to account for the diversity in the input data or across the search landscape. Thus, in this paper we propose to provide, as the solution to an RAP, a set of rankings to better explain the preferences expressed in the input orderings. We exemplify our proposal through the Optimal Bucket Order Problem (OBOP), an RAP which consists in finding a single consensus ranking (with ties) that generalizes a set of input rankings codified as a precedence matrix. To address this, we introduce the Optimal Set of Bucket Orders Problem (OSBOP), a generalization of the OBOP that aims to produce not a single ranking as output but a set of consensus rankings. Experimental results are presented to illustrate this proposal, showing how, by providing a set of consensus rankings, the fitness of the solution significantly improves with respect to the one of the original OBOP, without losing comprehensibility.