Hva er Markov Kjeder? 5 Nifty Real World Uses

Du har kanskje hørt begrepet “Markov kjede” før, men med mindre du har tatt noen klasser på sannsynlighetsteori eller datavitenskapsalgoritmer. Hvordan lære programmering uten all stress. Hvordan lære programmering uten all stress. Kanskje du har bestemt deg for å forfølge programmering, enten for en karriere eller like en hobby. Flott! Men kanskje du begynner å føle deg overveldet. Ikke så bra. Her er hjelp til å lette reisen din. Les mer, du vet sannsynligvis ikke hva de er, hvordan de fungerer, og hvorfor de er så viktige.

Begrepet en Markov-kjede er en “under panseret” konsept, noe som betyr at du ikke virkelig trenger å vite hva de er for å kunne dra nytte av dem. Men du kan sikkert ha nytte av å forstå hvordan de fungerer. De er enkle, men nyttige på så mange måter.

Så her er et krasj kurs - alt du trenger å vite om Markov kjeder kondensert ned i en enkelt, fordøyelig artikkel. Hvis du vil dykke enda dypere, kan du prøve gratis informasjonsteori-kurset på Khan Academy (og vurdere andre nettbaserte kursområder også 8 Awesome Websites å ta gratis høyskolekurs online 8 fantastiske nettsider å ta gratis høyskolekurs online Les mer).

Markov Kjeder 101

La oss si at du vil forutsi hvordan været blir som i morgen. En sann forutsigelse - typen utført av eksperimentelle meteorologer De 7 beste gratis værappene for Android De 7 beste gratis værappene for Android Disse gratis værappene hjelper deg med å holde deg på toppen av været med Android-enheten din. Les mer - vil innebære hundrevis, eller tusenvis av, forskjellige variabler som stadig endrer seg. Værsystemene er utrolig komplekse og umulige å modellere, i hvert fall for lekere som deg og meg. Men vi kan forenkle problemet ved å bruke sannsynlighetsestimater.

Tenk deg at du hadde tilgang til tretti år med værdata. Du starter i begynnelsen, og merker at Dag 1 var solfylt. Du fortsetter å legge merke til at Dag 2 var også solfylt, men Dag 3 var overskyet, da dag 4 var regnfull, noe som førte til tordenvær på dag 5, etterfulgt av solfylt og klart himmel på dag 6.

Ideelt sett vil du være mer granulær og velge en time-by-time analyse i stedet for en dag-til-dag analyse, men dette er bare et eksempel for å illustrere konseptet, så vær med meg!

Du gjør dette over hele det 30-årige datasettet (som ville være bare sjenert av 11 000 dager) og beregne sannsynlighetene for hvordan morgendagens vær vil være som basert på dagens vær. For eksempel, hvis i dag er solrik, så:

• En 50 prosent sjanse for at i morgen blir solfylt igjen.
• En 30 prosent sjanse for at i morgen blir overskyet.
• En 20 prosent sjanse for at i morgen blir regnfull.

Nå gjenta dette for alle mulige værforhold. Hvis i dag er overskyet, hva er sjansene for at i morgen blir sol, regnfull, tåke, tordenvær, hagelorm, tornadoer, etc? Ganske snart har du et helt system av sannsynligheter som du kan bruke til å forutsi ikke bare morgendagens vær, men neste dags vær og neste dag.

Overgangsstater

Dette er essensen av en Markov-kjede. Du har individuelle stater (i dette tilfellet værforhold) hvor hver stat kan overgå til andre stater (for eksempel solfylte dager kan overgang til overskyet dager) og disse overgangene er basert på sannsynligheter. Hvis du vil forutsi hvordan været kan være i løpet av en uke, kan du utforske de ulike sannsynlighetene de neste sju dagene og se hvilke som er mest sannsynlige. Dermed en Markov “kjede”.

Hvem er Markov? Han var en russisk matematiker som kom opp med hele ideen om en stat som fører direkte til en annen stat basert på en viss sannsynlighet, hvor ingen andre faktorer påvirker overgangskansen. I utgangspunktet oppfant han Markov-kjeden, derav navnet.

Hvordan Markov-kjeder brukes i den virkelige verden

Med forklaringen ut av veien, la oss utforske noen av de virkelige verdensapplikasjoner hvor de kommer til nytte. Du kan bli overrasket over å finne ut at du har brukt Markov-kjeder hele tiden uten å vite det!

Navn Generasjon

Har du noen gang deltatt i bordspill, MMORPG-spill, eller til og med fiksjonsskriving? Du kan ha agonized over navnet på dine tegn (minst på et eller annet tidspunkt) - og når du bare ikke kunne synes å tenke på et navn du liker, har du sannsynligvis benyttet deg av en online-navngenerator Lag et nytt alias med The Beste online-navngeneratorer [Merkelig og flott web] Lag et nytt alias med de beste online-navngeneratorene [Merkelig og flott nett] Ditt navn er kjedelig. Heldigvis kan du gå online og velge et nytt alias ved å bruke en av de utallige navngeneratorene som er tilgjengelige på Internetz. Les mer .

