Resumen Técnico: Una Relajación Bayesiana Diferenciable para la Inferencia de Orden Parcial Latente

Enunciado del Problema

Muchos conjuntos de datos que involucran clasificaciones, trazas de agentes y flujos de trabajo se registran como secuencias lineales (órdenes totales). Sin embargo, las restricciones subyacentes que gobiernan estas secuencias a menudo están solo parcialmente ordenadas (posets). En tales contextos, un orden lineal observado puede reflejar una linealización arbitraria, programación o artefactos de registro en lugar de relaciones reales de prerequisito. Tratar todas las precedencias observadas como prerequisitos reales conduce a estructuras excesivamente secuenciales y poco realistas, particularmente en flujos de trabajo complejos o entornos de agentes LLM, donde un ordenamiento innecesario induce pasos de ejecución redundantes.

El desafío central es inferir el orden parcial latente a partir de estas extensiones lineales ruidosas. Si bien la inferencia bayesiana es natural para manejar la incertidumbre inherente a trazas escasas o ruidosas, los métodos actuales enfrentan un cuello de botella computacional severo. Los enfoques existentes de "PO duro" dependen de cadenas de Markov de Monte Carlo (MCMC) combinatorias para explorar el espacio discreto de órdenes parciales. Esto es computacionalmente prohibitivo porque contar las extensiones lineales de un poset es #P-completo. Además, la naturaleza discontinua de las restricciones de precedencia dura impide el uso de métodos eficientes de inferencia basados en gradientes (como MCMC basado en gradientes o inferencia variacional), limitando la escalabilidad a instancias pequeñas.

Metodología

Los autores proponen una relajación bayesiana diferenciable que transforma el problema de inferencia discreto y combinatorio en un problema de optimización continuo, preservando al mismo tiempo la estructura semántica del modelo duro original.

1. Parametrización del Orden Producto Latente

En lugar de muestrear directamente órdenes parciales, el modelo parametriza la estructura latente utilizando una matriz de incrustación $U \in \mathbb{R}^{M \times d}$, donde cada elemento $x$ se asigna a un vector latente $u_x$. La relación de precedencia dura se define mediante un orden producto: $z \succ_U x$ si y solo si $u_{z,k} > u_{x,k}$ para todas las dimensiones $k=1,\dots,d$. Esto permite la incomparabilidad (cuando los vectores no están estrictamente dominados en todas las dimensiones) y codifica la geometría del orden parcial.

2. Relajación Diferenciable de Restricciones Duras

Para habilitar la inferencia basada en gradientes, los autores reemplazan los componentes discontinuos de la verosimilitud con restricciones de frontera dura con sustitutos suaves:

• Precedencia Suave: El indicador duro $1[z \succ_U x]$ se reemplaza por una puntuación suave $D_U(z, x) = \sigma(\gamma M_U(z, x))$. Aquí, el margen mínimo duro $m_U(z, x) = \min_k (u_{z,k} - u_{x,k})$ se aproxima mediante una función de mínimo suave $smin_\tau$, y el indicador se suaviza mediante una función sigmoide $\sigma$ con un parámetro de nitidez $\gamma$.
• Frontera Suave: La frontera dura (el conjunto de elementos máximos disponibles para selección) se reemplaza por un peso de frontera suave $\tilde{F}_t(x; U)$. Este peso es el producto de $(1 - D_U(z, x))$ para todos los elementos restantes $z$, reduciendo efectivamente el peso de los elementos fuertemente precedidos por otros pero permitiendo una probabilidad no nula para elecciones fuera de la frontera.
• Verosimilitud Relajada: La verosimilitud original de softmax de frontera, que asigna probabilidad cero a elementos fuera de la frontera, se reemplaza por una versión relajada que asigna probabilidades pequeñas pero no nulas a elementos fuera de la frontera. Esto resulta en una función objetivo continuamente diferenciable con respecto a los parámetros de incrustación $U$.

3. Garantías Teóricas

El artículo proporciona varias pruebas teóricas sobre la relajación:

• Transitividad Suave: Las puntuaciones relajadas satisfacen una propiedad de transitividad suave ($\text{logit } D_U(z, x) \ge \text{logit } D_U(z, y) + \text{logit } D_U(y, x)$), que converge a la transitividad dura a medida que los parámetros de suavizado se acercan a sus límites.
• Recuperación en el Límite de Nitidez: A medida que la temperatura $\tau \to 0$ y la nitidez $\gamma \to \infty$, los pesos de frontera relajados y la verosimilitud convergen al modelo con restricciones de frontera dura.
• Consistencia Marginal: La priori sobre los órdenes parciales relajados es marginalmente consistente, asegurando que la distribución sobre sub-órdenes sea consistente con la distribución global.

