On Linear Separability of the MNIST Handwritten Digits Dataset

✨

Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

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

Stel je voor dat je een enorme verzameling hebt van 70.000 foto's van handgeschreven cijfers (0 tot 9). Dit is het beroemde MNIST-dataset, een soort "trainingsmateriaal" voor computers die leren om handschrift te lezen.

De vraag die deze paper onderzoekt, klinkt heel simpel, maar is verrassend lastig: Kunnen we deze cijfers met één rechte lijn van elkaar scheiden?

Om dit uit te leggen, gebruiken we een paar creatieve analogieën.

1. De Rechterlijn (Lineaire Scheidbaarheid)

Stel je een grote vloer voor waarop iedereen een cijfer op zijn rug heeft geschreven.

Lineaire scheidbaarheid betekent dat je één rechte muur (een "scheidingswand") door de kamer kunt zetten, zodat alle mensen met een '3' aan de ene kant staan en alle mensen met een '5' aan de andere kant.
Als je die muur kunt plaatsen zonder dat iemand erdoorheen staat, zijn ze lineair scheidbaar.
Als er mensen met een '3' en '5' door elkaar lopen die je niet kunt scheiden zonder de muur te breken of mensen te snijden, dan zijn ze niet scheidbaar.

2. De Twee Manieren om te Kijken

De auteurs van dit paper keken naar dit probleem op twee manieren:

Manier A: "Twee tegen Twee" (Pairwise)
Hier kijken we alleen naar twee soorten cijfers tegelijk. Bijvoorbeeld: "Kunnen we alle '2'en van alle '8'en scheiden met één rechte lijn?"
- Het resultaat: Soms wel, soms niet. Sommige cijfers (zoals 0, 1 en 6) lijken heel makkelijk te scheiden van de rest. Maar andere paren, zoals een '2' en een '3', lopen zo door elkaar dat je geen rechte lijn kunt trekken zonder dat er een '2' en een '3' aan dezelfde kant komen.
Manier B: "Eén Tegen Alles" (One-vs-Rest)
Hier proberen we één specifiek cijfer (bijvoorbeeld alle '0'en) te scheiden van alle andere cijfers (1 tot 9) tegelijk.
- Het resultaat: Dit is veel moeilijker. Het is alsof je probeert alle mensen met een '0' op je rug in één hoek van de kamer te krijgen, terwijl iedereen met een 1, 2, 3...9 in de rest van de kamer staat. De paper toont aan dat dit niet lukt voor de trainingsdata. De '0'en zitten te ver verspreid en vermengd met de andere cijfers om ze met één rechte lijn af te zonderen.

3. De Verwarring Opgehelderd

Vroeger waren wetenschappers en experts het oneens. Sommigen zeiden: "MNIST is simpel, het is vast lineair scheidbaar!" Anderen zeiden: "Nee, handschrift is te rommelig, het is niet scheidbaar."

Deze paper doet een grondig onderzoek (met geavanceerde wiskundige software die als een super-snel rekenmachine werkt) om de waarheid te vinden. Ze kijken naar:

De trainingsset (waar de computer leert).
De testset (waar de computer wordt getoetst).
De gecombineerde set (alles bij elkaar).

4. De Conclusie: Het hangt ervan af!

De conclusie is verrassend genuanceerd. Het antwoord is niet simpelweg "ja" of "nee", maar hangt af van wat je precies vraagt:

