Bevezetés a Markov-láncokba példákkal - Markov-láncok a Pythonnal

Bevezetés a Markov-láncokba:

Gondolkodott már azon, hogy a Google hogyan rangsorolja a weboldalakat? Ha elvégezte a kutatását, akkor tudnia kell, hogy a Markov-láncok ötletén alapuló PageRank algoritmust használja. Ez a cikk a Bevezetés a Markov-láncokba című cikkben segít megérteni a Markov-láncok alapgondolatát és azt, hogy miként modellezhetők a valós problémák megoldására.

Itt van egy lista azokról a témákról, amelyekről szó lesz ebben a blogban:

1. Mi az a Markov-lánc?
2. Mi a Markov-ingatlan?
3. A Markov-láncok megértése egy példával
4. Mi az az átmeneti mátrix?
5. Markov lánc Pythonban
6. Markov lánc alkalmazások

Ha részletes ismereteket szeretne szerezni az adattudományról és a gépi tanulásról a Python használatával, regisztrálhat élőben Edureka 24/7 támogatással és élethosszig tartó hozzáféréssel.

Mi az a Markov-lánc?

Andrej Markov először 1906-ban mutatta be a Markov-láncokat. A Markov-láncokat a következőképpen magyarázta:

Véletlenszerű változókat tartalmazó sztochasztikus folyamat, amely bizonyos feltételezések és meghatározott valószínűségi szabályok függvényében változik egyik állapotból a másikba.

Ezek véletlenszerűek a változók áttérnek egyikről államra a másikra, az úgynevezett fontos matematikai tulajdonság alapján Markov Property.

Ezzel eljutottunk a kérdéshez:

Mi a Markov-ingatlan?

Diszkrét idő Markov tulajdonság azt állítja, hogy a véletlenszerű folyamat következő lehetséges állapotba való átmenetének kiszámított valószínűsége csak az aktuális állapottól és időtől függ, és független az azt megelőző állapotok sorától.

Az a tény, hogy egy véletlenszerű folyamat következő lehetséges művelete / állapota nem függ a korábbi állapotok sorrendjétől, Markov-láncokat memória nélküli folyamatgá teszi, amely kizárólag egy változó aktuális állapotától / műveletétől függ.

Vezetjük le ezt matematikailag:

Legyen a véletlenszerű folyamat {Xm, m = 0,1,2, ⋯}.

Ez a folyamat csak akkor Markov-lánc,

Markov-lánc - Bevezetés a Markov-láncokba - Edureka

minden m, j, i, i0, i1, ⋯ im & mínusz1 esetén

Véges számú állapot esetén, S = {0, 1, 2, ⋯, r}, ezt véges Markov-láncnak nevezzük.

P (Xm + 1 = j | Xm = i) itt az egyik állapotból a másikba való átmenet valószínűségét jelöli. Itt feltételezzük, hogy az átmenet valószínűsége független az időtől.

Ami azt jelenti, hogy P (Xm + 1 = j | Xm = i) nem függ az ’m’ értékétől. Ezért összefoglalhatjuk,

Markov láncformula - Bevezetés a Markov láncokba - Edureka

Tehát ez az egyenlet képviseli a Markov-lánc.

Most értsük meg, mi is pontosan Markov-lánc egy példával.

Markov láncpélda

Mielőtt példát mondanék, határozzuk meg, mi is az a Markov-modell:

Mi az a Markov modell?

A Markov-modell egy sztochasztikus modell, amely a véletlenszerű változókat úgy modellezi, hogy a változók a Markov tulajdonságot kövessék.

Most értsük meg, hogyan működik egy Markov modell egy egyszerű példával.

Mint korábban említettük, a Markov-láncokat szöveggeneráló és automatikus kiegészítési alkalmazásokban használják. Ebben a példában megnézünk egy példa (véletlenszerű) mondatot, és megnézzük, hogyan lehet modellezni Markov-láncok használatával.

