Hva er Markov-kjeder? 5 Nifty Real World bruker

Annonse

Du har kanskje hørt begrepet "Markov chain" før, men med mindre du har tatt noen klasser om sannsynlighetsteori eller informatikkalgoritmer Slik lærer du programmering uten all stressKanskje har du bestemt deg for å satse på programmering, enten det er for en karriere eller bare som en hobby. Flott! Men kanskje du begynner å bli overveldet. Ikke så bra. Her er hjelp til å lette reisen. Les mer , vet du sannsynligvis ikke hva de er, hvordan de fungerer og hvorfor de er så viktige.

Forestillingen om en Markov-kjede er et "under hette" -konsept, noe som betyr at du ikke trenger å vite hva de er for å dra nytte av dem. Du kan imidlertid absolutt dra fordel av å forstå hvordan de fungerer. De er enkle, men nyttige på så mange måter.

Så her er et krasjkurs - alt du trenger å vite om Markov-kjeder kondensert til en enkelt, fordøyelig artikkel. Hvis du vil dykke enda dypere, kan du prøve gratis informasjonsteori kurs på Khan Academy (og vurder andre nettkursider også De 8 beste nettstedene for gratis college-kurs online

Er du interessert i å få tilgang til gratis kurs på høyskolenivå? Her er noen av de beste nettstedene du kan ta gratis online-kurs. Les mer ).

Markov-kjeder 101

La oss si at du vil forutsi hvordan været blir i morgen. En sann spådom - den typen utført av ekspert meteorologer De 7 beste gratisvær-appene for AndroidDisse gratisvær-appene vil hjelpe deg å holde deg på toppen av været med Android-enheten din. Les mer - vil involvere hundrevis, eller til og med tusenvis, av forskjellige variabler som stadig endres. Værsystemer er utrolig komplekse og umulige å modellere, i alle fall for legfolk som deg og meg. Men vi kan forenkle problemet ved å bruke sannsynlighetsestimater.

Se for deg at du hadde tilgang til tretti års værdata. Du starter i begynnelsen, og bemerker at dag 1 var solrik. Du fortsetter med å merke deg at dag 2 også var sol, men dag 3 var overskyet, da var dag 4 regnfull, noe som førte inn i tordenvær på dag 5, etterfulgt av solfylte og klare himmel på dag 6.

Helst ville du være mer granulær og valgt en time-for-time-analyse i stedet for en dag-til-dag-analyse, men dette er bare et eksempel for å illustrere konseptet, så vær så snill og hold meg!

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

• 50 prosent sjanse for at i morgen blir sol igjen.
• En sjanse på 30 prosent for at det i morgen blir overskyet.
• 20 prosent sjanse for at morgendagen blir regnfull.

Gjenta dette nå for alle mulige værforhold. Hvis det i dag er skyet, hva er sjansen for at morgendagen blir sol, regnfull, tåkete, tordenvær, haglstormer, tornadoer osv.? 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 dagen etter.

Overgangsstater

Dette er essensen i en Markov-kjede. Du har individuelle stater (i dette tilfellet værforhold) der hver stat kan gå over til en annen tilstander (f.eks. solfylte dager kan gå over til overskyede dager), og disse overgangene er basert på sannsynligheter. Hvis du vil forutsi hvordan været kan være om en uke, kan du utforske de forskjellige sannsynlighetene i løpet av de neste syv dagene og se hvilke som er mest sannsynlig. Dermed en Markov "kjede".

Hvem er Markov? Han var en russisk matematiker som kom med hele ideen om at en stat skulle lede direkte til en annen stat basert på en viss sannsynlighet, der ingen andre faktorer påvirker overgangssjansen. I utgangspunktet oppfant han Markov-kjeden, derav navngivningen.

Hvordan Markov-kjeder brukes i den virkelige verden

La oss utforske noen av virkelighetens applikasjoner der de kommer godt med, med forklaringen ute av veien. Du kan bli overrasket over å finne ut at du har brukt Markov-kjeder hele denne tiden uten å vite det!

Navngenerering

Har du noen gang deltatt i bordplate-spill, MMORPG-spill, eller til og med skjønnlitterær skriving? Du har kanskje blitt plaget av navnet på karakterene dine (i det minste på et eller annet tidspunkt) - og når du bare ikke kunne synes å tenke på et navn du liker, har du sannsynligvis ty til en online navnegenerator Lag et nytt alias med de beste online navnegeneratorene [Rart og fantastisk nett]Navnet ditt er kjedelig. Heldigvis kan du gå online og velge et nytt alias ved å bruke en av de utallige navnegeneratorene som er tilgjengelige på Internetz. Les mer .

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

