Tom og Jerry inspirerer til hurtigere computere

Mens de fleste af os nok bare forventer, at vores computere fungerer af sig selv på magisk vis, når vi tænder dem, er der en særlig gruppe, der skal sørge for, at det rent faktisk sker: Datalogerne.

De står bare med en udfordring:

Mængden af data, der skabes og skal behandles, vokser hurtigere end computerkraften. Samtidig med at computere hele tiden bliver bedre, og den rå regnekraft større, bliver de altså (groft sagt) også langsommere og langsommere til at løse de opgaver, vi stiller dem - medmindre datalogi-forskerne opfinder nye algoritmer, der er hurtigere og bedre til at udnytte regnekraften end de gamle.

Her kommer den vietnamesiske datalogi-forsker Ninh Pham, der er postdoc på IT-Universitetet i København, med en prisvindende nyskabelse.

Han har netop forsvaret sin ph.d.-afhandling, der handler om algoritmer til at foretage 'similarity search', en søgemetode, der sammenligner datasæt – noget computere har afgørende brug for at kunne, for at finde ud af om to sæt data minder om hinanden eller ej.

»Problemet med 'similarity search' er på mange måder et helt centralt problem inden for datalogien. Hvis man bedre kan estimere, hvor ens to dokumenter er, kan man spare både meget tid og penge,« siger Ninh Pham.

Den hurtigste algoritme til at sammenligne data

Den ene af algoritmerne, som Ninh Pham har døbt 'Odd Sketch', vakte opmærksomhed tidligere på året, da Ninh Pham skrev en videnskabelig artikel om algoritmen sammen med den danske datalogi-professor Rasmus Pagh, også fra IT-Universitetet i København, og Harvard-professoren Michael Mitzenmacher.

»Vores algoritme er den hurtigste til at sammenligne dokumenter, hvis dokumenterne minder meget om hinanden, og den bruger mindre plads end den nuværende metode til at gøre det,« siger Ninh Pham.

Artiklen vandt 'best paper award' på den prestigefyldte WWW-konference i Seoul i april.

»Det er måske sådan noget, der sker én gang i en akademisk karriere,« siger Ninh Pham, »så selvfølgelig var det vigtigt for os. Det havde vi ikke regnet med.«

Algoritmnerne skal kun søge i et udpluk

Opgaven med at sammenligne sæt af data opstår næsten konstant for computere.

Når vi køber en bog på nettet, sammenligner netbutikken os med andre besøgende, for at finde de kunder der minder om os, så den kan anbefale os bøger, de også har købt.

Skal en underviser tjekke opgaver for plagiater, bliver opgaven sammenlignet med alle de opgaver, der er skrevet tidligere for at se, om dele af teksten er ens. Når vi søger på Google, sammenligner søgemaskinen vores søgeord med sin database.

»Sådan som mængden af data udvikler sig, skal Google indeksere milliarder af hjemmesider og får hver eneste måned milliarder af forespørgsler. Så spørgsmålet er, hvordan man kan nå at svare på forespørgslerne fra alle brugere,« siger Ninh Pham.

Når datamængderne er blevet så store og er stigende, er det nemlig ikke længere muligt for Google at sammenligne ens søgeord med alt, der nogensinde er lagt på nettet, eller for bognetbutikken at sammenligne den eksisterende kunde med alle tidligere kunder i databasen. Kunden ville være færdig med sit køb, og Google-søgeren ville have spurgt sin sidemand i stedet, før computeren var færdig med at finde svaret frem.

Derfor er forskerne nødt til at lave algoritmer, der kun søger i et udpluk af datahavet – samtidig med, at de skal være statistisk sikre på, at algoritmerne alligevel finder det, man leder efter.

»Fordi 'similarity search' er et så centralt problem, er der mange, der arbejder på at løse det. Hvis man forbedrer metoderne bare en lille smule, kan man spare mange ressourcer, når man skal bruge dem,« siger Ninh Pham.

Hjælp fra Harvard-datalog

Odd Sketch-metoden opstod i sammenarbejde mellem Ninh Pham og hans ph.d.-vejleder på IT-Universitetet i København, professor Rasmus Pagh. Sammen fik de algoritmen til at virke i praksis.

