Čo sú to Markovove reťazce? 5 použití šikovných skutočných svetov

Reklama

Možno ste už počuli termín „Markovov reťaz“, ale pokiaľ ste si nebrali niekoľko tried z teórie pravdepodobnosti alebo algoritmy počítačovej vedy Ako sa naučiť programovanie bez stresuMožno ste sa rozhodli venovať programovaniu, či už na kariéru alebo len ako koníček. Skvelé! Ale možno sa začínate cítiť ohromení. Nie také veľké. Tu je pomoc pri uľahčovaní vašej cesty. Čítaj viac , pravdepodobne neviete, čo sú, ako fungujú a prečo sú také dôležité.

Pojem Markovov reťaz je koncept „pod kapotou“, čo znamená, že na to, aby ste z nich mali úžitok, nepotrebujete vedieť, čo sú. Určite však môžete mať úžitok z porozumenia, ako fungujú. Sú jednoduché, ale užitočné v mnohých ohľadoch.

Takže tu je crash kurz - všetko, čo potrebujete vedieť o Markovových reťazcoch, sa skomprimovalo do jedného stráviteľného článku. Ak sa chcete ponoriť ešte hlbšie, vyskúšajte kurz bezplatnej teórie informácií na Khan Academy (a zvážte aj ďalšie stránky kurzov online 8 najlepších stránok pre bezplatné vysokoškolské kurzy online

Máte záujem o bezplatné kurzy na vysokej škole? Tu sú niektoré z najlepších stránok na bezplatné kurzy online. Čítaj viac ).

Markovove reťazce 101

Povedzme, že chcete predpovedať, aké bude zajtra počasie. Skutočná predpoveď - druh vykonávaný odbornými meteorológmi 7 najlepších bezplatných aplikácií pre počasie pre AndroidTieto bezplatné aplikácie pre počasie vám pomôžu zostať na vrchole počasia so zariadením Android. Čítaj viac - vyžadovalo by stovky alebo dokonca tisíce rôznych premenných, ktoré sa neustále menia. Meteorologické systémy sú neuveriteľne zložité a nedajú sa modelovať, aspoň pre laikov, ako ste vy a ja. Problém však môžeme zjednodušiť pomocou odhadov pravdepodobnosti.

Predstavte si, že ste mali prístup k tridsaťročným údajom o počasí. Začnete na začiatku a všimnete si, že 1. deň bol slnečný. Pokračujte ďalej, všimnite si, že Deň 2 bol tiež slnečný, ale Deň 3 bol zamračený, potom Deň 4 bol daždivý, čo v deň 5 viedlo k búrke, po ktorej nasledoval Deň 6 slnečná a jasná obloha.

V ideálnom prípade by ste mali byť podrobnejší a radšej by ste si vybrali analýzu od hodiny po hodinu namiesto analýzy zo dňa na deň, ale toto je len príklad na ilustráciu tohto konceptu, takže so mnou buďte!

Urobíte to počas celého 30-ročného súboru údajov (čo by bolo len plachých 11 000 dní) a na základe dnešného počasia vypočítate pravdepodobnosť toho, aké bude zajtra počasie. Napríklad, ak je dnes slnečno, potom:

• 50-percentná šanca, že zajtra bude opäť slnečno.
• 30-percentná šanca, že zajtra bude zamračená.
• 20-percentná šanca, že zajtra bude daždivá.

Teraz to zopakujte pre všetky možné poveternostné podmienky. Ak je dnes oblačno, aké sú šance, že zajtra budú slnečné, daždivé, hmlisté, búrky, krupobitie, tornáda atď.? Čoskoro budete mať celý systém pravdepodobností, ktoré môžete použiť na predpovedanie nielen zajtrajšieho počasia, ale aj počasia na nasledujúci deň a na nasledujúci deň.

Prechodné štáty

Toto je podstata Markovovej reťaze. Máte jednotlivé stavy (v tomto prípade poveternostné podmienky), z ktorých sa každý štát môže presunúť do iného stavy (napr. slnečné dni môžu prejsť do zamračených dní) a tieto prechody sú založené na pravdepodobnosti. Ak chcete predpovedať, aké bude počasie v priebehu jedného týždňa, môžete počas nasledujúcich siedmich dní preskúmať rôzne pravdepodobnosti a zistiť, ktoré z nich sú najpravdepodobnejšie. Markovský „reťaz“.

Kto je Markov? Bol to ruský matematik, ktorý prišiel s celou predstavou jedného štátu vedúceho priamo do iného štátu na základe určitej pravdepodobnosti, kde na prechodnú šancu neovplyvňujú žiadne iné faktory. V podstate vymyslel Markovovu reťaz, teda pomenovanie.

Ako sa Markovove reťazce používajú v reálnom svete

Po vysvetlení z cesty preskúmajme niektoré z aplikácií v reálnom svete, kde sa im hodí. Možno vás prekvapí, že ste celý čas využívali reťazce Markov bez toho, aby ste o tom vedeli!

Generovanie mien

Zúčastnili ste sa niekedy na stolových hrách, hrách MMORPG alebo dokonca na hraných filmoch? Možno ste sa trápili pomenovaním svojich postáv (aspoň v jednom alebo druhom bode) - a keď ste jednoducho nemohli myslieť na meno, ktoré sa vám páči, pravdepodobne použil online generátor mien Vytvorte nový alias s najlepšími generátormi mien online [čudný a skvelý web]Vaše meno je nudné. Našťastie môžete ísť online a zvoliť si nový alias pomocou jedného z nespočetných generátorov mien dostupných na internete. Čítaj viac .

