Избегание детерминизма с помощью марковской логики

Question

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

Пример:

Привет, Мир.Привет, Долли.Привет, Мир.

"Мир" следует за "Привет" ~ 66% времени в этом источнике.

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

Как я мог бы получить вариации из статического источника, учитывая статистические значения, но при этом обеспечивая некоторую гибкость?Используя мой приведенный выше пример, как мне разрешить моему генератору следовать за "Hello" с помощью "Dolly", когда "Dolly" следует за "Hello" только в 33% случаев?

Я предполагаю, что я спрашиваю, как мне основывать вероятность моего следующего выбора на статистическом присутствии слов, которые следуют за моим текущим выбором?Таким образом, "Долли" появляется в 33% случаев, а "Мир" - в 66% случаев - или я здесь совсем запутался?

Answer 1

Вы используете генератор случайных чисел, чтобы выбрать, по какому пути вам идти.Вы должны сохранить каждое состояние (которое на самом деле представляет собой историю из N предыдущих элементов) и вероятности для этого состояния.Затем вы выбираете случайное число и на его основе решаете, в какое следующее состояние вы перейдете.

В вашем примере у вас есть цепочка Маркова с N, равным 1, у вас была бы цепная структура, которая выглядела бы примерно так:

<start> -> Hello : 1.0

Hello -> World. : 0.66666
Hello -> Dolly. : 0.33333

Dolly. -> Hello : 1.0

World. -> <end> : 0.5
World. -> Hello : 0.5

Если ваше текущее состояние - Hello, то ваши следующие возможные состояния - World.и Долли..Сгенерируйте случайное число от 0 до 1 и выберите World.если оно меньше 0,666666, в противном случае выберите Dolly.

С цепочкой Маркова N = 2 вы получаете почти детерминированное поведение с этими входными данными:

<start> <start> -> <start> Hello : 1.0

<start> Hello -> Hello World. : 1.0

Hello World. -> World. Hello : 0.5
Hello World. -> World. <end> : 0.5

World. Hello -> Hello Dolly. : 1.0

Hello Dolly. -> Dolly. Hello : 1.0

Dolly. Hello -> Hello World. : 1.0

Answer 2

Два комментария:

1) Для генерации выборок из случайного процесса, независимо от того, является ли определенный выбор достаточно вероятным (> 50%), а другие менее вероятными, просто требуется взвешенный "бросок монеты".:генерируйте случайное вещественное число равномерно на [0,1) и рассматривайте возможности в том же фиксированном порядке, сохраняя пока сумму вероятностей.Как только эта сумма превысит ваше случайно выбранное число, выберите этот вариант.Если ваш выбор имеет ненормализованные (не суммирующиеся до 1) вероятности, вам сначала нужно вычислить сумму вероятностей s и либо разделить их все на s, либо выбрать случайное число в [0, s)

2) Чтобы предотвратить переобучение при оценке вашей модели на основе небольшого объема выборочных обучающих данных (по сравнению с количеством параметров), используйте байесовские априорные значения для параметров модели.Действительно классный пример этого, где количество параметров модели (размер истории) заранее не фиксировано ни на какое конечное число, смотрите в Бесконечный ХМММ.Если вы не используете байесовские методы, то вам захочется выбрать длину истории соответствующим образом для имеющегося у вас объема обучающих данных и / или реализовать некоторое сглаживание ad-hoc (напримерлинейная интерполяция между моделями порядка 2 и порядка 1).