Wat zijn Markov-kettingen? 5 handige toepassingen in de echte wereld

Advertentie

Je hebt de term 'Markov-ketting' misschien eerder gehoord, maar tenzij je een paar lessen hebt gevolgd over kansrekening of algoritmen voor informatica Programmeren leren zonder alle stressMisschien heb je besloten om te gaan programmeren, voor een carrière of gewoon als hobby. Super goed! Maar misschien begin je je overweldigd te voelen. Niet zo goed. Hier is hulp om uw reis te vergemakkelijken. Lees verder weet je waarschijnlijk niet wat ze zijn, hoe ze werken en waarom ze zo belangrijk zijn.

Het idee van een Markov-ketting is een 'onder de motorkap'-concept, wat betekent dat u niet echt hoeft te weten wat ze zijn om ervan te profiteren. U kunt er echter zeker baat bij hebben om te begrijpen hoe ze werken. Ze zijn eenvoudig maar toch op zoveel manieren nuttig.

Dus hier is een spoedcursus - alles wat u moet weten over Markov-kettingen, samengevat in één verteerbaar artikel. Als je nog dieper wilt graven, probeer dan de gratis cursus informatietheorie op Khan Academy (en overweeg ook andere online cursus sites

De 8 beste sites voor gratis college-cursussen onlineGeïnteresseerd in toegang tot gratis cursussen op universitair niveau? Hier zijn enkele van de beste sites om gratis online cursussen te volgen. Lees verder ).

Markov kettingen 101

Stel dat u wilt voorspellen hoe het weer morgen zal zijn. Een echte voorspelling - het soort uitgevoerd door deskundige meteorologen De 7 beste gratis weer-apps voor AndroidDeze gratis weer-apps helpen je om op de hoogte te blijven van het weer met je Android-apparaat. Lees verder - zou honderden, of zelfs duizenden, verschillende variabelen omvatten die voortdurend veranderen. Weersystemen zijn ongelooflijk complex en onmogelijk te modelleren, althans voor leken zoals jij en ik. Maar we kunnen het probleem vereenvoudigen door kansschattingen te gebruiken.

Stel je voor dat je toegang had tot dertig jaar weergegevens. Je begint bij 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 luchten op dag 6.

In het ideale geval zou u gedetailleerder zijn en kiezen voor een analyse van uur tot uur in plaats van een analyse van dag tot dag, maar dit is slechts een voorbeeld om het concept te illustreren, dus wees geduldig!

U doet dit over de gehele dataset van 30 jaar (die net geen 11.000 dagen zou zijn) en berekent de kansen van hoe het weer van morgen eruit zal zien op basis van het weer van vandaag. Als het 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 is.
• Een kans van 20 procent dat het morgen gaat regenen.

Herhaal dit nu voor alle mogelijke weersomstandigheden. Als het vandaag bewolkt is, hoe groot is de kans dan dat het morgen zonnig, regenachtig, mistig, onweer, hagelbui, tornado's, enz. Is? Vrij snel heb je een heel systeem van kansen 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.

Overgangsstaten

Dit is de essentie van een Markov-ketting. Je hebt individuele staten (in dit geval weersomstandigheden) waar elke staat kan overgaan in andere staten (bijv. zonnige dagen kunnen overgaan in bewolkte dagen) en die overgangen zijn gebaseerd op waarschijnlijkheden. Als je wilt voorspellen hoe het weer er in een week uitziet, kun je de verschillende kansen de komende zeven dagen verkennen en kijken welke waarschijnlijk zijn. Dus een Markov "ketting".

Wie is Markov? Hij was een Russische wiskundige die met het hele idee kwam dat een staat rechtstreeks naar een andere staat leidt op basis van een bepaalde waarschijnlijkheid, waar geen andere factoren de overgangskans beïnvloeden. Kortom, hij vond de Markov-ketting uit, vandaar de naamgeving.

Hoe Markov-kettingen worden gebruikt in de echte wereld

Met de uitleg uit de weg, laten we enkele van de echte wereldtoepassingen verkennen waar ze van pas komen. Het zal je misschien verbazen dat je al die tijd Markov-kettingen gebruikt zonder het te weten!

Naamgeneratie

Heb je ooit deelgenomen aan tabletop-gaming, MMORPG-gaming of zelfs fictie schrijven? Je hebt je misschien zorgen gemaakt over de naamgeving van je personages (althans op een bepaald moment) - en als je gewoon geen naam kon bedenken die je leuk vindt, dan heb je waarschijnlijk zijn toevlucht genomen tot een online naamgenerator Maak een nieuwe alias met de beste online naamgeneratoren [Weird & Wonderful Web]Je naam is saai. Gelukkig kun je online gaan en een nieuwe alias kiezen met een van de talloze naamgeneratoren die beschikbaar zijn op Internetz. Lees verder .

