Dansk-amerikansk makkerpar finder løsningen på gammelt datakomprimeringsproblem

Data er blevet det nye guld, der er grundlag for mange firmaers eksistens og vækstmuligheder.

For at kunne udnytte de enorme datamængder, skal man dog hurtigt og effektivt kunne søge i data og for gøre dette, er det nødvendigt at komprimere data på en måde, der bevarer de egenskaber, der findes i rådata.

En af de matematiske sætninger, som i dag ligger til grund for reduktion af data i mange dimensioner til data i færre dimensioner, er det såkaldte Johnson-Lindenstrauss lemma fra 1984.

31-årige Kasper Green Larsen fra Aarhus Universitet og hans nogenlunde jævnaldrende kollega Jelani Nelson fra Harvard University i USA har nu vist, at dette lemma ikke kun beskriver en effektiv måde til at reducere antallet af dimensioner i data. Det er den optimale måde hertil.

De har nylig præsenteret deres videnskabelige artikel herfor på en konference i USA arrangeret af IEEE Computer Society.

Af pressemeddelelsen, som er udsendt i den forbindelse fra Harvard University, fremgår det, at dette bevis har vakt opsigt. Matematikprofessor Noga Alon fra Tel Aviv University i Israel siger eksempelvis:

»Johnson-Lindenstrauss lemmaet er et grundlæggende resultat i højdimensionel geometri, men der var et irriterende hul i vores forståelse af, hvor meget man kan reducere dimensionen af en datamængde uden at forvrænge geometrien for meget. Jelani Nelson og Kasper Green Larsen har løst problemet.«

Anvendes til præprocessering

Johnson-Lindenstrauss lemmaet ligger i dag til grund for præprocessering af store datamængder, før de viderebehandles med algoritmiske metoder.

Det har betydning for udvikling af bl.a. spam-filtre, men har også en lang række andre anvendelser inden for eksempelvis computational biology.

Når et fundamentalt resultat inden for geometri har betydning inden for datalogi og datareduktion, er det fordi, data i mange tilfælde med fordel kan udtrykkes som en vektor i flere dimensioner.

Det gælder eksempelvis, når man skal analysere ord og indhold i en email. Som det fremgår af pressemeddelelsen fra Harvard University kan en email med 1000 ord resultere i en vektor med flere millioner dimensioner.

Det kan være besværligt i den videre analyse af håndtere så mange dimensioner.

Fra geometri til datalogi

Johnson-Lindenstrauss lemmaet siger helt generelt, at det er muligt at finde afbildninger, der kan reducere antallet af dimensioner ganske betragteligt, hvis man tillader, at afstandene mellem vektorerne efter afbildningen kun tilnærmelsesvis er den samme som før afbildningen.

Har man eksempelvis n punkter (eller vektorer) i d--dimensionalt rum, så er det muligt at finde afbildning givet ved en funktion f til et m-dimensionalt rum (hvor m er mindre end d), således, at det gælder:

[latex] (1-\epsilon) \parallel x-y \parallel ^2 \leq \parallel f(x) - f(y) \parallel ^2 \leq (1+\epsilon) \parallel x-y \parallel ^2 [/latex]

Johnson-Lindenstrauss lemmaet siger, at m mindst skal i størrelsesorden lnn/?², hvor ln er den naturlige logaritmefunktion. Det vil i mange tilfælde være langt mindre end den oprindelige dimension d.

Hvis man altså tillader en lille fejl eller unøjagtighed givet ved ?, kan man reducere antallet af dimensioner ganske betragteligt og lette den videre analyse af data.

Men kan man gøre det endnu bedre end Johnson-Lindenstrauss lemmaet? Det har matematikerne længe funderet over. Og nu har Jelani Nelson og Kasper Green Larsen som nævnt givet svaret: »Nej det kan man ikke«.

Dermed har de forbedret det resultat, som føromtalte Noga Alon var kommet frem til, at man mindst skulle bruge lnn/(?²ln(1/?)) dimensioner. Kasper Green Larsen og Jelani Nelson har nu fjernet ln(1/?) faktoren.

Kasper Green Larsen udtrykker selv betydningen af den nye indsigt på denne måde:

»Vi har nu en fuld matematisk forståelse af, hvor meget højdimensionel data kan komprimeres. Udover at dataloger ikke mere skal bruge tid på at forske i metoder til at komprimere data, betyder det også, at vi kan sætte alle kræfter ind på at gøre komprimeringsprocessen hurtigere. Datamængderne bliver kun større i fremtiden, så hurtigere algoritmer er essentielle«.

Emner : Matematik