Predicción Conforme En Línea Multimodelo con Retroalimentación Estructurada en Grafos

Información Básica

• ID del Artículo: 2506.20898
• Título: Predicción Conforme En Línea Multimodelo con Retroalimentación Estructurada en Grafos
• Autores: Erfan Hajihashemi, Yanning Shen (Universidad de California, Irvine)
• Clasificación: cs.LG
• Fecha de Publicación/Conferencia: Transactions on Machine Learning Research (10/2025)
• Enlace del Artículo: https://arxiv.org/abs/2506.20898

Resumen

La predicción conforme en línea ha demostrado su capacidad para construir un conjunto de predicción para cada punto de datos entrante que cubra la etiqueta verdadera con una probabilidad predeterminada. Para hacer frente a posibles cambios de distribución, se ha introducido la predicción conforme en línea multimodelo para seleccionar y aprovechar diferentes modelos de un conjunto de candidatos preseleccionado. Junto con la flexibilidad mejorada, la elección del conjunto preseleccionado también presenta desafíos. Un conjunto de candidatos que incluye un gran número de modelos puede aumentar la complejidad computacional. Además, la inclusión de modelos irrelevantes con bajo rendimiento puede impactar negativamente el desempeño y conducir a conjuntos de predicción innecesariamente grandes. Para abordar estos desafíos, proponemos un nuevo algoritmo de predicción conforme en línea multimodelo que identifica un subconjunto de modelos efectivos en cada paso de tiempo recopilando retroalimentación de un grafo bipartito, que se refina al recibir nuevos datos. Luego se selecciona un modelo de este subconjunto para construir el conjunto de predicción, lo que resulta en complejidad computacional reducida y conjuntos de predicción más pequeños. Además, demostramos que utilizar el tamaño del conjunto de predicción como retroalimentación, junto con la pérdida del modelo, puede mejorar significativamente la eficiencia al construir conjuntos de predicción más pequeños mientras se mantiene la garantía de cobertura requerida. Se demuestra que los algoritmos propuestos garantizan cobertura válida y logran arrepentimiento sublineal. Los experimentos en conjuntos de datos reales y sintéticos validan que los métodos propuestos construyen conjuntos de predicción más pequeños y superan los enfoques existentes de predicción conforme en línea multimodelo.

Antecedentes de Investigación y Motivación

1. Problema a Resolver: Los métodos existentes de predicción conforme en línea multimodelo enfrentan alta complejidad computacional y conjuntos de predicción excesivamente grandes al tratar cambios de distribución. Los métodos tradicionales requieren actualizar y evaluar todos los modelos candidatos, lo que resulta en ineficiencia cuando el conjunto de candidatos contiene muchos modelos o modelos con bajo rendimiento.
2. Importancia del Problema: En aplicaciones críticas para la seguridad (como conducción autónoma, diagnóstico médico), se requiere cuantificación confiable de incertidumbre para garantizar la confiabilidad de las decisiones. La predicción conforme puede proporcionar conjuntos de predicción válidos sin depender de suposiciones de distribución, pero en entornos en línea debe hacer frente a cambios dinámicos en la distribución de datos.
3. Limitaciones de Métodos Existentes:
   • La complejidad computacional crece linealmente con el número de modelos candidatos
   • La inclusión de modelos de bajo rendimiento impacta negativamente el desempeño general
   • Falta de mecanismos efectivos de selección de modelos para adaptarse dinámicamente a cambios de distribución
4. Motivación de Investigación: Desarrollar un algoritmo de predicción conforme en línea multimodelo que pueda seleccionar adaptativamente subconjuntos de modelos efectivos, reduciendo la complejidad computacional y el tamaño del conjunto de predicción mientras se garantiza la cobertura.

Contribuciones Principales

1. Propuesta del Algoritmo GMOCP: Diseño de un algoritmo de predicción conforme en línea multimodelo basado en retroalimentación estructurada en grafos que identifica dinámicamente subconjuntos de modelos efectivos mediante un grafo bipartito
2. Construcción de Marco de Generación de Grafos Adaptativo: Construcción y actualización dinámica del grafo bipartito basada en desempeño histórico de modelos, realizando selección de modelos en línea
3. Desarrollo del Algoritmo Extendido EGMOCP: Utilización del tamaño del conjunto de predicción como señal de retroalimentación adicional para mejorar aún más la eficiencia de predicción
4. Provisión de Garantías Teóricas: Demostración de cobertura válida del algoritmo y límites de arrepentimiento sublineal
5. Validación en Múltiples Conjuntos de Datos: Logro de conjuntos de predicción más pequeños y menor complejidad computacional en conjuntos de datos como CIFAR-10C y CIFAR-100C

