On Linear Separability of the MNIST Handwritten Digits Dataset

Cet article propose une enquête empirique complète pour déterminer si le jeu de données MNIST est linéairement séparable, en examinant systématiquement les séparations par paires et « un contre tous » sur les ensembles d'entraînement, de test et combinés afin de trancher les affirmations contradictoires existantes.

L'essentiel

🎨 Le Grand Débat : Peut-on séparer les chiffres manuscrits avec une seule ligne droite ?

Imaginez que vous êtes un professeur d'école maternelle. Vous avez un classeur rempli de dessins d'enfants représentant les chiffres de 0 à 9. C'est le célèbre dataset MNIST. Depuis des décennies, les experts en intelligence artificielle utilisent ce classeur pour tester si leurs "robots" savent apprendre à reconnaître ces chiffres.

Mais il y a une question bizarre qui tourne en boucle dans la communauté scientifique : Est-ce que l'on peut séparer tous ces dessins en utilisant une seule ligne droite ?

Pour faire simple, imaginez que vous étalez tous les dessins sur une table.

• Si vous pouvez tracer une seule ligne droite qui sépare parfaitement tous les "0" de tous les "1" (sans qu'aucun "0" ne se retrouve du mauvais côté), alors on dit que c'est linéairement séparable.
• Si les dessins sont si emmêlés qu'il faut une ligne courbe, ou une ligne en zigzag, ou même une grille complexe pour les séparer, alors ce n'est pas séparable.

L'auteur de cet article, Akos Hajnal, a décidé de trancher ce débat une bonne fois pour toutes, car les avis étaient contradictoires : certains disaient "Oui, c'est facile", d'autres "Non, c'est impossible".

🔍 L'Expérience : Le Test du "Tire-bouchon"

Pour répondre à la question, l'auteur n'a pas utilisé de devinettes. Il a utilisé un outil mathématique très puissant (appelé CVXPY) qui agit comme un tire-bouchon ultra-précis.

Il a posé deux types de questions à son ordinateur :

1. Le Duel (Pairwise) : "Peux-tu séparer les '2' des '3' avec une seule ligne ?" (Il a testé toutes les combinaisons possibles : 0 contre 1, 0 contre 2, etc.).
2. Le Combat contre tous (One-vs-Rest) : "Peux-tu séparer les '0' de TOUS les autres chiffres (1, 2, 3... 9) en même temps avec une seule ligne ?"

🏆 Les Résultats : La Vérité Sortie du Chapeau

Voici ce que l'expérience a révélé, avec des analogies pour bien comprendre :

1. Le Duel (Séparer deux chiffres spécifiques)

• Le verdict : C'est un mélange de "Oui" et de "Non".
• L'analogie : Imaginez que vous essayez de séparer les pommes rouges des pommes vertes. C'est facile ! Mais si vous essayez de séparer les pommes rouges des pommes qui ont une tache bizarre, c'est beaucoup plus dur.
• Ce qui a échoué : Certains couples de chiffres sont trop similaires. Par exemple, séparer un 2 d'un 3, ou un 5 d'un 8, est impossible avec une simple ligne droite. Les dessins sont trop emmêlés.
• Ce qui a réussi : Par contre, séparer un 0 d'un 1, ou un 6 d'un 7, est très facile. Une ligne droite suffit amplement.
• La surprise : Sur le petit groupe de test (les dessins que l'ordinateur n'a jamais vus avant), tous les duels ont réussi ! C'est comme si, par chance, les dessins de test étaient parfaitement rangés.

2. Le Combat contre tous (Un chiffre contre les 9 autres)

• Le verdict : C'est un grand NON.
• L'analogie : Imaginez que vous devez séparer les pommes rouges de tout le reste du panier (poires, bananes, oranges, raisins) en utilisant une seule ligne droite. C'est mathématiquement impossible si le panier est rempli de fruits de toutes formes.
• Ce que l'article prouve : Même les chiffres les plus "faciles" (comme le 0 ou le 1) ne peuvent pas être séparés de tous les autres chiffres en même temps avec une seule ligne. Les formes sont trop complexes et s'entremêlent trop.

💡 La Conclusion en une phrase

L'article conclut que dire "MNIST est séparable" ou "MNIST n'est pas séparable" est trop simpliste. C'est comme dire "La France est plate" : ça dépend de si vous regardez la plaine (c'est plat) ou les Alpes (c'est montagneux).

• Si vous voulez séparer deux chiffres précis : Parfois oui, parfois non.
• Si vous voulez séparer un chiffre de tout le reste : Non, c'est impossible avec une simple ligne droite.

🚀 Pourquoi est-ce important ?

Cela nous rappelle que l'intelligence artificielle, même pour des tâches qui semblent simples comme reconnaître un chiffre, doit souvent utiliser des "lignes courbes" (des modèles complexes) pour bien fonctionner. On ne peut pas se contenter d'une règle toute simple (linéaire) pour tout résoudre.

L'auteur a aussi montré que son outil de test était très rapide (comme un Ferrari par rapport à une vieille voiture), ce qui permettra aux autres chercheurs de faire ces vérifications beaucoup plus vite à l'avenir.

En résumé : Le dataset MNIST est un excellent terrain de jeu, mais il est plus complexe qu'il n'y paraît. On ne peut pas tout séparer avec une règle, il faut parfois un crayon pour dessiner des courbes ! 📐✨

Résumé technique

1. Problématique

Le jeu de données MNIST, contenant 70 000 images de chiffres manuscrits (0-9) en résolution 28x28, reste une référence fondamentale pour l'évaluation des modèles de reconnaissance de motifs. Malgré son histoire longue et sa simplicité relative, la question de savoir si ce jeu de données est linéairement séparable reste controversée.

La littérature scientifique et les sources informelles présentent des affirmations contradictoires : certaines prétendent que MNIST est linéairement séparable, tandis que d'autres affirment le contraire, souvent sans preuves empiriques rigoureuses. L'article vise à trancher cette question de manière définitive en distinguant deux scénarios :

• Séparabilité paire-à-paire (Pairwise) : Peut-on séparer linéairement une classe (ex: le chiffre 0) d'une autre classe spécifique (ex: le chiffre 1) ?
• Séparabilité un-contre-tous (One-vs-Rest) : Peut-on séparer linéairement une classe donnée de toutes les autres classes combinées ?

L'étude examine ces propriétés sur trois ensembles de données distincts : l'ensemble d'entraînement (60 000 échantillons), l'ensemble de test (10 000 échantillons) et l'ensemble combiné.

2. Méthodologie

L'auteur, Ákos Hajnal, adopte une approche basée sur l'optimisation convexe pour déterminer l'existence d'un hyperplan séparateur.

• Formulation du problème : La séparabilité linéaire est modélisée comme un problème de faisabilité (feasibility problem) via un Programme Linéaire (LP).
  • L'objectif est de trouver un vecteur normal $w$ et un biais $b$ tels que $y_i(w^\top x_i + b) \ge 1$ pour tous les échantillons $i$.
  • La fonction objectif est constante (minimiser 0), ce qui signifie que la solution existe si et seulement si le problème est faisable.
• Outils utilisés : L'expérimentation a été réalisée avec la bibliothèque CVXPY (version 1.6.7) sous Python, utilisant le solveur CLARABEL.
  • Contrairement aux SVM à marge douce (qui pénalisent les erreurs) ou aux méthodes heuristiques, cette approche teste la séparabilité parfaite. Si le solveur renvoie un statut INFEASIBLE, la séparabilité est prouvée comme impossible.
• Configuration expérimentale : Les tests ont été exécutés sur Google Colab avec un GPU T4 et un processeur Intel Xeon. Les temps d'exécution et les résultats de faisabilité ont été enregistrés pour toutes les combinaisons possibles.

3. Résultats Clés

A. Séparabilité Paire-à-Paire (Pairwise)

Sur l'ensemble d'entraînement (60k échantillons) :

• Non-séparabilité : 7 paires de chiffres sont non séparables : (2-3), (2-8), (3-5), (3-8), (4-9), (5-8) et (7-9).
• Séparabilité : Les chiffres 0, 1 et 6 sont séparables de tous les autres chiffres individuellement.
• Observation : Le chiffre 8 est le plus difficile à distinguer, entrant en conflit avec trois autres chiffres (2, 3, 5).
• Ensemble de test : Curieusement, toutes les paires de l'ensemble de test (10k échantillons) apparaissent séparables. L'auteur attribue cela à la taille d'échantillonnage plus faible, qui réduit la probabilité de chevauchement des classes.
• Ensemble combiné : Les résultats suivent ceux de l'entraînement (les paires non séparables restent non séparables).

B. Séparabilité Un-contre-Tous (One-vs-Rest)

Sur l'ensemble d'entraînement :

• Résultat global : Aucun chiffre (de 0 à 9) ne peut être séparé linéairement de l'ensemble des autres chiffres combinés.
• Même les chiffres 0, 1 et 6, qui étaient séparables en mode paire-à-paire, deviennent non séparables lorsqu'ils sont confrontés à la classe "tout le reste".
• Les temps de calcul pour ces tests sont significativement plus longs (89 à 209 secondes) en raison de la taille des ensembles de données négatives.

4. Contributions et Significativité

• Clarification d'un mythe : L'article démontre que les affirmations binaires (« MNIST est séparable » ou « MNIST n'est pas séparable ») sont toutes deux incorrectes si elles ne sont pas nuancées.
  • Vrai : L'ensemble de test est linéairement séparable en mode pairwise.
  • Vrai : L'ensemble d'entraînement (et donc le dataset complet) n'est pas séparable en mode one-vs-rest.
  • Nuance : La séparabilité dépend strictement de la définition du problème (paire vs global) et de la taille de l'échantillon.
• Preuve empirique rigoureuse : Contrairement à des études précédentes basées sur des approximations ou des sous-ensembles réduits, cette étude utilise une résolution exacte de problèmes de faisabilité sur l'intégralité des données.
• Benchmark de performance : L'auteur fournit des temps d'exécution de référence pour les tests de séparabilité linéaire, montrant que l'approche via CVXPY est 4 à 8 fois plus rapide que les méthodes précédentes (comme celles de Zhong et al.) sur des tâches similaires.
• Implications pour l'apprentissage automatique : Ces résultats soulignent les limites des modèles purement linéaires (comme le Perceptron ou la régression logistique sans noyau) pour résoudre le problème MNIST dans sa globalité, justifiant la nécessité d'approches non linéaires (SVM à noyau, Réseaux de Neurones) pour atteindre les performances actuelles (99,9 %).

Conclusion

L'article conclut que la séparabilité linéaire de MNIST n'est pas une propriété absolue du dataset, mais une propriété contextuelle. Bien que des séparateurs linéaires parfaits existent pour certaines paires de chiffres (surtout dans le jeu de test), l'ensemble complet des données manuscrites n'est pas linéairement séparable lorsqu'on considère la tâche de classification complète (un-contre-tous). Cette étude met fin aux débats informels en apportant une preuve mathématique et computationnelle définitive.