人工智能与机器学习原理精解【9】

马尔科夫过程论

基础

• 概率空间
  $$\begin{gathered} 总体(G,M,P)为概率空间，其中，G为某集， \\ M为它的子集\sigma 代数,P为M上的概率测度 \\ G中的点称为基本事件，M中的元为事件，值P(A)为事件的概率 \\ 每一个M-可测函数\phi (w)(w\in G)称为随机变量， \\ 积分{\int }_G\phi (w)P(dw)称为\phi 的数学期望，记为M\phi \\ 只定义在全空间G的子集G_{\phi }上的M可测函数\phi 称为随机变量 \\ {M}_{\phi }={\int }_G\phi (w)P(dw) \end{gathered}$$
• 马尔可夫链的状态转移概率矩阵
  假设一个马尔可夫链有三个状态：A、B和C。
  1.经过一段时间的观察，我们得到以下的转移次数：

根据上述数据，我们可以计算每个状态的转移频率，并构建状态转移概率矩阵：
$$\begin{gathered} 1.A行：A->A的状态转移频率为：(10)/(10+5+3)=0.55 \\ A->B的状态转移频率为：5/(10+5+3)=0.27 \\ A->C的状态转移频率为：3/(10+5+3)=0.17 \end{gathered}$$
$$\begin{gathered} 2.B行：B->A的状态转移频率为：2/(2+8+4)=0.14 \\ B->B的状态转移频率为：8/(2+8+4)=0.57 \\ B->C的状态转移频率为：4/(2+8+4)=0.29 \end{gathered}$$
$$\begin{gathered} 3.C行：C->A的状态转移频率为：1/(1+6+9)=0.06 \\ C->B的状态转移频率为：6/(1+6+9)=0.37 \\ C->C的状态转移频率为：9/(1+6+9)=0.57 \end{gathered}$$
因此，状态转移概率矩阵为：

P = ( 0.55 0.27 0.17 0.14 0.57 0.29 0.06 0.37 0.57 ) P =

$$\begin{pmatrix} 0.55 & 0.27 &0.17 \\ 0.14 & 0.57 &0.29 \\ 0.06 & 0.37 &0.57 \\ \end{pmatrix}$$ P= ​0.550.140.06​0.270.570.37​0.170.290.57​ ​

2. 验证

完成状态转移概率矩阵的构建后，需要验证每一行的元素之和是否等于1。这是因为从一个状态出发，转移到所有可能状态的概率之和必须为1，以满足概率的归一化条件。

通过以上步骤，就可以准确地计算出马尔可夫链的状态转移概率矩阵。

理论

得到马尔可夫链的状态转移概率矩阵

在得到马尔可夫链的状态转移概率矩阵时，我们首先需要明确马尔可夫链的所有可能状态以及这些状态之间的转移概率。以下是一个具体的例子，展示了如何根据给定的转移信息来构建状态转移概率矩阵。
计算马尔可夫链的状态转移概率通常基于实验观察、历史数据或理论假设。马尔可夫链的一个关键特性是“无记忆性”，即未来状态的概率分布仅依赖于当前状态，而与过去的状态无关。因此，状态转移概率描述了从当前状态转移到下一个状态的可能性。

计算状态转移概率的常见方法

以下是一些计算状态转移概率的常见方法：

1. 实验观察

最直接的方法是进行实验观察，并记录状态之间的转移情况。然后，可以使用这些观察数据来计算转移概率。例如，如果你正在观察一个天气系统，并记录每天的天气状态（晴天、多云、雨天），那么你可以计算从晴天转移到多云、晴天转移到雨天等的概率。

2. 历史数据分析

如果你有关于系统状态转移的历史数据，你可以使用这些数据来计算转移概率。这通常涉及统计每个状态转移到其他状态的频率，并将这些频率归一化为概率。

3. 理论假设

在某些情况下，你可能没有足够的数据来直接计算转移概率，或者你可能想要根据系统的某些已知特性来假设这些概率。例如，在建模一个排队系统时，你可能会根据到达率和服务率来假设状态之间的转移概率。

4. 使用统计模型