Har du noen gang lurt på hvordan disse navnegeneratorene jobbet? Som det viser seg, bruker mange av dem Markov-kjeder, noe som gjør den til en av de mest brukte løsningene. (Det finnes andre algoritmer der ute som er like effektive, selvfølgelig!)

Alt du trenger er en samling bokstaver hvor hvert brev har en liste over mulige oppfølgingsbrev med sannsynligheter. Så, for eksempel brevet “M” har en 60 prosent sjanse til å føre til brevet “EN” og en 40 prosent sjanse til å føre til brevet “Jeg”. Gjør dette for en hel haug med andre bokstaver, og kjør algoritmen. Boom, du har et navn som gir mening! (Mesteparten av tiden, uansett.)

Google PageRank

En av de interessante konsekvensene av Markov-kjede-teorien er at når lengden på kjeden øker (dvs. antall overganger øker), sannsynligheten for at du lander på en bestemt tilstand, konvergerer på et fast nummer, og denne sannsynligheten er uavhengig av hvor du starter i systemet.

Dette er ekstremt interessant når du tenker på hele verdensomspennende web som et Markov-system hvor hver nettside er en stat og koblingene mellom nettsider er overganger med sannsynligheter. Denne setningen sier i utgangspunktet det uansett hvilken nettside du starter på, er sjansen for landing på en bestemt nettside X en fast sannsynlighet, forutsatt a “lang tid” av surfing.

Og dette er grunnlaget for hvordan Google rangerer nettsider. Faktisk er PageRank-algoritmen en modifisert (les: mer avansert) form av Markov-kjedealgoritmen.

Jo høyere “fast sannsynlighet” når du kommer til en bestemt nettside, jo høyere er PageRank. Dette skyldes at en høyere fast sannsynlighet innebærer at nettsiden har mange innkommende linker fra andre nettsider - og Google antar at hvis en nettside har mange innkommende linker, må den være verdifull. Jo flere innkommende linker, jo mer verdifulle er det.

Det er mer komplisert enn det selvfølgelig, men det gir mening. Hvorfor får et nettsted som About.com høyere prioritet på søkeresultatene? Fordi det viser seg at brukerne pleier å ankomme der mens de surfer på nettet. Interessant, er det ikke?

Skriving av Word Prediction

Mobiltelefoner har hatt prediktiv skriving i flere tiår nå, men kan du gjette hvordan disse spådommene er gjort? Enten du bruker Android (alternativt tastaturalternativer Hva er det beste alternative tastaturet for Android? Hva er det beste alternative tastaturet for Android? Vi tar en titt på noen av de beste tastaturene i Play-butikken og legger dem på prøve. Mer) eller iOS (alternative tastaturalternativer 9 Alternative iOS-tastaturer for å gjøre skrivingen enklere eller mer morsomt 9 Alternative iOS-tastaturer for å gjøre skriveren enklere eller morsommere Når Apple endelig slutte å fungere som en overbeskyttende forelder og introduserte tastaturer fra tredjeparter, gikk alle sammen keyboard-crazy. Les mer), det er en god sjanse for at appen din etter eget valg bruker Markov-kjeder.

Dette er grunnen til at tastaturapplikasjoner spør om de kan samle inn data på skrivevaner. For eksempel, i Google Tastatur, er det en innstilling som heter Del snippets det ber om “dele utsnitt av hva og hvordan du skriver inn Google Apps for å forbedre Google Tastatur”. I hovedsak analyseres ordene dine og inkorporeres i appens Markov-kjede-sannsynligheter.

Det er også derfor at tastaturapplikasjoner ofte presenterer tre eller flere alternativer, vanligvis i størst mulig sannsynlighet til minst sannsynlig. Det kan ikke sikkert vite hva du mente å skrive neste, men det er riktig oftere enn ikke.

Subreddit Simulation

Hvis du aldri har brukt Reddit, oppfordrer vi deg til å sjekke ut dette fascinerende eksperimentet kalt / r / SubredditSimulator.

Enkelt sagt, Subreddit Simulator tar i en massiv del av ALLE kommentarene og titlene gjort over Reddits mange lokalsamfunn, og analyserer deretter ord for ord-sminke av hver setning. Ved å bruke disse dataene genererer det ord-til-ord-sannsynligheter - bruker deretter disse sannsynlighetene for å generere titler og kommentarer fra grunnen av.

Et interessant lag til dette eksperimentet er at kommentarer og titler kategoriseres av fellesskapet som dataene kom fra, slik at type kommentarer og titler generert av / r / matets datasett, er veldig forskjellige fra kommentarene og titlene genererer av / r / fotball datasett.

Og det morsomste - eller kanskje den mest forstyrrende - delen av alt dette er at de genererte kommentarene og titlene ofte kan skille seg fra de som er gjort av virkelige mennesker. Det er helt fascinerende.

Kjenner du til andre kule anvendelser for Markov-kjeder? Har du noen spørsmål som fortsatt trenger å svare? Gi oss beskjed i en kommentar nedenfor!

Utforsk mer om: Algoritmer.