Performance-Driven QUBO for Recommender Systems on Quantum Annealers

1. Enunciado del Problema

Los sistemas de recomendación a menudo sufren la "maldición de la dimensionalidad" debido a la gran cantidad de características de los elementos, lo que conduce a redundancia, aumento de los costos de almacenamiento y reducción de la eficiencia de recuperación. Aunque la selección de características es crítica, los métodos tradicionales a menudo no logran optimizar explícitamente el rendimiento final de la recomendación (por ejemplo, métricas de clasificación como nDCG).

Los enfoques existentes de Recocido Cuántico (QA) para la selección de características, que formulan el problema como Optimización Binaria Cuadrática Sin Restricciones (QUBO), enfrentan dos limitaciones principales:

1. Objetivos Desalineados: Los métodos actuales basados en QUBO (por ejemplo, MIQUBO, CoQUBO) construyen la matriz de coeficientes $Q$ basándose en dependencias estadísticas (información mutua, correlación) o salidas del modelo, en lugar del impacto directo en la métrica de rendimiento de la recomendación.
2. Inestabilidad: El rendimiento de los recocedores cuánticos en hardware real (era NISQ) es sensible al tamaño del problema, al número de muestras y a la dificultad del problema, lo que genera resultados inconsistentes.

Los autores plantean tres preguntas de investigación clave:

• ¿Cómo afecta la inestabilidad de los recocedores cuánticos al rendimiento de los sistemas de recomendación?
• ¿Qué tan efectivos son los recocedores cuánticos para la selección de características en este dominio?
• ¿Pueden los métodos basados en QUBO en hardware cuántico igualar o superar las líneas base de selección de características clásicas?

2. Metodología: PDQUBO

Los autores proponen PDQUBO (Optimización Binaria Cuadrática Sin Restricciones Impulsada por Rendimiento), un marco novedoso que alinea el objetivo de optimización de QUBO directamente con el rendimiento de recomendación aguas abajo utilizando análisis contrafactual.

Flujo de Trabajo Principal

1. Entrenamiento del Modelo Base: Se entrena un modelo de recomendación ($G_\Theta$) sobre el conjunto completo de características $F$.
2. Análisis Contrafactual: El método evalúa el impacto de las características creando "instancias contrafactuales". Enmascara sistemáticamente (elimina) características individuales ($f_i$) y pares de características ($f_i, f_j$) de la entrada y mide el cambio en la métrica de evaluación (por ejemplo, nDCG).
   • $E_i$: Caída de rendimiento cuando se elimina $f_i$.
   • $E_{ij}$: Caída de rendimiento cuando se eliminan tanto $f_i$ como $f_j$.
   • Nota: Un $E$ positivo indica que la característica es importante (el rendimiento cae al eliminarla); un $E$ negativo sugiere que la característica es redundante o perjudicial.
3. Formulación QUBO: Los valores contrafactuales se utilizan para construir la matriz de coeficientes QUBO $Q$:
   • Elementos diagonales ($Q_{ii}$): Se establecen en $-E_i$ (representando la importancia individual de la característica).
   • Elementos fuera de la diagonal ($Q_{ij}$): Se establecen en $-E_{ij}$ (representando las interacciones entre pares de características).
   • La función objetivo minimiza la energía $Y = x^T Q x$, donde $x$ es un vector binario que indica la selección de características. Minimizar $Y$ corresponde a seleccionar características que maximicen el rendimiento de la recomendación.
4. Optimización: El problema QUBO construido se resuelve utilizando solucionadores clásicos (Recocido Simulado, Búsqueda Tabú) o Recocedores Cuánticos (D-Wave).
5. Reentrenamiento: El subconjunto de características seleccionado se utiliza para reentrenar el modelo base para la evaluación final.

Distinciones Clave

• Agnóstico al Modelo: PDQUBO funciona con cualquier modelo base (KNN, MLP, NCF) y cualquier métrica.
• Consciente de Interacciones: A diferencia de los métodos de "filtro" que tratan las características de forma independiente, PDQUBO modela explícitamente las interacciones entre pares mediante los términos cuadráticos en $Q$.

3. Contribuciones Clave

1. Marco PDQUBO: Una nueva formulación QUBO que vincula explícitamente la selección de características con el rendimiento de la recomendación mediante análisis contrafactual, asegurando que la dirección de optimización esté impulsada por el rendimiento y no por la estadística.
2. Análisis Integral de Estabilidad: Una investigación detallada sobre la inestabilidad de los recocedores cuánticos del mundo real, analizando cómo varía la calidad de la solución con:
   • Tamaño del problema (número de características).
   • Tamaño de la muestra (número de ejecuciones de recocido).
   • Dificultad del problema (dispersión de datos).
