Markov chain

Markov chain (tsz. Markov chains)

1. (informatika) Markov-lánc

A Markov-lánc (angolul Markov chain) egy olyan sztochasztikus (valószínűségi) modell, amely állapotok közötti átmeneteket ír le egy valószínűségi szabály alapján. A Markov-lánc különlegessége, hogy a következő állapot csak az aktuális állapottól függ, és nem az odavezető múltbeli úttól. Ezt az elvet nevezzük Markov-tulajdonságnak vagy memória nélküli viselkedésnek.

• Állapottér (state space): Az összes lehetséges állapot halmaza, amelyben a rendszer tartózkodhat. Lehet véges vagy végtelen. Példa: Állapotok = {Napfényes, Felhős, Esős}
• Átmeneti valószínűségek (transition probabilities): Az egyes állapotok közötti mozgás valószínűsége. Példa: ${\textstyle P({\text{Felhős}}\to {\text{Esős}})=0{,}3}$
• Átmeneti mátrix (transition matrix): Egy mátrix, amely az összes állapotpár közötti átmeneti valószínűségeket tartalmazza.
• Markov-tulajdonság:

$${\displaystyle P(X_{n+1}=x\mid X_{n}=x_{n},X_{n-1}=x_{n-1},\dots ,X_{0}=x_{0})=P(X_{n+1}=x\mid X_{n}=x_{n})}$$

Ez azt jelenti, hogy a jövő csak a jelen állapottól függ, nem a múlttól.

Az állapotváltozás diszkrét lépésekben történik. Ilyenkor egy idősorozatot kapunk, ahol minden lépésben egy adott valószínűség szerint történik az állapotváltozás.

Az állapotváltozások folyamatos időben, exponenciálisan eloszló időközönként történnek. Ilyen például a Poisson-folyamat.

Tegyük fel, hogy van három állapot: A, B, C. Az átmeneti mátrix például lehet:

$${\displaystyle P={\begin{bmatrix}0.5&0.3&0.2\\0.4&0.4&0.2\\0.3&0.3&0.4\end{bmatrix}}}$$

• Minden sor az aktuális állapotot jelenti
• Az oszlopok a következő állapotokat
• A sorösszeg mindig 1

Ez azt adja meg, hogy a rendszer milyen valószínűséggel indul az egyes állapotokból. Például:

$${\displaystyle \pi _{0}=}$$

→ A rendszer biztosan az A állapotból indul.

A Markov-lánc evolúciója során az állapoteloszlás így alakul:

$${\displaystyle \pi _{n+1}=\pi _{n}\cdot P}$$

Többszöri szorzással meghatározható a valószínűségeloszlás bármelyik időpillanatban:

$${\displaystyle \pi _{n}=\pi _{0}\cdot P^{n}}$$

Egy stacionárius eloszlás ${\textstyle \pi }$ teljesíti:

$${\displaystyle \pi =\pi \cdot P}$$

Ez az eloszlás nem változik idővel — ha a rendszer ebben indul, mindig ugyanilyen marad. A legtöbb ergodikus (azaz “jó viselkedésű”) Markov-láncnak létezik ilyen.

• Visszatérő állapot: A rendszer előbb-utóbb biztosan visszatér ebbe az állapotba.
• Ergodikus lánc: Olyan lánc, amely minden állapotból bármelyik másikba eljuthat, véges időn belül.
• Periodikus állapot: Csak bizonyos lépésszámra térhet vissza önmagába (pl. minden második lépésre).

Állapotok: Napos (N), Felhős (F), Esős (E)

Átmeneti mátrix:

$${\displaystyle P={\begin{bmatrix}0.6&0.3&0.1\\0.2&0.5&0.3\\0.1&0.4&0.5\end{bmatrix}}}$$

Ha ma napos az idő, akkor holnap 60% eséllyel marad napos, 30% eséllyel felhős, stb.

Állapotok: Kezdőlap (K), Termékoldal (T), Kosár (C), Kilépett (L)

Egy Markov-lánccal modellezhetjük, hogyan mozog a felhasználó az oldalon. Ebből megérthető, hová érdemes reklámot tenni.

A játékos mozgása a táblán egy Markov-láncként modellezhető, ahol a dobókocka valószínűsége határozza meg az átmeneteket.

• Gépi tanulás: Rejtett Markov-modellek (HMM) hangfelismerésben, nyelvfeldolgozásban.
• Pénzügy: Árak változása (pl. részvények), kockázatelemzés.
• Hálózatelemzés: Google PageRank algoritmusa is egy Markov-láncon alapul.
• Karbantartás: Egy gép működési és hibás állapotait is modellezhetjük így.
• Bioinformatika: DNS-szekvenciák mintázatainak elemzése.

Speciális Markov-modell, ahol az állapotokat nem közvetlenül látjuk, csak a hozzájuk kapcsolódó megfigyeléseket. Használatos beszédfelismerésben, szöveganalízisben, genomikában.

Egy fontos numerikus módszer, amely Markov-láncokat használ valószínűségi eloszlásokból való mintavételre. Kulcsszerepet játszik a Bayes-statisztikában, gépi tanulásban és fizikai szimulációkban.

A Markov-lánc egy hatékony eszköz szekvenciális, véletlenszerű rendszerek modellezésére, ahol az aktuális állapot határozza meg a következő lépés valószínűségét. Alkalmas időfüggő döntések, viselkedésmodellek, rendszerek stabilitásának vizsgálatára, és sok területen alkalmazzák az ipartól kezdve a gépi tanulásig.

Főbb tulajdonságai:

• Jövőbeli állapot csak a jelen állapottól függ (Markov-tulajdonság)
• A rendszer állapotváltozásait valószínűségek írják le
• Az állapoteloszlás hosszú távon elérhet stabilitást (stacionárius eloszlás)

• Markov chain - Szótár.net (en-hu)
• Markov chain - Sztaki (en-hu)
• Markov chain - Merriam–Webster
• Markov chain - Cambridge
• Markov chain - WordNet
• Markov chain - Яндекс (en-ru)
• Markov chain - Google (en-hu)
• Markov chain - Wikidata
• Markov chain - Wikipédia (angol)