Google Mathematics-seminarium

Idag var jag på detta seminarium som gavs på ”Numme”-avdelningen på matematiska institutionen på Linköpings universitet. Seminariet hölls av Lars Eldén som är tidigare instutitionskollega till mig under min doktorandtid på matematiska instutitionen. (På Lars hemsida finns OH-bilderna från presentationen!)

Seminariet handlade om rangordning av sökresultat i en sökmotor, och speciellt hur Google rangordnar sina sökresultat. En sökmotor fungerar (vanligen) så att man skriver in ett eller flera sökord (säg ett för enkelhets skull) och tar fram alla dokument som innehåller det ordet. Detta räcker dock inte eftersom ingen brukar orka titta igenom alla resultaten för att se om de ”duger”. Alltså måste alla webbsidor som innehåller ditt sökord rangordnas, och frågan är hur man gör detta för att det skall uppfattas som en bra rangordning. I fallet Google används den i Googlekretser välbekanta, men likväl mystiska, PageRank-sorteringen.

Det var om PageRank, och en algebraisk tolkning av den, som seminariet handlade.

För varje indexerad webbsida i indexet vill vi beräkna ett ”PageRank”, ett tal mellan noll och ett. Ju högre PageRank desto intressantare sida. Det räcker alltså inte att titta på de sidor som innehåller det ord du just sökt på, utan PageRank vill man(?) veta för alla sidorna innan sökningen startar. (Det nämndes inte på seminariet, men RageRank är lite av nyckeln till varför Google är så snabb när det gäller att svara på en sökning. Den vet helt enkelt var den skall börja leta då den redan har alla sidor i PageRank-ordning, och sidor med högre PageRank skall visas högre upp bland resultaten. Det innebär t.ex. att man inte behöver titta igenom hela indexet för att hitta de 10 första sökresultaten. Detta kan observeras tydligt på Google: Prova att ta fram det 801:a sökresultatet, på den 80:de resultatsidan och notera att det tar betydligt längre tid än att ta fram den den första resultatsidan.)

Det är inte någon speciellt avancerad matematik/algebra som behövs för att beskriva hur PageRank fungerar.

Vad som kan kallas för ”PageRank-problemet” är att finna ett PageRank-tal, r, för alla n:st webbsidor så att




Här är r_i RageRank för sida i, I_i är antalet inlänkar till sida i och N_j är antalet utlänkar från sida j. Detta är ett rekursivt samband.

Frågor som en matematiker, eller numeriker, nu ställer sig är om det finns en lösning till detta. Om det gör det, finns det bara en lösning? (Är lösningen entydig?). Kan man svara ja på dessa (och det kan man i detta fall) så frågar man sig hur man beräknar r_i för alla i.

Det som gör det hela svårt är att n är stort, dvs webbsidorna i indexet är väldigt många. Google har c:a 3 miljarder sidor i sitt index, och uppdateringen har (åtminstone fram till nu) skett ungefär var fjärde vecka. Det innebär att det absolut inte får ta mer än så lång tid att beräkna detta, för att rangordna sidorna.

Det, för en numeriker, som är speciellt intressant i detta är att ”PageRank-problemet” ovan, kan tolkas i matrisoperationer som beräkningen en egenvektor för en länk-struktur-matris (Q i seminarieanteckningarna). Q-matrisen är en matris som innehåller nollor, förutom på vissa element som indikerar att det är möjligt att ta sig (via ett klick!) från en sida till en annan. Denna koppling, mellan PageRank-problemet och egenvektorberäkningen, kan dock göras först efter lite manipulering av Q-matrisen. Denna Q-matris kan tolkas i termer av en ”slumpvandring”, eller ”slumpsurfare”, i den mening att elementen i Q kan tolkas som sannolikheten att en ”slumpsurfare” förflyttar sig från en viss sida till en annan (en ”transition probability”). Sidor med fler länkar till sig, och speciellt länkar från sidor med högt r_i, får en högre sannolikhet att besökas av denne slumpsurfare.

Den manipulering som behövs av Q-matrisen innan vidare behandling kan göras kan, i princip, tolkas som att vi vill förhindra ”slumpsurfaren” från att fastna på webbsidor som inte har några utlänkar och förhinda han/hon att fastna på en liten ”ö” av webbsidor. Denna manipulering innebär i matematiska termer att en rang-1 uppdatering av Q-matrisen görs så att ingen kolumn i Q innehåller bara nollor. Denna rang-1 uppdatering kan i sin tur tolkas i termer av ”slumpsurfaren” som att denne hoppar iväg till en slumpmässig sida med viss sannolikhet. Man kan se det som att kan lägger in osynliga länkar på alla webbsidor till alla andra webbsidor. Hur troligt det är att ett sådant ”hopp” sker beror på en parameter alfa som ingår i rang-1 uppdateringen.

Storleken på alfa påverkar hur ”enkelt” PageRank-problemet är att lösa. Konvergenshastigheten (och därmed lösningstiden) hos Potensmetoden som lämpligen används för problemet påverkas direkt av valet av denna parameter. Potensmetoden i sig är ”gammal skåpmat” men är i detta fall, på grund av att antalet webbsidor som skall rangordnas är mycket stort, trots allt intressant eftersom alternativ just nu saknas.

Seminariet var intressant! För den som är intresserad av att beräkna (något som liknar) PageRank på ett eget litet index bör ta en titt på bilderna från seminariet.

Comments are closed.