3. Validación Empírica: Experimentos extensos en conjuntos de datos del mundo real (conjuntos de datos CLEF 2024 QuantumCLEF, KuaiRec, KuaiRand, Avazu, Criteo) que demuestran que PDQUBO supera a las líneas base QUBO existentes y compite con los métodos de selección de características clásicos más avanzados.
4. Perspectivas de Escalabilidad: Análisis del costo computacional y una estrategia de poda propuesta en dos etapas para mitigar la complejidad $O(|F|^2)$ de construir la matriz QUBO completa, aunque el artículo concluye que la formulación cuadrática completa es necesaria para un rendimiento óptimo.

4. Resultados Experimentales

Los autores evaluaron PDQUBO frente a líneas base (CQFS, MIQUBO, CoQUBO, QUBO-Boosting) y métodos clásicos (Lasso, GBDT, Importancia por Permutación) en diversos conjuntos de datos y modelos.

• Rendimiento vs. Líneas Base:

  • PDQUBO logró consistentemente las puntuaciones mejores o segundas mejores nDCG@10 en la mayoría de las configuraciones en los conjuntos de datos 150_ICM y 500_ICM.
  • En tareas de predicción CTR (Avazu, Criteo), PDQUBO-Híbrido (utilizando un solucionador híbrido cuántico-clásico) logró las puntuaciones AUC más altas, superando tanto a las líneas base clásicas como a otras variantes QUBO.
  • PDQUBO superó significativamente a otros métodos QUBO (como MIQUBO), demostrando que la construcción impulsada por el rendimiento es superior a la construcción de dependencias estadísticas.

• Hallazgos sobre Estabilidad:

  • Tamaño del Problema: Los resultados del Recocido Cuántico (QA) se vuelven inestables a medida que el número de características aumenta más allá de la capacidad de qubits lógicos del hardware, mientras que los solucionadores clásicos (SA, TS) permanecen estables.
  • Tamaño de la Muestra: Aumentar el número de muestras de QA reduce significativamente la varianza de energía y mejora el rendimiento aguas abajo, destacando la necesidad de un muestreo suficiente en dispositivos NISQ.
  • Dificultad: QA tiende a mostrar ganancias de rendimiento más grandes pero más volátiles en conjuntos de datos dispersos (difíciles).

• Necesidad de Términos Cuadráticos:

  • Los experimentos que comparan "Indiv" (solo diagonal) vs. "All" (matriz completa) mostraron que incluir interacciones entre pares ($Q_{ij}$) es crucial. El enfoque "All" produjo resultados significativamente mejores, confirmando que las interacciones entre características son vitales para una selección efectiva en este contexto.

• Eficiencia:

  • Mientras que la complejidad temporal de los solucionadores clásicos crece exponencialmente con el tamaño del problema, el tiempo de recocido cuántico permanece relativamente constante (limitado por el acceso al hardware y el tiempo de muestreo), ofreciendo una ventaja potencial de velocidad para problemas a gran escala una vez que se superen las limitaciones del hardware.

5. Significado y Direcciones Futuras

• Cerrando la Brecha: Este trabajo cierra con éxito la brecha entre la optimización cuántica teórica y el despliegue práctico de sistemas de recomendación al asegurar que el objetivo de optimización apunte directamente a la métrica empresarial (calidad de la recomendación).
• Viabilidad Práctica: Los resultados sugieren que, incluso con las limitaciones actuales del hardware NISQ, los enfoques híbridos cuántico-clásicos pueden proporcionar una selección de características competitiva o superior en comparación con los métodos clásicos maduros.
• Trabajo Futuro: Los autores sugieren extender PDQUBO para modelar interacciones de características de orden superior (más allá de pares) y explorar algoritmos cuánticos variacionales en computadoras cuánticas basadas en puertas para manejar estructuras de características más complejas y a mayor escala.

En conclusión, PDQUBO representa un paso significativo hacia adelante en la aplicación de la computación cuántica a los desafíos de recomendación del mundo real, demostrando que las formulaciones QUBO basadas en contrafactuales e impulsadas por el rendimiento pueden aprovechar eficazmente los recocedores cuánticos para una selección de características de alta calidad.