Czy skończona maszyna stanowa jest tylko implementacją łańcucha Markowa? Jakie są różnice między nimi?
Odpowiedzi:
Ł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.
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.
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”.
Przeczytaj te artykuły:
Powiązania między automatami probabilistycznymi a ukrytymi modelami Markowa (autor: Pierre Dupont) http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/HMM_PA_pres_n4.pdf
[Podręcznik teorii mózgu i sieci neuronowych] Ukryte modele Markowa i inne automaty stanu skończonego do przetwarzania sekwencji http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3344&rep=rep1&type=pdf
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.
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.
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.