首页 > 编程语言 >机器学习算法原理实现——HMM生成序列和维特比算法

机器学习算法原理实现——HMM生成序列和维特比算法

时间:2023-11-16 12:01:54浏览次数:44  
标签:状态 概率 probability 维特 states HMM 算法 发烧 健康

【HMM基本概念】

隐马尔可夫模型(Hidden Markov Model,HMM)是一种统计模型,用于描述一个含有未知参数(隐状态)的马尔可夫过程。在HMM中,我们不能直接观察到状态,但可以观察到每个状态产生的一些相关数据(观测值)。HMM的目标是,给定观测序列,估计出最可能的状态序列。

HMM的基本假设有两个(见例子的图):
1. 齐次马尔可夫性假设:即任意时刻的状态只与前一时刻的状态有关,与其他时刻状态及观测无关。
2. 观测独立性假设:即任意时刻的观测只与该时刻的状态有关,与其他观测和状态无关。

【举一个例子】

举一个日常生活中的例子,我们希望根据当前天气的情况来预测未来天气情况。一种办法就是假设这个模型的每个状态都只依赖于前一个的状态,即马尔科夫假设,这个假设可以极大简化这个问题。当然,这个例子也是有些不合实际的。但是,这样一个简化的系统可以有利于我们的分析,所以我们通常接受这样的假设,因为我们知道这样的系统能让我们获得一些有用的信息,尽管不是十分准确的。

机器学习算法原理实现——HMM生成序列和维特比算法_状态转移

上面的图显示了天气进行转移的模型。天气类型为三种:sunny, cloudy, rainy,
注意一个含有N个状态的一阶过程有N²个状态转移。每一个转移的概率叫做状态转移概率,就是从一个状态转移到另一个状态的概率。这所有的N²个概率可以用一个状态转移矩阵来表示,上面天气例子的状态转移矩阵如下:

[[0.5, 0.375, 0.125],

[0.25, 0.125, 0.625],

[0.25, 0.375, 0.375]]

机器学习算法原理实现——HMM生成序列和维特比算法_状态转移_02

这个矩阵表示,如果昨天是阴天,那么今天有25%的可能是晴天,12.5%的概率是阴天,62.5%的概率会下雨,很明显,矩阵中每一行的和都是1。
为了初始化这样一个系统,我们需要一个初始的概率向量:

[1.0, 0.0, 0.0]

机器学习算法原理实现——HMM生成序列和维特比算法_初始状态_03

这个向量表示第一天是晴天。到这里,我们就为上面的一阶马尔科夫过程定义了以下三个部分:

  1. 状态:晴天、阴天和下雨。
  2. 初始向量:定义系统在时间为0的时候的状态的概率。
  3. 状态转移矩阵:每种天气转换的概率。所有的能被这样描述的系统都是一个马尔科夫过程

然而,当马尔科夫过程不够强大的时候,我们又该怎么办呢?在某些情况下,马尔科夫过程不足以描述我们希望发现的模式。
比如我们的股市,如果只是观测市场,我们只能知道当天的价格、成交量等信息,但是并不知道当前股市处于什么样的状态(牛市、熊市、震荡、反弹等等),在这种情况下我们有两个状态集合,一个可以观察到的状态集合(股市价格成交量状态等)和一个隐藏的状态集合(股市状况)。我们希望能找到一个算法可以根据股市价格成交量状况和马尔科夫假设来预测股市的状况。
在上面的这些情况下,可以观察到的状态序列和隐藏的状态序列是概率相关的。于是我们可以将这种类型的过程建模为有一个隐藏的马尔科夫过程和一个与这个隐藏马尔科夫过程概率相关的并且可以观察到的状态集合,就是隐马尔可夫模型
隐马尔可夫模型(Hidden Markov Model) 是一种统计模型,用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数,然后利用这些参数来作进一步的分析。下图是一个三个状态的隐马尔可夫模型状态转移图,其中x表示隐含状态,y表示可观察的输出,a表示状态转换概率,b表示输出概率(也就是观测概率,见第二个例子,y仅仅和当前状态x有关)。

机器学习算法原理实现——HMM生成序列和维特比算法_概率分布_04

 

 

 