Heb je je ooit afgevraagd hoe die naamgeneratoren werkten? Het blijkt dat veel van hen Markov-kettingen gebruiken, waardoor het een van de meest gebruikte oplossingen is. (Er zijn andere algoritmen die natuurlijk net zo effectief zijn!)

Het enige dat u nodig heeft, is een verzameling brieven waarbij elke letter een lijst met mogelijke vervolgbrieven met waarschijnlijkheden bevat. Zo heeft de letter 'M' bijvoorbeeld een kans van 60 procent om naar de letter 'A' te leiden en een kans van 40 procent om naar de letter 'I' te leiden. Doe dit voor een hele reeks andere letters en voer vervolgens het algoritme uit. Boem, je hebt een naam die logisch is! (Meestal toch.)

Google PageRank

Een van de interessante implicaties van Markov-ketentheorie is dat naarmate de lengte van de ketting toeneemt (d.w.z. het aantal toestandsovergangen) verhogingen), de kans dat u in een bepaalde staat terechtkomt, komt samen op een vast aantal, en deze kans is onafhankelijk van waar u begint in het systeem.

Dit is buitengewoon interessant als je het hele wereldwijde web beschouwt als een Markov-systeem waarbij elke webpagina een staat is en de links tussen webpagina's overgangen met waarschijnlijkheden zijn. Deze stelling zegt dat in feite het maakt niet uit op welke webpagina je begint, je kans om op een bepaalde webpagina X te landen 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: geavanceerdere) vorm van het Markov-kettingalgoritme.

Hoe hoger de 'vaste kans' om op een bepaalde webpagina te komen, hoe hoger de PageRank. Dit komt omdat een hogere vaste waarschijnlijkheid impliceert dat de webpagina veel inkomende links heeft andere webpagina's - en Google gaat ervan uit dat als een webpagina veel inkomende links heeft, dat dat ook moet zijn waardevol. 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 blijkt dat gebruikers daar vaak aankomen als ze op internet surfen. Interessant, nietwaar?

Woordvoorspelling typen

Mobiele telefoons hebben al decennia lang voorspellend typen, maar kunt u raden hoe die voorspellingen worden gedaan? Of je nu Android gebruikt (alternatieve toetsenbordopties Wat is het beste alternatieve toetsenbord voor Android?We bekijken enkele van de beste toetsenborden in de Play Store en testen ze. Lees verder ) of iOS (alternatieve toetsenbordopties De 10 beste iPhone-toetsenbordapps: mooie lettertypen, thema's, GIF's en meerMoe van het standaard iPhone-toetsenbord? Deze alternatieve iPhone-toetsenbordapps bieden GIF's, thema's, zoeken en meer. Lees verder ), is de kans groot dat uw favoriete app Markov-kettingen gebruikt.

Dit is de reden waarom toetsenbord-apps vragen of ze gegevens kunnen verzamelen over je typegewoonten. In Google Keyboard is er bijvoorbeeld een instelling genaamd Deel fragmenten waarin wordt gevraagd om 'fragmenten te delen van wat en hoe u typt in Google-apps om het Google-toetsenbord te verbeteren'. In wezen worden uw woorden geanalyseerd en opgenomen in de Markov-kettingwaarschijnlijkheden van de app.

Dat is ook de reden waarom toetsenbord-apps vaak drie of meer opties bieden, meestal in volgorde van meest waarschijnlijke tot minst waarschijnlijke. Het weet niet zeker wat je vervolgens wilde typen, maar het klopt vaker wel dan niet.

Subreddit-simulatie

Als je Reddit nog nooit hebt gebruikt, raden we je aan om in ieder geval dit fascinerende experiment te bezoeken /r/SubredditSimulator.

Simpel gezegd, Subreddit Simulator neemt een groot deel van ALLE opmerkingen en titels op die zijn gemaakt in de vele communities van Reddit en analyseert vervolgens de woord-voor-woord-samenstelling van elke zin. Met behulp van deze gegevens genereert het woord-tot-woord-kansen - en gebruikt vervolgens die kansen om vanaf het begin titels en opmerkingen te genereren.

Een interessante laag bij dit experiment is dat opmerkingen en titels worden gecategoriseerd door de community waaruit de gegevens afkomstig zijn, dus de soorten commentaren en titels gegenereerd door de dataset van / r / food verschillen enorm van de commentaren en titels die worden gegenereerd door de gegevens van / r / soccer ingesteld.

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

Kent u nog andere coole toepassingen voor Markov-kettingen? Heeft u nog vragen die nog beantwoord moeten worden? Laat het ons weten in een reactie hieronder!