Úvod do Markovových řetězců s příklady - Markovovy řetězce s Pythonem

Úvod do Markovových řetězců:

Přemýšleli jste někdy nad tím, jak Google hodnotí webové stránky? Pokud jste provedli průzkum, musíte vědět, že používá algoritmus PageRank, který je založen na myšlence markovských řetězců. Tento článek o Úvod do Markovových řetězců vám pomůže pochopit základní myšlenku, která stojí za Markovovými řetězci, a jak je lze modelovat jako řešení problémů v reálném světě.

Zde je seznam témat, kterým se budeme věnovat v tomto blogu:

1. Co je to Markovův řetězec?
2. Co je majetek Markov?
3. Porozumění Markovových řetězců na příkladu
4. Co je přechodová matice?
5. Markovův řetězec v Pythonu
6. Markovské řetězové aplikace

Chcete-li získat podrobné znalosti o Data Science a Machine Learning pomocí Pythonu, můžete se zaregistrovat naživo od společnosti Edureka s nepřetržitou podporou a doživotním přístupem.

Co je to Markovův řetězec?

Andrey Markov poprvé představil markovské řetězy v roce 1906. Vysvětlil markovské řetězce jako:

Stochastický proces obsahující náhodné proměnné, přechod z jednoho stavu do druhého v závislosti na určitých předpokladech a definitivních pravděpodobnostních pravidlech.

Tyto náhodné přechod proměnných z jednoho do druhého na základě důležité matematické vlastnosti zvané Markovský majetek.

To nás přivádí k otázce:

Co je majetek Markov?

Vlastnost Diskrétní čas Markov uvádí, že vypočítaná pravděpodobnost přechodu náhodného procesu do dalšího možného stavu závisí pouze na aktuálním stavu a čase a je nezávislá na řadě stavů, které mu předcházely.

Skutečnost, že další možná akce / stav náhodného procesu nezávisí na posloupnosti předchozích stavů, vykresluje Markovovy řetězce jako proces bez paměti, který závisí pouze na aktuálním stavu / akci proměnné.

Pojďme to odvodit matematicky:

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

Tento proces je markovským řetězcem, pouze pokud

Markov Chain - Úvod do Markov Chains - Edureka

pro všechna m, j, i, i0, i1, ⋯ im & minus1

Pro konečný počet stavů, S = {0, 1, 2, ⋯, r}, se to nazývá konečný Markovův řetězec.

P (Xm + 1 = j | Xm = i) zde představuje pravděpodobnost přechodu k přechodu z jednoho stavu do druhého. Zde předpokládáme, že pravděpodobnosti přechodu jsou nezávislé na čase.

Což znamená, že P (Xm + 1 = j | Xm = i) nezávisí na hodnotě „m“. Můžeme tedy shrnout,

Vzorec Markovova řetězce - Úvod do Markovových řetězců - Edureka

Tato rovnice tedy představuje Markovský řetězec.

Nyní si na příkladu pochopíme, co přesně jsou Markovovy řetězce.

Příklad Markovova řetězce

Než uvedu příklad, definujme, co je Markovův model:

Co je Markovův model?

Markovův model je stochastický model, který modeluje náhodné proměnné takovým způsobem, že proměnné sledují Markovovu vlastnost.

Nyní pochopíme, jak funguje Markovův model, na jednoduchém příkladu.

Jak již bylo zmíněno dříve, Markovovy řetězce se používají v aplikacích pro generování textu a automatické dokončování. V tomto příkladu se podíváme na ukázkovou (náhodnou) větu a uvidíme, jak ji lze modelovat pomocí Markovových řetězců.

Příklad řetězce Markov - Úvod do řetězců Markov - Edureka

Výše uvedená věta je náš příklad, vím, že to nedává moc smysl (nemusí), je to věta obsahující náhodná slova, kde:

1. Klíče označte jedinečná slova ve větě, tj. 5 kláves (jeden, dva, zdráv, šťastný, edureka)

2. Žetony označují celkový počet slov, tj. 8 žetonů.

Do budoucna musíme pochopit frekvenci výskytu těchto slov, níže uvedený diagram ukazuje každé slovo spolu s číslem, které označuje frekvenci tohoto slova.

Klíče a frekvence - Úvod do Markovových řetězců - Edureka

Levý sloupec zde tedy označuje klíče a pravý sloupec označuje frekvence.