对于更复杂的系统，你可能需要使用统计模型来估计状态转移概率。这些模型可能包括回归分析、时间序列分析、机器学习算法等。

示例计算

假设你有一个简单的马尔可夫链，用于描述一个学生的学习状态（学习、休息、玩游戏），并且你已经有了一段时间的观察数据。以下是如何计算从“学习”状态转移到其他状态的概率的示例：

• 假设在观察期间，学生处于“学习”状态的总次数是100次。
• 在这100次中，学生继续学习的次数是70次。
• 学生从学习状态转移到休息状态的次数是20次。
• 学生从学习状态转移到玩游戏状态的次数是10次。

那么，从“学习”状态转移到其他状态的概率可以计算如下：

• 转移到“学习”的概率（即停留在当前状态）：$P(\text{学习}\to \text{学习})=\frac{70}{100}=0.7$
• 转移到“休息”的概率：$P(\text{学习}\to \text{休息})=\frac{20}{100}=0.2$
• 转移到“玩游戏”的概率：$P(\text{学习}\to \text{玩游戏})=\frac{10}{100}=0.1$

这些概率构成了状态转移概率矩阵中“学习”状态所在行的元素。

Python代码示例

虽然在这个简单的例子中我们不需要Python代码来计算概率（因为它们是直接基于观察数据得出的），但我们可以使用Python来验证或处理更复杂的数据集。

# 假设我们有以下观察数据
transitions_from_study = {'study': 70, 'rest': 20, 'game': 10}

# 计算从“学习”状态转移到其他状态的概率
total_transitions_from_study = sum(transitions_from_study.values())
transition_probs_from_study = {state: count / total_transitions_from_study for state, count in transitions_from_study.items()}

# 打印结果
print(transition_probs_from_study)
1
2
3
4
5
6
7
8
9

这段代码将输出从“学习”状态转移到其他状态的概率字典。

例子

假设有一个简单的马尔可夫链，用于描述一个学生的学习状态。该马尔可夫链有三种状态：

• 状态A：学生正在学习
• 状态B：学生正在休息
• 状态C：学生正在玩游戏

经过一段时间的观察，我们得到了以下状态之间的转移概率：

• 从状态A转移到A（继续学习）的概率为0.7
• 从状态A转移到B（开始休息）的概率为0.2
• 从状态A转移到C（开始玩游戏）的概率为0.1
• 从状态B转移到A（重新开始学习）的概率为0.4
• 从状态B转移到B（继续休息）的概率为0.5
• 从状态B转移到C（开始玩游戏）的概率为0.1
• 从状态C转移到A（结束游戏，开始学习）的概率为0.3
• 从状态C转移到B（结束游戏，开始休息）的概率为0.3
• 从状态C转移到C（继续玩游戏）的概率为0.4

（注意：这里假设了状态之间的转移是完整的，即所有可能的转移都被考虑到了，并且转移概率之和为1。）

接下来，我们将这些转移概率排列成矩阵形式，得到状态转移概率矩阵P：

P = [ 0.7 0.2 0.1 0.4 0.5 0.1 0.3 0.3 0.4 ] P =

$$\begin{bmatrix} 0.7 & 0.2 & 0.1 \\ 0.4 & 0.5 & 0.1 \\ 0.3 & 0.3 & 0.4 \end{bmatrix}$$ P= ​0.70.40.3​0.20.50.3​0.10.10.4​ ​

其中，矩阵P的每一行代表一个状态，每一列也代表一个状态。P[i][j]表示从状态i转移到状态j的概率。

Python代码验证

虽然在这个简单的例子中我们不需要Python代码来构建矩阵（因为它可以直接从给定的转移概率中写出来），但我们可以使用Python来验证矩阵的某些属性，比如每一行的概率之和是否等于1。

import numpy as np

# 定义状态转移概率矩阵
P = np.array([[0.7, 0.2, 0.1],
              [0.4, 0.5, 0.1],
              [0.3, 0.3, 0.4]])

# 验证每一行的概率之和是否等于1
print(np.all(np.sum(P, axis=1) == 1))  # 应该输出True
1
2
3
4
5
6
7
8
9

