概率图模型(1)——马尔可夫链

作者: To_QT | 来源:发表于2019-05-13 10:50 被阅读0次

思维导图

1. 定义

马尔可夫链：过程在 $t>t_0$ 时刻所处状态条件与过程在时刻 $t_0$ 之前所出的状态无关。（在已经知道“现在”的条件下，其“将来”与“过去”无关）
数学表达为：
$\begin{align} P \{X(t_n) = x_n|X(t_1)=x_1, X(t_2)=x_2,....,X(t_{n-1})=x_{n-1} \} \\ = P\{X(t_n) = x_n|X(t_{n-1})=x_{n-1} \} \tag {1.1} \end{align}$

2. 案例

2.1 模型准备

Bob和Alice是一对好朋友，Bob的心情与天气有关，如果天气很好为sunny，记为S，Bob一般是处于happy，记为H状态的，如果天气是rain，记为R，Bob的心情一般是处于grumpy，记为G状态的。 Alice呢，是一个很细心很会观察的女孩，收集了14天以来天气情况，以及Bob15天的心情。

统计图中状态转换对应的数量：

头一天天气	第二天天气	数量	比例
sunny	sunny	8	0.8
sunny	rain	2	0.2
rain	sunny	2	0.4
rain	rain	3	0.6

图2. Bob心情与天气对应关系

统计图中状态转换对应的数量：

天气	心情	数量	比例
sunny	happy	8	0.8
sunny	grumpy	2	0.2
rain	happy	2	0.4
rain	grumpy	3	0.6

图.2 天气状态转换统计以及心情对应统计图

绘制了下面这张图。

图3

图3-1中的几个概率值称为transition probabilities

图3-1

图3-2中的几个概率值称为emission probabilities

图3-2

2.2 考虑三个问题：

Question 1：如果随机选一天，Alice没从Bob那得到任何消息，那这天是晴天还是下雨天？

在[图2. Bob心情与天气对应关系]中，晴天有十天，雨天有五天，在Bob没有任何信息提示的情况下，晴天所占比例为 $2/3$ ，雨天所占比例为 $1/3$ 。所以第一问题的答案为有 $2/3$ 的可能性是晴天， $1/3$ 的可能性是雨天。

Question 2：如果Bob今天很开心，那么是晴天和雨天的概率各是多少？

其实这是一个贝叶斯问题：
已知
$P(Sunny)=2/3$ , $P(Rain)=1/3$ ,
$P(Happy)=2/3$ , $P(Grumpy)=1/3$ ,
$P(Happy|Sunny)=0.8$ , $P(Grumpy|Sunny)=0.2$ ,
$P(Happy|Rain)=0.4$ , $P(Grumpy|Rain)=0.6$

求 $P(Sunny| Happy)$ 与 $P(Rain| Happy)$ 的概率。

$P(Sunny| Happy) = \frac{P(Happy|Sunny)P(Sunny)}{P(Happy)}=0.8$

$P(Rain| Happy) = \frac{P(Happy|Rain)P(Rain)}{P(Happy)}=0.2$

Question 3：连续三天Bob的心情是Happy-Grumpy-Happy，最后一天是什么天气？

image.png

连续三天，共有 $2^3=8$ 中可能：

Sunny - Sunny - Sunny
Sunny - Sunny - Rain
Sunny - Rain - Sunny
Sunny - Rain - Rain
Rain - Rain - Rain
Rain - Rain - Sunny
Rain - Sunny - Rain
Rain - Sunny - Sunny

以第3种情况为例：

image.png

这样分别计算8中情况，取概率最大的

2.3 Viterbi 算法：

如果Bob的心情是“Happy-Happy-Grumpy-Grumpy-Grumpy-Happy”问最后一天的天气？

2.3.1 思路

考虑了六天，那么总共有 $2^6=64$ 种可能性，每增加一天，考虑的可能性是呈指数上升的，在这里，需要借助动态规划的思想。

step1：最后一天可能为Rain或者Sunny，因此，需要分别计算Sunny情况下Bob处于Happy的状态、Rain状态下Happy的状态，比较概率大小。

step 1
step 2：考虑最后一天是Sunny的情况下，倒数第二天是Sunny使Bob感觉Grumpy的概率以及倒数第二天是Rain使Bob感觉Grumpy的概率，选出概率最大的值。对于倒数第二天是Rain同样执行上述操作。

step 2
重复Step1 和Step2，直到状态完成。

