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

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

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

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

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

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

Дискретные цепи Маркова можно полностью описать семейством матриц переходных вероятностей P_t=[P(X_{t+1}=i|X_t=j)]i,j. Обратите внимание на то, что матрица P_t индексируется временем t, так как она в общем случае может меняться с течением времени. Если же P_t=P, то соответствующую марковскую цепь называют однородной.

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

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

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

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

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

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

  • Когда время ожидания истекает — выбирает новое состояние i≠j с вероятностью \frac{p_{i,j}} {\sum_{k≠i} p_{i,k}}.

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

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

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

  • Когда время ожидания истекает, переходит в новое состояние i≠j с вероятностью \frac{λ_{i,j}}{\sum_{k≠i}λ_{i,k}}.

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

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

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

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

Рассмотрим следующий сценарий, который покажет связь между дискретным равномерным распределением, распределением Бернулли, биномиальным и геометрическим распределениями. Пасхальный кролик прячет яйца в саду длиной 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] = '🥚'

print(''.join(garden))

>>> __________🥚__🥚______🥚_🥚__________________🥚________

Моделирование размещения яиц на основе распределения Бернулли

Процесс № 2

На каждом шаге кролик выбирает случайное неотрицательное целое число T из геометрического распределения с параметром 0,1. Затем он переходит на T участков вправо. Если после этого кролик остаётся в пределах сада, он прячет яйцо там, где оказался, и повторяет этот процесс до тех пор, пока не выйдет за пределы сада.

garden = ['_']*50
bunny_pos = -1

while bunny_pos<50: 
  bunny_pos += geometric(0.1)
  if bunny_pos<50:
    garden[bunny_pos] = '🥚'

print(''.join(garden))

>>> 🥚______🥚_________________🥚______________🥚🥚🥚___🥚_🥚🥚

Моделирование размещения яиц на основе геометрического распределения

Процесс № 3

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

garden = ['_']*50
number_of_eggs = binomial(p=0.1, n=50)
random_locations = permutation(np.arange(50))[:number_of_eggs]

for location in random_locations:
  garden[location] = '🥚'

print(''.join(garden))

>>> ________🥚_____🥚_______________🥚_🥚______🥚________🥚🥚

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

Каждый из рассмотренных вариантов поведения кролика — это моделирование точечного процесса с дискретным временем, в котором используется параметр p=0.1. Все три случая — это эквивалентные представления одного и того же точечного процесса:

  • Бинарная последовательность, каждый элемент которой, независимо от другого, сгенерирован на основе распределения Бернулли.

  • Бинарная последовательность, где длины промежутков между единицами следуют геометрическому распределению.

  • Бинарная последовательность, в которой количество единиц подчиняется биномиальному распределению, а выбор их позиций — равномерному распределению (без повторного выбора позиций).

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

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

Процесс № 1 по своей природе дискретен (он реализован в виде цикла по заранее заданному списку отрезков). А вот процессы № 2 и № 3 можно сделать непрерывными, заменив дискретные распределения вероятностей их непрерывными аналогами.

  • В процессе № 2 меняем геометрическое распределение на экспоненциальное. Оба обладают свойством отсутствия последействия.

  • В процессе № 3 меняем биномиальное распределение на его предельный случай — на распределение Пуассона, а дискретную равномерную выборку без возвращения на непрерывное равномерное распределение на всём отрезке. Тут мы можем отказаться от требования, чтобы выбранные позиции не повторялись, поскольку для непрерывных распределений это требование и так выполняется с вероятностью 1.

В обоих случаях полученный набор случайных точек представляет собой то, что называют «однородным пуассоновским точечным процессом». Вместо вероятности p у него теперь будет положительный параметр λ, определяющий ожидаемое количество точек, которые процесс разместит на заданном отрезке.

Точечные процессы и цепи Маркова

Вернёмся к цепям Маркова. Как они связаны с точечными процессами? Подсказкой может послужить то, что в рассмотренном выше процессе № 2 используются экспоненциальное и геометрическое распределения. Времена ожидания в цепях Маркова связаны с интервалами между последовательными точками в случайном точечном процессе. Посмотрим, как использовать точечные процессы для моделирования цепей Маркова. Начнём с дискретного случая, обозначив вероятность перехода из состояния i в состояние j как p_{i,j}.

