[Перевод] Учебник для начинающих по реализации цепей Маркова в Python

Оригинальный адрес:Markov Chains in Python: Beginner Tutorial

Оригинальный автор:Sejal Jaiswal

Перевод с:Программа перевода самородков

Постоянная ссылка на эту статью:GitHub.com/rare earth/gold-no…

Переводчик:cdpath

Корректор:jianboy, Kasheem Lew

Узнайте о цепях Маркова и их свойствах, узнайте о матрицах переходов и освойте Python!

Цепь Маркова — это математическая система, обычно определяемая набором случайных величин, которая может выполнять переходы между состояниями в соответствии с определенными вероятностными правилами. Набор передач удовлетворяетмарковское свойство, то есть вероятность перехода в какое-либо конкретное состояние зависит только от текущего состояния и затраченного времени, а не от его предыдущей последовательности состояний. Это уникальное свойство цепей Маркова заключается в том, чтонет памяти.

Следуйте этому руководству, чтобы научиться использовать цепи Маркова, и вы пойметеЦепь Маркова с дискретным временемчто. Вы также научитесь строить (дискретное время)Модель цепи МарковаНеобходимые компоненты и их общие характеристики. Затем научитесь использовать Python и егоnumpyиrandomбиблиотека для реализации простой модели. Также научитесь представлять цепи Маркова различными способами, такими как диаграммы состояний иматрица перехода.

Хотите решить больше статистических задач с помощью Python? Узнайте о DataCampКурс статистического мышления Python!

Давайте начнем……

Зачем использовать цепи Маркова?

Цепи Маркова широко используются в математике. Он также имеет широкий спектр приложений в экономике, теории игр, принципах коммуникации, генетике и финансах. Часто появляется в статистике, особенно в байесовской статистике, и в контексте теории информации. В действительности цепи Маркова предоставляют решения для изучения системы круиз-контроля автомобилей, очереди пассажиров, прибывающих в аэропорт, и курсов обмена валют. PageRank, впервые предложенный поисковой системой Google, представляет собой алгоритм, основанный на марковском процессе. В Reddit есть подраздел «Симулятор подраздела», Все сообщения и комментарии генерируются автоматически с использованием цепей Маркова.

Цепь Маркова

Цепь Маркова — это случайный процесс со свойствами Маркова. Стохастический процесс или случайный процесс — это математический объект, определяемый набором случайных величин. Цепи Маркова имеют либо дискретное пространство состояний (набор возможных значений случайной величины), либо дискретный набор индексов (обычно представляющих время), и существует множество вариантов цепей Маркова. Так называемая «цепь Маркова» относится к процессу с набором дискретного времени, то есть цепи Маркова с дискретным временем (DTMC).

Цепь Маркова с дискретным временем

Каждый шаг системы, содержащейся в цепи Маркова с дискретным временем, находится в определенном состоянии, и состояние изменяется случайным образом между шагами. Эти шаги часто сравнивают с моментами времени (хотя вы также можете думать о физических расстояниях или любой дискретной мере). Цепь Маркова с дискретным временем представляет собой последовательность случайных величин X1, X2, X3..., но она должна удовлетворять марковскому свойству, поэтому вероятность перехода к следующей связана только с текущим состоянием и не имеет ничего общего с предыдущим состоянием. Математическая формула вероятности выражается следующим образом:

Pr( Xn+1 = x | X1 = x1, X2 = x2, …, Xn = xn) = Pr( Xn+1 = x | Xn = xn)

Можно видеть, что вероятность Xn+1 связана только с предыдущей вероятностью Xn. Таким образом, вам нужно знать только предыдущее состояние, чтобы определить распределение вероятностей текущего состояния, удовлетворяющее условной независимости (то есть вам нужно знать только текущее состояние, чтобы определить следующее состояние).

Счетное множество S, образованное возможными значениями Xi, называется цепью Марковагосударственное пространство. Пространство состояний может быть любым: буквы, цифры, результаты баскетбольных матчей или погодные условия. Хотя временные параметры обычно дискретны, пространство состояний марковских цепей с дискретным временем не имеет общепринятых ограничений, и лучше рассматривать процесс в любом пространстве состояний. Однако во многих приложениях цепей Маркова используются конечные или счетно бесконечные пространства состояний, где статистический анализ проще.

Модель

Цепи Маркова представлены вероятностными автоматами (поверьте мне, это не так сложно, как кажется!). Изменения в состоянии системы называются переходами. Вероятность изменения каждого состояния называется вероятностью перехода. Вероятностный автомат состоит из вероятностей известных переходов к уравнениям переходов, которые преобразуются в матрицы переходов.

