Дискретная диффузия: цепи Маркова с непрерывным временем

Этот материал, задуманный как первый в серии статей о дискретных диффузионных моделях, уже несколько месяцев лежал у меня в черновиках. Выход модели Gemini Diffusion от Google показался мне отличным поводом наконец его опубликовать.

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

Марковская цепь — это случайный процесс (бесконечное семейство случайных величин, индексированных временем ), определяемый двумя свойствами:

• Случайные величины принимают дискретные значения (их называют состояниями).

• Процесс не обладает памятью (характеризуется отсутствием последействия): то, что произойдёт с процессом в будущем, зависит только от состояния, в котором он находится в текущий момент. На языке математики это выражается как для всех , где обозначает условную независимость.

Цепи Маркова различают по тому, какие значения может принимать индекс . Если  — целое число, то перед нами — цепь Маркова с дискретным временем. А если  — вещественное число, то процесс называют цепью Маркова с непрерывным временем.

Дискретные цепи Маркова можно полностью описать семейством матриц переходных вероятностей . Обратите внимание на то, что матрица индексируется временем , так как она в общем случае может меняться с течением времени. Если же , то соответствующую марковскую цепь называют однородной.

Однородные цепи Маркова с непрерывным временем

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

Геометрическое распределение — это единственное дискретное распределение, обладающее свойством отсутствия последействия, которое выражается формулой . Это означает, что если мы находимся в моменте времени s и знаем, что событие ещё не произошло, распределение оставшегося времени ожидания остаётся одним и тем же, независимо от того, сколько времени мы ждали. Оказывается, геометрическое распределение — это единственное дискретное распределение с таким свойством.

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

А именно, когда марковская цепь начинает с состояния , она:

• Остаётся в одном и том же состоянии в течение времени, выбранного из геометрического распределения с параметром .

• Когда время ожидания истекает — выбирает новое состояние с вероятностью .

Другими словами, мы представили описание цепи Маркова в виде двух составляющих. Первая описывает то, когда произойдёт следующий переход. Вторая — то, как изменится состояние при переходе. Если при таком подходе нужно описать нечто, напоминающее цепь Маркова с непрерывным временем, сделать это можно, позволив времени ожидания принимать не только целочисленные, но и вещественные значения. Достичь этого можно, заменив геометрическое распределение на какое‑нибудь непрерывное распределение. Но для того чтобы сохранить марковское свойство, нам при выборе нового распределения важно сохранить свойство отсутствия последействия . Существует лишь одно такое непрерывное распределение — экспоненциальное. В результате однородную цепь Маркова с непрерывным временем можно описать следующим образом.

Начиная с состояния в момент времени цепь:

• Остаётся в том же состоянии в течение времени, выбранного из экспоненциального распределения с неким параметром .

• Когда время ожидания истекает, переходит в новое состояние с вероятностью .

Обратите внимание на то, что я здесь ввёл новый набор параметров — , которые заменяют переходные вероятности . Эти параметры больше не обязаны образовывать распределение вероятностей. Достаточно, чтобы все они были положительными вещественными числами. Матрицу, содержащую эти параметры, будем называть матрицей интенсивностей. Я обозначу её как , но отмечу, что в недавних публикациях по машинному обучению для её обозначения часто используют .

Неоднородные цепи Маркова и точечные процессы

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

Точечные процессы

Рассмотрим следующий сценарий, который покажет связь между дискретным равномерным распределением, распределением Бернулли, биномиальным и геометрическим распределениями. Пасхальный кролик прячет яйца в саду длиной 50 метров, который мы рассматриваем как одномерный отрезок. На каждом участке длиной 1 метр он прячет не более одного яйца. Кролик старается, чтобы в среднем вероятность того, что на участке будет спрятано яйцо, составляла 10%. Кроме того, он стремится к тому, чтобы яйца располагались случайным образом.

Кролик рассматривает несколько способов добиться этого.

Процесс № 1

Кролик перемещается от участка к участку. На каждом из них он с вероятностью 0,1 прячет яйцо, а потом переходит к следующему участку.

bernoulli = partial(numpy.random.binomial, n=1)
garden = ['_']*50

for i in range(50):
  if bernoulli(0.1)
    garden[i] = '