Úvod do reťazcov Markov s príkladmi - reťazce Markov s Pythonom

Úvod do reťazcov Markov:

Zaujímalo vás niekedy, ako Google hodnotí webové stránky? Ak ste vykonali prieskum, musíte vedieť, že používa algoritmus PageRank, ktorý je založený na myšlienke Markovových reťazcov. Tento článok o Úvode k Markovovým reťazcom vám pomôže pochopiť základnú myšlienku, ktorá stojí za Markovovými reťazcami, a ako je možné ich modelovať ako riešenie problémov v reálnom svete.

Tu je zoznam tém, ktorým sa budeme venovať v tomto blogu:

1. Čo je to Markovov reťaz?
2. Čo je nehnuteľnosť Markov?
3. Pochopenie Markovových reťazcov na príklade
4. Čo je to prechodová matica?
5. Markovov reťazec v Pythone
6. Markovove reťazové aplikácie

Ak chcete získať podrobné znalosti o dátovej vede a strojovom učení pomocou Pythonu, môžete sa zaregistrovať naživo od spoločnosti Edureka s nepretržitou podporou a doživotným prístupom.

Čo je to Markovov reťaz?

Andrey Markov prvýkrát predstavil markovské reťaze v roku 1906. Markovské reťazce vysvetlil ako:

Stochastický proces obsahujúci náhodné premenné, prechádzajúci z jedného stavu do druhého v závislosti od určitých predpokladov a určitých pravdepodobnostných pravidiel.

Tieto náhodné premenné prechádzajú z jedného do druhého stavu na základe dôležitej matematickej vlastnosti zvanej Markovský majetok.

To nás privádza k otázke:

Čo je nehnuteľnosť Markov?

Vlastnosť Diskrétny čas Markov uvádza, že vypočítaná pravdepodobnosť prechodu náhodného procesu do ďalšieho možného stavu závisí iba od aktuálneho stavu a času a je nezávislá od série stavov, ktoré mu predchádzali.

Skutočnosť, že ďalšia možná akcia / stav náhodného procesu nezávisí od postupnosti predchádzajúcich stavov, robí Markovove reťazce ako proces bez pamäte, ktorý závisí výlučne od aktuálneho stavu / akcie premennej.

Poďme to odvodiť matematicky:

Nech je náhodný proces {Xm, m = 0,1,2, ⋯}.

Tento proces je markovským reťazcom, iba ak

Markovský reťazec - Úvod do markovských reťazcov - Edureka

pre všetky m, j, i, i0, i1, ⋯ im & mínus1

Pre konečný počet stavov, S = {0, 1, 2, ⋯, r}, sa to nazýva konečný Markovov reťazec.

P (Xm + 1 = j | Xm = i) tu predstavuje pravdepodobnosť prechodu na prechod z jedného stavu do druhého. Tu predpokladáme, že pravdepodobnosti prechodu sú nezávislé od času.

Čo znamená, že P (Xm + 1 = j | Xm = i) nezávisí od hodnoty „m“. Preto môžeme zhrnúť,

Markovov reťazec - Úvod do Markovových reťazcov - Edureka

Táto rovnica teda predstavuje reťazca Markov.

Poďme si teraz na príklade porozumieť, čo presne sú markovské reťazce.

Markovov reťazový príklad

Predtým, ako uvediem príklad, definujme, čo je Markovov model:

Čo je to Markovov model?

Markovov model je stochastický model, ktorý modeluje náhodné premenné takým spôsobom, že tieto sledujú markovskú vlastnosť.

Teraz si ukážeme, ako funguje Markovov model, na jednoduchom príklade.

Ako už bolo spomenuté, Markovove reťazce sa používajú v aplikáciách na generovanie textu a automatické dokončovanie. V tomto príklade sa pozrieme na ukážkovú (náhodnú) vetu a uvidíme, ako ju možno modelovať pomocou Markovových reťazcov.

Príklad reťazca Markov - Úvod do reťazcov Markov - Edureka

Vyššie uvedená veta je náš príklad, viem, že to nemá veľký zmysel (nemusí), je to veta obsahujúca náhodné slová, kde:

1. Kľúče označte jedinečné slová vo vete, t. j. 5 klávesov (jeden, dva, pozdravujte, šťastný, edureka)

2. Žetóny označujú celkový počet slov, t. j. 8 tokenov.

Ak budeme postupovať vpred, musíme pochopiť frekvenciu výskytu týchto slov, nasledujúci diagram zobrazuje každé slovo spolu s číslom, ktoré označuje frekvenciu daného slova.

Kľúče a frekvencie - Úvod do reťazcov Markov - Edureka

Ľavý stĺpec tu teda označuje kľúče a pravý stĺpec označuje frekvencie.

