Úvod do Markovových řetězců

Markovovy řetězce jsou poměrně běžným a relativně jednoduchým způsobem statistického modelování náhodných procesů. Používají se v mnoha různých oblastech, od generování textu po finanční modelování. Oblíbeným příkladem je r/SubredditSimulator, který používá Markovovy řetězce k automatizaci tvorby obsahu celého subredditu. Celkově jsou Markovovy řetězce koncepčně poměrně intuitivní a jsou velmi přístupné, protože je lze implementovat bez použití pokročilých statistických nebo matematických konceptů. Jsou skvělým způsobem, jak se začít učit o pravděpodobnostním modelování a technikách datové vědy.

Scénář

Na úvod je popíšu na velmi běžném příkladu:

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.

Tento příklad ilustruje mnoho klíčových konceptů Markovova řetězce. Markovský řetězec se v podstatě skládá z množiny přechodů, které jsou určeny nějakým rozdělením pravděpodobnosti splňujícím Markovovu vlastnost.

Všimněte si, že v příkladu je rozdělení pravděpodobnosti získáno pouze pozorováním přechodů z aktuálního dne do následujícího. To ilustruje Markovovu vlastnost, jedinečnou vlastnost Markovových procesů, která je činí bezpaměťovými. Díky tomu obvykle nejsou schopny úspěšně vytvářet posloupnosti, v nichž by se očekával nějaký základní trend. Například zatímco Markovův řetězec může být schopen napodobit styl psaní autora na základě četnosti slov, nebyl by schopen vytvořit text, který obsahuje hluboký smysl nebo tematický význam, protože ty se vyvíjejí v mnohem delších sekvencích textu. Chybí jim tedy schopnost vytvářet obsah závislý na kontextu, protože nemohou zohlednit celý řetězec předchozích stavů.

Model

Formálně je Markovův řetězec pravděpodobnostní automat. Pravděpodobnostní rozdělení přechodů mezi stavy je obvykle reprezentováno jako matice přechodů Markovova řetězce. Má-li Markovův řetězec N možných stavů, bude matice matice N x N taková, že zápis (I, J) je pravděpodobnost přechodu ze stavu I do stavu J. Navíc matice přechodů musí být stochastická matice, tedy matice, jejíž zápisy v každém řádku musí dávat součet přesně 1. To dává naprostý smysl, protože každý řádek představuje své vlastní rozdělení pravděpodobnosti.

Dále, má Markovův řetězec také počáteční stavový vektor, reprezentovaný jako matice N x 1 (vektor), který popisuje rozdělení pravděpodobnosti začátku každého z N možných stavů. Položka I vektoru popisuje pravděpodobnost začátku řetězce ve stavu I.

Tyto dvě entity jsou obvykle vše, co je třeba k reprezentaci Markovova řetězce.

Teď už víme, jak získat pravděpodobnost přechodu z jednoho stavu do druhého, ale jak zjistit pravděpodobnost, že tento přechod nastane ve více krocích? Abychom to formalizovali, chceme nyní určit pravděpodobnost přechodu ze stavu I do stavu J v průběhu M kroků. Jak se ukazuje, je to ve skutečnosti velmi jednoduché zjistit. Při dané matici přechodů P ji lze určit výpočtem hodnoty položky (I, J) matice získané zvýšením P na mocninu M. Pro malé hodnoty M to lze snadno provést ručně opakovaným násobením. Pro velké hodnoty M je však, pokud jste obeznámeni s jednoduchou lineární algebrou, efektivnějším způsobem, jak zvýšit matici na mocninu, matici nejprve diagonalizovat.

Závěr

Teď, když znáte základy Markovových řetězců, byste měli být schopni je snadno implementovat v jazyce podle svého výběru. Pokud kódování není vaší silnou stránkou, existuje také mnoho pokročilejších vlastností Markovových řetězců a Markovových procesů, do kterých se můžete ponořit. Podle mého názoru by přirozený postup po teoretické cestě směřoval ke skrytým Markovovým procesům nebo MCMC. Jednoduché Markovovy řetězce jsou stavebními kameny dalších, sofistikovanějších modelovacích technik, takže s těmito znalostmi můžete nyní přejít k různým technikám v rámci témat, jako je modelování víry a vzorkování.