Men et udbredt problem blandt computerprogrammører i it-virksomhederne er, at de ikke har forskernes matematiske og statistiske beviser for, at en algoritme altid vil virke. Derfor benytter de sig ofte af algoritmer, der af og til fejler på kritiske tidspunkter.

Det teoretiske bevis var derfor vigtigt for Pham og Pagh, der kontaktede Harvard-datalogiprofessoren Michael Mitzenmacher.

»Han er verdenskendt inden for datalogien og arbejder meget tæt på vores felt, så vi involverede ham i at sikre, at algoritmen ikke kun virker godt i praksis, men at der også er teoretisk bevis for det,« fortæller Ninh Pham.

På jagt efter Tom og Jerry-fans

For at give et eksempel på, hvordan Odd Sketch-algoritmen fungerer og give indblik i computernes indmad, griber Ninh Pham fat i film-streamingtjenesten Netflix.

Et uforudset problem ved at bringe det konkrete eksempel op er, at Videnskab.dk straks spørger, hvad Ninh Pham selv ser.

Der er stille lidt i den anden ende af telefonen.

»Tom og Jerry,« udbryder Ninh Pham så, griner og skynder sig at forklare: »Når man arbejder med forskning, er hjernen på arbejde hele tiden, så når man kommer hjem og skal koble den af, er tegnefilm en af de bedste måder at gøre det på.«

Ud over at Netflix giver mulighed for at streame film og tv-serier, kommer tjenesten også med anbefalinger til, hvad brugerne ellers kunne være interesserede i at se.

Når Ninh Pham går på Netflix, dykker tjenesten altså ned i databasen af millioner af kunder for at finde ud af, hvad andre Tom og Jerry-fans har set, så Netflix kan anbefale det til Ninh Pham.

10-50 film bliver tilfældigt udvalgt

Ninh Pham fortæller, at Odd Sketch-algoritmen fungerer i to stadier.

1. Først foretager den en stikprøve af den næsten uendelige datamængde.
   
2. Derefter koger den filmtitlerne fra stikprøven ned til en ultrakort række af tal, som algoritmen kan sammenligne meget hurtigt.

Første skridt er at benytte sig af det, der hedder en minwise hashing; en metode der har været brugt, siden den var en del af AltaVista, der i slut-90'erne var en af nettets første søgemaskiner.

Metoden udvælger tilfældigt mellem 10 og 50 elementer at se på. I stedet for at tjekke, om Ninh Pham og hver eneste anden kunde deler interesse i samtlige film, der nogensinde er udgivet, nøjes man altså med at se på 10-50 film – der bliver tilfældigt udvalgt.

Som en date i biografen

Hvis man ikke har noget til fælles, antager man, at de to brugere ikke minder om hinanden.

Det er lidt ligesom, hvis du skal på en første date: Hvis du siger din mening om 10 film, og han/hun ikke er enig i noget som helst af det, er det nok en dårlig idé at gå i biografen. Og hvis I ikke er enige om noget som helst efter at være 50 film igennem, så er der ikke meget håb for et match – selvom det kun er et estimat baseret på et udvalg, og I ikke har talt alle film igennem.

»Antallet, du vælger, vil selvfølgelig påvirke kvaliteten. Jo flere du tager med, jo sikrere bliver dit estimat,« siger Ninh Pham. Hvis man nøjes med at tjekke 10 film, vil algoritmen selvfølgelig kunne nå alle brugere igennem hurtigere, mens man statistisk er mere sikker på, at man ikke tilfældigvis kun har kigget på franske filmklassikere og er gået helt glip af tegnefilm med katte og mus, hvis tallet er højere.

Hjælp fra en gammel botaniker

For at sammenligne de film, som forskellige brugere ser og kan lide, trækker Ninh Pham på botanikeren Paul Jaccard.

Han var professor på universitetet ETH Zürich og offentliggjorde i 1901 en metode til at sammenligne flora-forekomster i Alperne – en metode, der i dag har bevæget sig sig væk fra blomster og ind i computere og er blevet en grundbestanddel i, hvordan computere fungerer, når de sammenligner data.