这段代码首先导入了NumPy库，然后定义了状态转移概率矩阵P。接着，它使用np.sum函数沿着轴1（即行方向）对矩阵进行求和，并使用np.all函数检查所有行的和是否都等于1。在这个例子中，输出应该是True，表示我们定义的状态转移概率矩阵是有效的。

马尔可夫链的状态转移概率矩阵

马尔可夫链的状态转移概率矩阵是描述马尔可夫链中各状态之间转移概率的矩阵。以下是一个具体的例子和例题来说明这一概念。

例子

假设有一个简单的马尔可夫链，用于描述一个网站的用户访问状态。该马尔可夫链有三种状态：

• 状态A：用户正在浏览首页
• 状态B：用户正在浏览产品页面
• 状态C：用户已经完成购买并离开

经过一段时间的观察，我们得到了以下状态转移次数：

（注意：在实际情况中，C状态到C状态的转移次数应为0，因为一旦用户完成购买并离开，他们就不会再回到这个“完成购买”的状态。但为了示例的完整性，这里暂时保留该列，并假设其转移次数为0。）

接下来，我们计算每个状态的转移频率，即每个状态转移到其他状态的次数除以该状态的总转移次数。以状态A为例：

• A的总转移次数 = 100 + 50 + 30 = 180
• A → A的转移频率 = 100 / 180 ≈ 0.556
• A → B的转移频率 = 50 / 180 ≈ 0.278
• A → C的转移频率 = 30 / 180 ≈ 0.167

类似地，我们可以计算出状态B和状态C的转移频率。然后，将这些转移频率排列成矩阵形式，即得到状态转移概率矩阵：

P = [ 0.556 0.278 0.167 0.250 0.500 0.250 0.333 0.167 0.000 ] P =

$$\begin{bmatrix} 0.556 & 0.278 & 0.167 \\ 0.250 & 0.500 & 0.250 \\ 0.333 & 0.167 & 0.000 \\ \end{bmatrix}$$ P= ​0.5560.2500.333​0.2780.5000.167​0.1670.2500.000​ ​

（注意：由于C状态到C状态的转移次数为0，且C状态是终止状态，因此C行的最后一列被设置为0。同时，为了保持矩阵的规范性，对C行的其他元素进行了归一化处理。）

例题

例题：给定一个马尔可夫链的状态转移概率矩阵P，以及初始状态分布向量v0，求经过n步转移后的状态分布向量vn。

解：

1. 定义状态转移概率矩阵P：
   假设P是一个m×m的矩阵，其中m是状态的数量。$P[i][j]表示从状态i转移到状态j的概率。$

2. 定义初始状态分布向量$v_0$：
   $v_0$是一个长度为m的向量，其中$v_0[i]$表示初始时处于状态i的概率。

3. 计算n步转移后的状态分布向量$v_n$：
   使用矩阵乘法，$v_n=v_{n-1}\times P=v_0\times P^n。其中，P^n表示矩阵P的n次方$。

4. 应用实例：
   $$\begin{gathered} 假设P和v_0如上例所示，且n=2， \\ 我们需要计算v_2。 \\ 这通常通过编程实现，因为手动计算矩阵的高次幂可能非常繁琐。 \end{gathered}$$

请注意，以上例题中的矩阵P和向量v_0是基于前面例子的简化表示，并且为了说明问题而进行了适当的调整。在实际应用中，P和v-0将根据具体问题的上下文来确定。

此外，马尔可夫链的状态转移概率矩阵在多个领域都有广泛的应用，如自然语言处理、机器学习、金融分析等。通过分析状态转移概率矩阵，我们可以获得关于系统动态行为的重要信息，并据此进行预测和决策。

马尔可夫链例子

马尔可夫链（Markov Chain）是一种数学系统，该系统中，每个事件的概率仅取决于该系统的当前状态，而与之前的状态无关。这种特性被称为“无记忆性”或“无后效性”。以下是几个马尔可夫链的例子和例题：

例子

• 天气预测
  描述：考虑一个天气预报模型，其中有三种可能的天气状态：晴天、多云和雨天。根据马尔科夫性质，预测明天的天气时，只需考虑今天的天气状态以及从今天到明天每种天气状态的转移概率。
  应用：在天气预测中，可以利用马尔科夫链来预测未来几天的天气情况。