Z výše uvedené tabulky můžeme usoudit, že klíč „edureka“ se objevuje 4x tolik jako kterýkoli jiný klíč. Je důležité takové informace odvodit, protože nám mohou pomoci předpovědět, jaké slovo se může v určitém časovém okamžiku vyskytnout. Pokud bych měl uhodnout další slovo ve vzorové větě, použil bych „edureka“, protože má nejvyšší pravděpodobnost výskytu.

Když už mluvíme o pravděpodobnosti, další opatření, které si musíte být vědomi, je vážené distribuce.

V našem případě je vážená distribuce pro edureku 50% (4/8), protože její frekvence je 4 z celkového počtu 8 tokenů. Zbytek klíčů (jeden, dva, krupobití, šťastný) má všechny 1/8 šanci na výskyt (& asymp 13%).

Nyní, když máme pochopení váženého rozdělení a představu o tom, jak se konkrétní slova vyskytují častěji než jiná, můžeme pokračovat další částí.

Porozumění Markovovým řetězcům - Úvod do Markovových řetězců - Edureka

Na výše uvedeném obrázku jsem přidal další dvě slova, která označují začátek a konec věty, pochopíte, proč jsem to udělal v následující části.

Nyní přiřaďte frekvenci i těmto klíčům:

Aktualizované klíče a frekvence - Úvod do Markovových řetězců - Edureka

Nyní vytvořme Markovův model. Jak již bylo zmíněno dříve, Markovův model se používá k modelování náhodných proměnných v konkrétním stavu takovým způsobem, že budoucí stavy těchto proměnných závisí pouze na jejich aktuálním stavu a nikoli na jejich minulých stavech.

Takže v podstatě v Markovově modelu, abychom mohli předpovědět další stav, musíme vzít v úvahu pouze současný stav.

V níže uvedeném diagramu vidíte, jak každý token v naší větě vede k dalšímu. To ukazuje, že budoucí stav (další token) je založen na aktuálním stavu (současný token). Toto je nejzákladnější pravidlo v Markovově modelu.

Níže uvedený diagram ukazuje, že existují páry žetonů, kde každý žeton ve dvojici vede k druhému ve stejné dvojici.

Markovské řetězové páry - Úvod do Markovských řetězů - Edureka

V níže uvedeném diagramu jsem vytvořil strukturální reprezentaci, která zobrazuje každý klíč s řadou dalších možných tokenů, s nimiž se může spárovat.

Řada markovských řetězových párů - Úvod do markovských řetězců - Edureka

Chcete-li shrnout tento příklad, zvažte scénář, ve kterém budete muset vytvořit větu pomocí pole klíčů a tokenů, které jsme viděli ve výše uvedeném příkladu. Než projdeme tímto příkladem, dalším důležitým bodem je, že musíme určit dvě počáteční míry:

1. Počáteční rozdělení pravděpodobnosti (tj. Počáteční stav v čase = 0, (klávesa „Start“))

2. Pravděpodobnost přechodu z jednoho státu do druhého (v tomto případě pravděpodobnost přechodu z jednoho tokenu do druhého)

Vážené rozdělení jsme definovali na samém začátku, takže máme pravděpodobnosti a počáteční stav, pojďme na příklad.

• Takže začít s počátečním tokenem je [Start]

• Dále máme jen jeden možný token, tj. [Jeden]

• V současné době má věta pouze jedno slovo, tj. „Jedno“

• Z tohoto tokenu je další možný token [edureka]

• Věta byla aktualizována na „jednu edureku“

• Z [edureka] se můžeme přesunout na některý z následujících tokenů [dva, zdráv, šťastný, konec]

• Existuje 25% šance, že budou vybráni dva, což by pravděpodobně vedlo k vytvoření původní věty (jedna edureka dvě edureka kroupy edureka šťastná edureka). Je-li však vybrán ‚konec ', proces se zastaví a my nakonec vygenerujeme novou větu, tj.‚ Jednu edureku'.

Poklepejte si na záda, protože jste právě postavili Markovův model a spustili testovací případ. Abychom shrnuli výše uvedený příklad, v podstatě jsme použili současný stav (přítomné slovo) k určení dalšího stavu (dalšího slova). A přesně to je proces Markov.

Jedná se o stochastický proces, při kterém náhodné proměnné přecházejí z jednoho stavu do druhého takovým způsobem, že budoucí stav proměnné závisí pouze na současném stavu.

