Dansk forsker skal redde søgemaskinerne

Rasmus Pagh var 9-10 år gammel, da problemet med søgninger første gang åbenbarede sig for ham. Drengen, der senere skulle blive professor på IT-Universitetet i København, havde lige fået sin første computer med 48 KB ram og lånte bøger på biblioteket om programmering.

Han havde dengang et klovnepuslespil, som han tænkte, at computeren måtte kunne løse. Han programmerede derfor et program, der løb igennem alle muligheder for, hvordan brikkerne kunne ligge.

»Og det kørte, og det kørte, og det kørte og blev aldrig færdigt,« fortæller Rasmus Pagh, der kalder episoden en 'aha-oplevelse': Den enorme mængde af mulige kombinationer af puslespilsbrikkerne viste ham, at søgninger, hvor man går al data igennem, bliver så tunge, at man ikke har tålmodighed til at vente på søgeresultatet. Og den førte ham samtidig i retning mod forskning, der prøver at finde smartere måder at gøre netop dét på.

Alternativet til, at søgemaskinen gennemgår hvert eneste stykke data i databasen, er i dag ofte, at søgningerne er baseret på tilfældige stikprøver. De søgemetoder, vi finder på Google, Facebook, i forsikringsselskabernes databaser og i virksomhedernes marketingsafdelinger, fungerer langt fra så godt, som de kunne se ud på overfladen. Der er nemlig ingen garantier for, at man finder alt det, man søgte efter i dataens dyb.

Det skal Rasmus Pagh nu forsøge at lave om på. Han har vakt international opsigt med sin forskning i Big Data – de meget store datamængder, som forskere, virksomheder og myndigheder har fået til rådighed de seneste år - og i de særlige matematiske algoritmer, der kan bruges til at søge i de store mængder data.

Bedre metoder til 'bløde søgninger'

Han skal nu stå i spidsen for et kæmpe forskningsprojekt, efter at han i januar blev tildelt et 'Consolidator Grant' fra Det Europæiske Forskningsråd. Uddannelses- og Forskningsministeriet kalder bevillingen for forskningens svar på en Oscar, og de 1,9 million euro skal finansiere forskningen de kommende fem år.

»Det er lidt et højrisikospil, for vi forsøger at gøre noget, som en del andre smarte mennesker har prøvet før. Men vi tror måske, at vi har de ekstra ledetråde, der gør, at vi kan komme igennem med noget,« siger Rasmus Pagh.

Projektet går ud på at finde nye og bedre metoder til såkaldte 'bløde søgninger', også kaldet 'similarity search'. Altså søgninger, hvor man står med én ting og gerne vil finde noget, der ligner - men uden at vide hvordan det, der ligner, ser ud.

Samtidig vil Rasmus Pagh undersøge matematisk, om de metoder, som mange søgemaskiner bruger i praksis, virker. Disse metoder er bygget på tommelfingerregler og ad hoc-løsninger, men er uden teoretisk grundlag. Rasmus Paghs teori er, at de ikke altid virker ordentligt.

Søgning uden garantier

En blød søgning kunne for eksempel være med udgangspunkt i et billede, forklarer Rasmus Pagh. Man har et foto af en løve og vil gerne finde andre billeder, der ligner, men uden at vide, om fotosamlingen indeholder andre løver, andre kattedyr eller måske et løvemaleri.

Det er langt fra sikkert, at søgningen finder alle resultater, der ligner løven på billedet, for metoderne, man bruger i dag, er baseret på stikprøver, hvor man ikke kender kvaliteten af svarene på søgningen – og skal man have sikre svar, kræver det meget store computerressourcer.

»Søgningerne, vi har i dag, er bygget på, at man har noget, der virker nogenlunde. Men det er efter bedste evne – der er ikke nogen garanti for, at man rent faktisk modtager resultatet på søgningen, hvis der er noget, der ligner,« siger Rasmus Pagh.

Selvom man får nogle resultater, kan man altså ikke være sikker på at finde alt, der er relevant.

»En løve er ikke det mest kritiske eksempel, for sådan en søgning gør ofte et fornuftigt job og returnerer et resultat.«

»Men tænker man på en læge, der søger på sygdomshistorier, der ligner, og han misser en behandling, som reddede en patient et andet sted, så er man nede i noget, hvor man gerne vil vide med sikkerhed, at softwaren finder det, hvis der er noget at finde. Det er ikke særligt velforstået, hvordan man gør det på bedste vis,« siger Rasmus Pagh.

Sandsynligt at være uheldig

Med de nuværende metoder omdanner computeren først vores løvebillede til elektroniske 1'er og 0'er. Til ja'er og nej'er. Man tager en stikprøve af forskellige parametre: Er der en hat? Nej. Er det et dyr? Ja.

