Цепи Маркова

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

Модели Маркова дают визуальное представление с диаграммой состояний, такой как та ниже.

Диаграмма состояний для модели Маркова

Прямоугольники в схеме представляют возможные состояния процесса, который вы пытаетесь смоделировать, и стрелки представляют переходы между состояниями. Метка на каждой стрелке представляет вероятность того перехода. На каждом шаге процесса модель может сгенерировать вывод или emission, в зависимости от которого состояния это находится в, и затем делает переход к другому состоянию. Важная характеристика моделей Маркова - то, что следующее состояние зависит только от текущего состояния, а не от истории переходов, которые приводят к текущему состоянию.

Например, для последовательности бросков монеты два состояния являются головами и хвостами. Новый бросок монеты определяет текущее состояние модели, и каждый последующий бросок определяет переход к следующему состоянию. Если монета справедлива, вероятности перехода являются всем 1/2. Эмиссия может просто быть текущим состоянием. В более сложных моделях вероятностные процессы в каждом состоянии сгенерируют эмиссию. Вы могли, например, прокрутить умирание, чтобы определить эмиссию на любом шаге.

Markov chains является математическими описаниями моделей Маркова с дискретным набором состояний. Цепи Маркова характеризуются:

  • Набор состояний {1, 2..., M}

  • M-by-M transition matrix T, чей i, запись j является вероятностью перехода от i состояния, чтобы утвердить j. Сумма записей в каждой строке T должна быть 1, потому что это - сумма вероятностей создания перехода от данного состояния до каждого из других состояний.

  • Набор возможных выходных параметров или эмиссии, {s1, s2..., sN}. По умолчанию набор эмиссии {1, 2..., N}, где N является количеством возможной эмиссии, но можно выбрать различный набор чисел или символов.

  • M на n emission matrix E, чей i, запись k дает вероятность испускания символа sk, учитывая, что модель находится в i состояния.

Цепи Маркова начинаются в i initial state 0 на шаге 0. Цепочка затем переходы, чтобы утвердить i1 с вероятностью T1i1, и испускает вывод sk1 с вероятностью Ei1k1. Следовательно, вероятность наблюдения последовательности состояний i1i2...ir и последовательность эмиссии sk1sk2...skr на первых шагах r,

T1i1Ei1k1Ti1i2Ei2k2...Tir1irEirk

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте