Bevezetés a Markov-láncokba

A Markov-láncok meglehetősen gyakori és viszonylag egyszerű módja a véletlen folyamatok statisztikai modellezésének. Számos különböző területen használják őket, a szöveggenerálástól kezdve a pénzügyi modellezésig. Egy népszerű példa az r/SubredditSimulator, amely Markov-láncokat használ egy egész subreddit tartalomkészítésének automatizálására. Összességében a Markov-láncok koncepcionálisan meglehetősen intuitívak, és nagyon könnyen hozzáférhetőek, mivel fejlett statisztikai vagy matematikai fogalmak használata nélkül is megvalósíthatók. Remek módja annak, hogy elkezdjük a valószínűségi modellezés és az adattudományi technikák megismerését.

Scenario

Kezdésként egy nagyon gyakori példán keresztül ismertetem őket:

Imagine that there were two possible states for weather: sunny or cloudy. You can always directly observe the current weather state, and it is guaranteed to always be one of the two aforementioned states.Now, you decide you want to be able to predict what the weather will be like tomorrow. Intuitively, you assume that there is an inherent transition in this process, in that the current weather has some bearing on what the next day's weather will be. So, being the dedicated person that you are, you collect weather data over several years, and calculate that the chance of a sunny day occurring after a cloudy day is 0.25. You also note that, by extension, the chance of a cloudy day occurring after a cloudy day must be 0.75, since there are only two possible states.You can now use this distribution to predict weather for days to come, based on what the current weather state is at the time.

Ez a példa a Markov-lánc számos kulcsfogalmát szemlélteti. Egy Markov-lánc lényegében olyan átmenetek halmazából áll, amelyeket valamilyen valószínűségi eloszlás határoz meg, amelyek kielégítik a Markov-tulajdonságot.

Nézzük meg, hogy a példában a valószínűségi eloszlást kizárólag az aktuális napról a következő napra történő átmenetek megfigyelésével kapjuk. Ez szemlélteti a Markov-tulajdonságot, a Markov-folyamatok azon egyedi tulajdonságát, amely emlékezetmentessé teszi őket. Emiatt jellemzően nem képesek sikeresen előállítani olyan szekvenciákat, amelyekben valamilyen mögöttes trend várható. Például, bár egy Markov-lánc képes lehet egy szerző írásmódját utánozni a szavak gyakorisága alapján, de nem képes olyan szöveget előállítani, amely mély jelentést vagy tematikus jelentőséget tartalmaz, mivel ezek sokkal hosszabb szövegrészletek során alakulnak ki. Ezért nem képesek kontextusfüggő tartalmak előállítására, mivel nem tudják figyelembe venni az előzetes állapotok teljes láncolatát.

A modell

Formálisan a Markov-lánc egy valószínűségi automata. Az állapotátmenetek valószínűségi eloszlását jellemzően a Markov-lánc átmenetmátrixaként ábrázoljuk. Ha a Markov-láncnak N lehetséges állapota van, akkor a mátrix egy N x N mátrix lesz, úgy, hogy a (I, J) bejegyzés az I állapotból a J állapotba való átmenet valószínűsége. Továbbá az átmenetmátrixnak sztochasztikus mátrixnak kell lennie, olyan mátrixnak, amelynek minden sorában a bejegyzéseknek pontosan 1-et kell adniuk. Ennek teljes értelme van, mivel minden sor a saját valószínűségi eloszlását reprezentálja.

Kiegészítésképpen, egy Markov-láncnak van egy N x 1 mátrixként (vektorként) ábrázolt kezdeti állapotvektora is, amely az N lehetséges állapotok mindegyikéből való kiindulás valószínűségi eloszlását írja le. A vektor I. bejegyzése azt a valószínűséget írja le, hogy a lánc az I. állapotból indul.

Ez a két egység általában elegendő egy Markov-lánc ábrázolásához.

Most már tudjuk, hogyan kapjuk meg az egyik állapotból a másikba való átmenet esélyét, de mi a helyzet annak az esélyével, hogy ez az átmenet több lépésben következik be? Ennek formalizálására most meg akarjuk határozni az I állapotból a J állapotba való átmenet valószínűségét M lépésen keresztül. Mint kiderül, ezt valójában nagyon egyszerű kideríteni. Adott egy P átmenetmátrix, ezt úgy határozhatjuk meg, hogy kiszámítjuk a mátrix (I, J) bejegyzésének értékét, amelyet úgy kapunk, hogy P-t M hatványára emeljük. M kis értékei esetén ez könnyen elvégezhető kézzel, ismételt szorzással. Nagy M értékek esetén azonban, ha ismeri az egyszerű lineáris algebrát, a mátrix hatványra emelésének hatékonyabb módja, ha először diagonalizálja a mátrixot.

Következtetés

Most, hogy ismeri a Markov-láncok alapjait, most már képesnek kell lennie arra, hogy könnyen megvalósítsa őket az Ön által választott nyelven. Ha a kódolás nem az erősséged, a Markov-láncok és Markov-folyamatok számos fejlettebb tulajdonságában is elmerülhetsz. Véleményem szerint az elméleti úton a természetes fejlődés a rejtett Markov-folyamatok vagy az MCMC felé vezetne. Az egyszerű Markov-láncok más, kifinomultabb modellezési technikák építőkövei, így ezzel a tudással már továbbléphet az olyan témákon belüli különböző technikák felé, mint a hitmodellezés és a mintavételezés.