Z vyššie uvedenej tabuľky môžeme vyvodiť záver, že kláves „edureka“ vychádza 4x toľko ako ktorýkoľvek iný kláves. Je dôležité odvodiť tieto informácie, pretože nám môžu pomôcť predpovedať, aké slovo sa môže v konkrétnom okamihu vyskytnúť. Ak by som mal hádať o ďalšom slove vo vzorovej vete, použil by som výraz „edureka“, pretože je najvyššia pravdepodobnosť jeho výskytu.

Keď už hovoríme o pravdepodobnosti, ďalším opatrením, ktoré si musíte uvedomiť, je vážené rozdelenia.

V našom prípade je vážená distribúcia aplikácie „edureka“ 50% (4/8), pretože jej frekvencia je 4 z celkového počtu 8 tokenov. Zvyšok kľúčov (jeden, dva, pozdravte, šťastný) má všetky 1/8 pravdepodobnosť výskytu (& asymp 13%).

Teraz, keď máme porozumenie pre vážené rozdelenie a predstavu o tom, ako sa konkrétne slová vyskytujú častejšie ako iné, môžeme pokračovať ďalšou časťou.

Pochopenie Markovových reťazí - Úvod do Markovových reťazcov - Edureka

Na vyššie uvedený obrázok som pridal ďalšie dve slová, ktoré označujú začiatok a koniec vety, pochopíte, prečo som to urobil v nasledujúcej časti.

Teraz priradíme frekvenciu aj týmto klávesom:

Aktualizované kľúče a frekvencie - Úvod do reťazcov Markov - Edureka

Teraz vytvorme Markovov model. Ako už bolo spomenuté skôr, Markovov model sa používa na modelovanie náhodných premenných v konkrétnom stave takým spôsobom, že budúce stavy týchto premenných závisia výlučne od ich súčasného stavu a nie od ich minulých stavov.

Takže v zásade v Markovovom modeli, aby sme mohli predpovedať ďalší stav, musíme brať do úvahy iba súčasný stav.

Na nasledujúcom diagrame vidíte, ako každý token v našej vete vedie k ďalšiemu. To ukazuje, že budúci stav (nasledujúci token) je založený na aktuálnom stave (súčasný token). Toto je teda najzákladnejšie pravidlo v Markovovom modeli.

Nasledujúci diagram ukazuje, že existujú páry žetónov, kde každý žetón v páre vedie k druhému v tej istej dvojici.

Markovské reťazové páry - Úvod do Markovských reťazí - Edureka

V nasledujúcom diagrame som vytvoril štrukturálne znázornenie, ktoré zobrazuje každý kľúč s poľom ďalších možných tokenov, s ktorými sa môže spárovať.

Rad markovských párov reťazí - Úvod do markovských reťazí - Edureka

Ak chcete zhrnúť tento príklad, zvážte scenár, v ktorom budete musieť vytvoriť vetu pomocou poľa kľúčov a tokenov, ktoré sme videli vo vyššie uvedenom príklade. Skôr ako si ukážeme tento príklad, ďalším dôležitým bodom je, že musíme určiť dve počiatočné miery:

1. Počiatočné rozdelenie pravdepodobnosti (t. J. Počiatočný stav v čase = 0, (kláves „Štart“))

2. Pravdepodobnosť prechodu skoku z jedného stavu do druhého (v tomto prípade pravdepodobnosť prechodu z jedného tokenu do druhého)

Vážené rozdelenie sme si definovali na samom začiatku, takže máme pravdepodobnosti a počiatočný stav, poďme ďalej na príklad.

• Takže začiatočný token je [Štart]

• Ďalej máme iba jeden možný token, t. J. [Jeden]

• V súčasnosti má veta iba jedno slovo, teda „jedno“

• Z tohto tokenu je ďalší možný token [edureka]

• Veta sa aktualizuje na „jednu edureku“

• Z aplikácie [edureka] môžeme prejsť na ktorýkoľvek z nasledujúcich tokenov [dva, Zdravas, šťastný, koniec]

• Existuje 25% šanca, že si vyberú „dvaja“, čo by pravdepodobne viedlo k vytvoreniu pôvodnej vety (jedna edureka dve edureka hail edureka happy edureka). Ak sa však vyberie koniec, proces sa zastaví a nakoniec vygenerujeme novú vetu, t. J. Edureka.

Dajte si potľapkanie po pleci, pretože ste práve postavili Markovov model a prešli ste ním testovací prípad. Na zhrnutie vyššie uvedeného príkladu sme v zásade použili súčasný stav (súčasné slovo) na určenie ďalšieho stavu (ďalšie slovo). A to je presne to, čo je proces Markov.

Je to stochastický proces, pri ktorom náhodné premenné prechádzajú z jedného stavu do druhého tak, že budúci stav premennej závisí iba od súčasného stavu.

Poďme na ďalší krok a pre tento príklad si nakreslime Markovov model.