Példa Markov-láncra - Bevezetés a Markov-láncokba - Edureka

A fenti mondat a mi példánk, tudom, hogy nincs sok értelme (nem muszáj), ez egy véletlenszerű szavakat tartalmazó mondat, ahol:

1. Kulcsok jelölje a mondatban szereplő egyedi szavakat, azaz 5 kulcsot (egy, kettő, jégeső, boldog, edureka)

2. Tokenek jelölje a szavak teljes számát, azaz 8 jelzőt.

Előre haladva meg kell értenünk ezeknek a szavaknak az előfordulási gyakoriságát, az alábbi ábra az egyes szavakat egy számmal együtt mutatja, amely a szó gyakoriságát jelöli.

Kulcsok és frekvenciák - Bevezetés a Markov-láncokba - Edureka

Tehát a bal oldali oszlop itt a kulcsokat, a jobb oszlop pedig a frekvenciákat jelöli.

A fenti táblázatból arra a következtetésre juthatunk, hogy az „edureka” kulcs négyszer annyiban kerül elő, mint bármely más kulcs. Fontos kikövetkeztetni az ilyen információkat, mert ez segíthet megjósolni, hogy egy adott pillanatban melyik szó fordulhat elő. Ha kitalálnám a példa mondat következő szavát, akkor az „edureka” kifejezéssel járnék, mivel annak előfordulási valószínűsége a legnagyobb.

A valószínűségről szólva egy másik mérőszám, amellyel tisztában kell lennie súlyozott eloszlások.

Esetünkben az „edureka” súlyozott eloszlása ​​50% (4/8), mert gyakorisága 4, a teljes 8 tokenből. A többi kulcs (egy, kettő, jégeső, boldog) mindegyikének 1/8-a esélye van (& asymp 13%).

Most, hogy megértettük a súlyozott eloszlást, és van egy elképzelésünk arról, hogy a konkrét szavak hogyan fordulnak elő gyakrabban, mint mások, folytathatjuk a következő részt.

A Markov-láncok megértése - Bevezetés a Markov-láncokba - Edureka

A fenti ábrán két további szót is felvettem, amelyek a mondat kezdetét és végét jelzik, az alábbi részben meg fogja érteni, miért tettem ezt.

Most rendeljük hozzá ezeknek a kulcsoknak a frekvenciáját is:

Frissített kulcsok és frekvenciák - Bevezetés a Markov-láncokba - Edureka

Most hozzunk létre egy Markov-modellt. Mint korábban említettük, egy Markov-modellt használnak a véletlenszerű változók modellezésére egy adott állapotban oly módon, hogy e változók jövőbeli állapota kizárólag az aktuális állapotuktól és nem a korábbi állapotoktól függ.

Tehát alapvetően Markov-modellben a következő állapot megjóslásához csak a jelenlegi állapotot kell figyelembe vennünk.

Az alábbi ábrán láthatja, hogy a mondatunkban szereplő egyes tokenek hogyan vezetnek egy másikhoz. Ez azt mutatja, hogy a jövőbeli állapot (következő token) az aktuális állapoton (jelenlegi token) alapul. Tehát ez a legalapvetőbb szabály a Markov-modellben.

Az alábbi ábra azt mutatja, hogy vannak olyan tokenpárok, ahol a párban lévő minden token ugyanabban a párban vezet a másikhoz.

Markov láncpárok - Bevezetés a Markov láncokba - Edureka

Az alábbi ábrán létrehoztam egy strukturális ábrázolást, amely minden kulcsot megjelenít egy sor következő lehetséges tokennel, amelyekkel párosítani lehet.

Markov láncpárok tömbje - Bevezetés a Markov láncokba - Edureka

A példa összefoglalásaként vegyen figyelembe egy olyan forgatókönyvet, ahol a fenti példában látott kulcsok és tokenek tömbjének használatával kell mondatot alkotnia. Mielőtt áttekintenénk ezt a példát, egy másik fontos pont az, hogy két kezdeti intézkedést kell megadnunk:

1. Kezdeti valószínűségeloszlás (azaz a kezdő állapot időpontjában = 0, („Start” gomb))

2. Átmenet valószínűsége az egyik állapotból a másikba ugráshoz (ebben az esetben az egyik tokenből a másikba való átmenet valószínűsége)

   megtalálja a legnagyobb számot egy java tömbben

Magában az elején definiáltuk a súlyozott eloszlást, tehát megvan a valószínűség és a kezdeti állapot, most folytassuk a példával.

• Tehát a kezdeti tokennel kezdve a [Start]

• Ezután csak egy lehetséges tokenünk van, azaz [egy]

• Jelenleg a mondatnak csak egy szava van, azaz „egy”

• Ebből a tokenből a következő lehetséges token az [edureka]

• A mondat „egy edureka” -ra frissül

• Az [edureka] -ból a következő tokenek egyikére léphetünk [kettő, jégeső, boldog, vége]

• 25% esély van arra, hogy a „kettőt” kiválasztják, ez az eredeti mondat kialakítását eredményezheti (egy edureka két edureka jégeső edureka boldog edureka). Ha azonban a „véget” választja, akkor a folyamat leáll, és végül egy új mondatot, azaz „egy edurekát” generálunk.

Pofozzon meg a hátán, mert csak felépít egy Markov modellt, és végigvezetett rajta egy tesztesetet. A fenti példa összefoglalásaként alapvetően a jelenlegi állapotot (jelen szót) használtuk a következő állapot (következő szó) meghatározásához. És pontosan ez egy Markov-folyamat.

Ez egy sztochasztikus folyamat, ahol a véletlenszerű változók egyik állapotból a másikba úgy lépnek át, hogy egy változó jövőbeli állapota csak a jelenlegi állapottól függ.

Folytassuk a következő lépéssel, és rajzoljuk ki a Markov modellt ehhez a példához.

Állapotátmeneti ábra - Bevezetés a Markov-láncokba - Edureka

A fenti ábra az államátmeneti diagram néven ismert. Erről bővebben az alábbi szakaszban fogunk beszélni, egyelőre csak arra emlékezzünk, hogy ez a diagram az egyik állapotból a másikba való átmeneteket és valószínűségeket mutatja.

Figyelje meg, hogy az ábra minden oválja egy kulcsot képvisel, és a nyilak a lehetséges billentyűk felé irányulnak, amelyek követhetik azt. A nyilakon lévő súlyok a az adott állapotokból / állapotokba való átmenet valószínűsége vagy súlyozott eloszlása.

Tehát csak arról volt szó, hogy működik a Markov Model. Most próbáljuk megérteni a Markov-folyamat néhány fontos terminológiáját.

Mi az átmenet valószínűségi mátrix?

A fenti részben egy Markov-modell működését vitattuk meg egy egyszerű példával, most pedig értsük meg a Markov-folyamat matematikai terminológiáit.

A Markov-folyamat során mátrixot használunk az egyik állapotból a másikba való átmenet valószínűségének ábrázolására. Ezt a mátrixot nevezzük Átmenet vagy valószínűségi mátrixnak. Általában P-vel jelöljük.

Átmeneti mátrix - Bevezetés a Markov-láncokba - Edureka

Megjegyezzük, hogy a pij & ge0 és az „i” minden értékre

Átmeneti mátrix képlet - Bevezetés Markov láncokba - Edureka

Hadd magyarázzam el ezt. Feltéve, hogy jelenlegi állapotunk „i”, a következő vagy a következő állapotnak a lehetséges állapotok egyikének kell lennie. Ezért miközben k összes értékének összegzését meg kell kapnunk.

Mi az állapotátmenet-diagram?

A Markov-modellt egy államátmeneti ábra ábrázolja. A diagram a Markov-lánc különböző állapotai közötti átmeneteket mutatja. Értsük meg egy példával az átmeneti mátrixot és az állapotátmenet mátrixot.

