En lettere forkortet udgave af denne tekst er publiceret i Weekendavisen 2014 #27 fra d. 4. juli 2014 i sektionen Idéer, s. 12.
Algoritmer. Den 9. juli uddeles Gödelprisen for teoretisk datalogi ved en konference i København. I år går prisen til et en algoritme som blandt andet muliggør personaliseret informationssøgning. Eksistensen af den slags effektive algoritmer bestemmer, hvordan den digitale virkelighed ser ud for os.
Informationsteknologien har medført to helt gennemgribende ændringer i vores måde at tilgå information. I »gamle dage« i midten af halvfemserne var information organiseret som et bibliotek. Tjenesten Yahoo! havde kategoriseret webbens sider efter emne. Ville man finde noget om Paris, så var man nødt til at klikke sig igennem et hierarki – geografi, Europa, Frankrig, byer, Paris – ganske som at finde den rette hylde i kommunebiblioteket. Googles siderangeringsalgoritme »Pagerank« fra 1998 indebar en fundamental nytænkning af denne århundreder gamle tradition. Nu kunne man skrive »Paris« ind i et søgefelt, og straks fik vi en liste med alle websider om Paris, sorteret efter kvalitet – lidt som at gå op til bibliotekaren, mumle et enkelt ord, og lade hende gøre alt opslagsarbejdet. Kategorierne var borte og Googles algoritme blev så fundamental, at det i dag for det fleste virker utænkeligt at gennemsøge webben på nogen anden måde end ved rangeret fritekstsøgning.
Den næste ændring kom først i slutningen af nullerne: personaliserede søgeresultateter. Opslaget »Hilton Paris« betyder nemlig noget helt andet for Jürgen, en tysk turist i en europæisk storby, end for Ashley, en amerikansk teenager. Derfor forsøger søgemaskiner som Google at tilpasse den sorterede liste af svar til den individuelle bruger, baseret på de digitale spor, vi har efterladt. Brugerens alder og geografisk opholdssted er nok til at anbefale det rigtige hotel til Jürgen og den rigtige kendis til Ashley. Googles vision er at besvare spørgsmålet inden brugeren har stillet det. For at blive i biblioteksmetaforen svarer det til at gå op til bibliotekaren og få stukket en bog i hånden, før man åbner munden.
Personalisering er den informationvirkelighed, vi lever i lige nu. Google personalerer websøgninger, Amazon personaliserer boganbefalinger, Netflix film og Spotify musik. Partnerformidling har altid været personaliseret, og de store elektroniske dating sites er også selvfølgeligt med på den vogn. Personalisering har en hel række interessante potentielle konsekvenser, fx skabelsen af såkaldte potentielle Filterbobler i informationsformidling, som WA tidligere har belyst [Det hele handler om dig, WA 20, 2011].
De algoritmer, der indgår i at få personalisering til at virke, har altså direkte og mærkbare konsekvenser for, hvordan vi opfatter verden – på godt og ondt. En af dem, tærskelalgoritmen for top-k-søgninger af Ron Fagin, Amnon Lotem og Moni Naor modtager i disse dage den teoretiske datalogis fornemste udmærkelse, Gödelprisen, ved en konference i København.
Samtidigt med at algoritmerne træffer en masse valg for os og véd mere og mere om os, véd vi temmelig lidt om algoritmer. En algoritme er nu hverken kunstig intelligens, sort magi eller »hvad en programmør siger, når han ikke har lyst til at forklare, hvad der sker.« Algoritmer er problemløsningsmetoder, udtrykt så præcise, at det kan udføres af en computer – som man kan tænke på som en uendelig tålmodig, lydig og irriterende ordret tolvårig.
Inden personaliseringsbølgen fra 2010 kunne en søgetjeneste nøjes med at sortere information efter bare én parameter. En bestsellerliste kunne fx rangordne bøger efter mest solgte. Men personaliseringen åbner muligheden at rangere og kategorisere bøger efter pris, alder, antal sider, sprog, genre, osv.
Om en bestemt bog er skrevet af en dansk forfatter kan være meget relevant for fru Hansen men helt irrelevant for fru Jensen. Og fru Jensen hader måske krimier mens fru Jensen elsker dem. Personalisering er altså implementeret som en vægtning af produktets mange parametre, og denne vægtning er skræddersyet til netop fru Jensen.
Men hvordan holder nu vores bøger sorteret, når hver bruger har sin egen opfattelse af, hvad der er relevant? I princippet et det meget nemt at løse: Gennemløb alle bogtitler, beregn fru Jensens score for hver af dem, sortér resultatet efter score, og præsentér de 20 bedste resultater for hende.
Desværre tager det for lang tid.
Det skal man måske lige gentage, fordi det strider imod vores intuition: Det tager for lang tid at sortere.
Hvordan kan det være? Bliver datamater ikke hurtigere og hurtigere? Jo, det gør de skam. Den teknologiske udvikling har selvfølgeligt gjort processorhastigheder meget hurtigere siden Princeton-matematikeren John von Neumanns »ENIAC« fra slutningen af Anden Verdenskrig, som vejede 30 tons og bestod af 17468 radiorør. Men samtidigt er datamængder også blevet større og større. Maskinens hukommelse og problemernes størrelse er vokset endnu hurtigere en processorhastigheden. Vil man sætte det på en spids kan man sige, at computere bliver langsommere og langsommere i forhold til de beregningsproblemer, vi udsætter dem for. Men som en tommelfingerregel gælder “det tager en computer et sekund at berøre hele datamængden” før som nu. Den udfordring er altså et aspekt ved det vil kalder massedata, big data: at vi knapt nok har tid til at besvare endog de mest enkle spørgsmål til meget store datamængder.
Nu kunne man måske sige, at et sekund måske ikke er så voldsomt lang tid alligevel. Fru Jensen vil nok godt kunne vente, til vi har omorganiseret hele bibioteket, så det passer til netop hendes præferencer. Problemet er bare, at vi også håber, at der er flere kunder i butikken end fru Jensen; vi vil gerne servicere mere en én bruger per sekund. Helst et par millioner per sekund. Og vi vil nødigt investere i et par millioner computere til at betjene disse kunder.
Vi skal gennemføre beregning her og nu, fordi der er for mange forskellige kunder til at vi kan forberede en kopi af hele biblioteket til hver af dem. Det skulle tage en kopi af hele datamængden for hver bruger, og så meget lagerplads har vi ikke.
Det algoritmiske problem opstår altså fordi vi skal håndtere for store datamængder til at sortere alting på stående fod og for mange kunder til at sortere alting på forhånd.
Uden sådan en algoritmisk løsning til dette problem ingen personalisering. Der findes forresten rigtig mange beregningsproblemer, hvor vi er mindre heldige, og hvor det ikke er lykkedes algoritmeforskningen at finde en snedig løsning. Visse ønskværdige algoritmer findes ganske enkelt ikke. Det kan man så også bevise.
Den østrigske logikers Gödels egen forskning i 1930erne, længe inden datalogi var blevet en egen disciplin, drejede sig netop om a bevise fraværet af algoritmer for bestemte problemer.
Men det viser sig altså, at en sådan algoritme faktisk findes, nemlig tærskelalgoritmen. Den er kort og elegant, og man kan more sig med selv at komme på den eller google efter svaret på nettet. Den elegante løsning kræver en sindrig datastruktur, hvor man i forvejen har sorteret hele databasen for hver enkelt parameter for sig, samt nogle ekstra indholdsfortegnelser med krydshenvisninger mellem listerne. I disse sorterede lister kan man så nøjes med ganske få opslag. Selve algoritmen er nem at følge og let at implementere som programkode, hvorimod analysen for korrekthed og effektivitet kræver lidt mere datalogisk baggrundsviden.
Teoretisk datalogi er en matematisk disciplin, så algoritmen som forskningsresultat publiceres sammen med en stringent analyse af dens effektivitet og et formelt bevis af dens optimalitet. Tærskelalgoritmen blev opdaget og publiceret i 2001 af tre israelske og amerikanske forskere, som derfor modtager Gödelprisen i år.
Gödelprisen er en udmærkelse inden for teoretisk datalogi, så det har sikkert også været udslagsgivende, at de matematiske aspekter af resultatet opfylder matematikkens æstetiske krav til enkelhed. Selve tærskelalgoritmen kan beskrives på 10 linjer, og forfatterne bag resultatet var i sin tid alvorligt bekymrede for at få manuskriptet afvist, fordi det så for let ud. Sådan gik det dog ikke. Artiklen blev dog straks optaget på ACM Symposium on Principles of Database Systems i 2001, vandt prisen for bedste artikel, vandt symposiets Test-of-Time Award 10 år senere og får nu altså Gödelprisen.
Mange algoritmer i den datalogiske literatur er ren grundforskning og finder aldrig vej til et produkt, men tærskelalgoritmen er et godt eksempel på et af de efterhånden mange stykker teoretisk datalogi som sætter et umiddelbart præg på vores virkelighed, efterhånden som den virkelighed bliver mere og mere algoritmisk. Den vælger vores næste bog, vores næste nyhed og måske vores næste parforhold.
Gödelprisen uddeles årligt siden 1993 for fremragende resultater i teoretisk datalogi. Prisoverrækkelsen finder sted på skift mellem Nordamerika og Europa.
Fagin, Naor, Lotem, Optimal aggregation algorithms for middleware, J. Comput. Syst. Sc. 66 (2003) 614–656. PDF
Summary
This is a Danish popular science introduction to the threshold algorithm of Fagin, Lotem, and Naor, which received the Gödel prize at ICALP 2014.
A shortened form of this manuscript appeared in the Danish weekly broadsheet Weekendavisen.
Thore Husfeldt 