Explicación Detallada del Método

Definición de Tarea

Dado el historial de datos $\{(X_τ, Y^{true}_τ)\}^{t-1}_{τ=1}$ y entrada nueva $X_t$, construir conjunto de predicción $C^m_α(X_t) ⊆ Y$ tal que la etiqueta verdadera $Y^{true}_t$ esté contenida en el conjunto de predicción con probabilidad $1-α$, donde $α$ es la probabilidad de no cobertura.

Arquitectura del Modelo

1. Diseño de Estructura de Grafo Bipartito

• Nodos de Modelo: $\{v^{(l)}_1, ..., v^{(l)}_M\}$ representan M modelos candidatos
• Nodos de Selección: $\{v^{(s)}_1, ..., v^{(s)}_J\}$ representan J nodos de selección
• Restricciones de Conexión: Cada nodo de selección se conecta como máximo a N nodos de modelo

2. Algoritmo de Generación de Grafos

Probabilidad de conexión de nodo de modelo: $p^m_t = (1 - η_e) \frac{w^m_t}{\sum^M_{\bar{m}=1} w^{\bar{m}}_t} + \frac{η_e}{M}$

donde $η_e$ es el coeficiente de exploración y $w^m_t$ es el peso del modelo.

3. Actualización de Peso del Modelo

Estimación de pérdida con muestreo de importancia: $w^m_{t+1} = w^m_t \exp(-ε l^m_t / 2^b)$

donde la función de pérdida es: $l^m_t = \frac{L(\bar{α}^m_t, α^m_t)}{q^m_t} I\{m ∈ S_t\}$

4. Actualización Adaptativa de Probabilidad de No Cobertura

Utilizando descenso de gradiente en línea sin escala: $α^m_{t+1} = α^m_t - η \frac{∇_{α^m_t} L(\bar{α}^m_t, α^m_t)}{\sqrt{\sum^t_{τ=1} \|∇_{α^m_τ} L(\bar{α}^m_τ, α^m_τ)\|^2_2}}$

Puntos de Innovación Técnica

1. Mecanismo de Retroalimentación Estructurada en Grafos: Selección dinámica de subconjuntos de modelos mediante grafo bipartito, evitando actualización de todos los modelos
2. Diseño de Retroalimentación Dual: EGMOCP considera simultáneamente pérdida de predicción y tamaño del conjunto de predicción como señales de retroalimentación
3. Balance Adaptativo de Exploración-Explotación: Implementación de estrategia de exploración multinivel mediante diferentes coeficientes de exploración

Configuración Experimental

Conjuntos de Datos

1. CIFAR-10C/CIFAR-100C: Contienen 15 tipos de corrupción, 5 niveles de severidad
2. TinyImageNet-C: Versión corrupta de conjunto de datos de 200 clases
3. Conjunto de Datos Sintético: 3000 muestras, 20 clases, simulando cambio de distribución

Métricas de Evaluación

• Cobertura: Porcentaje de conjuntos de predicción que contienen la etiqueta verdadera
• Ancho Promedio: Tamaño promedio del conjunto de predicción
• Tiempo de Ejecución: Tiempo de ejecución del algoritmo
• Ancho Único: Porcentaje de conjuntos de predicción de tamaño 1 que cubren correctamente

Métodos de Comparación

• MOCP: Método de línea base de predicción conforme en línea multimodelo
• COMA: Método de agregación de modelos en línea conforme
• Métodos Unimodelo: ACI, FACI, DECAY, SAOCP

Detalles de Implementación

• Tasa de cobertura objetivo: 90% (α = 0.1)
• Hiperparámetros: ε = 0.5, η = 0.05, β = 0.05
• Número de pasos de tiempo: T = 6000
• Tamaño de lote: 500 muestras

Resultados Experimentales

Resultados Principales

En experimentos de cambio de distribución repentino en el conjunto de datos CIFAR-100C:

• GMOCP logra tiempo de ejecución más rápido (aproximadamente 50% de mejora) y tamaño de conjunto de predicción similar en comparación con MOCP
• EGMOCP reduce significativamente el tamaño del conjunto de predicción, de 12.63 en MOCP a 6.18, manteniendo la tasa de cobertura objetivo del 90%
• La proporción de ancho único aumenta de 22.43% a 29.91%

Experimentos de Ablación