Alt du trenger er en samling av bokstaver der hver bokstav har en liste over potensielle oppfølgingsbokstaver med sannsynlighet. Så for eksempel har bokstaven "M" 60 prosent sjanse til å føre til bokstaven "A" og en 40 prosent sjanse til å føre til bokstaven "jeg". Gjør dette for en hel haug med andre bokstaver, og kjør deretter algoritmen. Boom, du har et navn som er fornuftig! (Det meste av tiden, uansett.)

Google PageRank

En av de interessante implikasjonene av Markov-kjedeteori er at når lengden på kjeden øker (dvs. antallet statlige overganger øker), sannsynligheten for at du lander i en viss tilstand konvergerer på et fast tall, og denne sannsynligheten er uavhengig av hvor du starter i systemet.

Dette er ekstremt interessant når du tenker på hele internett som et Markov-system der hver webside er en tilstand og koblingene mellom nettsider er overganger med sannsynlighet. Denne setningen sier i utgangspunktet det uansett hvilken webside du starter på, er sjansen for å lande på en bestemt webside X en fast sannsynlighet, forutsatt at du har "lang tid" på 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" for å komme til en bestemt webside, jo høyere er PageRank. Dette er fordi en høyere fast sannsynlighet innebærer at nettsiden har mange innkommende lenker fra andre nettsider - og Google antar at hvis en webside har mange innkommende lenker, så må det være det verdifull. Jo flere innkommende lenker, jo mer verdifull er det.

Det er selvfølgelig mer komplisert enn det, men det er fornuftig. Hvorfor får et nettsted som About.com høyere prioritet på søkeresultatsider? Fordi det viser seg at brukere har en tendens til å ankomme dit når de surfer på nettet. Interessant, er det ikke?

Å skrive ordprediksjon

Mobiltelefoner har hatt prediktiv inntasting i flere tiår nå, men kan du gjette hvordan disse spådommene blir gjort? Enten du bruker Android (alternative tastaturalternativer Hva er det beste alternative tastaturet for Android?Vi tar en titt på noen av de beste tastaturene i Play Store og setter dem på prøve. Les mer ) eller iOS (alternative tastaturalternativer De 10 beste appene for iPhone-tastatur: fancy fonter, temaer, GIF-er og merEr du lei av standard iPhone-tastaturet? Disse alternative iPhone-tastaturappene tilbyr GIF-er, temaer, søk og mer. Les mer ), er det en god sjanse for at den valgte appen din bruker Markov-kjeder.

Dette er grunnen til at tastaturapper spør om de kan samle inn data om skrivevanene dine. I Google Keyboard er det for eksempel en innstilling som heter Del utdrag som ber om å "dele utdrag om hva og hvordan du skriver inn Google-apper for å forbedre Google Keyboard". I hovedsak blir ordene dine analysert og innlemmet i appens Markov-kjedenes sannsynligheter.

Det er også grunnen til at tastaturapper ofte presenterer tre eller flere alternativer, typisk i rekkefølge av mest sannsynlige til minst sannsynlige. Den kan ikke vite helt sikkert hva du mente å skrive videre, men det er riktig oftere enn ikke.

Subreddit Simulation

Hvis du aldri har brukt Reddit, oppfordrer vi deg til i det minste å sjekke ut dette fascinerende eksperimentet som heter /r/SubredditSimulator.

Enkelt sagt tar Subreddit Simulator inn en massiv del av ALLE kommentarene og titlene som er laget på tvers av Reddits mange samfunn, og analyserer deretter ord for ord-sammensetningen av hver setning. Ved å bruke disse dataene genererer den ord-til-ord-sannsynligheter - bruker deretter disse sannsynlighetene for å komme og generere titler og kommentarer fra bunnen av.

Et interessant lag med dette eksperimentet er at kommentarer og titler er kategorisert av fellesskapet som dataene kom fra, så typer kommentarer og titler generert av / r / matts datasett er veldig forskjellige fra kommentarene og titler generert av / r / fotballs data sett.

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

Vet du om andre kule bruksområder for Markov-kjeder? Har du noen spørsmål som fortsatt trenger å svare? Gi oss beskjed i en kommentar nedenfor!