隐马尔科夫模型(HMM)详解

马尔科夫过程马尔科夫过程 马尔科夫过程可以看做是一个自动机 以一定的概率在各个状态之间跳转 考虑一个系统 在每个时刻都可能处于 N 个状态中的一个 N 个状态集合 是 S1 S2 S3 SN 我们现在用 q1 q2 q3 qn来表示系统在 t 1 2 3 n 时刻下的 状态 在 t 1 时 系统所在的状态 q 取决于一个初始概率分布 PI PI SN 表示 t 1 时系统状态为 SN的概率 马尔科夫模型有两个假设 1 系统在时刻 t 的状态只与时刻 t 1 处的状态相关 也称为无后效性 2 状态转移概率与时间无关 也称为齐次性或时齐性 第一条具体可以用如下公式表示 P qt Sj qt 1 Si qt 2 Sk P qt Sj qt 1 Si 其中 t 为大于 1 的任意数值 Sk为任意状态 第二个假设则可以用如下公式表示 P qt Sj qt 1 Si P qk Sj qk 1 Si 其中 k 为任意时刻 下图是一个马尔科夫过程的样例图 可以把状态转移概率用矩阵 A 表示 矩阵的行列长度均为状态数目 aij表 示 P Si Si 1 隐马尔科夫过程隐马尔科夫过程 与马尔科夫相比 隐马尔科夫模型则是双重随机过程 不仅状态转移之间 是个随机事件 状态和输出之间也是一个随机过程 如下图所示 此图是从别处找来的 可能符号与我之前描述马尔科夫时不同 相信 大家也能理解 该图分为上下两行 上面那行就是一个马尔科夫转移过程 下面这一行则 是输出 即我们可以观察到的值 现在 我们将上面那行的马尔科夫转移过程 中的状态称为隐藏状态 下面的观察到的值称为观察状态 观察状态的集合表 示为 O O1 O2 O3 OM 相应的 隐马尔科夫也比马尔科夫多了一个假设 即输出仅与当前状态有 关 可以用如下公式表示 P O1 O2 Ot S1 S2 St P O1 S1 P O2 S2 P Ot St 其中 O1 O2 Ot为从时刻 1 到时刻 t 的观测状态序列 S1 S2 St则为隐 藏状态序列 另外 该假设又称为输出独立性假设 举个例子举个例子 举个常见的例子来引出下文 同时方便大家理解 比如我在不同天气状态 下去做一些事情的概率不同 天气状态集合为 下雨 阴天 晴天 事情集合 为 宅着 自习 游玩 假如我们已经有了转移概率和输出概率 即 P 天气 A 天气 B 和 P 事情 a 天气 A 的概率都已知道 那么则有几个问题要问 注意 假 设一天我那几件事情中的一件 1 假如一周内的天气变化是 下雨 晴天 阴天 下雨 阴天 晴天 阴 天 那么我这一周 自习 宅着 游玩 自习 游玩 宅着 自习的概率是多大 2 假如我这一周做事序列是 自习 宅着 游玩 自习 游玩 宅着 自习 不知道天气状态的情况下这个做事序列的概率是多大 3 假如一周内的天气变化是 下雨 晴天 阴天 下雨 阴天 晴天 阴天 那我们这一周最有可能的做事序列是什么 4 假如我这一周做事序列是 自习 宅着 游玩 自习 游玩 宅着 自习 那么这一周的天气变化序列最有可能是什么 对于第一个问题 我想大家应该都能很快知道怎么算 啥 不知道 答 案在本文最后 隐马模型基本要素及基本三问题隐马模型基本要素及基本三问题 综上所述 我们可以得到隐马尔科夫的基本要素 即一个五元组 S N A B PI S 隐藏状态集合 N 观察状态集合 A 隐藏状态间的转移概率矩阵 B 输出矩阵 即隐藏状态到输出状态的概率 PI 初始概率分布 隐藏状态的初始概率分布 其中 A B PI 称为隐马尔科夫的参数 用 X 表示 由上述问题可以引出隐马尔科夫的三个基本问题的其中两个 下文中为了 简便 将隐马尔科夫模型简称为 HMM Hiden Markov Model HMM 的三个基本问题是 1 给定模型 五元组 求某个观察序列给定模型 五元组 求某个观察序列 O 的概率 样例问题的概率 样例问题 2 即已知模型参数 计算某一特定输出序列的概率 通常使用 forward 算 法解决 2 给定模型和观察序列给定模型和观察序列 O 求可能性最大的隐藏状态序列 样例问题 求可能性最大的隐藏状态序列 样例问题 4 即已知模型参数 寻找最可能的能产生某一特定输出序列的隐含状态 的序列 通常使用 Viterbi 算法解决 3 对于给定的观察序列对于给定的观察序列 O 调整 调整 HMM 的参数 使观察序列出现的概率的参数 使观察序列出现的概率 最大 最大 即已知输出序列 寻找最可能的状态转移以及输出概率 通 常使用 Baum Welch 算法以及 Reversed Viterbi 算法解决 前向算法前向算法 对于第一个基本问题 计算公式为 即对于观察序列 O 我们需要找出所有可能的隐藏状态序列 S 计算出在 给定模型下 S 输出为 O 的概率 就是样例问题一啊 然后计算概率之和 直观上看 假如序列 O 的长度为 T 模型的隐藏状态集合大小为 N 那么 一共有 NT个可能的隐藏状态序列 计算复杂度极高 O NT 暴力算法太慢了 解决方案就是动态规划 Dynamic Programming 假设观察序列为 O1 O2 O3 Ot 在时刻 i 1 i t 时 定义 C 为产生序 列 O1 O2 Oi且 Si Sk的概率 其中 Sk为任意一个隐藏状态值 则 C i 1 Sr 的计算公式为 其中 Sr为任意一个隐藏状态值 A 为转移概率 B 为隐藏状态到观察状 态的概率 为了便于理解 还是看图 C 3 下雨 考虑了 t 1 和 t 2 的所有组合情况 同时也是 C 4 下雨 阴天 晴天 的子问题 C 3 阴天 和 C 3 晴天 也是如此计算 而 C i 1 Sr 计算公式则可以表 示成 由图知 C 4 阴天 C 3 下雨 A 下雨 阴天 C 3 阴天 A 阴天 阴天 C 3 晴天 A 晴天 阴天 B 阴天 自习 通过图片 大家应该能直观的理解该算法了 该算法又称为前向算法 那 还有后向算法 是的 后向算法就是这个算法倒过来嘛 也是动态规划 这里 就不赘述了 有兴趣的看参考文献 另外 这里没有讲解如何初始化概率 也 可以去参考文献里查证 维特比算法维特比算法 现在 HMM 的第一个基本问题解决了 下面开始解决第二个问题 第二 个问题又称为解码问题 同样的 暴力算法是计算所有可能性的概率 然后找 出拥有最大概率值的隐藏状态序列 与问题一的暴力解决方案类似 复杂度为 O NT 那应该用什么方案呢 毫无疑问 还是动态规划啊 假设观察序列为 O1 O2 O3 Ot 在时刻 i 1 i 2 时 节点中保存着一些小节点 这些小节点的数目即为上一个状态的状态 数目 小节点的值意义为到达该时刻状态为 Sr且前一时刻状态为 Sk时能够产生 状态序列的最大概率 比如背景为绿色的小节点的值的意义为时刻 3 为下雨 时刻 2 为下雨时去自习 宅着 游玩的最大概率 注意 节点表示时刻 i 时某 个状态 小节点表示节点中保存的前一状态的节点 比如绿色的那个节点 对于时刻 i i 2 每个小节点的概率为 那么对于时刻 i 1 小节点的概率为 然后 从时刻 t 中寻找最大的小节点回溯即可 样例问题一答案样例问题一答案 上面样例问题中第一问的答案是 概率 P P 下雨 P 晴天 下雨 P 阴天 晴天 P 自习 下雨 P 宅着 晴天 P 自习 阴天 注