Resumen Técnico: Modelos Jerárquicos de Orden Parcial para el Ranking

Planteamiento del Problema

La agregación de rankings busca combinar listas ordenadas de diversas fuentes en una estructura de consenso. Los modelos paramétricos clásicos, como Mallows y Plackett–Luce, asumen que las preferencias se concentran alrededor de uno o más rankings de consenso completos (órdenes totales). Sin embargo, en muchas aplicaciones, la suposición de que la verdadera estructura de preferencia es un orden total no está justificada; los evaluadores pueden considerar que ciertos elementos son incomparables. Además, los datos de preferencia suelen exhibir estructuras de grupo (por ejemplo, diferentes evaluadores, escenarios distintos o segmentos de series temporales) que los modelos existentes tienen dificultades para acomodar mientras preservan las estructuras de orden parcial.

Si bien trabajos recientes han relajado la suposición de orden total para permitir órdenes parciales (posets), y otros trabajos han introducido extensiones jerárquicas para órdenes totales, existe una falta de un marco unificado que combine el agrupamiento jerárquico con el consenso de orden parcial. Los modelos jerárquicos existentes para órdenes parciales (por ejemplo, Arcagni et al., 2022) dependen de estimaciones puntuales basadas en pérdida en lugar de la inferencia bayesiana generativa.

Metodología

El artículo introduce los modelos de Orden Parcial Jerárquico (HPO) y su extensión de agrupamiento no supervisado (HCPO).

1. El Marco HPO

El modelo HPO está diseñado para datos de orden de ranking que provienen de grupos etiquetados (por ejemplo, $A$ evaluadores). Está estructurado como un árbol con un nodo raíz que representa un orden parcial "global" y nodos hoja que representan órdenes parciales específicos de cada evaluador.

• Construcción de Variables Latentes: El modelo parametriza los órdenes parciales mediante variables latentes continuas. Para cada elemento $j$ en el universo de elecciones, existe un vector de pesos de preferencia $U_j \in \mathbb{R}^K$. Un orden parcial se forma mediante la intersección de $K$ órdenes completos derivados de estos pesos.
• Proceso Generativo:
  • Nivel Global: Se extrae una matriz de pesos latentes globales $U^{(0)}$ de una distribución normal multivariante con una estructura de correlación controlada por $\rho$.
  • Nivel Local: Para cada evaluador $a$, los pesos latentes $U^{(a)}$ se extraen condicionalmente de $U^{(0)}$ mediante una distribución normal multivariante con el parámetro de correlación $\tau$. Este parámetro $\tau \in (0, 1]$ controla la "contracción" (shrinkage) de los posets específicos del evaluador hacia el poset global.
  • Mapeo a Posets: Los pesos latentes se transforman mediante una construcción Gumbel (usando la función inversa de la CDF de la distribución Gumbel aplicada a la CDF normal) para generar puntuaciones de preferencia $\eta$. El orden parcial $h^{(a)}$ se define por la intersección de los órdenes derivados de estas puntuaciones.
• Modelos de Observación: El artículo propone tres verosimilitudes para observar un ranking $y$ dado un poset $h$:
  1. Libre de ruido: Muestreo uniforme de extensiones lineales (computacionalmente costoso para $M$ grandes).
  2. Salto de cola (Queue-jumping): Un modelo de selección repetida donde, con probabilidad $p$, se elige un elemento al azar (ruido), y de lo contrario se elige basado en las restricciones del poset.
  3. Salto de cola ponderado (Weighted Queue-jumping): Una extensión donde las elecciones aleatorias están sesgadas por las puntuaciones latentes $\eta$, haciendo que los errores sean menos probables para elementos con grandes brechas de preferencia.
  4. Frontier-softmax: Un modelo de utilidad donde los elementos se eligen de la "frontera" (elementos maximales) del suborden restante, ponderados por el número de elementos que dominan. Es computacionalmente eficiente ($O(M)$ por paso) y adecuado para conjuntos de datos grandes.

2. El Marco HCPO

Cuando las etiquetas de grupo son desconocidas, el artículo extiende HPO a modelos de Agrupamiento de Orden Parcial Jerárquico (HCPO).

• Agrupamiento (Clustering): Se coloca un proceso de Pitman-Yor sobre la partición de las listas (o evaluadores) en $G$ grupos latentes.
• Inferencia: El número de grupos $G$ y las asignaciones de los clústeres se infieren conjuntamente con la jerarquía del poset mediante MCMC.
• Agrupamiento de Evaluador vs. Lista: El modelo puede agrupar listas individuales o evaluadores completos (moviendo todas las listas de un evaluador juntas).

3. Inferencia Bayesiana

La inferencia se realiza mediante MCMC. La distribución posterior es sobre los parámetros de correlación ($\rho, \tau$), las matrices de pesos latentes ($U$), los coeficientes de regresión ($\beta$) y la partición ($C$). La dimensión del espacio latente $K$ también puede inferirse mediante MCMC de salto reversible (reversible jump MCMC).

Principales Contribuciones

1. Modelos HPO y HCPO: La introducción de un marco bayesiano generativo para datos de ranking agrupados que modela explícitamente estructuras de consenso de orden parcial, extendiendo el modelo Plackett–Luce al dominio de los posets.
2. Propiedades Teóricas:
   • Prueba de que los modelos Plackett–Luce y sus variantes jerárquicas son casos especiales de HPO (cuando $K=1$).
   • Demostración de que el modelo es marginalmente consistente, asegurando que la distribución previa de los subórdenes sea consistente con la distribución previa del universo completo.
   • Prueba de que el modelo puede representar cualquier jerarquía de posets siempre que $K \ge \lfloor M/2 \rfloor$.
3. Nuevos Modelos de Observación: El desarrollo de las verosimilitudes Weighted Queue-jumping y Frontier-softmax, que permiten el ruido y la eficiencia computacional manteniendo una interpretación generativa.
4. Agrupamiento No Supervisado: La extensión a HCPO para descubrir estructuras de agrupación latente en datos de ranking no etiquetados.

Resultados Experimentales

El artículo evalúa los modelos en conjuntos de datos sintéticos y del mundo real:

• Datos Sintéticos (HPO): En entornos con grupos etiquetados, HPO recupera con éxito la jerarquía latente de los posets. La precisión de la recuperación está impulsada principalmente por la longitud de las listas observadas (tamaño del conjunto de elección) y la fuerza de acoplamiento ($\tau$). La verosimilitud Frontier-softmax ofrece mejoras significativas en velocidad computacional (escalando linealmente con la longitud de la lista) en comparación con los métodos exactos de conteo de extensiones lineales, que se bloquean para $M \ge 50$.
• Datos Sintéticos (HCPO): En entornos no etiquetados, HCPO recupera con precisión tanto la estructura de agrupación latente como los posets específicos de cada clúster. El beneficio del agrupamiento es más pronunciado cuando el acoplamiento entre grupos es débil (alta heterogeneidad).
• Trazas de Aprovisionamiento de Nube (Agentes LLM): Aplicado a trazas de ejecución de agentes de LLM (Aliyun Cloud-IaC-6). El modelo HPO, tratando los diferentes escenarios como grupos, superó a las líneas base de un solo poset independiente en la recuperación de los grafos de dependencia subyacentes (estructuras de flujo de trabajo). El agrupamiento jerárquico mejoró la recuperación de las restricciones de precedencia, particularmente en escenarios con datos dispersos.
• Datos de Preferencia Humana (Sonido 3D): Aplicado a datos de preferencia de pares acústicos donde los oyentes exhibieron patrones cíclicos (que violan los órdenes totales). El modelo HCPO superó significativamente a las líneas base de orden total (mezclas de Plackett–Luce y Mallows) en ajuste predictivo (WAIC). Crucialmente, los resúmenes de HCPO revelaron estructuras interpretables donde los clústeres contenían capas superiores amplias de elementos incomparables, una característica que los modelos de orden total no podían representar sin forzar rankings estrictos arbitrarios.

Significancia y Reivindicaciones

El artículo afirma que los marcos propuestos HPO y HCPO proporcionan una forma fundamentada de manejar datos de ranking agrupados donde las preferencias pueden ser incompletas o incomparables.

• Interpretabilidad Estructural: Los modelos permiten la recuperación de estructuras de orden parcial que reflejan incomparabilidades genuinas, evitando los artefactos introducidos al forzar los datos en órdenes totales.
• Compartición de Información: La estructura jerárquica permite la compartición de información fundamentada (contracción o shrinkage) a través de los grupos, mejorando la estimación en regímenes de bajos datos mientras se preservan los matices específicos de cada grupo.
• Viabilidad Computacional: La verosimilitud Frontier-softmax permite la aplicación de estos modelos a conjuntos de elementos más grandes donde el conteo exacto de extensiones lineales es intratable.
• Generalidad: El marco subsume los modelos jerárquicos Plackett–Luce existentes y extiende el dominio al de los órdenes parciales, ofreciendo un enfoque unificado tanto para datos de ranking agrupados etiquetados como no etiquetados.

Los autores enfatizan que su enfoque es superior a los métodos existentes basados en pérdida para órdenes parciales al proporcionar una distribución posterior bayesiana completa, lo que permite la cuantificación de la incertidumbre y la comparación de modelos mediante WAIC.