Care sunt lanțurile Markov? 5 Utilizări minunate ale lumii reale

Ați auzit termenul “Lanțul Markov” înainte de, dar cu excepția cazului în care ați luat câteva clase despre teoria probabilității sau algoritmi de știință de calculator Cum să înveți programarea fără toate stresul Cum să înveți programarea fără toate stresul Poate ați decis să urmeze programare, fie pentru o carieră sau ca un hobby. Grozav! Dar poate că începi să te simți copleșit. Nu prea grozav. Iată ajutorul pentru a vă ușura călătoria. Citiți mai multe, probabil că nu știți ce sunt, cum funcționează și de ce sunt atât de importante.

Noțiunea de lanț Markov este un “sub capotă” concept, ceea ce înseamnă că nu trebuie să știți cu adevărat ce sunt pentru a beneficia de ele. Cu toate acestea, puteți beneficia cu siguranță de la înțelegerea modului în care acestea funcționează. Sunt simple și totuși utile în multe feluri.

Deci, aici este un curs de accident - tot ce trebuie să știți despre lanțurile Markov condensat într-un singur articol digerabil. Dacă doriți să vă scufundați chiar mai adânc, încercați cursul teoretic gratuit de informare despre Academia Khan (și luați în considerare alte site-uri de curs online, de asemenea, 8 site-uri minunate pentru a lua cursuri gratuite de colegiu online 8 site-uri minunate pentru a lua cursuri gratuite de colegiu online,.

Markov Lanțuri 101

Să presupunem că doriți să prezicați cum va fi vremea de mâine. O predicție adevărată - tipul efectuat de meteorologii experți Cele mai bune 7 aplicații meteo gratuite pentru Android Cele mai bune 7 aplicații meteo gratuite pentru Android Aceste aplicații meteorologice gratuite vă vor ajuta să rămâneți la vârful vremii cu ajutorul dispozitivului Android. Citiți mai multe - ar implica sute sau chiar mii de variabile diferite care se schimbă în mod constant. Sistemele meteorologice sunt incredibil de complexe și imposibil de modelat, cel puțin pentru laici ca tine și cu mine. Dar putem simplifica problema folosind estimările de probabilitate.

Imaginați-vă că aveați acces la datele de vreme de treizeci de ani. Începeți la început, notând că Ziua 1 a fost însorită. Continuați să mergeți, observând că Ziua a 2-a a fost și însorită, dar Ziua a 3-a a fost tulbure, iar Ziua 4 a fost ploioasă, ceea ce a dus la o furtună în Ziua 5, urmat de cerul însorit și clar în Ziua 6.

În mod ideal, ați fi mai granulat, optați pentru o analiză oră cu ora în loc de o analiză de zi cu zi, dar acesta este doar un exemplu pentru a ilustra conceptul, deci purtați-mă cu mine!

Puteți face acest lucru pe întregul set de date de 30 de ani (care ar fi doar timid de 11.000 de zile) și să calculați probabilitățile pentru care va fi vremea de mâine pe baza vremii de astăzi. De exemplu, dacă astăzi este însorită, atunci:

• O șansă de 50% ca mâine să fie din nou soare.
• O șansă de 30% ca mâine să fie tulbure.
• O șansă de 20% ca mâine să fie ploioasă.

Acum repetați acest lucru pentru orice condiție meteorologică posibilă. Dacă astăzi este tulbure, care sunt șansele ca ziua de mâine să fie însorită, ploioasă, ceață, furtună, grindină, tornadă etc? Curând, aveți un întreg sistem de probabilități pe care îl puteți folosi pentru a prezice nu numai vremea de mâine, ci și vremea de a doua zi și a doua zi.

State tranzitorii

Aceasta este esența unui lanț Markov. Aveți stări individuale (în acest caz, condiții meteorologice) în care fiecare stat poate trece în alte state (de exemplu, zilele însorite pot trece în zile tulburi), iar aceste tranziții se bazează pe probabilități. Dacă doriți să prezicați cum poate fi vremea într-o săptămână, puteți explora diferitele probabilități în următoarele șapte zile și puteți vedea care dintre acestea sunt cele mai probabile. Astfel, un Markov “lanţ”.

Cine este Markov? El a fost un matematician rus care a venit cu ideea unui stat care să conducă direct la un alt stat bazat pe o anumită probabilitate, în care niciun alt factor nu influențează șansa de tranziție. Practic, el a inventat lanțul Markov, de aici și denumirea.

Cum se folosesc lanțurile Markov în lumea reală

Cu explicația din drum, hai să explorăm unele dintre aplicațiile din lumea reală în care acestea vin la îndemână. S-ar putea să fiți surprins să aflați că ați folosit lanțurile Markov tot timpul, fără să știi asta!

Generarea de nume

Ați participat vreodată la jocurile de masă, la jocurile MMORPG sau chiar la scrierea de ficțiune? Este posibil să fiți agonizați în legătură cu numirea personajelor dvs. (cel puțin la un moment dat sau altul) - și când nu ați putea să vă gândiți la un nume care vă place, ați recurs probabil la un generator de nume online Crearea unui nou alias cu Cel mai bun generator de nume online [Web ciudat și minunat] Creați un nou alias cu cele mai bune generatoare de nume online [Web ciudat și minunat] Numele dvs. este plictisitor. Din fericire, puteți merge online și puteți alege un nou alias utilizând unul dintre nenumăratele generatoare de nume disponibile pe Internetz. Citeste mai mult .

Te-ai intrebat vreodata cum au lucrat generatoarele de nume? După cum se dovedește, mulți dintre ei folosesc lanțurile Markov, făcându-l una dintre cele mai utilizate soluții. (Există și alți algoritmi care sunt la fel de eficienți, desigur!)

Tot ce aveți nevoie este o colecție de litere în care fiecare literă are o listă de posibile scrisori de urmărire cu probabilități. Deci, de exemplu, scrisoarea “M” are șansa de 60% să conducă la scrisoare “A” și o șansă de 40% să conducă la scrisoare “eu”. Faceți acest lucru pentru o grămadă de alte litere, apoi executați algoritmul. Boom, ai un nume care are sens! (De cele mai multe ori, oricum.)

Google PageRank

Una dintre implicațiile interesante ale teoriei lanțului Markov este că, pe măsură ce lungimea lanțului crește (adică numărul de tranziții de stat crește), probabilitatea de a ateriza pe o anumită stare converge pe un număr fix și această probabilitate este independentă de locul unde porniți în sistem.

Acest lucru este extrem de interesant atunci când vă gândiți la întreaga rețea mondială ca pe un sistem Markov în care fiecare pagină web este o stare și legăturile dintre paginile web sunt tranziții cu probabilități. Această teoremă spune în principiu că indiferent de pagina de web pe care începeți, șansa dvs. de aterizare pe o anumită pagină web X este o probabilitate fixă, presupunând că “perioadă lungă de timp” de surfing.

Și aceasta este baza modului în care Google clasifică paginile web. Într-adevăr, algoritmul PageRank este o formă modificată (citiți mai avansată) a algoritmului lanțului Markov.

Cu cât este mai mare “probabilitate fixă” de a ajunge la o anumită pagină de web, cu atât mai mare este PageRank. Acest lucru se datorează faptului că o probabilitate mai mare fixă ​​implică faptul că pagina web are multe linkuri de intrare de la alte pagini web - și Google presupune că dacă o pagină web are o mulțime de linkuri primite, atunci aceasta trebuie să fie valoroasă. Cu cat mai multe link-uri primite, cu atat este mai valoros.

E mai complicat decât asta, desigur, dar are sens. De ce un site, cum ar fi About.com, obține o prioritate mai mare pe paginile cu rezultate ale căutării? Deoarece se pare că utilizatorii tind să ajungă acolo pe măsură ce navighează pe web. Interesant, nu-i așa??

Tastarea predicției cuvântului

Telefoanele mobile au tastat predictiv acum zeci de ani, dar puteți să ghiciți cum se fac aceste predicții? Indiferent dacă utilizați Android (opțiuni alternative de tastatură Care este cea mai bună tastatură alternativă pentru Android și care este cea mai bună tastatură alternativă pentru Android? Uitați-vă la unele dintre cele mai bune tastaturi din Magazinul Play și le puneți la încercare. Mai mult) sau iOS (opțiuni alternative de tastatură) 9 Tastaturi alternative iOS pentru a face tastarea dvs. mai ușoară sau mai multă distracție 9 Tastaturi alternative iOS pentru a face tastarea dvs. mai ușoară sau mai distractivă Când Apple a încetat în cele din urmă să acționeze ca un părinte supraprotetic și a introdus tastaturi terțe, tastatură-nebun Citiți mai multe), există o șansă bună ca aplicația dvs. de alegere să utilizeze lanțurile Markov.

