Vad är Markov-kedjor? 5 Nifty Real World Uses

Du kanske har hört termen “Markov-kedjan” förut, men om du inte har tagit några klasser på sannolikhetsteori eller datavetenskapsalgoritmer. Hur lära sig programmering utan all stress Hur man lär sig programmering utan all stress. Kanske har du bestämt dig för att driva programmering, oavsett om det är en karriär eller bara en hobby. Bra! Men kanske börjar du känna dig överväldigad. Inte så bra. Här är hjälp för att underlätta din resa. Läs mer, du vet nog inte vad de är, hur de fungerar, och varför de är så viktiga.

Begreppet en Markov-kedja är en “under huven” koncept, vilket innebär att du inte verkligen behöver veta vad de är för att dra nytta av dem. Men du kan säkert dra nytta av att förstå hur de fungerar. De är enkla men ändå användbara på så många sätt.

Så här är en krasch kurs - allt du behöver veta om Markov kedjor kondenseras ner i en enda, smältbar artikel. Om du vill gräva ännu djupare, prova gratis informationsteori-kursen på Khan Academy (och överväga andra onlinekurser också 8 fantastiska webbplatser att ta gratis högskolekurser online 8 fantastiska webbplatser att ta gratis högskolekurser på nätet Läs mer).

Markovkedjor 101

Låt oss säga att du vill förutse hur vädret blir som imorgon. En sann förutsägelse - den typ som utförs av experter Meteorologerna De 7 bästa gratis väderapparna för Android De 7 bästa gratis väderapparna för Android Dessa gratis väderappar hjälper dig att hålla dig på toppen av vädret med din Android-enhet. Läs mer - skulle innebära hundratals, eller till och med tusentals, av olika variabler som ständigt förändras. Vädersystemen är oerhört komplexa och omöjliga att modellera, åtminstone för lekmän som du och jag. Men vi kan förenkla problemet genom att använda sannolikhetsbedömningar.

Tänk dig att du hade tillgång till trettio års väderdata. Du börjar i början och noterar att Dag 1 var solig. Du fortsätter och noterade att Dag 2 var också soligt, men Dag 3 var molnigt, då Dag 4 var regnig, vilket ledde till åskväder på Dag 5, följt av soligt och klart himmel på Dag 6.

Helst skulle du vara mer granulär och välja en timme för timmeanalys istället för en dag-för-dag-analys, men det här är bara ett exempel för att illustrera konceptet, så bära med mig!

Du gör detta över hela 30-åriga datasatsen (som skulle vara bara blyg på 11 000 dagar) och beräkna sannolikheten för hur morgondagens väder kommer att vara utifrån dagens väder. Till exempel, om idag är soligt, då:

• En 50 procent chans att imorgon blir soligt igen.
• En 30 procent chans att imorgon blir molnigt.
• En 20 procent chans att imorgon blir regnig.

Upprepa detta för alla möjliga väderförhållanden. Om det idag är grumligt, vad är risken att imorgon blir soligt, regnigt, dimmigt, åskväder, hagelstor, tornador, etc? Ganska snart har du ett helt system av sannolikheter som du kan använda för att förutsäga inte bara morgondagens väder, men nästa dag är väder och nästa dag.

Övergångsstater

Detta är kärnan i en Markov-kedja. Du har enskilda stater (i det här fallet väderförhållanden) där varje stat kan övergå till andra stater (t ex soliga dagar kan övergå till grumliga dagar) och dessa övergångar är baserade på sannolikheter. Om du vill förutse hur vädret kan vara på en vecka kan du utforska de olika sannolikheterna de närmaste sju dagarna och se vilka som är mest troliga. Således en Markov “kedja”.

Vem är Markov? Han var en rysk matematiker som kom upp med hela idén om en stat som leder direkt till ett annat land baserat på en viss sannolikhet, där inga andra faktorer påverkar övergångsförmågan. I grund och botten uppfann han Markov-kedjan, följaktligen namnet.

Hur Markov-kedjor används i den verkliga världen

Med förklaringen ur vägen, låt oss utforska några av de verkliga applikationerna där de kommer till nytta. Du kan bli förvånad över att du har använt Markov-kedjor hela tiden utan att veta det!

Namn Generation

Har du någonsin deltagit i bordspel, MMORPG-spel, eller till och med fictionskrivning? Du kanske har agoniserat över namnen på dina tecken (åtminstone vid en eller flera tillfällen) - och när du bara inte kunde tycka om ett namn du gillar, har du antagligen använt en online-namngenerator Skapa ett nytt alias med The Bästa online-namngeneratorer [Kusligt och underbart webben] Skapa ett nytt alias med de bästa online-namngivarna [Kusligt och underbart webb] Ditt namn är tråkigt. Tack och lov kan du gå online och välja ett nytt alias med en av de otaliga namngeneratorer som finns på Internetz. Läs mer .