隐马尔可夫模型(HMM)的观测序列生成是指根据模型的参数(初始状态概率、状态转移概率和观测概率)生成一系列的观测数据。
具体步骤如下:
1. 根据初始状态概率分布选择一个初始状态。
2. 根据当前状态的观测概率分布生成一个观测数据。
3. 根据当前状态的状态转移概率分布选择下一个状态。
4. 重复步骤2和3,直到生成足够数量的观测数据。

 

一个HMM应用:根据当前天气的情况来预测未来天气情况
天气类型为三种:sunny, cloudy, rainy,
注意一个含有N个状态的一阶过程有N²个状态转移。每一个转移的概率叫做状态转移概率,就是从一个状态转移到另一个状态的概率。这所有的N²个概率可以用一个状态转移矩阵来表示,上面天气例子的状态转移矩阵如下:
[[0.5, 0.375, 0.125],
[0.25, 0.125, 0.625],
[0.25, 0.375, 0.375]]

这个矩阵表示,如果昨天是阴天,那么今天有25%的可能是晴天,12.5%的概率是阴天,62.5%的概率会下雨,很明显,矩阵中每一行的和都是1。
为了初始化这样一个系统,我们需要一个初始的概率向量:
[1.0, 0.0, 0.0]

这个向量表示第一天是晴天。到这里,我们就为上面的一阶马尔科夫过程定义了以下三个部分:
状态:晴天、阴天和下雨。
初始向量:定义系统在时间为0的时候的状态的概率。
状态转移矩阵:每种天气转换的概率。所有的能被这样描述的系统都是一个马尔科夫过程。

使用HMM预测未来5天的天气。给出python代码如下:

【python编码实现】

import numpy as np

# 状态集合
states = ('Sunny', 'Cloudy', 'Rainy')

# 初始状态概率
start_probability = np.array([1.0, 0.0, 0.0])

# 转移概率
transition_probability = np.array([
    [0.5, 0.375, 0.125],
    [0.25, 0.125, 0.625],
    [0.25, 0.375, 0.375]
])

def predict_weather(start_probability, transition_probability, days):
    # 初始化天气预测
    weather = np.random.choice(states, p=start_probability)
    prediction = [weather]

    # 根据转移概率预测未来的天气
    for i in range(days-1):
        weather = np.random.choice(states, p=transition_probability[states.index(weather)])
        prediction.append(weather)

    return prediction

# 预测未来5天的天气
print(predict_weather(start_probability, transition_probability, 5))

  

输出:

机器学习算法原理实现——HMM生成序列和维特比算法_初始状态_05

 ['Sunny', 'Sunny', 'Rainy', 'Rainy', 'Rainy']

 

上面这个例子没有观测概率这个,因为观测值是基于隐含变量的概率分布输出。

我们来一个有观测概率的例子。就是说y的输出依赖观测概率b1,而b1依赖隐藏变量x,

 

【再来一个例子】该例来自《统计学习方法》例10.1

python编程实现,hmm的算法应用:

假设有4个盒子,每个盒子里面都有红白两种颜色的球,各个盒子里面的红白球数量分布为观测概率矩阵,如下:
[[0.5, 0.5],  ==》例如,选择了盒子1,则红白球概率都是0.5
[0.6, 0.4],  ==》选择了盒子2,则红白球概率是0.6和0.4
[0.2, 0.8],
[0.3, 0.7]]  ==》无非就是选择了某一个盒子,则红白球的输出概率会改变!

从4个盒子里等概率地选择1个盒子,从这个盒子里随机摸一个球,记录颜色后放回。然后从当前盒子随机转移到下一个盒子,转移规则如下:如果当前盒子为1,那么下一个盒子一定是2;如果当前盒子是2或者3,则分别以概率0.4和0.6转移到左边或者右边的盒子;如果当前盒子是4,那么各以0.5的概率停留在4或者转移到3,确定了转移的盒子后,就从该盒子中随机摸取一个球记录其颜色并放回。

将上述摸球试验独立重复进行5次,得到一个球的观测序列为:[白, 红, 白, 红, 红]

按照HMM的三要素来分析该例子。在上述摸球过程中,我们只能观测到摸到的球的颜色,即可以观测到球的颜色序列,而观察不到球是从哪个盒子摸到的,即观测不到盒子的序列。所以,该例中状态序列即为盒子的序列,观测序列即为摸到的球的颜色序列,具体如下所示。