Happy	Grumpy	Happy
Sunny： $PS_1=0.67$	Sunny : $PS_2$	Sunny : $PS_3$
Rain : $PR_1=0.33$	Rain $PR_2$	Rain : $PR_3$

$\begin {align} PS_2 =& max(init\_state\ from \ PS_1, init\_state\ from\ PR_1) \\ =& max(0.8*0.67*0.8*0.2, 0.4*0.33*0.4*0.2) \\\\ PR_3 =& max(init\_state\ from \ PS_2, init\_state\ from\ PR_2) \\ \end {align}$

2.3.2 案例代码（Viterbi Algorithm）

# 根据图中定义天气之间状态转移概率(transition probability)
Weather2Weather_Prob = {
    'sunny': {
        'sunny': 0.8,
        'rain': 0.2
    },
    'rain': {
        'sunny': 0.4,
        'rain': 0.6
    }
}
# 定义发射概率(emission probability)

Mood2Weather_Prob = {
    'happy': {
        'sunny': 0.8,
        'rain': 0.4,
    },
    'grumpy': {
        'sunny': 0.2,
        'rain': 0.6
    }

}

weather_state = ['sunny', 'rain']
mood_state = ['happy', 'grumpy']

# 初始化两种天气的概率
sunny_init_prob = 2/3
rain_init_prob = 1/3

def predictMood(BobMood):
    weather = {}
    weather_prob = {}
    # 定义概率矩阵
    for iday in range(len(BobMood)+1):
        weather_prob[iday] = {
            'sunny': 0,
            'rain': 0
        }
    weather_prob[0] = {
        'sunny': sunny_init_prob,
        'rain': rain_init_prob
    }
    # 根据Bob的心情，计算每一天可能的概率
    for iday, iday_mood in enumerate(BobMood):
        # 考虑当前天气的状态数量
        for icurrent_weather_state in weather_state:
            weather_prob[iday][icurrent_weather_state] *= Mood2Weather_Prob[iday_mood][icurrent_weather_state]
            # 考虑状态转移之后的概率
            for ifuture_weather_state in weather_state:
                weather_prob[iday+1][ifuture_weather_state] = max(
                    weather_prob[iday][icurrent_weather_state] * Weather2Weather_Prob[icurrent_weather_state][ifuture_weather_state],
                    weather_prob[iday + 1][ifuture_weather_state]
                )

        weather[iday] = 'sunny' if weather_prob[iday]['sunny'] > weather_prob[iday]['rain'] else 'rain'

    return weather, weather_prob

if __name__ == '__main__':


    BobMood = ['happy', 'happy', 'grumpy', 'grumpy', 'grumpy', 'happy']

    weather, weather_prob = predictMood(BobMood)
    print('weather is:')
    print(weather)

    print('probabilities are:')
    print(weather_prob)

3. 隐马尔科夫的科学推导

3.1 基本概念

状态序列：对应上图中的 $y$
观测序列：对应上图中的 $x$
一个时刻：序列的每一个位置，对应上图中的 $i$

在“如果Bob的心情是“Happy-Happy-Grumpy-Grumpy-Grumpy-Happy”问最后一天的天气？”中：
观测序列就是Bob的心情，状态序列就是天气。

隐马尔可夫模型的形式定义：

$Q$ 对应上例中的天气， $V$ 对应上例中的心情。 $N=2 \ (Sunny、Rain)$ ， $M=2 (Happy、Grumpy)$

$I=[S, S, S, S, R, R, R, S, S, S, S, R, R, S, S]$ ：15天的天气序列， $O=[G, H, H, H, G, G, H, G, H, H, H, G, H, H, H]$ ：15天中Bob的心情序列。

状态转移矩阵 $A$ （可根据图3列出）
$p(i+1=S|i=S) = 0.8\\ p(i+1=R|i=S) = 0.2\\ p(i+1=S|i=R) = 0.4\\ p(i+1=R|i=R) = 0.6\\ A=\begin{bmatrix} 0.8& 0.2\\ 0.4& 0.6 \end{bmatrix}$

观测概率矩阵 $A$ （可根据图4列出）
$p(o=H|i=S) = 0.8\\ p(o=G|i=S) = 0.2\\ p(o=H|i=R) = 0.4\\ p(o=G|i=R) = 0.6\\ A=\begin{bmatrix} 0.8& 0.2\\ 0.4& 0.6 \end{bmatrix}$

