Story
Google ::
Linjär algebra för 367 miljarder dollar.

Av :: Mikael Forsberg
Google är idag ett av värdens mest kända och högst värderade bolag. Grunden för goodles framgång är dess sökmotor som utvecklades av googles grundare Lawrence Page och Sergey Brin. Vad som många inte känner till är att denna sökmotor använder sig av grundläggande idéer från linjär algebra och det är detta som denna story handlar om.

En sorts grundförutsättning är att ordet vi söker efter är ett relativt vanligt ord, vilket innebär att det är ett av kanske 20 000 som vanligen används. 
Eftersom det finns många miljarder webbsidor så  kan det vara väldigt många sidor som innehåller det ord vi söker.  Detta betyder att det är viktigt att sortera fram de webbsidor som är mest 
relevanta och det är detta som Googles PageRank idé är konstruerad att göra.

För att göra det  väldigt enkelt för oss så ska vi exemplifiera det hela med ett litet internet om hela tre (3) sidor. (se figuren nedan) 

Här följer några huvudsteg för PageRank på detta förenklade internet.

 

1.  Representera internet som en riktad graf:     ett minimalt internet som exempel

Varje sida representeras av en nod (en cirkel med sidans nummer).  När en sida (t.ex. 1) länkar till en annan sida (t.ex. sida 2) så representeras detta som en pil från, i detta fall sida 1 till sida 2. Vårt internet ges av den riktade grafen "internet" här intill.

Detta betyder alltså att sida ett länkar till 2, sida 2 till 3 och sida 3 länkar både till sida 1 och 2.

2. Varje sida har ett mått på "internetcred" om 1 som den delar ut genom att länka. 

Om en sida länkar till tre sidor så delas en tredjedel av detta cred till vardera av de länkade sidorna. Om vi betecknar med \(x_1\) den cred som sida \(1\) får från alla som länkar till den  så kan vi ställa upp följande  ekvationssystem sidornas erhållna cred för vårt tresidorsinternet: 

\[ \begin{eqnarray} x_1 &=&0\cdot x_1+0\cdot x_2+0.5 x_3\\  x_2 &=&1\cdot x_1+0\cdot x_2+0.5x_3\\    x_3 &=&0\cdot x_1+ 1\cdot x_2+0\cdot x_3\end{eqnarray} \] 

Detta ekvationssystem kan skrivas på matris form som 

\[ \mathbf{x} =\mathbf{G}\mathbf{x},\]

där \(\mathbf{G}\) är Googlematrisen för vårt internet:

\[\mathbf{G}=\left[ \begin{array}{ccc}0 & 0 & 0.5 \\1 & 0 & 0.5 \\0 & 1 & 0\end{array} \right]\]    

3. Egenvektorer från linjär algebra::  

Med kunskaper från vår kurs i linjär algebra så kommer vi känna igen att vektorn \(\mathbf{x}\) är en s.k. egenvektor till egenvärdet till googlematrisen. Löser vi detta egenvärdesproblem så får vi att egenvektorerna spänns upp av vektorn \[ \mathbf{x}=\left( \begin{array}{c}0.5 \\  1 \\1\end{array}\right)\]Detta är då det PageRank som Googles metod skapar. Det betyder att de två sista sidorna har högst rang (eller internetcred som sades i ovan) och är de sidor som presenteras först när sökningen ska presenteras.

4. Iterativa metoder. 

Nu är ju ett tresidors internet ganska poänglöst så hur funkar ovanstående lösningsmetod för det riktiga internet  som innehåller kanske 25 miljarder sidor. Vårt tresidors internet gav ett linjärt ekvationssystem med tre ekvationer och tre obekanta. För ett 25 miljarder sidor stort internet så talar vi om 25 miljarder ekvationer med lika många obekanta och detta betyder att de rättframmametoderna som funkar för \(3\times 3\) system är alldeles för resurskrävande och skulle inte fungera för så stora system som är aktuella. Iterativ metod för att lösa vårt \(3\times 3\) system: 

 Idén är att upprepa följande 
         \[
             \mathbf{x}_{k+1}=G\ \mathbf{x}_k
         \]


4.a:: Startpunkt \(k=0\):: 


                 \[\mathbf{x}_0=
                     \left[
                     \begin{array}{c}
                     1 \\
                     1 \\
                     1
                     \end{array}
                     \right]
                 \]
 Notera att \(\mathbf{x}_0\) kan tolkas som ursprungscredden för internetsidorna, den som alltså delas ut via den riktade grafen  eller Googlematrisen om vi så vill. Vi sätter alltså in ursprungscreden för variablerna i Googlematrisavbildningen.  Då ger internetgrafen en ny cred \(\mathbf{x}_1\). Denna nya cred sätter vi in igen i Googlematrisen och får en ytterligare en ny cred \(\mathbf{x}_2\).  Nästa steg ger oss \(\mathbf{x}_3\) och vi har då

\[\mathbf{x}_3=G\ \mathbf{x}_2=G\  G\ \mathbf{x}_1=G\ G\ G\ \mathbf{x}_0= G^3\ \mathbf{x}_0\]

I varje steg multiplicerar vi med googlematrisen från vänster.

4.b :: Iteration minimerar räkneoperationer :


Poängen med iteration istället för att lösa systemet direkt är att iterationen innehåller mycket färre räkneoperationer  i och med att iterationen i princip är ren multiplikation. Googlematrisen är dessutom en gles matris: den innehåller många nollor eftersom de flesta webbsidor innehåller få länkar till andra sidor, jämfört med det totala antalet webbsidor. Denna gleshet kan utnyttjas mer fördelaktigt vid iterationen än  för den rena ekvationslösningen.


 4.c ::Oändlig Iteration ::

Iterationen får vi när vi upprepar detta. Om vi gör detta i oändlighet så får vi
                 \[
                     x_\infty=\lim_{k\to\infty} \mathbf{x}_k=
                     \left[
                         \begin{array}{c}
                             0.6 \\
                             1.2 \\
                             1.2
                         \end{array}
                     \right]
                 \]
 I själva verket så kommer man fram till dessa siffror redan efter omkring 13 iterationer, så vi behöver alltså inte upprepa så länge. Problemet är nu att denna slutliga credd som iterationen ger inte är samma som den exakta som vi får genom att lösa systemet direkt.  Det är faktiskt inte ens säkert att iterationen konvergerar. För att lösa detta så behövde man modifiera metoden.



 5. Modifierade Google ekvationerna. 


 För att få iterationen att konvergera något snabbare och till siffror som ligger närmare de rätta så ställs följande ekvation upp
         \[
             \mathbf{x}=(1-\delta)\mathbf{x}_0 +\delta G\mathbf{x},
         \]
där \(\delta\) är den så kallade dämpningsfaktorn. Notera att om \(\delta=1\) så har vi den ursprungliga Googleekvationen. Googles ursprungsartikel noterar att siffran \(\delta=0.85\) har kommit att föredras.

 Det är naturligtvis mycket mer i Googles sökteori än vad som sagts här men det ger förhoppningsvis en liten inblick hur linjär algebra kan  komma till användning.  Läs mer i  t.ex. googlegrundarnas artikel

http://www.linearalgebra.se/pdfs/Brin-Page-google.pdf

story::

Detta är kursmaterial och kommentering endast möjlig för studenter registrerade på kursen vid högskolan i gävle Logga in för att kommentera och ställa frågor ::