Wat zijn Markov-ketens? 5 Handig gebruik van echte wereld

Je hebt misschien de term gehoord “Markov-ketting” voor, maar tenzij je een paar lessen hebt gevolgd over waarschijnlijkheidstheorie of computerwetenschappelijke algoritmen. Hoe leer je programmeren zonder al de stress Leren programmeren zonder al je stress Misschien heb je besloten om te blijven programmeren, of het nu voor een carrière is of gewoon een hobby. Super goed! Maar misschien begin je je overweldigd te voelen. Niet zo goed. Hier is hulp om uw reis te vergemakkelijken. Lees Meer, je weet waarschijnlijk niet wat ze zijn, hoe ze werken, en waarom ze zo belangrijk zijn.

Het idee van een Markov-keten is een “onder de motorkap” concept, wat betekent dat je niet echt hoeft te weten wat ze zijn om ervan te profiteren. U kunt er echter zeker baat bij hebben te begrijpen hoe ze werken. Ze zijn eenvoudig en toch handig op zoveel verschillende manieren.

Dus hier is een spoedcursus - alles wat u moet weten over Markov-kettingen, samengevat in een enkel, verteerbaar artikel. Als je nog dieper wilt graven, probeer dan de gratis informatietheoriscursus over Khan Academy (en overweeg ook andere online cursuswebsites 8 Geweldige websites om gratis college te volgen online 8 Geweldige websites om gratis college te volgen online Lees meer).

Markov kettingen 101

Laten we zeggen dat je wilt voorspellen hoe het weer morgen zal zijn. Een echte voorspelling - het soort uitgevoerd door deskundige meteorologen De 7 beste gratis weer-apps voor Android De 7 beste gratis weer-apps voor Android Deze gratis weer-apps zullen u helpen om op de hoogte te blijven van het weer met uw Android-apparaat. Meer lezen - zou gepaard gaan met honderden of zelfs duizenden verschillende variabelen die voortdurend veranderen. Weersystemen zijn ongelooflijk complex en onmogelijk te modelleren, tenminste voor leken zoals jij en ik. Maar we kunnen het probleem vereenvoudigen door waarschijnlijkheidsramingen te gebruiken.

Stel je voor dat je toegang had tot dertig jaar weersinformatie. Je begint aan het begin en merkt op dat dag 1 zonnig was. Je blijft doorgaan en merkt op dat dag 2 ook zonnig was, maar dag 3 was bewolkt, toen was dag 4 regenachtig, wat leidde tot een onweersbui op dag 5, gevolgd door zonnige en heldere hemel op dag 6.

Idealiter zou je meer granulair zijn en kiezen voor een analyse van één uur per dag in plaats van een analyse van dag tot dag, maar dit is slechts een voorbeeld om het concept te illustreren, dus hou vol!

U doet dit gedurende de gehele 30-jaar durende dataset (die slechts 11.000 dagen zou zijn) en berekent de waarschijnlijkheden van hoe het weer van morgen zal zijn op basis van het weer van vandaag. Als vandaag bijvoorbeeld zonnig is, dan:

• Een kans van 50 procent dat het morgen weer zonnig zal zijn.
• Een kans van 30 procent dat het morgen bewolkt zal zijn.
• Een kans van 20 procent dat het morgen regenachtig zal zijn.

Herhaal dit nu voor alle mogelijke weersomstandigheden. Als het vandaag bewolkt is, wat zijn de kansen dat het morgen zonnig zal zijn, regenachtig, mistig, onweersbuien, hagelbuien, tornado's, enz.? Al snel heb je een heel systeem van waarschijnlijkheden die je kunt gebruiken om niet alleen het weer van morgen te voorspellen, maar ook het weer van de volgende dag en de volgende dag..

Overgangslanden

Dit is de essentie van een Markov-keten. Je hebt individuele staten (in dit geval weersomstandigheden) waar elke staat kan overstappen naar andere staten (bijvoorbeeld zonnige dagen kunnen overgaan in bewolkte dagen) en die overgangen zijn gebaseerd op waarschijnlijkheden. Als u wilt voorspellen hoe het weer in een week kan zijn, kunt u de verschillende kansen in de komende zeven dagen verkennen en zien welke waarschijnlijk zijn. Dus, een Markov “keten”.

Wie is Markov? Hij was een Russische wiskundige die met het hele idee kwam van één staat die rechtstreeks naar een andere staat leidde op basis van een zekere waarschijnlijkheid, waar geen andere factoren de overgangskans beïnvloeden. Kortom, hij heeft de Markov-keten uitgevonden, vandaar de naamgeving.

Hoe Markovketens worden gebruikt in de echte wereld

Laten we, met de uitleg uit de weg, een aantal van de echte wereldapplicaties verkennen waar ze van pas komen. Je zult verbaasd zijn als je merkt dat je al deze tijd gebruik hebt gemaakt van Markov-ketens zonder het te weten!

Naam genereren

Heb je ooit deelgenomen aan tableop gaming, MMORPG gaming of zelfs fictie schrijven? Je hebt je misschien gekwetst over de naamgeving van je personages (op zijn minst op een bepaald punt) - en toen je gewoon niet kon denken aan een naam die je leuk vindt, heb je waarschijnlijk zijn toevlucht genomen tot een online naamgenerator Create A New Alias ​​With The Beste online naamgenerators [Weird & Wonderful Web] Creëer een nieuw alias met de beste online naamgenerators [Weird & Wonderful Web] Je naam is saai. Gelukkig kun je online gaan en een nieuwe alias kiezen met behulp van een van de ontelbare naamgenerators die beschikbaar zijn op Internetz. Lees verder .