初始状态概率向量 $\pi_i$ （问题1）：有 $\pi_S=2/3$ ， $\pi_R=1/3$ 。

3.2 隐马尔可夫的前提

4. 马尔科夫的应用

Alice根据Bob心情预测天气的例子就是问题3——预测问题。

4.1 概率计算问题

通过一道简单例题说明：

《统计学习方法》P177

4.1.1 前向算法

代表，在时刻，观测序列是：红1（第一颗红球），且盒子1是白球的概率。

分为以下几个步骤：

1. 通过观测概率矩阵计算第一个观测数据来自不同状态的前向概率。

在 $t_1$ 时刻，红球的概率为

box at $t_1$	probability
1（盒子1是红球的概率）	$0.2*0.5=0.1$
2（盒子2是红球的概率）	$0.4*0.4=0.16$
3（盒子3是红球的概率）	$0.4*0.7=0.28$

2. 通过转移概率矩阵计算生成下一状态的概率，再通过观测概率矩阵计算生成下一个观测值的概率

在 $t_2$ 时刻，3个盒子转移到不同盒子的概率以及生成白球的概率如下表所示。

box at $t_2$	trans_probability
1（三个盒子的红球转换到盒子1的概率）	$0.10.5+0.160.3+0.28*0.2=0.154$
2（三个盒子的红球转换到盒子2的概率）	$0.10.2+0.160.5+0.28*0.3=0.184$
3（三个盒子的红球转换到盒子3的概率）	$0.10.3+0.160.2+0.28*0.5=0.202$

box at $t_2$	probability
1（盒子1产生红球的概率）	$0.154*0.5=0.077$
2（盒子2产生红球的概率）	$0.184*0.6=0.1104$
3（盒子3产生红球的概率）	$0.202*0.3=0.0606$

3. 重复步骤2，直到观测序列终止。

4. 将最后的概率值相加。

完整过程如下：

4.1.2 后向计算

从后往前考虑：

$\beta_1(1)$ 代表，在 $t_1$ 时刻，在盒子1是红球的条件的情况下，观测序列是：白，红2（第二颗红球）的概率。

1. 最后一个观测数据已经确定，所以初始化三个状态的概率为1。

在 $t_{T}$ 时刻

box at $t_T$	probability
1（盒子1是红球的条件下，观测序列为[空]的概率）	$1$
2（盒子2是红球的条件下，观测序列为[空]的概率）	$1$
3（盒子3是红球的条件下，观测序列为[空]的概率）	$1$

通过观测概率矩阵计算指定观测数据的概率（上表的另一种理解方法）

box at $t_{T}$	color_probability
1 （从盒子1中选一个球，观测序列为空的概率，即选中红球的概率）	$1*0.5=0.5$
2 （从盒子2中选一个球，观测序列为空的概率，即选中红球的概率）	$1*0.4=0.4$
3 （从盒子3中选一个球，观测序列为空的概率，即选中红球的概率）	$1*0.7=0.7$

2. 再计算转移到不同状态的概率。

在 $t_{T-1}$ 时刻

box at $t_{T-1}$	probability
1 （在 $T-1$ 时刻，对于盒子1而言，需要考虑 $T$ 时刻盒子1转移到盒子1,2,3的概率）	$0.50.5+0.40.2 + 0.7*0.3=0.54$
2 （在 $T-1$ 时刻，对于盒子2而言，需要考虑 $T$ 时刻盒子2转移到盒子1,2,3的概率）	$0.50.3+0.40.5 + 0.7*0.2=0.49$
3 （在 $T-1$ 时刻，对于盒子3而言，需要考虑 $T$ 时刻盒子3转移到盒子1,2,3的概率）	$0.50.2+0.40.3 + 0.7*0.5=0.57$

每一个盒子的概率和的意义为：该盒子是白球的条件下，观测序列为[红球]的概率

3. 重复步骤2，直到观测序列终止。

4. 最后一步将转移概率替换成初始概率，求和即可。

4.1.3 前、后项概率的关系

