Vielleicht haben Sie schon einmal den Begriff "Markov-Kette" gehört, aber es sei denn, Sie haben ein paar Kurse über Wahrscheinlichkeitstheorie oder Informatik-Algorithmen absolviert. Wie lernt man Programmierung ohne all den Stress? Wie lernt man Programmierung ohne all den Stress? Vielleicht haben Sie sich entschieden Programmieren, ob für eine Karriere oder nur als Hobby. Groß! Aber vielleicht fängst du an, dich überwältigt zu fühlen. Nicht so toll. Hier ist Hilfe, um Ihre Reise zu erleichtern. Lesen Sie weiter, Sie wissen wahrscheinlich nicht, was sie sind, wie sie funktionieren und warum sie so wichtig sind.
Die Vorstellung einer Markov-Kette ist ein Konzept "unter der Haube", was bedeutet, dass Sie nicht wirklich wissen müssen, was sie sind, um von ihnen zu profitieren. Sie können jedoch davon profitieren, zu verstehen, wie sie funktionieren. Sie sind einfach, aber in vielerlei Hinsicht nützlich.
Also hier ist ein Crash-Kurs - alles, was Sie über Markov-Ketten wissen müssen, die zu einem einzigen verdaulichen Artikel zusammengefasst sind. Wenn Sie noch tiefer vertiefen möchten, versuchen Sie den kostenlosen Informationstheorie-Kurs auf Khan Academy (und betrachten Sie andere Online-Kurs-Websites auch 8 Super Websites zu kostenlosen College-Kurse Online 8 Super Websites zu kostenlosen College-Kurse Online Lesen Sie weiter).
Markov Ketten 101
Nehmen wir an, Sie möchten vorhersagen, wie das Wetter morgen sein wird. Eine wahre Vorhersage - die Art von Experten durchgeführt Meteorologen 7 besten kostenlosen Wetter Apps für Android 7 besten kostenlosen Wetter Apps für Android Lesen Sie mehr - würde Hunderte oder sogar Tausende von verschiedenen Variablen, die sich ständig ändern. Wettersysteme sind unglaublich komplex und unmöglich zu modellieren, zumindest für Laien wie du und ich. Aber wir können das Problem vereinfachen, indem wir Wahrscheinlichkeitsschätzungen verwenden.
Stellen Sie sich vor, Sie hätten Zugriff auf 30 Jahre Wetterdaten. Sie beginnen am Anfang und merken, dass Tag 1 sonnig war. Du gehst weiter und weißt, dass Tag 2 auch sonnig war, aber Tag 3 war bewölkt, dann war Tag 4 regnerisch, was an Tag 5 zu einem Gewitter führte, gefolgt von einem sonnigen und klaren Himmel an Tag 6.
Im Idealfall würden Sie granularer sein und sich statt einer täglichen Analyse für eine stündliche Analyse entscheiden, aber dies ist nur ein Beispiel, um das Konzept zu veranschaulichen, also ertragen Sie mit mir!
Sie tun dies über den gesamten 30-jährigen Datensatz (der knapp 11.000 Tage wäre) und berechnen die Wahrscheinlichkeiten für das Wetter von morgen basierend auf dem heutigen Wetter. Zum Beispiel, wenn heute sonnig ist, dann:
- Eine 50-prozentige Chance, dass es morgen wieder sonnig wird.
- Eine 30-prozentige Chance, dass es morgen trüb wird.
- Eine 20-prozentige Chance, dass es morgen regnet.
Wiederholen Sie dies für alle möglichen Wetterbedingungen. Wenn heute bewölkt ist, wie groß ist die Wahrscheinlichkeit, dass es morgen sonnig, regnerisch, neblig, Gewitter, Hagelstürme, Tornados usw. sein wird? Sehr bald haben Sie ein ganzes System von Wahrscheinlichkeiten, mit dem Sie nicht nur das Wetter von morgen, sondern auch das Wetter des nächsten Tages und den nächsten Tag vorhersagen können.
Übergangsstaaten
Dies ist die Essenz einer Markov-Kette. Sie haben einzelne Zustände (in diesem Fall Wetterbedingungen), in denen jeder Staat in andere Zustände übergehen kann (zB sonnige Tage können in wolkige Tage übergehen) und diese Übergänge basieren auf Wahrscheinlichkeiten. Wenn Sie vorhersagen wollen, wie das Wetter in einer Woche aussieht, können Sie die verschiedenen Wahrscheinlichkeiten in den nächsten sieben Tagen untersuchen und sehen, welche am wahrscheinlichsten sind. Also eine Markov- "Kette".
Wer ist Markov? Er war ein russischer Mathematiker, der die Idee hatte, dass ein Staat mit einer bestimmten Wahrscheinlichkeit direkt in einen anderen Staat führt, wo keine anderen Faktoren die Übergangschance beeinflussen. Im Grunde erfand er die Markov-Kette, daher die Namensgebung.
Wie Markov Ketten in der realen Welt verwendet werden
Lassen Sie uns, mit der erklärten Erklärung, einige der Anwendungen aus der realen Welt erkunden, in denen sie nützlich sind. Sie werden überrascht sein, dass Sie die ganze Zeit Markov-Ketten benutzt haben, ohne es zu wissen!
Namensgenerierung
Hast du jemals an Tabletop-Spielen, MMORPG-Spielen oder sogar dem Schreiben von Büchern teilgenommen? Du magst dich über die Benennung deiner Charaktere gequält haben (zumindest an einem Punkt oder an einem anderen Punkt) - und wenn du einfach nicht an einen Namen denkst, den du magst, hast du wahrscheinlich auf einen Online-Namensgenerator zurückgegriffen Beste Online-Namensgeneratoren [Seltsames & Wunderbares Web] Erstellen Sie ein neues Alias mit den besten Online-Namensgeneratoren [Seltsames & Wunderbares Web] Ihr Name ist langweilig. Zum Glück können Sie online gehen und einen neuen Alias mit einem der unzähligen Namensgeneratoren auf dem Internetz auswählen. Weiterlesen .
Haben Sie sich jemals gefragt, wie diese Namensgeneratoren funktionierten? Wie sich herausstellt, verwenden viele von ihnen Markov-Ketten und sind damit eine der am häufigsten verwendeten Lösungen. (Es gibt andere Algorithmen, die natürlich genauso effektiv sind!)
Alles, was Sie brauchen, ist eine Sammlung von Briefen, bei denen jeder Buchstabe eine Liste potenzieller Folgebriefe mit Wahrscheinlichkeiten enthält. So hat zum Beispiel der Buchstabe "M" eine 60-prozentige Chance, zum Buchstaben "A" zu führen und eine 40-prozentige Chance, zum Buchstaben "I" zu führen. Tun Sie dies für eine ganze Reihe von anderen Buchstaben, dann führen Sie den Algorithmus aus. Boom, du hast einen Namen, der Sinn macht! (Die meiste Zeit sowieso.)
Google PageRank
Eine der interessanten Implikationen der Markov-Kettentheorie ist, dass mit zunehmender Länge der Kette (dh die Anzahl der Zustandsübergänge zunimmt) die Wahrscheinlichkeit, dass Sie in einem bestimmten Zustand landen, gegen eine feste Zahl konvergiert, und diese Wahrscheinlichkeit ist unabhängig von wo Sie beginnen im System.
Dies ist äußerst interessant, wenn Sie an das gesamte World Wide Web als ein Markov-System denken, bei dem jede Webseite ein Zustand ist und die Verbindungen zwischen Webseiten Übergänge mit Wahrscheinlichkeiten sind. Dieser Satz sagt im Grunde, dass unabhängig von der Webseite, auf der Sie anfangen, Ihre Chance, auf einer bestimmten Webseite X zu landen, eine feste Wahrscheinlichkeit ist, unter der Annahme einer "langen Zeit" des Surfens .
Und dies ist die Grundlage dafür, wie Google Webseiten bewertet. In der Tat ist der PageRank-Algorithmus eine modifizierte (gelesen: fortgeschrittenere) Form des Markov-Kettenalgorithmus.
Je höher die "feste Wahrscheinlichkeit" ist, zu einer bestimmten Webseite zu gelangen, desto höher ist der PageRank. Dies liegt daran, dass eine höhere feste Wahrscheinlichkeit bedeutet, dass die Webseite viele eingehende Links von anderen Webseiten hat - und Google geht davon aus, dass, wenn eine Webseite viele eingehende Links hat, diese wertvoll sein muss. Je mehr eingehende Links, desto wertvoller ist es.
Es ist natürlich komplizierter, aber es macht Sinn. Warum erhält eine Website wie About.com auf Suchergebnisseiten eine höhere Priorität? Denn es stellt sich heraus, dass Nutzer dazu neigen, dort anzukommen, wenn sie im Internet surfen. Interessant, nicht wahr?
Wortvorhersage eingeben
Mobiltelefone haben seit Jahrzehnten prädiktive Typisierung, aber können Sie erraten, wie diese Vorhersagen gemacht werden? Ob Sie Android verwenden (alternative Tastaturoptionen Was ist die beste alternative Tastatur für Android? Was ist die beste Alternative Tastatur für Android? Wir werfen einen Blick auf einige der besten Tastaturen im Play Store und stellen sie auf den Prüfstand. Lesen Mehr) oder iOS (alternative Tastaturoptionen 9 Alternative iOS-Tastaturen, um Ihre Eingabe einfacher oder mehr Spaß zu machen 9 Alternative iOS-Tastaturen, um Ihre Eingabe einfacher oder mehr Spaß zu machen Als Apple endlich aufhört, sich wie ein überfürsorglicher Elternteil zu verhalten und Drittanbieter-Tastaturen einzuführen, gingen alle Keyboard-verrückt.Lesen Sie mehr), es ist eine gute Chance, dass Ihre App der Wahl Markov Ketten verwendet.
Aus diesem Grund fragen Tastatur-Apps, ob sie Daten über Ihre Tippgewohnheiten sammeln können. In Google Keyboard gibt es beispielsweise eine Einstellung mit dem Namen Teilen-Snippets, in der Sie aufgefordert werden, "Snippets von was und wie Sie Google-Apps eingeben, um Google Keyboard zu verbessern" zu teilen. Im Wesentlichen werden Ihre Wörter analysiert und in die Markov-Kettenwahrscheinlichkeiten der App integriert.
Das ist auch der Grund, warum Tastatur-Apps oft drei oder mehr Optionen bieten, typischerweise in der Reihenfolge von am wahrscheinlichsten zu am wenigsten wahrscheinlich. Es kann nicht genau wissen, was Sie als nächstes tippen wollten, aber es ist meistens richtig.
Subreddit Simulation
Wenn Sie Reddit noch nie benutzt haben, sollten Sie zumindest dieses faszinierende Experiment namens / r / SubredditSimulator ausprobieren.
Kurz gesagt, Subreddit Simulator nimmt einen großen Teil ALLER Kommentare und Titel auf, die in Reddits zahlreichen Communities gesammelt wurden, und analysiert dann das Wort-für-Wort-Make-up jedes Satzes. Mit diesen Daten generiert es Wort-zu-Wort-Wahrscheinlichkeiten - und verwendet diese Wahrscheinlichkeiten, um Titel und Kommentare von Grund auf neu zu generieren.
Eine interessante Ebene dieses Experiments ist, dass Kommentare und Titel nach der Community kategorisiert werden, aus der die Daten stammen. Daher unterscheiden sich die Arten von Kommentaren und Titeln, die vom Datensatz von / r / food generiert werden, stark von den Kommentaren und Titeln, die von / r / generiert werden. Fußballdatensatz.
Und der lustigste - oder vielleicht auch verstörendste - Teil von allem ist, dass die generierten Kommentare und Titel oft nicht von denen der tatsächlichen Menschen zu unterscheiden sind. Es ist absolut faszinierend.
Kennen Sie andere coole Anwendungen für Markov-Ketten? Haben Sie Fragen, die noch beantwortet werden müssen? Lass es uns in einem Kommentar unten wissen!