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

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

Пример:

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

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

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

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

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


variations deterministic markov-chains
person Sampson    schedule 04.09.2009    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Вы используете генератор случайных чисел, чтобы выбрать путь, по которому вы пойдете. Вы должны сохранить каждое состояние (которое на самом деле является историей 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

Если ваше текущее состояние — «Привет», то вашим следующим возможным состоянием будет «Мир». и Долли.. Создайте случайное число от 0 до 1 и выберите Мир. если меньше 0,666666, в противном случае выберите Долли.

С цепью Маркова 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
person Omnifarious    schedule 04.09.2009

arrow_upward
0
arrow_downward

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

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

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

person Jonathan Graehl    schedule 04.09.2009