Heb je je ooit afgevraagd hoe die naamgenerators werkten? Het blijkt dat velen van hen gebruik maken van Markov-ketens, waardoor het een van de meest gebruikte oplossingen is. (Er zijn andere algoritmen die er zijn die natuurlijk net zo effectief zijn!)

Het enige dat u nodig hebt, is een verzameling brieven waarin elke letter een lijst met mogelijke vervolgbrieven met waarschijnlijkheden bevat. Dus bijvoorbeeld de brief “M” heeft een kans van 60 procent om naar de brief te leiden “EEN” en een kans van 40 procent om naar de brief te leiden “ik”. Doe dit voor een hele reeks andere letters en voer het algoritme uit. Boom, je hebt een naam die logisch is! (Meestal, hoe dan ook.)

Google PageRank

Een van de interessante implicaties van Markov-ketentheorie is dat naarmate de lengte van de keten toeneemt (dat wil zeggen het aantal toestandsovergangen toeneemt), de waarschijnlijkheid dat je op een bepaalde toestand terechtkomt, convergeert op een vast getal, en deze waarschijnlijkheid is onafhankelijk van waar je begint in het systeem.

Dit is buitengewoon interessant als je denkt aan het hele wereldwijde web als een Markov-systeem waarbij elke webpagina een staat is en de koppelingen tussen webpagina's overgangen met waarschijnlijkheden zijn. Deze stelling zegt in feite dat het maakt niet uit op welke webpagina je begint, je kans om te landen op een bepaalde webpagina X is een vaste kans, uitgaande van een “lange tijd” van surfen.

En dit is de basis van hoe Google webpagina's rangschikt. Het PageRank-algoritme is inderdaad een gewijzigde (lees: meer geavanceerde) vorm van het Markov-ketenalgoritme.

Hoe hoger de “vaste waarschijnlijkheid” om op een bepaalde webpagina aan te komen, des te hoger de PageRank. Dit komt omdat een hogere vaste kans impliceert dat de webpagina veel inkomende links bevat van andere webpagina's - en Google gaat ervan uit dat als een webpagina veel inkomende links bevat, deze waardevol moet zijn. Hoe meer inkomende links, hoe waardevoller het is.

Het is natuurlijk ingewikkelder dan dat, maar het is logisch. Waarom krijgt een site als About.com een ​​hogere prioriteit op pagina's met zoekresultaten? Omdat het erop lijkt dat gebruikers daar meestal aankomen terwijl ze op internet surfen. Interessant, is het niet?

Woordvoorspelling typen

Mobiele telefoons hebben nu al tientallen jaren voorspellend typen, maar kun je raden hoe die voorspellingen zijn gedaan? Of u nu Android gebruikt (alternatieve toetsenbordopties Wat is het beste alternatieve toetsenbord voor Android? Wat is het beste alternatieve toetsenbord voor Android? We bekijken enkele van de beste toetsenborden in de Play Store en testen deze. Meer) of iOS (alternatieve toetsenbordopties 9 Alternatieve iOS-toetsenborden om uw typen gemakkelijker of leuker te maken 9 Alternatieve iOS-toetsenborden om uw typen gemakkelijker of leuker te maken Toen Apple eindelijk optrad als een overbezorgde ouder en toetsenborden van derden introduceerde, ging iedereen keyboard-crazy. Read More), is de kans groot dat uw app naar keuze Markov-ketens gebruikt.

Dit is de reden waarom toetsenbord-apps vragen of ze gegevens over uw typegewoonten kunnen verzamelen. In Google Keyboard is bijvoorbeeld de instelling genaamd Deel fragmenten dat vraagt ​​om “deel fragmenten van wat en hoe u typt in Google-apps om het Google-toetsenbord te verbeteren”. In essentie worden je woorden geanalyseerd en opgenomen in de Markov ketenkansen van de app.

Dat is ook waarom toetsenbordapps vaak drie of meer opties presenteren, meestal in volgorde van meest waarschijnlijk tot minst waarschijnlijk. Het kan niet zeker weten wat je vervolgens wilde typen, maar het klopt vaker wel dan niet.

Subreddit-simulatie

Als je Reddit nog nooit hebt gebruikt, moedigen we je aan om in elk geval dit fascinerende experiment genaamd / r / SubredditSimulator te bekijken.

Simpel gezegd, neemt Subreddit Simulator een enorm deel van ALLE opmerkingen en titels op die over de vele gemeenschappen van Reddit zijn gemaakt, en analyseert vervolgens de woord-voor-woord-make-up van elke zin. Met behulp van deze gegevens genereert het woord-naar-woord-waarschijnlijkheden - gebruikt vervolgens die kansen om vanaf het begin titels en opmerkingen te genereren.

Een interessante laag voor dit experiment is dat opmerkingen en titels worden gecategoriseerd door de community waaruit de gegevens afkomstig zijn, dus de soorten opmerkingen en titels die worden gegenereerd door de dataset van / r / food zijn enorm verschillend van de opmerkingen en titels genereert met / r / gegevensset van voetbal.

En het grappigste - of misschien wel het meest verontrustende - deel van dit alles is dat de gegenereerde opmerkingen en titels vaak niet te onderscheiden zijn van die gemaakt door echte mensen. Het is absoluut fascinerend.

Kent u andere coole toepassingen voor Markov-ketens? Heb je nog vragen die nog beantwoord moeten worden? Laat het ons weten in een commentaar hieronder!

Meer informatie over: algoritmen.