Schéma štátneho prechodu - úvod do Markovových reťazcov - Edureka

Vyššie uvedený obrázok je známy ako štátny prechodový diagram. Viac si o tom povieme v nasledujúcej časti, zatiaľ si len pamätajte, že tento diagram zobrazuje prechody a pravdepodobnosť z jedného štátu do druhého.

Všimnite si, že každý ovál na obrázku predstavuje kľúč a šípky smerujú k možným klávesom, ktoré ho môžu nasledovať. Hmotnosti na šípkach tiež označujú pravdepodobnosť alebo vážené rozdelenie prechodu z / do príslušných štátov.

Takže to bolo všetko o tom, ako funguje Markovov model. Teraz sa pokúsime pochopiť niektoré dôležité terminológie v Markovovom procese.

Čo je matica pravdepodobnosti prechodu?

V predchádzajúcej časti sme sa zaoberali fungovaním Markovovho modelu na jednoduchom príklade. Poďme si teraz predstaviť matematické terminológie v Markovovom procese.

V Markovovom procese používame maticu na predstavenie pravdepodobností prechodu z jedného stavu do druhého. Táto matica sa nazýva prechodná alebo pravdepodobnostná matica. Zvyčajne to označuje P.

Prechodová matica - úvod do Markovových reťazcov - Edureka

Všimnite si, pij & ge0 a ‘i’ pre všetky hodnoty je,

Vzorec prechodnej matice - Úvod do Markovových reťazcov - Edureka

Vysvetlím to. Za predpokladu, že náš súčasný stav je „i“, nasledujúci alebo nadchádzajúci stav musí byť jedným z potenciálnych stavov. Preto, keď vezmeme súčet všetkých hodnôt k, musíme jednu dostať.

Čo je to diagram prechodného stavu?

Markovov model je predstavovaný diagramom štátneho prechodu. Diagram zobrazuje prechody medzi rôznymi stavmi v Markovovom reťazci. Poďme si predstaviť prechodovú maticu a stavovú prechodovú maticu na príklade.

Príklad prechodovej matice

Zvážte Markovov reťazec s tromi stavmi 1, 2 a 3 a nasledujúcimi pravdepodobnosťami:

Príklad prechodnej matice - úvod do Markovových reťazcov - Edureka

Príklad schémy prechodu štátu - úvod do Markovových reťazcov - Edureka

Vyššie uvedený diagram predstavuje stavový prechodový diagram pre Markovov reťazec. Tu sú 1,2 a 3 tri možné stavy a šípky smerujúce z jedného stavu do ostatných stavov predstavujú pravdepodobnosti prechodu pij. Keď pij = 0, znamená to, že neexistuje prechod medzi stavom „i“ a stavom „j“.

Teraz, keď sme poznajte matematiku a logiku za Markovovými reťazcami, poďme si predstaviť ukážku a pochopíme, kde je možné použiť Markovove reťazce.

Markovov reťazec v Pythone

Na spustenie tejto ukážky budem používať Python, takže ak nepoznáte Python, môžete si prečítať nasledujúce blogy:

2. Ako sa naučiť program Python 3 od začiatku - Sprievodca pre začiatočníkov

Teraz začneme s programovaním!

Markovov reťazový generátor textu

Vyhlásenie o probléme: Aplikovať vlastnosť Markov a vytvoriť model Markov, ktorý dokáže generovať textové simulácie študovaním množiny rečových údajov Donalda Trumpa.

Popis množiny údajov: Textový súbor obsahuje zoznam prejavov, ktoré predniesol Donald Trump v roku 2016.

Logika: Použite vlastnosť Markov na generovanie prejavu Donalda Trumpa zvážením každého slova použitého v prejave a pre každé slovo vytvorte slovník slov, ktoré sa použijú ako ďalšie.

Krok 1: Importujte požadované balíčky

importovať numpy ako np

Krok 2: Prečítajte si množinu údajov

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Thank ty toľko. To je také pekné. Nie je to skvelý chlap. Nedostane spravodlivú tlač, nedostane ju. To jednoducho nie je fér. A musím vám povedať, že som tu a veľmi dôrazne tu, pretože si veľmi vážim Steva Kinga a rovnako si veľmi vážim aj občanov Citizens United, Davida a všetkých a nesmiernu úctu k Tea Party. Tiež tiež obyvatelia Iowy. Majú niečo spoločné. Pracovití ľudia ....

Krok 3: Rozdeľte množinu údajov na jednotlivé slová

corpus = trump.split () # Zobrazte korpusovú tlač (corpus) 'powerful', ',' but ',' not ',' powerful ',' like ',' us. ',' Iran ',' has ',' nasadený ',' teror ', ...

Ďalej vytvorte funkciu, ktorá v prejavoch generuje rôzne dvojice slov. Aby sme ušetrili miesto, použijeme objekt generátora.

