Python中的马尔可夫链(入门教程)

本文概述

  • 为什么选择马尔可夫链
  • 马尔可夫链
  • 离散时间马尔可夫链
  • 模型
  • Python中的马尔可夫链
  • 马尔可夫心态
马尔可夫链是通常定义为随机变量集合的数学系统, 该随机变量根据某些概率规则从一种状态转换为另一种状态。这些过渡集满足马尔可夫性质, 该性质表明过渡到任何特定状态的可能性仅取决于当前状态和经过的时间, 而不取决于之前的状态顺序。马尔可夫过程的这一独特特征使其无记忆。
在本教程中, 你将发现何时可以使用马尔可夫链, 什么是离散时间马尔可夫链。你还将了解构建(离散时间)马尔可夫链模型所需的组件及其一些公共属性。接下来, 你将使用Python的numpy和random库实现一个这样的简单模型。你还将学习一些表示Markov链的方法, 例如状态图和转换矩阵。
是否想使用Python处理更多的统计主题?查看srcmini的Python统计思维课程!
让我们过渡…
为什么选择马尔可夫链 马尔可夫链在数学中有丰富的用途。它们被广泛应用于经济学, 博弈论, 传播理论, 遗传学和金融学。它们广泛地出现在统计方面, 特别是贝叶斯统计和信息理论环境中。当遇到实际问题时, 它们被用于提出解决方案, 以研究汽车中的巡航控制系统, 到达机场的顾客排队或排队, 货币汇率等。最初提出的称为PageRank的算法互联网搜索引擎Google是基于马尔可夫过程的。 Reddit的Subreddit Simulator是一个全自动的subreddit, 它使用markov链生成随机提交和评论, 太酷了!
马尔可夫链 马尔可夫链是具有马尔可夫属性的随机过程。随机过程或通常称为随机属性是定义为随机变量集合的数学对象。马尔可夫链具有离散状态空间(随机变量的可能值集)或离散索引集(通常表示时间)-事实是, 马尔可夫链存在许多变化。通常, 术语” 马尔可夫链” 保留给具有离散时间集的过程, 即离散时间马尔可夫链(DTMC)。
离散时间马尔可夫链 离散时间马尔可夫链涉及一个系统, 该系统在每个步骤中都处于特定状态, 并且该状态在各个步骤之间随机变化。这些步骤通常被认为是时间上的瞬间(但是你也可以参考物理距离或任何其他离散量度)。离散时间马尔可夫链是具有马尔可夫属性的一系列随机变量X1, X2, X3, … , 因此, 移动到下一个状态的概率仅取决于当前状态, 而不取决于先前的状态。放这是数学概率公式:
Pr(Xn + 1 = x | X1 = x1, X2 = x2, … , Xn = xn)= Pr(Xn + 1 = x | Xn = xn)
如你所见, Xn + 1的概率仅取决于它前面的Xn的概率。这意味着了解前一状态是确定当前状态的概率分布所必需的, 满足条件独立性的规则(或以其他方式说:你只需知道当前状态即可确定下一状态)。
Xi的可能值形成一个可计数的集合S, 称为链的状态空间。状态空间可以是任何东西:字母, 数字, 篮球得分或天气情况。尽管时间参数通常是离散的, 但离散时间马尔可夫链的状态空间没有任何广泛同意的限制, 而是指任意状态空间上的过程。但是, 马尔可夫链的许多应用都采用有限或可计数的无限状态空间, 因为它们具有更直接的统计分析。
模型 使用概率自动机表示马尔可夫链(听起来很复杂!)。系统状态的变化称为过渡。与各种状态变化相关联的概率称为过渡概率。概率自动机包括将给定转换为转换函数的概率, 将其转换为转换矩阵。
你可以将其视为有向图的序列, 其中图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。为什么?由于每一行代表其自己的概率分布。
因此, 该模型的特征在于状态空间, 描述特定转换概率的转换矩阵以及状态空间中的初始状态(在初始分布中给出)。
整个单词都是吗?
让我们看一个简单的例子来理解这些概念:
当Cj难过时, 这不是很平常:她要么去跑步, 要么倒冰淇淋, 要么小睡。
从历史数据来看, 如果她度过了难过的一天。第二天, 她有60%的可能性去跑步, 第二天她有20%的时间躺在床上, 而她有20%的机会吃冰淇淋。
当她悲伤并要跑步时, 第二天有60%的机会去跑步, 第二天她有30%的机会吃冰淇淋, 第二天睡觉的机会只有10%。
最后, 当她在悲伤的一天沉迷于冰淇淋时, 第二天她仍然只有10%的机会继续吃冰淇淋, 第二天她很可能会跑步, 而第二天她会花20%的时间睡觉天。
Python中的马尔可夫链(入门教程)

