隐马尔可夫总结

隐马尔可夫 隐马尔可夫 Hidden Markov Model HMM 一 马尔可夫过程 一 马尔可夫过程 Markov Process 1 马尔可夫过程介绍 马尔可夫过程介绍 马尔可夫过程 Markov Process 它因俄罗斯数学家安德烈 马尔可夫而得名 代表数 学中具有马尔可夫性质马尔可夫性质的离散随机过程 该过程中 每个状态的转移只依赖于之前的 n 个 状态 这个过程被称为 1 个 n 阶的模型 其中 n 是影响转移状态的数目 最简单的马尔科 夫过程就是一阶过程 每一个状态的转移只依赖于其之前的那一个状态 马尔可夫链是随机变量 X1 Xn的一个数列 这些变量的范围 即他们所有可能取 值的集合 被称为 状态空间 而 Xn的值则是在时间 n 的状态 如果 Xn 1对于过去状态 的条件概率分布仅是 Xn的一个函数 则 这里 x 为过程中的某个状态 上面这个恒等式可以被看作是马尔可夫性质马尔可夫性质 2 马尔可夫过程举例 马尔可夫过程举例 下图展示了天气这个例子中所有可能的一阶转移 注意一个含有 N 个状态状态的一阶过程有 N2个状态转移 每一个转移的概率叫做状态转 移概率 state transition probability 即从一个状态转移到另一个状态的概率 这所有的 N2 个概率可以用一个状态转移矩阵状态转移矩阵来表示 其表示形式如下 对该矩阵有如下约束条件 下面就是海藻例子的状态转移矩阵 这个矩阵表示 如果昨天是晴天 那么今天有 50 的可能是晴天 37 5 的概率是阴 天 12 5 的概率会下雨 很明显 矩阵中每一行的和都是 1 为了初始化这样一个系统 我们需要一个初始的概率向量初始的概率向量 这个向量表示第一天是晴天 3 一阶马尔可夫过程定义 一阶马尔可夫过程定义 如上述马尔可夫过程例子可知 我们为一阶马尔可夫过程定义了以下三个部分 状态状态 晴天 阴天和下雨 初始向量初始向量 定义系统在时间为 0 的时候的状态的概率 状态转移矩阵状态转移矩阵 每种天气转换的概率 所有的能被这样描述的系统都是一个马尔可夫过程 二 隐马尔可夫过程 二 隐马尔可夫过程 HMM 1 隐马尔可夫模型介绍 隐马尔可夫模型介绍 隐马尔可夫模型 HMM 是一个输出符号序列统计模型 具有 T 个状态 X1 X2 Xt 1 它 按一定的周期从一个状态转移到另一个状态 每次转移时 输出一个符号 观测值 转移 到哪一个状态 转移时输出什么符号 分别由状态转移概率和转移时输出概率来决定 因 为只能观测到输出符号的序列 而不能观测到状态转移序列 即模型的观测序列是通过哪 个状态路径是不知道的 所以称为隐马尔可夫模型 2 隐马尔可夫过程举例 隐马尔可夫过程举例 下面是一个简单的例子 气象学上 可通过年轮的宽窄了解各年的气候状况 利用年 轮上的信息可推测出几千年来的气候变迁情况 年轮宽表示那年光照充足 风调雨顺 若 年轮较窄 则表示那年温度低 雨量少 气候恶劣 为了简单起见 我们只考虑冷 code 热 hot 两种温度 根据现代的气象知识可以知道 冷 的一年跟着下一年为热的概率为 0 4 为冷的概率为 0 6 热 的一年跟着下一年为热的概率为 0 7 为冷的概率为 0 3 可以简单的归纳为下面规律 我们将树的年轮简单分为小 small 中 middle 大 large 三种 或者分别写成 S M L 根 据现代的气象知识可以知道 热的一年树木年轮为 小 中 大 的概率分别为 0 1 0 4 0 5 冷的一年树木年轮为 小 中 大 的概率分别为 0 7 0 2 0 1 因此 冷 C 热 H 对年轮的影响可以简单归纳为下面规律 在这个系统中 状态序列是每年的温度 H 或者 C 因为下一年的温度只与上一年有关 所以从一个状态 温度 转移到下一个状态 温度 可以看成是一个一阶 Markov process 因为 无法观测过去的温度 状态序列也被称为隐藏状态 尽管我们不能观测过去的状态 温度 序列 但是可以通过树的年轮给我们提供的信息预测温度 我们的目标就是充分利用可观 测的年轮序列 来预测那些年的温度序列情况 Markov 过程 从上面规律可以得到 状态转移矩阵 A 混淆矩阵 confusion matrix B 假设初始状态矩阵 如本例中是初始状态矩阵是最开始产生 Hot 和 Cold 天气的概率 这样可以得到天气与树年轮的概率图模型 图中最开始产生 Hot 天气的概率为 0 6 由初始状态矩阵 PI 决定 Hot 天气产生树年 轮 Small 的概率为 0 1 Hot 状态产生 Hot 状态的概率为 0 7 接着 Hot 产生 Middle 的概率 为 0 4 以此类推 因此可以得到隐藏天气序列 HHCC 产生树木年轮序列为 SMSL 的概率 使用这种办法我们就可以计算产生 SMSL 序列存在的所有天气序列的概率 比较可得 P CCCH 的概率为 0 002822 是最大的 结论 若树木年轮序列为 SMSL 则最可能状态序列 Markov process 是 CCCH 产生树木年轮序列为 SMSL 的概率为 0 009629 所有可能相加 3 HMM 的三个重要假设的三个重要假设 下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系 我们假设隐藏 的状态是一个简单的一阶马尔可夫过程 并且他们两两之间都可以相互转换 对 HMM 来说 有如下三个重要假设 尽管这些假设是不现实的 假设假设 1 马尔可夫假设 状态构成一阶马尔可夫链 假设假设 2 不动性假设 状态与具体时间无关 假设假设 3 输出独立性假设 输出仅与当前状态有关 4 HMM 的基本元素的基本元素 一个 HMM 可用一个 5 元组 N M A B 表示 其中 N 表示隐藏状态的数量 我们要么知道确切的值 要么猜测该值 M 表示可观测状态的数量 可以通过训练集获得 i 为初始状态概率 A aij 为隐藏状态的转移矩阵 Pr xt i xt 1 j B bik 表示某个时刻因隐藏状态而导致可观察状态的概率 即混淆矩阵 Pr ot i xt j 在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的 即当系统演化时 这些矩 阵并不随时间改变 对于一个 N 和 M 固定的 HMM 来说 用 A B 表示 HMM 参 数 三 三 HMM 的三个基本问题的三个基本问题 1 问题 问题 1 识别问题识别问题 1 1 问题描述问题描述 给定模型 A B 和观测序列 O O0 O1 OT 1 如何快速有效的找到 P O 解释 解释 假设我们已经有一个特定的隐马尔科夫模型 和一个可观察状态序列集 我 们也许想知道在所有可能的隐藏状态序列下 给定的可观察状态序列的概率 问题 1 可以 归纳为 举例 举例 如 2 2 小节的例子中 已知模型 观测序列 O SMSL 求产生 SMSL 年 轮序列的概率 1 2 解决方案解决方案 1 2 1 蛮力算法蛮力算法 若用图表示可以得到如下 其中 然而 这种直接的计算的方法 蛮力算法 一般是不可行的 实际情况中 我们不可能 知道每一种可能的路径 而且这种计算的计算量也是十分惊人的 达到大约数量级 如 当 HMM 的状态数为 5 观测序列长度为 100 时 计算量达到 是完全无法接受的 因此 需要更有效的算法 这就是 Baum 等人提出的前向 后向算法 1 2 2 前向算法前向算法 a pass 前向算法即按输出观察值序列的时间 从前向后递推计算输出概率 首先说明下列符号的定义 由上面的符号的定义 则 at i 可由下面递推公式计算得到 解释 解释 使用这种前向递推计算算法的计算量大为减少 复杂度变为 N2T 同样的 1 中例子 N 5 T 100 时 只需要大约 2500 次乘法 1 2 3 后向算法后向算法 pass 与前向算法类似 向后算法即使按输出观察序列的时间 从后面向前递推计算输出概 率的方法 首先说明下列符号的定义 由递推公式可得 解释 解释 2 问题 问题 2 解码问题解码问题 2 1 问题描述问题描述 给定模型 A B 和观测序列 O O0 O1 OT 1 找到最优的隐藏状态序列 解释 解释 根据可观察状态的序列找到一个最可能的隐藏状态序列 问题 2 可以归纳为 举例 举例 如 2 2 小节的例子中 已知模型 观测序列 O SMSL 求最有可能产生 SMSL 序列的状态序列 CCCH 2 2 解决方案解决方案 2 2 1 蛮力算法蛮力算法 如 1 2 1 中计算每一条可能状态序列的概率 然后比较找出其中概率最大的一条就为我 们需要的状态序列 X 如开始的例 1 中就是采用这种算法 这种算法虽然易理解 但是计 算开销太大 一般不可取 2 2 2 前向后向算法前向后向算法 在 4 1 中我们详细的讨论了前向算法以及后向算法 而前向后向算法就是综合这两种 算法 可以用来解决寻找最可能隐藏状态序列 X 的问题 首先我们说明下列符号的定义 2 2 3 维特比维特比 Viterbi 算法算法 在给定了一个可观察序列和 HMM 的情况下 我们可以考虑递归的来寻找最可能的隐 藏序列 我们可以先定义一个部分概率 即到达某个中间状态的概率 接下来我们将讨 论如何计算 t 1 和 t n n 1 的部分概率 注意这里的部分概率和前向算法中的部分概率是不一样的 这里的部分概率表示的是 在 t 时刻最可能到达某个状态的一条路径的概率 而不是所有概率之和 1 部分概率和部分最优路径部分概率和部分最优路径 考虑下面这个图以及可观察序列 dry damp soggy 的一阶转移 对于每一个中间状态和终止状态 t 3 都有一个最可能的路径 比如说 在 t 3 时刻的三 个状态都有一个如下的最可能的路径 我们可以称这些路径为部分最优路径部分最优路径 这些部分最优路径都有一个概率 也就是部分 概率 和前向算法中的部分概率不一样 这里的概率只是一个最可能路径的概率 而不 是所有路径的概率和 我们可以用 i t 来表示在 t 时刻 到状态 i 的所有可能的序列 路径 中概率最大 的序列的概率 部分最优路径就是达到这个最大概率的路径 对于每一个时刻的每一个状 态都有这样一个概率和部分最优路径 最后 我们通过计算 t T 时刻的每一个状态的最大概率和部分最优路径 选择其中概 率最大的状态和它的部分最优路径来得到全局的最优路径 2 计算计算 t 1 时刻的部分概率时刻的部分概率 当 t 1 时刻的时候 到达某个状态最大可能的路径还不存在 但是我们可以直接使用 在 t 1 时刻某个状态的概率和这个状态到可观察序列 k1的转移概率 3 计算计算 t 1 时刻的部分概率时刻的部分概率 接下来我们可以根据 t 1 时刻的部分概率来求 t 时刻的部分概率 我们可以计算所有到状态 X 的路径的概率 找到其中最可能的路径 也就是局部最优 路径 注意到这里 到达 X 的路径必然会经过 t 1 时刻的 A B 和 C 所以我们可以利 用之前的结果 达到 X 的最可能的路径就是下面三个之一 状态序列 A X 状态序列 B X 状态序列 C X 我们需要做的就是找到以 AX BX 和 CX 结尾的路径中概率最大的那个 根据一阶马尔科夫的假设 一个状态的发生只和之前的一个状态有关系 所以 X 在某 个序列的最后发生的概率只依赖于其之前的一个状态 Pr 到达 A 的最优路径 Pr X A Pr 观察状态 X 有个了这个公式 我们就可以利用 t 1 时刻的结果和状态转移矩阵和混淆矩阵的数据 将上面这个表达式推广一下 就可以得到 t 时刻可观察状态为 kt 的第 i 个状态的最大 部分概率的计算公式 其中 aji 表示从状态 j 转移到状态 i 的概率 bikt 表示状态 i 被观察成 kt 的概率 4 后向指针后向指针 考虑下图 在每一个中间状态和结束状态都有一个部分最优概率 i t 但是我们的目的是找到 最可能的隐藏状态序列 所以我们需要一个方法去记住部分最优路径的每一个节点 考虑到要计算 t 时刻的部分概率 我们只需要知道 t 1 时刻的部分概率 所以我们只 需要记录那个导致了 t 时刻最大部分概率的的状态 也就是说 在任意时刻 系统都必须 处在一个能在下一时刻产生最大部分概率的状态 如下图所示 我们可以利用一个后向指针 来记录导致某个状态最大局部概率的前一个状态 即 这里 argmax 表示能最大化后面公式的 j 值 同样可以发现这个公式和 t 1 时刻的部 分概率和转移概率有关 因为后向指针只是为了找到 我从哪里来 这个问题和可观察状 态没有关系 所以这里不需要再乘上混淆矩阵因子 全局的行为如下图所示 5 优点优点 使用 viterbi 算法对一个可观察状态进行解码有两个重要的优点 a 通过使用递归来减少复杂度 这点和之前的前向算法是一样的 b 可以根据可观察序列找到最优的隐藏序列 这个的计算公式是 这里就是一个从左往右翻译的过程 通过前面的翻译结果得到后面的结果 起始点是 初始向量 6 补充 补充 但在序列某个地方有噪声干扰的时候 某些方法可能会和正确答案相差的较远 但是 Viterbi 算法会查看整个序列来决定最可能的终止状态 然后通过后向指针来找到之前的状 态 这对忽略孤立的噪声非常有用 Viterbi 算法提供了一个根据可观察序列计算隐藏序列的很高效的方法 它利用递归来 降低计算复杂度 并且使用之前全部的序列来做判断 可以很好的容忍噪声 在计算