Hans Humenberger Das PageRank-System von Google – ?· Google und seine Gründer • „Google“ –…

  • Published on
    04-Jun-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>Hans Humenberger</p><p>Das PageRank-System von Google eine aktuelle Anwendung im MU </p></li><li><p>Google und seine Grnder</p><p> Google etwas Riesengroes nach der unglaublichen Flle des WWW</p><p>Googol = 10^100 1938 durch E. Kasner (Amer. Mathematiker) etabliert: Neunjhriger Neffe sollte Wort erfinden . . . </p><p> Suchmaschinen untersuchen mit einem spider(webcrawler) das WWW: Mglichst gute Momentaufnahme der Inhalte und der Vernetzungsstruktur des WWW</p><p> Wie kommt man zu einer Reihung der Liste(wichtige Seiten zuerst)? </p><p> Neues Verbum: googeln bzw. to google</p></li><li><p>Lawrence (Larry) Page(geb. 1973 in USA): Master in Informatik, Stanford</p><p>Sergej Michailowitsch Brin(geb. 1973 in Moskau): Master in Informatik, Stanford </p><p>Programmierten 1996 eine Suchmaschine (keines der groen Portale heutige Konkurrenten interessierte sich dafr)</p><p>Grndung von Google 1998mit einer Starthilfe von 100.000 $ von Sun Microsystems. Suchmaschinen heute zweitwichtigste Internet-Anwendung (nach Email) </p><p>2009: Unternehmenswert: viele Milliarden $ (Brsegang 2004) Marktanteil: ca. 62% (Yahoo: 21%), ca. 3 Mrd. Anfragen/Tag</p><p>Internet-penetration-rates: Europa: 52%, NA: 74%, Welt: 26%</p><p>Angefangene Promotionen werden nicht weiterverfolgt, wozu auch?</p><p>L. Page S.M. Brin</p></li><li><p>Einstiegsbeispiel: 3 Telefongesellschaften, Wechsel der Kunden jeweils zu Jahresende nach folgendem Schema (gerichteter Graph): </p><p>Angenommen: konst. bergangsrate in den nchsten 5 (10, 20) Jahren</p><p>Verteilung der Kunden auf die Firmen, wenn zu Beginn (1/3, 1/3, 1/3)</p><p>bzw. (0.3, 0.5, 0.2)?</p></li><li><p>Z. B. mit EXCEL:</p><p>1 0,8 0,3 0,2n n n nA A B C+ = + +</p><p>1 0,1 0,6 0,1n n n nB A B C+ = + +</p><p>1 0,1 0,1 0,7n n n nC A B C+ = + +</p><p>EXCEL-File</p><p>Dies auch ohne Kenntnisse von Markoff-Ketten bzw. bergangsmatrizen mglich!</p><p>Dieses iterative Prinzip entspricht sogar der Praxis: </p><p>Lsungen von zugehrigen groen LGS nicht geschlossen, sondern nherungsweise, iterativ</p><p>Iterativ Grenzverteilung</p></li><li><p>Einfaches Bsp. mit 4 Webseiten</p><p>gerichteter Graph als Ergebnis der Durchforstung des WWW</p><p>Modellannahme: Bei allen von einer Seite ausgehenden Pfeilen dasselbe Gewicht, d. h. jedem von einer Seite ausgehenden Link wird mit gleicher W gefolgt</p><p> 2 ausgehende Pfeile: jeweils 1/2</p><p> 3 ausgehende Pfeile: jeweils 1/3</p><p>1</p><p>1</p><p>1</p><p>1</p><p>0,5 0,5</p><p>0,5 0,5 0,5</p><p>0,5</p><p>n n</p><p>n n n</p><p>n n n n</p><p>n n</p><p>C A</p><p>A D B</p><p>A B D C</p><p>B D</p><p>+</p><p>+</p><p>+</p><p>+</p><p>=</p><p>+ =</p><p>+ + =</p><p>=</p><p>Rekursionsgleichungen: </p><p>Bei welcher Verteilung auf die 4 Seiten werden sich die User la longue einpendeln?</p><p> EXCEL?</p></li><li><p>1</p><p>1</p><p>1</p><p>1</p><p>1</p><p>::</p><p>0 0 1 0</p><p>0,5 0 0 0,5</p><p>0,5 0,5 0 0,5</p><p>0 0,5 0 0</p><p>n n</p><p>n n</p><p>n n</p><p>n n</p><p>n n</p><p>vU v</p><p>A A</p><p>B B</p><p>C C</p><p>D D</p><p>+</p><p>+</p><p>+</p><p>+</p><p>+</p><p>==</p><p> = </p><p>Solche Situationen (LGS) auch gut mit Matrizen und Vektoren zu beschreiben:</p><p>Alle bergnge zwischen Verteilungen werden durch dieselbe </p><p>bergangsmatrix U vermittelt. Die Eintrge sind bergangswahrscheinlichkeiten: In Spalte i stehen die einzelnen bergangsWen i j, Spaltensummen = 1</p><p>1n nv v + </p><p>bergangsmatrix Verteilungsvektoren</p></li><li><p>0 1U v v = </p><p>( )</p><p>1</p><p>20</p><p>0 2</p><p>v</p><p>U v</p><p>U U v v</p><p> =</p><p>( )</p><p>2</p><p>1</p><p>30</p><p>0 3</p><p>v</p><p>v</p><p>U v</p><p>U U U v v</p><p> = </p><p>0</p><p>n</p><p>nU v v = </p><p>.</p><p>bergnge:</p><p>Explizite Darstellung fr (geschlossene Formel, nicht nur rekursive Darstellung).</p><p>Wichtig: Multiplizieren und Potenzieren von Matrizen, Assoziativgesetz der Multiplikation</p><p>nv</p></li><li><p>0 0 1 0</p><p>0,5 0 0 0,5</p><p>0,5 0,5 0 0,5</p><p>0 0,5 0 0</p><p>U</p><p> = </p><p>stochastischer Vektor: Eintrge aus [0;1]; Summe = 1</p><p>Verteilungsvektoren und bergangsmatrizen sind stochastisch!</p><p>stochastische Matrix: quadratisch, Spaltenvektoren stochastisch</p></li><li><p>Wichtigkeit einer Seite?Seite umso wichtiger, je mehr Seiten auf diese verweisen: Auf dieser Seite dann wohl tragende Standards bezglich des Suchbegriffes </p><p>Welche ist nun die wichtigste Seite in diesem Graph? </p><p>Idee: Viele User benutzen diese Netzstruktur; wenn sich langfristig beim Surfen 90% auf Seite X befinden, so ist diese wohl die wichtigste!</p><p>D. h.: Suche die Grenzverteilung; reihe die Wichtigkeit der Seiten nach den Werten in dieser.</p></li><li><p>0</p><p>0,25</p><p>0,25</p><p>0,25</p><p>0,25</p><p>v</p><p> = </p><p>Startverteilung z. B.: </p><p>1 0</p><p>0,25</p><p>0,25</p><p>0,375</p><p>0,125</p><p>v U v</p><p> = = </p><p> 2</p><p>2 1 0</p><p>0,375</p><p>0,1875</p><p>0,3125</p><p>0,125</p><p>v U v U v</p><p> = = = </p><p>A und C scheinen im Vorteil zu sein!</p><p>0</p><p>3/ 9</p><p>2 / 9</p><p>3 / 9</p><p>1/ 9</p><p>nn</p><p>nv U v v</p><p> = = </p><p> Grenzverteilung:</p></li><li><p>Grenzverteilung bestimmen</p><p>1) Mit EXCEL die Iteration so lange durchfhren, bis sich die Werte nicht mehr ndern</p><p>2) Mit CAS hohe Matrixpotenz bestimmen:</p><p>3) Gesucht ist ein stochastischer Vektor , der sich bei Multiplikation mit U nicht mehr ndert: </p><p>Lineares Gleichungssystem in den Variablen</p><p>0</p><p>nv U v n</p><p>Uv</p><p>U v v = </p><p>0,i</p><p>v 1iv =Probleme: 1) Kann es mehrere solche Grenzverteilungen geben (je nach Startverteilung)? Am besten wre eine eindeutige!</p><p>2) Obige Methoden zur Berechnung von funktionieren nur bei relativ kleinem m, aber nicht bei z. B. m = 1000 000 oder mehr (Google); hier iterative Nherungsverfahren!</p><p>v</p></li><li><p>Grenzwertsatz (Markoff, ohne Beweis): </p><p>U ist stochastisch und enthlt fr ein </p><p>nur positive Eintrge</p><p>Grenzmatrix existiert, ist stochastisch </p><p>und hat identische Spalten</p><p>1n nU</p><p>: lim nn</p><p>G U</p><p>=</p></li><li><p>Klar: die (ident.) Spalten dieser Grenzmatrix geben den eindeutigen, vom Startvektor unabhngigen Grenzvektor an: </p><p>0</p><p>01 1 1 1 1</p><p>02 2 2 2 2</p><p>03 3 3 3 3</p><p>04 4 4 4 4</p><p>vG</p><p>Au u u u u</p><p>Bu u u u uv</p><p>Cu u u u u</p><p>Du u u u u</p><p> = = </p><p>0 0 0 0 1A B C D+ + + =</p><p>1i</p><p>u =</p><p>Obiges Beispiel:</p><p>0 0 1 0</p><p>0,5 0 0 0,5</p><p>0,5 0,5 0 0,5</p><p>0 0,5 0 0</p><p>U</p><p> = </p><p>5</p><p>5 /16 5 /16 3/ 8 5 /16</p><p>9 / 32 1/ 4 1/ 8 9 / 32</p><p>11/ 32 11/ 32 5 /16 11/ 32</p><p>1/16 3/ 32 3/16 1/16</p><p>U</p><p> = </p></li><li><p>0 0 1/ 3 0 0 0</p><p>1/ 2 0 1/ 3 0 0 0</p><p>1/ 2 0 0 0 0 0</p><p>0 0 1/ 3 0 0 1/ 2</p><p>0 0 0 1/ 2 0 1/ 2</p><p>0 0 0 1/ 2 1 0</p><p>U</p><p>= </p><p>Ein etwas komplizierteres Beispiel und weitere Modellannahmen</p><p>Sackgasse bzw. Senke bei 2 , nur Nullen in der 2. Spalte, </p><p>U nicht mehr stochastisch!</p></li><li><p>0 0 1/ 3 0 0 0</p><p>1/ 2 0 1/ 3 0 0 0</p><p>1/ 2 0 0 0 0 0</p><p>0 0 1/ 3 0 0 1/ 2</p><p>0 0 0 1/ 2 0 1/ 2</p><p>0 0 0 1/ 2 1 0</p><p>U</p><p>= </p><p>Weitere Modellannahmen: 1) Rckkehr zur Liste </p><p>(nicht: Seite davor, Ende)</p><p>1/ 6</p><p>1/ 6</p><p>0 1/ 6 1/ 3 0 0 0</p><p>1/ 2 1/ 6 1/ 3 0 0 0</p><p>1/ 2 1/ 6 0 0 0 0*</p><p>0 1/ 6 1/ 3 0 0 1/ 2</p><p>0 1/ 6 0 1/ 2 0 1/ 2</p><p>0 1/ 6 0 1/ 2 1 0</p><p>U</p><p>= </p><p>stochastisch!*U</p><p>2) Zuflliges Anklicken einer Seite, alle Seiten beim Neueinstieg gleichwahrscheinlich: 1/6 (1/m)</p><p>Ausweg bei Sackgasse? </p><p>Obiges Bsp.: Ersetzen der Nullenspalte durch:</p></li><li><p>Dadurch auf den Plan gerufen Verbesserung des Modells: Rckkehr zur Liste und erneuter zuflliger Einstieg</p><p>ist immer mglich, auch ohne Sackgasse! Mathematische Beschreibung dieses Szenarios?</p><p>2) Zuflliger Neueinstieg mit W : </p><p>nchste Verteilung muss gegeben sein durch: 1/</p><p>1/</p><p>m</p><p>m</p><p>bergangsmatrix: </p><p>1</p><p>stochastisch 1</p><p>1/ 1/ 1/</p><p>1/ 1/ 1/</p><p>i</p><p>m</p><p>v</p><p>m m v m</p><p>m m v m</p><p>=</p><p> = </p><p>1) Weitersurfen mit W : bergangsmatrix *U=</p><p>1 </p><p>Allgemein zwei Flle mglich: </p></li><li><p>Kombination:</p><p>Mit W' denLinks folgen</p><p>Mit W' (1 ) neu einsteigen</p><p>1/ 1/</p><p>* (1 )</p><p>1/ 1/</p><p>m m</p><p>T U</p><p>m m</p><p>= + </p><p>Neue bergangsmatrix T (wieder stochastisch):</p><p>Entscheidender Vorteil dieser bergangsmatrix T:</p><p>T hat nur mehr positive Eintrge!</p><p>Nach obigem Grenzwertsatz gibt es also jedenfalls eine Grenzverteilung, die sogar unabhngig von der Startverteilung ist!</p><p>Durch diese Grenzverteilung: Reihung der Seiten mglich (Wichtigkeit)</p></li><li><p>Der Wert von ist hierbei sehr wichtig: Google whlte lange Zeit</p><p>0,85 =</p><p>Unser Beispiel mit1/ 40 1/ 6 37 /120 1/ 40 1/ 40 1/ 40</p><p>9 / 20 1/ 6 37 /120 1/ 40 1/ 40 1/ 40</p><p>9 / 20 1/ 6 1/ 40 1/ 40 1/ 40 1/ 40</p><p>1/ 40 1/ 6 37 /120 1/ 40 1/ 40 9 / 20</p><p>1/ 40 1/ 6 1/ 40 9 / 20 1/ 40 9 / 20</p><p>1/ 40 1/ 6 1/ 40 9 / 20 7 / 8 1/ 40</p><p>T</p><p>= </p><p>0,85: =</p><p>Zu lsendes lineares Gleichungssystem: T v v = </p><p>1</p><p>06</p><p>, 1i</p><p>v</p><p>v v</p><p>v </p><p>= = </p><p>1/ 1/</p><p>* (1 )</p><p>1/ 1/</p><p>m m</p><p>T U</p><p>m m</p><p>= + </p></li><li><p>CAS (4 NK-Stellen):</p><p>0,0517</p><p>0,0737</p><p>0,0574</p><p>0,1999</p><p>0, 2686</p><p>0,3487</p><p>v</p><p>= </p><p>Resultat (Reihung nach Wichtigkeit): Seite 6 Seite 5 Seite 4 Seite 2 Seite 3 Seite 1</p><p>In der Realitt (m = 1000 000 und mehr) funktioniert dieses Lsen eines LGS nicht mehr geschlossen (Gau-Algorithmus), sondern nur mehr nherungsweise: iterativ </p></li><li><p> Allgemein: -) Einen Link auf der Seite benutzen mit W-) zuflliger Neueinstieg mit W</p><p>Die wichtigen Modellierungen im Kern:</p><p> Alle Links auf einer Seite haben gleiche W</p><p> Sackgasse: Rckkehr zur Liste und zuflliger Neueinstieg, d. h. ersetze alle Nullen in der Spalte durch 1/m</p><p>Mit W' denLinks folgen</p><p>Mit W' (1 ) neu einsteigen</p><p>1/ 1/</p><p>* (1 )</p><p>1/ 1/</p><p>m m</p><p>T U</p><p>m m</p><p>= + </p><p>1 </p><p>einfache Modellierungen (nicht selbstndiges Modellieren!), aber beachtliche Tragweite!</p></li><li><p>Potential im Schulunterricht</p><p> Spannendes und aktuelles PhnomenRealittsbezug: Jeder verwendet Google!Besttigung: Grundlegende Ideen sind bedeutungsvoll!</p><p> Sichtbarmachen, wie Mathematik in der modernen Gesellschaft angewendet wird; Mathematik wird immer weniger wahrgenommen, ist aber gesellschaftlich sicher eine Schlsseltechnologie</p><p> Motivation, Verblffung: Mit welch elementaren Ideen ist etwas Weltbewegendes auf die Beine zu stellen und viel Geld zu verdienen</p><p> Beitrag zum einfachen Modellbilden (nicht selbstndig durch S&amp;S)</p><p> Wenige Voraussetzungen: Matrizen und VektorenIn einem deutschen Schulbuch: 2-stufige Prozesse zur Einfhrung der Matrizenmultiplikation(auch als zustzliche sinnvolle Anwendung mglich)</p><p> Sinnvoller Computereinsatz: EXCEL, CAS</p></li><li><p>Potential im Schulunterricht</p><p> Gute Vernetzungsmglichkeit: Stochastik, LA, Analysis</p><p> Mglicher Einstieg in das Thema Markoff-Ketten (fr WPF), oder eine zustzliche aktuelle Anwendung</p><p> Theorie der Grenzwertstze bei Markoff-Ketten nicht ntig, bei Bedarf knnen auch einfache theoretische Aspekte bercksichtigt werden</p><p> Mglichkeit, elementare iterative Methoden fr LGS zu behandeln (Jacobi- oder Gau-Seidel-Verfahren, EXCEL)</p><p> Werbung fr Mathematik: Riesenkarriere mglich durch kluge Verarbeitung ebenso einfacher wie genialer Ideen!</p></li><li><p>Deutschland 2009:</p><p>Google Zeitgeist</p></li><li><p>sterreich 2009:</p></li><li><p>Weltweit 2009</p><p>USA 2009</p></li><li><p>LiteraturH. H. (2009): Das Google-PageRank-System Mit Markoff-Ketten und linearen Gleichungssystemen Ranglisten erstellen. In: mathematiklehren154 (Juni 2009), 5863.</p><p>H. H. (2009): Das PageRank-System von Google eine aktuelle Anwendung im Mathematikunterricht. In: Beitrge zum Mathematikunterricht 2009, 663666. WTM-Verlag, Mnster. Auch online unter:http://www.mathematik.uni-dortmund.de/ieem/BzMU/BzMU2009/Beitraege/HUMENBERGER_Hans_2009_google.pdf</p><p>H. H.: Homepage</p><p>H. H. (2012): nchstes MG-Didaktik-Heft</p></li><li><p>Jacobi-Verfahren 11 1 12 2 13 3 1</p><p>21 1 22 2 23 3 2</p><p>31 1 32 2 33 3 3</p><p>a x a x a x b</p><p>a x a x a x b</p><p>a x a x a x b</p><p>+ + =</p><p>+ + =</p><p>+ + =</p><p>LGS sei eindeutig lsbar, Diagonalelemente (sonst Zeilen- bzw. Spaltentausch)</p><p>0ii</p><p>a </p><p>( )</p><p>( )</p><p>( )</p><p>1 12 2 13 3 1 11</p><p>2 21 1 23 3 2 22</p><p>3 31 1 32 2 3 33</p><p>/</p><p>/</p><p>/</p><p>x a x a x b a</p><p>x a x a x b a</p><p>x a x a x b a</p><p>= +</p><p>= +</p><p>= +</p><p>( )</p><p>( )</p><p>( )</p><p>( 1) ( ) ( )</p><p>1 12 2 13 3 1 11</p><p>( 1) ( ) ( )</p><p>2 21 1 23 3 2 22</p><p>( 1) ( ) ( )</p><p>3 31 1 32 2 3 33</p><p>/</p><p>/</p><p>/</p><p>k k k</p><p>k k k</p><p>k k k</p><p>x a x a x b a</p><p>x a x a x b a</p><p>x a x a x b a</p><p>+</p><p>+</p><p>+</p><p>= +</p><p>= +</p><p>= +</p><p>Auflsen von Zeile i nach : i</p><p>x</p><p>EXCEL-File</p><p>( )(0) (0) (0)1 2 3, ,x x xStartwerte</p></li></ul>