GOOZZLES VIA PUZZELS GOOGLE LEREN
Goozzles: Puzzles teaching you Google
Beste bezoeker van Lowlands, Welkom in de wiskundetent, en in het bijzonder bij de UvA-workshop over de PageRank van Google. Met behulp van dit boekje willen we je een wiskundig getinte uitleg geven over de werking van de zoekmachine Google. Google rangschikt zijn zoekresultaten aan de hand van het belang van deze bladzijde, genaamd de PageRank. Hoe deze PageRank in 1989 door Larry Page en Sergey Brin werd bepaald leggen we uit aan de hand van een paar Google-puzzles, Goozzles genaamd. Wiskundige voorkennis is niet vereist. Veel plezier!
Jan Brandts Universiteit van Amsterdam http://staff.science.uva.nl/∼ brandts 1
2
Het woord Googol werd in 1920 bedacht door de 9-jarige Milton Sirotta voor het getal 10100 , een ´e´en met honderd nullen.
1. De PageRank vergelijking van Google Een belangrijk onderdeel van Google is de PageRank vergelijking. Dit is de E = mc2 van het world wide web, en ziet er in wiskundige symbolen als volgt uit:
π ∗ = π ∗ (αS + (1 − α)E) De uitkomst π ∗ van deze vergelijking is een rij van rapportcijfers voor alle acht miljard internet bladzijdes. Toepassing. Als je Google gebruikt om te zoeken naar een bepaalde term, worden deze rapportcijfers gebruikt om de resultaten in volgorde van belangrijkheid weer te geven. Het kost maar liefst drie dagen om deze acht miljard rapportcijfers uit te rekenen met behulp van grote hoeveelheden aan elkaar geschakelde supercomputers. Dat is erg duur, en dus doet Google dit maar ´e´en keer per maand. De oplossing π ∗ van de PageRank vergelijking stemt vaak verrassend goed overeen met wat mensen echt belangrijk vinden. In dit boekje proberen we daarom in lekentaal uit te leggen waarop deze vergelijking is gebaseerd. 3
Google wordt soms aangeklaagd door bedrijven die vinden dat hun PageRank te laag is. Ze verdedigen zich dan door te stellen dat de PageRank slechts hun mening voorstelt.
2. Een raadsel met kabouters en een goede fee Stel, er zijn vijf kabouters die we even B1 , B2 , B3 , B4 en B5 noemen. Ieder van deze kabouters heeft vrienden voor wie hij alles over heeft. In onderstaand plaatje kan je zien wie een vriend van wie is: de pijl van B2 naar B1 betekent dat B1 door B2 als vriend wordt beschouwd. De kabouters wijzen dus in Figuur 1 met pijlen hun vrienden aan.
B2
B3
B1
B4
B5
Figuur 1. Niet-wederzijdse vriendschapsrelaties. 4
Behalve kabouters is er ook een goede fee, in het bezit van enorme hoeveelheden knikkers, die ze graag aan de kabouters wil uitdelen. Er is echter een probleem: zodra een kabouter knikkers krijgt, zal hij ze eerlijk verdelen over zijn vrienden. Zo zitten kabouters nu eenmaal in elkaar.
Figuur 2. Typische Lowlands fee met knikkers. De fee besluit daarom elke kabouter een zodanig aantal knikkers te geven (minstens ´e´en), dat nadat iedere kabouter zijn knikkers heeft verdeeld over zijn vrienden, ze allemaal weer net zoveel knikkers hadden als erv´o´or. Maar hoe kan ze dit doen? Omdat dit niet gemakkelijk even snel uit te leggen is, komen we er later op terug. 5
PageRank wordt ook te koop aangeboden. Bedrijven zorgen dan tegen betaling voor links van hoog genoteerde pagina’s naar de jouwe.
3. Verband tussen raadsel en PageRank Het world wide web kan net als het vrienden-netwerk van de kabouters gezien worden als items met pijlen ertussen. Een pijl van B1 naar B2 geeft dan aan dat bladzijde B1 een hyperlink heeft waarmee je naar B2 kunt surfen.
Figuur 3. Een web-site met hyperlinks. De hoeveelheid knikkers waarmee het raadsel is opgelost, komt overeen met het belang van de web-bladzijde. In die situatie heeft een kabouter veel knikkers als: • hij vrienden heeft met veel knikkers, • die vrienden niet veel andere vrienden hebben. 6
Dit komt overeen met de heuristiek die Page en Brin in hun PageRank model tot uitdrukking wilden laten komen, namelijk, een web-bladzijde is belangrijk als: • er naar verwezen wordt door belangrijke bladzijdes, • die bladzijdes niet naar veel andere bladzijdes verwijzen. Oftewel, je bent goed af als Koningin Beatrix op haar webbladzijde naar de jouwe verwijst, maar al een stuk minder goed als ze naar al haar onderdanen blijkt te verwijzen!
4. Eenvoudigere versies van het raadsel Hieronder volgen drie gemakkelijkere opgaven dan die in Figuur 1 om mee te oefenen. Opgave 1. Bepaal de zgn. evenwichts-verdeling die, na het verdelen van de knikkers volgens de pijlen, dezelfde knikker-verdeling oplevert.
B1
B2
Figuur 4. Eenvoudigste versie van het raadsel. Controleer dat als je een oplossing hebt gevonden, dit niet de enige oplossing is: als je alle kabouters tweemaal zoveel knikkers had gegeven, had dit ook gewerkt. Sterker nog, ieder veelvoud van een oplossing is weer een oplossing! 7
Opgave 2. Bepaal de evenwichts-verdeling van elk van de volgende twee configuraties: B2
B2
B1
B1
B3
B3
Figuur 5. Eenvoudiger en wat moeilijker raadsel. Een alternatieve grafische voostelling van dezelfde twee raadsels als in Figuur 5 zie je rechts in Figuur 6. Hierbij is het idee als volgt. • Plaats knikkers in bovenste drie vakjes, • Verdeel ze eerlijk over de lege vakjes er verticaal onder, • Verplaats ze horizontaal naar de rechter drie vakjes. Als de hoeveelheden knikkers in de rechtervakjes nu hetzelfde zijn als waarmee je bovenin begon, heb je de gevraagde evenwichts-verdelingen gevonden. 8
Opgave 3. Opgave 2 als Goozzle (Google puzzle).
1
2
3
1
2
1 2 3
3
1 2 3
Figuur 6. Figuur 5 in een ander jasje. 9
Opgave 4. Los de volgende Goozzle op. Om je op weg te helpen hebben we ´e´en van de drie gezochte getallen al ingevuld!
1
B2
B1
2
B3
3
4
1 2 3
Figuur 7. Deels ingevulde Goozzle. Sommige mensen willen liever niet geholpen worden bij het puzzelen, en hadden de 4 in bovenstaande opgave liever niet kado gekregen. Toch is het niet echt een kado: we hadden immers al gezien dat veelvouden van een oplossing, ook weer oplossingen zijn. Er is dan ook een veelvoud dat inderdaad een 4 op die positie heeft. Mocht dit tijdens het oplossen ergens tot gebroken knikkers -breuken dusleiden, is dat niet erg: na afloop vermenigvuldigen we dan alles met een getal zodanig dat alle breuken verdwijnen. 10
Ongeveer vier vijfde van de documenten in het World Wide Web bevat geen hyperlinks. Denk hierbij aan jpg-, gif-, en pdf-bestanden. Dergelijke documenten heten dangling nodes.
5. Onvolkomenheden in het model De voorgaande Goozzles hebben allemaal een oplossing. Dit is echter niet altijd het geval, zoals blijkt uit het volgende voorbeeld.
1
B1
B2
2
B3
3
1 2 3
Figuur 8. Onoplosbare Goozzle. In dit voorbeeld krijgt kabouter B3 knikkers van B1 en B2 , maar geeft zelf niets weg. Hij zal dus altijd meer bezitten dan ervoor, tenzij B1 en B2 geen knikkers hadden. Maar, 11
de fee gaf iedere kabouter minstens ´e´en knikker! Er is dus geen oplossing van deze Goozzle. Page en Brin argumenteren dat als een surfer in een dangling node aankomt, hij bij gebrek aan hyperlinks een willekeurig nieuw web-adres in de browserbalk zal intikken. In een plaatje komt dit erop neer dat je vanuit een dangling node pijlen trekt naar ieder van de ander bladzijden, inclusief de dangling node zelf, ondanks dat deze links dus eigenlijk geen van alle echt bestaan. Het reizen naar een andere webpagina zonder daarbij een hyperlink te volgen wordt teleportatie genoemd. Opgave 5. Los de volgende Goozzle op:
1
B1
B2 B3
2
3
1 2 3
Figuur 9. Goozzle uit Figuur 8 inclusief teleportatie. 12
Reden om ook een pijl te trekken naar de dangling node zelf, is dat ieder van de drie bladzijden B1 , B2 , B3 evenveel profiteert van de PageRank die B3 uiteindelijk krijgt. Geen van de bladzijden wordt dus bevoordeeld in deze behandeling van dangling nodes. Ondanks de heuristisch verantwoorde aanpak van dangling nodes zijn nog niet alle problemen de wereld uit. Bijvoorbeeld, het world wide web zou kunnen bestaan uit meerdere groepen van bladzijdes die onderling geen links hebben. Bladzijdes uit verschillende groepen kunnen dan niet eerlijk met elkaar worden vergeleken, omdat de hoeveelheid knikkers binnen iedere groep met een willekeurig getal vermenigvuldigd kan worden.
6. Uiteindelijke basismodel: meer teleportatie Brin en Page merkten terecht op, dat niet alleen als een surfer in een dangling node aankomt, hij een nieuw webadres in de browserbalk kan intikken. Hij doet dit ook op andere momenten. Vraag is wanneer, en hoe vaak. De α-factor. Een surfer zal een deel α (met α een getal tussen de nul en ´e´en) van de tijd hyperlinks volgen, en een deel 1 − α een nieuw adres in de browserbalk intikken. Het uiteindelijke model bestaat uit een combinatie van het model dat we hadden na het repareren van de problemen 13
die door dangling nodes worden veroorzaakt, en het volledige teleportatie-model. Dit laatste model gaat er (onterecht) vanuit dat er van iedere bladzijde een link is naar iedere andere bladzijde, inclusief zichzelf. Hoe wordt deze combinatie in de praktijk gemaakt? Door te stellen dat een deel α van de knikkers via de pijlen moet lopen van het oorspronkelijke model, en het resterende deel volgens de pijlen van het volledige teleportatie model.
1
3 20 1
2
2 3
3 1
17 20 2
3
1 2 3
Figuur 10: Goozzle met teleportatie en α-factor. Middels wiskundig speurwerk valt te beredeneren dat Google in hun model de waarde α = 0.85 = 17 20 gebruikt. Het 14
linkerdeel van de Goozzle in Figuur 10 is het teleportatieblok; het 3/20-e deel van de knikers dat hierin belandt wordt gelijkelijk verdeeld over alle andere bladzijden. We zien dat het overeenkomstige kabouter-raadsel nu wel heel erg ingewikkeld kan worden. De vraag is nu dus hoe de fee de kabouters knikkers kan geven zodanig, dat als 85% van de knikkers via het rechterblok in Figuur 10 wordt verdeeld, en 15% van de knikkers volgens het linkerblok, de situatie weer is zoals tevoren. En voor het echte world wide web dan ook nog eens met zo’n acht miljard kabouters in plaats van de drie die we hier bekijken. Dit verklaart waarom er grote aantallen aan elkaar gekoppelde supercomputers nodig zijn om de oplossing binnen een dag of drie te kunnen berekenen! Opmerking. Door een deel 1−α van de knikkers volgens het teleportatie-model te laten rollen, hebben we het probleem van de groepen bladzijdes zonder onderlinge links opgelost. De toegevoegde teleportatie zorgt ervoor dat alle bladzijdes aan elkaar gerelateerd zijn. Natuurlijk is het tot zover beschreven model nog lang niet de hele waarheid. Google heeft ongetwijfeld nog heel veel kleinere en grotere slimmigheden om effici¨ent om te gaan met zoek-opdrachten en pageranking. Deze zijn, begrijpelijkerwijs, voor het grootste deel geheim. 15
Universiteit van Amsterdam
