隐马尔可夫模型

机器学习与数据挖掘
问题 分类 聚类 回归 异常检测 数据清洗 自动机器学习 关联规则 强化学习 结构预测 特征工程 特征学习 線上機器學習 無監督學習 半监督学习 排序学习 语法归纳
監督式學習 (分类 · 回归) 决策树 集成（装袋，提升，随机森林） k-NN 线性回归 朴素贝叶斯 神经网络 邏輯迴歸 感知器 支持向量机（SVM） 相关向量机（RVM）
聚类 BIRCH 层次 k-平均 期望最大化（EM） DBSCAN OPTICS 均值飘移
降维 因素分析 CCA ICA LDA NMF PCA LASSO t-SNE
结构预测 概率图模型（贝叶斯网络，CRF, HMM）
异常检测 k-NN 局部离群因子
神经网络 自编码 深度学习 多层感知机 RNN 受限玻尔兹曼机 SOM CNN Transformer模型
强化学习 Q学习 SARSA 时序差分学习 深度强化学习
理论 偏差/方差困境 计算学习理论 经验风险最小化 PAC学习 统计学习 VC理论
研讨会 NeurIPS ICML ICLR
查 论 编

隐马尔可夫模型状态变迁图（例子）
x — 隐含状态
y — 可观察的输出
a — 转换概率（transition probabilities）
b — 输出概率（output probabilities）

隐马尔可夫模型（Hidden Markov Model；縮寫：HMM）或稱作隐性马尔可夫模型，是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。

在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中，状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。

马尔可夫模型的演化

下边的图示强调了HMM的状态变迁。有时，明确的表示出模型的演化也是有用的，我们用 x(t₁) 与 x(t₂) 来表达不同时刻 t₁ 和 t₂ 的状态。

圖中箭頭方向則表示不同資訊間的關聯性，因此可以得知${\displaystyle x(t)}$和${\displaystyle x(t-1)}$有關，而${\displaystyle x(t-1)}$又和${\displaystyle x(t-2)}$有關。

而每個${\displaystyle y(t)}$只和${\displaystyle x(t)}$有關，其中${\displaystyle x(t)}$我們稱為隱藏變數（hidden variable），是觀察者無法得知的變數。

隱性馬可夫模型常被用來解決有未知條件的數學問題。

假設隱藏狀態的值對應到的空間有${\displaystyle N}$個元素，也就是說在時間${\displaystyle t}$時，隱藏狀態會有${\displaystyle N}$種可能。

同樣的，${\displaystyle t+1}$也會有${\displaystyle N}$種可能的值，所以從${\displaystyle t}$到${\displaystyle t+1}$間的關係會有${\displaystyle N^{2}}$種可能。

除了${\displaystyle x(t)}$間的關係外，每組${\displaystyle x(t),y(t)}$間也有對應的關係。

若觀察到的${\displaystyle y(t)}$有${\displaystyle M}$種可能的值，則从${\displaystyle x(t)}$到${\displaystyle y(t)}$的输出模型复杂度為${\displaystyle O(NM)}$。如果${\displaystyle y(t)}$是一个${\displaystyle M}$维的向量，则从${\displaystyle x(t)}$到${\displaystyle y(t)}$的输出模型复杂度為${\displaystyle O(NM^{2})}$。

在这个图中,每一个时间块（x(t), y(t)）都可以向前或向后延伸。通常，时间的起点被设置为t=0 或 t=1.

马尔可夫模型的機率

假設觀察到的結果為${\displaystyle Y}$

${\displaystyle Y=y(0),y(1),...,y(L-1)}$

隱藏條件為${\displaystyle X}$

${\displaystyle X=x(0),x(1),...,x(L-1)}$

長度為${\displaystyle L}$，則馬可夫模型的機率可以表達為：

${\displaystyle P(Y)=\sum _{X}P(Y\mid X)P(X)\,}$

由這個機率模型來看，可以得知馬可夫模型將該時間點前後的資訊都納入考量。

使用隐马尔可夫模型

HMM有三个典型(canonical)问题:

• 预测(filter)：已知模型参数和某一特定输出序列，求最后时刻各个隐含状态的概率分布，即求 ${\displaystyle P(x(t)\ |\ y(1),\dots ,y(t))}$。通常使用前向算法解决。
• 平滑(smoothing)：已知模型参数和某一特定输出序列，求中间时刻各个隐含状态的概率分布，即求 ${\displaystyle P(x(k)\ |\ y(1),\dots ,y(t)),k<t}$。通常使用前向-后向算法解决。
• 解码(most likely explanation)：已知模型参数，寻找最可能的能产生某一特定输出序列的隐含状态的序列，即求 ${\displaystyle P([x(1)\dots x(t)]|[y(1)\dots ,y(t)])}$。通常使用Viterbi算法解决。

