On Linear Separability of the MNIST Handwritten Digits Dataset

Diese Arbeit liefert eine umfassende empirische Untersuchung, die die bisher widersprüchlichen Behauptungen zur linearen Trennbarkeit des MNIST-Datensatzes klärt, indem sie systematisch alle relevanten Datensatzkombinationen und Trennszenarien analysiert.

Das Wesentliche

Titel: Sind die Ziffern von MNIST wie getrennte Inseln? – Eine einfache Erklärung

Stellen Sie sich vor, Sie haben einen riesigen Korb voller Zettel. Auf jedem Zettel ist eine handgeschriebene Zahl von 0 bis 9 zu sehen. Das ist der berühmte MNIST-Datensatz, der seit Jahrzehnten als „Prüfstein" für Computer dient, um zu sehen, wie gut sie Muster erkennen können.

Die große Frage, die dieser Paper beantwortet, ist: Kann man diese Zahlen mit einer einzigen, geraden Linie trennen?

Um das zu verstehen, nutzen wir ein paar einfache Bilder:

1. Das Grundproblem: Die gerade Linie

Stellen Sie sich vor, Sie zeichnen auf einen großen Tisch eine gerade Linie.

• Die Aufgabe: Können Sie eine Linie so ziehen, dass alle Zettel mit der Zahl „3" auf der einen Seite liegen und alle Zettel mit der Zahl „8" auf der anderen Seite?
• Der Clou: Wenn Sie das für jedes Paar von Zahlen (z. B. 3 gegen 8, 3 gegen 5, 0 gegen 1) schaffen können, dann sind diese Zahlen „linear trennbar".

Die Wissenschaftler haben sich gefragt: Ist das bei den MNIST-Zahlen möglich? Oder sind die Zahlen so durcheinander gewürfelt, dass keine gerade Linie alle „3er" von allen „8ern" trennen kann, ohne dass ein paar Zettel auf die falsche Seite fallen?

2. Die zwei Arten des Trennens

Der Paper untersucht zwei verschiedene Szenarien, wie man diese Zahlen sortieren könnte:

Szenario A: Das Duell (Paarweise Trennung)
Stellen Sie sich ein Boxring vor. Nur zwei Kämpfer sind im Ring: Die Zahl 3 gegen die Zahl 8.

• Können wir eine Linie ziehen, die alle 3er von allen 8ern trennt?
• Das Ergebnis: Ja, das geht oft! Wenn man nur zwei Zahlen vergleicht, finden die Computer fast immer eine gerade Linie, die sie trennt. Selbst wenn die Handschriften krumm sind, gibt es meist eine mathematische „Trennlinie".
• Aber: Bei manchen Paaren (wie 2 gegen 3 oder 5 gegen 8) ist es wie bei zwei Menschen, die sich so ähnlich sehen, dass man sie nicht unterscheiden kann, ohne dass einer falsch zugeordnet wird. Hier scheitert die gerade Linie.

Szenario B: Der König gegen alle (One-vs-Rest)
Jetzt wird es schwieriger. Stellen Sie sich vor, die Zahl 3 ist der König. Alle anderen Zahlen (0, 1, 2, 4, 5, 6, 7, 8, 9) sind eine riesige Armee, die ihn angreift.

• Können wir eine einzige gerade Linie ziehen, die den König (alle 3er) von der gesamten Armee (alle anderen Zahlen) trennt?
• Das Ergebnis: Nein. Das ist unmöglich. Die Zahlen sind zu unterschiedlich geformt und liegen im „Raum" der Daten so vermischt, dass keine gerade Linie den König von allen anderen gleichzeitig trennen kann. Es gibt immer ein paar 3er, die so aussehen wie ein 5er oder 8er, und sie rutschen durch die Lücken der Linie.

3. Der Unterschied zwischen Übung und Prüfung

Der Paper macht noch einen wichtigen Unterschied zwischen zwei Gruppen von Daten:

• Die Trainingsgruppe: Das sind 60.000 Zettel, mit denen der Computer lernt. Hier ist das Chaos groß. Die Zahlen sind so vielfältig, dass man sie nicht perfekt mit einer Linie trennen kann.
• Die Prüfgruppe: Das sind 10.000 Zettel, die der Computer zum ersten Mal sieht.
  • Überraschung: Bei den paarweisen Duellen (z. B. 3 gegen 8) waren sogar die Prüfzettel trennbar! Das liegt daran, dass die Stichprobe kleiner ist und weniger „krumme" Handschriften enthält.
  • Aber auch hier gilt: Wenn man einen König gegen alle anderen stellt, scheitert die gerade Linie.

