An Iterative Geometric Approach to Optimizing Separating Hyperplanes

Resumen Técnico: Un Enfoque Geométrico Iterativo para la Optimización de Hiperplanos Separadores

Planteamiento del Problema
El artículo aborda el problema de calcular el hiperplano separador de máximo margen para un conjunto de datos con etiquetas binarias y linealmente separables. Esto es equivalente a resolver el problema de optimización del SVM de margen duro (hard-margin), el cual es un programa cuadrático convexo. Mientras que los solvers estándar (por ejemplo, SMO, métodos de punto interior) resuelven este problema directamente sobre todo el conjunto de datos, el artículo investiga un escenario específico: dado un hiperplano separador inicial, factible (pero no óptimo), ¿puede alcanzarse la solución óptima de manera más eficiente mediante una secuencia de refinamientos geométricos iterativos? El objetivo es mejorar el margen de forma continua manteniendo estrictamente la separabilidad lineal en cada paso.

Metodología
El método propuesto es un algoritmo iterativo que transforma un hiperplano separador actual $H_i$ en un nuevo hiperplano $H_{i+1}$ con un margen mayor. El proceso se basa en información local (el "conjunto activo") en lugar de en el conjunto de datos global. El algoritmo procede de la siguiente manera:

1. Identificación del Conjunto Activo: Para el hiperplano actual $H_i$, el algoritmo identifica el conjunto activo $A_i$, que consiste en las muestras de ambas clases más cercanas al hiperplano.
2. Optimización Local: Se aplica un solver de SVM existente exclusivamente al conjunto activo $A_i$ para calcular su hiperplano separador de máximo margen local, denotado como $H^*_i$, con un vector normal $w^*_i$.
3. Verificación de Convergencia: Si el hiperplano actual $H_i$ coincide con $H^*_i$, el algoritmo termina, ya que se demuestra que un hiperplano óptimo para su conjunto activo es globalmente óptimo (Lema 1).
4. Realineación Geométrica: Si $H_i \neq H^*_i$, el algoritmo realinea $H_i$ hacia $H^*_i$. Esto se logra interpolando el vector normal: $w_i(\alpha) = (1-\alpha)w_i + \alpha w^*_i$. La rotación ocurre alrededor de un punto pivote $m$, definido como el punto medio de un par seleccionado de vectores de soporte de etiquetas opuestas de $A_i$.
5. Expansión del Margen y Bloqueo: El parámetro $\alpha$ se incrementa de 0 a 1. Durante esta rotación, el margen con respecto al conjunto activo aumenta de forma estrictamente monotónica. Sin embargo, la rotación está limitada por "muestras de bloqueo" fuera del conjunto activo que podrían cruzar los hiperplanos de margen. El algoritmo calcula el $\alpha$ máximo admisible ($\alpha_{actual}$) tal que ninguna nueva muestra viole la restricción de separación.
6. Iteración: El hiperplano se actualiza utilizando $\alpha_{actual}$. Si $\alpha_{actual} < 1$, una nueva muestra (o conjunto de muestras) se ha vuelto activa (una "muestra de bloqueo"), y el proceso se repite con el conjunto activo actualizado. Si $\alpha_{actual} = 1$, se ha alcanzado el óptimo global.

Contribuciones Clave

• Técnica Geométrica Iterativa: El artículo introduce un nuevo algoritmo que descompone el problema de optimización global en una secuencia de subproblemas más pequeños definidos por conjuntos activos. A diferencia de los métodos tradicionales que minimizan una función objetivo global, este enfoque realiza transformaciones geométricas (rotaciones) del hiperplano para maximizar el margen.
• Hallazgos Teóricos:
  • Optimalidad Local-Global: El artículo formaliza la condición de que si un hiperplano separador es óptimo con respecto a su conjunto activo, es globalmente óptimo.
  • Relación de Margen Geométrico: Deriva una relación que muestra que el margen del hiperplano interpolado es proporcional al coseno del ángulo entre el vector normal actual y el vector normal óptimo del conjunto activo ($\gamma(\alpha) = \gamma^* \cos \theta(\alpha)$).
  • Interpretación KKT: El trabajo proporciona una interpretación geométrica de las condiciones de Karush–Kuhn–Tucker (KKT) en el contexto de los SVM, vinculando la separación de los envolventes convexos proyectados con la optimalidad.
• Evaluación Experimental: El método se implementó en Python utilizando NumPy y CVXPY y se probó en pares de dígitos MNIST linealmente separables.

Resultados Experimentales
Los experimentos compararon el método de refinamiento iterativo propuesto contra un solver global de referencia (CVXPY con OSQP) en pares de dígitos MNIST (con un rango de ~2,000 a ~12,000 muestras).

• Conjuntos de Datos Pequeños (~2,000 muestras): El método propuesto fue más lento que el solver global directo, requiriendo aproximadamente 10 veces más tiempo de computación en algunos casos. La sobrecarga de resolver múltiples subproblemas superó los beneficios.
• Conjuntos de Datos Grandes (~12,000 muestras): El método se volvió competitivo. Cuando se incluyó el tiempo para computar el hiperplano factible inicial, el método fue más rápido en 6 de 10 experimentos de conjuntos de entrenamiento. Cuando se asumió que el hiperplano inicial ya existía, la fase de refinamiento por sí sola superó a la de referencia en 8 de 10 experimentos.
• Tamaño del Conjunto Activo: Los conjuntos activos permanecieron significativamente más pequeños que el tamaño total del conjunto de datos (el tamaño promedio del conjunto activo fue aproximadamente la mitad del número de vectores de soporte), validando la estrategia de resolver subproblemas reducidos.
• Convergencia: El algoritmo alcanzó consistentemente la solución óptima en todos los experimentos, con recuentos de iteración que variaron de 84 a 778.

Significancia y Reivindicaciones
El artículo afirma que el enfoque propuesto es particularmente beneficioso en escenarios donde encontrar un hiperplano separador factible es computacionalmente más sencillo que computar el óptimo directamente, o cuando un hiperplano factible ya está disponible. El método no reemplaza a los solvers de SVM existentes, sino que ofrece un marco alternativo que explota la factibilidad y la geometría del conjunto activo.

Los autores son modestos respecto a la universalidad del método. Reconocen que el método no supera la optimización directa en conjuntos de datos más pequeños y que la complejidad computacional depende fuertemente del solver elegido para los subproblemas del conjunto activo. Además, el artículo señala que quedan preguntas teóricas abiertas, específicamente sobre si la dirección de realineación elegida garantiza el aumento de margen más rápido posible y si el método garantiza la terminación en un número finito de iteraciones para todos los casos. El trabajo se presenta como una perspectiva geométrica sobre la optimización de máximo margen que proporciona nuevas ideas sobre la relación entre los óptimos locales y globales.