Для каждого из N(N−1) возможных переходов i→j между N состояниями создадим независимый точечный процесс с параметром p_{i,j}. Теперь имеется список моментов времени, в которые происходят события для каждого перехода. Для цепи Маркова с тремя состояниями это будет выглядеть так:

Точечные процессы для событий перехода. По оси X показаны временные шаги, по оси Y — переходы
Точечные процессы для событий перехода. По оси X показаны временные шаги, по оси Y — переходы

Здесь для каждого перехода i→j мы наносим на диаграмму точки, символизирующие события перехода, сгенерированные точечным процессом с параметром, соответствующим вероятности этого перехода.

Каждому направлению перехода из состояния i в состояние j соответствует одна полоса. Для каждого перехода мы наносим на диаграмму точки, соответствующие событиям перехода, сгенерированным подходящим точечным процессом. Обратите внимание на то, что на некоторых полосах точки расположены плотнее, чем на других. Это связано с тем, что соответствующие вероятности переходов выше. Вот переходная матрица, которую я использовал:

Граф переходов между состояниями дискретной цепи Маркова
Граф переходов между состояниями дискретной цепи Маркова

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

Представим, что в момент t цепь Маркова находится в состоянии i. Мы рассматриваем точечные процессы для всех переходов из состояния i и ищем самое раннее событие после t в любой из последовательностей, генерируемых этими процессами. Предположим, что это событие происходит в момент s+t и что относится оно к точечному процессу, соответствующему переходу i→j. Цепь будет находиться в состоянии i до момента s+t, после чего перейдёт в состояние j и процесс повторится.

Вот как это выглядит на рисунке:

От точечных процессов к переходам между состояниями
От точечных процессов к переходам между состояниями

Работа цепи Маркова начинается с состояния 1. Поэтому нас интересуют переходы 1→0 и 1→2. Это показано зелёной областью в левой части диаграммы. Мы пребываем в состоянии 1 до тех пор, пока не произойдёт событие перехода (чёрная точка) для любого из этих двух переходов. Это происходит примерно через 5 временных шагов, что проиллюстрировано красным крестиком. В этот момент мы переходим в состояние 2, так как первое событие перехода происходит в полосе 1→2. Теперь нас интересуют события перехода для полос 2→1 и 2→0, то есть — две верхние полосы. Следующего события перехода долго ждать не приходится. Оно меняет состояние цепи на 0. Работа продолжается в том же духе. В результате сведения о состояниях цепи Маркова можно считывать, анализируя зелёные области, символизирующие текущее состояние системы.

Такая перепараметризация марковской цепи с непрерывным временем посредством лежащих в её основе пуассоновских точечных процессов открывает дорогу и к моделированию неоднородных цепей Маркова. Но материал и так получился довольно длинным, поэтому я не собираюсь рассказывать тут о том, как это сделать. Вот вам домашнее задание: поразмышляйте над процессами № 2 и № 3, использованными для моделирования однородного пуассоновского процесса. Что именно обеспечивает их однородность (то есть неизменность их свойств во времени)? Какие компоненты изменились бы, если бы матрица интенсивностей менялась с течением времени? Какое из представлений позволяет легче работать с непостоянными интенсивностями?

Итоги

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

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

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

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

  • Мы обсудили различные представления дискретных точечных процессов и отметили (хотя и не доказали) их эквивалентность.

  • Перейти к непрерывным версиям этих точечных процессов можно, заменяя дискретные распределения непрерывными и, опять же, сохраняя их ключевые свойства, такие как отсутствие памяти.

  • Мы, кроме того, поговорили о том, как можно описывать цепи Маркова с помощью точечных процессов. Суть в том, что с каждой парой состояний связан точечный процесс, а переходы происходят тогда, когда «срабатывает» точечный процесс, связанный с текущим состоянием.

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

О, а приходите к нам работать? 🤗 💰

Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.

Сейчас мы ищем плюсовиков, питонистов, дата‑инженеров и мл‑рисерчеров.

Присоединяйтесь к нашей команде