Krok 4: Vytvorenie dvojíc klávesov a nadväzujúcich slov

def make_pairs (corpus): for i in range (len (corpus) - 1): yield (corpus [i], corpus [i + 1]) pair = make_pairs (corpus)

Ďalej inicializujeme prázdny slovník na ukladanie dvojíc slov.

V prípade, že prvé slovo v páre je už kľúčom v slovníku, stačí pridať ďalšie potenciálne slovo do zoznamu slov, ktoré za slovom nasledujú. Ak ale slovo nie je kľúčom, vytvorte nový záznam v slovníku a priraďte kľúč k prvému slovu v páre.

Krok 5: Pripojenie slovníka

zlúčiť triediaci kód c ++

word_dict = {} pre word_1, word_2 v pároch: ak word_1 v word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Ďalej náhodne vyberieme slovo z korpusu, ktoré naštartuje markovský reťazec.

Krok 6: Zostavte Markovov model

#randomly vyberte prvé slovo first_word = np.random.choice (corpus) # Vyberte prvé slovo ako slovo s veľkým začiatočným písmenom, aby vybrané slovo nebolo prevzaté z medzery medzi vetou a first_word.islower (): # Začnite reťazec od reťazec vybratých slov = [first_word] #Initializovať počet stimulovaných slov n_words = 20

Za prvým slovom je každé slovo v reťazci náhodne vzorkované zo zoznamu slov, ktoré nasledovali za týmto konkrétnym slovom v živých prejavoch Trumpa. Toto je zobrazené v nasledujúcom útržku kódu:

pre i v rozsahu (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Krok 7: Predpovede

Na záver si zobrazíme stimulovaný text.

#Join vráti reťazec ako tlač reťazca ('' .join (chain)) Počet neuveriteľných ľudí. A Hillary Clintonová má našich ľudí a má tak skvelú prácu. A nebudeme biť Obamu

Toto je vygenerovaný text, ktorý som získal zvážením Trumpovho prejavu. Možno to nebude mať veľký zmysel, ale je to dosť dobré na to, aby ste pochopili, ako možno použiť Markovove reťazce na automatické generovanie textov.

Teraz sa pozrime na ďalšie aplikácie reťazcov Markov a ako sa používajú na riešenie problémov v reálnom svete.

Markovove reťazové aplikácie

Tu je zoznam reálnych aplikácií Markovových reťazcov:

1. Google PageRank: Celý web možno považovať za Markovov model, kde každá webová stránka môže byť stavom a odkazy alebo referencie medzi týmito stránkami je možné považovať za prechod s pravdepodobnosťou. Takže v podstate bez ohľadu na to, na ktorej webovej stránke začnete surfovať, je šanca dostať sa na určitú webovú stránku, povedzme, X, pevnou pravdepodobnosťou.

2. Predikcia písania slova: Je známe, že markovské reťazce sa používajú na predpovedanie nadchádzajúcich slov. Môžu byť tiež použité pri automatickom dopĺňaní a návrhoch.

3. Simulácia subredditu: Určite ste už narazili na Reddit a došlo k interakcii s jedným z ich vlákien alebo subredditov. Reddit používa simulátor subreddit, ktorý spotrebúva obrovské množstvo údajov obsahujúcich všetky komentáre a diskusie uskutočnené v rámci ich skupín. Použitím Markovových reťazcov simulátor vytvára pravdepodobnosti medzi slovami, na vytváranie komentárov a tém.

4. Generátor textu: Markovove reťazce sa najčastejšie používajú na generovanie fiktívnych textov alebo na produkciu veľkých esejí a zostavovanie prejavov. Používa sa tiež v generátoroch mien, ktoré vidíte na webe.

Teraz, keď viete, ako vyriešiť problém v reálnom svete pomocou Markovových reťazcov, som si istý, že by ste sa chceli dozvedieť viac. Tu je zoznam blogov, ktoré vám pomôžu začať s ďalšími štatistickými konceptmi:

Týmto sa dostávame na koniec tohto blogu Introduction To Markov Chains. Ak máte akékoľvek otázky týkajúce sa tejto témy, zanechajte prosím komentár nižšie a my sa vám ozveme.

Zostaňte naladení na ďalšie blogy o trendových technológiách.

Ak hľadáte štruktúrované online školenie v odbore Data Science, edureka! má špeciálne upravený program, ktorý vám pomôže získať odborné znalosti v oblasti štatistík, hádania dát, prieskumných analýz dát, algoritmov strojového učenia ako K-Means Clustering, rozhodovacie stromy, Random Forest, Naive Bayes. Naučíte sa tiež koncepty časových radov, ťažby textu a úvod do hlbokého učenia. Nové dávky pre tento kurz čoskoro začnú !!