Algoritmes

Hoe werkt het pagerank algoritme op bronnen?

Pagerank Algoritme

Vroeger werden er in zoekmachines websites op volgorde gezet door de tekst die in de websites zelf stond. Als er bijvoorbeeld wordt gezocht op het woord Google, zou er een pagina helemaal bovenaan kunnen staan waar een miljoen keer het woord Google in staat en verder niks. Dat was niet de bedoeling van de zoekmachine, dus kwamen Larry Page en Sergey Brin met een idee.

Ze hebben het pagerank algoritme opgericht die websites op het internet op volgorde zet door te kijken welke pagina's aan een specifieke pagina linken.

Naar samenvatting ⬇

Knooppunten

Een site wordt in het pagerank algoritme als een knooppunt gezien. Als een knooppunt A aan een ander knooppunt B gekoppeld is, zal het knooppunt A verwijzen naar het knooppunt B. Je zou de waarde van elke pagina dan kunnen bepalen door een stelsel van lineaire vergelijkingen op te lossen. Het enige probleem daarmee is dat het veel geheugen en tijd kost. Dat is niet ideaal. [1]

Het is makkelijker om een markovketen te gebruiken om websites een verschillende waarde te geven. Een markovketen heeft een vaste verdeling in het geval dat vanaf elk knooppunt alle andere knooppunten verbonden zijn. Dat is bij het pagerank algoritme aan de hand. Na een hele lange wandeling in de markovketen komt er een vaste verdeling uit die π genoemd wordt. Hoe hoger de kans dat een gebruiker op een knooppunt terecht komt, hoe belangrijk het knooppunt is. Daarmee kunnen websites gesorteerd worden op waarde. Hieronder wordt de markovketen wat uitgebreider uitgelegd.

"Markovketens zijn de manier om websites te sorteren op waarde."

Markovketen

In de Markovketen hieronder staan 3 getallen die verbonden zijn met pijlen. De 3 getallen stellen websites voor waar gebruikers op kunnen komen.

De pijlen geven aan wat de kans is dat de gebruiker op de volgende website (het volgende getal) terecht komt. De pijlen worden 'weighted arrows' genoemd. Er zijn ook pijlen die naar hetzelfde getal terug gaan. Die pijlen heten 'self-pointing arrows'. De uitkomst van alle pijlen samen die van een bepaald getal komen is 1.

De algemene formule voor markovketens is:

P(Xn+1 = x│Xn = xn)

In de formule staat eigenlijk dat Xn+1 alleen afhangt van Xn. Stel dat X1 = 4, X2 = 5 en X3 = 4. In het voorbeeld van eerder ziet de algemene formule voor markovketens er dan zo uit:

P(X4 = 7│X3 = 4) = 0,7

Opnieuw wordt dus alleen het huidige getal gebruikt om het volgende getal te bepalen. De formule geeft aan dat de kans 0,7 is, dat X4 het getal 7 wordt, als X3 = 4. [2]

"De kans dat een gebruiker op een bepaalde pagina terecht komt kan worden berekend met een markovketen."

Kansen berekenen

In markovketens bestaat er een vaste verdeling van kansen. Deze vaste verdeling kan worden uitgerekend door veel stappen random te genereren. Deze methode is alleen niet efficiënt en ook niet betrouwbaar, omdat er een andere vaste verdeling uit had kunnen komen als er meer getallen waren gebruikt bij het genereren. Het is namelijk een toevalsproces die met de tijd verandert. Daarom is het nodig om lineaire algebra te gebruiken om de vaste verdeling uit te rekenen.

Dat is met een transitiematrix te bepalen. De transitiematrix van het eerder genoemde voorbeeld ziet er als volgt uit:

A =

0,2 0,6 0,2
0,3 0 0,7
0,5 0 0,5

De waardes in de matrix zijn de waardes die invloed hebben op de pijlen in het voorbeeld. De knooppunten staan op volgorde van 5, 4, 7. Als de huidige waarde 5 zou zijn en de volgende waarde 7 zou dat 0,2 kans zijn, omdat rechts bovenin de matrix 0,2 staat. De rij staat dus voor de huidige waarde en de kolom voor de volgende waarde.

Stel dat de eerste stap X1 = 4. Als dit in een matrix weergegeven zou worden, zou het er zo uit zien:

X1 =

0 1 0

Om de waarde van X2 te krijgen wordt X1 vermenigvuldigt met A. Dat ziet er zo uit:

X2 = X1A =

0 1 0
0,2 0,6 0,2
0,3 0 0,7
0,5 0 0,5

=

0,3 0 0,7

De kans voor de volgende waarde komt dus uit de transitiematrix vermenigvuldigd met de huidige waarde. Als de output meerdere keren wordt ingevoerd als input zou er uiteindelijk dezelfde output als input uit komen. Dat is de meer nauwkeurige manier om de vaste verdeling te krijgen. [3]

Er is alleen wel één probleem. Stel dat er een knooppunt is, waar geen links in staan. Dan kan de gebruiker nergens anders meer heen. De oplossing daarvoor is teleportatie. Er is altijd een kans dat de gebruiker teleporteert vanuit een pagina naar een andere pagina. De formule voor deze kans kan worden weergegeven als:

M = (1 - p) * A + p * B waar B = 1/n *

1 1 1
1 1 1
1 1 1

M staat voor de pagerank matrix, A staat voor de transitiematrix en B staat voor de huidige pagina. In de formule is een constante p die een waarde heeft tussen de 0 en de 1. Deze constante heet de dempingsfactor. De dempingsfactor geeft aan wat de kans is dat de gebruiker naar een andere pagina teleporteert. Elke pagina heeft een kans van 1/n om gekozen te worden door de gebruiker. De matrix bij de huidige pagina is zo groot als hoeveel pagina's er in totaal zijn. [3]

Samenvatting
  • Google gebruikt complexe algoritmes om zoekresultaten te rangschikken
  • PageRank was het eerste belangrijke algoritme
  • Machine learning speelt een steeds grotere rol
  • De kans dat een gebruiker op een bepaalde pagina terecht komt kan worden berekend met een markovketen
Bronnen
  • 1. Amine, A. (2021, 24 december). PageRank algorithm, fully explained - Towards Data Science. Medium. towardsdatascience
  • 2. Normalized Nerd. (2020, 25 oktober). Markov Chains Clearly Explained! Part - 1 [Video]. YouTube. www.youtube.com
  • 3. Radu, R. T. R. (z.d.). PageRank Algorithm - The Mathematics of Google Search. pi.math.cornell