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

思维导图



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 前向算法


代表,在时刻,观测序列是:红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. 参考文献

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 151,829评论 1 331
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 64,603评论 1 273
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 101,846评论 0 226
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 42,600评论 0 191
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 50,780评论 3 272
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 39,695评论 1 192
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 31,136评论 2 293
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 29,862评论 0 182
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 33,453评论 0 229
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 29,942评论 2 233
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 31,347评论 1 242
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 27,790评论 2 236
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 32,293评论 3 221
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 25,839评论 0 8
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 26,448评论 0 181
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 34,564评论 2 249
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 34,623评论 2 249

推荐阅读更多精彩内容

  • 你是不是经常会感受到你的孩子一直会黏着你,特别是当到了一个陌生的环境,遇到了陌生人? 有的时候甚至是你的家人都没办...
    凯老师的凯阅读 833评论 0 0
  • 20180220,大年初五,假期即将结束。 广东天气又开始转热,没有了那股股寒气,很是温暖。今天与麦生之间发生了一...
    YC_小拉阅读 363评论 0 0
  • 凤落峪阅读 167评论 1 1
  • 一问简书,平台高筑,吸引无数帅哥美女! 二问简书,诗词歌赋,膳食故事传奇载体。 三问简书,非男即女,如此吸引各路大...
    冲天农锄草阅读 1,832评论 139 325
  • 文/香梅 考试于我,不过一纸;于他人,却成了命。 努力为何,若是喜欢就成了欢喜,若是不喜欢便成了痛苦。 随着期末的...
    烟雨梅花阅读 360评论 5 3