Что такое марковская цепь
Цепи Маркова и Пайтон — разбираемся в теории и собираем генератор текстов
Понимаем и создаём
Хорошие новости перед статьей: высоких математических скиллов для прочтения и (надеюсь!) понимания не требуется.
Дисклеймер: кодовая часть данной статьи, как и предыдущей, является адаптированным, дополненным и протестированным переводом. Я благодарна автору, потому что это один из первых моих опытов в коде, после которого меня поперло ещё больше. Надеюсь, что на вас моя адаптация подействует так же!
Итак, поехали!
Структура такая:
Что такое цепь Маркова?
Цепь Маркова — инструмент из теории случайных процессов, состоящий из последовательности n количества состояний. Связи между узлами (значениями) цепочки при этом создаются, только если состояния стоят строго рядом друг с другом.
Держа в голове жирношрифтовое слово только, выведем свойство цепи Маркова:
Вероятность наступления некоторого нового состояния в цепочке зависит только от настоящего состояния и математически не учитывает опыт прошлых состояний => Марковская цепь — это цепь без памяти.
Иначе говоря, новое значение всегда пляшет от того, которое его непосредственно держит за ручку.
Пример работы цепочки
Как и автор статьи, из которой позаимствована кодовая реализация, возьмем рандомную последовательность слов.
Старт — искусственная — шуба — искусственная — еда — искусственная — паста — искусственная — шуба — искусственная — конец
Представим, что на самом деле это великолепный стих и нашей задачей является скопировать стиль автора. (Но делать так, конечно, неэтично)
Как решать?
Первое явное, что хочется сделать — посчитать частотность слов (если бы мы делали это с живым текстом, для начала стоило бы провести нормализацию — привести каждое слово к лемме (словарной форме)).
Старт == 1
Искусственная == 5
Шуба == 2
Паста == 1
Еда == 1
Конец == 1
Держа в голове, что у нас цепочка Маркова, мы можем построить распределение новых слов в зависимости от предыдущих графически:
Что на русском означает «сумма ряда вероятностей для некоторого события k, зависимого от i == сумме всех значений вероятностей события k в зависимости от наступления состояния i, где событие k == m+1, а событие i == m (то есть событие k всегда на единицу отличается от i)».
Но для начала поймем, что такое матрица.
Матрица переходов
При работе с цепями Маркова мы имеем дело со стохастический матрицей переходов — совокупностью векторов, внутри которых значения отражают значения вероятностей между градациями.
Да, да, звучит так, как звучит.
Но выглядит не так страшно:
P — это обозначение матрицы. Значения на пересечении столбцов и строк здесь отражают вероятности переходов между состояниями.
Для нашего примера это будет выглядеть как-то так:
Заметьте, что сумма значений в строке == 1. Это говорит о том, что мы правильно всё построили, ведь сумма значений в строке стохастический матрицы должна равняться единице.
Голый пример без искусственных шуб и паст:
Респекто. С теорией закончили.
Используем Пайтон.
Модель, основанная на Марковской цепи при помощи Пайтона — генерация текста на основе данных
Импортируем релевантный пакет для работы и достаём данные.
Не заостряйте внимание на структуре текста, но обратите внимание на кодировку utf8. Это важно для прочтения данных.
Разделим данные на слова.
Создадим функцию для связки пар слов.
Главный нюанс функции в применении оператора yield(). Он помогает нам удовлетворить критерию цепочки Маркова — критерию хранения без памяти. Благодаря yield, наша функция будет создавать новые пары в процессе итераций(повторений), а не хранить все.
Тут может возникнуть непонимание, ведь одно слово может переходить в разные. Это мы решим, создав словарь для нашей функции.
Рандомно выберем первое слово и, чтобы слово было действительно случайным, зададим условие while при помощи строкового метода islower(), который удовлетворяет True в случае, когда в строке значения из букв нижнего регистра, допуская наличие цифр или символов.
При этом зададим количество слов 20.
Запустим нашу рандомную штуку!
Функция join() — функция для работы со строками. В скобках мы указали разделитель для значений в строке(пробел).
А текст… ну, звучит по-машинному и почти логично.
P.S. Как вы могли заметить, цепи Маркова удобны в лингвистике, но их применение выходит за рамки обработки естественного языка. Здесь и здесь вы можете ознакомиться с применением цепей в других задачах.
P.P.S. Если моя практика кода вышла непонятной для вас, прилагаю исходную статью. Обязательно примените код на практике — чувство, когда оно «побежало и сгенерировало» заряжает!
Жду ваших мнений и буду рада конструктивным замечаниям по статье!
Цепь Маркова – это просто: подробно разбираем принцип
Цепь Маркова – череда событий, в которой каждое последующее событие зависит от предыдущего. В статье мы подробнее разберём это понятие.
Цепь Маркова – это распространенный и довольно простой способ моделирования случайных событий. Используется в самых разных областях, начиная генерацией текста и заканчивая финансовым моделированием. Самым известным примером является SubredditSimulator. В данном случае Цепь Маркова используется для автоматизации создания контента во всем subreddit.
Цепь Маркова понятна и проста в использовании, т. к. она может быть реализована без использования каких-либо статистических или математических концепций. Цепь Маркова идеально подходит для изучения вероятностного моделирования и Data Science.
Сценарий
Представьте, что существует только два погодных условия: может быть либо солнечно, либо пасмурно. Всегда можно безошибочно определить погоду в текущий момент. Гарантированно будет ясно или облачно.
Теперь вам захотелось научиться предсказывать погоду на завтрашний день. Интуитивно вы понимаете, что погода не может кардинально поменяться за один день. На это влияет множество факторов. Завтрашняя погода напрямую зависит от текущей и т. д. Таким образом, для того чтобы предсказывать погоду, вы на протяжении нескольких лет собираете данные и приходите к выводу, что после пасмурного дня вероятность солнечного равна 0,25. Логично предположить, что вероятность двух пасмурных дней подряд равна 0,75, так как мы имеем всего два возможных погодных условия.
Теперь вы можете прогнозировать погоду на несколько дней вперед, основываясь на текущей погоде.
Этот пример показывает ключевые понятия цепи Маркова. Цепь Маркова состоит из набора переходов, которые определяются распределением вероятностей, которые в свою очередь удовлетворяют Марковскому свойству.
Обратите внимание, что в примере распределение вероятностей зависит только от переходов с текущего дня на следующий. Это уникальное свойство Марковского процесса – он делает это без использования памяти. Как правило, такой подход не способен создать последовательность, в которой бы наблюдалась какая-либо тенденция. Например, в то время как цепь Маркова способна сымитировать стиль письма, основанный на частоте использования какого-то слова, она не способна создать тексты с глубоким смыслом, так как она может работать только с большими текстами. Именно поэтому цепь Маркова не может производить контент, зависящий от контекста.
Модель
Формально, цепь Маркова – это вероятностный автомат. Распределение вероятностей переходов обычно представляется в виде матрицы. Если цепь Маркова имеет N возможных состояний, то матрица будет иметь вид N x N, в которой запись (I, J) будет являться вероятностью перехода из состояния I в состояние J. Кроме того, такая матрица должна быть стохастической, то есть строки или столбцы в сумме должны давать единицу. В такой матрице каждая строка будет иметь собственное распределение вероятностей.
Общий вид цепи Маркова с состояниями в виде окружностей и ребрами в виде переходов.
Примерная матрица перехода с тремя возможными состояниями.
Цепь Маркова имеет начальный вектор состояния, представленный в виде матрицы N x 1. Он описывает распределения вероятностей начала в каждом из N возможных состояний. Запись I описывает вероятность начала цепи в состоянии I.
Этих двух структур вполне хватит для представления цепи Маркова.
Мы уже обсудили, как получить вероятность перехода из одного состояния в другое, но что насчет получения этой вероятности за несколько шагов? Для этого нам необходимо определить вероятность перехода из состояния I в состояние J за M шагов. На самом деле это очень просто. Матрицу перехода P можно определить вычислением (I, J) с помощью возведения P в степень M. Для малых значений M это можно делать вручную, с помощью повторного умножения. Но для больших значений M, если вы знакомы с линейной алгеброй, более эффективным способом возведения матрицы в степень будет сначала диагонализировать эту матрицу.
Цепь Маркова: заключение
Теперь, зная, что из себя представляет цепь Маркова, вы можете легко реализовать её на одном из языков программирования. Простые цепи Маркова являются фундаментом для изучения более сложных методов моделирования.
Что такое цепи Маркова и как они работают
Простой способ сгенерировать много текста, который будет похож на настоящий.
В «Коде» уже вышло несколько проектов, где мы генерировали какой-то случайный текст, чтобы показать его пользователю:
Проблема с этими генераторами была в том, что нам вручную приходилось прописывать все варианты, последовательности и комбинации из слов и предложений. Чтобы добавить новый вариант в этих проектах, нужно зайти в код и вручную прописать новый текстовый блок в одной из переменных.
Главный минус такого подхода — вы делаете всю работу за компьютер. Вы сами жёстко задаёте структуру каждого предложения. Такой текст вас ничем не удивит, потому что вы чётко знаете, сколько предложений у вас в шаблоне и из каких частей состоит каждое.
Чтобы генерировать много похожего текста, но без таких заморочек, используют нейросети или алгоритмы на цепях Маркова. Нейросети пока оставим, а сегодня займёмся цепями.
Что такое цепь Маркова
Представьте, что у нас есть набор каких-то событий, связанных друг с другом. Например, первое наступает только после второго, второе — после третьего или четвёртого, а третье — после четвёртого с вероятностью 30% и так далее. Получается, что каждое новое событие зависит только от предыдущего и не зависит от всех остальных до него.
Допустим, у нас есть событие «Взять зонт», которое всегда идёт только после события «Идёт дождь». Даже если сейчас середина декабря, кругом снег, но внезапно случилась оттепель и пошёл дождь — следом за ним по этой логике будет событие «Взять зонт».
👉 Цепи Маркова — это последовательность событий или действий, где каждое новое событие зависит только от предыдущего и не учитывает все остальные события. Такой алгоритм не помнит, что было раньше, а смотрит только на предыдущее состояние.
Чтобы было понятнее, разберём на тексте.
Текст и цепи Маркова
Возьмём такую скороговорку:
Ехал грека через реку, видит грека — в реке рак, сунул грека руку в реку, рак за руку греку цап.
В теории цепей Маркова это называется корпус — исходный материал, по которому будут составляться взаимосвязи. В нашем случае по этому предложению мы поймём, как одни слова будут связаны с другими.
❗️ Для простоты мы опустим знаки препинания и большие буквы. В нормальных алгоритмах это, конечно, учитывается, но пока мы учимся, можно и так.
Наша задача — понять на этом примере, как устроены и как работают цепи Маркова. Для этого мы шаг за шагом смоделируем работу алгоритма и посмотрим, что получится в итоге.
Считаем слова
Посчитаем, сколько раз встречается каждое слово в нашем тексте:
Краткое введение в цепи Маркова
В 1998 году Лоуренс Пейдж, Сергей Брин, Раджив Мотвани и Терри Виноград опубликовали статью «The PageRank Citation Ranking: Bringing Order to the Web», в которой описали знаменитый теперь алгоритм PageRank, ставший фундаментом Google. Спустя чуть менее двух десятков лет Google стал гигантом, и даже несмотря на то, что его алгоритм сильно эволюционировал, PageRank по-прежнему является «символом» алгоритмов ранжирования Google (хотя только немногие люди могут действительно сказать, какой вес он сегодня занимает в алгоритме).
С теоретической точки зрения интересно заметить, что одна из стандартных интерпретаций алгоритма PageRank основывается на простом, но фундаментальном понятии цепей Маркова. Из статьи мы увидим, что цепи Маркова — это мощные инструменты стохастического моделирования, которые могут быть полезны любому эксперту по аналитическим данным (data scientist). В частности, мы ответим на такие базовые вопросы: что такое цепи Маркова, какими хорошими свойствами они обладают, и что с их помощью можно делать?
Краткий обзор
В первом разделе мы приведём базовые определения, необходимые для понимания цепей Маркова. Во втором разделе мы рассмотрим особый случай цепей Маркова в конечном пространстве состояний. В третьем разделе мы рассмотрим некоторые из элементарных свойств цепей Маркова и проиллюстрируем эти свойства на множестве мелких примеров. Наконец, в четвёртом разделе мы свяжем цепи Маркова с алгоритмом PageRank и увидим на искусственном примере, как цепи Маркова можно применять для ранжирования узлов графа.
Примечание. Для понимания этого поста необходимы знания основ вероятностей и линейной алгебры. В частности, будут использованы следующие понятия: условная вероятность, собственный вектор и формула полной вероятности.
Что такое цепи Маркова?
Случайные переменные и случайные процессы
Прежде чем вводить понятие цепей Маркова, давайте вкратце вспомним базовые, но важные понятия теории вероятностей.
Во-первых, вне языка математики случайной величиной X считается величина, которая определяется результатом случайного явления. Его результатом может быть число (или «подобие числа», например, векторы) или что-то иное. Например, мы можем определить случайную величину как результат броска кубика (число) или же как результат бросания монетки (не число, если только мы не обозначим, например, «орёл» как 0, а «решку» как 1). Также упомянем, что пространство возможных результатов случайной величины может быть дискретным или непрерывным: например, нормальная случайная величина непрерывна, а пуассоновская случайная величина дискретна.
Далее мы можем определить случайный процесс (также называемый стохастическим) как набор случайных величин, проиндексированных множеством T, которое часто обозначает разные моменты времени (в дальнейшем мы будем считать так). Два самых распространённых случая: T может быть или множеством натуральных чисел (случайный процесс с дискретным временем), или множеством вещественных чисел (случайный процесс с непрерывным временем). Например, если мы будем бросать монетку каждый день, то зададим случайный процесс с дискретным временем, а постоянно меняющаяся стоимость опциона на бирже задаёт случайный процесс с непрерывным временем. Случайные величины в разные моменты времени могут быть независимыми друг от друга (пример с подбрасыванием монетки), или иметь некую зависимость (пример со стоимостью опциона); кроме того, они могут иметь непрерывное или дискретное пространство состояний (пространство возможных результатов в каждый момент времени).
Разные виды случайных процессов (дискретные/непрерывные в пространстве/времени).
Марковское свойство и цепь Маркова
Существуют хорошо известные семейства случайных процессов: гауссовы процессы, пуассоновские процессы, авторегрессивные модели, модели скользящего среднего, цепи Маркова и другие. Каждое из этих отдельных случаев имеет определённые свойства, позволяющие нам лучше исследовать и понимать их.
Одно из свойств, сильно упрощающее исследование случайного процесса — это «марковское свойство». Если объяснять очень неформальным языком, то марковское свойство сообщает нам, что если мы знаем значение, полученное каким-то случайным процессом в заданный момент времени, то не получим никакой дополнительной информации о будущем поведении процесса, собирая другие сведения о его прошлом. Более математическим языком: в любой момент времени условное распределение будущих состояний процесса с заданными текущим и прошлыми состояниями зависит только от текущего состояния, но не от прошлых состояний (свойство отсутствия памяти). Случайный процесс с марковским свойством называется марковским процессом.
Марковское свойство обозначает, что если мы знаем текущее состояние в заданный момент времени, то нам не нужна никакая дополнительная информация о будущем, собираемая из прошлого.
На основании этого определения мы можем сформулировать определение «однородных цепей Маркова с дискретным временем» (в дальнейшем для простоты мы их будем называть «цепями Маркова»). Цепь Маркова — это марковский процесс с дискретным временем и дискретным пространством состояний. Итак, цепь Маркова — это дискретная последовательность состояний, каждое из которых берётся из дискретного пространства состояний (конечного или бесконечного), удовлетворяющее марковскому свойству.
Математически мы можем обозначить цепь Маркова так:
где в каждый момент времени процесс берёт свои значения из дискретного множества E, такого, что
Тогда марковское свойство подразумевает, что у нас есть
Снова обратите внимание, что эта последняя формула отражает тот факт, что для хронологии (где я нахожусь сейчас и где я был раньше) распределение вероятностей следующего состояния (где я буду дальше) зависит от текущего состояния, но не от прошлых состояний.
Примечание. В этом ознакомительном посте мы решили рассказать только о простых однородных цепях Маркова с дискретным временем. Однако существуют также неоднородные (зависящие от времени) цепи Маркова и/или цепи с непрерывным временем. В этой статье мы не будем рассматривать такие вариации модели. Стоит также заметить, что данное выше определение марковского свойства чрезвычайно упрощено: в истинном математическом определении используется понятие фильтрации, которое выходит далеко за пределы нашего вводного знакомства с моделью.
Характеризуем динамику случайности цепи Маркова
В предыдущем подразделе мы познакомились с общей структурой, соответствующей любой цепи Маркова. Давайте посмотрим, что нам нужно, чтобы задать конкретный «экземпляр» такого случайного процесса.
Сначала заметим, что полное определение характеристик случайного процесса с дискретным временем, не удовлетворяющего марковскому свойству, может быть сложным занятием: распределение вероятностей в заданный момент времени может зависеть от одного или нескольких моментов в прошлом и/или будущем. Все эти возможные временные зависимости потенциально могут усложнить создание определения процесса.
Однако благодаря марковскому свойству динамику цепи Маркова определить довольно просто. И в самом деле. нам нужно определить только два аспекта: исходное распределение вероятностей (то есть распределение вероятностей в момент времени n=0), обозначаемое
и матрицу переходных вероятностей (которая даёт нам вероятности того, что состояние в момент времени n+1 является последующим для другого состояния в момент n для любой пары состояний), обозначаемую
Если два этих аспекта известны, то полная (вероятностная) динамика процесса чётко определена. И в самом деле, вероятность любого результата процесса тогда можно вычислить циклически.
Пример: допустим, мы хотим знать вероятность того, что первые 3 состояния процесса будут иметь значения (s0, s1, s2). То есть мы хотим вычислить вероятность
Здесь мы применяем формулу полной вероятности, гласящую, что вероятность получения (s0, s1, s2) равна вероятности получения первого s0, умноженного на вероятность получения s1 с учётом того, что ранее мы получили s0, умноженного на вероятность получения s2 с учётом того, что мы получили ранее по порядку s0 и s1. Математически это можно записать как
И затем проявляется упрощение, определяемое марковским допущением. И в самом деле, в случае длинных цепей мы получим для последних состояний сильно условные вероятности. Однако в случае цепей Маркова мы можем упростить это выражение, воспользовавшись тем, что
получив таким образом
Так как они полностью характеризуют вероятностную динамику процесса, многие сложные события можно вычислить только на основании исходного распределения вероятностей q0 и матрицы переходной вероятности p. Стоит также привести ещё одну базовую связь: выражение распределения вероятностей во время n+1, выраженное относительно распределения вероятностей во время n
Цепи Маркова в конечных пространствах состояний
Представление в виде матриц и графов
Здесь мы допустим, что во множестве E есть конечное количество возможных состояний N:
Тогда исходное распределение вероятностей можно описать как вектор-строку q0 размером N, а переходные вероятности можно описать как матрицу p размером N на N, такую что
Преимущество такой записи заключается в том, что если мы обозначим распределение вероятностей на шаге n вектором-строкой qn, таким что его компоненты задаются
тогда простые матричные связи при этом сохраняются
(здесь мы не будем рассматривать доказательство, но воспроизвести его очень просто).
Если умножить справа вектор-строку, описывающий распределение вероятностей на заданном этапе времени, на матрицу переходных вероятностей, то мы получим распределение вероятностей на следующем этапе времени.
Итак, как мы видим, переход распределения вероятностей из заданного этапа в последующий определяется просто как умножение справа вектора-строки вероятностей исходного шага на матрицу p. Кроме того, это подразумевает, что у нас есть
Динамику случайности цепи Маркова в конечном пространстве состояний можно с лёгкостью представить как нормированный ориентированный граф, такой что каждый узел графа является состоянием, а для каждой пары состояний (ei, ej) существует ребро, идущее от ei к ej, если p(ei,ej)>0. Тогда значение ребра будет той же вероятностью p(ei,ej).
Пример: читатель нашего сайта
Давайте проиллюстрируем всё это простым примером. Рассмотрим повседневное поведение вымышленного посетителя сайта. В каждый день у него есть 3 возможных состояния: читатель не посещает сайт в этот день (N), читатель посещает сайт, но не читает пост целиком (V) и читатель посещает сайт и читает один пост целиком (R ). Итак, у нас есть следующее пространство состояний:
Допустим, в первый день этот читатель имеет вероятность 50% только зайти на сайт и вероятность 50% посетить сайт и прочитать хотя бы одну статью. Вектор, описывающий исходное распределение вероятностей (n=0) тогда выглядит так:
Также представим, что наблюдаются следующие вероятности:
Из предыдущего подраздела мы знаем как вычислить для этого читателя вероятность каждого состояния на следующий день (n=1)
Вероятностную динамику этой цепи Маркова можно графически представить так:
Представление в виде графа цепи Маркова, моделирующей поведение нашего придуманного посетителя сайта.
Свойства цепей Маркова
В этом разделе мы расскажем только о некоторых самых базовых свойствах или характеристиках цепей Маркова. Мы не будем вдаваться в математические подробности, а представим краткий обзор интересных моментов, которые необходимо изучить для использования цепей Маркова. Как мы видели, в случае конечного пространства состояний цепь Маркова можно представить в виде графа. В дальнейшем мы будем использовать графическое представление для объяснения некоторых свойств. Однако не стоит забывать, что эти свойства необязательно ограничены случаем конечного пространства состояний.
Разложимость, периодичность, невозвратность и возвратность
В этом подразделе давайте начнём с нескольких классических способов характеризации состояния или целой цепи Маркова.
Во-первых, мы упомянем, что цепь Маркова неразложима, если можно достичь любого состояния из любого другого состояния (необязательно, что за один шаг времени). Если пространство состояний конечно и цепь можно представить в виде графа, то мы можем сказать, что граф неразложимой цепи Маркова сильно связный (теория графов).
Иллюстрация свойства неразложимости (несокращаемости). Цепь слева нельзя сократить: из 3 или 4 мы не можем попасть в 1 или 2. Цепь справа (добавлено одно ребро) можно сократить: каждого состояния можно достичь из любого другого.
Состояние имеет период k, если при уходе из него для любого возврата в это состояние нужно количество этапов времени, кратное k (k — наибольший общий делитель всех возможных длин путей возврата). Если k = 1, то говорят, что состояние является апериодическим, а вся цепь Маркова является апериодической, если апериодичны все её состояния. В случае неприводимой цепи Маркова можно также упомянуть, что если одно состояние апериодическое, то и все другие тоже являются апериодическими.
Иллюстрация свойства периодичности. Цепь слева периодична с k=2: при уходе из любого состояния для возврата в него всегда требуется количество шагов, кратное 2. Цепь справа имеет период 3.
Состояние является невозвратным, если при уходе из состояния существует ненулевая вероятность того, что мы никогда в него не вернёмся. И наоборот, состояние считается возвратным, если мы знаем, что после ухода из состояния можем в будущем вернуться в него с вероятностью 1 (если оно не является невозвратным).
Иллюстрация свойства возвратности/невозвратности. Цепь слева имеет такие свойства: 1, 2 и 3 невозвратны (при уходе из этих точек мы не можем быть абсолютно уверены, что вернёмся в них) и имеют период 3, а 4 и 5 возвратны (при уходе из этих точек мы абсолютно уверены, что когда-нибудь к ним вернёмся) и имеют период 2. Цепь справа имеет ещё одно ребро, делающее всю цепь возвратной и апериодической.
Для возвратного состояния мы можем вычислить среднее время возвратности, которое является ожидаемым временем возврата при покидании состояния. Заметьте, что даже вероятность возврата равна 1, то это не значит, что ожидаемое время возврата конечно. Поэтому среди всех возвратных состояний мы можем различать положительные возвратные состояния (с конечным ожидаемым временем возврата) и нулевые возвратные состояния (с бесконечным ожидаемым временем возврата).
Стационарное распределение, предельное поведение и эргодичность
В этом подразделе мы рассмотрим свойства, характеризующие некоторые аспекты (случайной) динамики, описываемой цепью Маркова.
Распределение вероятностей π по пространству состояний E называют стационарным распределением, если оно удовлетворяет выражению
Так как у нас есть
Тогда стационарное распределение удовлетворяет выражению
По определению, стационарное распределение вероятностей со временем не изменяется. То есть если исходное распределение q является стационарным, тогда оно будет одинаковых на всех последующих этапах времени. Если пространство состояний конечно, то p можно представить в виде матрицы, а π — в виде вектора-строки, и тогда мы получим
Это снова выражает тот факт, что стационарное распределение вероятностей со временем не меняется (как мы видим, умножение справа распределения вероятностей на p позволяет вычислить распределение вероятностей на следующем этапе времени). Учтите, что неразложимая цепь Маркова имеет стационарное распределение вероятностей тогда и только тогда, когда одно из её состояний является положительным возвратным.
Ещё одно интересное свойство, связанное с стационарным распределением вероятностей, заключается в следующем. Если цепь является положительной возвратной (то есть в ней существует стационарное распределение) и апериодической, тогда, какими бы ни были исходные вероятности, распределение вероятностей цепи сходится при стремлении интервалов времени к бесконечности: говорят, что цепь имеет предельное распределение, что является ничем иным, как стационарным распределением. В общем случае его можно записать так:
Ещё раз подчеркнём тот факт, что мы не делаем никаких допущений об исходном распределении вероятностей: распределение вероятностей цепи сводится к стационарному распределению (равновесному распределению цепи) вне зависимости от исходных параметров.
Наконец, эргодичность — это ещё одно интересное свойство, связанное с поведением цепи Маркова. Если цепь Маркова неразложима, то также говорится, что она «эргодическая», потому что удовлетворяет следующей эргодической теореме. Допустим, у нас есть функция f(.), идущая от пространства состояний E к оси (это может быть, например, цена нахождения в каждом состоянии). Мы можем определить среднее значение, перемещающее эту функцию вдоль заданной траектории (временное среднее). Для n-ных первых членов это обозначается как
Также мы можем вычислить среднее значение функции f на множестве E, взвешенное по стационарному распределению (пространственное среднее), которое обозначается
Тогда эргодическая теорема говорит нам, что когда траектория становится бесконечно длинной, временное среднее равно пространственному среднему (взвешенному по стационарному распределению). Свойство эргодичности можно записать так:
Иными словами, оно обозначает, что в пределе ранее поведение траектории становится несущественным и при вычислении временного среднего важно только долговременное стационарное поведение.
Вернёмся к примеру с читателем сайта
Снова рассмотрим пример с читателем сайта. В этом простом примере очевидно, что цепь неразложима, апериодична и все её состояния положительно возвратны.
Чтобы показать, какие интересные результаты можно вычислить с помощью цепей Маркова, мы рассмотрим среднее время возвратности в состояние R (состояние «посещает сайт и читает статью»). Другими словами, мы хотим ответить на следующий вопрос: если наш читатель в один день заходит на сайт и читает статью, то сколько дней нам придётся ждать в среднем того, что он снова зайдёт и прочитает статью? Давайте попробуем получить интуитивное понятие о том, как вычисляется это значение.
Сначала мы обозначим
Итак, мы хотим вычислить m(R,R). Рассуждая о первом интервале, достигнутом после выхода из R, мы получим
Однако это выражение требует, чтобы для вычисления m(R,R) мы знали m(N,R) и m(V,R). Эти две величины можно выразить аналогичным образом:
Итак, у нас получилось 3 уравнения с 3 неизвестными и после их решения мы получим m(N,R) = 2.67, m(V,R) = 2.00 и m(R,R) = 2.54. Значение среднего времени возвращения в состояние R тогда равно 2.54. То есть с помощью линейной алгебры нам удалось вычислить среднее время возвращения в состояние R (а также среднее время перехода из N в R и среднее время перехода из V в R).
Чтобы закончить с этим примером, давайте посмотрим, каким будет стационарное распределение цепи Маркова. Чтобы определить стационарное распределение, нам нужно решить следующее уравнение линейной алгебры:
То есть нам нужно найти левый собственный вектор p, связанный с собственным вектором 1. Решая эту задачу, мы получаем следующее стационарное распределение:
Стационарное распределение в примере с читателем сайта.
Можно также заметить, что π( R ) = 1/m(R,R), и если немного поразмыслить, то это тождество довольно логично (но подробно об этом мы говорить не будем).
Поскольку цепь неразложима и апериодична, это означает, что в длительной перспективе распределение вероятностей сойдётся к стационарному распределению (для любых исходных параметров). Иными словами, каким бы ни было исходное состояние читателя сайта, если мы подождём достаточно долго и случайным образом выберем день, то получим вероятность π(N) того, что читатель не зайдёт на сайт в этот день, вероятность π(V) того, что читатель зайдёт, но не прочитает статью, и вероятность π® того, что читатель зайдёт и прочитает статью. Чтобы лучше уяснить свойство сходимости, давайте взглянем на следующий график, показывающий эволюцию распределений вероятностей, начинающихся с разных исходных точек и (быстро) сходящихся к стационарному распределению:
Визуализация сходимости 3 распределений вероятностей с разными исходными параметрами (синяя, оранжевая и зелёная) к стационарному распределению (красная).
Классический пример: алгоритм PageRank
Настало время вернуться к PageRank! Но прежде чем двигаться дальше, стоит упомянуть, что интерпретация PageRank, данная в этой статье, не единственно возможная, и авторы оригинальной статьи при разработке методики не обязательно рассчитывали на применение цепей Маркова. Однако наша интерпретация хороша тем, что очень понятна.
Произвольный веб-пользователь
PageRank пытается решить следующую задачу: как нам ранжировать имеющееся множество (мы можем допустить, что это множество уже отфильтровано, например, по какому-то запросу) с помощью уже существующих между страницами ссылок?
Чтобы решить эту задачу и иметь возможность отранжировать страницы, PageRank приблизительно выполняет следующий процесс. Мы считаем, что произвольный пользователь Интернета в исходный момент времени находится на одной из страниц. Затем этот пользователь начинает случайным образом начинает перемещаться, щёлкая на каждой странице по одной из ссылок, которые ведут на другую страницу рассматриваемого множества (предполагается, что все ссылки, ведущие вне этих страниц, запрещены). На любой странице все допустимые ссылки имеют одинаковую вероятность нажатия.
Так мы задаём цепь Маркова: страницы — это возможные состояния, переходные вероятности задаются ссылками со страницы на страницу (взвешенными таким образом, что на каждой странице все связанные страницы имеют одинаковую вероятность выбора), а свойства отсутствия памяти чётко определяются поведением пользователя. Если также предположить, что заданная цепь положительно возвратная и апериодичная (для удовлетворения этим требованиям применяются небольшие хитрости), тогда в длительной перспективе распределение вероятностей «текущей страницы» сходится к стационарному распределению. То есть какой бы ни была начальная страница, спустя длительное время каждая страница имеет вероятность (почти фиксированную) стать текущей, если мы выбираем случайный момент времени.
В основе PageRank лежит такая гипотеза: наиболее вероятные страницы в стационарном распределении должны быть также и самыми важными (мы посещаем эти страницы часто, потому что они получают ссылки со страниц, которые в процессе переходов тоже часто посещаются). Тогда стационарное распределение вероятностей определяет для каждого состояния значение PageRank.
Искусственный пример
Чтобы это стало намного понятнее, давайте рассмотрим искусственный пример. Предположим, что у нас есть крошечный веб-сайт с 7 страницами, помеченными от 1 до 7, а ссылки между этими страницами соответствуют следующему графу.
Ради понятности вероятности каждого перехода в показанной выше анимации не показаны. Однако поскольку подразумевается, что «навигация» должна быть исключительно случайной (это называют «случайным блужданием»), то значения можно легко воспроизвести из следующего простого правила: для узла с K исходящими ссылками (странице с K ссылками на другие страницы) вероятность каждой исходящей ссылки равна 1/K. То есть переходная матрица вероятностей имеет вид:
где значения 0.0 заменены для удобства на «.». Прежде чем выполнять дальнейшие вычисления, мы можем заметить, что эта цепь Маркова является неразложимой и апериодической, то есть в длительной перспективе система сходится к стационарному распределению. Как мы видели, можно вычислить это стационарное распределение, решив следующую левую задачу собственного вектора
Сделав так, мы получим следующие значения PageRank (значения стационарного распределения) для каждой страницы
Значения PageRank, вычисленные для нашего искусственного примера из 7 страниц.
Тогда ранжирование PageRank этого крошечного веб-сайта имеет вид 1 > 7 > 4 > 2 > 5 = 6 > 3.
Выводы
Основные выводы из этой статьи:
Разумеется, огромные возможности, предоставляемые цепями Маркова с точки зрения моделирования и вычислений, намного шире, чем рассмотренные в этом скромном обзоре. Поэтому мы надеемся, что нам удалось пробудить у читателя интерес к дальнейшему изучению этих инструментов, которые занимают важное место в арсенале учёного и эксперта по данным.