Is de hele dataset lineair scheidbaar? Nee. Je kunt niet alle cijfers van elkaar scheiden met één simpele regel.
Zijn specifieke paren scheidbaar? Soms wel, soms niet. Bijvoorbeeld, een '0' en een '1' zijn makkelijk te scheiden. Maar een '2' en een '3' zijn dat niet.
Wat is het belangrijkste verschil?
- Als je kijkt naar de testset (de kleine groep van 10.000 foto's die de computer nog niet heeft gezien), lijken alle paren scheidbaar te zijn. Dit komt alleen omdat de groep zo klein is dat er minder "verwarring" is.
- Maar als je kijkt naar de trainingsset (de grote groep van 60.000 foto's), is het duidelijk: Het is niet lineair scheidbaar. Je kunt geen enkele rechte lijn vinden die perfect alle '0'en van alle '1en' tot '9en' scheidt.

Samenvattend

Deze paper zegt eigenlijk: "Stop met het zeggen dat MNIST simpel is. Het is alsof je probeert een rechte lijn te trekken door een dichte menigte mensen die allemaal verschillende cijfers dragen. Soms lukt het tussen twee specifieke groepen, maar als je de hele menigte wilt ordenen met één lijn, is dat onmogelijk."

Dit is belangrijk omdat het ons leert dat zelfs "simpele" datasets complexer zijn dan ze lijken, en dat we slimme algoritmen (zoals diep neurale netwerken) nodig hebben die kunnen omgaan met deze rommel, in plaats van te vertrouwen op simpele rechte lijnen.

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

Titel: Over Lineaire Scheidbaarheid van het MNIST Handgeschreven Cijfers Dataset

Auteur: Ákos Hajnal (SZTAKI & Óbuda University)
Datum: November 2025

1. Probleemstelling

Het MNIST-dataset, bestaande uit 70.000 grijstinten afbeeldingen van handgeschreven cijfers (28x28 pixels), is een fundamentele benchmark voor patroonherkenning en beeldclassificatie. Ondanks de lange geschiedenis en relatieve eenvoud van het dataset, is de vraag of het dataset lineair scheidbaar is, nooit volledig beantwoord. Er bestaan tegenstrijdige claims in zowel wetenschappelijke als informele bronnen: sommigen beweren dat het dataset lineair scheidbaar is, terwijl anderen het tegendeel beweren.

De paper onderscheidt twee scenario's voor lineaire scheidbaarheid:

Paarsgewijze scheidbaarheid (Pairwise): Kan één cijfer (bijv. '0') lineair worden gescheiden van één ander specifiek cijfer (bijv. '1')?
One-vs-Rest scheidbaarheid: Kan één cijfer worden gescheiden van alle andere negen cijfers samen?

De auteurs willen deze onduidelijkheid wegnemen door een uitgebreid empirisch onderzoek uit te voeren op de trainingsset, de testset en de gecombineerde set.

2. Methodologie

De auteurs hebben gekozen voor een convex optimalisatie-benadering om de scheidbaarheid te testen, specifiek door het oplossen van een Lineair Programma (LP).

Formulering: Het probleem wordt geformuleerd als een haalbaarheidsprobleem (feasibility problem). Het doel is om een scheidend hypervlak te vinden ( $w^T x_i + b = 0$ $w^{T} x_{i} + b = 0$ ) dat voldoet aan de voorwaarden:
- $w^T x_i + b \geq 1$ voor positieve klassen.
- $w^T x_j + b \leq -1$ voor negatieve klassen.
- De objectieve functie is constant (minimiseer 0), waardoor de focus ligt op het bestaan van een oplossing in plaats van het maximaliseren van de marge.
Tools: De experimenten zijn uitgevoerd met CVXPY (versie 1.6.7), een open-source bibliotheek voor convex optimalisatie. De solver CLARABEL werd automatisch geselecteerd.
Hardware: Experimenten liepen op Google Colab met een Intel Xeon CPU en een T4 GPU (hoewel GPU-versnelling in deze specifieke CVXPY-versie niet werd gebruikt).
Aanpak:
- Alle 45 mogelijke paarsgewijze combinaties (10 cijfers) werden getest.
- De 'one-vs-rest' scenario's werden getest voor elk van de 10 cijfers.
- Dit werd herhaald voor de trainingsset (60.000 samples), de testset (10.000 samples) en de gecombineerde set.

3. Belangrijkste Resultaten

A. Paarsgewijze Lineaire Scheidbaarheid

Trainingsset:
- Niet scheidbaar: Zeven paren bleken niet lineair scheidbaar: (2-3), (2-8), (3-5), (3-8), (4-9), (5-8) en (7-9).
- Scheidbaar: De cijfers 0, 1 en 6 bleken lineair scheidbaar van elk ander cijfer in paarsgewijze vergelijkingen.
- Moeilijkste cijfer: Cijfer 8 bleek het meest problematisch, aangezien het conflicteerde met drie andere cijfers (2, 3 en 5).
Gecombineerde Set (Train + Test): De resultaten waren identiek aan de trainingsset. Het toevoegen van testdata veranderde de scheidbaarheid van geen enkel paar. Dit impliceert dat als een scheidend hypervlak bestaat voor de trainingsset, het theoretisch ook perfect werkt op de testset.
Testset: Alle paarsgewijze combinaties bleken scheidbaar. Dit wordt toegeschreven aan de kleinere steekproefgrootte (10.000 samples), wat de kans op overvleugeling (overlap) van de convex hulls verkleint.
Prestatie: De methode was 4-8 keer sneller dan eerdere methoden (zoals die van Zhong et al.) voor vergelijkbare taken.

B. One-vs-Rest Lineaire Scheidbaarheid

Trainingsset: Geen enkel cijfer (0 t/m 9) was lineair scheidbaar van alle andere cijfers samen. Zelfs de cijfers 0, 1 en 6, die in paarsgewijze tests goed presteerden, faalden in de 'one-vs-rest' setting.
Gecombineerde Set: Dezelfde resultaten als de trainingsset (allemaal niet scheidbaar).
Testset: Cijfers 0, 1, 2, 3, 4, 6 en 7 bleken scheidbaar van de rest. Echter, de auteurs waarschuwen dat dit resultaat niet definitief is vanwege de kleine steekproefgrootte van de testset. Cijfers 5, 8 en 9 waren niet scheidbaar.

4. Bijdragen en Conclusies

De paper levert een definitief empirisch antwoord op de vraag naar de lineaire scheidbaarheid van MNIST, waarbij de nuance tussen verschillende dataset-indelingen en scheidingsstrategieën cruciaal is:

Nuancering van claims: De algemene uitspraken "MNIST is lineair scheidbaar" of "MNIST is niet lineair scheidbaar" zijn te simplistisch.
- De testset is wel degelijk lineair scheidbaar, maar alleen in paarsgewijze vergelijkingen.
- De trainingsset (en dus het volledige dataset) is niet lineair scheidbaar in de 'one-vs-rest' setting.
Empirisch bewijs: De auteurs hebben voor het eerst systematisch alle 45 paarsgewijze combinaties en alle 10 'one-vs-rest' scenario's getest op de volledige trainingsset met een robuuste convex-optimalisatie-oplosser.
Methodologische validatie: Het gebruik van CVXPY als haalbaarheidsoplosser bleek zeer efficiënt en betrouwbaar voor het vaststellen van niet-scheidbaarheid (INFEASIBLE status), wat lastiger is met benaderingsmethoden zoals SVM met straffactoren.

5. Significatie

De studie corrigeert misvattingen in de literatuur en biedt een helder beeld van de complexiteit van het MNIST-dataset. Het bevestigt dat hoewel MNIST vaak wordt gebruikt als een "eenvoudig" dataset voor diepe leermodellen, de onderliggende lineaire structuur complex is:

Cijfers zijn vaak niet lineair scheidbaar van elkaar als je ze in één keer tegen alle anderen moet afzetten.
De prestaties van lineaire modellen op MNIST worden beperkt door deze intrinsieke niet-scheidbaarheid, wat de noodzaak onderstreept van niet-lineaire modellen (zoals CNN's) voor hoge nauwkeurigheid.

De paper concludeert dat de claim "MNIST is niet lineair scheidbaar" geldig is voor de trainingsset in een realistische classificatietaken (one-vs-rest), terwijl de claim "MNIST is lineair scheidbaar" alleen geldt voor de testset in geïsoleerde paarsgewijze scenario's.