Вы также можете думать о цепи Маркова как о ориентированном графе, где ребра графа n обозначают вероятность того, что состояние в момент времени n переходит в состояние в момент времени n+1, Pr(Xn+1 = x | Xn = xn) . Это выражение можно прочитать как вероятность перехода из известного состояния Xn в состояние Xn+1. Эту концепцию также можно использовать от времени n до времени n+1.матрица переходаПредставлять. Первое появление каждого состояния в пространстве состояний — это строка матрицы перехода, а второе — столбец. Каждый элемент матрицы представляет собой вероятность перехода из состояния, представленного этой строкой, в состояние столбца.

Если цепь Маркова имеет N состояний, матрица перехода имеет размерность N x N, где (I, J) представляет собой вероятность перехода из состояния I в состояние J. Кроме того, матрица перехода должна быть матрицей вероятностей, то есть сумма элементов в каждой строке должна быть равна 1. Зачем? Потому что каждая строка представляет свое собственное распределение вероятностей.

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

Кажется сложным?

Давайте рассмотрим простой пример, который поможет понять эти концепции:

Если СиДжей была в редком настроении, она бегала, или ела мороженое (примечание переводчика: гугл должен быть гобл), или вздремнула, чтобы привыкнуть.

Согласно прошлым данным, если она хорошо выспалась ночью, чтобы настроить свое настроение, она с вероятностью 60% отправится на пробежку на следующий день, с вероятностью 20% останется в постели и с вероятностью 20% съест большую порцию льда. крем.

Если она бежит, чтобы расслабиться, с вероятностью 60 % она будет бегать на следующий день, с вероятностью 30 % будет есть мороженое и только с вероятностью 10 % ляжет спать.

Наконец, если она баловалась мороженым, когда ей было грустно, то вероятность того, что она продолжит есть мороженое на следующий день, составляла всего 10 %, вероятность побегать — 70 %, а вероятность сна — 20 %.

Цепь Маркова, представленная на приведенной выше диаграмме состояний, имеет 3 возможных состояния: сон, работа и мороженое. Таким образом, матрица перехода представляет собой матрицу 3 x 3. Обратите внимание, что сумма значений стрелок, выходящих из определенного состояния, должна быть равна 1, что совпадает с суммой элементов каждой строки матрицы состояния, равной 1, что представляет собой распределение вероятностей. Значение каждого элемента в матрице перехода аналогично значению каждого состояния на диаграмме состояний.

Этот пример должен помочь вам понять несколько различных концепций, связанных с цепями Маркова. Но как эта теория применима в реальном мире?

С помощью этого примера вы должны быть в состоянии ответить на вопрос: «Какова вероятность того, что Cj, наконец, решит бежать (состояние бега) через 2 дня после выхода из спящего состояния?»

Давайте посчитаем вместе. Для перехода от сна к бегу у Сиджея есть следующие варианты: в первый день продолжать спать, а во второй день бегать (0,2 ⋅ 0,6), в первый день перейти на бег, а во второй день продолжить бегать (0,6). ⋅ 0,6); первый Ходить за мороженым в один день и бегать на следующий день (0,2 ⋅ 0,7). Расчетная вероятность: ((0,2 ⋅ 0,6) + (0,6 ⋅ 0,6) + (0,2 ⋅ 0,7)) = 0,62. Итак, начиная со спящего состояния, вероятность того, что Cj окажется в рабочем состоянии через 2 дня, составляет 62%.

Надеюсь, этот пример покажет вам, какие проблемы могут быть решены с помощью сетей Маркова.

В то же время можно лучше понять несколько важных свойств цепей Маркова:

Интероперабельность: цепь Маркова неприводима, если она может переходить из любого состояния в любое состояние. Другими словами, если вероятность того, что существует последовательность шагов между любыми двумя состояниями, положительна, она неприводима.
Периодичность: состояние цепи Маркова является периодическим, если она возвращает состояние только в том случае, если оно больше целого числа, кратного 1. Следовательно, начиная с состояния «i», вернуться в «i» можно только через целое число, кратное циклам «k», где k — максимальное значение всех целых чисел, удовлетворяющих условию. Если k = 1, состояние «i» не периодическое, если k > 1, «i» периодическое.
Преходящее и повторяющееся: если, начиная с состояния «i», существует вероятность того, что он не может вернуться в состояние «i», тогда состояние «i» является переходным. В противном случае оно повторяется (или постоянно). Если состояние можно воспроизвести за конечное число шагов, оно повторяется, в противном случае оно не повторяется.
Эргодическое: состояние «i» является эргодическим, если оно удовлетворяет апериодичности и положительной рекуррентности. Если каждое неприводимое состояние цепи Маркова эргодично, то эта цепь Маркова также эргодична.
Поглощающее состояние: «i» находится в поглощающем состоянии, если его нельзя перевести из состояния «i» в другое состояние. Следовательно, если pii = 1 и pij = 0, когда i ≠ j, состояние «i» находится в поглощающем состоянии. Если каждое состояние цепи Маркова может достигать состояния поглощения, она называется цепью Маркова с состоянием поглощения.

