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

2,198 阅读7分钟

思维导图




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中可能:

  1. Sunny - Sunny - Sunny
  2. Sunny - Sunny - Rain
  3. Sunny - Rain - Sunny
  4. Sunny - Rain - Rain
  5. Rain - Rain - Rain
  6. Rain - Rain - Sunny
  7. Rain - Sunny - Rain
  8. 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 前向算法

\alpha_2(1)代表,在t_2时刻,观测序列是:红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.1*0.5+0.16*0.3+0.28*0.2=0.154
2(三个盒子的红球转换到盒子2的概率) 0.1*0.2+0.16*0.5+0.28*0.3=0.184
3(三个盒子的红球转换到盒子3的概率) 0.1*0.3+0.16*0.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.5*0.5+0.4*0.2 + 0.7*0.3=0.54
2 (在T-1时刻,对于盒子2而言,需要考虑T时刻盒子2转移到盒子1,2,3的概率) 0.5*0.3+0.4*0.5 + 0.7*0.2=0.49
3 (在T-1时刻,对于盒子3而言,需要考虑T时刻盒子3转移到盒子1,2,3的概率) 0.5*0.2+0.4*0.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. 参考文献