4. Estrategias de Inferencia

La posterior continua permite la aplicación de algoritmos de inferencia eficientes:

• MCMC Relajado: Utiliza Monte Carlo Hamiltoniano (NUTS) para muestrear desde la posterior relajada.
• FullRank-VI: Emplea inferencia variacional con diferenciación automática (ADVI) con una aproximación gaussiana de rango completo.
• Flow-VI: Utiliza flujos normalizantes para modelar la distribución posterior, ofreciendo mayor flexibilidad que las aproximaciones gaussianas.

Contribuciones Clave

1. Relajación Diferenciable: La introducción de una relajación bayesiana diferenciable para la inferencia de orden parcial latente, que habilita el uso de MCMC basado en gradientes e inferencia variacional para un problema previamente restringido a la búsqueda combinatoria discreta.
2. Verosimilitud con Restricciones de Frontera Suave: El desarrollo de una verosimilitud suave que preserva la semántica de frontera del modelo duro (distinguiendo acciones factibles de no factibles) mientras reemplaza las restricciones discretas con sustitutos continuos.
3. Convergencia Teórica: Pruebas que demuestran que el modelo relajado converge al modelo duro en el límite de nitidez y exhibe transitividad suave.
4. Validación Empírica: Experimentos exhaustivos que muestran que los métodos relajados alcanzan una alta fidelidad posterior al MCMC duro en instancias pequeñas y ofrecen compensaciones superiores entre tiempo de ejecución y precisión en problemas más grandes.

Resultados Experimentales

Los autores evaluaron el método en tres conjuntos de datos: datos sintéticos, el corpus de listas de testigos de obispos (dominancia social histórica) y trazas de agentes en la nube (flujos de trabajo generados por LLM).

• Datos Sintéticos: En instancias con hasta 100 elementos, los métodos relajados (MCMC Relajado, FullRank-VI, Flow-VI) coincidieron estrechamente con la fidelidad posterior del MCMC Duro (medida por el Error Absoluto Medio de las probabilidades de precedencia por pares) mientras eran órdenes de magnitud más rápidos. El MCMC Duro se volvió inviable para $n > 30$ debido a la explosión combinatoria, mientras que Flow-VI escaló eficientemente hasta $n=100$.
• Corpus de Obispos: En 68 listas de testigos con 45 actores, el MCMC Relajado logró el mejor ajuste predictivo (WAIC más bajo), superando significativamente a las líneas base de mezclas Plackett-Luce. FullRank-VI ofreció la mejor compensación práctica, ejecutándose en 5.5 minutos en comparación con 70 minutos para el MCMC Duro, con WAIC comparable.
• Trazas de Agentes en la Nube: En 54 trazas de flujos de trabajo, el MCMC Relajado casi igualó al MCMC Duro en la recuperación estructural (F1 de cierre) y logró el mejor rendimiento predictivo (NLL de paso más bajo). FullRank-VI proporcionó la inferencia más rápida con una fuerte recuperación estructural, mientras que Flow-VI mostró una calibración predictiva mejorada sobre el MCMC Duro a pesar de una recuperación estructural ligeramente más débil.

Significado y Afirmaciones

El artículo afirma que este trabajo cierra la brecha entre la corrección semántica de la inferencia de orden parcial dura y la escalabilidad de los métodos basados en gradientes. Al relajar las restricciones discretas, los autores habilitan la inferencia bayesiana sobre órdenes parciales latentes para conjuntos de datos que anteriormente eran computacionalmente intratables.

Los autores enfatizan que la posterior relajada no es meramente una aproximación para la velocidad, sino un "buen modelo por derecho propio" que preserva la semántica con restricciones de frontera esencial para interpretar los prerequisitos. Señalan que, aunque el método escala hasta $M=100$, enfrenta limitaciones de memoria en $M=200$ debido al almacenamiento $O(M^2)$ de la matriz de precedencia suave. El trabajo se posiciona como una solución práctica para inferir estructuras interpretables en trazas de agentes y flujos de trabajo, distinguiendo prerequisitos estables de acciones reordenables sin incurrir en los costos computacionales de la búsqueda combinatoria discreta.