Pojďme k dalšímu kroku a pro tento příklad nakreslíme Markovův model.

Státní přechodový diagram - Úvod do Markovových řetězců - Edureka

Výše uvedený obrázek je známý jako přechodový diagram stavu. Více si o tom povíme v níže uvedené části, nyní si jen pamatujte, že tento diagram ukazuje přechody a pravděpodobnost z jednoho stavu do druhého.

Všimněte si, že každý ovál na obrázku představuje klávesu a šipky směřují k možným klávesám, které ji mohou následovat. Váhy na šipkách také označují pravděpodobnost nebo vážené rozdělení přechodu z / do příslušných stavů.

Takže to bylo o tom, jak funguje Markovův model. Nyní se pokusíme porozumět některým důležitým terminologiím v Markovově procesu.

Co je matice pravděpodobnosti přechodu?

Ve výše uvedené části jsme diskutovali o fungování Markovova modelu na jednoduchém příkladu, pojďme nyní pochopit matematické terminologie v Markovově procesu.

V Markovově procesu používáme matici k reprezentaci pravděpodobností přechodu z jednoho stavu do druhého. Tato matice se nazývá přechodová nebo pravděpodobnostní matice. To je obvykle označeno P.

Transition Matrix - Úvod do Markovových řetězců - Edureka

Všimněte si, pij & ge0 a ‚i 'pro všechny hodnoty je,

Transition Matrix Formula - Introduction to Markov Chains - Edureka

Dovolte mi to vysvětlit. Za předpokladu, že náš současný stav je „i“, musí být příští nebo nadcházející stav jedním z potenciálních stavů. Proto při součtu všech hodnot k musíme jednu získat.

Co je diagram přechodu stavu?

Markovův model je reprezentován přechodovým diagramem státu. Diagram ukazuje přechody mezi různými stavy v Markovově řetězci. Na příkladu si vysvětlíme přechodovou matici a stavovou přechodovou matici.

Příklad přechodové matice

Zvažte Markovův řetězec se třemi stavy 1, 2 a 3 a následujícími pravděpodobnostmi:

Příklad přechodové matice - Úvod do Markovových řetězců - Edureka

Příklad přechodového diagramu stavu - Úvod do Markovových řetězců - Edureka

Výše uvedený diagram představuje stavový přechodový diagram pro Markovův řetězec. Zde jsou 1,2 a 3 tři možné stavy a šipky ukazující z jednoho stavu do ostatních představují pravděpodobnosti přechodu pij. Když pij = 0, znamená to, že neexistuje přechod mezi stavem „i“ a stavem „j“.

Teď, když jsme znát matematiku a logiku za Markovovými řetězci, pojďme si udělat jednoduchou ukázku a pochopit, kde lze Markovovy řetězce použít.

Markovův řetězec v Pythonu

Pro spuštění této ukázky budu používat Python, takže pokud Python neznáte, můžete projít následujícími blogy:

2. Jak se naučit Python 3 od začátku - Průvodce pro začátečníky

Pojďme začít s kódováním!

Markovský řetězový generátor textu

Problémové prohlášení: Chcete-li použít vlastnost Markov a vytvořit model Markov, který může generovat textové simulace studiem datové sady Donalda Trumpa.

Popis datové sady: Textový soubor obsahuje seznam projevů, které přednesl Donald Trump v roce 2016.

Logika: Aplikujte vlastnost Markov na generování projevu Donalda Trumpa zvážením každého slova použitého v řeči a pro každé slovo vytvořte slovník slov, která se použijí jako další.

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

importovat numpy jako np

Krok 2: Přečtěte si datovou sadu

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) Mluví 1 ... Děkuji ty moc. To je milé. Není to skvělý chlap. Nedostane spravedlivý tisk, nedostane to. To prostě není fér. A musím vám říci, že jsem tady, a velmi silně zde, protože si velmi vážím Steva Kinga a také si velmi vážím Citizens United, Davida a všech ostatních a nesmírnou úctu k Tea Party. Také také obyvatelé Iowy. Mají něco společného. Pracovití lidé ....

Krok 3: Rozdělte datovou sadu na jednotlivá slova

corpus = trump.split () # Zobrazí korpusový tisk (corpus) 'powerful', ',' but ',' not ',' powerful ',' like ',' us. ',' Iran ',' has ',' nasazený ',' teror ', ...

