HMM简介

·约 2154 字·5 分钟·
AI摘要: 本文介绍了隐马尔可夫模型（HMM）的基本原理、前提假设以及三个核心问题：评估问题、预测问题和学习问题的解决方法。详细阐述了HMM的联合概率函数建模，包括初始状态概率分布π、状态转移概率矩阵A和发射概率矩阵B。针对评估问题，提到了前向算法；对于预测问题，讨论了贪心算法和维特比算法；在学习问题上，区分了有监督学习和无监督学习场景，并指出无监督学习中常用EM算法来估计模型参数。

HMM的前提假设

        +------+     +------+     +------+     +------+
Start-> | S₁   | --> | S₂   | --> | S₃   | --> | Sₙ   |
        +------+     +------+     +------+     +------+
           |             |             |             |
           v             v             v             v
        +------+     +------+     +------+     +------+
        | O₁   |     | O₂   |     | O₃   |     | Oₙ   |
        +------+     +------+     +------+     +------+
  • 马尔科夫性：t时刻状态，只和t-1时刻状态有关，和更前的无关
  • 观测独立性：t时刻观测值只依赖该时刻的状态，和其他任何时刻的观测值以及状态无关

HMM中拿到数据集之后，我们建模他们的联合概率函数：

P(O1,O2,...,On,X1,X2,...,Xn)=P(X1,O1,X2,O2,...,Xn,On)=P(X1)∗P(O1∣X1)∗P(X2∣X1O1)∗P(O2∣X2X1O1)∗...=P(X1)∗P(O1∣X1)∗P(X2∣X1)∗P(O2∣X2)∗....P(Xn∣Xn−1)∗P(On∣Xn)=P(X1)P(O1∣X1)∏t=2nP(Xt∣Xt−1)P(Ot∣Xt)\begin{aligned} P(O_1, O_2, ...,O_n, X_1, X_2, ..., X_n) &= P(X_1, O_1, X_2, O_2, ..., X_n, O_n) \\ &= P(X_1) * P(O_1 | X_1) * P(X_2 | X_1 O_1) * P(O_2|X_2X_1O_1) * ...\\ &=P(X_1) * P(O_1 | X_1) * P(X_2 | X_1) * P(O_2 | X_2) * ....P(X_n | X_{n - 1}) * P(O_n | X_n) \\ &=P(X_1) P(O_1 | X_1) \prod_{t = 2}^n P(X_t | X_{t - 1}) P(O_t | X_t) \end{aligned}

因此，联合概率只依赖：

  • P(X1)P(X_1): 初始状态概率分布，不妨记作π\pi
  • P(Xt∣Xt−1)P(X_t | X_{t - 1})：状态转移概率矩阵，不妨记作AA
  • P(Ot∣Xt)P(O_t | X_t) ：给定状态时候，观测值的概率分布，也叫做发射概率，不妨记作BB

HMM的所有计算和预测，都围绕如何从数据集中计算得到λ=(π,A,B)\lambda = (\pi, A, B)

  • 评估问题：已知λ=(π,A,B)\lambda = (\pi, A, B) 和观测序列O1,O2,...,OnO_1, O_2, ... , O_n, 需要计算这个观测序列的出现概率, 一般解法为前向算法或者后向算法
  • 预测问题：已知λ=(π,A,B)\lambda = (\pi, A, B) 和观测序列O1,O2,...,OnO_1, O_2, ... , O_n， 预测最有可能的状态序列，一般用贪心算法或者维特比算法
  • 学习问题：模型参数λ=(π,A,B)\lambda = (\pi, A, B) 未知，需要学习推断，分为两种场景：
    • 已知诸多观测序列和状态序列的监督学习，直接根据数据集统计出AA矩阵和BB矩阵
    • 只知道观测序列，不知道背后状态情况的无监督学习，这个常常采用EM算法

关于评估问题：

P(O1,O2,...,On)=∑所有可能的状态序列XP(O,X)=∑x1,x2,...,xnP(o1,o2,...,on,x1,x2,...,xn)\begin{aligned} P(O_1, O_2, ..., O_n) &= \sum_{所有可能的状态序列X} P(O, X) \\ &= \sum_{x_1, x_2, ..., x_n} P(o_1, o_2, ..., o_n, x_1, x_2, ..., x_n) \end{aligned}

由于状态序列的可能性是指数级增长的, 如果状态有TT种可能，那么状态序列有TNT^N种可能，不可能穷尽, 于是改成采用动态规划的前向算法，具体算法过程没看。

关于预测问题

MAXx1,x2,...,xnP(x1,x2,...,xn)=MAX(P(x1))∗MAX(P(x2))∗...∗MAX(P(xn))(贪心解法)\begin{aligned} MAX_{x_1, x_2, ..., x_n}P(x_1, x_2, ..., x_n) & = MAX(P(x_1)) * MAX(P(x_2)) * ... * MAX(P(x_n)) (贪心解法) \end{aligned}

希望找到一个状态序列x1,x2,...,xnx_1, x_2, ..., x_n, 使得概率最大，那么贪心的解法就是令每个状态的出现概率最大，即每次选择概率最大的状态。

维特比算法没看。

关于学习问题

有监督场景

既然已经知道每个观测背后的状态是什么，那状态转移矩阵和发射矩阵很好直接统计出来：

  • 将状态序列划分为二元组，就能直接得到一个状态到另外一个状态的频率，最后归一化为概率
  • 直接统计一个状态到某种观测的次数，就能得到发射频率，最后归一化为发射概率

无监督场景

只能看到观测序列，不知道背后的状态是什么，反正就是学习出模型参数λ=(π,A,B)\lambda = (\pi, A, B) ， 使得P(O∣λ)P(O | \lambda)最大 。

那就采用EM算法，但是这个HMM中用的的EM算法的E步骤有点奇怪，暂时解决不了