Czy łańcuch Markowa to to samo, co skończona maszyna stanowa?

80

Czy skończona maszyna stanowa jest tylko implementacją łańcucha Markowa? Jakie są różnice między nimi?

math statistics state-machine fsm markov-chains Carson
źródło
24
Możesz pomyśleć o łańcuchu Markowa jako FSM, w którym przejścia są napędzane przez prawdopodobieństwo
Dr. Belisarius

Odpowiedzi:

61

Łańcuchy Markowa mogą być reprezentowane przez maszyny skończone. Chodzi o to, że łańcuch Markowa opisuje proces, w którym przejście do stanu w czasie t + 1 zależy tylko od stanu w czasie t. Najważniejszą rzeczą, o której należy pamiętać, jest to, że przejścia w łańcuchu Markowa są raczej probabilistyczne niż deterministyczne, co oznacza, że ​​nie zawsze można powiedzieć z całkowitą pewnością, co się stanie w czasie t + 1.

Artykuły Wikipedii na temat maszyn skończonych zawierają podsekcję poświęconą procesom skończonego łańcucha Markowa , polecam przeczytać ją, aby uzyskać więcej informacji. Również artykuł Wikipedii na temat łańcuchów Markowa zawiera krótkie zdanie opisujące użycie maszyn skończonych w reprezentowaniu łańcucha Markowa. To stwierdza:

Maszyna skończonych stanów może być używana jako reprezentacja łańcucha Markowa. Zakładając sekwencję niezależnych i identycznie rozłożonych sygnałów wejściowych (na przykład symbole z binarnego alfabetu wybranego przez rzuty monetą), jeśli maszyna jest w stanie y w czasie n, to prawdopodobieństwo, że przejdzie do stanu x w czasie n + 1 zależy tylko od aktualnego stanu.

James Thompson
źródło
2
Właściwie to, co twierdzisz tutaj o łańcuchu Markowa, nie jest w 100% poprawne. Wspomniałeś tutaj o „procesie Markowa pierwszego rzędu”. W przypadku procesu Markowa drugiego rzędu, następny stan będzie zależał od stanów ostatnich 2 kroków czasowych, ...... Automat stanów jest specjalnym przypadkiem łańcucha Markowa; ponieważ łańcuch Markowa ma charakter stochastyczny. O ile wiem, maszyna stanowa jest deterministyczna.
A. Isaac
5
Bez zastrzeżeń, termin łańcuch Markowa oznacza dyskretny proces stochastyczny z właściwością Markowa, co oznacza, że ​​nie zależy od przeszłych stanów. Oryginalny plakat nie pytał o procesy Markowa wyższego rzędu, więc nie są one tak naprawdę istotne. Maszyna skończonych stanów jest ogólnie pojęciem chwytliwym dla automatu skończonego, mogą one mieć charakter deterministyczny lub niedeterministyczny.
Tim Seguine
28

Chociaż łańcuch Markowa jest skończoną maszyną stanową, wyróżnia się tym, że jego przejścia są stochastyczne, tj. Losowe i opisywane przez prawdopodobieństwa.

Oliver Charlesworth
źródło
3
Dzięki za to, dokładnie to, czego szukałem.
Stefan Mai
4
Czy mogę powiedzieć, stochastyczne automaty skończone?
Souradeep Nanda
19

Oba są podobne, ale pozostałe wyjaśnienia są nieco błędne. Tylko FINITE łańcuchy Markowa mogą być reprezentowane przez FSM. Łańcuchy Markowa pozwalają na nieskończoną przestrzeń stanów. Jak wskazano, przejścia łańcucha Markowa są opisywane przez prawdopodobieństwa, ale należy również wspomnieć, że prawdopodobieństwa przejścia mogą zależeć tylko od aktualnego stanu. Bez tego ograniczenia zostałby nazwany „dyskretnym procesem stochastycznym”.

Tim Seguine
źródło
Właściwie uważam, że można by to nazwać „niestacjonarnym”.
Michael Tamillow,
@Michael Mogę się mylić, ponieważ od jakiegoś czasu nie zajmowałem się tematem, ale pomyślałem, że „stacjonarność” dotyczy zależności od czasu. Mogę się mylić, ale wydaje się to ortogonalne.
Tim Seguine,
„Proces” jest zwykle stosowane do ekspresji ciągłej wersji czasu określenie „łańcuch” (odnośnik: teorii prawdopodobieństwa: pole zwięzły Rozanov) i FSM można przedstawić nieskończenie lub zdarzeniami lub nie deterministyczny . Jedyną zależnością, jaką mogę sobie wyobrazić, poza stanem, byłby czas.
Michael Tamillow,
@Michael „proces” to termin ogólny. Może to być czas ciągły lub dyskretny. FSM nie może być reprezentowany w nieskończoność, ma w nazwie słowo skończony . Podane przez ciebie łącze mówi nawet, że nie jest maszyną skończoną. Nie ja poruszyłeś kwestię zależności czasowej, ale w dyskretnych procesach czasu indeks sekwencji jest zwykle uważany za czas. W tym sensie, tak, proces stochastyczny w czasie dyskretnym byłby niestacjonarny, ale nie jest to wystarczająco opisowe, ponieważ potencjalnie mógłby to być również czas ciągły. Szedłem na superset, a nie na uzupełnienie mojego nazewnictwa.
Tim Seguine,
3

Myślę, że to powinno odpowiedzieć na twoje pytanie:

https://en.wikipedia.org/wiki/Probabilistic_automaton

I masz dobry pomysł - są one prawie takie same, podzbiory, nadzbiory i modyfikacje w zależności od tego, jaki przymiotnik opisuje łańcuch lub automat. Automaty zazwyczaj również pobierają dane wejściowe, ale jestem pewien, że istniały artykuły wykorzystujące „łańcuchy Markowa” z danymi wejściowymi.

Pomyśl o rozkładzie Gaussa vs. rozkład normalny - te same pomysły, różne dziedziny. Automaty należą do informatyki, Markov do prawdopodobieństwa i statystyki.

Michael Tamillow
źródło
1

Jeśli odkładasz na bok wewnętrzne szczegóły robocze, maszyna stanów skończonych jest jak zwykła wartość, podczas gdy łańcuch markowa jest jak zmienna losowa (dodaj prawdopodobieństwo do zwykłej wartości). Tak więc odpowiedź na pierwotne pytanie brzmi: nie, to nie to samo. W sensie probabilistycznym łańcuch Markowa jest przedłużeniem skończonej maszyny stanów.

liang
źródło
1

Myślę, że większość odpowiedzi nie jest odpowiednia. Proces Markowa jest generowany przez (probablistyczną) skończoną maszynę stanów, ale nie każdy proces generowany przez probablistyczną skończoną maszynę stanów jest procesem Markowa. Np. Ukryte Procesy Markowa są zasadniczo takie same jak procesy generowane przez probabilistyczne maszyny skończone, ale nie każdy Ukryty Proces Markowa jest Procesem Markowa.

Radony
źródło