此外，已知输出序列，寻找最可能的状态转移以及输出概率.通常使用Baum-Welch算法以及Viterbi algorithm解决。另外,最近的一些方法使用联结树算法来解决这三个问题。

具体实例

假设你有一个住得很远的朋友，他每天跟你打电话告诉你他那天做了什么。你的朋友仅仅对三种活动感兴趣：公园散步，购物以及清理房间。他选择做什么事情只凭天气。你对于他所住的地方的天气情况并不了解，但是你知道总的趋势。在他告诉你每天所做的事情基础上，你想要猜测他所在地的天气情况。

你认为天气的运行就像一个马尔可夫链。其有两个状态「雨」和「晴」，但是你无法直接观察它们，也就是说，它们对于你是隐藏的。每天，你的朋友有一定的概率进行下列活动：「散步」、「购物」、「清理」。因为你朋友告诉你他的活动，所以这些活动就是你的观察数据。这整个系统就是一个隐马尔可夫模型（HMM）。

你知道这个地区的总的天气趋势，并且平时知道你朋友会做的事情。也就是说这个隐马尔可夫模型的参数是已知的。你可以用程序语言（Python）写下来：

 states = ('Rainy', 'Sunny')
 
 observations = ('walk', 'shop', 'clean')
 
 start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
 transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
 
 emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
    }

在这些代码中,start_probability代表了你对于你朋友第一次给你打电话时的天气情况的不确定性（你知道的只是那个地方平均起来下雨多些）。在这里，这个特定的概率分布并非平衡的，平衡概率应该接近（在给定变迁概率的情况下）{'Rainy': 0.571, 'Sunny': 0.429}。 transition_probability 表示基于马尔可夫链模型的天气变迁，在这个例子中，如果今天下雨，那么明天天晴的概率只有30%。代码emission_probability 表示了你朋友每天做某件事的概率。如果下雨，有50% 的概率他在清理房间；如果天晴，则有60%的概率他在外头散步。

这个例子在维特比算法页上有更多的解释。

隐马尔可夫模型的应用

• 语音识别、中文斷詞/分詞或光学字符识别
• 机器翻译
• 生物信息学 和 基因组学
  • 基因组序列中蛋白质编码区域的预测
  • 对于相互关联的DNA或蛋白质族的建模
  • 从基本结构中预测第二结构元素
  • 通信中的译码过程
  • 地图匹配算法
• 还有更多...

隐马尔可夫模型在語音處理上的應用

因為馬可夫模型有下列特色：

• 時間點${\displaystyle t}$的隱藏條件和時間點${\displaystyle t-1}$的隱藏條件有關。因為人類語音擁有前後的關聯，可以從語義與發音兩點來看：

1. 單字的發音擁有前後關聯：例如"They are"常常發音成"They're"，或是"Did you"會因為"you"的發音受"did"的影響，常常發音成"did ju"，而且語音辨識中用句子的發音來進行分析，因此需要考慮到每個音節的前後關係，才能夠有較高的準確率。
2. 句子中的單字有前後關係：從英文文法來看，主詞後面常常接助動詞或是動詞，動詞後面接的會是受詞或介係詞。而或是從單一單字的使用方法來看，對應的動詞會有固定使用的介係詞或對應名詞。因此分析語音訊息時需要為了提升每個單字的準確率，也需要分析前後的單字。

• 馬可夫模型將輸入訊息視為一單位一單位，接著進行分析，與人類語音模型的特性相似。語音系統辨識的單位為一個單位時間內的聲音。利用梅爾倒頻譜等語音處理方法，轉換成一個發音單位，為離散型的資訊。而馬可夫模型使用的隱藏條件也是一個個被封包的${\displaystyle x(t)}$，因此使用馬可夫模型來處理聲音訊號比較合適。

历史

隐马尔可夫模型最初是在20世纪60年代后半期Leonard E. Baum和其它一些作者在一系列的统计学论文中描述的。HMM最初的应用之一是开始于20世纪70年代中期的语音识别。

在1980年代后半期，HMM开始应用到生物序列尤其是DNA的分析中。此后，在生物信息学领域HMM逐渐成为一项不可或缺的技术。

参见

• 安德雷·马尔可夫
• 贝叶斯推断
• 估计理论
• 條件隨機域
• 排队理论
• 馬可夫決策過程

注解

参考书目

外部链接

规范控制 GND: 4352479-5 J9U: 987007544695605171 LCCN: sh2007000125