文章图片
状态图中描述的马尔可夫链具有3种可能的状态:睡眠, 跑步, 冰淇淋。因此, 过渡矩阵将是3 x 3矩阵。请注意, 退出状态的箭头总和总计为1, 类似地, 转换矩阵中每一行中的项也必须总计为1, 代表概率分布。在过渡矩阵中, 单元格执行的操作与状态图中的箭头相同。
Python中的马尔可夫链(入门教程)

文章图片
现在你已经看到了示例, 这应该使你对与马尔可夫链有关的不同概念有所了解。但是, 在现实生活中如何以及在何处使用这些理论?
在你看到的示例中, 你现在可以回答以下问题:” 从状态:睡眠开始, 在令人难过的2天持续时间结束时, Cj运行(状态:运行)的概率是多少?”
让我们来解决这个问题:为了从状态:睡眠转换为状态:运行, Cj必须保持在状态:睡眠第一个动作(或一天), 然后移动至状态:运行下一(第二个)动作(0.2 $ \ cdot $ 0.6); 或移至状态:运行第一天, 然后在第二天呆在那儿(0.6 $ \ cdot $ 0.6), 否则她可以过渡到状态:在第一步运行冰淇淋, 然后到状态:在第二天运行(0.2 $ \ cdot $ 0.7)。因此概率为(((0.2 $ \ cdot $ 0.6)+(0.6 $ \ cdot $ 0.6)+(0.2 $ \ cdot $ 0.7))= 0.62。因此, 我们现在可以说Cj进入状态的机会有62%:如果她开始处于该状态, 则是在悲伤的两天后运行:睡觉。
希望这使你对使用马尔可夫链网络可以回答的各种问题有所了解。
同样, 有了这一清晰的思想, 就更容易理解马尔可夫链的一些重要属性:
  • 可还原性:如果可以从任何状态进入任何状态, 则认为马尔可夫链是不可约的。换句话说, 如果在两个具有正概率的状态之间存在步骤链, 则马尔可夫链是不可约的。
  • 周期性:如果马尔可夫链只能以大于1的某个整数的倍数返回状态, 则该状态为周期性。因此, 从状态” i” 开始, 链只能以整数的倍数返回” i” 。周期” k” , 而k是最大的整数。如果k = 1, 则状态’ i’ 是非周期性的;如果k> 1, 则状态’ i’ 是周期性的。
  • 瞬态和递归:如果假设我们从状态” i” 开始, 并且我们永远不会返回” i” 的可能性为非零, 则状态” i” 被称为瞬态。如果状态i不是瞬态的, 则它是周期性的(或持久的)。如果期望在有限的步数内返回, 则循环状态称为正循环, 否则将其称为空循环。
  • 遍历性:如果状态” i” 是非周期性且为正重复性, 则称其为遍历性。如果不可约马尔可夫链中的所有状态都是遍历的, 则称该链为遍历的。
  • 吸收状态:如果无法离开该状态, 则称为吸收状态。因此, 对于i≠j, 如果pii = 1且pij = 0, 则状态” i” 正在吸收。如果每个状态都可以达到吸收状态, 那么马尔可夫链就是吸收马尔可夫链。
提示:如果你还想看到马尔可夫链的直观说明, 请确保访问此页面。
Python中的马尔可夫链 让我们尝试用Python编写上面的示例。尽管在现实生活中, 你可能会使用以高效方式对马氏链进行编码的库, 但是代码应该可以帮助你入门…
首先, 导入一些将要使用的库。
import numpy as npimport random as rm

现在让我们定义状态及其概率:转移矩阵。请记住, 矩阵将是3 X 3矩阵, 因为你具有三个状态。同样, 你将必须定义过渡路径, 也可以使用矩阵进行此操作。
# The statespacestates = ["Sleep", "Icecream", "Run"]# Possible sequences of eventstransitionName = [["SS", "SR", "SI"], ["RS", "RR", "RI"], ["IS", "IR", "II"]]# Probabilities matrix (transition matrix)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可能不是。它是一个可选参数, 可让你输入采样集的概率分布, 在本例中为过渡矩阵。
# A function that implements the Markov model to forecast the state/mood.def activity_forecast(days):# Choose the starting stateactivityToday = "Sleep"print("Start state: " + activityToday)# Shall store the sequence of states taken. So, this only has the starting state for now.activityList = [activityToday]i = 0# To calculate the probability of the activityListprob = 1while i != days:if activityToday == "Sleep":change = np.random.choice(transitionName[0], replace=True, p=transitionMatrix[0])if change == "SS":prob = prob * 0.2activityList.append("Sleep")passelif change == "SR":prob = prob * 0.6activityToday = "Run"activityList.append("Run")else:prob = prob * 0.2activityToday = "Icecream"activityList.append("Icecream")elif activityToday == "Run":change = np.random.choice(transitionName[1], replace=True, p=transitionMatrix[1])if change == "RR":prob = prob * 0.5activityList.append("Run")passelif change == "RS":prob = prob * 0.2activityToday = "Sleep"activityList.append("Sleep")else:prob = prob * 0.3activityToday = "Icecream"activityList.append("Icecream")elif activityToday == "Icecream":change = np.random.choice(transitionName[2], replace=True, p=transitionMatrix[2])if change == "II":prob = prob * 0.1activityList.append("Icecream")passelif change == "IS":prob = prob * 0.2activityToday = "Sleep"activityList.append("Sleep")else:prob = prob * 0.7activityToday = "Run"activityList.append("Run")i += 1print("Possible states: " + str(activityList))print("End state after "+ str(days) + " days: " + activityToday)print("Probability of the possible sequence of states: " + str(prob))# Function that forecasts the possible state for the next 2 daysactivity_forecast(2)

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

从状态:睡眠开始, 你会获得随机的过渡集以及发生过渡的可能性。进一步扩展该程序, 以使其在相同的开始状态下迭代数百次, 然后你可以看到在任何特定状态下结束的预期概率及其概率。让我们重写函数activity_forecast并添加一组新的循环来执行此操作…
def activity_forecast(days):# Choose the starting stateactivityToday = "Sleep"activityList = [activityToday]i = 0prob = 1while i != days:if activityToday == "Sleep":change = np.random.choice(transitionName[0], replace=True, p=transitionMatrix[0])if change == "SS":prob = prob * 0.2activityList.append("Sleep")passelif change == "SR":prob = prob * 0.6activityToday = "Run"activityList.append("Run")else:prob = prob * 0.2activityToday = "Icecream"activityList.append("Icecream")elif activityToday == "Run":change = np.random.choice(transitionName[1], replace=True, p=transitionMatrix[1])if change == "RR":prob = prob * 0.5activityList.append("Run")passelif change == "RS":prob = prob * 0.2activityToday = "Sleep"activityList.append("Sleep")else:prob = prob * 0.3activityToday = "Icecream"activityList.append("Icecream")elif activityToday == "Icecream":change = np.random.choice(transitionName[2], replace=True, p=transitionMatrix[2])if change == "II":prob = prob * 0.1activityList.append("Icecream")passelif change == "IS":prob = prob * 0.2activityToday = "Sleep"activityList.append("Sleep")else:prob = prob * 0.7activityToday = "Run"activityList.append("Run")i += 1return activityList# To save every activityListlist_activity = []count = 0# `Range` starts from the first count up until but excluding the last countfor iterations in range(1, 10000):list_activity.append(activity_forecast(2))# Check out all the `activityList` we collected#print(list_activity)# Iterate through the list to get a count of all activities ending in state:'Run'for smaller_list in list_activity:if(smaller_list[2] == "Run"):count += 1# Calculate the probability of starting from state:'Sleep' and ending at state:'Run'percentage = (count/10000) * 100print("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进行统计, 请确保签出此页面。
【Python中的马尔可夫链(入门教程)】你是否有兴趣探索更实用的Python统计案例研究?在Python课程中查看srcmini在统计思维或网络分析中的案例研究。

    推荐阅读