[Playlisten] [Impressum und Datenschutzerklärung]

07E.2 Idee hinter Google PageRank, Übergangsmatrix, Eigenwert 1


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

wir – sehen uns etwas anders erst überhaupt nicht nach Matrizen aussieht – ?? eigen werden Eigenvektoren aussieht nämlich Links auf Webseiten – immer vier zum Beispiel zu haben – vier Webseiten – habe CD – Komma – und die sollen verlinkt sein ?? die Webseite – A soll einen Link zu B haben – also dass sie auf der Webseite A klicken können – um zu Webseite B zu kommen ?? die Webseite B soll einen Link haben zur Webseite A kommt sie wieder zurück – und zur Webseite C – und die – Webseite D soll auch ein Link haben zur Webseite A – stellen sich das vorrangig mit vier Webseiten sondern mit Milliarden Webseiten dann haben sie nur ?? bessere Idee auch ?? mit vieren hinkriegen – er dann ?? wir was weicht auch mit Milliarden hinkriegen – die Frage ist zum Beispiel die Frage die sich die beiden Gründer von Google gestellt haben wie kann ich jetzt solche Webseiten – bewerten welche sind wichtig – welche sind weniger wichtig – offensichtlich sind welche wichtig – die von vielen – als Links angegeben werden – diese Webseite Ade scheint hier wichtiger zu sein als andere – die Stadt unwichtig zu sein – D hat keiner verlinkt aber Arzt von zweien verlinkt das schon wichtig zu sein es könnte natürlich nicht nur einfach zählen – wie viele Dingsda eingehen – auf der Webseite – es könnte nämlich sein dass die Situation so aussieht – jemand baut ein Mini Universum – von lauter Webseiten – die auf eine Webseite verweisen – aber das große Internet das Leben eben an und hat überhaupt nichts damit zu tun – dann ist diese Webseite nicht wichtig Komma nämlich keiner hin muss das im großen Ganzen betrachten man kann nicht einfach nur gucken mir kommen jetzt zwei Links rein das hilft uns nicht an will wissen wie jetzt der Fluss sozusagen – hier passiert wenn Leute da Durchklicken durch diese Webseiten – wie häufig sind sie vor – dass es die ersten Ideen so – hinter Google gewesen – der sogenannte Page Frank – gewann Herrn die beiden Gründer Page und beim – Arbeitgeber geschrieben ganz zu Beginn muss es beschrieben haben den sogenannten Patch Schrenk Wortwitz wegen des Gründers Page – die Grundidee dahinter was sie vorführen ist nicht genau der Patch bringt aber die Grundidee dahinter sich vorzustellen und jetzt habe ich hier einen Server – eines Server sind die einfach auf Links klickt – der Seite A darunter muss immer zur Seite B kommen – auf der Seite B kann ich mich entscheiden fifty-fifty klicke ich zurück – zu A Komma oder glücklich so das ich zu C Komma was fehlt mir noch glaube ich sie sollte ?? zwar verlinken Beistrich müsse langweilig und gemein mehr – auf der Webseite die Energie zu einigen komme ich ?? zwar – und so weiter und so weiter das stelle ich mir vor was ist wenn ich so einen Server modellieren – der immer nur auf Links klickt die ganze Zeit auf Linksklick – wenn so ein Link gibt okay – dann auf den einen Link klicken – ?? wenn es zwei Links gibt hier wie bei B ein wenig zufällig einen von den beiden X – das heißt man könnte sagen wenn ich auf AHA bin – dann gehe ich mit einer Wahrscheinlichkeit – von eins nach B – wenn ich auf der Seite B bin ich mit Wahrscheinlichkeit – ein halb – zur ?? hin und genoss Heiligkeit von ein halb zu ziehen – wenn ich ins See bin – ich muss doch noch mehr als eine Messe so langweilig wird oder wenn ich in C bin – ich mit der Äußerlichkeit von ein halb zu B – O und ein halb zu A – wenn ich in DB hingegen Äußerlichkeit von eins zu haben – das wäre ein Modell – das man – jeden Link mit der gleichen Wahrscheinlichkeit anklickt – und dann überlegt man sich wo sind jetzt die Leute – typischerweise – zulassen jemanden das Millionen Mal machen und gucken irgendwann mal wieder hin mit welcher Wahrscheinlichkeit – ist die Person auf A auf B auf C auf D – und das wird dann im Endeffekt – mit bisschen – Finessen noch wird der Page Frank wenn jemand zufällig klickt und lügt und lügt und klickt und sie gucken dann nach drei Tagen drauf – wo sind wir dann typischerweise – mit welcher Wahrscheinlichkeit sind wir auf A auf B auf C dürfte – das Wetter beschränkt werden – dass es lustigerweise auch wieder was mit Matrizen zu tun – man kann das ganze als Matrix hinschreiben – kommen von einer bestimmten Seite – habe ICD – von – ICD – und sie gehen zu einer bestimmten Seite – A – B C – D diese Wahrscheinlichkeiten – kann ?? letzte Sondermatrix – reinschreiben – ?? ich komme von A – dann – gehe ich auf jeden Fall – nach B – Komma von A – hier nicht nach A – ich gehe nach B ich gehe nicht achtzig gehen ich dachte – so könnte das aussehen man das als Matrix dann aufschreibt – wenn ich von – B – Komma was schreiben Sie die nächste Spalte rein ✂ hier – brauchen wir also ein halb von B – Wahrscheinlichkeit – ein halb nach A zurückkommen Äußerlichkeitseinheit – nach C hier ein halb – ansonsten nichts – von C – ?? Äußerlichkeit ein halb zu A nur scheinbar ?? zu B – ein halbeinhalb – sonst nichts und von Thesen sehen Sie jedes mit Äußerlichkeit von eins zu A und ansonsten – nirgends wohin das Ganze als Matrix geschrieben – es ist bis dahin erst mal nur nach Art ?? Tabelle aufzubauen – das scheint erst mal nichts mit Matrizenrechnung – zu tun zu haben der Witz ist es diese Matrix tatsächlich – als Matrix – keinen Sinn ergibt – sollte als Fußnote anmerken normalerweise – wird man die transponiert Schreiben – als Übergangsmatrix – verteilt wahrscheinlich ?? gesehen Übergangsmatrix – ich das wirklich mal so – das er mit dem Formalismus weiter arbeiten können den ?? hatten – diese Matrix die nenn ich mal – definiert – als ähm die nenn ich mal ähm – sie überlegen sich was ist das Quadrat von ähm – was ist die dritte Potenz von M – und was bedeutet das wenn ich diese Matrixquartiere – und was bedeutet das jetzt für diese Anwendung wenn ich diese Matrix in die dritte Potenz setze ✂ mal – auf die Schnelle gleich ?? Computer – auf die Schnelle immer gerade – links oben die erste – Spalte mal die erste Zeile sollte seine erste Zeile war die erste Spalte zu Stammzellen – die Schranke Matrix im Zusammenleben nannte – links oben – wird werden die erste Zeile – war die erste Spalte – null ein halbeinhalb eins mal null eins null null – das einzige was bleibt ist es ein halb mal eins – also ein halb – der da drunter – ich will die zweite Zeile mal die erste Spalte haben für den darunter – ?? null mal eins Minuten – überlebt nichts interessanterweise – das bleibt also null – Komma zum Beispiel – den rechts daneben – erste Zeile zweite Spalte – erst seine zweite Spalte – null mal ein halbeinhalb – mal null ein halb mal ein halb Komma null einhalb mal ein halb oder einmal oder in Mathe war mit ein halbhalb bleibt hier steht also ein viertel ✂ so – es kommen werde minder ungemütlich Matrizen raus man das so weiter macht – was heißt denn das jetzt – die zweite Potenz von dieser Matrix – wieder schon ein Gefühl für – was heißt denn jetzt die zweite Potenz dieser Matrix was heißt die dritte Potenz der Matrix – bestimme ich damit eigentlich ✂ also – im Quadrat sagt Ihnen was nach zwei Klicks passiert – wenn sie von A kommen – wenn sie von A kommen – sind sie nach zwei Klicks mehr Wahrscheinlichkeit von ein halb wieder bei A gelandet – sie kommen von A – dann können Sie zu B gehen – oder müssen sogar zu begehen und dann haben sie die Wahl – geht zurück zu A oder gehen Sie zu C nach zwei Klicks sind Sie mit Wahrscheinlichkeit von ein halb wieder bei AA angekommen – wenn sie von Arstaaten – und so weiter und so weiter – das sagt Ihnen das Quadrat der Matrix das könnte man jetzt Nummer ausbuchstabieren – wie das zustande kommt für dieses Produkt – der beiden Matrizen – durch das jetzt vorliegende man sich auf weiteres Komma sie verständigen sie als Baum auf mal von A Gensina und so weiter und so weiter das ist genauso mit dem Produkt der Matrizen ausrechnen – wir summieren entlang der verschiedenen Fahrdiebe haben durch sein Baum und die dritte Potenz wird dann sein was nach drei Klicks wenn ich von A starte – bin ich nach drei Klicks – mit Äußerlichkeit von drei Vierteln bei B bin ich immer einen zufälligen Blick und so weiter soweit sie sie sind nie – nach drei Klicks in die – weil sie werden mit jedem Klick sofort – weg sein von den so kann man das betreiben und jetzt angemerkt diese Potenzen ausrechnen ist – lustig – glücklicherweise – gibt es ja passende Software sie sowas kann auch der ?? ist – in weiten Zügen wie matlap – aber – Open Source – Komma damit – diese – Matrixpotenzen – ausrechnen also an meine Matrix ähm soll sein – eckige Klammer auf – null – einhalb – halb eins für die erste Zeile Return – eins null – einhalb – null für die zweite Zeile – null einhalb – null null – ?? für die dritte Zeile null null – null – eckige Klammer zu – für die vierte Zeile – extravagant – Semikolon dahinter dass ich es Sommer die Matrix hier nicht der ?? eingegeben habe – wollen ?? eins null – gut sieht gut aus – die zweite Potenzmatrix – hoch zwei – im ?? genannt – das ist die zweite Potenz – haben wir – so rausbekommen – die dritte Potenz – Punkt natürlich groß M – wird auch so was will – man – ja – was ich jetzt natürlich hier machen kann ist zu sagen wir nehmen mal die – CD Potenz – das Wort jetzt nicht zu Fuß rechnen – zehnte Potenz der Matrix was es nach zehn Mausklicks ?? ich klicke zufällig – immer wieder die Links an wenn ich mir auf einer Seite habe – ich mir gleich verteilt einen Gas aus was es nach zehn Klicks – und an denen sie das scheint sich allmählich einzupendeln – dass es noch hundert Klicks – hat sich das schon sehr verdächtig eingependelt nach hundert Klicks liegen sie also – mit egal wo sie gestartet sind wenn sie mit A gestartet sind mit der Seite A gestartet sind oder mit B oder mit CD gestartet sind nach hundert sechs liegen sie mit – drei dreißig Prozent Wahrscheinlichkeit – auf A mit vierundsiebzig Prozent Wahrscheinlichkeit – auf B mit zwanzig Prozent Persönlichkeit auf C und mit null Prozent wahrscheinlich auf die das wäre dann – im großen Ganzen nicht genau aber im Großen und Ganzen vom Prinzip her der Page Frank das man sagt die Seite B kriecht ein Pagering von null Komma vier vier die Seite Arglisteinbettung – von null Komma drei drei wo landet man typischerweise – was ist die richtige Seite – wichtigste Seite scheint mir zu sein die unwichtigste – Idee zu sein – Punkt die hat jetzt gewiss gezeichnet habe sind sie – zwei eingehende Links A hat aber sogar – drei eingehende Links ist das ich interessant trotzdem gewinnt die ?? wird typischerweise auf der Seite B sein – als dieses ganze Netzdurchsagen – so verstört – das die am häufigsten besucht wird B hätte den höchsten Page Frank – obwohl es weniger eingehende Links hat als A – nichtsdestotrotz – wenn sie das B hier – gewinnt – Garbo sie starten – sie werden nach – hundert X – mit vierzig Prozent Wahrscheinlichkeit auf B gelandet sein – Komma ?? mal ein paar andere Eigenschaften von dieser Matrix – uns angucke – ?? das ist das transponiert – der Übergangsmatrix – normalerweise wird man Übergangsmatrizen – transponiert – stürzen seinen Spalten vertauschen ?? ich finde sie jetzt für uns einfacher – das wäre mit Website stellt sich irgendwelche Zustände vor in einem Spiel die Figur läuft die Figur springt die Figur schläft was auch immer und hundert Übergangswahrscheinlichkeiten – zwischen den Zuständen des typischerweise meinen Haaren herbeigezogen – mag auf Ketten wenn sich das dann professionell die kommen zwar professionell wirklich vor aber die Beispiele die man üblicherweise angeht sind haarsträubend – bis auf die Geschichte mit dem Webseiten weil das ist tatsächlich die Grundidee – hinter dem Ring in Google – das man sich hier Übergangswahrscheinlichkeiten – ein Punkt zwischen Webseiten – dann überlegt was wird sich der nach langer Zeit einstellen – dieser Matrix hier war das – in Ordnung – sind alle Spalten – sind – zu den gleichen Vektoren geworden – Punkt ein Beispiel an wo das nicht stattfindet – aber – ?? Komma zurück – Eigenwerte Eigenvektoren – was fehlt Ihnen jetzt auf von ✂ wegen Eigenwerten – und Eigenvektoren – kommt die jetzt ins Spiel – haben – also ein Eigenvektor – zum Eigenwert eins gefunden wenn sie Staaten mit dieser Wahrscheinlichkeitsverteilung – sind dreiunddreißig Prozent auf der Seite A mit vierundvierzig Prozent auf der Seite B zwanzig Prozent auf der Seite C – gar nicht auf der Seite die die Staaten mit dieser Verteilung – der machen sie einen Schritt – diese genau diese Verteilung wieder raus war mein Eigenvektor gefunden zum Eigenwert eins – interessanterweise – diese Verteilung die man versucht eigentlich mehr der Manager Page Frank ist ein Eigenvektor – zum Eigenwert eins – stellt das wahrscheinlicher mit einer einzigen Person vor sie stellen sich persönlich vor sie haben dreiunddreißig – tausend drei hundert dreiunddreißig Leute auf der Seite A sie haben vierundvierzig tausend vier hundert vierundvierzig Leute auf der Seite B zwanzig tausend ?? auf der Seite zielt niemanden auf der Seite die – jeder klickt einmal zufällig – nahm sie wieder drei dreißig tausend hundert dreiunddreißig auf der Seite A und so weiter und so weiter – mit einer Person dann mehr vorstellen sondern wirklich mit Millionen Milliarden Menschen vorstellte dann jeweils – klicken – und diese Verteilung die bleibt dann so wie sie ist ein Eigenvektor zum Eigenwert eins – ist – nicht immer so man kann – andere Beispiele kosten im Vergleich noch wo das nicht so hundertprozentig ?? hinkommt aber das ist die Idee dahinter dass das stationär bleibt – das Matrizen von dieser Art immer – einen eigenen – Wert eins haben müssen ist Klammer zu Nummer überlegen – als Wiederholung für diese Formel mit Determinante – Matrixministern – der Einheitsmatrix – schafft das mal so diese Matrix hat einen Eigenwert einzelne analog aller Sprechen konstruierten Matrizen – kam immer ein Eigenwert eins – das überlegen uns gerade mal denn – mich interessiert folgendes – Lambda – ist ein Eigenwert – dieser Matrix ähm – genau dann wenn jetzt kommt diese übliche Formel – die Matrix ähm Minuslander – mal die Einheitsmatrix – wenn das Einlösungsproblem – hat – es muss ein Vektor geben der von dieser Matrix im Mittelstand eines Matrix zu null gemacht wird also wenn die Determinante – davon doch nur ist es – schon oft genug gesagt aber ich sag's noch mal das keine gute Idee das jetzt für Matrizen – mit Milliarden mal Milliarden Einträgen zu machen – die Determinante wird nicht Funktion jetzt aber – als Gedankenexperiment – in der Mathematik Komma das so hinschreiben ?? wenn es niemals ausreichend für große Matrizen – aber es müsste gehen wenn es wirklich ausrechnen würden korrekt müsste so gehen – anders ein Wert dieser Matrix genau dann wenn diese Determinante gleich null ist jetzt kann ich diese Determinante – ja mal hinschreiben – war ?? Matrix gerade verschwunden zu viele ?? – beschreibt das ?? dahinter was ist diese Determinante – sie zu Trierlander – auf der Diagonalen – hier Minuslander – halb – halb eins – eins – minuslandereinhalb – null – null einhalb – Minislander – null und die unten haben wir dann noch ?? null null null minus Lambda – das ist jetzt dieses Ausrüster wird mit unserer Determinante – auf der Diagonalen – Lander abgezogen – ?? – ich möchte zeigen dass dieses hierfür Lambda gleich eins gleich null wird – wie können Sie das hier umformen – spaltentechnisch – seien technisch diese Determinante – hier umformen – sodass ich tatsächlich irgendwie siehe eins Minuslander – ist übrig – wenn sie da was – wie üblich umformen Spaltenzeilen – irgendwie raffiniert addieren was weiß ich was für dich wie Tun – unter eins minus dann daraus zu disziplinieren – das muss er nach einer vor Komma – hier muss irgendwie ein Faktor stehen verwegen ✂ einzelnes Lander – damit wenn ich Lander gleich Einsätze – null rauskommt – Komma – wahrscheinlich auf Anhieb nicht drauf ich sage mal an was mir vorschwebt und sie überlegen sich warum das denn – funktioniert – sie nehmen mal die zweite Zeile auf die erste drauf addiert die dritte auf die erste drauf addiert und die vierte Zeile auf die erste drauf addiert – an Determinante so umformen wie sie das kennen ?? ich kann eine Zeile auf eine andere Zeile addieren und die dritte Platte bleibt gleich der werte Determinante bleibt leicht das man Zimmer mit der zweiten dritten vierten Zeile alle von den Zeilen – auf die erste Zeile draufaddieren – was passiert da und warum passiert das da was sie dann sehen beschreibt die Zeile zwei drei vier schon wieder hin ✂ überlegen sich die erste Zeile – warum steht in der ersten Zeile was denn der steht – also – überall eins minus Lambda interessanterweise – in allen Spalten kriegen sind ersten Zeile einzelnes Lander – hier – die einzige ?? nach oben es noch neun einzelnes Lander – ein halb das Minus Landerkom nach oben des ein halb kommt nach oben einzelnes Lander und so weiter und so weiter – die kriegen in jeder Spalte – oben eins Minuslander – das ganze natürlich mit allen Übergangsmatrizen – Punkt sie haben in jeder Spalte – das Minus Lander stehen – auf der Diagonalen – okay soweit – und ansonsten haben Sie in jeder Spalte die Summe eins – Dinge Wahrscheinlichkeit – nicht Komma – aus dem Zustand B – da müssen sich die Wahrscheinlichkeiten – insgesamt – mit den ich zu Abi CD gehe zu eins addieren sie alles nach oben bringen musste einzelnes Lander stehen und so weiter und so weiter also egal welche Übergangsmatrix sich nehmen oder transponiert – Übergangsmatrix sich nehmen die Ohrmuscheln als Minister lassen weiter als Gesandter ✂ stehen – und das kann ich jetzt vereinfachen wie können Sie diese Determinante – vereinfachen – und – Organe aus – wenn sie so eine Matrix hätten also eine Determinante hätten dran zwanzig ?? zwanzig ?? zwanzig ?? zwanzig ✂ GESTOHLENE irgend ein Unsinn – wie können Sie die umformen – damit die einfacher wird – so – überall eins sind die rein zwanzig aus sind sie ziehen aus der ersten Zeile den Faktor dreiundzwanzig raus – dir lauter Einsen stehen – denn dieses währende Spalte – sie haben – das Volumen – mit einem Spaltenvektor – Dreifaltigkeit soll das seit neunzehn zwanzig – und den verkürzen sie dann auf ein drei Zwanzigstel besser nur noch eins eins eins eins eins – das Volumen von drei zwanzig Wacht und der Vektor ist dann nur noch als als ein Satz eins die ziehen aus der ersten Zeile jetzt gespaltene aus ersten Zeile in Faktor drei zwanzig außenstehender lauter Einsen – das ?? hier – hier steht also der Faktor eins minus Lambda rausgezogen – mal – irgendwas – wird fürchterlich werden ein Polynom dritten Grades – Bettes werden – was auch immer da jetzt steht auf jeden Fall ein Polynom dritten Grades ist den Ort außer ich schon ?? weit dann doch das nur so hinschreiben – man sich mal hier stehen jetzt lauter Einsen eins eins eins eins und so weiter und so weiter und so weiter – das Ergebnis der Polynom den Rat eines Windowslander habe ich jetzt abgespalten – Grades – welches auch immer offensichtlich irgendwas mit Lander hoch drei drin man das weiter betrachtet – und jetzt sehe ich wenn ich Lander gleich Einsätze – null aus – eins ist ein Eigenwert – also was zu beweisen war hier sehen Sie jetzt wenn Lander ein Eigenwert ist genau dann wenn man dann Eigenwert ist meiner Matrix – muss das null werden – okay das wird null ?? Lander gleich einsetzen – einfach nur weil die Summe jeder Spalte – gleich eins ist – Punkt was dann daraus – was man sieht es muss so einen – besonders den stationären Zustand geben – der sich nicht verändert ?? einen Vektor mit Eigenwert eins – abschließend noch einmal kurz gezeigt dass es nicht ganz immer so einfach ist die Potenz der Matrix bilden und so weiter – das kommt nicht immerhin einer großen bisschen mehr Gehirnsschmalz reinstecken – Punkt muss mal – andere Situation an – Hermes Seite A sie haben Seite B – und die verlinken sich gegenseitig – wie sie die Matrix aus wie sie die zweite Potenz von der Matrix aus – ist sie die dritte Potenz von der Matrix aus – sehen das mit dem Potenzen ist jetzt leider ✂ noch nicht hundert Prozent das was man machen kann – so – ich komme aus A – Beistrich nicht nach A ich gehe nach B ich komme aus B dann gehe ich nach A und nicht nach B so sind diese Matrix aus eine Spiegelung wenn sie sich erinnern – könnte man auch noch geometrisch auffassen das Quadrat davon ich komme aus A G nach beta muss ich wieder nach Artikel das Quadrat aus Rechner bis offensichtlich – wieder die Einheitsmatrix – das Quadrat die dritte Potenz Einheitsmatrix – mal – die öffentliche Matrix ist wieder die ursprüngliche Matrix – Sie klicken dreimal – von A müssen sie nach B von B müssen sie nach A – und von A müssen sie wieder nach B das wieder unser vertauschen und so weiter – die hundertste Potenz wird wieder so aussehen ?? hundert und erste Potenz wird wieder so aussieht das oszilliert – wie haben Sie das Phänomen – das die hundertste Potenz sich schon irgendwohin konvertiert ist – es oszilliert – auf Dauer das hier machen also muss etwas vorsichtig sein man kenne sich etwas an den hundertste Protest – sie können aber – schon jetzt nicht aus offensichtlich sie können aber Eigenwert der Eigenvektoren – ausrechnen – was wenn sie rauskriegen – ?? Bindestrich rauskriegen dass der Patchring für diese beiden Seiten gleich sein muss sie dann raus kriegen ein halbeinhalb – passen auch sonst wenn sie so stark mit ein halbeinhalb – und jeder klickt – dann – bleibt es auch bei einhalbeinhalb – ?? das ist ein Phänomen was auftreten kann und an das Phänomen widmet ?? noch erwähnen was auftreten kann ist dass sie mit dem einzelnen Teilnetzwerke – haben die komplett voneinander getrennt sind – Solesituation – haben – dann wird natürlich auch was schief gehen – dann haben sie nicht nur einen einzigen – Eigenvektor nicht nur eine einzige Richtung soll ich sagen hat sie nicht nur eine einzige – Einrichtung – nicht nur eine einzige Verteilung die gleichbleibt sondern – hier in diesem Fall bei so einem – bei so einem Web – können Sie sagen ich nehme – fünfzig Prozent meiner Bevölkerung hier rein fünfundsiebzig Prozent meine Bevölkerung darein oder – ein Drittel darein zwei Drittel daran – gibt er sich auf weitere Freiheitsgrade – wenn ihr Netz nicht verbunden ist – was ist es nicht ganz so leicht dieser scheint aber die Grundidee – ist tatsächlich – ?? lässt jemand zufällig klicken Punkt – wo ist er oder sie denn dann typischerweise – benutzt das als Maß – für die Wichtigkeit – einer Website