Átmeneti mátrix példa

Vegyünk egy Markov-láncot három 1., 2. és 3. állapottal és a következő valószínűségekkel:

Átmeneti mátrix példa - Bevezetés a Markov-láncokba - Edureka

Állapotátmeneti ábra - Bevezetés a Markov-láncokba - Edureka

A fenti ábra a Markov-lánc állapotátmeneti diagramját ábrázolja. Itt az 1,2 és 3 a három lehetséges állapot, és az egyik állapotból a másik állapotba mutató nyilak a pij átmeneti valószínűségeket jelentik. Amikor, pij = 0, ez azt jelenti, hogy nincs átmenet az „i” és a „j” állapot között.

Most, hogy mi ismerje a matematikát és a Markov-láncok logikáját, futtassunk egy egyszerű bemutatót, és értsük meg, hol használhatók Markov-láncok.

Markov lánc Pythonban

A bemutató futtatásához a Python-t fogom használni, így ha nem ismeri a Python-t, akkor a következő blogokat tekintheti meg:

2. Hogyan lehet megtanulni a Python 3 alkalmazást a Scratch-ból - Útmutató kezdőknek

Most kezdjük el a kódolást!

Markov lánc szöveggenerátor

Probléma nyilatkozat: A Markov Property alkalmazásához és olyan Markov modell létrehozásához, amely szövegszimulációkat generálhat Donald Trump beszédadatok tanulmányozásával.

Adatkészlet leírása: A szöveges fájl tartalmazza a Donald Trump által 2016-ban tartott beszédek listáját.

Logika: Alkalmazza Markov Property-t Donald Trump beszédének előállításához, figyelembe véve a beszédben használt minden szót, és minden szóhoz hozzon létre egy szótárt a következő szavakból.

1. lépés: Importálja a szükséges csomagokat

importálja a numpy-t np-ként

2. lépés: Olvassa el az adatsort

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Köszönöm annyira. Ez olyan kedves. Hát nem nagyszerű srác. Nem kap tisztességes sajtót, nem kap. Csak nem igazságos. És el kell mondanom, hogy itt vagyok, és nagyon erősen itt vagyok, mert nagyon tisztelem Steve Kinget, nagy tiszteletet tanúsítom a Citizens United, David és mindenki iránt, és óriási tiszteletet tanúsítok a Tea Party iránt. Továbbá az iowaiak is. Van bennük valami közös. Szorgalmas emberek ....

3. lépés: Az adatkészlet felosztása egyes szavakra

corpus = trump.split () # Jelenítse meg a korpusz nyomtatását (korpusz) „erőteljes”, „de”, „nem”, „erőteljes”, „hasonló”, „minket”, „Irán”, „van”, „ magva ”,„ terror ”, ...

Ezután hozzon létre egy olyan függvényt, amely a beszédekben előállítja a különböző szópárokat. Helytakarékosság érdekében egy generátor objektumot fogunk használni.

4. lépés: Párok létrehozása a kulcsokhoz és a követőszavakhoz

def make_pairs (korpusz): az i tartományban (len (corpus) - 1): hozam (corpus [i], corpus [i + 1]) párok = make_pairs (korpusz)

Ezután inicializáljunk egy üres szótárat a szavpárok tárolására.

Ha a pár első szava már kulcs a szótárban, egyszerűen csak csatolja a következő potenciális szót a szót követő szavak listájához. De ha a szó nem kulcs, akkor hozzon létre egy új bejegyzést a szótárban, és rendelje hozzá a kulcsot a pár első szavához.

5. lépés: A szótár hozzáfűzése

