PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering

Each language version is independently generated for its own context, not a direct translation.

Imagina que tienes una caja gigante llena de miles de objetos: manzanas, naranjas, piedras, juguetes y zapatos. Tu trabajo es organizarlos en grupos (cestas) para que todo esté ordenado. Esto es lo que hace la agrupación de datos (clustering) en la informática: buscar patrones y poner cosas similares juntas.

Pero, ¿qué pasa si tienes reglas estrictas?

Regla 1 (Must-Link): "¡Estas dos manzanas rojas siempre deben ir en la misma cesta!"
Regla 2 (Cannot-Link): "¡Esta piedra y este zapato nunca pueden estar en la misma cesta!"

El problema es que cuando tienes millones de objetos y miles de reglas contradictorias, ordenarlos se vuelve una pesadilla. Las computadoras tradicionales se quedan atascadas pensando en todas las posibilidades a la vez, y las computadoras cuánticas (que son muy potentes pero aún inmaduras) no tienen suficiente "espacio" en su cerebro para procesar tantos objetos y reglas al mismo tiempo.

Aquí es donde entra PASS, el nuevo método presentado en este artículo.

La Metáfora: El "Equipo de Rescate" (PASS)

Imagina que PASS es un equipo de rescate de alta eficiencia que entra a la caja gigante de objetos. En lugar de intentar reorganizar todo el contenido de la caja de golpe (lo cual es imposible y lento), PASS hace algo muy inteligente:

1. El "Agrupamiento" (Contraer lo obvio)

Primero, PASS mira las reglas de "Must-Link". Si dice que 10 manzanas siempre deben ir juntas, PASS las pega con superglue y las trata como una sola "super-manzana".

Analogía: En lugar de mover 1000 ladrillos sueltos, los pegas en bloques de 10. Ahora tienes que mover solo 100 bloques. ¡Mucho más fácil!

2. La "Selección del Equipo" (Encontrar el problema real)

Aquí está la magia. PASS no intenta arreglar todo. Solo busca los puntos donde hay confusión o problemas.

Si una manzana está muy lejos de su cesta y nadie la quiere, PASS la marca.
Si hay una regla que dice "No pongas el zapato con la piedra" y el zapato y la piedra están en la misma cesta, PASS marca ese error.
PASS crea un "Equipo de Trabajo" (Working Set) pequeño. Solo incluye a los objetos que están en el lío o que están cerca de la línea de confusión. El resto de los objetos (los que ya están bien ordenados) se quedan quietos y no se tocan.

3. La "Reparación Certificada" (El detective infalible)

Una vez que PASS tiene su pequeño equipo de trabajo, intenta reorganizar solo a esos pocos objetos para cumplir las reglas.

El truco: PASS no solo intenta arreglarlo; usa una certificación matemática. Es como si el equipo de rescate dijera: "Hemos verificado con un algoritmo infalible que, si movemos solo a estos 5 objetos, el resto de la caja seguirá cumpliendo todas las reglas".
Si el algoritmo dice "Sí, se puede arreglar", PASS lo hace y te da un "certificado de garantía" de que todo está bien.
Si dice "No, es imposible arreglarlo sin romper otras reglas", PASS te avisa exactamente dónde está el problema y cuántas reglas se rompieron, en lugar de quedarse pensando eternamente.

¿Por qué es esto revolucionario?

Velocidad: Al ignorar el 99% de los objetos que ya están bien, PASS es increíblemente rápido. Puede manejar millones de datos en segundos, mientras que otros métodos se quedan colgados.
El Puente Cuántico: Las computadoras cuánticas actuales son como niños pequeños con una memoria muy corta. No pueden recordar millones de reglas. Pero como PASS reduce el problema a un "Equipo de Trabajo" pequeño, ¡ahora sí cabe en la memoria de una computadora cuántica!
- PASS toma el problema gigante, lo reduce a un pequeño rompecabezas y se lo pasa a la computadora cuántica para que lo resuelva. Luego, PASS vuelve a poner la solución en la caja gigante.
Honestidad: Si el problema es imposible de resolver (por ejemplo, si te piden que una piedra y un zapato estén juntos y separados al mismo tiempo), PASS no miente ni se bloquea. Te dice claramente: "Aquí hay un conflicto que no se puede arreglar" y te muestra la evidencia.