Acesta este motivul pentru care aplicațiile de la tastatură întreabă dacă pot colecta date despre obiceiurile dvs. de tipare. De exemplu, în tastatura Google există o setare numită Partajați fragmente care cere “fragmente de fragmente de ce și cum introduceți în aplicațiile Google pentru a îmbunătăți tastatura Google”. În esență, cuvintele dvs. sunt analizate și integrate în probabilitățile lanțului Markov ale aplicației.

De aceea, de asemenea, aplicațiile de la tastatură prezintă adesea trei sau mai multe opțiuni, de obicei în ordinea celor mai probabile sau mai puțin probabile. Nu știe sigur ce intenționați să scrieți în continuare, dar este corect mai des decât nu.

Simulare subreditară

Dacă nu ați folosit niciodată Reddit, vă încurajăm să verificați cel puțin acest experiment fascinant numit / r / SubredditSimulator.

Pur și simplu, Subreddit Simulator ia o bucată masivă de TOATE comentariile și titlurile făcute de-a lungul numeroaselor comunități ale Reddit, apoi analizează compoziția cuvânt-cuvânt a fiecărei propoziții. Folosind aceste date, aceasta generează probabilități cuvânt-cuvânt - apoi folosește aceste probabilități pentru a veni genera titluri și comentarii de la zero.

Un strat interesant al acestui experiment este acela că comentariile și titlurile sunt clasificate de către comunitatea din care provin datele, astfel încât tipurile de comentarii și titluri generate de setul de date / r / alimentelor sunt foarte diferite de comentariile și titlurile generate de / r / setul de date pentru fotbal.

Și cea mai amuzantă - sau poate cea mai tulburătoare - din toate acestea este că comentariile și titlurile generate pot fi deseori indistinguizabile de cele făcute de oamenii reali. Este absolut fascinant.

Știți despre alte utilizări reci pentru lanțurile Markov? Aveți întrebări care trebuie încă să răspundeți? Spuneți-ne într-un comentariu de mai jos!

Explorați mai multe despre: Algoritmi.