状态序列为:[盒子1, 盒子2, 盒子3, 盒子4]

观测序列为:[红球, 白球]

状态序列和观测序列长度5,初始概率分布为:[0.25, 0.25, 0.25, 0.25]

状态转移概率分布矩阵为:
[[0,1,0,0],
[0.4,0,0.6,0],
[0, 0.4, 0, 0.6],
[0, 0, 0.5, 0.5]]

根据前面的HMM理论和案例分析,生成其观测序列。

import numpy as np

# 状态集合
states = ('Box1', 'Box2', 'Box3', 'Box4')

# 观测集合
observations = ('Red', 'White')

# 初始状态概率
start_probability = np.array([0.25, 0.25, 0.25, 0.25])

# 状态转移概率
transition_probability = np.array([
    [0, 1, 0, 0],
    [0.4, 0, 0.6, 0],
    [0, 0.4, 0, 0.6],
    [0, 0, 0.5, 0.5]
])

# 观测概率
emission_probability = np.array([
    [0.5, 0.5],
    [0.6, 0.4],
    [0.2, 0.8],
    [0.3, 0.7]
])

def generate_sequence(start_probability, transition_probability, emission_probability, length):
    # 初始化状态和观测
    state = np.random.choice(states, p=start_probability)
    observation = np.random.choice(observations, p=emission_probability[states.index(state)])
    states_sequence = [state]
    observations_sequence = [observation]

    # 根据状态转移概率和观测概率生成序列
    for i in range(length-1):
        state = np.random.choice(states, p=transition_probability[states.index(state)])
        observation = np.random.choice(observations, p=emission_probability[states.index(state)])
        states_sequence.append(state)
        observations_sequence.append(observation)

    return states_sequence, observations_sequence

# 生成长度为5的状态序列和观测序列
states_sequence, observations_sequence = generate_sequence(start_probability, transition_probability, emission_probability, 5)
print('States Sequence: ', states_sequence)
print('Observations Sequence: ', observations_sequence)

  

输出:

States Sequence:  ['Box4', 'Box3', 'Box2', 'Box3', 'Box2']

Observations Sequence:  ['White', 'White', 'Red', 'White', 'Red']

 

【动态规划的维特比算法】

接下来是维特比算法了,先举一个通俗的例子:

尝试用高中概率知识去理解一下 Veterbi 算法。内容绝对粗浅,100% 抄袭,欢迎指正。用一个别人家的栗子来说一下。

1.题目背景:

从前有个村儿,村里的人的身体情况只有两种可能:健康或者发烧。
假设这个村儿的人没有体温计或者百度这种神奇东西,他唯一判断他身体情况的途径就是到村头我的偶像金正月的小诊所询问。
月儿通过询问村民的感觉,判断她的病情,再假设村民只会回答正常、头晕或冷。
有一天村里奥巴驴就去月儿那去询问了。
第一天她告诉月儿她感觉正常。
第二天她告诉月儿感觉有点冷。
第三天她告诉月儿感觉有点头晕。
那么问题来了,月儿如何根据阿驴的描述的情况,推断出这三天中阿驴的一个身体状态呢?
为此月儿上百度搜 google ,一番狂搜,发现维特比算法正好能解决这个问题。月儿乐了。

 

2.已知情况:

隐含的身体状态 = { 健康 , 发烧 }

可观察的感觉状态 = { 正常 , 冷 , 头晕 }

月儿预判的阿驴身体状态的概率分布 = { 健康:0.6 , 发烧: 0.4 }

月儿认为的阿驴身体健康状态的转换概率分布 = {
健康->健康: 0.7 ,
健康->发烧: 0.3 ,
发烧->健康:0.4 ,
发烧->发烧: 0.6
}

月儿认为的在相应健康状况条件下,阿驴的感觉的概率分布 = {
健康,正常:0.5 ,冷 :0.4 ,头晕: 0.1 ;
发烧,正常:0.1 ,冷 :0.3 ,头晕: 0.6
}
阿驴连续三天的身体感觉依次是: 正常、冷、头晕 。

 

3.题目:

已知如上,求:阿驴这三天的身体健康状态变化的过程是怎么样的?

 