Dále vytvořte funkci, která generuje různé páry slov v projevech. Abychom ušetřili místo, použijeme objekt generátoru.

Krok 4: Vytváření dvojic klíčů a následných slov

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

Dále inicializujeme prázdný slovník pro uložení dvojic slov.

V případě, že první slovo v páru je již klíčem ve slovníku, stačí přidat další potenciální slovo do seznamu slov, která za slovem následují. Pokud ale slovo není klíčem, vytvořte ve slovníku nový záznam a přiřaďte klíč rovný prvnímu slovu v páru.

Krok 5: Přidání slovníku

co je má vztah v Javě

word_dict = {} pro word_1, word_2 v párech: pokud word_1 v word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Dále náhodně vybereme slovo z korpusu, které spustí markovský řetězec.

Krok 6: Sestavte Markovův model

#randomly vybrat první slovo first_word = np.random.choice (corpus) # Vyberte první slovo jako slovo s velkými písmeny, aby vybrané slovo nebylo převzato z věty, zatímco first_word.islower (): # Spusťte řetězec z řetězec vybraného slova = [první_slovo] # Inicializovat počet stimulovaných slov n_words = 20

Za prvním slovem je každé slovo v řetězci náhodně vzorkováno ze seznamu slov, která následovala po konkrétním slovu v živých projevech Trumpa. To se zobrazuje v následujícím fragmentu kódu:

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

Krok 7: Předpovědi

Nakonec si zobrazme stimulovaný text.

#Join vrací řetězec jako tisk řetězce ('' .join (chain)) Počet neuvěřitelných lidí. A Hillary Clintonová má naše lidi a tak skvělou práci. A nebudeme porazit Obamu

Toto je vygenerovaný text, který jsem získal zvážením Trumpova projevu. Nemusí to mít smysl, ale je to dost dobré, abyste pochopili, jak lze použít Markovovy řetězce k automatickému generování textů.

Nyní se podívejme na několik dalších aplikací řetězů Markov a jak jsou zvyklí řešit problémy v reálném světě.

Markovské řetězové aplikace

Zde je seznam skutečných aplikací Markovových řetězců:

1. Google PageRank: Celý web lze považovat za Markovův model, kde každá webová stránka může být stavem a odkazy nebo odkazy mezi těmito stránkami lze považovat za přechody s pravděpodobností. Takže v zásadě, bez ohledu na to, na které webové stránce začnete surfovat, je šance dostat se na určitou webovou stránku, řekněme, X pevná pravděpodobnost.

2. Predikce psaní slov: O Markovových řetězcích je známo, že se používají k předpovídání nadcházejících slov. Mohou být také použity při automatickém dokončování a návrzích.

3. Simulace Subreddit: Určitě jste narazili na Reddit a došlo k interakci s jedním z jejich vláken nebo subredditů. Reddit používá simulátor subreddit, který spotřebovává obrovské množství dat obsahující všechny komentáře a diskuse konané napříč jejich skupinami. Použitím Markovových řetězců simulátor produkuje pravděpodobnosti mezi slovy k vytváření komentářů a témat.

4. Generátor textu: Markovovy řetězce se nejčastěji používají ke generování fiktivních textů nebo k vytváření velkých esejů a sestavování projevů. Používá se také v generátorech názvů, které vidíte na webu.

Nyní, když víte, jak vyřešit problém v reálném světě pomocí Markovových řetězů, jsem si jistý, že se chcete dozvědět více. Zde je seznam blogů, které vám pomohou začít s dalšími statistickými koncepty:

Tímto se dostáváme na konec tohoto blogu Úvod do řetězců Markov. Máte-li jakékoli dotazy týkající se tohoto tématu, zanechte prosím níže uvedený komentář a my se vám ozveme.

Sledujte další blogy o trendových technologiích.

Pokud hledáte online strukturované školení v oblasti datové vědy, edureka! má speciálně upravený program, který vám pomůže získat odborné znalosti v oblasti statistik, hádání dat, průzkumné analýzy dat, algoritmů strojového učení, jako je shlukování K-Means, rozhodovací stromy, náhodný les, naivní Bayes. Naučíte se také pojmy časové řady, dolování textu a úvod do hlubokého učení. Nové dávky pro tento kurz brzy začnou !!