Wprowadzenie do łańcuchów Markowa

Łańcuchy Markowa są dość powszechnym i stosunkowo prostym sposobem statystycznego modelowania procesów losowych. Zostały one wykorzystane w wielu różnych dziedzinach, od generowania tekstów po modelowanie finansowe. Popularnym przykładem jest r/SubredditSimulator, który używa łańcuchów Markowa do zautomatyzowania tworzenia treści dla całego subreddita. Ogólnie rzecz biorąc, łańcuchy Markowa są koncepcyjnie dość intuicyjne i są bardzo przystępne w tym sensie, że można je zaimplementować bez użycia zaawansowanych pojęć statystycznych lub matematycznych. Są świetnym sposobem na rozpoczęcie nauki o modelowaniu probabilistycznym i technikach data science.

Scenariusz

Na początek opiszę je na bardzo powszechnym przykładzie:

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.

Ten przykład ilustruje wiele kluczowych pojęć łańcucha Markowa. Łańcuch Markowa zasadniczo składa się z zestawu przejść, które są określone przez pewien rozkład prawdopodobieństwa, które spełniają własność Markowa.

Zauważ, jak w przykładzie, rozkład prawdopodobieństwa jest uzyskany wyłącznie poprzez obserwację przejść z bieżącego dnia na następny. Ilustruje to własność Markowa, unikalną cechę procesów Markowa, która sprawia, że są one pozbawione pamięci. To zazwyczaj sprawia, że nie są one w stanie skutecznie tworzyć sekwencji, w których można by się spodziewać wystąpienia jakiegoś podstawowego trendu. Na przykład, podczas gdy łańcuch Markowa może być w stanie naśladować styl pisania autora na podstawie częstotliwości słów, nie będzie w stanie wyprodukować tekstu, który zawiera głębokie znaczenie lub znaczenie tematyczne, ponieważ są one rozwijane przez znacznie dłuższe sekwencje tekstu. Brakuje im zatem zdolności do tworzenia treści zależnych od kontekstu, ponieważ nie mogą wziąć pod uwagę pełnego łańcucha wcześniejszych stanów.

Model

Formalnie, łańcuch Markowa jest automatem probabilistycznym. Rozkład prawdopodobieństwa przejść stanów jest zwykle reprezentowany jako macierz przejść łańcucha Markowa. Jeśli łańcuch Markowa ma N możliwych stanów, macierz będzie macierzą N x N, taką, że wpis (I, J) jest prawdopodobieństwem przejścia ze stanu I do stanu J. Dodatkowo, macierz przejść musi być macierzą stochastyczną, macierzą, której wpisy w każdym wierszu muszą sumować się do dokładnie 1. Ma to pełny sens, ponieważ każdy wiersz reprezentuje swój własny rozkład prawdopodobieństwa.

Dodatkowo, łańcuch Markowa posiada również wektor stanu początkowego, reprezentowany jako macierz N x 1 (wektor), który opisuje rozkład prawdopodobieństwa rozpoczęcia w każdym z N możliwych stanów. Pozycja I wektora opisuje prawdopodobieństwo rozpoczęcia łańcucha w stanie I.

Te dwie jednostki są zazwyczaj wszystkim, co jest potrzebne do reprezentacji łańcucha Markowa.

Wiemy teraz jak uzyskać szansę przejścia z jednego stanu do drugiego, ale jak znaleźć szansę tego przejścia w wielu krokach? Aby to sformalizować, chcemy teraz określić prawdopodobieństwo przejścia ze stanu I do stanu J na przestrzeni M kroków. Jak się okazuje, jest to bardzo proste do ustalenia. Biorąc pod uwagę macierz przejścia P, można to wyznaczyć poprzez obliczenie wartości wejścia (I, J) macierzy otrzymanej przez podniesienie P do potęgi M. Dla małych wartości M, można to łatwo zrobić ręcznie poprzez wielokrotne mnożenie. Jednakże, dla dużych wartości M, jeśli jesteś zaznajomiony z prostą algebrą liniową, bardziej efektywnym sposobem podniesienia macierzy do potęgi jest najpierw diagonalizacja macierzy.

Wniosek

Teraz, gdy znasz podstawy łańcuchów Markowa, powinieneś być w stanie łatwo zaimplementować je w wybranym języku. Jeśli kodowanie nie jest Twoją mocną stroną, istnieje również wiele bardziej zaawansowanych właściwości łańcuchów i procesów Markowa, w które możesz się zagłębić. Moim zdaniem, naturalnym postępem na drodze teorii jest przejście w kierunku Ukrytych Procesów Markowa lub MCMC. Proste łańcuchy Markowa są budulcem innych, bardziej zaawansowanych technik modelowania, więc mając tę wiedzę, możesz teraz przejść do różnych technik w ramach tematów takich jak modelowanie przekonań i próbkowanie.