4.过程:

根据 Viterbi 理论,后一天的状态会依赖前一天的状态和当前的可观察的状态。那么只要根据第一天的正常状态依次推算找出到达第三天头晕状态的最大的概率,就可以知道这三天的身体变化情况。
传不了图片,悲剧了。。。
1.初始情况:

  • P(健康) = 0.6,P(发烧)=0.4。

2.求第一天的身体情况:
计算在阿驴感觉正常的情况下最可能的身体状态。

  • P(今天健康) = P(正常|健康)*P(健康|初始情况) = 0.5 * 0.6 = 0.3
  • P(今天发烧) = P(正常|发烧)*P(发烧|初始情况) = 0.1 * 0.4 = 0.04

那么就可以认为第一天最可能的身体状态是:健康。
3.求第二天的身体状况:
计算在阿驴感觉冷的情况下最可能的身体状态。
那么第二天有四种情况,由于第一天的发烧或者健康转换到第二天的发烧或者健康。

  • P(前一天发烧,今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(冷|发烧) = 0.04 * 0.6 * 0.3 = 0.0072
  • P(前一天发烧,今天健康) = P(前一天发烧)*P(发烧->健康)*P(冷|健康) = 0.04 * 0.4 * 0.4 = 0.0064
  • P(前一天健康,今天健康) = P(前一天健康)*P(健康->健康)*P(冷|健康) = 0.3 * 0.7 * 0.4 = 0.084
  • P(前一天健康,今天发烧) = P(前一天健康)*P(健康->发烧)*P(冷|发烧) = 0.3 * 0.3 *.03 = 0.027

那么可以认为,第二天最可能的状态是:健康。
4.求第三天的身体状态:
计算在阿驴感觉头晕的情况下最可能的身体状态。

  • P(前一天发烧,今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(头晕|发烧) = 0.027 * 0.6 * 0.6 = 0.00972
  • P(前一天发烧,今天健康) = P(前一天发烧)*P(发烧->健康)*P(头晕|健康) = 0.027 * 0.4 * 0.1 = 0.00108
  • P(前一天健康,今天健康) = P(前一天健康)*P(健康->健康)*P(头晕|健康) = 0.084 * 0.7 * 0.1 = 0.00588
  • P(前一天健康,今天发烧) = P(前一天健康)*P(健康->发烧)*P(头晕|发烧) = 0.084 * 0.3 *0.6 = 0.01512

那么可以认为:第三天最可能的状态是发烧。

5.结论

根据如上计算。这样月儿断定,阿驴这三天身体变化的序列是:健康->健康->发烧。

 

维基百科的这个例子的动态图:File:Viterbi animated demo.gif

 

这个算法大概就是通过已知的可以观察到的序列,和一些已知的状态转换之间的概率情况,通过综合状态之间的转移概率和前一个状态的情况计算出概率最大的状态转换路径,从而推断出隐含状态的序列的情况。

 

【python编程实现】

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    for st in states:
        V[0][st] = {"prob": start_p[st] * emit_p[st][obs[0]], "prev": None}
    for t in range(1, len(obs)):
        V.append({})
        for st in states:
            max_tr_prob = max(V[t-1][prev_st]["prob"]*trans_p[prev_st][st] for prev_st in states)
            for prev_st in states:
                if V[t-1][prev_st]["prob"] * trans_p[prev_st][st] == max_tr_prob:
                    max_prob = max_tr_prob * emit_p[st][obs[t]]
                    V[t][st] = {"prob": max_prob, "prev": prev_st}
                    break
    opt = []
    max_prob = max(value["prob"] for value in V[-1].values())
    previous = None
    for st, data in V[-1].items():
        if data["prob"] == max_prob:
            opt.append(st)
            previous = st
            break
    for t in range(len(V) - 2, -1, -1):
        opt.insert(0, V[t + 1][previous]["prev"])
        previous = V[t + 1][previous]["prev"]
    return opt

states = ('健康', '发烧')
observations = ('正常', '冷', '头晕')
start_probability = {'健康': 0.6, '发烧': 0.4}
transition_probability = {
   '健康' : {'健康': 0.7, '发烧': 0.3},
   '发烧' : {'健康': 0.4, '发烧': 0.6},
   }
emission_probability = {
   '健康' : {'正常': 0.5, '冷': 0.4, '头晕': 0.1},
   '发烧' : {'正常': 0.1, '冷': 0.3, '头晕': 0.6},
   }

print(viterbi(observations, states, start_probability, transition_probability, emission_probability))

  

 输出:

['健康', '健康', '发烧']

 

就是一个dp算法+回溯求path的,不再赘述了! 

 



标签:状态,概率,probability,维特,states,HMM,算法,发烧,健康
From: https://blog.51cto.com/u_11908275/8416148

相关文章

  • 机器学习算法原理实现——EM算法
    【EM算法简介】EM算法,全称为期望最大化算法(Expectation-Maximization Algorithm),是一种迭代优化算法,主要用于含有隐变量的概率模型参数的估计。EM算法的基本思想是:如果给定模型的参数,那么可以根据模型计算出隐变量的期望值;反过来,如果给定隐变量的值,那么可以通过最大化似然函数来估......
  • 机器学习算法原理实现——朴素贝叶斯
    【先说条件概率】条件概率是指在某个事件发生的条件下,另一个事件发生的概率。以下是一个实际的例子:假设你有一副扑克牌(不包括大小王,共52张牌),你随机抽一张牌。我们设事件A为"抽到的牌是红色的"(红心和方块为红色,共26张),事件B为"抽到的牌是心"(红心共13张)。1.首先,我们可以计算事件A和事......
  • 机器学习算法原理实现——最大熵模型
    【写在前面】在sklearn库中,没有直接称为"最大熵模型"的类,但是有一个与之非常相似的模型,那就是LogisticRegression。逻辑回归模型可以被视为最大熵模型的一个特例,当问题是二分类问题,且特征函数是输入和输出的线性函数时,最大熵模型就等价于逻辑回归模型。【最大熵模型的原理】最大熵......
  • 算法刷题记录-哈希表
    算法刷题记录-哈希表有效的字母异位词给定两个字符串*s*和*t*,编写一个函数来判断*t*是否是*s*的字母异位词。注意:若*s*和*t*中每个字符出现的次数都相同,则称*s*和*t*互为字母异位词。示例1:输入:s="anagram",t="nagaram"输出:true示例2:输入:s......
  • KMeans算法全面解析与应用案例
    本文深入探讨了KMeans聚类算法的核心原理、实际应用、优缺点以及在文本聚类中的特殊用途,为您在聚类分析和自然语言处理方面提供有价值的见解和指导。关注TechLead,分享AI全维度知识。作者拥有10+年互联网服务架构、AI产品研发经验、团队管理经验,同济本复旦硕,复旦机器人智能实验......
  • 测试开发常见算法题
    1.冒泡排序deffaet_sort(test:list)->list:"""冒泡排序"""foriinrange(len(test)):forjinrange(len(test)-i-1):iftest[j]>test[j+1]:test[j],test[j+1]=test[j+1],te......
  • 算法~base64算法理解
    base64Base64是一种用于将二进制数据编码成ASCII字符的编码方式。它主要用于在文字环境中传输或存储二进制数据,如在电子邮件、XML文件、URL参数等。Base64编码不是一种加密算法,而是一种编码方式,其主要作用是将二进制数据转换为文本数据,以便更容易在文本协议中处理。Base64......
  • 对匈牙利算法的一些解释
    首先看蓝书上的代码为什么即将开始dfs时,没有一开始就把vis[i]标记了?其实dfs的流程是从左部的一个节点出发,考察右部的一个节点,如果右部的节点已经匹配了,下次dfs直接从这个右部节点的匹配点开始计算,所以vis的标记都是标记的右部节点,左部节点是不用标记的(因为是匹配二分图,只会被访......
  • 【路径规划】基于动态窗口法DWA算法的机器人动态避障路径规划研究附Matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。......
  • 【iOS逆向与安全】某茅台App算法分析还原
    1.目标某茅台软件的actParam算法分析还原。2.使用工具mac系统frida-ios-dump:砸壳已越狱iOS设备:脱壳及frida调试IDAPro:静态分析Charles:抓包工具ss:小火箭,配合Charles使用3.流程处理启动闪退在IDAPro搜索SVC得到如下函数列表:NOP掉sub_函数的最后一行汇编......