• 股市波动
  描述：股市的涨跌也可以看作是一个马尔可夫链。假设股市有两种状态：上涨和下跌。根据历史数据，可以计算出从一种状态转移到另一种状态的概率。
  应用：投资者可以利用这些转移概率来制定投资策略，预测股市的未来走势。

• 随机游动
  描述：随机游动是马尔可夫链的一个经典例子。考虑一个质点在数轴上随机移动，每次只能向左或向右移动一单位，或原地不动。移动的概率是固定的，且各次移动相互独立。
  应用：随机游动模型在物理学、生物学、经济学等多个领域都有广泛的应用，如描述分子在溶液中的扩散过程、种群基因频率的随机变化等。

• 赌徒破产问题
  描述：赌徒甲和乙进行赌博，每局赌博甲获胜的概率为p，乙获胜的概率为q（p+q=1），且每局赌注为1元。甲初始时有a元，乙初始时有b元，直到其中一方输光为止。
  马尔可夫链：在这个问题中，可以将甲或乙的剩余资金视为系统的状态，系统的状态转移概率取决于当前状态和赌博的结果。
  应用：通过分析这个马尔可夫链，可以计算出甲或乙最终破产的概率。

例题

例题1：直线上带吸收壁的随机游动（醉汉游动）

• 描述：设一质点在线段[1,5]上随机游动，每秒钟发生一次随机游动，移动的规则是：若当前在位置1或5，则下一步只能停留在原位置（吸收壁）；若当前在位置2、3、4，则向左或向右移动的概率均为1/2。
• 问题：求质点在时刻n所处的位置的概率特性。
• 分析：这是一个典型的马尔可夫链问题，可以通过构建转移矩阵和转移图来求解。

例题2：赌徒输光问题的具体计算

• 描述：赌徒甲有资本a元，赌徒乙有资本b元，两人进行赌博，每赌一局输者给赢者1元，直到其中一人输光为止。设甲每局获胜的概率为p，乙获胜的概率为q（p+q=1）。
• 问题：求甲最终输光的概率。
• 分析：这个问题可以通过构建马尔可夫链，并求解从初始状态（甲有a元）到吸收状态（甲输光，即0元）的转移概率来求解。可以使用动态规划或递推关系式等方法进行计算。

以上例子和例题展示了马尔可夫链在不同领域中的应用和求解方法。通过构建和分析马尔可夫链，我们可以更好地理解和预测这些系统的行为。

概率测度

定义

概率测度（Probability Measure）是概率论、遍历理论等数学分支中常用的一种重要的有限测度。在数学中，概率测度是在满足测度属性（如可加性）的概率空间中的一组事件上定义的实值函数。具体而言，概率测度μ在测度空间(X,Ω,μ)中，如果满足μ(X)=1，则称μ为概率测度。这意味着整个概率空间X的概率测度为1，且对于任意可数的不相交集合，其并集的概率等于各集合概率之和（即满足可加性）。

原理

概率测度的原理主要基于测度论，特别是概率空间中的可加性原理。这一原理表明，对于任意两个不相交的事件A和B（即A∩B=∅），事件A和B的并集的概率P(A∪B)等于事件A的概率P(A)与事件B的概率P(B)之和，即P(A∪B)=P(A)+P(B)。这一原理是概率论中最基本的原理之一，也是概率测度定义的核心。

例子

1. 抛硬币：假设有一个公平的硬币，抛掷后正面朝上的概率为P(正面)=0.5，反面朝上的概率为P(反面)=0.5。这里，整个样本空间（即所有可能的结果）的概率测度为1，正面和反面这两个不相交事件的概率之和也为1，满足概率测度的定义。
2. 掷骰子：一个六面体的骰子，每一面出现的概率都是1/6。这里，整个样本空间（即骰子的六个面）的概率测度为1，每一面作为一个事件，其概率之和也为1。

例题

例题：一个袋子中有5个红球和3个白球，随机取出一个球，求取出红球的概率。

解：

