📊 statistics

A scalable version of MADD for big-data classification

Dit artikel stelt een schaalbare versie voor van de Mean Absolute Difference of Distances (MADD)-classifier die de computationele complexiteit voor big-data-classificatie aanzienlijk vermindert door gebruik te maken van representatieve verzamelingselectie en Random Fourier Features, waardoor de toepassing ervan op grootschalige, hoogdimensionale datasets mogelijk wordt terwijl de prestaties vergelijkbaar blijven met die van de oorspronkelijke methode.

Oorspronkelijke auteurs: Annesha Ghosh, Adrija Saha, Soham Sarkar

Gepubliceerd 2026-07-10

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Annesha Ghosh, Adrija Saha, Soham Sarkar

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert de "beste vriend" te vinden van een nieuw persoon die een drukke kamer binnenloopt. In de wereld van computerwetenschappen wordt dit classificatie genoemd: uitzoeken bij welke groep een nieuw datapunt hoort door te kijken naar welke groep het dichtstbij is.

Lange tijd gebruikten computers een simpel liniaal genaamd Euclidische afstand om deze nabijheid te meten. Maar hier komt de wending: in hoogdimensionale werelden (denk aan data met honderden of duizenden kenmerken, zoals gensequenties of hoogwaardige afbeeldingen), werkt die liniaal niet meer. Het is alsof je probeert te beoordelen wie het dichtstbij staat in een kamer waar iedereen zo ver uit elkaar staat dat iedereen even ver weg lijkt. De computer raakt in de war, de "nabijheid" van de buurt stort in, en de classificatie mislukt.

Om dit op te lossen, hebben wetenschappers een slimmere liniaal uitgevonden genaamd MADD (Mean Absolute Difference of Distances). In plaats van alleen de afstand van A naar B te meten, vraagt MADD: "Hoe verhoudt de afstand van A tot iedereen anders zich tot de afstand van B tot iedereen anders?" Als A en B uit dezelfde groep komen, is dit verschil minuscuul. Als ze uit verschillende groepen komen, is dit verschil enorm. Het is een briljante truc die perfect werkt in hoge dimensies.

Maar er is een addertje onder het gras.

MADD is een beetje een traaglul. Om de afstand tussen twee punten te meten, moet het naar elke andere persoon in de kamer kijken. Als je een kleine kamer hebt (een kleine dataset), is dat prima. Maar als je een enorme menigte hebt (big data), moet MADD een wiskundig probleem oplossen voor elke denkbare combinatie van mensen. Het onderzoek laat zien dat als je 16.384 trainingsmonsters hebt, MADD meer dan 6,5 uur nodig heeft om slechts 5.000 nieuwe mensen te classificeren. Dat is alsof je een naald in een hooiberg probeert te vinden door elke strohalm één voor één met een vergrootglas te controleren. Het werkt, maar het is pijnlijk traag.

Het Grote Idee: De "Representatieve Squad"

De auteurs van dit paper vroegen zich af: "Moeten we echt iedereen in de menigte vragen? Of kunnen we gewoon een paar slimme vertegenwoordigers vragen?"

Ze stelden een schaalbare versie van MADD voor (genoemd MADDsc). In plaats van de nieuwe persoon te vergelijken met alle 16.384 mensen, kiest de computer een kleine, super-slimme "squad" van vertegenwoordigers. Deze squad wordt gekozen met behulp van een fancy wiskundig hulpmiddel genaamd een Determinantal Point Process (DPP).

Denk aan DPP als een zeer kieskeurige feestplanner. Als je een willekeurig persoon vraagt om een groep vrienden te kiezen, kiezen ze misschien vijf mensen die allemaal in dezelfde hoek zitten en er precies hetzelfde uitzien. Maar DPP is anders; het vermijdt actief het kiezen van vergelijkbare mensen. Het zorgt ervoor dat de squad een mix heeft van mensen uit verschillende hoeken van de kamer, waardoor de volledige vibe van de menigte wordt gevangen zonder dat er met iedereen gesproken hoeft te worden.

Door deze squad te gebruiken (die misschien zo klein is als 50 of 100 mensen in plaats van duizenden), kan de computer de MADD-berekening in een fractie van de tijd uitvoeren.