En resumen

PASS es como un arquitecto muy inteligente que, ante un edificio desordenado, no intenta mover todos los muebles a la vez.

Pega juntos los muebles que siempre van juntos.
Identifica solo las habitaciones donde hay muebles mal colocados o reglas rotas.
Reorganiza solo esos muebles problemáticos.
Te entrega un plano con una "garantía de seguridad" de que el resto de la casa sigue perfecta.

Gracias a esto, podemos organizar datos masivos mucho más rápido y, por primera vez, usar la tecnología cuántica para ayudar a resolver problemas de organización que antes eran demasiado grandes para cualquier computadora.

Each language version is independently generated for its own context, not a direct translation.

1. Planteamiento del Problema

El agrupamiento (clustering) es una tarea fundamental en el aprendizaje no supervisado, cuyo objetivo es encontrar grupos cohesivos y bien separados en los datos. El criterio estándar es el Criterio de Mínima Suma de Cuadrados (MSSC), que minimiza la suma de errores al cuadrado (SSE).

Sin embargo, en muchas aplicaciones prácticas, las soluciones puramente no supervisadas pueden contradecir el conocimiento del dominio. Para abordar esto, se utiliza el agrupamiento con restricciones de pares, que incorpora información semisupervisada mediante:

Must-Link (ML): Pares de puntos que deben pertenecer al mismo grupo.
Cannot-Link (CL): Pares de puntos que no deben pertenecer al mismo grupo.

Desafíos principales:

Complejidad Computacional: El MSSC con restricciones es NP-duro. Las restricciones rompen la estructura que aprovechan las actualizaciones estándar de k-means.
Inviabilidad: Conjuntos de restricciones densas o inconsistentes pueden hacer que el problema sea intratable o que no exista solución factible.
Escalabilidad Cuántica: En enfoques cuánticos y híbridos (NISQ), la codificación de restricciones densas requiere un número de variables y acoplamientos que excede la capacidad de los dispositivos actuales (limitaciones de qubits y tiempos de coherencia).

2. Metodología: El Marco PASS

El artículo propone PASS (Pairwise constrained Assignment via Subset Selection), un marco escalable que aborda el problema mediante la optimización restringida a un subconjunto de trabajo y una reparación certificada.

A. Reducción del Problema (Fase 1 y 2)

Colapso de Must-Link (ML): Los componentes conectados por restricciones ML se colapsan en "puntos pseudo" ponderados. Esto elimina las restricciones ML explícitas y preserva la función objetivo MSSC (hasta una constante aditiva), reduciendo el tamaño del problema.
Selección del Subconjunto de Trabajo ( $S$ ): En lugar de reasignar todos los puntos en cada iteración, PASS selecciona un subconjunto pequeño $S \subset \hat{S}$ $S \subset \hat{S}$ (donde $\hat{S}$ $\hat{S}$ son los puntos colapsados). La selección se basa en dos estrategias:
- PASS-CA (Consciente de Restricciones): Selecciona puntos involucrados en violaciones de CL y puntos ambiguos cerca de los límites de decisión (basado en márgenes).
- PASS-IG (Geométrico de Información): Utiliza puntuaciones de ambigüedad basadas en la métrica de Fisher-Rao sobre asignaciones suaves para identificar puntos inciertos.
- Garantía: Los puntos fuera de $S$ mantienen sus asignaciones actuales ("congelados").

B. Optimización Restringida (Fase 3)

Se resuelve un problema de asignación restringido (ILP 0-1 o QUBO) solo sobre el subconjunto $S$ :

Se minimiza el SSE local.
Se respetan las restricciones CL dentro de $S$ .
Se imponen restricciones de consistencia en el borde: si un punto en $S$ tiene un vecino CL congelado fuera de $S$ , no puede tomar la etiqueta de ese vecino.
Esto reduce drásticamente el número de variables binarias de $O(N \cdot K)$ a $O(|S| \cdot K)$ .

C. Reparación Certificada (Fase 4)

Para garantizar la factibilidad global de las restricciones CL bajo actualizaciones restringidas:

