Скрытая марковская модель для трехсторонней игры в кости - PullRequest
Новая
       33

Скрытая марковская модель для трехсторонней игры в кости

6 голосов
/ 07 декабря 2011

Меня учили HMM и дали эту домашнюю задачу. Я понял часть этого, но я не уверен, правильно ли это. Проблема:

Рассмотрим другую игру, в которой дилер не подбрасывает монету, но вместо этого катится трехсторонний штамп с метками 1, 2 и 3. (Постарайтесь не думать о том, что такое трехсторонний кубик может выглядеть так.) У дилера есть две загруженные кости D1 и D2. Для каждого кубика Ди, вероятность прокатки числа i равна 1/2, а вероятность каждого из двух других Результаты 1/4. На каждом ходу дилер должен решить, следует ли (1) сохранить умереть, (2) переключиться на другой кубик или (3) закончить игру. Он выбирает (1) с вероятностью 1/2 и каждый из остальных с вероятностью 1/4. В начале дилер выбирает один из двух кубиков с равной вероятностью.

  • Дайте HMM для этой ситуации. Укажите алфавит, штаты, переход вероятности и вероятности эмиссии. Включить стартовое состояние start и предположить что HMM начинается в состоянии, начинается с вероятности 1. Также включите конец конец государства.

  • Предположим, что вы наблюдаете следующую последовательность бросков кубика: 1 1 2 1 2 2. Найдите последовательность состояний, которая лучше всего объясняет последовательность бросков. Какова вероятность этой последовательности? Найдите ответ, заполнив таблицу Витерби. Включают стрелки возврата в ячейках, чтобы вы могли проследить последовательность состояний. Некоторые из следующие факты могут быть полезны:

    log2 (0) = −∞
    log2 (1/4) = −2
    log2 (1/2) = −1
    log2 (1) = 0

  • На самом деле есть две оптимальные последовательности состояний для этой последовательности бросков кубика. Какова другая последовательность состояний?

Если я не ошибаюсь в первой части, я должен сделать что-то вроде этого http://en.wikipedia.org/wiki/Hidden_Markov_model#A_concrete_example Но я не понял, что предполагать, начать с вероятности 1.

Кроме того, я не уверен, что я должен сделать для таблицы Витерби во второй части вопроса. Если какое-либо тело может дать мне подсказку или подсказку, это будет здорово.

1 Ответ

2 голосов
/ 07 декабря 2011

Чтобы предположить, что ваша начальная вероятность равна единице: В HMM у вас либо фиксированное начальное состояние, либо распределение вероятностей по всем состояниям, которое указывает, насколько вероятно, что оно начнется в состоянии X. Предположим, чтоВаша начальная вероятность данного состояния равна 1, равному первому альтернативному.

Алгоритм Витерби: В матрице Витерби i-ая строка offten соответствует i-м состояниям, а j-й столбец соответствуетпрефикс длины j вашего испускаемого символа.В каждой записи (i, j) указана максимальная вероятность того, что вы уже видели префикс j, и вы находитесь в состоянии i.

Для отслеживания возврата необходимо отслеживать каждый (i, j) -ячейкукакой максимальный предшественник участвовал в вычислении (i, j) -клетки.Если у вас есть эта информация, вы можете вернуться из ячейки с самым высоким значением в последнем столбце к началу.Отмените это возвращение назад, и вы получите свой путь Витерби.

...