Het Resultaat: In hun tests was deze nieuwe methode bijna even nauwkeurig als de trage, originele MADD, maar het was massaal sneller. Voor een dataset van 4.096 monsters duurde de nieuwe methode ongeveer 472 seconden, terwijl de oude methode 1.249 seconden nodig had. Dat is een enorme versnelling!

De "Super-Snelheid" Truc voor Gigantische Datasets

Wat als de menigte zo groot is dat zelfs het kiezen van een squad te lang duurt? De auteurs voegden een tweede truc toe genaamd Random Fourier Features (RFF).

Stel je voor dat je een enorme bibliotheek met boeken hebt en je moet vergelijkbare boeken vinden. In plaats van elke pagina te lezen, gebruik je een magische scanner die de tekst omzet in een eenvoudige code. Deze code is kort genoeg om in je zak te passen, maar behoudt nog steeds de "essentie" van het boek. RFF doet dit voor de w математиka achter de selectie van de squad.

Toen ze dit testten op een dataset met 25.000 trainingsmonsters:

Faalde de originele MADD-methode omdat het het geheugen tekortkwam (het kon de data letterlijk niet vasthouden).
De MADDsc-methode (zonder de magische scanner) duurde meer dan 15 uur.
De MADDsc-methode met de RFF-magische scanner was in minder dan 25 minuten klaar (specifiek, 1.468,68 seconden).

Heeft het echt gewerkt?

De auteurs hebben niet alleen gegokt; ze hebben 25 simulaties uitgevoerd voor elk scenario om er zeker van te zijn. Ze hebben de methode getest op:

Synthetische Data: Opgemaakte data waarbij ze het antwoord kenden.
Echte Data: Real-world tijdreeksdata zoals hartslagen, elektriciteitsverbruik en sensorgegevens uit de UCR Time Series Classification Archive.

In de simulaties was de nieuwe methode (MADDsc) consistent competitief en versloeg het vaak andere populaire methoden zoals Random Forests of Support Vector Machines, vooral wanneer de data lastige vormen of mengelingen had. In de tests met echte data presteerde het erg goed en kwam het vaak op de eerste of tweede plaats. Bijvoorbeeld, op de "Synthetic Control Chart" dataset maakte MADDsc slechts 1,29% fouten, waarmee het de standaard nearest-neighbor methode versloeg die 9,13% fouten maakte.

Wat ze niet deden (En wat ze vermeden)

Het is belangrijk om te weten wat dit paper niet beweerde.

Ze sloten eenvoudige willekeurige bemonstering (het kiezen van een squad door met je ogen dicht te wijzen) uit. Ze toonden aan dat willekeurige keuzes vaak belangrijke structuren in de data missen, wat leidt tot slechtere prestaties.
Ze beweerden niet dat dit voor elke mogelijke soort data voor altijd werkt. Ze merkten op dat voor een complexere versie van hun methode (genaamd gMADD), ze de "magische scanner" (RFF) truc nog niet konden gebruiken omdat de wiskunde te ingewikkeld is om de juiste code te bepalen. Ze suggereren dat dit een probleem kan zijn voor toekomstige onderzoekers om op te lossen.
Ze zeiden niet dat de methode "perfect" of "opgelost" is. Ze toonden aan dat de foutmarges in hun specifieke simulaties zeer dicht bij de originele trage methode lagen (meestal binnen 1%), maar de snelheidswinst was de echte held.

De Kern van het Verhaal

Het paper bewijst dat je kunt hebben wat je wilt. Je hoeft niet te kiezen tussen een trage, nauwkeurige methode en een snelle, onnauwkeurige methode. Door een slimme, diverse "squad" van vertegenwoordigers te kiezen in plaats van de hele menigte te vragen, en door enkele slimme wiskundige shortcuts te gebruiken voor de grootste datasets, kun je enorme hoeveelheden data snel classificeren zonder aan nauwkeurigheid in te boeten.

Zoals de auteurs in hun tests lieten zien, maakt deze aanpak het mogelijk om een krachtige tool (MADD) te gebruiken op "big data" problemen die voorheen te traag of te geheugenintensief waren om te verwerken. Het is een overwinning voor snelheid, en een overwinning voor nauwkeurigheid, terwijl de wiskunde eerlijk blijft.

Technische Samenvatting: Een Schaalbare Versie van MADD voor Big-Data Classificatie

Probleemstelling
Afstandsgebaseerde classificatoren, in het bijzonder die gebaseerd op de Euclidische afstand, zijn fundamenteel voor moderne machine learning. Echter, in scenario's met hoge dimensionaliteit en een kleine steekproefomvang (HDLSS), lijdt de Euclidische afstand aan "afstandconcentratie", waarbij de afstanden tussen punten binnen dezelfde klasse groter worden dan de afstanden tussen punten in verschillende klassen. Dit schendt de buurtstructuren en leidt tot de opkomst van "hubs", wat de prestaties van de classifier ernstig verslechtert.

Om dit aan te pakken, introduceerden Pal et al. (2016) de Mean Absolute Difference of Distances (MADD), een datagedreven semi-metriek die deze problemen in hoge dimensies succesvol omzeilt door correcte buurtstructuren te behouden op basis van locatie- en schaalverschillen. Ondanks de theoretische voordelen kampt MADD echter met een kritieke bottleneck: de computationele complexiteit. Het berekenen van MADD tussen twee punten vereist $O(nd)$ operaties (waarbij $n$ de omvang van de trainingssteekproef is en $d$ de dimensionaliteit), en het classificeren van een enkel testpunt via een Nearest Neighbor (NN) benadering vereist $O(n^2d)$ operaties. Zoals in het artikel wordt aangetoond, maakt deze kwadratische schaling MADD computationeel onhaalbaar voor grote datasets met een grote $n$ , zelfs op moderne hardware.

Methodologie
De auteurs stellen een schaalbare versie van MADD voor, genaamd MADDsc, die de computationele complexiteit aanzienlijk vermindert terwijl de statistische voordelen van de oorspronkelijke metriek behouden blijven. De methodologie bestaat uit drie kerncomponenten:

Selectie van een Representatieve Set via Determinantal Point Processes (DPP):
In plaats van de afstand te berekenen tegen de volledige trainingsset, herdefinieert MADDsc de metriek met behulp van een kleine, representatieve subset van observaties, $X^* \subset X$ . De auteurs stellen dat de theoretische scheidingseigenschappen van MADD behouden blijven als de representatieve set de diversiteit van de oorspronkelijke data vastlegt.
- Om deze set te selecteren, maken de auteurs gebruik van Determinantal Point Processes (DPP). In tegenstelling tot eenvoudige willekeurige steekproeftrekking, die intrinsieke datastructuren kan missen (vooral bij multimodale distributies), introduceren DPP's een "afstotend" effect. Door een gelijkenismatrix $L$ te construeren met behulp van een Gaussische radial basis kernel, selecteren DPP's een subset van punten die divers zijn en verspreid liggen over de datacloud, waardoor wordt gewaarborgd dat de representatieve set het landschap van de volledige trainingssteekproef vastlegt.
- De computationele kosten worden verminderd van $O(n^2d)$ naar $O(knd)$, waarbij $k$ de omvang van de representatieve set is ( $k \ll n$ ).
Incrementele Cross-Validatie voor Hyperparameterselectie:
De omvang van de representatieve set ( $k$ ) is een cruciale hyperparameter. Standaard cross-validatie zou het herhaaldelijk selecteren van DPP-steekproeven en het opnieuw berekenen van afstanden voor elke fold en kandidaat- $k$ vereisen, wat de snelheidswinst tenietdoet.
- De auteurs stellen een incrementele cross-validatie techniek voor. Door het DPP-samplingalgoritme aan te passen zodat de geselecteerde subsets genest zijn (d.w.z. $X^*(k_t) \subseteq X^*(k_{t+1})$ ), kunnen de MADDsc-waarden incrementeel worden berekend. Dit stelt het algoritme in staat de metriek bij te werken naarmate $k$ toeneemt zonder de volledige afstandmatrix opnieuw te berekenen, wat de computationele overhead van modelselectie drastisch vermindert.
Random Fourier Features (RFF) voor Massale Datasets:
Voor extreem grote datasets waar zelfs de constructie van de $n \times n$ gelijkenismatrix voor DPP onhaalbaar is (vanwege geheugen- of eigenwaardedecompositiekosten), integreren de auteurs Random Fourier Features (RFF).
- Op basis van de stelling van Bochner wordt de Gaussische kernel benaderd via een Monte Carlo-verwachting. De gelijkenismatrix $L$ wordt benaderd door $R R^T$ , waarbij $R$ een laagdimensionale feature map matrix is ( $n \times 2D$ ).
- Dit maakt het mogelijk om de eigenwaardedecompositie die vereist is voor DPP-sampling uit te voeren op een veel kleinere $2D \times 2D$ matrix (of via SVD van $R$ ), wat zowel de tijd- als de geheugencomplexiteit vermindert. Deze aanpak wordt geformaliseerd als NN-MADDsc met RFF.