El problema de reparación se formula como un problema de coloreado de listas en el subgrafo inducido por las restricciones en $S$ .
Teorema de Certificado (Local Slack): Se establece una condición suficiente basada en la degeneración del grafo. Si el tamaño mínimo de las listas de colores permitidos en $S$ es mayor que la degeneración del subgrafo inducido más uno ( $\min |L_i| \ge \text{deg}(G[S]) + 1$ ), entonces existe una reparación factible que puede construirse mediante un algoritmo voraz.
Si la condición se cumple, PASS devuelve una asignación reparada con un certificado verificable (una traza de coloreado). Si falla, reporta violaciones residuales o evidencia de obstrucción.

3. Contribuciones Clave

Reparación Certificada: Formaliza la factibilidad bajo actualizaciones de subconjunto como un problema de coloreado de listas, proporcionando certificados verificables de éxito o evidencia de fallo.
Marco de Reducción Escalable: Combina colapso de ML, selección de subconjunto y reparación para manejar problemas grandes (hasta millones de puntos) donde los métodos exactos fallan.
Pipeline Híbrido Cuántico-Clásico: La reducción del subconjunto permite formular problemas cuánticos (QUBO) mucho más pequeños ( $O(|S| \cdot K)$ en lugar de $O(N \cdot K)$ ), haciéndolos viables para dispositivos NISQ actuales.
Evaluación Exhaustiva: Demuestra que PASS logra un SSE competitivo con menor tiempo de ejecución y resuelve instancias donde los métodos de referencia (baselines) no terminan dentro del límite de tiempo.

4. Resultados Experimentales

A. Rendimiento Clásico

Datasets: Se evaluó en 12 conjuntos de datos (UCI y sintéticos) de tamaños variables (desde 150 hasta más de 4 millones de puntos).
Comparación: Se comparó contra COP-k-means, BLPKM-CC y PCCC.
Hallazgos:
- PASS logra un SSE competitivo (a menudo igual o mejor que los baselines) con un tiempo de ejecución significativamente menor.
- En datasets grandes (ej. Skin, Gas_methane), PASS encuentra soluciones factibles dentro del límite de tiempo, mientras que otros métodos (como PCCC o BLPKM-CC) a menudo no encuentran solución o exceden el tiempo límite.
- PASS-IG tiende a seleccionar subconjuntos más pequeños y alcanza factibilidad sin necesidad de invocar la reparación en muchos casos.

B. Rendimiento Cuántico (q-PCKMeans)

Se evaluó un algoritmo cuántico de refinamiento (q-PCKMeans) utilizando una simulación de hardware IBM-Q (con ruido) y Qiskit.
Comparación: Se comparó contra CP-QAOA (codificación completa del problema).
Hallazgos:
- Gracias a la reducción de subconjunto, q-PCKMeans logra reducciones de SSE del 6% al 84% en comparación con CP-QAOA.
- Permite ejecutar problemas con restricciones en dispositivos simulados de tamaño manejable (hasta $N=900$ en la simulación), algo imposible con la codificación completa debido a la limitación de qubits.
- Mantiene tasas de violación de restricciones muy bajas (cercanas a 0% en muchos casos) bajo protocolos de simulación con ruido.

5. Significado e Impacto

Viabilidad Cuántica: El trabajo demuestra que la reducción de problemas (mediante selección de subconjuntos) es una estrategia crítica para hacer que el agrupamiento con restricciones sea accesible para la computación cuántica en la era NISQ, superando las barreras de escalabilidad de variables.
Garantías Teóricas: A diferencia de muchos métodos heurísticos, PASS ofrece garantías teóricas sobre la factibilidad de las soluciones a través de certificados de reparación, lo cual es crucial en aplicaciones críticas donde las restricciones no pueden violarse.
Eficiencia Práctica: Ofrece una solución práctica para el agrupamiento a gran escala con restricciones, llenando la brecha entre los métodos exactos (lentos) y los heurísticos (sin garantías de factibilidad).

En resumen, PASS introduce un paradigma donde la complejidad se gestiona localmente en un subconjunto crítico, permitiendo tanto una optimización clásica eficiente como una refinación cuántica viable, todo ello respaldado por certificados matemáticos de corrección.