Марковская цепь - это то же самое, что конечный автомат?
Является ли конечный автомат просто реализацией цепи Маркова? Каковы различия между этими двумя?
6 ответов
Цепи Маркова могут быть представлены конечными автоматами. Идея состоит в том, что цепь Маркова описывает процесс, в котором переход в состояние в момент времени t+1 зависит только от состояния в момент времени t. Главное, что нужно иметь в виду, это то, что переходы в цепи Маркова скорее вероятностные, чем детерминированные, что означает, что вы не всегда можете с полной уверенностью сказать, что произойдет в момент времени t+1.
В статьях Википедии о машинах с конечным числом состояний есть подраздел о процессах с конечной цепью Маркова, я рекомендовал бы прочитать его для получения дополнительной информации. Кроме того, статья в Википедии о цепях Маркова содержит краткое предложение, описывающее использование конечных автоматов при представлении цепей Маркова. Это заявляет:
Конечный автомат можно использовать как представление цепи Маркова. Предполагая последовательность независимых и одинаково распределенных входных сигналов (например, символов из двоичного алфавита, выбранного подбрасыванием монет), если машина находится в состоянии y в момент времени n, то вероятность того, что она переместится в состояние x в момент времени n + 1 зависит только от текущего состояния.
Хотя цепь Маркова является конечным автоматом, она отличается тем, что ее переходы являются стохастическими, то есть случайными, и описываются вероятностями.
Эти два схожи, но другие объяснения здесь немного ошибочны. Только конечные цепи Маркова могут быть представлены FSM. Цепи Маркова допускают бесконечное пространство состояний. Как было указано, переходы цепи Маркова описываются вероятностями, но также важно отметить, что вероятности переходов могут зависеть только от текущего состояния. Без этого ограничения его можно было бы назвать "случайным процессом с дискретным временем".
Пожалуйста, прочитайте эти документы:
Связи между вероятностными автоматами и скрытыми марковскими моделями (Пьер Дюпон) http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/HMM_PA_pres_n4.pdf
[Справочник по теории мозга и нейронным сетям] Скрытые марковские модели и другие конечные автоматы для обработки последовательностей http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3344&rep=rep1&type=pdf
Я считаю, что это должно ответить на ваш вопрос:
https://en.wikipedia.org/wiki/Probabilistic_automaton
И вы идете к правильной идее - они почти одинаковы: подмножества, надмножества и модификации в зависимости от того, какое прилагательное описывает цепь или автомат. Автоматы, как правило, также принимают данные, но я уверен, что были бумаги, использующие "цепочки Маркова" со входами.
Подумайте о распределении Гаусса по сравнению с нормальным распределением - одни и те же идеи в разных областях. Автоматы относятся к информатике, Марков относится к вероятности и статистике.
Я думаю, что большинство ответов неуместны. Марковский процесс генерируется (вероятностным) конечным автоматом, но не каждый процесс, генерируемый вероятностным конечным автоматом, является марковским процессом. Например, скрытые марковские процессы в основном такие же, как процессы, генерируемые вероятностными конечными автоматами, но не каждый скрытый марковский процесс является марковским.
Если оставить в стороне внутренние рабочие детали, конечный автомат похож на обычное значение, а цепочка Маркова - на случайную величину (добавьте вероятность поверх простого значения). Таким образом, ответ на оригинальный вопрос - нет, они не совпадают. В вероятностном смысле цепь Маркова является продолжением конечного автомата.