Premýšľali ste niekedy nad tým, ako tieto generátory mien fungujú? Ako sa ukázalo, mnoho z nich používa Markovove reťazce, čo z neho robí jedno z najpoužívanejších riešení. (Existujú aj iné algoritmy, ktoré sú samozrejme rovnako efektívne!)

Všetko, čo potrebujete, je zbierka listov, kde každé písmeno obsahuje zoznam možných následných listov s pravdepodobnosťou. Napríklad písmeno „M“ má 60% šancu viesť k písmenu „A“ a 40% šancu viesť k písmenu „I“. Urobte to pre celý rad ďalších listov, potom spustite algoritmus. Boom, máš meno, ktoré dáva zmysel! (Každopádne väčšinu času.)

Google PageRank

Jedným zo zaujímavých dôsledkov Markovovej teórie reťazcov je to, že so zvyšujúcou sa dĺžkou reťazca (t.j. počet prechodov stavu) zvyšuje), pravdepodobnosť, že pristane v určitom štáte, konverguje na pevné číslo a táto pravdepodobnosť je nezávislá od toho, kde začínate systém.

To je mimoriadne zaujímavé, keď uvažujete o celom webe ako o Markovovom systéme, kde každá webová stránka je stav a prepojenia medzi webovými stránkami sú prechody s pravdepodobnosťou. Táto veta v podstate hovorí, že bez ohľadu na to, na ktorej webovej stránke začnete, je vaša pravdepodobnosť pristátia na určitej webovej stránke X pevnou pravdepodobnosťou, za predpokladu „dlhého“ času surfovania.

A to je základ toho, ako Google hodnotí webové stránky. Algoritmus PageRank je skutočne modifikovanou (čítanou: pokročilejšou) formou algoritmu Markovovho reťazca.

Čím vyššia je „pevná pravdepodobnosť“ dosiahnutia určitej webovej stránky, tým vyššia je jej PageRank. Je to preto, že vyššia fixná pravdepodobnosť znamená, že webová stránka obsahuje veľa prichádzajúcich odkazov ďalšie webové stránky - a spoločnosť Google predpokladá, že ak webová stránka obsahuje veľa prichádzajúcich odkazov, musí to tak byť cenný. Čím viac prichádzajúcich odkazov, tým je to hodnotnejšie.

Je to zložitejšie ako to, samozrejme, ale dáva to zmysel. Prečo majú stránky ako About.com vyššiu prioritu na stránkach s výsledkami vyhľadávania? Pretože sa ukazuje, že používatelia majú tendenciu prichádzať tam, keď surfujú na webe. Zaujímavé, nie?

Písanie predpovede slov

Mobilné telefóny majú prediktívne písanie už desaťročia, ale viete uhádnuť, ako sa tieto predpovede robia? Či už používate Android (alternatívne možnosti klávesnice Aká je najlepšia alternatívna klávesnica pre Android?Pozrime sa na niektoré z najlepších klávesníc v Obchode Play a otestujeme ich. Čítaj viac ) alebo iOS (alternatívne možnosti klávesnice 10 najlepších aplikácií pre klávesnicu pre iPhone: Efektné písma, motívy, GIF a ďalšieUž vás nebaví predvolená klávesnica iPhone? Tieto alternatívne aplikácie klávesnice iPhone ponúkajú GIF, motívy, vyhľadávanie a ďalšie. Čítaj viac ), existuje veľká šanca, že vaša aplikácia výberu používa Markovove reťazce.

Z tohto dôvodu sa aplikácie klávesnice spýtajú, či môžu zhromažďovať údaje o vašich zvykoch pri písaní. Napríklad v Klávesnici Google sa volá nastavenie Zdieľajte úryvky ktorý žiada „zdieľať úryvky toho, čo a ako píšete v aplikáciách Google na zlepšenie klávesnice Google“. V podstate sú vaše slová analyzované a začlenené do pravdepodobnosti aplikácie Markov v reťazci.

Preto aplikácie klávesnice často ponúkajú tri alebo viac možností, zvyčajne v poradí od najpravdepodobnejšej po najmenšiu pravdepodobnú. Určite nevie, čo máte v úmysle zadať ďalej, ale je správna častejšie ako nie.

Simulácia subreddit

Ak ste Reddit nikdy nepoužili, odporúčame vám, aby ste si aspoň vyskúšali tento fascinujúci experiment s názvom /r/SubredditSimulator.

Jednoducho povedané, Subreddit Simulator preberá obrovské množstvo VŠETKÝCH komentárov a titulov napísaných v mnohých komunitách Redditu a potom analyzuje jednotlivé vety jednotlivých slov. Použitím týchto údajov sa generujú pravdepodobnosti medzi slovami - potom sa pomocou týchto pravdepodobností generujú tituly a komentáre od nuly.

Jednou zaujímavou vrstvou tohto experimentu je to, že komentáre a tituly sú kategorizované podľa komunity, z ktorej údaje pochádzajú, takže druhy komentárov a titulov generovaných súborom údajov / r / food sa výrazne líšia od komentárov a titulov generovaných údajmi / r / soccer set.

Najzábavnejšou - alebo možno najznepokojujúcejšou - časťou všetkého toho je, že generované komentáre a tituly môžu byť často nerozoznateľné od tých, ktoré robia skutoční ľudia. Je to úplne fascinujúce.

Poznáte nejaké iné skvelé použitie pre Markovove reťazce? Máte nejaké otázky, na ktoré treba odpovedať? Dajte nám vedieť v komentári nižšie!