On Linear Separability of the MNIST Handwritten Digits Dataset

Este artículo presenta una investigación empírica exhaustiva para determinar si el conjunto de datos MNIST es linealmente separable, resolviendo afirmaciones contradictorias mediante el análisis sistemático de la separación par a par y uno contra todos en sus conjuntos de entrenamiento, prueba y combinado.

Lo esencial

¡Claro que sí! Imagina que este artículo es como un detective resolviendo un misterio matemático sobre un archivo de fotos muy famoso. Aquí tienes la explicación en español, usando analogías sencillas:

🕵️‍♂️ El Misterio: ¿Se pueden separar las fotos con una sola línea?

El conjunto de datos MNIST es como una gran caja de 70,000 fotos de dígitos escritos a mano (del 0 al 9). Es el "examen de conducir" clásico para cualquier inteligencia artificial que quiera aprender a leer números.

El gran debate de este artículo es: ¿Es posible separar estos números usando solo una línea recta?

Imagina que tienes un montón de bolas de dos colores mezcladas en una mesa.

• Si puedes poner una regla recta (una línea) sobre la mesa y separar todas las bolas rojas de las azules sin que ninguna se quede del lado equivocado, se dice que son "linealmente separables".
• Si las bolas están tan mezcladas que la regla siempre toca una bola del color incorrecto, entonces no son separables.

🔍 ¿Qué descubrió el autor?

El autor, Ákos Hajnal, decidió ponerle fin a las discusiones informales (donde unos decían "sí, se puede" y otros "no, es imposible") y lo comprobó con matemáticas estrictas y computadoras potentes.

Dividió la investigación en dos juegos:

1. El juego "Uno contra Uno" (Pairwise)

Aquí preguntamos: ¿Puedo separar los 2s de los 3s con una línea?

• La sorpresa: ¡Sí! En el conjunto de pruebas (las fotos que la IA nunca ha visto antes), cualquier par de números (como un 2 contra un 3, o un 5 contra un 8) se puede separar con una línea recta. Es como si en una caja pequeña de canicas, siempre pudieras encontrar una forma de poner la regla para separar dos colores específicos.
• La realidad: Sin embargo, en el conjunto de entrenamiento (las fotos con las que la IA aprende), hay algunos pares que son tan confusos (como el 2 contra el 3, o el 3 contra el 8) que no se pueden separar con una sola línea. Están demasiado mezclados.

2. El juego "Uno contra Todos" (One-vs-Rest)

Aquí preguntamos: ¿Puedo separar los 0s de TODOS los demás números (1, 2, 3... 9) a la vez con una sola línea?

• La respuesta dura: No. Ni siquiera en el conjunto de pruebas.
• La analogía: Imagina que quieres separar a las personas que usan gorras rojas de todas las demás personas que usan gorras de todos los demás colores. Si hay alguien con una gorra roja que se parece mucho a alguien con una gorra naranja, o si hay alguien con una gorra azul que se parece a una roja, una sola línea recta no podrá hacer el trabajo.
• El artículo demuestra que, en el conjunto de entrenamiento, ningún número puede aislarse perfectamente de los otros nueve con una sola línea. El 0, el 1, el 6... todos tienen "vecinos" que se parecen demasiado para separarlos con una regla simple.

🛠️ ¿Cómo lo hicieron? (La herramienta mágica)

El autor no usó adivinanzas. Usó una herramienta matemática llamada CVXPY.

• Imagina que CVXPY es un robot arquitecto superinteligente.
• El robot recibe las fotos y trata de construir una "pared" (una línea o hiperplano) que divida los números.
• Si el robot puede construir la pared sin que ninguna foto quede del lado equivocado, grita: "¡Éxito! Es separable".
• Si el robot prueba millones de posiciones y descubre que es imposible sin romper la regla, grita: "¡Imposible! No es separable".

📝 El Veredicto Final

El artículo concluye que la respuesta no es un simple "sí" o "no", sino que depende de cómo mires el problema:

1. Si miras el conjunto de pruebas (las fotos nuevas): ¡Sí! Puedes separar cualquier par de números con una línea. (Pero ojo, esto es solo por suerte de tener pocas fotos en esa caja).
2. Si miras el conjunto de entrenamiento (donde se aprende): No. No puedes separar un número de todos los demás con una sola línea.
3. La lección: Decir simplemente "MNIST es linealmente separable" o "MNIST no lo es" es una simplificación excesiva. La realidad es más compleja y depende de si estás comparando dos números o uno contra todos.

En resumen: Las máquinas de aprendizaje modernas (como las redes neuronales profundas) son necesarias porque una sola línea recta (un modelo simple) no es suficiente para entender la complejidad de los números escritos a mano, especialmente cuando hay muchos ejemplos y variaciones. ¡La línea recta se queda corta! 📏❌

Resumen técnico

Resumen Técnico: Separabilidad Lineal del Dataset MNIST

1. Planteamiento del Problema

El dataset MNIST, que contiene 70.000 imágenes en escala de grises de dígitos escritos a mano (28x28 píxeles), es un estándar fundamental en la evaluación de modelos de reconocimiento de patrones. A pesar de su larga historia y relativa simplicidad, existe una ambigüedad persistente en la literatura científica y fuentes informales sobre si este dataset es linealmente separable.

• La pregunta central: ¿Existe un hiperplano de decisión lineal único que pueda separar las clases de dígitos en el espacio de características de 784 dimensiones?
• El conflicto: Algunas fuentes afirman que MNIST es separable, mientras que otras (citando erróneamente trabajos anteriores) sostienen que no lo es.
• Definiciones clave: El estudio distingue entre dos escenarios:
  1. Separabilidad Par a Par (Pairwise): ¿Se puede separar un dígito específico (ej. '0') de otro específico (ej. '1')?
  2. Separabilidad Uno-vs-Rest (One-vs-Rest): ¿Se puede separar un dígito específico de todos los demás dígitos (1-9) simultáneamente?

