📖机器学习｜隐马尔可夫模型

2024-7-6|2024-8-19
黎明
黎明
type
status
date
slug
summary
tags
category
icon
password
进度
 
HMM解决什么问题 🤔不足之处专业俗语 📖马尔可夫链马尔可夫模型两个假设三个基本问题参考文章 🔗

HMM解决什么问题 🤔

隐马尔可夫模型是一种统计模型，该模型帮助我们分析、理解包含潜在状态信息的序列数据。比如语音识别、手写字符识别和自然语言处理等场景。
  • 语音识别：信号是连续的时间序列，潜在状态信息是音素，英文音素比如音标，中文音素比如拼音。
  • 手写字符识别：手写字符看作笔画的时间序列，潜在状态信息是顺序和形状等。
 

不足之处

  • 观察值间严格独立，无记忆
  • 状态转移仅依赖前一状态（一阶马尔科夫）
  • 状态转移方向性问题可能会导致无限循环
 

专业俗语 📖

  • 隐马尔可夫模型 HMM Hidden Markov Model
  • 马尔可夫链 Markov Chain
  • 前向-后向算法 forward-backward algorithm
  • 无记忆 memory-less
  • 服从于 subject to(s.t.)
  • 动态规划 dynamic programming
  • 维特比算法 viterbi algorithm
 

马尔可夫链

随机变量序列; 表示时刻的随机变量
 
状态空间
notion image
 
假设的随机变量遵循概率分布，称为初始状态分布。在某个时刻的随机变量与前一个时刻的随机变量之间有条件分布。如果只依赖于,而不是依赖于过去的随机变量，即
这一个性质称为马尔可夫性；具备马尔可夫性的随机序列称为马尔可夫链。
这一个性质称为马尔可夫性；具备马尔可夫性的随机序列称为马尔可夫链。
 
若马尔可夫链在时刻处于状态，在时刻移动到状态。将转移概率记作：
状态本身或者状态下标可以将其表示成形式
满足：
马尔可夫链的转移概率可以由矩阵表示:
矩阵列元素之和为1
notion image
令：马尔可夫链在时刻的概率为
表示时刻状态为的概率，即：
表示时刻状态为的概率，即：
特别地，马尔可夫链的初始状态分布：
 

马尔可夫模型

马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由每个状态随机序列生产观测随机序列。如图所示：
 
分析：
 
状态序列
隐:表示无法被观测到
马尔可夫链:满足马尔可夫性
 
观察序列
可被直接观测
 
设：是所有状态的集合，是所有观测的集合。
已知:
状态转移矩阵：在时刻处于状态的条件下，在时刻转移到状态的概率。
观测概率矩阵：在时刻处于状态的条件下，在时刻生成观测的概率。
初始概率分布：在时刻处于状态的概率。
马尔可夫模型参数，；
马尔可夫模型参数，；

两个假设

齐次马尔可夫假设：隐藏的马尔可夫链在任意时刻的状态只依赖时刻的状态，与其他时刻的状态、观测和时刻无关。
观测独立性假设：任何时刻的观测只依赖该时刻的马尔可夫链的状态，与其他时刻的状态和观测无关。

三个基本问题

概率计算：给定模型和观察序列，计算在条件下出现的概率？
概率计算：给定模型和观察序列，计算在条件下出现的概率？
其中：
化简得：
使用齐次马尔可夫假设：
化简得：
服从状态转移矩阵
即：
化简得：
使用观察独立假设:
化简得：
服从发射矩阵
由可知：
注意：，暴力计算概率的时间复杂度是指数级：
 
级别的算法可不行，为提升效率，提出前向-后向算法。
📖 前向概率：给定模型参数,定义时刻部分观察序列且状态是的概率。
前向概率定义:
 
🤔那么?
即：
则：
📖 后向概率：给定模型参数,定义时刻后部分观察序列且状态是的概率
后向概率定义:
 
 
🤔那么?
即：
则：
化简得：
结合前向概率和后向概率，得：
化简得：
算法复杂度(平方级):
page icon
学习问题：观察序列，估计模型参数，使得在该模型下出现的概率最大？
BW算法(EM算法)
参数替换
即：
注意是关于的函数，是常量。
由得:
由和可得：
即:
其中：，则：
将带入得：
化简得：
求解的问题：
由可知：
边缘概率公式:
利用拉格朗日乘子法，写出拉格朗日函数
令求偏导等于求极值，即M步。
函数导数公示：; 本文中
化简得：
将带入得：
即：
同理，由可知，，即：
利用拉格朗日乘子法，写出拉格朗日函数
由带入得：
同理，由可知，
利用拉格朗日乘子法，写出拉格朗日函数
注意，满足 。将代入得：
综上所述：由可知：
利用前向概率和后向概率，定义单状态和两个状态概率的计算公式。
  1. 给定模型和观测，在时刻处于的概率为。
  1. 给定模型和观测，在时刻处于且在时刻处于得概率为。
求解
 
由前向概率和后向概率定义可知：
求解
由前向概率、后向概率定义、状态转移矩阵和发射矩阵可知：
 
整列和可知：
 
预测问题（解码问题）：给定模型和观察序列，求在条件概率下最大的状态序列？
预测问题（解码问题）：给定模型和观察序列，求在条件概率下最大的状态序列？
维特比算法通过动态规划解决解码问题，即解决最大概率路径（最优路径）。
假设：
  1. 最优路径
  1. 在时刻通过节点
结论：
根据动态规划原理，一定是 → 所有路径中最优的。
反证法：
若 不是 → 所有路径中最优的，
则存在使得 → 是最优路径，
那么比更优路径
则与动态规划原理矛盾
 
根据以上原理，只需从时刻，递推计算各路径概率最大值，直到。
 
记表示时，所有单个路径中概率最大值：
那么 🤔?
即：
记表示时，所有单个路径中最大概率路径的第个节点：
个人理解：求解 → 最大概率的
输入： 和
输出：
  1. 初始化
    1. 递推
      1. 终止
        1. 回遡
          1. 最优路径
             

            参考文章 🔗

            深度学习
            机器学习｜EM算法中间件｜Redis
            Loading...