word_dict = {} a word_1 szóhoz, a word_2 párban: ha word_1 a word_dict.keys-ben (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Ezután véletlenszerűen kiválasztunk egy szót a korpuszból, amely elindítja a Markov-láncot.

6. lépés: Készítse el a Markov modellt

#véletlenszerűen válassza ki az első szót first_word = np.random.choice (corpus) # Válassza ki az első szót nagybetűs szóként, hogy a kiválasztott szó ne kerüljön a mondat közé, míg first_word.islower (): # a kiválasztott lánc = [first_word] # Kezdje a stimulált szavak számát n_words = 20

Az első szó után a lánc minden egyes szavát véletlenszerűen mintavételezzük azoknak a szavaknak a listájáról, amelyek ezt az adott szót követték Trump élő beszédeiben. Ezt az alábbi kódrészlet mutatja:

i tartományban (n_words): chain.append (np.random.choice (word_dict [lánc [-1]]))

7. lépés: Jóslatok

Végül jelenítsük meg a stimulált szöveget.

A #Join karakterláncként adja vissza a láncot ('' .join (chain)) A hihetetlen emberek száma. És Hillary Clintonnak vannak embereink, és olyan nagyszerű munka. És nem fogjuk megverni Obamát

Tehát ezt a generált szöveget kaptam, figyelembe véve Trump beszédét. Lehet, hogy ennek nincs sok értelme, de elég jó ahhoz, hogy megértsd, hogyan használhatók Markov-láncok szövegek automatikus létrehozására.

Most nézzünk meg még néhány alkalmazást és hogyan használják őket a valós problémák megoldására.

Markov lánc alkalmazások

Az alábbiakban felsoroljuk a Markov-láncok valós alkalmazásait:

1. Google PageRank: Az egész web Markov-modellnek tekinthető, ahol minden weboldal állapot lehet, és az ezen oldalak közötti hivatkozások vagy hivatkozások valószínűleg valószínű átmeneteknek tekinthetők. Tehát alapvetően, függetlenül attól, hogy melyik weboldalon kezd szörfözni, az esély, hogy eljutunk egy bizonyos weboldalra, mondjuk, X fix valószínűség.

2. Gépelés szó előrejelzése: A következő szavak előrejelzéséhez ismert Markov-láncok használhatók. Automatikus kiegészítésben és javaslatokban is felhasználhatók.

3. Subreddit szimuláció: Biztosan találkoztál már a Reddittel és interakciót folytattál az egyik szálukon vagy alfeladatukon. A Reddit egy subreddit szimulátort használ, amely hatalmas mennyiségű adatot fogyaszt, amely a csoportjaikban tartott összes megjegyzést és megbeszélést tartalmazza. A Markov-láncok felhasználásával a szimulátor szó-szó valószínűségeket produkál, hogy hozzászólásokat és témákat hozzon létre.

4. Szöveggenerátor: A Markov-láncokat leggyakrabban dummy szövegek létrehozására, vagy nagy esszék készítésére és beszédek összeállítására használják. Az interneten látható névgenerátorokban is használják.

Most, hogy tudja, hogyan oldja meg a valós problémákat a Markov Láncok használatával, biztos vagyok benne, hogy kíváncsi rá, hogy többet tudjon meg. Az alábbiakban felsoroljuk azokat a blogokat, amelyek segítenek eljutni más statisztikai fogalmakba:

Ezzel a Markov Láncok Bevezetés blogjának végére értünk. Ha bármilyen kérdése van ezzel a témával kapcsolatban, kérjük, hagyjon megjegyzést alább, és kapcsolatba lépünk Önnel.

Tartson velünk további blogokat a felkapott technológiákról.

Ha online strukturált képzést keres az adattudományban, az edureka! van egy speciálisan kurátora program, amely szakértelmet szerez a statisztikákban, az adatkezelésben, a feltáró adatelemzésben, a gépi tanulási algoritmusokban, például a K-Means klaszterezésben, a döntési fákban, a Random Forestben és a Naiv Bayes-ben. Megtanulja az idősor, a szövegbányászat fogalmát és a mély tanulás bevezetését is. Hamarosan új tételek kezdődnek erre a tanfolyamra !!