Цепь Маркова - это то же самое, что и конечный автомат?

80

Является ли конечный автомат просто реализацией цепи Маркова? В чем разница между ними?

math statistics state-machine fsm markov-chains Карсон
источник
24
Вы можете думать о цепи Маркова как о автомате, в котором переходы являются вероятностными,
доктор велизарий

Ответы:

61

Цепи Маркова могут быть представлены конечными автоматами. Идея состоит в том, что цепь Маркова описывает процесс, в котором переход в состояние в момент времени t + 1 зависит только от состояния в момент времени t. Главное, что нужно иметь в виду, - это то, что переходы в цепи Маркова скорее вероятностные, чем детерминированные, а это означает, что вы не всегда можете с полной уверенностью сказать, что произойдет в момент времени t + 1.

В статьях Википедии о машинах с конечным числом состояний есть подраздел о процессах с конечными цепями Маркова , я бы рекомендовал прочитать его для получения дополнительной информации. Кроме того, в статье Википедии о цепях Маркова есть краткое предложение, описывающее использование конечных автоматов для представления цепей Маркова. В нем говорится:

Конечный автомат может использоваться как представление цепи Маркова. Предполагая последовательность независимых и одинаково распределенных входных сигналов (например, символов из двоичного алфавита, выбранного подбрасыванием монеты), если автомат находится в состоянии y в момент времени n, то вероятность того, что он перейдет в состояние x в момент времени n + 1 зависит только от текущего состояния.

Джеймс Томпсон
источник
2
На самом деле то, что вы здесь говорите о цепи Маркова, не на 100% правильно. Вы упомянули здесь «Марковский процесс первого порядка». Для марковского процесса второго порядка следующее состояние будет зависеть от состояний последних двух временных шагов, ...... Конечный автомат - это частный случай цепи Маркова; поскольку цепь Маркова носит стохастический характер. Конечный автомат, насколько мне известно, детерминирован.
A. Isaac
5
Без оговорок термин цепь Маркова означает случайный процесс с дискретным временем и свойством Маркова, что означает, что он не зависит от прошлых состояний. В оригинальном плакате не спрашивалось о марковских процессах более высокого порядка, поэтому они на самом деле не так актуальны. Конечный автомат обычно является универсальным термином для конечного автомата, они могут быть детерминированными или недетерминированными по своей природе.
Тим Сегин
28

Хотя цепь Маркова является конечным автоматом, она отличается тем, что ее переходы являются стохастическими, т. Е. Случайными, и описываются вероятностями.

Оливер Чарльзуорт
источник
3
Спасибо за это, именно то, что я искал.
Стефан Май
4
Можно сказать, стохастические конечные автоматы?
Сурадип Нанда
19

Они похожи, но другие объяснения здесь немного неверны. Только КОНЕЧНЫЕ цепи Маркова могут быть представлены автоматом. Цепи Маркова допускают бесконечное пространство состояний. Как уже отмечалось, переходы цепи Маркова описываются вероятностями, но также важно отметить, что вероятности переходов могут зависеть только от текущего состояния. Без этого ограничения его можно было бы назвать «случайным процессом с дискретным временем».

Тим Сегин
источник
Собственно, я думаю, это можно было бы назвать «нестационарным».
Майкл Тамиллоу
@Michael: Возможно, я ошибаюсь, потому что какое-то время был вне темы, но я думал, что «стационарный» связан с временной зависимостью. Я могу ошибаться, но это кажется ортогональным.
Tim Seguine
«процесс» , как правило , используется для выражения непрерывного времени версии термина «цепочка» (ссылка: теория вероятности: краткий конечно, Розаны) и FSM может быть представлен бесконечно или управляемые события или недетерминированные . Единственная другая зависимость, которую я могу себе представить, помимо состояния, - это время.
Майкл Тамиллоу
@Michael "процесс" - это общий термин. Это может быть непрерывное время или дискретное время. Конечный автомат не может быть представлен бесконечно, в его названии есть слово конечный . В приведенной вами ссылке даже говорится, что это не конечный автомат. Вы затронули не меня временную зависимость, но в процессах с дискретным временем индекс последовательности обычно считается временем. В этом смысле да, случайный процесс с дискретным временем был бы нестационарным, но это недостаточно описательно, поскольку потенциально он также может быть непрерывным временем. Я собирался сделать суперсет, а не дополнение в моем именовании.
Tim Seguine 05
7

Пожалуйста, прочтите эти документы:

Связи между вероятностными автоматами и скрытыми марковскими моделями (Пьер Дюпон) 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

Хуан Карлос Кури Пинто
источник
3

Я считаю, что это должно ответить на ваш вопрос:

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

И вы правы - они почти одинаковы, подмножества, надмножества и модификации в зависимости от того, какое прилагательное описывает цепочку или автомат. Автоматы обычно тоже принимают входные данные, но я уверен, что были статьи, в которых использовались «цепи Маркова» с входными данными.

Подумайте о гауссовом распределении и нормальном распределении - одни и те же идеи в разных областях. Автоматы относятся к информатике, Марков - к вероятности и статистике.

Майкл Тамиллоу
источник
1

Если оставить в стороне внутренние рабочие детали, конечный автомат будет похож на простое значение, в то время как марковская цепь похожа на случайную величину (добавьте вероятность поверх простого значения). Итак, ответ на исходный вопрос - нет, они не совпадают. В вероятностном смысле цепь Маркова является расширением конечного автомата.

лян
источник
1

Я думаю, что большинство ответов неуместны. Марковский процесс генерируется (вероятностным) конечным автоматом, но не каждый процесс, генерируемый вероятностным конечным автоматом, является марковским процессом. Например, скрытые марковские процессы в основном такие же, как процессы, генерируемые вероятностными конечными автоматами, но не каждый скрытый марковский процесс является марковским.

Радоны
источник