1. 定义样本空间：样本空间Ω是所有可能取出的球组成的集合，即Ω={红球1, 红球2, …, 红球5, 白球1, 白球2, 白球3}。但在这里，我们更关心的是球的颜色种类，因此可以将样本空间简化为Ω’={红球, 白球}。
2. 定义事件：事件A是“取出红球”。
3. 计算概率：根据概率测度的定义，事件A的概率P(A)是事件A包含的样本点数与整个样本空间包含的样本点数之比。即P(A)=红球数/总球数=5/8。

这个例题展示了如何在具体情境中应用概率测度的定义和原理来计算事件的概率。

σ代数的定义、原理、例子和例题

一、定义

σ代数（σ-algebra）在数学中，特别是在测度论中，是一个重要的概念。它又称为σ域、完全加法类、可列加法类、σ加法类，是某个集合X的所有子集的集合（即幂集）的一个子集。
这个子集满足对于可数个集合的并集运算和补集运算的封闭性（因此对于交集运算也是封闭的）。
σ代数可以用来严格地定义所谓的“可测集”，是测度论的基础概念之一。

二、原理

σ代数的核心原理在于其对可数个集合运算的封闭性。具体来说，如果Γ是由集合X中一些子集所构成的集合族（也叫做集类），并且满足以下条件：

1. X ∈ Γ（即X本身属于Γ）。
2. 若A ∈ Γ，则A的补集A^c ∈ Γ（即A的补集也属于Γ）。
3. 若A_n ∈ Γ（n=1,2,…），则∪A_n ∈ Γ（即可数个A_n的并集也属于Γ）。

那么，我们称Γ是一个σ代数。

三、例子

假设集合X = {a, b, c, d}，我们可以构造一个σ代数如下：

1. 首先，X本身和空集∅是任何σ代数都必须包含的。
2. 假设我们选取子集{a, b}和{c}作为σ代数的基础元素。
3. 根据σ代数的定义，我们需要包含这些基础元素的补集，即{a, b}的补集{c, d}和{c}的补集{a, b, d}。
4. 接下来，我们可以考虑这些子集的并集。例如，{a, b} ∪ {c} = {a, b, c}，{a, b} ∪ {c, d} = {a, b, c, d}（即X本身），{c} ∪ {a, b, d} = {a, b, c, d}（同样是X本身），但这些并集要么已经在基础元素中（如X本身），要么可以通过其他方式得到（如{a, b, c}可以通过{a, b}和{c}的并集得到，但它不是直接从基础元素通过补集和并集操作得到的）。
5. 实际上，在这个例子中，我们可以构造一个更小的σ代数，只包含{∅, {a, b}, {c}, {a, b, c, d}}，这个集合族满足σ代数的所有条件。

然而，需要注意的是，这个例子并不是唯一的，而且在实际应用中，σ代数可能会包含更多的元素。

四、例题

例题：已知Ω={1,2,3}，求由C={{1,2},{1,3}}生成的σ代数。

答案：

1. 首先，包含Ω和空集∅。
2. 包含C中的元素{1,2}和{1,3}。
3. 包含这些元素的补集：{1,2}的补集是{3}，{1,3}的补集是{2}。
4. 考虑并集：{1,2} ∪ {1,3} = {1,2,3}（即Ω本身），但Ω已经在集合中了；{1,2} ∪ {2} = {1,2}，但这个结果已经在C中了；{1,3} ∪ {3} = {1,3}，这个结果也在C中了；{1,3} ∪ {2} = {1,2,3}（即Ω），但这个结果已经在集合中了。
5. 因此，由C={{1,2},{1,3}}生成的σ代数为{∅, {1}, {2}, {3}, {1,2}, {1,3}, {Ω}}。注意这里{1},{2},{3}是通过补集操作间接得到的（例如，{1}是{2,3}的补集，而{2,3}是Ω中除了{1,2}和{1,3}之外的部分）。但在实际书写时，我们通常会直接列出这些元素，而不是通过补集操作来推导它们。

这个例题展示了如何从一个给定的集合族出发，通过应用σ代数的定义（即包含原集合、补集和可数个并集）来构造一个σ代数。

参考文献

1.文心一言
2.《邓肯-马尔科夫过程论基础》