aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/80-wahrscheinlichkeit
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/google.tex175
1 files changed, 172 insertions, 3 deletions
diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex
index 34beae2..bb5597d 100644
--- a/buch/chapters/80-wahrscheinlichkeit/google.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/google.tex
@@ -240,7 +240,7 @@ entlang eines Links.
\begin{beispiel}
Für das Beispiel-Internet von Abbildung~\ref{buch:figure:modellinternet}
ist die zugehörige Matrix
-\[
+\begin{equation}
H =
\begin{pmatrix}
0 & 0& 0 & 0 & 0 & 0&\frac12& 0 \\
@@ -252,8 +252,9 @@ H =
0 & 0& 0 & 0 &\frac13& 0& 0 &\frac12\\
0 & 0& 0 & 0 &\frac13& 1&\frac12& 0
\end{pmatrix}.
+\label{buch:google:eqn:linkmatrixbeispiel}
+\end{equation}
\qedhere
-\]
\end{beispiel}
%
@@ -304,7 +305,7 @@ P(S'_j|\overline{F}) = \sum_{i=1}^N P(S'_j|S_i) P(S_i).
\]
oder in Vektorform
\[
-(P(S'_j|\overline{F}))_j
+(P(S'_j|\overline{F}))_{j=1,\dots,n}
=
Hp.
\]
@@ -421,12 +422,180 @@ heisst die
\index{Google-Matrix}%
\end{definition}
+Die Google-Matrix wurde von Sergei Brin und Larry Page
+in dem Artikel \cite{BRIN1998107} als Basis der Suchmaschine
+Google beschrieben.
+Sie war die Basis für den Erfolg von Google und wird dem Prinzip nach
+auch heute noch zur Rangierung der Suchresultate verwendet.
+Dazu muss natürlich die Gleichung $p=Gp$ gelöst werden, was
+weiter unten in Abschnitt~\ref{buch:subsection:wahrscheinlichkeitsverteilung}
+diskutiert wird.
+
+Natürlich ist die heutzutage verwendete Matrix mit Sicherheit komplizierter.
+In der vorgestellten Form unterstützt sie zum Beispiel auch das folgende
+Geschäftsmodell, welches in der Anfangszeit von Google eine Zeitlang
+erfolgreich war.
+Ein Anbieter betreibt zu diesem Zweck eine grosse Zahl von Websites,
+deren Seiten im Wesentlichen aus Suchbegriffen und Links untereinander
+und auf die Website des Kunden verweisen.
+Dadurch entsteht für die Google-Matrix der ``Eindruck'', dass sehr viele
+Websites gibt, die die Kundenwebsite als relevant für die Suchbegriffe
+ansehen.
+Die Kundenwebsite wird daher in den Suchresultaten weiter oben gezeigt.
+Das Problem rührt natürlich daher, dass alle Links als gleichermassen
+aussagekräftig betrachtet werden.
+
+Die aktuell verwendete Variante der Google-Matrix ist natürlich ein
+Betriebsgeheimnis der Firma Google.
%
% Bestimmung der zu erwartenden stationären Verteilung
%
\subsection{Wahrscheinlichkeitsverteilung
\label{buch:subsection:wahrscheinlichkeitsverteilung}}
+Die Google-Matrix $G$ selbst interessiert weniger als die
+Wahrscheinlichkeitsverteilung $p$.
+Ziel dieses Abschnittes, ist den Vektor $p$ zu berechnen.
+
\subsubsection{Stationäre Verteilung}
+Die Einträge $P(S_i)$ des Vektors $p$ geben die Wahrscheinlichkeit an, mit
+der sich ein Benutzer auf der Seite $i$ befindet.
+Wir interpretieren diese Wahrscheinlichkeit auch als ein Mass für die
+Relevanz einer Seite.
+
+Wir nehmen an, dass sich diese Wahscheinlichkeit nur langsam ändert.
+Diese Annahme trifft nicht zu für neue Nachrichten, die durchaus eine
+hohe Relevanz haben, für es aber noch nicht viele Links geben kann,
+die die Relevanz in der Google-Matrix erkennbar machen.
+Die Annahme bedeutet, dass sich die Verteilung $p$ sehr viel langsamer
+ändert als der Navigationsprozess entlang der Links erfolgt.
+In erster Näherung ist es daher zulässig, nach einem Vektor $p$ zu
+suchen, der sich unter Navigation nicht ändert, also nach einer
+{\em stationären} Lösung.
+\index{stationäre Verteilung}%
+
+Für eine stationäre Wahrscheinlichkeitsverteilung gilt $p'=p$.
+Der Vektor $p$ erfüllt daher die Gleichung
+\begin{equation}
+Gp = p.
+\label{buch:google:ewgleichung}
+\end{equation}
+$p$ ist also ein Eigenvektor der Matrix $G$ zum Eigenwert $1$.
+
+Für ein sehr kleines Netzwerk wie im oben dargestellten Beispiel ist es
+einfach, mit verbreiteten numerischen Algorithmen alle Eigenwerte und
+Eigenvektoren zu finden.
+Benötigt wird allerdings nur der Eigenvektor zum Eigenwert $1$.
+
+\begin{beispiel}
+Ein Eigenvektor zum Eigenwert $1$ der Matrix $G$, die aus der Matrix $H$
+von \eqref{buch:google:eqn:linkmatrixbeispiel}
+und dem Vektor $q=\frac18u$ und $\alpha=0.9$ gebildet wurde, ist
+\[
+p_0=\begin{pmatrix}
+ 0.20100\\
+ 0.25440\\
+ 0.12163\\
+ 0.26014\\
+ 0.16394\\
+ 0.45543\\
+ 0.37739\\
+ 0.66007
+\end{pmatrix}
+\qquad\Rightarrow\qquad
+p
+=
+\frac{1}{\|p_0\|_1}p_0
+=
+\begin{pmatrix}
+ 0.080595\\
+ 0.102004\\
+ 0.048769\\
+ 0.104305\\
+ 0.065735\\
+ 0.182609\\
+ 0.151320\\
+ 0.264664
+\end{pmatrix}.
+\]
+Der Vektor $p_0$ ist ein Einheitsvektor in der euklidischen Norm.
+Er kann daher nicht eine Wahrscheinlichkeitsverteilung sein,
+da sich die Elemente nicht zu $1$ summieren.
+Die $L^1$-Norm $\|\;\cdot\;\|_1$ eines Vektors ist die Summe der Beträge aller
+Elemente eines Vektors.
+Indem man $p_0$ durch die Summe aller Einträge von $p_0$ teilt,
+erhält man die Wahrscheinlichkeitsverteilung $p$.
+\end{beispiel}
+
+
\subsubsection{Potenzverfahren}
+Die üblichen Algorithmen wie der Francis-Algorithmus zur Bestimmung
+von Eigenwerten und Eigenvektoren ist für grosse Matrizen nicht praktikabel.
+Da aber $1$ der betragsgrösste Eigenwert ist, kann sehr oft ein zugehöriger
+Eigenvektor mit der nachfolgend beschriebenen {\em Potenzmethode}
+gefunden werden.
+
+Sei $A$ eine $n\times n$-Matrix, der Einfachheit halber nehmen wir an,
+dass die Eigenwerte $\lambda_1>\lambda_2\ge \dots\ge \lambda_n$
+absteigend geordnet sind,
+und dass $v_1,\dots,v_n$ zugehörige linear unabhängige Eigenvektoren sind.
+Ein beliebiger Vektor $v$ lässt sich in der Eigenbasis von $A$
+als
+\[
+v = a_1v_1+\dots+a_nv_n
+\]
+ausdrücken.
+Wendet man darauf die Matrix $A$ $k$-mal an, erhält man
+\[
+A^kv
+=
+a_1\lambda_1^k v_1
++
+a_2\lambda_2^k v_2
++
+\dots
++
+a_n\lambda_2^k v_n.
+\]
+Da $\lambda_1$ der betragsmässig grösste Eigenwert ist, wird der Vektor
+$A^kv$ ungefähr mit der $k$-ten Potenz anwachsen.
+Indem man durch $\lambda_1^k$ teilt, erhält man
+\[
+\frac{1}{\lambda_1^k} A^k v
+=
+a_1v_1
++
+a_2\biggl(\frac{\lambda_2}{\lambda_1}\biggr)^k v_2
++
+\dots
++
+a_n\biggl(\frac{\lambda_n}{\lambda_1}\biggr)^k v_n.
+\]
+Da alle Brüche Betrag $<1$ haben, konvergiert die rechte Seite für $k\to\infty$
+gegeben den ersten Summanden.
+Durch wiederholte Anwendung von $A/\lambda_1$ auf einen (fast) belieibigen
+Startvektor $v$ erhält man also eine Folge von Vektoren, die gegen eine
+Eigenvektor zum Eigenwert $\lambda_1$ konvergiert.
+
+Numerische Ungenauigkeiten können bewirken, dass die Iteration mit der
+Matrix $A/\lambda_1$ trotzdem nicht konvergiert.
+Man kann dies komponsieren, indem man nach jeder Iteration normiert.
+Da der gesuchte Eigenvektor eine Wahrscheinlichkeitsverteilung sein muss,
+muss die $L^1$-Norm $1$ sein.
+Statt mit der euklidischen $L^2$-Norm zu normieren, normiert man daher
+besser mit der $L^1$-Norm.
+Damit ergibt sich das folgende Verfahren zur Bestimmung der Pagerank-Verteilung
+$p$ für die Google-Matrix.
+
+\begin{satz}
+Für die Google-Matrix $p$ konvergiert die Folge
+\[
+p^{(0)} = u,
+\qquad
+p^{(k+1)} = \frac{G^{(k)}}{\| G^{(k)} \|_1}
+\]
+gegen die stationäre Verteilung $p$ mit $Gp=p$.
+\end{satz}
+
+