Kort sagt tog Jaccard to kvadrater på Alpernes bjergsider og optalte, hvor mange plantearter de to kvadrater havde til fælles, og hvor mange arter der var unikke i hvert kvadrat.

Ved at dividere de fælles arter med det samlede antal arter fik han en koefficient, og jo højere tallet var, jo mere mindede de to felter om hinanden. Det samme gør Odd Sketch-algoritmen, når den sammenligner data.

»Der findes mange måder at måle, hvor ens to ting er, men vi valgte Jaccard-indekset, fordi det i forvejen er meget udbredt at bruge blandt algoritmedesignere, når de skal sammenligne noget,« siger Ninh Pham.

Kaster bolde i spande

Med de film, som minwise-hashing-funktionen har udvalgt, kunne man sagtens sammenligne to brugere og udregne Jaccard-koefficienten.

Men når det er en beregning, der skal foretages millioner af gange, tæller hver en lille optimering – algoritmen laver derfor lange filmtitler om til computeres grundbestanddel: 1'er og 0'er.

Ninh Pham sammenligner det med at have en række spande, som man smider bolde i.

»Hvis du har et antal bolde og smider dem i forskellige spande, så vil nogle spande indeholde et ulige antal bolde, andre et lige antal. Hvis der er et lige antal i en spand gemmer vi et 0, mens vi gemmer 1, hvis tallet er ulige,« siger Ninh Pham. Metoden med at tælle ulige ('odd' på engelsk) eller lige er også det, der har lagt navn til algoritmen.

For eksempel kunne der være en spand med tegnefilm, en spand med gysere og en til de franske filmklassikere. Før algoritmen kører, ville talrækken, der gemmer oplysninger om spandene, hedde 0-0-0.

Når algoritmen har set, at Ninh Pham ser Tom og Jerry, ville en bold så lande i tegnefilmspanden og skifte de gemte tal til 1-0-0. Rækken af tal er derefter meget hurtigere at sammenligne, end hvis algoritmen skulle se på lange filmtitler.

Smartere end tidligere algoritmer

Men det er med en særlig egenskab, at Odd Sketch-algoritmen for alvor rykker fra de eksisterende algoritmer, der hidtil har været til rådighed for algoritmedesignerne.

Jo færre 1'er og 0'er, algoritmen skal sammenligne, jo hurtigere kan den gøre det.

Når Odd Sketch-algoritmen skal sammenligne to talrækker, kan den nøjes med at se på, hvor mange steder de er forskellige; altså hvor der er et lige antal bolde i den ene talrække og et ulige antal i den anden.

Når to talrækker minder om hinanden, ser algoritmen kun meget få forskelle og kan derfor ifølge Ninh Pham gøre det hurtigere, end det hidtil har været muligt.

»Vores algoritme bruger mindre og mindre plads, jo mere sættene af data ligner hinanden. De metoder, vi havde før, kunne ikke tilpasse sig – de gemte alt data, ikke kun forskellen,« siger Ninh Pham.

Reducerer beregningstiden bemærkelsesværdigt

Ira Assent er lektor på Institut for Datalogi på Aarhus Universitet og forsker i algoritmer.

Hun er imponeret over Ninh Phams Odd Sketch-algoritme og dens effektivitet og er enig i, at algoritmer, der kan sammenligne datasæt, er et vigtigt forskningsfelt.

»Man kan sige, at de er en basal byggesten, når man skal finde noget. Når vi skal søge i store datasamlinger, som mange er interesserede i at kunne, har vi brug for meget effektive algoritmer for at holde responstiden nede,« siger Ira Assent.

Hun fortæller ligesom Ninh Pham, at algoritmen er betydeligt hurtigere, end hvad der hidtil har været muligt, men påpeger også, at der med hastigheden går en smule tabt.

»Der er et lille trade-off ved den her teknik, fordi man opnår den høje grad af effektivitet ved at reducere præcisionen en smule. Men han (Ninh Pham, red.) demonstrerer samtidig, at det ikke er noget stort tab,« siger Ira Assent.

»Hans algoritme reducerer beregningstiden bemærkelsesværdigt i forhold til de algoritmer, vi havde, før han gik i gang med sit arbejde – det er her, jeg ser det store fremskridt,« siger Ira Assent.