给定模型参数 $\lambda$ 和观测 $O$ ，在时刻 $t$ 处于状态 $q_i$ 的概率记为：
$\begin{align} \gamma_t(i)=&P(i_t=q_i|O; \lambda)\\ =&\frac{P(i_t=q_i,O; \lambda)}{P(O;\lambda)}\\ =&\frac{P(O|i_t=q_i; \lambda)P(i_t=q_i;\lambda)}{P(O;\lambda)}\\ =&\frac{P(O_1,O_2,...,O_t,O_{t+1},...,O_{T}|i_t=q_i; \lambda)P(i_t=q_i;\lambda)}{P(O;\lambda)}\\ =&\frac{P(O_1,O_2,...,O_t|i_t=q_i; \lambda)P(O_{t+1},...,O_{T}|i_t=q_i; \lambda)P(i_t=q_i;\lambda)}{P(O;\lambda)}\\ =&\frac{P(O_1,O_2,...,O_t,i_t=q_i; \lambda)P(O_{t+1},...,O_{T}|i_t=q_i; \lambda)}{P(O;\lambda)}\\ =&\frac{\alpha_t(i)\beta_t(i)}{P(O;\lambda)}\\ =&\frac{\alpha_t(i)\beta_t(i)}{\sum_{i=1}^{N}\alpha_t(i)\beta_t(i)}\tag{4.1} \end{align}$

4.2 学习算法

在学习算法中，分为监督学习和非监督学习。

4.2.1 监督学习

基本概念

当训练集中包括了观测序列和状态序列时，可采用监督学习的方法对参数值进行估计。

状态转移矩阵的估计：
观测概率矩阵的估计：

image.png
初始状态概率的估计：

具体例子

本文第3节“隐马尔科夫的科学推导” 之“3.1 基本概念” 中“隐马尔可夫模型的形式定义”下方的Bob心情与天气的例子。

4.2.2 非监督学习

当训练集仅包括观测序列，目标是学习估计马尔科夫的参数（状态转移矩阵，观测概率矩阵以及初始概率）
此时，将观测序列看做是观测数据 $O$ ，状态序列看做是隐变量 $I$ 借助EM模型即可求解。

4.3 预测算法

4.3.1 Viterbi算法

具体例子见本文2.3节：Viterbi 算法

5. 参考文献

《统计学习方法》
参考地址

概率图模型(1)——马尔可夫链

1. 定义

2. 案例

2.1 模型准备

2.2 考虑三个问题：

Question 1：如果随机选一天，Alice没从Bob那得到任何消息，那这天是晴天还是下雨天？

Question 2：如果Bob今天很开心，那么是晴天和雨天的概率各是多少？

Question 3：连续三天Bob的心情是Happy-Grumpy-Happy，最后一天是什么天气？

2.3 Viterbi 算法：

如果Bob的心情是“Happy-Happy-Grumpy-Grumpy-Grumpy-Happy”问最后一天的天气？

2.3.1 思路

2.3.2 案例代码（Viterbi Algorithm）

3. 隐马尔科夫的科学推导

3.1 基本概念

状态序列：对应上图中的

观测序列：对应上图中的

一个时刻：序列的每一个位置，对应上图中的

隐马尔可夫模型的形式定义：

3.2 隐马尔可夫的前提

4. 马尔科夫的应用

4.1 概率计算问题

4.1.1 前向算法

1. 通过 观测概率矩阵 计算第一个 观测数据 来自不同 状态 的前向概率。

2. 通过 转移概率矩阵 计算生成下一 状态 的概率，再通过 观测概率矩阵 计算生成下一个 观测值 的概率

3. 重复步骤2，直到 观测序列 终止。

4. 将最后的概率值相加。

4.1.2 后向计算

1. 最后一个 观测数据 已经确定，所以初始化三个 状态 的概率为1。

通过 观测概率矩阵 计算 指定观测数据 的概率（上表的另一种理解方法）

2. 再计算转移到不同 状态 的概率 。

3. 重复步骤2，直到观测序列终止。

4. 最后一步将转移概率替换成初始概率，求和即可。

4.1.3 前、后项概率的关系

4.2 学习算法

4.2.1 监督学习

基本概念

具体例子

4.2.2 非监督学习

4.3 预测算法

4.3.1 Viterbi算法

5. 参考文献

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

状态序列：对应上图中的 $y$

观测序列：对应上图中的 $x$

一个时刻：序列的每一个位置，对应上图中的 $i$

1. 通过观测概率矩阵计算第一个观测数据来自不同状态的前向概率。

2. 通过转移概率矩阵计算生成下一状态的概率，再通过观测概率矩阵计算生成下一个观测值的概率

3. 重复步骤2，直到观测序列终止。

1. 最后一个观测数据已经确定，所以初始化三个状态的概率为1。

通过观测概率矩阵计算指定观测数据的概率（上表的另一种理解方法）

2. 再计算转移到不同状态的概率。