Du kanske har hört termen "Markov-kedjan" förut, men om du inte har tagit några klasser på sannolikhetsteori eller datavetenskapsalgoritmer. Lär dig programmering utan all stress. Hur lär du dig programmering utan all stress. Kanske har du bestämt dig för att förfölja programmering, vare sig för en karriär eller bara som 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 ett "underhuvud" -koncept, vilket innebär att du inte 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 med meteorologer 7 Bästa gratis väderapps för Android 7 Bästa gratis väderapps för Android Läs mer - skulle innebära hundratals eller tusentals 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 regnigt, 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-till-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örutse inte bara morgondagens väder, men nästa dag 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 kan ha agoniserat över namnen på dina karaktärer (åtminstone vid en eller flera tillfällen) - och när du bara inte kunde tycka om ett namn du gillar, har du förmodligen tillgripit en nätverksnamngenerator 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, har bokstaven "M" en 60 procent chans att leda till bokstaven "A" och en 40 procent chans att leda till bokstaven "I". 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 grund och botten att oavsett vilken webbsida du börjar på, är din chans att landa på en viss webbsida X en fast sannolikhet, förutsatt att du har en "lång tid" med 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" för 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, eller hur?
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 som frågar om att "dela ut delar av vad och hur du skriver in i Google Apps för att förbättra Google Keyboard". 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 uppmanar vi dig att å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!