diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/google.tex | 175 |
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} + + |