1. Impacto de Parámetros de Grafo: Prueba de diferentes combinaciones de N (número de nodos de modelo) y J (número de nodos de selección)
2. Estrategia de Exploración: Comparación del efecto de diferentes configuraciones de coeficientes de exploración
3. Mecanismo de Retroalimentación: Validación de la efectividad de la retroalimentación del tamaño del conjunto de predicción

Análisis de Casos

Demostración mediante tres configuraciones de entrenamiento de DenseNet121 (120D, 10R, 1R):

• Modelos de alto rendimiento (120D) obtienen el peso más alto y probabilidad de selección
• EGMOCP puede identificar efectivamente y favorecer la selección de modelos con mejor rendimiento
• El tamaño del conjunto de predicción muestra correlación negativa con el rendimiento del modelo

Hallazgos Experimentales

1. Mejora de Eficiencia Computacional: La complejidad por paso de GMOCP es O(Nt + JMN), significativamente reducida en comparación con O(Mt) de MOCP cuando N << M
2. Mejora de Calidad de Predicción: EGMOCP logra conjuntos de predicción más pequeños mediante mecanismo de retroalimentación dual
3. Validación de Robustez: Mantiene desempeño estable bajo múltiples escenarios de cambio de distribución

Trabajo Relacionado

1. Fundamentos de Predicción Conforme: Basado en marco clásico de Vovk et al., extendido a entorno en línea
2. Predicción Conforme Adaptativa: Método de probabilidad de no cobertura variable en tiempo de Gibbs & Candès
3. Métodos Multimodelo: Comparación con trabajos de Hajihashemi & Shen y Gasparin & Ramdas
4. Teoría de Aprendizaje En Línea: Incorpora ideas de aprendizaje de expertos y máquinas tragaperras multibrazo

Conclusiones y Discusión

Conclusiones Principales

1. El mecanismo de retroalimentación estructurada en grafos puede reducir efectivamente la complejidad computacional y mejorar la eficiencia de predicción
2. El tamaño del conjunto de predicción como señal de retroalimentación mejora significativamente el desempeño del algoritmo
3. Las garantías teóricas son consistentes con los resultados experimentales, validando la efectividad del método

Limitaciones

1. La construcción del grafo requiere ajuste adicional de hiperparámetros
2. La mejora es limitada cuando la calidad de los modelos candidatos es similar
3. El análisis teórico se basa en suposiciones específicas de función de pérdida

Direcciones Futuras

1. Exploración de estructuras de grafo más complejas y estrategias de actualización
2. Extensión a tareas de regresión y otros métodos de cuantificación de incertidumbre
3. Investigación de adaptabilidad bajo cambio de distribución fuerte

Evaluación Profunda

Fortalezas

1. Innovación Metodológica Fuerte: El mecanismo de retroalimentación estructurada en grafos proporciona nuevas perspectivas para selección multimodelo
2. Fundamentos Teóricos Sólidos: Proporciona demostraciones rigurosas de cobertura y límites de arrepentimiento
3. Diseño Experimental Integral: Cubre múltiples conjuntos de datos y escenarios de cambio de distribución
4. Alto Valor Práctico: Reduce significativamente la complejidad computacional mientras mejora la calidad de predicción

Deficiencias

1. Sensibilidad a Hiperparámetros: Requiere ajuste de múltiples parámetros relacionados con grafos
2. Limitaciones de Escenarios Aplicables: Las ventajas no son evidentes cuando la diferencia de calidad entre modelos es pequeña
3. Análisis Teórico Complejo: El proceso de demostración es intrincado, con aplicabilidad práctica por verificar

Impacto

1. Contribución Académica: Proporciona nueva ruta técnica para el campo de cuantificación de incertidumbre en línea
2. Perspectivas de Aplicación: Tiene valor importante en sistemas críticos para la seguridad que requieren toma de decisiones en tiempo real
3. Reproducibilidad: Descripción de algoritmo detallada y configuración experimental clara

Escenarios Aplicables

1. Sistemas de aprendizaje en línea que requieren cuantificación de incertidumbre en tiempo real
2. Entornos dinámicos que enfrentan cambio de distribución
3. Escenarios con recursos computacionales limitados pero que requieren fusión multimodelo
4. Necesidades de predicción confiable en aplicaciones críticas para la seguridad

Referencias

1. Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic learning in a random world
2. Gibbs, I., & Candès, E. J. (2021). Adaptive conformal inference under distribution shift
3. Hajihashemi, E., & Shen, Y. (2024). Multi-model ensemble conformal prediction in dynamic environments
4. Gasparin, M., & Ramdas, A. (2024). Conformal online model aggregation