Har du någonsin undrat hur dessa generatorer fungerade? Som det visar sig använder många av dem Markov-kedjor, vilket gör den till en av de mest använda lösningarna. (Det finns andra algoritmer där ute som är lika effektiva, förstås!)

Allt du behöver är en samling bokstäver där varje bokstav har en lista över potentiella uppföljningsbrev med sannolikheter. Så, till exempel brevet “M” har en 60 procent chans att leda till brevet “en” och en 40 procent chans att leda till brevet “jag”. Gör det här för en hel massa andra bokstäver, och kör sedan algoritmen. Boom, du har ett namn som är meningsfullt! (Mest av tiden, hur som helst.)

Google PageRank

En av de intressanta konsekvenserna av Markov-kedjeteori är att när kedjans längd ökar (det vill säga antalet tillståndsövergångar ökar), sänker sannolikheten att du landar i ett visst tillstånd på ett fast antal och denna sannolikhet är oberoende av var du börjar i systemet.

Det här är väldigt intressant när du tänker på hela världen som ett Markov-system där varje webbsida är en stat och länkarna mellan webbsidor är övergångar med sannolikheter. Denna teorem säger i princip att oavsett vilken webbsida du börjar med, är din chans att landa på en viss webbsida X en fast sannolikhet, förutsatt att a “länge sedan” av surfing.

Och detta är grunden för hur Google rankas webbsidor. Faktum är att PageRank-algoritmen är en modifierad (läs: mer avancerad) form av Markov-kedjalgoritmen.

Ju högre “fast sannolikhet” om att komma till en viss webbsida, desto högre är dess PageRank. Detta beror på att en högre fast sannolikhet innebär att webbsidan har många inkommande länkar från andra webbsidor - och Google förutsätter att om en webbsida har många inkommande länkar måste det vara värdefullt. Ju mer inkommande länkar, ju mer värdefulla det är.

Det är mer komplicerat än det självklart, men det är vettigt. Varför får en webbplats som About.com högre prioritet på sökresultatsidorna? Eftersom det visar sig att användarna brukar komma dit när de surfar på nätet. Intressant, är det inte?

Skriva ordförutsägelse

Mobiltelefoner har haft prediktiv typing i årtionden nu, men kan du gissa hur dessa förutsägelser görs? Oavsett om du använder Android (alternativa tangentbordsmöjligheter Vad är det bästa alternativa tangentbordet för Android? Vad är det bästa alternativa tangentbordet för Android? Vi tittar på några av de bästa tangentborden i Play Butik och sätter dem på provet. Mer) eller iOS (alternativa tangentbordsmöjligheter 9 Alternativa iOS-tangentbord för att göra din typning enklare eller mer kul 9 Alternativa iOS-tangentbord för att göra din typing enklare eller mer kul När Apple slutligen slutade fungera som en överskyddande förälder och införde tangentbord från tredje part gick alla keyboard-crazy. Läs mer), det finns en bra chans att din app ska välja Markov-kedjor.

Det är därför som tangentbordsprogram frågar om de kan samla in data på dina skrivvanor. I Google Tangentbord finns det till exempel en inställning som heter Dela utdrag det ber om “dela ut delar av vad och hur du skriver in i Google Apps för att förbättra Googles tangentbord”. I huvudsak analyseras dina ord och införlivas i appens Markov-kedjans sannolikheter.

Det är också därför att tangentbordsapplikationer ofta presenterar tre eller flera alternativ, vanligen i sannolikaste sannolikhet. Det kan inte säkert veta vad du menade att skriva nästa, men det är rätt oftare än inte.

Subreddit Simulation

Om du aldrig har använt Reddit rekommenderar vi att du åtminstone kolla in detta fascinerande experiment som heter / r / SubredditSimulator.

Enkelt uttryckt, Subreddit Simulator tar in en stor del av ALLA kommentarer och titlar gjorda över Reddits många samhällen, och analyserar sedan ord för ord-smink av varje mening. Med hjälp av denna data genererar det ord-till-ord sannolikheter - använder sedan dessa sannolikheter för att generera titlar och kommentarer från början.

Ett intressant skikt för detta experiment är att kommentarer och titlar kategoriseras av det samhälle som data kom från, så typerna av kommentarer och titlar som genereras av / r / matets dataset skiljer sig väldigt annorlunda från kommentarerna och titlarna genereras av / r / fotbolls dataset.

Och den roligaste - eller kanske störstaste - delen av allt detta är att de genererade kommentarerna och titlarna ofta kan skilja sig från de som gjorts av faktiska personer. Det är helt fascinerande.

Känner du till några andra häftiga användningsområden för Markov-kedjor? Har du några frågor som fortfarande behöver svara? Låt oss veta i en kommentar nedan!

Utforska mer om: Algoritmer.