4. Wie haben sie das herausgefunden? (Der Werkzeugkasten)

Früher haben Wissenschaftler versucht, das mit komplizierten mathematischen Methoden zu berechnen, die ewig dauerten.
Dieser Autor hat ein modernes Werkzeug namens CVXPY benutzt. Man kann sich das wie einen super-schnellen Robotermathematiker vorstellen, der in Sekundenbruchteilen prüft: „Gibt es eine gerade Linie, die das schafft?"

• Wenn der Roboter eine Linie findet, sagt er: „Ja, trennbar!"
• Wenn er beweist, dass keine Linie existiert, sagt er: „Nein, unmöglich!"

Fazit: Was bedeutet das für uns?

Die lange, verwirrende Frage „Ist MNIST linear trennbar?" hat keine einfache Ja/Nein-Antwort. Es kommt darauf an, wie man die Frage stellt:

1. Ist es möglich, zwei beliebige Zahlen voneinander zu trennen?
   • Meistens Ja, aber bei manchen ähnlichen Zahlen (wie 2 und 3) Nein.
2. Ist es möglich, eine Zahl von allen anderen gleichzeitig zu trennen?
   • Nein. Das ist unmöglich. Die Welt der handgeschriebenen Zahlen ist zu komplex für eine einzige, einfache gerade Linie.

Die große Lektion:
Dies zeigt uns, warum moderne KI (wie Deep Learning) so erfolgreich ist. Einfache, gerade Linien (wie bei alten Computern) reichen nicht aus, um komplexe Dinge wie Handschrift zu verstehen. Wir brauchen „krumme" Linien und komplexe Netzwerke, die die Welt so sehen, wie sie wirklich ist: nicht in einfachen Kategorien, sondern in einem riesigen, verschlungenen Gewebe von Mustern.

Der Paper sagt also im Grunde: „Hört auf zu behaupten, MNIST sei einfach linear trennbar. Es ist ein bisschen wie ein Puzzle, bei dem einige Teile gut passen, aber das ganze Bild nie durch einen einzigen Schnitt geteilt werden kann."

Technische Zusammenfassung

Technische Zusammenfassung: Lineare Trennbarkeit des MNIST-Datensatzes

1. Problemstellung
Der MNIST-Datensatz (70.000 handgeschriebene Ziffern in 28x28 Pixeln) ist seit den späten 1990er Jahren ein fundamentaler Benchmark für Mustererkennung und Bildklassifizierung. Trotz seiner weiten Verbreitung und relativen Einfachheit bleibt die Frage nach der linearen Trennbarkeit (Linear Separability) des Datensatzes unbeantwortet und Gegenstand widersprüchlicher Behauptungen in der wissenschaftlichen Literatur.
Die zentrale Frage lautet: Existiert eine einzelne lineare Entscheidungsgrenze (Hyperebene), die die Datenpunkte zweier Klassen perfekt voneinander trennt?
Untersucht werden zwei Szenarien:

• Pairwise (Paarweise): Kann eine Ziffer (z. B. 0) linear von einer anderen spezifischen Ziffer (z. B. 1) getrennt werden?
• One-vs-Rest (Ein-gegen-Alle): Kann eine Ziffer linear von allen anderen neun Ziffern getrennt werden?

Bisherige Studien waren entweder unvollständig, basierten auf reduzierten Datensätzen oder lieferten keine definitiven Beweise für die Nicht-Trennbarkeit.

2. Methodik
Der Autor, Ákos Hajnal, führt eine umfassende empirische Untersuchung durch, um die Trennbarkeit für den Trainingsset, den Testset und den kombinierten Datensatz zu bestimmen.

• Formulierung als lineares Programm (LP): Das Problem der linearen Trennbarkeit wird als reines Zulässigkeitsproblem (Feasibility Problem) formuliert. Gesucht wird ein Vektor $w$ und ein Bias $b$, sodass für alle positiven Proben $w^T x_i + b \ge 1$ und für alle negativen Proben $w^T x_j + b \le -1$ gilt.
• Werkzeug: Als Solver wird die Bibliothek CVXPY (Version 1.6.7) verwendet, die auf dem CLARABEL-Solver basiert. Dies ermöglicht die Lösung von konvexen Optimierungsproblemen und liefert einen definitiven Status:
  • OPTIMAL: Eine trennende Hyperebene existiert (Daten sind linear trennbar).
  • INFEASIBLE: Keine solche Hyperebene existiert (Daten sind nicht linear trennbar).