Het framework wordt ook uitgebreid naar gMADDsc, een schaalbare versie van de gegeneraliseerde MADD (gMADD), die gevallen afhandelt waarin populaties verder verschillen dan alleen de eerste twee momenten (locatie en schaal).

Belangrijkste Resultaten
Uit extensieve simulatiestudies en analyses op echte data van de UCR Time Series datasets blijkt de effectiviteit van de voorgestelde methoden:

Prestaties vs. Oorspronkelijke MADD: In simulaties over diverse distributies (locatie, schaal, mengsel en heavy-tailed) bereikt NN-MADDsc foutpercentages die bijna identiek zijn aan de oorspronkelijke NN-MADD (verschillen doorgaans $\le 1\%$ ).
Computationele Efficiëntie:
- NN-MADDsc is aanzienlijk sneller dan NN-MADD. Voor een trainingsomvang van $n=16.384$ duurde NN-MADD meer dan 6,5 uur, terwijl NN-MADDsc een fractie van die tijd voltooide.
- De incrementele cross-validatie strategie vermindert de runtime verder vergeleken met standaard cross-validatie, waardoor de rekentijd met bijna de helft wordt verkort voor $n=4096$ .
- De RFF-gebaseerde aanpak biedt de meest dramatische versnelling. Voor $n=25.000$ voltooide de RFF-gebaseerde methode in minder dan 25 minuten, terwijl de standaard NN-MADDsc meer dan 15 uur duurde en de oorspronkelijke NN-MADD faalde door geheugenbeperkingen.
Vergelijking met Andere Classificatoren: NN-MADDsc presteert consequent beter dan of is gelijk aan state-of-the-art classificatoren (inclusief Random Forest, SVM's en GLMNET) in hoogdimensionale settings, met name wanneer de datadistributies verschillen in vorm of schaal. In real-world tijdreeksbenchmarks behaalde het de laagste foutpercentages in verschillende datasets (bijv. Synthetic Control Chart, Two Patterns).
Theoretische Garanties: Het paper stelt vast dat onder high-dimension, high-sample-size (HDHSS) regimes, de classificatiebeslissingen van NN-MADDsc convergeren naar die van NN-MADD met een waarschijnlijkheid die naar 1 tendeert, mits de omvang van de representatieve set proportioneel groeit ten opzichte van het logaritme van de steekproefomvang.

Betekenis en Claims
Het paper claimt de reikwijdte van MADD te verbreden, waardoor het toepasbaar wordt in big-data scenario's die gekenmerkt worden door zowel hoge dimensionaliteit als grote observatieaantallen. De primaire bijdrage is het ontkoppelen van de statistische robuustheid van MADD van de kwadratische computationele complexiteit. Door gebruik te maken van DPP's voor diversiteitsbehoudende subsampling en RFF's voor kernelbenadering, bieden de auteurs een praktische, schaalbare oplossing die de theoretische voordelen van MADD in hoogdimensionale ruimtes behoudt. Het werk claimt niet alle classificatoren te vervangen, maar positioneert MADDsc als een superieur alternatief voor afstandgebaseerde classificatie in regimes waar de Euclidische afstand faalt en traditionele MADD computationeel onhaalbaar is.