обманывать: ты можешь видетьэтот сайтДано наглядное объяснение цепи Маркова.

Реализация цепей Маркова в Python

Давайте реализуем приведенный выше пример на Python. Конечно, цепь Маркова, реализованная в реальной библиотеке, будет намного эффективнее Вот пример кода, который поможет вам начать работу...

Сначала импортируйте используемую библиотеку.

import numpy as np
import random as rm

Затем задайте состояния и их вероятности, то есть матрицу переходов. Помните, поскольку есть три состояния, матрица 3х3-мерная. Кроме того, должен быть определен путь перехода, который также может быть представлен матрицей.

# 状态空间
states = ["Sleep","Icecream","Run"]

# 可能的事件序列
transitionName = [["SS","SR","SI"],["RS","RR","RI"],["IS","IR","II"]]

# 概率矩阵（转移矩阵）
transitionMatrix = [[0.2,0.6,0.2],[0.1,0.6,0.3],[0.2,0.7,0.1]]

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

if sum(transitionMatrix[0])+sum(transitionMatrix[1])+sum(transitionMatrix[1]) != 3:
    print("Somewhere, something went wrong. Transition matrix, perhaps?")
else: print("All is gonna be okay, you should move on!! ;)")

All is gonna be okay, you should move on!! ;)

Теперь, чтобы добраться до сути. мы будем использоватьnumpy.random.choiceСлучайная выборка выбирается из множества возможных переходов. Значение большинства параметров в коде видно из названия параметра, но параметрpМожет сбивать с толку. Это необязательный параметр, который можно передать в распределении вероятностей набора выборок, в данном случае матрицу перехода.

# 实现了可以预测状态的马尔可夫模型的函数。
def activity_forecast(days):
    # 选择初始状态
    activityToday = "Sleep"
    print("Start state: " + activityToday)
    # 应该记录选择的状态序列。这里现在只有初始状态。
    activityList = [activityToday]
    i = 0
    # 计算 activityList 的概率
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1  
    print("Possible states: " + str(activityList))
    print("End state after "+ str(days) + " days: " + activityToday)
    print("Probability of the possible sequence of states: " + str(prob))

# 预测 2 天后的可能状态
activity_forecast(2)

Start state: Sleep
Possible states: ['Sleep', 'Sleep', 'Run']
End state after 2 days: Run
Probability of the possible sequence of states: 0.12

В результате могут быть получены возможные переходы из состояния сна и их вероятности. Расширяя эту функцию, она может начинаться из спящего состояния и повторяться несколько сотен раз, чтобы получить ожидаемую вероятность завершения в определенном состоянии. Перепишите это нижеactivity_forecastфункция, добавьте несколько циклов...

def activity_forecast(days):
    # 选择初始状态
    activityToday = "Sleep"
    activityList = [activityToday]
    i = 0
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1    
    return activityList

# 记录每次的 activityList
list_activity = []
count = 0

# `range` 从第一个参数开始数起，一直到第二个参数（不包含）
for iterations in range(1,10000):
        list_activity.append(activity_forecast(2))

# 查看记录到的所有 `activityList`    
#print(list_activity)

# 遍历列表，得到所有最终状态是跑步的 activityList
for smaller_list in list_activity:
    if(smaller_list[2] == "Run"):
        count += 1

# 计算从睡觉状态开始到跑步状态结束的概率
percentage = (count/10000) * 100
print("The probability of starting at state:'Sleep' and ending at state:'Run'= " + str(percentage) + "%")

The probability of starting at state:'Sleep' and ending at state:'Run'= 62.419999999999995%

Итак, вопрос в том, почему расчетный результат стремится к 62%?

УведомлениеНа самом деле это «закон больших чисел» в действии. Закон больших чисел — это закон вероятности, который гласит, что события с одинаковой вероятностью имеют тенденцию происходить с одинаковой частотой при достаточном количестве испытаний. То есть по мере увеличения числа испытаний фактическое отношение стремится к теоретической или прогнозируемой вероятности.

марковское мышление

Вот и все, что касается учебника по цепям Маркова. В этой статье представлены цепи Маркова и их свойства. Простые цепи Маркова — это способ начать изучение науки о данных Python. Дополнительные ресурсы по статистике Python см.этот сайт.

Если вы обнаружите ошибки в переводе или в других областях, требующих доработки, добро пожаловать наПрограмма перевода самородковВы также можете получить соответствующие бонусные баллы за доработку перевода и PR. начало статьиПостоянная ссылка на эту статьюЭто ссылка MarkDown этой статьи на GitHub.

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.