2. Metodología

El autor, Ákos Hajnal, realizó una investigación empírica exhaustiva utilizando optimización convexa para determinar la factibilidad de la separación lineal.

• Enfoque Teórico: Se reformuló el problema de separabilidad como un Programa Lineal (LP) de factibilidad. El objetivo es encontrar un vector normal $w$ y un sesgo $b$ tales que $y_i(w^T x_i + b) \ge 1$ para todas las muestras. Si el problema es factible, existe un hiperplano separador; si es infactible, no existe.
• Herramientas: Se utilizó la biblioteca de optimización convexa CVXPY (versión 1.6.7) en un entorno Python.
  • Se formuló el problema minimizando una constante (0) sujeto a las restricciones lineales.
  • El solucionador automático seleccionado fue CLARABEL.
  • Se verificó el estado de la solución: OPTIMAL indica separabilidad, mientras que INFEASIBLE indica no separabilidad.
• Configuración Experimental:
  • Hardware: Google Colab con GPU T4 y CPU Intel Xeon.
  • Datos: Se probaron tres configuraciones de datos:
    1. Conjunto de Entrenamiento (60.000 muestras).
    2. Conjunto de Prueba (10.000 muestras).
    3. Conjunto Combinado (Entrenamiento + Prueba).
  • Escenarios: Se evaluaron todas las 45 combinaciones posibles de pares de dígitos y las 10 configuraciones de "uno-vs-rest".

3. Resultados Clave

A. Separabilidad Par a Par (Pairwise):

• Conjunto de Entrenamiento:
  • No separable: Se identificaron 7 pares de dígitos que no son linealmente separables: (2-3), (2-8), (3-5), (3-8), (4-9), (5-8) y (7-9).
  • Separable: Los dígitos 0, 1 y 6 resultaron ser separables de cualquier otro dígito individualmente.
  • El dígito 8 fue el más problemático, mostrando conflictos de separabilidad con tres otros dígitos (2, 3 y 5).
• Conjunto Combinado (Entrenamiento + Prueba): Los resultados fueron idénticos a los del conjunto de entrenamiento. Esto sugiere que si existe un hiperplano para el entrenamiento, también funcionaría teóricamente para la prueba (sin necesidad de ver los datos de prueba).
• Conjunto de Prueba: Todos los pares de dígitos resultaron ser linealmente separables. Esto se atribuye al tamaño de muestra reducido del conjunto de prueba (10.000 muestras vs 60.000), lo que reduce la probabilidad de solapamiento de las envolventes convexas.

B. Separabilidad Uno-vs-Rest:

• Conjunto de Entrenamiento: Ningún dígito (del 0 al 9) es linealmente separable de todos los demás dígitos simultáneamente. Incluso los dígitos 0, 1 y 6, que eran separables par a par, fallaron en este escenario de múltiples clases.
• Conjunto Combinado: Resultados consistentes con el entrenamiento (ninguno es separable).
• Conjunto de Prueba: Algunos dígitos (0-4, 6, 7) aparecieron como separables, pero el autor advierte que estos resultados no son concluyentes debido al pequeño tamaño de la muestra, similar al caso par a par.

C. Rendimiento Computacional:

• El uso de CVXPY demostró ser eficiente. Los tiempos de ejecución para pares en el conjunto de entrenamiento variaron entre 6.4 y 24.7 segundos.
• Los casos no separables (infactibles) tardaron más en resolverse (hasta 25s) que los separables (12s), lo cual es consistente con la complejidad de demostrar la infactibilidad en programación lineal.
• Se observó una aceleración de 4 a 8 veces en comparación con métodos anteriores (como los de Zhong et al.) para el mismo subconjunto de datos.

4. Contribuciones y Conclusiones

• Clarificación Definitiva: El artículo resuelve la controversia histórica matizando la afirmación absoluta.
  • La afirmación "MNIST es linealmente separable" es falsa para el conjunto de entrenamiento en el escenario "uno-vs-rest" (el caso más relevante para clasificación multiclase real).
  • La afirmación "MNIST no es linealmente separable" es verdadera para el entrenamiento en "uno-vs-rest", pero falsa para el conjunto de prueba en el escenario "par a par".
• Hallazgo Principal: El dataset completo (entrenamiento) no es linealmente separable en el sentido de clasificación multiclase (uno-vs-rest). Sin embargo, ciertas distinciones binarias específicas (como 0 vs 1) sí son posibles.
• Implicaciones: Esto refuerza la necesidad de modelos no lineales (como Redes Neuronales Convolucionales o SVM con kernels no lineales) para lograr la alta precisión (>99%) observada en MNIST, ya que un clasificador lineal puro no puede separar perfectamente todas las clases simultáneamente en el conjunto de entrenamiento.

5. Significado

Este trabajo proporciona una base empírica rigurosa para entender las limitaciones geométricas de los datos MNIST. Al utilizar herramientas modernas de optimización convexa, el autor no solo confirma la intuición de que MNIST es complejo, sino que cuantifica exactamente qué pares de dígitos son confusos geométricamente y demuestra que la "separabilidad" depende críticamente de la configuración del experimento (tamaño del conjunto de datos y estrategia de clasificación). Los códigos fuente y los resultados de tiempo de ejecución sirven como referencia para futuros estudios sobre la complejidad de los datos en aprendizaje automático.