Transcript
PageRank: Der Google-Ranking-Algorithmus Ordnung einer Menge verlinkter Dokumente auf der Basis der Verlinkungsstruktur Eine Einführung mit Erläuterungen der mathematischen Grundlagen
Karin Haenelt
29.2.2016
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
2
PageRank Entwicklung und Patente Algorithmus zur Bestimmung einer Rangordnung von verlinkten Dokumenten Grundlage der von Lawrence Page und Sergey Brin gegründeten Suchmaschine Google Erfinder und Namensgeber der Methode: Lawrence Page SW-Entwickler: Lawrence Page und Sergey Brin, Stanford University Patentanmeldung durch Stanford University 1998 (ff): (Page, 2001) 1998 Gründung von Google, Lawrence Page und Sergey Brin
© Karin Haenelt, PageRank, 6.11.2015
3
PageRank Ziele und Ansatz PageRank: Berechnung der Relevanzgewichtung von Dokumenten unabhängig vom Inhalt der Dokumente oder einer Anfrage auf der Basis der Verlinkungsstruktur der Dokumente … und möglicherweise weiterer Kriterien http://www.google.com/intl/de/insidesearch/howsearchworks/thestory/
zum Zeitpunkt der Indexierung Suchmaschine ermittelt Menge der zur Anfrage passenden Dokumente ordnet Elemente der Menge nach ihrem PageRank-Wert … und weiteren Kriterien
© Karin Haenelt, PageRank, 6.11.2015
4
PageRank-Grundidee Gewichtung über Verlinkungsstruktur Eine Seite ist wichtig, wenn viele wichtige Seiten auf diese Seite verweisen Gewichtungsergebnis für eine Seite W beruht auf Anzahl der Seiten, die auf die Seite W verlinken Gewichtung der Seiten, die auf die Seite W verlinken
(Page, 2001) © Karin Haenelt, PageRank, 6.11.2015
5
PageRank-Grundidee Gewichtung über Verlinkungsstruktur angenommen Seite A hat 2 ausgehende Links einer der Links weist auf Seite B einer der Links weist auf Seite C dann gibt Seite A ½ ihrer Gewichtung an Seite B weiter ½ ihrer Gewichtung an Seite C weiter Darstellung als Gleichungssystem
A
B C
pr ( A) = pr (C ) pr ( B ) = 1 / 2 pr ( A)
pr ( A) = 0.4 pr ( B ) = 0.2
pr (C ) = 1 / 2 pr ( A) + pr ( B )
pr (C ) = 0.4
© Karin Haenelt, PageRank, 6.11.2015
N
∑ pr(i ) = 1 i =1
6
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
7
PageRank – Modellierung Basis: Darstellung des Webs als Graph Web als gerichteter Graph Knoten: Web-Dokument gerichtete Kanten: Links von einem Dokument zu einem anderen Beispiel A
B C Page, 2001
© Karin Haenelt, PageRank, 6.11.2015
8
PageRank – Modellierungskomponenten 1. Darstellung des Graphen als Hyperlink-Matrix Hyperlinkmatrix H von A von B von C
A
B C
H=
zu A zu B
0 1/ 2
0 0
1 0
zu C
1/ 2
1
0
N x N Spaltenmatrix mit Gewichten für die Links Wie werden die Gewichte der Links bestimmt? eine Möglichkeit: © Karin Haenelt, PageRank, 6.11.2015
1 / n j hij = 0
falls j auf i verlinkt sonst
9
PageRank – Modellierungskomponenten 2. PageRank-Vektor Der PageRank-Vektor enthält die PageRank-Werte der einzelnen Webseiten pr ( A) pr = pr ( B ) pr (C )
wird aus der Hyperlink-Matrix berechnet
© Karin Haenelt, PageRank, 6.11.2015
10
PageRank – Modellierungskomponenten Anmerkung zum Beispiel Das gezeigte Beispiel eignet sich nicht zur approximativen Berechnung des PageRank-Vektors (die auf den späteren Folien eingeführt wird), da die Matrix dieses Beispiels nicht aperiodisch ist. Die Approximation konvergiert für eine aperiodische Matrix nicht.
© Karin Haenelt, PageRank, 29.2.2016
11
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
12
Notation A, B, C i,j ni N H S r pr(A) oder pr(i) p[i] pn P p0[i] p∞ [i]
Webseiten Repräsentation von Knoten im Web bzw. von Webseiten, und entsprechende Matrixindizes Grad von i, d.h. Anzahl der ausgehenden Kanten von i Gesamtzahl der betrachteten Webseiten Hyperlinkmatrix (gewichtet) stochastische ergodische Hyperlinkmatrix Vektor des Ranges aller Webseiten PageRank von Seite A bzw. Knoten i - algebraische Sicht - stochastische Sicht n-te Approximation an p Wahrscheinlichkeit Wahrscheinlichkeit, dass Zufallssurfende am Knoten i beginnen zu surfen (Startwahrscheinlichkeit) Wahrscheinlichkeit, dass Zufallssurfende nach unendlich vielen Schritten am Knoten i sind ; stationäre Verteilung (steady state probability), stochastische Sicht des PageRanks Konstante im Intervall [0,1]
© Karin Haenelt, PageRank, 6.11.2015
13
Wie berechnet man aus der Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten
Matrix PageRank-Vektor Lineares Gleichungssystem Koeffizientenmatrix Lösungsvektor eines linearen Gleichungssystems des linearen Gleichungssystems Lineare Abbildung Abbildungsmatrix Markov-Prozess Übergangsmatrix eines Markov-Prozesses
pr (i ) =
Fixvektor der Abbildungsmatrix
x = Ax
Grenzvektor
p ∞ = lim S n p0 n →∞
→ © Karin Haenelt, PageRank, 6.11.2015
∑
{ j| j →i }
pr ( j ) nj
j verlinkt nach i 14
Wie berechnet man aus der Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten: Lineare Algebra Perspektive: Lineares Gleichungssystem (Lineare Algebra 1) Betrachtung der Matrix als Koeffizientenmatrix eines linearen Gleichungssystems PageRank-Vektor ist der Lösungsvektor des Gleichungssystems pr (i ) =
pr ( j ) ∑ { j| j →i } n j
Perspektive: Lineare Abbildung (Lineare Algebra 2) Betrachtung der Matrix als Abbildungsmatrix eines Vektorraumes in einen anderen Vektorraum PageRank-Vektor ist der Fixvektor x = A x der Abbildungsmatrix
© Karin Haenelt, PageRank, 6.11.2015
15
Wie berechnet man aus der Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten: Stochastik Perspektive: Markov-Prozess (Stochastik) Betrachtung der Matrix als Beschreibung eines Markov-Prozesses S n p0 PageRank-Vektor entspricht dem Grenzvektor p∞ = lim n →∞ (Grenzvektor der Wahrscheinlichkeiten der einzelnen Zustände, dem sich der durch die stochastische Matrix beschriebene Markov-Prozess nähert)
© Karin Haenelt, PageRank, 6.11.2015
16
Mathematische Betrachtungsvariante: Lineares Gleichungssystem Betrachtungsvariante: Lineares Gleichungssystem (Lineare Algebra 1) Matrix als Koeffizientenmatrix PageRank-Vektor als Lösungsvektor eines linearen Gleichungssystems
© Karin Haenelt, PageRank, 6.11.2015
17
M
Perspektive: Lineares Gleichungssystem Definition: Lineare Gleichung Definition: Eine lineare Kombination von x1, …, xn hat die Form a1x1 + a2x2 + a3x3 + … + anxn wobei a1, …, an ∊ ℝ die Koeffizienten der Kombination sind. Definition: Eine lineare Gleichung mit x1, …, xn hat die Form a1x1 + a2x2 + a3x3 + … + anxn = d wobei d ∊ ℝ eine Konstante ist. Definition: Ein n-Tupel (s1, s2, …, sn) ist eine Lösung einer linearen Gleichung, oder erfüllt eine lineare Gleichung, wenn die Einsetzung der Zahlen s1, s2, …, sn für die Variablen eine wahre Aussage ergibt: a1s1 + a2s2 + a3s3 + … + ansn = d Hefferon, 2012, 2 © Karin Haenelt, PageRank, 6.11.2015
18
M
Perspektive: Lineares Gleichungssystem Definition: Lineares Gleichungssystem Definition: Ein lineares Gleichungssystem ist eine Menge von linearen Gleichungen, die gleichzeitig erfüllt sein müssen. Definition: Ein lineares Gleichungssystem a1,1x1 + a1,2x2 + a1,3x3 + … + a1,nxn = d1 a2,1x1 + a2,2x2 + a2,3x3 + … + a2,nxn = d2 . . am,1x1 + am,2x2 + am,3x3 + … + am,nxn = dm hat die Lösung (s1, s2, …, sn), wenn dieses n-Tupel eine Lösung aller Gleichungen des Systems ist. Hefferon, 2012, 2 © Karin Haenelt, PageRank, 6.11.2015
19
Perspektive: Lineares Gleichungssystem Matrix als Koeffizientenmatrix, Page Rank als Lösungsvektor Matrixnotation des Gleichungssystems ⋅ x = b H 0 0 1 pr1 pr1 1 / 2 0 0 ⋅ pr2 = pr2 1 / 2 1 0 pr pr 3 3
→ die Verlinkungsmatrix entspricht einer Koeffizientenmatrix (hier: H) → der PageRank-Vektor entspricht dem Lösungsvektor (hier: b) eines linearen Gleichungssystems
Direkte Notation des Gleichungssystems entsprechendes homogenes b H ⋅x Gleichungssystem
pr1 = 0 ⋅ pr1 + 0 ⋅ pr2 + 1 ⋅ pr3
pr1 = pr3
pr2 = 1 2 pr1 + 0 ⋅ pr2 + 0 ⋅ pr3
pr2 = 1 2 pr1
pr3 = 1 2 pr1 + 1 ⋅ pr2 + 0 ⋅ pr3
pr3 = 1 2 pr1 + pr2
© Karin Haenelt, PageRank, 6.11.2015
−
pr1 1 2 pr1 − 1 2 pr1 +
pr2 pr2
−
pr3
= 0
pr3
= 0 = 0 20
Perspektive: Lineares Gleichungssystem Lösungsverfahren für lineare Gleichungssysteme „Direkte Verfahren sind solche, die nach endlich vielen Rechenschritten die (bis auf Rundungsfehler) exakte Lösung des Gleichungssystems liefern.“ bekannte Methode: Gaußsches Eliminationsverfahren „Bei der iterativen Lösung berechnet man ausgehend von einem beliebigen Startvektor x0 eine Folge von Iterierten xm für m = 1, 2, . . .: x 0 a x1 a x 2 a ... a x m a x m+1 a ...
Im Folgenden ist xm+1 nur von xm abhängig, so dass die Abbildung x m a x m+1 das Iterationsverfahren bestimmt. Die Wahl des Startwertes x0 ist nicht Teil des Verfahrens.“ bekannte Methode: Gauß-Seidel-Verfahren Hackbusch, 2004: 8/9 © Karin Haenelt, PageRank, 6.11.2015
21
Perspektive: Lineares Gleichungssystem Lösung des Gleichungssystems mit Gauß-Elimination −
pr1
Gleichungssystem
1 2 pr1 − 1 2 pr1 +
Umformung 1
ρ
ρ1 − 1 2 ρ1 + ρ 2 : − 1 2 ρ1 + ρ 3 :
pr2 pr2
−
−
pr:1 −
pr2 pr2
pr3
= 0
pr3
= 0 = 0
pr3
+ 1 2 pr3 − 1 2 pr3
= 0 = 0 = 0
Reihe des Gleichungssystems
Umformung 2
© Karin Haenelt, PageRank, 6.11.2015
pr1 pr2
= pr3 = 1 2 pr3 22
Perspektive: Lineares Gleichungssystem Lösung des Gleichungssystems mit Gauß-Elimination pr1 pr2
= pr3 = 1 2 pr3
Lösungsmenge pr1 1
pr 1 2 pr | pr = ∈ ℜ 2 3 3 pr 1 3
nicht-triviale (d.h. Nicht-Null) Lösung z.B.: pr1 = 2, pr2 = 1, pr3 = 2 jedes Vielfache dieser Lösung ist ebenfalls eine Lösung N pr1 0.4 Normierung aus PageRankpri = 1 ∑ Anwendungssicht1) pr2 = 0.2 Vektor pr i =1 pr 0.4 ergibt eindeutige Lösung 3 1)
Die PageRank-Werte bilden eine Wahrscheinlichkeitsverteilung über die Webseiten, so dass die Summe der PageRank-Werte über alle Webseiten gleich 1 ist (Page, 2001: 4) © Karin Haenelt, PageRank, 6.11.2015
23
Perspektive: Lineares Gleichungssystem Lösung des Gleichungssystems mit Gauß-Elimination Komplexität des Eliminationsverfahrens nach Gauß „Im allgemeinen Fall benötigt die Gauß-Elimination für die Lösung eines Gleichungssystems Ax = b mit n Unbekannten 2n3/3 + (n2) Operationen. Der Speicherbedarf beträgt n2 + n.“ (Hackbusch, 2004: 8) dabei wurden folgende Operationen gezählt: Addition, Subtraktion, Multiplikation, Division
→ nur für sehr kleine Matrizen möglich © Karin Haenelt, PageRank, 6.11.2015
24
Mathematische Betrachtungsvariante: Lineare Abbildung Betrachtungsvariante: Lineare Abbildung (Lineare Algebra 2) Matrix als Abbildungsmatrix PageRank-Vektor als Fixvektor der Abbildungsmatrix
© Karin Haenelt, PageRank, 6.11.2015
25
M
Perspektive: Lineare Algebra vorausgesetzte Definition: Vektorraum Definition: ein Vektorraum V über einem Körper K ist eine Menge V mit zwei Verknüpfungen der Form + und K × V V ×V → V →V ( v , w) a v + w
( c, v ) a cv
die man Addition (+) und Skalarmultiplikation (⋅) nennt, und für die folgende Axiome gelten:
Artin 1998, 95/96 © Karin Haenelt, PageRank, 6.11.2015
26
M
Perspektive: Lineare Algebra vorausgesetzte Definition: Vektorraum Definition (Fortsetzung) 1. Bezüglich der Addition bildet V eine Abelsche Gruppe 1. Abgeschlossenheit v + w ∊ V, für alle v,w ∊ V 2. Assoziativität (v+w)+u = v+(w+u) , für alle u,v,w ∊ V 3. Neutrales Element e es gibt ein neutrales Element e: v+e = v, für e ∊ V und alle v ∊ V (hier: e ist der Nullvektor ) 4. Inverses Element i es gibt ein inverses Element i: v + i = i + v = e, für alle v ∊ V 5. Kommutativität v+w = w+v , für alle v,w ∊ V Artin 1998, 95/96 © Karin Haenelt, PageRank, 6.11.2015
27
M
Perspektive: Lineare Algebra vorausgesetzte Definition: Vektorraum Definition (Fortsetzung): 2. Die Skalarmultiplikation ist assoziativ mit der Multiplikation in K: (ab)v = a(bv) für alle a, b ∊ K, v ∊ V 3. Die Skalarmultiplikation mit der reellen Zahl 1 wirkt als identische Abbildung auf V: 1v = v, für alle v ∊ V 4. Es gelten zwei Distributivgesetze (a+b)v = av+bv a(v+w) = av + aw für alle a, b ∊ K, v,w ∊ V und
Artin 1998, 95/96 © Karin Haenelt, PageRank, 6.11.2015
28
M
Perspektive: Lineare Abbildung vorausgesetzte Definition: Lineare Abbildung Definition: Es sei K ein Körper. Eine Abbildung f eines Vektorraumes V in einen Vektorraum W heißt lineare Abbildung von V nach W, wenn die folgenden Gleichungen für alle v1, v2 ∊ V und alle a ∊ K gelten: f(v1 + v2) = f(v1) + f(v2) f(av) = af(v)
© Karin Haenelt, PageRank, 6.11.2015
29
Perspektive: Lineare Abbildung Geometrisches Beispiel einer linearen Abbildung und Abbildungsmatrix
M
Beispiel: Dehnung: Kreis → Ellipse (mit Erhaltung des Mittelpunkts) Multiplikation der Komponenten der Vektoren X = (x,y) (Punkte des Kreises) mit den Skalaren μ bzw.ν, also μx und νy Beschreibung der Abbildung durch eine Matrix (Abbildungsmatrix) µ 0 X → ⋅ X 0 ν
X → AX
Die Matrix erfasst die Art der „Dehnung“ beider Dimensionen
Kunze, 2013: 1/2 © Karin Haenelt, PageRank, 6.11.2015
30
M
Perspektive: Lineare Abbildung Eigenwert und Eigenvektor Da es sich um lineare Operationen handelt, kann man bei der Matrix einen Faktor ausklammern, indem man alle Elemente der Matrix durch dividiert. Dasselbe ist mit Vektoren möglich. Damit entsteht eine Kunze, 2013: 1/2 Variationsmöglichkeit für die Abbildung X → A X so kann es einen Fall geben
→ = =λ =λ
© Karin Haenelt, PageRank, 6.11.2015
31
M
Perspektive: Lineare Abbildung Eigenwert und Eigenvektor eine Zahl heißt Eigenwert einer Matrix A, genau dann, wenn die Gleichung AX = λ X
nichttriviale (d.h. vom Nullvektor verschiedene) Lösungen besitzt Diese Lösungen heißen die zu gehörigen Eigenvektoren von A.
Kunze, 2013: 1/2 © Karin Haenelt, PageRank, 6.11.2015
32
M
Perspektive: Lineare Abbildung Definition: Eigenwert und Eigenvektor Definition: Es sei f: V → V ein Endomorphismus eines K-Vektorraumes V. Eine Konstante ∊ K heißt Eigenwert zu f, wenn es einen Vektor a ∊ V – {0} mit f(a) = a gibt. Man nennt in diesem Falle a einen Eigenvektor von f zum Eigenwert . Für eine Matrix A ∊ Knxn seien Eigenwerte und Eigenvektoren erklärt als Eigenwerte und Eigenvektoren der zugehörigen linearen Abbildung Kn → Kn, x ↦ Ax
Bosch, 2006:194 © Karin Haenelt, PageRank, 6.11.2015
33
M
Perspektive: Lineare Abbildung Beispiel: Eigenwert und Eigenvektor A
x
0 0 1 1 / 2 0 0 1 / 2 1 0
2 / 5 1 / 5 2 / 5
⋅
=
x
=
2 / 5 1 / 5 2 / 5
1
⋅
Dies ist das Beispiel von vorne: 2 / 5 4 / 10 1 / 5 = 2 / 10 = 2 / 5 4 / 10
0.4 0.2 0.4
ein Eigenwert der Matrix A =1
Abbildungsmatrix A
Eigenvektor von A zum Eigenwert = 1 Vektor x ≠ 0, der durch f: V → V auf ein Vielfaches x von sich selbst abgebildet wird (d.h. nur gestreckt, nicht gedreht wird) © Karin Haenelt, PageRank, 6.11.2015
34
M
Perspektive: Lineare Abbildung Fixvektor A
x =
x
2 / 5 0 0 1 2 / 5 1 / 2 0 0 ⋅ 1 / 5 = 1 ⋅ 1 / 5 2 / 5 1 / 2 1 0 2 / 5
wählt man = 1, so sind die Eigenvektoren gerade die Fixelemente der durch x → Ax
definierten Funktion f: Es sind diejenigen Vektoren, die durch f in sich selbst überführt werden Diese Eigenvektoren heißen auch Fixvektoren von A. Kunze, 2013 © Karin Haenelt, PageRank, 6.11.2015
35
M Perspektive: Lineare Abbildung Darstellung des homogenen linearen Gleichungssystems in der für Fixvektoren charakteristischen Form Ax = λx mit λ=1
Homogene Gleichungen der Gestalt a1 x1 + a2 x2 + ... + an xn = 0
lassen sich auch in der für Eigenvektoren charakteristischen Form schreiben: Ax = λx
das gilt aber nur für = 1; wäre variabel, so könnte man die Gleichungsform mit konstanten Koeffizienten ai nicht erreichen
Kunze, 2013 © Karin Haenelt, PageRank, 6.11.2015
36
Perspektive: Lineare Abbildung Darstellung des homogenen linearen Gleichungssystems in der für Fixvektoren charakteristischen Form Ax = x mit =1 A
x =
x
0 0 1 2 / 5 2 / 5 1 / 2 0 0 ⋅ 1 / 5 = 1 / 5 1 / 2 1 0 2 / 5 2 / 5
A
x =
x
0 0 1 pr1 pr1 1 / 2 0 0 ⋅ pr2 = pr2 1 / 2 1 0 pr pr 3 3
→ der PageRank-Vektor entspricht dem Fixvektor der Verlinkungsmatrix
© Karin Haenelt, PageRank, 6.11.2015
37
Mathematische Betrachtungsvariante: Stochastik Betrachtungsvariante: Markov-Modell (Stochastik) Matrix als probabilistische Übergangsmatrix eines MarkovProzesses PageRank-Vektor als stationäre Verteilung des Markov-Prozesses (Vektor gegen den der Markov-Prozess nach sehr vielen Schritten konvergiert)
© Karin Haenelt, PageRank, 6.11.2015
38
M
Perspektive: Stochastik Definition: Markov-Kette Einführung Eine Markov-Kette ist eine Folge von Zufallsvariablen mit kurzem Gedächtnis; das Verhalten zum jeweils nächsten Zeitpunkt hängt nur vom jeweils aktuellen Wert ab und nicht davon, welche Werte vorher angenommen wurden. Von besonderem Interesse ist das Langzeit-Verhalten solch einer Folge – z.B. Absorption in einer „Falle“ oder Konvergenz ins Gleichgewicht
Georgii, 2009:153 © Karin Haenelt, PageRank, 6.11.2015
39
M
Perspektive: Stochastik Definition: Markov-Kette - vorausgesetzte Definitionen im Folgenden wird Ω als eine höchstens abzählbare Menge vorausgesetzt. P(Ω) ist die Potenzmenge von Ω, also die Menge aller Teilmengen von Ω Definition: Sei Ω≠ ∅. Ein System F⊂P(Ω) mit den Eigenschaften a) Ω ∊ F b) A ∊F ⟹ Ac := Ω \ A ∊F (“logische Verneinung“) c) A1, A2, … ∊F ⟹ ∪i≧1 Ai ∊F (“logisches Oder“) heißt eine σ-Algebra in Ω. Das Paar (Ω,F) heißt dann ein Ereignisraum oder ein messbarer Raum. Ist Ω als höchstens abzählbar, dann setzt man F = P(Ω) vgl. Georgii, 2009:10, 13
© Karin Haenelt, PageRank, 6.11.2015
40
M
Perspektive: Stochastik Definition: Markov-Kette - vorausgesetzte Definitionen Definition: Sei (Ω,F) ein Ereignisraum. Eine Funktion P: F→ [0,1] mit den Eigenschaften Normierung: P(Ω) = 1 σ-Addititvität: Für paarweise disjunkte Ereignisse A1, A2, … ∊F (i.e. Ai I Aj = ∅ für i ≠ j ) gilt P(Ui ≥1 Ai ) = ∑i ≥1 P( Ai ) heißt Wahrscheinlichkeitsmaß oder auch Wahrscheinlichkeitsverteilung, kurz Verteilung auf (Ω,F) . Das Tripel (Ω,F,P) heißt dann Wahrscheinlichkeitsraum. Georgii, 2009:13 © Karin Haenelt, PageRank, 6.11.2015
41
M
Perspektive: Stochastik Definition: Markov-Kette - vorausgesetzte Definitionen Definition: Ist Ω eine abzählbare Menge, so heißt eine Folge ρ=(ρ(ω))ω∊Ω in [0,1] mit Σω∊Ω ρ(ω) = 1 eine Zähldichte auf Ω. Erläuterung: ρ ist ein Vektor mit Wahrscheinlichkeitswerten ρ(ω) für die Variable ω∊Ω Definition: Ist E≠ ∅ eine höchstens abzählbare Menge, und П = (П(x,y))x,y∊Ω eine Matrix, in der jede Zeile П(x,·) eine Zähldichte (2009) / Wahrscheinlichkeitsdichte (2015) auf E ist, dann heißt П eine stochastische Matrix vgl. Georgii, 2009:18 und 153 vgl. Georgii, 2015 © Karin Haenelt, PageRank, 6.11.2015
42
M
Perspektive: Stochastik Definition: Markov-Kette Sei E ≠ ∅ eine höchstens abzählbare Menge und П eine stochastische Matrix. Definition: Eine Folge X0, X1, … von Zufallsvariablen auf einem Wahrscheinlichkeitsraum (Ω, F,P) mit Werten in E heißt (nach A.A. Markov, 1856-1922) eine Markov-Kette mit Zustandsraum E und Übergangsmatrix П, wenn für alle n ≧ 0 und alle x0, …, xn+1 ∊ E gilt: P(Xn+1 = xn+1 | X0=x0, …, Xn = xn) = П(xn, xn+1) sofern P(X0=x0, …, Xn = xn) > 0. Die Verteilung von X0 heißt die Startverteilung der Markov-Kette
vgl. Georgii, 2009:153
© Karin Haenelt, PageRank, 6.11.2015
43
M
Perspektive: Stochastik Definition: Markov-Kette Gleichung P(Xn+1 = xn+1 | X0=x0, …, Xn = xn) = П(xn, xn+1) besteht aus zwei Teilaussagen: Die bedingte Verteilung von Xn+1 bei bekannter Vorgeschichte x0,…,xn hängt nur von der Gegenwart xn ab und nicht von der Vergangenheit; diese so genannte Markov-Eigenschaft ist die entscheidende Annahme Diese bedingten Verteilungen hängen nicht vom Zeitpunkt n ab. Eine Markov-Kette (Xn)n≧0 ist ein stochastischer Prozess mit kurzem Gedächtnis von genau einer Zeiteinheit und ohne innere Uhr. Georgii, 2009:153/154 © Karin Haenelt, PageRank, 6.11.2015
44
M
Perspektive: Stochastik Definition: Ergodensatz für Markov-Kette Für eine „kommunikative“ Markov-Kette pendelt sich die Verteilung nach langer Zeit bei einer invarianten Gleichgewichtsverteilung ein. Dies ist die Aussage des folgenden Ergodensatzes: Ergodensatz für Markov-Ketten. Sei E endlich, und es gebe ein k ≥ 1 mit Пk(x,y) > 0 für alle x,y ∊ E. Dann existiert für alle y ∊ E der Limes lim Π n ( x, y ) = α ( y ) > 0 n→∞
unabhängig von der Wahl des Startpunkts x ∊ E, und der Limes α ist die einzige Zähldichte/Wahrscheinlichkeitsdichte auf E mit
∑α ( x)Π( x, y ) =α ( y ) für alle y ∈ E x∈E
Anm.: "äußerst kommunikative" Markov-Kette: kann von jedem Zustand in jeden anderen gelangen, und zwar in einer festgelegten Anzahl von Schritten Georgii 2009:261/262, Georgii, 2015 © Karin Haenelt, PageRank, 6.11.2015
45
M
Perspektive: Stochastik Definition: Stationäre Verteilung Bemerkung und Definition: Stationäre Verteilungen. Fasst man α als Zeilenvektor auf, so kann man die Gleichung
∑α ( x)Π( x, y ) =α ( y ) für alle y ∈ E x∈E
αΠ = α schreiben; in der Form die Limesverteilung lim Π n ( x, y ) = α ( y ) > 0 n→∞ ist also ein linker Eigenvektor von П zum Eigenwert 1 1). Verwendet man solch ein α als Startverteilung, so ist die zugehörige Markov-Kette zeitlich invariant („stationär“) in dem Sinn, dass Pα (( Xn, Xn + 1,...) ∈ A) = Pα ( A) ⊗
für alle A ∊ ℱ = P (E) ℤ+ und n ≧ 0. Eine Wahrscheinlichkeitsdichte α mit αП = α heißt deshalb eine stationäre (Start-)Verteilung. 1) Perron-Frobenius-Theorem © Karin Haenelt, PageRank, 6.11.2015
Georgii, 2009:162 46
M
Perspektive: Stochastik Matrix irreduzibel und aperiodisch (ergodisch) Definition: Eine Übergangsmatrix П heißt irreduzibel, wenn zu beliebigen x,y ∊ E ein k = k(x,y) ≧ 0 existiert mit Пk(x,y) > 0 jeder Zustand kann von jedem anderen mit positiver Wahrscheinlichkeit in einer endlichen Anzahl von Schritten erreicht werden kann
Definition: Eine Übergangsmatrix П heißt aperiodisch, wenn für ein (und daher alle) x ∊ E gilt: die Menge {k ≧ 1: Пk(x,x) > 0} hat den größten gemeinsamen Teiler 1. die Längen der Wege, auf denen ein Knoten x wieder erreicht werden kann, sind teilerfremd Prozess springt nicht systematisch von einem bestimmten Zustand zu einem Zustand zurück
Eine stochastische Matrix П erfüllt genau dann die Voraussetzungen des Ergodensatzes, wenn П irreduzibel und aperiodisch ist. Georgii, 2009:171 (irreduzibel) und 185 © Karin Haenelt, PageRank, 6.11.2015
47
Perspektive: Stochastik Annahme: Surfmodell ist ein Markov-Modell Annahme des PageRank-Modells: Markov-Modell Zufallssurfende wählen zufällig Links einer Webseite, um zur nächsten Webseite zu gelangen Die Auswahl einer nachfolgenden Seite ist unabhängig von den vorher besuchten Seiten (Markov-Eigenschaft)
© Karin Haenelt, PageRank, 6.11.2015
48
Perspektive: Stochastik PageRank als stationäre Verteilung eines Markov-Prozesses PageRank-Wert einer Seite i : modelliert die Wahrscheinlichkeit, mit der Zufalls-Surfende nach der Verfolgung einer großen Anzahl von Links auf Seite i landen nach sehr vielen Schritten entlang der Verlinkungen hat die Wahrscheinlichkeit, auf einer bestimmten Seite zu sein, für jede Seite einen bestimmten Wert dieser Wert ist der PageRank einer Seite
Page, 2001: 5 © Karin Haenelt, PageRank, 6.11.2015
49
Perspektive: Stochastik PageRank als stationäre Verteilung eines Markov-Prozesses Iterationsprozess Vektor p0: eine N-dimensionale Wahrscheinlichkeitsverteilung, bei der jede Komponente p0[i] die Wahrscheinlichkeit angibt, dass Zufallssurfende auf Seite i beginnen Matrix S: probabilistische NxN-Übergangsmatrix, modelliert die Wahrscheinlichkeit des Zufalls-Übergangs von Seite j zu Seite i Die Wahrscheinlichkeitsverteilung ist nach einem Zustandsübergang p1 = S⋅p0 nach zwei Zustandsübergängen p2 = S⋅p1 = S2 ⋅ p0
Page, 2001: 5 © Karin Haenelt, PageRank, 6.11.2015
50
Perspektive: Stochastik PageRank als stationäre Verteilung eines Markov-Prozesses vorausgesetzt, die Iteration konvergiert, dann konvergiert sie zu p∞ = lim S n p0 n →∞
p∝ heißt in diesem Kontext stationäre Verteilung (steady state probability) →der PageRank-Vektor entspricht der stationären Verteilung des Markov-Prozesses „Die Iteration zirkuliert die Wahrscheinlichkeiten durch die verlinkten Knoten wie ein Energiefluss im Stromkreis und akkumuliert sie an wichtigen Stellen“ Page, 2001: 5 Page, 2001: 5 © Karin Haenelt, PageRank, 6.11.2015
51
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
52
PageRank Plan des Algorithmus Start Select an initial n-dimensional vector p0 Compute an approximation pn to a steadystate probability p∞ in accordance with the equation pn = Anp0 Determine a rank r[k] for node k from a kth component of pn Done © Karin Haenelt, PageRank, 6.11.2015
Page, 2001: Fig. 3 53
Berechnung des PageRanks – Grundprinzip 3. Approximative Berechnung des PageRanks 1. Select an initial n-dimensional vector p0 Initialisierung des PageRank-Vektors: Startzustand p0
© Karin Haenelt, PageRank, 6.11.2015
1 3 1 3 1 3
beliebig gewählter Startvektor p0 hier: 1/N Interpretation: Wahrscheinlichkeit für Knoten 1 bis N, Startknoten eines zufälligen Surf-Ereignisses zu sein
54
Berechnung des PageRanks – Grundprinzip 3. Approximative Berechnung des PageRanks 2. Compute an approximation pn to a steady-state probability p∞ in accordance with the equation pn = Anp0 p1 = H ⋅ p0
p2 = H ⋅ p1 p2 = H 2 ⋅ p0
0 0 1 1 3 0 1 / 2 0 0 ⋅ 1 3 = 1 6 1 / 2 1 0 1 / 3 1 6 0 0 1 1 3 0 1 / 2 0 0 ⋅ 1 6 = 1 6 1 / 2 1 0 1 / 2 1 6
+
+ 1 3 1 3 0.3333 + 0 + 0 = 1 6 = 0.1666 + 1 3 + 0 1 2 0.5000 0
+ 0 + 1 2 1 2 0.5000 + 0 + 0 = 1 6 = 0.166 + 1 6 + 0 1 3 0.3333
für irreduzible primitive stochastische Matrizen (dazu: nachfolgende Folien) gilt: PageRank-Vektor ≙ Grenzvektor p∞ (stochastisch) ≙ Fixvektor PR (algebraisch) © Karin Haenelt, PageRank, 6.11.2015
55
Berechnung des PageRanks – Grundprinzip 3. Approximative Berechnung des PageRanks 2. Compute an approximation pn to a steady-state probability p∞ in accordance with the equation pn = Anp0 p3 = H ⋅ p2
0 0 1 1 2 0 + 0 + 1 3 1 3 0.3333 = + + = = 1 / 2 0 0 ⋅ 1 6 1 4 0 0 1 4 0 . 2500 1 / 2 1 0 1 / 3 1 4 + 1 6 + 0 5 12 0.4166 ...
p10 = H ⋅ p9 + + 38 96 38 96 0.3958 0 0 0 1 39 96 0 = + + = = 1 / 2 0 0 ⋅ 19 96 39 192 0 0 39 192 0 . 2031 1 / 2 1 0 38 / 96 39 192 + 19 96 + 0 77 192 0.4010 Anm. zu diesem Beispiel: Wenn man weiterrechnet, stellt man fest, dass die Approximation nicht konvergiert. Das liegt daran, dass die Matrix dieses Beispiels nicht aperiodisch ist. © Karin Haenelt, PageRank, 6.11.2015
56
Berechnung des PageRanks – Grundprinzip 3. Approximative Berechnung des PageRanks 3. Determine a rank r[k] for node k from a kth component of pn
0.3958 p10 = 0.2031 0.4010
© Karin Haenelt, PageRank, 6.11.2015
2 Rang r = 3 1
57
Berechnung des PageRanks – Grundprinzip Logarithmische Definition des PageRanks Ränge von Dokumenten können um Größenordnungen differieren daher logarithmische Definition zweckmäßig r[i ] = log
p∞ [i ] min { p∞ [k ]} k ∈ [1, N ]
ordnet dem niedrigsten Rang den Wert 0 zu und erhöht sich für jede Größenordnung um 1
Page, 2001:6 © Karin Haenelt, PageRank, 6.11.2015
58
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
59
Konvergenzbedingung für Markov-Ketten Theorie für Markov-Ketten: für beliebige Startvektoren konvergiert die iterative Berechnung des Grenzvektors gegen einen eindeutigen und positiven stationären Vektor (stationäre Verteilung) und dieser Vektor ist der Fixvektor, der durch die Matrix gegebenen linearen Abbildung wenn die Matrix stochastisch, irreduzibel und aperiodisch ist p ∞ = lim S n p 0 n →∞
=
p=Sp
Basis: Sätze von Perron (1907) und Frobenius (1912) © Karin Haenelt, PageRank, 6.11.2015
(vgl. Law, 2008) 60
Konvergenzbedingungen für Markov-Ketten Wirkung der Bedingungen stochastisch
∀sij : sij ≥ 0
N
∑s i =1
ij
= 1 → Grenzvektor ist eindeutig
irreduzibel (zerfällt nicht in unabhängige Teile)
→ Grenzvektor bekommt für alle Einträge positive Werte
aperiodisch (Längen der Zyklen sind teilerfremd)
→ Prozess konvergiert
© Karin Haenelt, PageRank, 6.11.2015
61
M
Stochastische Matrix Definition: irreduzibel Sei E eine höchstens abzählbare Menge und E ≠ ∅ Definition: Eine Übergangsmatrix П heißt irreduzibel, wenn zu beliebigen x,y ∊ E ein k = k(x,y) ≧ 0 existiert mit Пk(x,y) > 0 Erläuterung: Irreduzibilität bedeutet: jeder Zustand kann von jedem anderen mit positiver Wahrscheinlichkeit in einer endlichen Anzahl von Schritten erreicht werden kann
Georgii, 2009:171 © Karin Haenelt, PageRank, 6.11.2015
62
Verletzung der Konvergenzbedingungen Reduzible Matrix - Beispiel 1
A
reduzible Matrix: unabhängiger Teil: Knoten ohne ausgehende Kanten (dangling node) pr0
1 3 1 3 1 3
pr1 = S ⋅ pr0
0 0 0 1 3 0 0 0 0 ⋅ 1 3 = 0 1 1 0 1 / 3 2 / 3
B C
pr2 = H ⋅ pr1
0 0 0 0 0 0 0 0 ⋅ 0 = 0 1 1 0 2 / 3 0
Formal: Prozess konvergiert gegen 0 es gibt nach einer gewissen Anzahl von Schritten keine Möglichkeit mehr in bestimmte Zustände zurückzukehren Problem: PageRank sagt nichts über die relative Bedeutung der Webseiten aus nach Austin, 2006 © Karin Haenelt, PageRank, 6.11.2015
63
Verletzung der Konvergenzbedingungen Reduzible Matrix - Beispiel 2 reduzible Matrix: unabhängiger Teil: unabhängiger Teilgraph 1
3
5
7
p∞
H
0 1 / 2 2 4 6 8 1 / 2 0 Prozess konvergiert 0 für den unabhängigen 0 Teilgraphen gegen 0 0 0
0 0 0 0 0 1/ 2 1/ 3 0 0 0 0 0 1 0 0 0 0 1/ 2 1/ 3 0 0 0 1/ 3 1/ 3 0 0 0 1/ 3 0 0 0 1/ 3
0 0 0 0 0 0 0 0 0 0 0 0 0 1/ 2 0 0 0 1/ 2 0 0 1 / 2 1 1 / 2 0
0 0 0 0 0.12 0.24 0.24 0.12 Austin, 2006
© Karin Haenelt, PageRank, 6.11.2015
64
M
Stochastische Matrix Definition: aperiodisch Sei E eine höchstens abzählbare Menge und E ≠ ∅ Definition: Eine Übergangsmatrix П heißt aperiodisch, wenn für ein (und daher alle) x ∊ E gilt: die Menge {k ≧ 1: Пk(x,x) > 0} hat den größten gemeinsamen Teiler 1. die Längen der Wege, auf denen ein Knoten x wieder erreicht werden kann, sind teilerfremd Prozess springt nicht systematisch von einem bestimmten Zustand zu einem Zustand zurück
Georgii, 2009:185 © Karin Haenelt, PageRank, 6.11.2015
65
M
Stochastische Matrix Beispiel: aperiodisch Es ist Пk(x,x) > 0, wenn es in der Matrix einen Weg von x nach x der Länge k gibt ein Zustand x ist dann aperiodisch, wenn k = 1: П1(x,x) > 0: es gibt eine Schleife oder k ≧ 1: Пk(x,x) > 0: es gibt mindestens zwei Wege der Länge k1 und k2, und es gilt ggT(k1,k2) = 1 Matrix des ersten Beispiels ist NICHT aperiodisch: pBB1 Schritt = 0 (es gibt keine Schleife) pAA1 Schritt = 0 (es gibt keine Schleife) 2 Schritte = 0 p BB pAA 2 Schritte > 0 A B pBB 3 Schritte > 0 3 Schritte pAA >0 es gibt keine zwei Wege der C ggT {2,3} = 1 Länge k und k 1
© Karin Haenelt, PageRank, 6.11.2015
2
66
Verletzung der Konvergenzbedingungen Periodische Matrix – Beispiel 1 Periodische Matrix Prozess konvergiert nicht bzw. Konvergenz ist abhängig vom Startvektor A B
Konvergenz abhängig vom Startvektor p0
H
p0
p1
p2
p0
0 1 1 0
1 0
0 1
1 0
1 1
konvergiert nicht
Fixvektor existiert
© Karin Haenelt, PageRank, 6.11.2015
p1 2 2
1 1
2 2
konvergiert
H 0 1 1 2 1 ⋅ = 1 0 1 2 1
2 2 67
Verletzung der Konvergenzbedingungen Periodische Matrix – Beispiel 2 Periodische Matrix Prozess konvergiert nicht bzw. Konvergenz ist abhängig vom Startvektor H
A B
E C
D
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
p0
p1
p2
p3
p4
p5
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
Prozess konvergiert nicht – obwohl ein Fixvektor existiert Austin, 2006 © Karin Haenelt, PageRank, 6.11.2015
68
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
69
Die Google-Matrix G Um zu garantieren, dass der Markov-Prozess gegen einen eindeutigen Vektor mit ausschließlich positiven Werten konvergiert, muss man dafür sorgen, dass die Matrix folgende Eigenschaften hat: stochastisch (entspricht Markov-Prozess gemäß Definition) und irreduzibel und aperiodisch hierfür gibt es mehrere Möglichkeiten eine Variante ist die folgende Modifikation der Beispiel-Matrix H: S=H+A (stochastisch nach Einführung des Korrekturwertes für dangling nodes) G = αS + (1-α) 1/N 1 (irreduzibel und aperiodisch) © Karin Haenelt, PageRank, 6.11.2015
70
Die Google-Matrix G 1. Die Matrix H: Hyperlinks mit Gewichtungen 1 / n j hij = 0
H:
falls j auf i verlinkt sonst
H ist nicht stochastisch: A
B C
0 0 0 H = 0 0 0 1 1 0 N
∑h i =1
© Karin Haenelt, PageRank, 6.11.2015
ij
=1
ist nicht erfüllt
71
Die Google-Matrix G 2. Die stochastische Matrix S S=H+A
1 / n j aij = 0
H
für Knoten ohne ausgehende Kanten sonst
A
0 0 0 0 0 1 / 3 0 0 1 / 3 S = 0 0 0 + 0 0 1 / 3 = 0 0 1 / 3 1 1 0 0 0 1 / 3 1 1 1 / 3
© Karin Haenelt, PageRank, 6.11.2015
A
B C
72
Die Google-Matrix G 3. Die stochastische, irreduzible und aperiodische Matrix G G = αS + (1-α) 1/N 1 α Konstante 0 ≤ α < 1 1 N x N Matrix, alle Einträge sind 1 (dient der korrekten Formulierung der Addition von (1-α) 1/N zur Matrix S) A B Beispiel: sei α = 1/2 C α S (1-α)⋅1/N 1 1 1 1 1 / 6 1 / 6 2 / 6 1 / 6 1 / 6 1 / 3 0 0 1 / 3 1 1 1 G = ⋅ 0 0 1 / 3 + ⋅ 1 1 1 = 1 / 6 1 / 6 2 / 6 = 1 / 6 1 / 6 1 / 3 2 2 3 1 1 1 4 / 6 4 / 6 2 / 6 2 / 3 2 / 3 1 / 3 1 1 1 / 3 © Karin Haenelt, PageRank, 6.11.2015
73
Die Google-Matrix G Interpretation: ist die Modellierung G anwendungsadäquat? G
S
A
A
B C
H B C
A
B C
zufällig Surfende folgen den Links (H) oder springen zufällig auf eine andere Seite weiter (z.B. durch Eingabe einer Adresse in den Browser) (G)
© Karin Haenelt, PageRank, 6.11.2015
74
Die Google-Matrix G Wahl des Parameters α: Modellierungsaspekt aus der Sicht der Modellierung des Objektbereichs wenn α = 1, dann ist G = S entspricht der gegebenen Hyperlinksstuktur + Korrektur für Knoten ohne ausgehende Kanten Achtung: Matrix kann reduzibel und periodisch sein (positive PageRank-Werte und Konvergenz nicht gesichert) wenn α = 0, dann ist G = 1/N 1 alle Knoten gleichgewichtig mit allen verbunden, gegebene Hyperlinkstruktur völlig verloren → wünschenswert: ein Wert nahe 1 Austin, 2006 © Karin Haenelt, PageRank, 6.11.2015
75
Die Google-Matrix G Wahl des Parameters α: Konvergenzaspekt aus der Sicht der Konvergenzgeschwindigkeit Konvergenzgeschwindigkeit der Iteration wird beeinflusst durch die Größe des zweiten Eigenwertes |λ2| für die Google-Matrix G = αS + (1-α) 1/N 1 wurde bewiesen, dass die Größe des zweiten Eigenwertes | λ2| = α je kleiner | λ2|, desto schneller die Konvergenz d.h. bei einem Wert nahe 1 ist die Konvergenzgeschwindigkeit sehr gering Brin und Page geben als einen guten Kompromisswert α = 0.85 an
Austin, 2006 © Karin Haenelt, PageRank, 6.11.2015
76
Die Google-Matrix G Wahl des Parameters α Konstante α mit 0 ≤ α < 1 Wert von α: typisch: 0.85 muss aber nicht notwendigerweise gleichverteilt werden Wirkung: α wirkt als Dämpfungsfaktor: limitiert das Ausmaß in dem ein PageRank-Wert von Kind-Knoten geerbt werden kann Interpretation von 1-α: Wahrscheinlichkeit, mit der Zufallssurfende zu einer beliebigen Seite springen statt einem Link zu folgen
© Karin Haenelt, PageRank, 6.11.2015
77
A
Die Google-Matrix G Ein Beispiel
B C
0 0 1 / 3 1 1 1 1 / 6 1 / 6 2 / 6 1 / 6 1 / 6 1 / 3 1 1 1 G = ⋅ 0 0 1 / 3 + ⋅ 1 1 1 = 1 / 6 1 / 6 2 / 6 = 1 / 6 1 / 6 1 / 3 2 2 3 1 1 1 4 / 6 4 / 6 2 / 6 2 / 3 2 / 3 1 / 3 1 1 1 / 3
p0
p1
1 / 6 1 / 6 1 / 3 1 / 3 1 / 6 ⋅ 1 / 3 + 1 / 6 ⋅ 1 / 3 + 1 / 3 ⋅ 1 / 3 = 2 / 9 1 / 6 1 / 6 1 / 3 ⋅ 1 / 3 = 1 / 6 ⋅ 1 / 3 + 1 / 6 ⋅ 1 / 3 + 1 / 3 ⋅ 1 / 3 = 2 / 9 2 / 3 2 / 3 1 / 3 1 / 3 2 / 3 ⋅ 1 / 3 + 2 / 3 ⋅ 1 / 3 + 1 / 3 ⋅ 1 / 3 = 5 / 9
p0 p1 1 / 6 1 / 6 1 / 3 1 / 6 1 / 6 1 / 3 2 / 3 2 / 3 1 / 3 © Karin Haenelt, PageRank, 6.11.2015
p2
p3
1 / 3 2 / 9 7 / 27 20 / 81 1 / 3 2 / 9 7 / 27 20 / 81 1 / 3 2 / 9 13 / 27 41 / 81 78
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
79
Komplexität Anforderungen G hat ungefähr 25 Milliarden Spalten und Zeilen ungefähr 10 Einträge in jeder Spalte sind nicht 0
Austin, 2006 © Karin Haenelt, PageRank, 6.11.2015
80
Komplexität Lösung des Gleichungssystems mit Iteration Komplexität: Speicherplatz Speicherplatz: Matrix G, Vektor prm, Vektor prm+1 Komplexität: Berechnung Berechnung des PageRanks nicht mit hoher Präzision erforderlich hinreichende Konvergenz bei Millionen von Webseiten bei einer Größenordnung von 100 Iterationen (Page 2001:5)
© Karin Haenelt, PageRank, 6.11.2015
81
Anwendung des PageRank-Algorithmus Web-Crawler kundschaftet das Web aus und erstellt Volltext-Index PageRank-Vektor PageRank-Berechnung viel weniger aufwändig als die Erstellung eines Volltext-Indexes Konvergenz für das gesamte Web sehr schnell: wenige Stunden Anreicherung des Index um Vokabular aus den verlinkenden Dokumenten Stand: Page, 2001:7 Linktexte, Titel der verlinkenden Dokumente (Wills 2006): PageRank-Wert für mehr als 25 Milliarden Webseiten © Karin Haenelt, PageRank, 6.11.2015
82
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
83
Themenspezifischer PageRank-Wert in der bisherigen Betrachtung wurde α als gleichverteilt angenommen das ist aber nicht erforderlich Möglichkeit 1: Bildung thematischer Subnetze (z.B. Sport) (wie erkennt man Themen?) Seiten im betrachteten Subnetz erhalten α > 0, andere α = 0 → Einschränkung der weiteren Betrachtung auf das betretene Subnetz Möglichkeit 2: System arbeitet mit einer Hierarchie von Matrizen Matrix der Übergänge innerhalb eines Themas (z.B. Sport) Matrix der Übergänge zwischen Themen (z.B. Sport -> Politik) Manning/Raghavan/Schütze, 2007:317-323 © Karin Haenelt, PageRank, 6.11.2015
84
Themenspezifischer PageRank-Wert Möglichkeit 3: System lernt aus dem Klickverhalten
Manning/Raghavan/Schütze, 2007:317-323 © Karin Haenelt, PageRank, 6.11.2015
85
Mögliche Modifikationen Zusätzliche Parameter zur Berechnung des PageRanks Folgende Eigenschaften können berücksichtigt werden: eingehende Links Anzahl unterschiedlicher Institutionen, Autoren, Orte, Hauptseiten einer Domäne, … Eigenschaften der Links in einem verlinkenden Dokument Anfang des Dokuments Hervorhebung durch Fettdruck o.ä., .. Änderungsdatum der verlinkenden Seite (Aktualität) Klickverhalten Anzahl der Klicks auf die Seiten Page, 2001:7-9 © Karin Haenelt, PageRank, 6.11.2015
86
Mögliche Modifikationen Zusätzliche Parameter zur Berechnung des PageRanks Personalisierung Vergabe hoher initialer Page-Rank-Werte für die Webseite und die Lesezeichen von Nutzenden, hohe Wahrscheinlichkeit des Ansurfens dieser Seiten trainiert das System Seiten zu erkennen, die in Relation zur Webseite von Nutzenden stehen
Page, 2001:7 © Karin Haenelt, PageRank, 6.11.2015
87
Inhalt Entwicklung, Ziele, Grundidee Hyperlink-Matrix und PageRank-Vektor Wie berechnet man aus der Hyperlink-Matrix den PageRank-Vektor? Mathematische Betrachtungsvarianten Der Page-Algorithmus Konvergenzbedingungen und Modifikation der Matrix stochastisch, irreduzibel, aperiodisch die Google-Matrix Komplexität der Berechnung Personalisierung und Adaption an Nutzungsverhalten Zusammenfassung © Karin Haenelt, PageRank, 6.11.2015
88
Zusammenfassung PageRank-Verfahren PageRank-Verfahren gewichtet Webseiten nicht nach ihrem Inhalt sondern nach der Verlinkungsstrukur Verlinkungsstruktur wird als Graph repräsentiert Graph wird als Matrix repräsentiert PageRank-Vektor wird aus Matrix berechnet Matrix und PageRank-Vektor lassen sich betrachten als: Matrix Koeffizientenmatrix eines linearen Gleichungssystems Abbildungsmatrix
PageRank-Vektor Lösungsvektor des linearen Gleichungssystems
Übergangsmatrix eines Markov-Prozesses
Grenzvektor; stationäre Verteilung, bei der sich ein Markov-Prozess nach längerer Zeit invariant einpendelt
© Karin Haenelt, PageRank, 6.11.2015
pr (i ) =
∑
{ j | j →i }
Fixvektor der Abbildungsmatrix
pr ( j ) nj
x = Ax p ∞ = lim S n p0 n→∞
89
Zusammenfassung PageRank-Verfahren eine direkte Berechnung des PageRank-Vektors ist im Falle vieler Variablen zu komplex eine iterative Berechnung ist sehr schnell möglich eine approximative Berechnung mit wenigen Iterationen ist ausreichend Um die Berechnung partiell und iterativ durchführen zu können, muss die Matrix die Eigenschaften einer ergodischen Markov-Kette haben (stochastisch, irreduzibel, aperiodisch) Hierzu wird die Hyperlink-Matrix (H) erweitert um zusätzliche Links für Knoten ohne ausgehende Kanten (Matrix S) (stochastisch) und eine Konstante α (Matrix G) (irreduzibel und aperiodisch) © Karin Haenelt, PageRank, 6.11.2015
90
Zusammenfassung PageRank-Verfahren: Konstante α Die Konstante ist formal erforderlich, um die Konvergenz des approximativen Berechnungsverfahrens zu sichern: sie stellt sicher, dass die Matrix irreduzibel und aperiodisch ist (bei 0 ≤ α < 1). Die Werte der Konstanten beeinflussen die Konvergenzgeschwindigkeit: je kleiner α, desto schneller die Konvergenz
© Karin Haenelt,, 29.2.2016
91
Zusammenfassung PageRank-Verfahren: Konstante α Die Werte der Konstanten beeinflussen die Ergebnisse: 1-α kann als Modell des zufälligen Springens von einer Webseite zur nächsten ohne einem Link zu folgen aufgefasst werden. α wirkt als Dämpfungsfaktor, d.h. der Wert limitiert das Ausmaß, in dem ein PageRank-Wert von Kind-Knoten geerbt werden kann α = 1 (entspricht G = S): gegebene Hyperlinksstuktur + Korrektur für Knoten ohne ausgehende Kanten Achtung: Matrix kann reduzibel und periodisch sein (positive PageRank-Werte und Konvergenz nicht gesichert) α = 0 (entspricht G = 1/N 1): alle Knoten gleichgewichtig mit allen verbunden, gegebene Hyperlinkstruktur völlig verloren
© Karin Haenelt,, 29.2.2016
92
Zusammenfassung Suchergebnisse Unabhängigkeit von Queries hat das Ranking wesentlich beschleunigt PageRank lässt sich beim Indizieren berechnen in bestimmten Zeitabständen aktualisieren Verfahren kann aus Nutzungsverhalten lernen Ergebnis reflektiert nicht unbedingt die Relevanz einer Seite für die Anfragen der Nutzenden unpopuläre, aber für eine bestimmte Aufgabenlösungen höchst relevante Seiten werden möglicherweise nicht oder sehr spät präsentiert Neue Information ist erst nach einer gewissen Zeit gut verlinkt Die neue Qualität der Suchergebnisse gegenüber anderen Suchmaschinen hat Google zum Marktführer gemacht Vgl. Berry/Browne, 2005 © Karin Haenelt, PageRank, 6.11.2015
93
Literatur Patente Lawrence Page (2001), Method for node ranking in a linked database—Patent number 6,285,999—September 4, 2001 (Original PageRank U.S. Patent), http://patft.uspto.gov/netacgi/nph-Parser?patentnumber=6,285,999 und http://www.google.com/patents/US6285999 Lawrence Page (2004), PageRank U.S. Patent—Method for scoring documents in a linked database—Patent number 6,799,176—September 28, 2004 Lawrence Page (2006), PageRank U.S. Patent—Method for node ranking in a linked database—Patent number 7,058,628—June 6, 2006 Lawrence Page (2007), PageRank U.S. Patent—Scoring documents in a linked database—Patent number 7,269,587—September 11, 2007
© Karin Haenelt, PageRank, 6.11.2015
94
Literatur PageRank David Austin (2006), How Google Finds Your Needle in the Web’s Haystack. American Mathematical Society. Feature Column: Monthly Essays on Mathematical Topics. December, 2006. http://www.ams.org/samplings/feature-column/fcarc-pagerank (besucht: August 2013) Michael W. Berry und Murray Browne (2005). Understanding Search Engines. Mathematical Modelling and Text Retrieval. Philadelphia: Society for Industrial and Applied Mathematics (SIAM). Amy N. Langville & Carl D. Meyer (2006). Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press Edith Law (2008). Page Rank. Lecture. 9.10.2008. http://www.cs.cmu.edu/~elaw/pagerank.pdf
© Karin Haenelt, PageRank, 6.11.2015
95
Literatur PageRank Christopher Manning, Prabhakar Raghavan, Hinrich Schütze (2007) . Introduction to Information Retrieval. Kap. 21. Cambridge University Press. Rebecca S. Wills (2008). Google's PageRank for Beginners: A Directed Graph Example for Liberal Arts Math Courses. https://sites.google.com/site/rebeccawillswebsite/Home/papers_and_presentations/R SW_Mathfest_08_PageRank_2.pdf (besucht: August 2013) Rebecca S. Wills (2006). Google's PageRank: The Math Behind the Search Engine. http://www.cems.uvm.edu/~tlakoba/AppliedUGMath/other_Google/Wills.pdf (besucht: August 2013)
© Karin Haenelt, PageRank, 6.11.2015
96
Literatur Mathematische Grundlagen Michael Artin (1998). Algebra. Aus dem Englischen übersetzt von Annette A‘Campo. Basel, Boston, Berlin: Birkhäuser Verlag. Siegfried Bosch (2006). Lineare Algebra. Heidelberg: Springer Verlag. Ferdinand Georg Frobenius (1912). Über Matrizen aus nicht negativen Elementen, Berl. Ber. 1912, 456-477. elektronisches Faksimile: http://dx.doi.org/10.3931/e-rara-18865 Hans Otto Georgii (2015). Stochastik. Einführung in die Wahrscheinlichkeitstheorie und Statistik. 5. Aufl. Berlin: Walter de Gruyter. Hans Otto Georgii (2009). Stochastik. Einführung in die Wahrscheinlichkeitstheorie und Statistik. 4. Aufl. Berlin: Walter de Gruyter. Wolfgang Hackbusch (2004). Iterative Lösung großer Gleichungssysteme. www.mis.mpg.de/scicomp/Fulltext/ggl.ps (besucht: August 2013) Jim Hefferon (2012). Linear Algebra. 29.2.2012. http://joshua.smcvt.edu/linearalgebra
© Karin Haenelt, PageRank, 6.11.2015
97
Literatur Mathematische Grundlagen Jürgen Kunze (2013). Notizen zum PageRank-Verfahren. Internes Papier. HumboldtUniversität zu Berlin. 21.6.2013 Oskar Perron (1907). Zur Theorie der Matrices, Math. Ann. 64, 248-263. elektronisches Faksimile: http://gdz.sub.unigoettingen.de/dms/load/img/?PPN=GDZPPN002261693&IDDOC=36725
Folienversionen 1.2.1 29.2.2016 1.1.1 6.11.2015 1.1.0 9.11.2014 1.0.0 13.10.2013
© Karin Haenelt, PageRank, 6.11.2015
98