• Experimentelles Setup: Die Experimente wurden in einer Google Colab-Umgebung mit einer T4 GPU und Intel Xeon CPU durchgeführt. Alle 45 möglichen Ziffernpaare (Pairwise) sowie die 10 One-vs-Rest-Konfigurationen wurden für Trainings-, Test- und Kombinierte-Sets separat getestet.

3. Wichtige Ergebnisse

Die Studie liefert differenzierte Ergebnisse, die pauschale Aussagen widerlegen:

• Pairwise-Trennbarkeit (Ziffer gegen Ziffer):

  • Trainingsset: 7 von 45 Paaren sind nicht linear trennbar (insbesondere: 2–3, 2–8, 3–5, 3–8, 4–9, 5–8, 7–9). Die Ziffern 0, 1 und 6 sind jedoch von allen anderen Ziffern paarweise trennbar.
  • Testset: Alle 45 Paare sind linear trennbar. Dies wird auf die geringere Stichprobengröße des Testsets zurückgeführt.
  • Kombiniertes Set: Die Ergebnisse entsprechen denen des Trainingssets (die nicht trennbaren Paare bleiben nicht trennbar).
  • Interpretation: Das Hinzufügen des Testsets zum Trainingsset ändert die Trennbarkeit nicht; wenn eine Hyperebene im Trainingsset existiert, kann sie theoretisch auch das Testset perfekt trennen.

• One-vs-Rest-Trennbarkeit (Ziffer gegen alle anderen):

  • Trainingsset: Keine der 10 Ziffern ist linear von allen anderen getrennt. Dies bestätigt, dass der gesamte MNIST-Datensatz im One-vs-Rest-Szenario nicht linear trennbar ist.
  • Testset: Mehrere Ziffern (0–4, 6, 7) scheinen trennbar zu sein, was jedoch aufgrund der kleinen Stichprobengröße nicht als endgültiger Beweis für die generelle Trennbarkeit gewertet wird.
  • Kombiniertes Set: Wie beim Trainingsset sind keine Ziffern trennbar.

• Performance:

  • Die CVXPY-Methode zeigte eine hohe Effizienz. Paarweise Tests dauerten im Trainingsset zwischen 6,4 und 24,7 Sekunden. One-vs-Rest-Tests dauerten aufgrund der größeren Datenmenge zwischen 89 und 209 Sekunden.
  • Ein Vergleich mit früheren Methoden (Zhong et al.) zeigt eine 4- bis 8-fache Beschleunigung durch die verwendete CVXPY-Implementierung.

4. Hauptbeiträge

• Klärung einer offenen Frage: Das Paper liefert den ersten umfassenden, empirischen Beweis für die lineare Trennbarkeit des MNIST-Datensatzes unter verschiedenen Bedingungen.
• Differenzierung der Ergebnisse: Es widerlegt die pauschalen Behauptungen, MNIST sei entweder „linear trennbar" oder „nicht linear trennbar". Die Wahrheit liegt in der Nuance:
  • Der Trainingsset ist im One-vs-Rest-Szenario nicht linear trennbar.
  • Der Testset ist im Pairwise-Szenario linear trennbar (aufgrund kleinerer Stichprobe).
• Reproduzierbarkeit: Der Autor stellt den Quellcode auf GitHub zur Verfügung und dokumentiert die Laufzeiten als Benchmark für zukünftige Studien.

5. Signifikanz und Fazit
Die Studie zeigt, dass die Annahme, lineare Modelle könnten MNIST perfekt lösen, falsch ist, sobald man den gesamten Trainingsdatensatz im One-vs-Rest-Szenario betrachtet. Die Nicht-Trennbarkeit bestimmter Ziffernpaare (insbesondere 2, 3, 5, 8, 9) erklärt, warum einfache lineare Klassifikatoren (wie Perzeptron oder lineare SVM ohne Kernel-Tricks) bei MNIST an ihre Grenzen stoßen und tiefere Architekturen (CNNs) notwendig sind, um die hohen Genauigkeitswerte (>99%) zu erreichen.

Die Arbeit etabliert einen klaren methodischen Rahmen zur Überprüfung der linearen Trennbarkeit und liefert definitive Daten, die als Referenz für die Bewertung von Klassifikationsalgorithmen und die theoretische Analyse von Merkmalsräumen dienen können.