Derefter finder computeren andre billeder, hvor der kan svares ja og nej til de samme spørgsmål. Men hvilke parametre, der bliver undersøgt, er tilfældigt udvalgt, og det er derfor tilfældigt, om computeren går på jagt efter andre billeder med dyr eller andre billeder uden hatte.

»Hvis man er heldig, bliver de rigtige parametre valgt. Men der er rimelig stor sandsynlighed for at være uheldig. Så gentager man nogle hundrede gange med tilfældige stikprøver, og så er der rimelig stor sandsynlighed for at være heldig,« siger Rasmus Pagh.

»Det er de bedste algoritmer, der findes i dag – og de er en lille smule bedre end at kigge alt igennem,« siger han.

Det bliver sværere at bruge gode metoder

Men eftersom den metode – kaldet locality sensitive hashing – også kræver store computerressourcer på samme måde som at gå al data igennem, bruger man ofte metoder, hvor man ikke matematisk kender kvaliteten af søgeresultatet.

Og det vil i fremtiden blive sværere og sværere at bruge de gode metoder.

Mængden af data vokser i eksploderende tempo – hvert andet år fordobles den ifølge analyseinstituttet IDC. Selvom computerkraften også vokser, så vokser evnen til at lave avancerede beregninger ikke nær så hurtigt som mængden af data.

Søgninger, der i dag stadig kan gå alt igennem, vil derfor fremover være prisgivet de søgemetoder, der – indtil videre – er statistisk usikre.

»En del af motivationen for forskningsprojektet er, at man fortsat skal kunne bruge bløde søgninger i fremtiden. Det andet er at beskrive de nuværende systemer, der har nogle tommelfingerregler, der tit virker. Men nogle gange virker de ikke, og det er ikke altid helt klart, hvornår de ikke virker,« siger Rasmus Pagh.

Søgemaskinernes forbandelse

Men når Rasmus Pagh og hans team tager udfordringen op med at finde metoder, der er hurtigere end at kigge alt igennem, men statistisk sikrere end de nuværende stikprøvemetoder, så er det uden sikkerhed for resultater.

»Man taler om 'the Curse of Dimensionality' – altså forbandelsen ved høj dimension. Der er lidt Indiana Jones over projektet. Vi skal finde måder at komme rundt om den her forbandelse, men det er ikke sikkert, at man kan rydde den fuldstændigt af vejen,« siger Rasmus Pagh.

I forsøget på at gøre op med forbandelsen vil han blandt andet se på bedre måder at organisere computernetværk, der kommunikerer med hinanden om søgningerne.

Og så vil han forsøge at bygge videre på en teori fra Stanford-forskeren Gregory Valiant, der groft sagt går ud på, at det kan være en fordel at søge efter noget andet, end det man leder efter.

»Det virker ikke helt intuitivt,« erkender Rasmus Pagh, »Projektet går ud på at skabe noget, vi ikke er sikre på kan lade sig gøre.«

»Efter projektet har vi i den bedste verden nogle bedre metoder, men ellers har vi en bedre forståelse af, hvad der kan lade sig gøre, og hvad der ikke kan lade sig gøre.«

Harvard-professor: Forskningen er vigtig

Lykkes det at forbedre metoderne inden for bløde søgninger, vil det være et vigtigt skridt fremad, mener Michael Mitzenmacher, der er professor i datalogi på Harvard University og forsker i algoritmer.

I en email til Videnskab.dk kalder han Rasmus Pagh en 'verdenskendt leder inden for algoritmiske metoder til dataudtrækning'.

»Når vi øger antallet af områder, hvor vi vil have bløde søgninger til at fungere, er flere teknikker, analyser og øget forståelse nødvendigt. Dette forskningsprojekt fokuserer på dette spændende område og lover nye fremskridt, som vil føre til bedre og mere kraftfulde metoder, der vil gøre os i stand til at løse en bredere række af problemer,« skriver Michael Mitzenmacher.

Også Gerth Stølting Brodal, lektor på Institut for Datalogi på Aarhus Universitet, mener, at fremskridt på området er vigtige. Han kalder søgninger med mange parametre – såkaldte højdimensionelle søgninger – notorisk svære.

»Lige nu har vi nogle metoder, der virker i praksis, men vi har ikke bevis for, hvorfor de virker. Det er vigtigt matematisk at finde ud af hvorfor,« siger han. Som Rasmus Pagh også selv erkender, mener Gerth Stølting Brodal, at det kan blive en udfordring at nå det helt store gennembrud.

»Han vil finde nye metoder, og det er et meget ambitiøst mål at have. Om han får det løst, ved jeg ikke. Sådan er det med grundforskning,« slutter Gerth Stølting Brodal.