最详细最容易理解的HMM文章

喜欢ヅ旅行 2022-05-24 03:13 254阅读 0赞

# 最详细最容易理解的HMM文章 #

[https://blog.csdn.net/daringpig/article/details/8072794][https_blog.csdn.net_daringpig_article_details_8072794]  
[http://www.52nlp.cn/hmm-learn-best-practices-four-hidden-markov-models][http_www.52nlp.cn_hmm-learn-best-practices-four-hidden-markov-models]

# 核心目的：对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列，我们常常希望能找到生成此序列最可能的隐藏状态序列。 #

# 我们使用一个隐马尔科夫模型（HMM）对这些例子建模。这个模型包含两组状态集合和三组概率集合： #

# \* 隐藏状态：一个系统的（真实）状态，可以由一个马尔科夫过程进行描述（例如，天气）。 #

# \* 观察状态：在这个过程中‘可视’的状态（例如，海藻的湿度）。 #

# \* 向量：包含了（隐）模型在时间t=1时一个特殊的隐藏状态的概率（初始概率）。 #

# \* 状态转移矩阵：包含了一个隐藏状态到另一个隐藏状态的概率 #

# \* 混淆矩阵：包含了给定隐马尔科夫模型的某一个特殊的隐藏状态，观察到的某个观察状态的概率。 #

# 因此一个隐马尔科夫模型是在一个标准的马尔科夫过程中引入一组观察状态，以及其与隐藏状态间的一些概率关系。 #

## [wiki上一个比较好的HMM例子][wiki_HMM] ##

HMM(隐马尔科夫模型)是自然语言处理中的一个基本模型，用途比较广泛，如汉语分词、词性标注及语音识别等，在NLP中占有很重要的地位。网上关于HMM的介绍讲解文档很多，我自己当时开始看的时候也有点稀里糊涂。后来看到wiki上举得一个关于HMM的例子才如醍醐灌顶，忽然间明白HMM的三大问题是怎么回事了。例子我借助中文wiki重新翻译了一下，并对三大基本问题进行说明，希望对读者朋友有所帮助：

Alice 和Bob是好朋友，但是他们离得比较远，每天都是通过电话了解对方那天作了什么.Bob仅仅对三种活动感兴趣:公园散步,购物以及清理房间.他选择做什么事情只凭当天天气.Alice对于Bob所住的地方的天气情况并不了解,但是知道总的趋势.在Bob告诉Alice每天所做的事情基础上,Alice想要猜测Bob所在地的天气情况.  
　　Alice认为天气的运行就像一个马尔可夫链. 其有两个状态 “雨”和”晴”,但是无法直接观察它们,也就是说,它们对于Alice是隐藏的.每天,Bob有一定的概率进行下列活动:”散步”, “购物”, 或 “清理”. 因为Bob会告诉Alice他的活动,所以这些活动就是Alice的观察数据.这整个系统就是一个隐马尔可夫模型HMM.  
　　Alice知道这个地区的总的天气趋势,并且平时知道Bob会做的事情.也就是说这个隐马尔可夫模型的参数是已知的.可以用程序语言(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代表了Alice对于Bob第一次给她打电话时的天气情况的不确定性(Alice知道的只是那个地方平均起来下雨多些).在这里,这个特定的概率分布并非平衡的,平衡概率应该接近（在给定变迁概率的情况下）\{‘Rainy’: 0.571, ‘Sunny’: 0.429\}。 transition\_probability 表示马尔可夫链下的天气变迁情况,在这个例子中,如果今天下雨,那么明天天晴的概率只有30%.代码emission\_probability 表示了Bob每天作某件事的概率.如果下雨,有 50% 的概率他在清理房间;如果天晴,则有60%的概率他在外头散步。  
　　Alice和Bob通了三天电话后发现第一天Bob去散步了，第二天他去购物了，第三天他清理房间了。Alice现在有两个问题：这个观察序列“散步、购物、清理”的总的概率是多少？(注：这个问题对应于HMM的基本问题之一：已知HMM模型λ及观察序列O，如何计算P(O|λ)？) 最能解释这个观察序列的状态序列（晴/雨）又是什么？（注：这个问题对应HMM基本问题之二：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列S = q1,q2,…qT，使得S能够最为合理的解释观察序列O？）  
　　至于HMM的基本问题之三：如何调整模型参数, 使得P(O|λ)最大？这个问题事实上就是给出很多个观察序列值，来训练以上几个参数的问题。

## [HMM学习最佳范例与崔晓源的博客][HMM] ##

“HMM学习最佳范例”与“崔晓源的博客”本来是不搭边的，由于自己花了几乎一个晚上浏览崔师兄的博客，没有时间写文章了，所以最终决定放在这里做成大杂烩，不过我觉得这个大杂烩还是有点价值的。  
　　先说说HMM，通过Google Analytics 发现，读者经常通过与“隐马尔科夫模型、HMM”相关的关键字访问52nlp的，因为这里曾经写了一篇简单的介绍HMM的文章。事实上，对于HMM，由于自己没有直接实践过，仅停留在“纸上得来”的程度，所以心里也虚。某天赶巧遇到了国外这个专门介绍HMM及其相关算法的主页：[http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html\_dev/main.html][http_www.comp.leeds.ac.uk_roger_HiddenMarkovModels_html_dev_main.html]  
　　里面图文并茂还动感十足，写得又通俗易懂，可以说是我见到过的介绍HMM最好的范例了。读完了立即有翻译全文的冲动，这样一方面可以给有需要的读者以帮助，另一方面翻译虽然耗时，但却能仔细把握一下比较细节的地方，这也是我翻译“MIT自然语言处理”的初衷。不过Google了一下，发现已经有人把这件事做了，这个人就是崔晓源，中文译名是“隐马尔科夫模型HMM自学”。  
　　原计划这一篇博客题目为“HMM学习最佳范例”的，准备介绍这个英文主页和崔晓源的翻译，出于尊重译者劳动的缘故，Google“隐马尔科夫模型HMM自学”，可是发现其被转载了很多，除了知道译者是“崔晓源”外，原始出处似乎被丢失了。不过最终还是找到了原始出处：  
　　[http://blogcui.spaces.live.com/blog/cns!46BDB23E24219CE9!144.entry?\_c=BlogPart][http_blogcui.spaces.live.com_blog_cns_46BDB23E24219CE9_144.entry_c_BlogPart]  
　　其实就是崔师兄在msn spaces上的博客，仔细对比了一下原文，发现崔师兄的这个翻译是一个简化和缩略版本，有些地方只是概况性的翻译了一下，省去了一些内容，所以这个介绍HMM主页还有再翻译的必要。有可能的话，今后在52nlp上我会慢慢翻译HMM这个系列。  
　　对比完之后，我就浏览开他的博客了，没想到，一发而不可收，主要在于他的博客多数内容都很有价值。博客最集中更新的一段时间，是在05年5月到9月份他在MSRA-NLC组实习的时候，不过可惜的是，现在几乎不更新了，但是技术博客的好处再于其有效期更长，所以许多东西仍很可以参考，读者如果对NLP，IR或者机器学习感兴趣，不妨按时间顺序读读他的日志，定会有不小收获的，这里绝非广告。他目前在MSRA工作，以下是他的“About me”：  
　　”A man full of enthusiasm for advanced technology business, natrual language processing, IR and search engine technology. I’m finding my way. You never do a bad job only if you choose the right time. So keep your pace accordingly.“  
　　我在上面最大的发现是这个关于机器学习的英文博客：

## [几种不同程序语言的HMM版本][HMM 1] ##

“纸上得来终觉浅，绝知此事要躬行”，在继续翻译《HMM学习最佳范例》之前，这里先补充几个不同程序语言实现的HMM版本，主要参考了维基百科。读者有兴趣的话可以研究一下代码，这样对于HMM的学习会深刻很多！

C语言版：  
1、 HTK（Hidden Markov Model Toolkit）：  
　　HTK是英国剑桥大学开发的一套基于C语言的隐马尔科夫模型工具箱，主要应用于语音识别、语音合成的研究，也被用在其他领域，如字符识别和DNA排序等。HTK是重量级的HMM版本。  
　　HTK主页：[http://htk.eng.cam.ac.uk/][http_htk.eng.cam.ac.uk]  
2、 GHMM Library：  
　　The General Hidden Markov Model library (GHMM) is a freely available LGPL-ed C library implementing efficient data structures and algorithms for basic and extended HMMs.  
　　GHMM主页：[http://www.ghmm.org/][http_www.ghmm.org]  
3、 UMDHMM（Hidden Markov Model Toolkit）：  
　　Hidden Markov Model (HMM) Software: Implementation of Forward-Backward, Viterbi, and Baum-Welch algorithms.  
　　这款属于轻量级的HMM版本。  
　　UMDHMM主页：[http://www.kanungo.com/software/software.html][http_www.kanungo.com_software_software.html]

Java版：  
4、 Jahmm Java Library (general-purpose Java library)：  
　　Jahmm (pronounced “jam”), is a Java implementation of Hidden Markov Model (HMM) related algorithms. It’s been designed to be easy to use (e.g. simple things are simple to program) and general purpose.  
　　Jahmm主页：[http://code.google.com/p/jahmm/][http_code.google.com_p_jahmm]

Malab版：  
5、 Hidden Markov Model (HMM) Toolbox for Matlab：  
　　This toolbox supports inference and learning for HMMs with discrete outputs (dhmm’s), Gaussian outputs (ghmm’s), or mixtures of Gaussians output (mhmm’s).  
　　Matlab-HMM主页：[http://www.cs.ubc.ca/~murphyk/Software/HMM/hmm.html][http_www.cs.ubc.ca_murphyk_Software_HMM_hmm.html]

Common Lisp版：  
6、CL-HMM Library (HMM Library for Common Lisp)：  
　　Simple Hidden Markov Model library for ANSI Common Lisp. Main structures and basic algorithms implemented. Performance speed comparable to C code. It’s licensed under LGPL.  
　　CL-HMM主页：[http://www.ashrentum.net/jmcejuela/programs/cl-hmm/][http_www.ashrentum.net_jmcejuela_programs_cl-hmm]

Haskell版：  
7、The hmm package （A Haskell library for working with Hidden Markov Models）：  
　　A simple library for working with Hidden Markov Models. Should be usable even by people who are not familiar with HMMs. Includes implementations of Viterbi’s algorithm and the forward algorithm.  
　　Haskell-HMM主页：[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmm][http_hackage.haskell.org_cgi-bin_hackage-scripts_package_hmm]  
　　注：Haskell是一种纯函数式编程语言，它的命名源自美国数学家Haskell Brooks Curry，他在数学逻辑方面上的工作使得函数式编程语言有了广泛的基础。

是否还有C++版、Perl版或者Python版呢？欢迎补充！

## [HMM学习最佳范例一：介绍][HMM 2] ##

隐马尔科夫模型（HMM）依然是读者访问“我爱自然语言处理”的一个热门相关关键词，我曾在《HMM学习最佳范例与崔晓源的博客》中介绍过国外的一个不错的[HMM学习教程][HMM 3]，并且国内崔晓源师兄有一个相应的[翻译版本][Link 1]，不过这个版本比较简化和粗略，有些地方只是概况性的翻译了一下，省去了一些内容，所以从今天开始计划在52nlp上系统的重新翻译这个学习教程，希望对大家有点用。

### 一、介绍（Introduction） ###

我们通常都习惯寻找一个事物在一段时间里的变化模式（规律）。这些模式发生在很多领域，比如计算机中的指令序列，句子中的词语顺序和口语单词中的音素序列等等，事实上任何领域中的一系列事件都有可能产生有用的模式。  
　　考虑一个简单的例子，有人试图通过一片海藻推断天气——民间传说告诉我们‘湿透的’海藻意味着潮湿阴雨，而‘干燥的’海藻则意味着阳光灿烂。如果它处于一个中间状态（‘有湿气’），我们就无法确定天气如何。然而，天气的状态并没有受限于海藻的状态，所以我们可以在观察的基础上预测天气是雨天或晴天的可能性。另一个有用的线索是前一天的天气状态（或者，至少是它的可能状态）——通过综合昨天的天气及相应观察到的海藻状态，我们有可能更好的预测今天的天气。  
　　这是本教程中我们将考虑的一个典型的系统类型。  
　　首先，我们将介绍产生概率模式的系统，如晴天及雨天间的天气波动。  
　　然后，我们将会看到这样一个系统，我们希望预测的状态并不是观察到的——其底层系统是隐藏的。　　在上面的例子中，观察到的序列将是海藻而隐藏的系统将是实际的天气。  然 后 ， 我 们 将 会 看 到 这 样 一 个 系 统 ， 我 们 希 望 预 测 的 状 态 并 不 是 观 察 到 的 — — 其 底 层 系 统 是 隐 藏 的 。 　 　 在 上 面 的 例 子 中 ， 观 察 到 的 序 列 将 是 海 藻 而 隐 藏 的 系 统 将 是 实 际 的 天 气 。   
　　最后，我们会利用已经建立的模型解决一些实际的问题。对于上述例子，我们想知道：  
　　1. 给出一个星期每天的海藻观察状态，之后的天气将会是什么?  
　　2. 给定一个海藻的观察状态序列，预测一下此时是冬季还是夏季？直观地，如果一段时间内海藻都是干燥的，那么这段时间很可能是夏季，反之，如果一段时间内海藻都是潮湿的，那么这段时间可能是冬季。

### 二、生成模式（Generating Patterns） ###

#### 1、确定性模式（Deterministic Patterns） ####

考虑一套交通信号灯，灯的颜色变化序列依次是红色-红色/黄色-绿色-黄色-红色。这个序列可以作为一个状态机器，交通信号灯的不同状态都紧跟着上一个状态。  
![hmm确定性模式][hmm]  
　　　　  
　　注意每一个状态都是唯一的依赖于前一个状态，所以，如果交通灯为绿色，那么下一个颜色状态将始终是黄色——也就是说，该系统是确定性的。确定性系统相对比较容易理解和分析，因为状态间的转移是完全已知的。

#### 2、非确定性模式（Non-deterministic patterns） ####

为了使天气那个例子更符合实际，加入第三个状态——多云。与交通信号灯例子不同，我们并不期望这三个天气状态之间的变化是确定性的，但是我们依然希望对这个系统建模以便生成一个天气变化模式（规律）。  
　　一种做法是假设模型的当前状态仅仅依赖于前面的几个状态，这被称为***马尔科夫假设***，它极大地简化了问题。显然，这可能是一种粗糙的假设，并且因此可能将一些非常重要的信息丢失。  
　　当考虑天气问题时，马尔科夫假设假定今天的天气只能通过过去几天已知的天气情况进行预测——而对于其他因素，譬如风力、气压等则没有考虑。在这个例子以及其他相似的例子中，这样的假设显然是不现实的。然而，由于这样经过简化的系统可以用来分析，我们常常接受这样的知识假设，虽然它产生的某些信息不完全准确。

一个马尔科夫过程是状态间的转移仅依赖于前n个状态的过程。这个过程被称之为***n阶马尔科夫模型***，其中n是影响下一个状态选择的（前）n个状态。最简单的马尔科夫过程是一阶模型，它的状态选择仅与前一个状态有关。这里要注意它与确定性系统并不相同，因为下一个状态的选择由相应的概率决定，并不是确定性的。  
　　下图是天气例子中状态间所有可能的一阶状态转移情况：  
　　![这里写图片描述][70]  
　　　　  
　　对于有M个状态的一阶马尔科夫模型，共有个状态转移，因为任何一个状态都有可能是所有状态的下一个转移状态。每一个状态转移都有一个概率值，称为状态转移概率——这是从一个状态转移到另一个状态的概率。所有的个概率可以用一个状态转移矩阵表示。注意这些概率并不随时间变化而不同——这是一个非常重要（但常常不符合实际）的假设。  
　　下面的状态转移矩阵显示的是天气例子中可能的状态转移概率：  
![这里写图片描述][70 1]

也就是说，如果昨天是晴天，那么今天是晴天的概率为0.5，是多云的概率为0.375。注意，每一行的概率之和为1。  
　　要初始化这样一个系统，我们需要确定起始日天气的（或可能的）情况，定义其为一个初始概率向量，称为π  π 向量。  
　　![这里写图片描述][70 2]　　　　　　　　  
　　-也就是说，第一天为晴天的概率为1。  
　　现在我们定义一个一阶马尔科夫过程如下：  
　　　状态：三个状态——晴天，多云，雨天。  
　　　π  π 向量：定义系统初始化时每一个状态的概率。  
　　　状态转移矩阵：给定前一天天气情况下的当前天气概率。  
　　任何一个可以用这种方式描述的系统都是一个马尔科夫过程。

#### 3、总结 ####

我们尝试识别时间变化中的模式，并且为了达到这个目我们试图对这个过程建模以便产生这样的模式。我们使用了离散时间点、离散状态以及做了马尔科夫假设。在采用了这些假设之后，系统产生了这个被描述为马尔科夫过程的模式，它包含了一个向量（初始概率）和一个状态转移矩阵。关于假设，重要的一点是状态转移矩阵并不随时间的改变而改变——这个矩阵在整个系统的生命周期中是固定不变的。

### 三、隐藏模式（Hidden Patterns） ###

#### 1、马尔科夫过程的局限性 ####

在某些情况下，我们希望找到的模式用马尔科夫过程描述还显得不充分。回顾一下天气那个例子，一个隐士也许不能够直接获取到天气的观察情况，但是他有一些水藻。民间传说告诉我们水藻的状态与天气状态有一定的概率关系——天气和水藻的状态是紧密相关的。在这个例子中我们有两组状态，观察的状态（水藻的状态）和隐藏的状态（天气的状态）。我们希望为隐士设计一种算法，在不能够直接观察天气的情况下，通过水藻和马尔科夫假设来预测天气。  
　　一个更实际的问题是语音识别，我们听到的声音是来自于声带、喉咙大小、舌头位置以及其他一些东西的组合结果。所有这些因素相互作用产生一个单词的声音，一套语音识别系统检测的声音就是来自于个人发音时身体内部物理变化所引起的不断改变的声音。  
　　一些语音识别装置工作的原理是将内部的语音产出看作是隐藏的状态，而将声音结果作为一系列观察的状态，这些由语音过程生成并且最好的近似了实际（隐藏）的状态。在这两个例子中，需要着重指出的是，隐藏状态的数目与观察状态的数目可以是不同的。一个包含三个状态的天气系统（晴天、多云、雨天）中，可以观察到4个等级的海藻湿润情况（干、稍干、潮湿、湿润）；纯粹的语音可以由80个音素描述，而身体的发音系统会产生出不同数目的声音，或者比80多，或者比80少。  
　　***在这种情况下，观察到的状态序列与隐藏过程有一定的概率关系。我们使用隐马尔科夫模型对这样的过程建模，这个模型包含了一个底层隐藏的随时间改变的马尔科夫过程，以及一个与隐藏状态某种程度相关的可观察到的状态集合***。

#### 2、隐马尔科夫模型（Hidden Markov Models） ####

下图显示的是天气例子中的隐藏状态和观察状态。假设隐藏状态（实际的天气）由一个简单的一阶马尔科夫过程描述，那么它们之间都相互连接。  
　　![hidden-weather-example][]  
　　  
　　隐藏状态和观察状态之间的连接表示：在给定的马尔科夫过程中，一个特定的隐藏状态生成特定的观察状态的概率。这很清晰的表示了‘进入’一个观察状态的所有概率之和为1，在上面这个例子中就是Pr(Obs|Sun), Pr(Obs|Cloud) 及 Pr(Obs|Rain)之和。这里再引用一下读者jiuren的注解：

这里作者是把obs作为参数来用，是说

∑Obs=Dry,Dryish,Damp,Soggy(Obs|Sun)=1  ∑ O b s = D r y , D r y i s h , D a m p , S o g g y ( O b s | S u n ) = 1

;

∑Obs=Dry,Dryish,Damp,Soggy(Obs|Cloud)=1  ∑ O b s = D r y , D r y i s h , D a m p , S o g g y ( O b s | C l o u d ) = 1

;

∑Obs=Dry,Dryish,Damp,Soggy(Obs|Rain)=1  ∑ O b s = D r y , D r y i s h , D a m p , S o g g y ( O b s | R a i n ) = 1

;

除了定义了马尔科夫过程的概率关系，我们还有另一个矩阵，定义为混淆矩阵（confusion matrix），它包含了给定一个隐藏状态后得到的观察状态的概率。对于天气例子，混淆矩阵是：

![weather-b-matrix][]　　  
　　注意矩阵的每一行之和是1。

#### 3、总结（Summary） ####

我们已经看到在一些过程中一个观察序列与一个底层马尔科夫过程是概率相关的。在这些例子中，观察状态的数目可以和隐藏状态的数量不同。

# 我们使用一个隐马尔科夫模型（HMM）对这些例子建模。这个模型包含两组状态集合和三组概率集合： #

# \* 隐藏状态：一个系统的（真实）状态，可以由一个马尔科夫过程进行描述（例如，天气）。 #

# \* 观察状态：在这个过程中‘可视’的状态（例如，海藻的湿度）。 #

# \* 向量：包含了（隐）模型在时间t=1时一个特殊的隐藏状态的概率（初始概率）。 #

# \* 状态转移矩阵：包含了一个隐藏状态到另一个隐藏状态的概率 #

# \* 混淆矩阵：包含了给定隐马尔科夫模型的某一个特殊的隐藏状态，观察到的某个观察状态的概率。 #

# 因此一个隐马尔科夫模型是在一个标准的马尔科夫过程中引入一组观察状态，以及其与隐藏状态间的一些概率关系。 #

### 四、隐马尔科夫模型（Hidden Markov Models） ###

#### 1、定义（Definition of a hidden Markov model） ####

一个隐马尔科夫模型是一个三元组(∏,A,B)  ( ∏ , A , B ) 。∏=(πi)  ∏ = ( π i )   
　　  
　　初始化概率向量：∏=(πi)  ∏ = ( π i )   
　　隐藏状态： A=(aij)  A = ( a i j )   
　　观察状态： B=(bij)  B = ( b i j )   
　　状态转移矩阵： Pr(ait|aji−1)  P r ( a i t | a j i − 1 )  包含了一个隐藏状态到另一个隐藏状态的概率  
　　混淆矩阵： Pr(bi|aj)  P r ( b i | a j )  包含了给定隐马尔科夫模型的某一个特殊的隐藏状态，观察到的某个观察状态的概率。  
　　  
　　在状态转移矩阵及混淆矩阵中的每一个概率都是时间无关的——也就是说，当系统演化时这些矩阵并不随时间改变。实际上，这是马尔科夫模型关于真实世界最不现实的一个假设。  
　　再次强调，只有当测量概率是离散的情况下，我们才能用一个矩阵来表示P(yt|xt)。对于连续的情况，　　比如我们认为观测变量的取值符合高斯分布，也即是概率P(yt|xt)的分布符合高斯分布，那么应该有多少个高斯　　分布呢？显然有多少个隐状态（例如k个），就应该有多少个高斯分布。那么矩阵B就应该变成了由k个高斯分　　布的参数，即σ1,μ1,σ2,μ2,⋯,σk,μk，组成的一个集合。  再 次 强 调 ， 只 有 当 测 量 概 率 是 离 散 的 情 况 下 ， 我 们 才 能 用 一 个 矩 阵 来 表 示 P ( y t | x t ) 。 对 于 连 续 的 情 况 ， 　 　 比 如 我 们 认 为 观 测 变 量 的 取 值 符 合 高 斯 分 布 ， 也 即 是 概 率 P ( y t | x t ) 的 分 布 符 合 高 斯 分 布 ， 那 么 应 该 有 多 少 个 高 斯 　 　 分 布 呢 ？ 显 然 有 多 少 个 隐 状 态 （ 例 如 k 个 ） ， 就 应 该 有 多 少 个 高 斯 分 布 。 那 么 矩 阵 B 就 应 该 变 成 了 由 k 个 高 斯 分 　 　 布 的 参 数 ， 即 σ 1 , μ 1 , σ 2 , μ 2 , ⋯ , σ k , μ k ， 组 成 的 一 个 集 合 。

#### 2、应用（Uses associated with HMMs） ####

一旦一个系统可以作为HMM被描述，就可以用来解决三个基本问题。其中前两个是模式识别的问题：给定HMM求一个观察序列的概率（评估）；搜索最有可能生成一个观察序列的隐藏状态训练（解码）。第三个问题是给定观察序列生成一个HMM（学习）。  
　***a) 评估（Evaluation）***  
　　考虑这样的问题，我们有一些描述不同系统的隐马尔科夫模型（也就是一些(∏,A,B)  ( ∏ , A , B ) 三元组的集合）及一个观察序列。我们想知道哪一个HMM最有可能产生了这个给定的观察序列。例如，对于海藻来说，我们也许会有一个“夏季”模型和一个“冬季”模型，因为不同季节之间的情况是不同的——我们也许想根据海藻湿度的观察序列来确定当前的季节。  
　　我们使用前向算法（forward algorithm）来计算给定隐马尔科夫模型（HMM）后的一个观察序列的概率，并因此选择最合适的隐马尔科夫模型(HMM)。  
　　在语音识别中这种类型的问题发生在当一大堆数目的马尔科夫模型被使用，并且每一个模型都对一个特殊的单词进行建模时。一个观察序列从一个发音单词中形成，并且通过寻找对于此观察序列最有可能的隐马尔科夫模型（HMM）识别这个单词。  
　***b) 解码（ Decoding）***  
　　给定观察序列搜索最可能的隐藏状态序列。  
　　另一个相关问题，也是最感兴趣的一个，就是搜索生成输出序列的隐藏状态序列。在许多情况下我们对于模型中的隐藏状态更感兴趣，因为它们代表了一些更有价值的东西，而这些东西通常不能直接观察到。  
　　考虑海藻和天气这个例子，一个盲人隐士只能感觉到海藻的状态，但是他更想知道天气的情况，天气状态在这里就是隐藏状态。  
　　我们使用Viterbi 算法（Viterbi algorithm）确定（搜索）已知观察序列及HMM下最可能的隐藏状态序列。  
　　Viterbi算法（Viterbi algorithm）的另一广泛应用是自然语言处理中的词性标注。在词性标注中，句子中的单词是观察状态，词性（语法类别）是隐藏状态（注意对于许多单词，如wind，fish拥有不止一个词性）。对于每句话中的单词，通过搜索其最可能的隐藏状态，我们就可以在给定的上下文中找到每个单词最可能的词性标注。  
　***C）学习（Learning）***  
　　根据观察序列生成隐马尔科夫模型。  
　　第三个问题，也是与HMM相关的问题中最难的，根据一个观察序列（来自于已知的集合），以及与其有关的一个隐藏状态集，估计一个最合适的隐马尔科夫模型（HMM），也就是确定对已知序列描述的最合适的(∏,A,B)  ( ∏ , A , B ) 三元组。  
　　当矩阵A和B不能够直接被（估计）测量时，前向-后向算法（forward-backward algorithm）被用来进行学习（参数估计），这也是实际应用中常见的情况。

#### 3、总结（Summary） ####

由一个向量和两个矩阵(∏,A,B)  ( ∏ , A , B ) 描述的隐马尔科夫模型对于实际系统有着巨大的价值，虽然经常只是一种近似，但它们却是经得起分析的。隐马尔科夫模型通常解决的问题包括：  
　　1. 对于一个观察序列匹配最可能的系统——评估，使用前向算法（forward algorithm）解决；  
　　2. 对于已生成的一个观察序列，确定最可能的隐藏状态序列——解码，使用Viterbi 算法（Viterbi algorithm）解决；  
　　3. 对于已生成的观察序列，决定最可能的模型参数——学习，使用前向-后向算法（forward-backward algorithm）解决。

### 五、前向算法（Forward Algorithm） ###

***计算观察序列的概率（Finding the probability of an observed sequence）***

#### 1.穷举搜索（ Exhaustive search for solution） ####

给定隐马尔科夫模型，也就是在模型参数(∏,A,B)  ( ∏ , A , B ) 已知的情况下，我们想找到观察序列的概率。还是考虑天气这个例子，我们有一个用来描述天气及与它密切相关的海藻湿度状态的隐马尔科夫模型(HMM)，另外我们还有一个海藻的湿度状态观察序列。假设连续3天海藻湿度的观察结果是（干燥、湿润、湿透）——而这三天每一天都可能是晴天、多云或下雨，对于观察序列以及隐藏的状态，可以将其视为网格：  
![这里写图片描述][70 3]

网格中的每一列都显示了可能的的天气状态，并且每一列中的每个状态都与相邻列中的每一个状态相连。而其状态间的转移都由状态转移矩阵提供一个概率。在每一列下面都是某个时间点上的观察状态，给定任一个隐藏状态所得到的观察状态的概率由混淆矩阵提供。  
　　可以看出，一种计算观察序列概率的方法是找到每一个可能的隐藏状态，并且将这些隐藏状态下的观察序列概率相加。对于上面那个（天气）例子，将有3^3 = 27种不同的天气序列可能性，因此，观察序列的概率是：

Pr(dry,damp,soggy|HMM)=Pr(dry,damp,soggy|sunny,sunny,sunny)\+Pr(dry,damp,soggy|sunny,sunny,cloudy)\+Pr(dry,damp,soggy|sunny,sunny,rainy)\+....Pr(dry,damp,soggy|rainy,rainy,rainy)  P r ( d r y , d a m p , s o g g y | H M M ) = P r ( d r y , d a m p , s o g g y | s u n n y , s u n n y , s u n n y ) + P r ( d r y , d a m p , s o g g y | s u n n y , s u n n y , c l o u d y ) + P r ( d r y , d a m p , s o g g y | s u n n y , s u n n y , r a i n y ) + . . . . P r ( d r y , d a m p , s o g g y | r a i n y , r a i n y , r a i n y )

用这种方式计算观察序列概率极为昂贵，特别对于大的模型或较长的序列，因此我们可以利用这些概率的时间不变性来减少问题的复杂度。

#### 2.使用递归降低问题复杂度 ####

给定一个隐马尔科夫模型（HMM），我们将考虑递归地计算一个观察序列的概率。我们首先定义局部概率（partial probability）,它是到达网格中的某个中间状态时的概率。然后，我们将介绍如何在t=1和t=n(>1)时计算这些局部概率。  
　　假设一个T-长观察序列是：

(Yk1,Yk2,Yk3,......,Ykt)  ( Y k 1 , Y k 2 , Y k 3 , . . . . . . , Y k t )

##### 2a.局部概率 a′s  a ′ s  #####

考虑下面这个网格，它显示的是天气状态及对于观察序列干燥，湿润及湿透的一阶状态转移情况：  
　![这里写图片描述][70 4]　　  
　　我们可以将计算到达网格中某个中间状态的概率作为所有到达这个状态的可能路径的概率求和问题。  
　　例如，t=2时位于“多云”状态的局部概率通过如下路径计算得出：  
　![paths.to.cloudy][]  
　　我们定义t时刻位于状态j的局部概率为atj  a t j ——这个局部概率计算如下：  
　　atj=Pr(观察状态|隐藏状态j)×Pr(t时刻所有指向j状态的路径）  a t j = P r ( 观 察 状 态 | 隐 藏 状 态 j ) × P r ( t 时 刻 所 有 指 向 j 状 态 的 路 径 ）   
　　对于最后的观察状态，其局部概率包括了通过所有可能的路径到达这些状态的概率——例如，对于上述网格，最终的局部概率通过如下路径计算得出：  
![alphas.at.t\_eq\_3][alphas.at.t_eq_3]　　　  
　　由此可见，对于这些最终局部概率求和等价于对于网格中所有可能的路径概率求和，也就求出了给定隐马尔科夫模型(HMM)最后的观察序列概率。

##### 2b.计算t=1时的局部概率a′s  a ′ s  #####

我们按如下公式计算局部概率：  
　　atj=Pr(观察状态|隐藏状态j)×Pr(t时刻所有指向j状态的路径）  a t j = P r ( 观 察 状 态 | 隐 藏 状 态 j ) × P r ( t 时 刻 所 有 指 向 j 状 态 的 路 径 ）   
　　特别当t=1时，没有任何指向当前状态的路径。故t=1时位于当前状态的概率是初始概率，即Pr(state|t=1)=P(state)  P r ( s t a t e | t = 1 ) = P ( s t a t e ) ，因此，t=1时的局部概率等于当前状态的初始概率乘以相关的观察概率：

a1(j)=π(j)×bjk1  a 1 ( j ) = π ( j ) × b j k 1

所以初始时刻状态j的局部概率依赖于此状态的初始概率及相应时刻我们所见的观察概率。

##### 2c.计算t>1时的局部概率a′s  a ′ s  #####

我们再次回顾局部概率的计算公式如下：  
　　atj=Pr(观察状态|隐藏状态j)×Pr(t时刻所有指向j状态的路径）  a t j = P r ( 观 察 状 态 | 隐 藏 状 态 j ) × P r ( t 时 刻 所 有 指 向 j 状 态 的 路 径 ）   
　　我们可以假设（递归地），乘号左边项“Pr( 观察状态 | 隐藏状态j )”已经有了，现在考虑其右边项“Pr(t时刻所有指向j状态的路径）  P r ( t 时 刻 所 有 指 向 j 状 态 的 路 径 ） ”。  
　　为了计算到达某个状态的所有路径的概率，我们可以计算到达此状态的每条路径的概率并对它们求和，例如：  
![allpath][]　　　　　　  
　　计算a  a 所需要的路径数目随着观察序列的增加而指数级递增，但是t-1时刻a′s a ′s给出了所有到达此状态的前一路径概率，因此，我们可以通过t-1时刻的局部概率定义t时刻的a′s  a ′ s ，即：

at\+1(j)=bjkt\+1∑at(i)aij  a t + 1 ( j ) = b j k t + 1 ∑ a t ( i ) a i j

故我们所计算的这个概率等于相应的观察概率（亦即，t+1时在状态j所观察到的符号的概率）与该时刻到达此状态的概率总和——这来自于上一步每一个局部概率的计算结果与相应的状态转移概率乘积后再相加——的乘积。  
　　注意我们已经有了一个仅利用t时刻局部概率计算t+1时刻局部概率的表达式。  
　　现在我们就可以递归地计算给定隐马尔科夫模型(HMM)后一个观察序列的概率了——即通过t=1时刻的局部概率  a′s  a ′ s  计算t=2时刻的  a′s  a ′ s  ，通过t=2时刻的  a′s  a ′ s  计算t=3时刻的  a′s  a ′ s  等等直到t=T。给定隐马尔科夫模型(HMM)的观察序列的概率就等于t=T时刻的局部概率之和。

##### 2d.降低计算复杂度 #####

我们可以比较通过穷举搜索（评估）和通过递归前向算法计算观察序列概率的时间复杂度。  
　　我们有一个长度为T的观察序列O以及一个含有n个隐藏状态的隐马尔科夫模型l=(,A,B)。  
　　穷举搜索将包括计算所有可能的序列：  
　　　  
　　公式  
　　　　  
　　对我们所观察到的概率求和——注意其复杂度与T成指数级关系。相反的，使用前向算法我们可以利用上一步计算的信息，相应地，其时间复杂度与T成线性关系。  
注：穷举搜索的时间复杂度是2TNT  2 T N T ，前向算法的时间复杂度是N2T  N 2 T ，其中T指的是观察序列长度，N指的是隐藏状态数目。

##### 3.总结 #####

我们的目标是计算给定隐马尔科夫模型HMM下的观察序列的概率——Pr(observations|λ)  P r ( o b s e r v a t i o n s | λ ) 。

*  我们首先通过计算局部概率a′s  a ′ s 降低计算整个概率的复杂度，局部概率表示的是t时刻到达某个状态s的概率。
 *  t=1时，可以利用初始概率(来自于π  π 向量）和观察概率Pr(observation|state)（  P r ( o b s e r v a t i o n | s t a t e ) （ 来自于混淆矩阵）计算局部概率；
 *  t>1时，的局部概率可以利用t-时的局部概率计算。  
    　　因此，这个问题是递归定义的，观察序列的概率就是通过依次计算t=1,2,…,T时的局部概率，并且对于t=T时所有局部概率a′s  a ′ s 相加得到的。
    
    　　注意，用这种方式计算观察序列概率的时间复杂度远远小于计算所有序列的概率并对其相加（穷举搜索）的时间复杂度。

#### 3.前向算法 ####

我们使用前向算法计算T长观察序列的概率:

Yk=Yk1,Yk2,......,YkT  Y k = Y k 1 , Y k 2 , . . . . . . , Y k T

其中y的每一个是观察集合之一。局部（中间）概率  a′s  a ′ s  是递归计算的，首先通过计算t=1时刻所有状态的局部概率  a  a  ：

a1(j)=π(j)⋅bjk1 a 1( j ) = π ( j ) ⋅bjk 1

然后在每个时间点，t=2，… ，T时，对于每个状态的局部概率，由下式计算局部概率  a  a  ：

at\+1(j)=∑i→1n(at(i)aij)bjk1 at \+ 1( j ) =∑i → 1n(a t( i )ai j)bjk 1

也就是当前状态相应的观察概率与所有到达该状态的路径概率之积，其递归地利用了上一个时间点已经计算好的一些值。  
　　最后，给定HMM,,观察序列的概率等于T时刻所有局部概率之和：

Pr(Y(k))=∑j=1naT(j)  P r ( Y ( k ) ) = ∑ j = 1 n a T ( j )

再重复说明一下，每一个局部概率（t > 2 时）都由前一时刻的结果计算得出。  
　　对于“天气”那个例子，下面的图表显示了t = 2为状态为多云时局部概率的计算过程。这是相应的观察概率b与前一时刻的局部概率与状态转移概率a相乘后的总和再求积的结果：  
![example.forward][]

##### 总结（Summary） #####

我们使用前向算法来计算给定隐马尔科夫模型（HMM）后的一个观察序列的概率。它在计算中利用递归避免对网格所有路径进行穷举计算。  
　　给定这种算法，可以直接用来确定对于已知的一个观察序列，在一些隐马尔科夫模型（HMMs）中哪一个HMM最好的描述了它——先用前向算法评估每一个（HMM），再选取其中概率最高的一个。

### 六、维特比算法（Viterbi Algorithm） ###

寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)

对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列，我们常常希望能找到生成此序列最可能的隐藏状态序列。

#### 1.穷举搜索 ####

我们使用下面这张网格图片来形象化的说明隐藏状态和观察状态之间的关系：  
　![这里写图片描述][70 5]  
　我们可以通过列出所有可能的隐藏状态序列并且计算对于每个组合相应的观察序列的概率来找到最可能的隐藏状态序列。最可能的隐藏状态序列是使下面这个概率最大的组合  最 可 能 的 隐 藏 状 态 序 列 是 使 下 面 这 个 概 率 最 大 的 组 合

Pr（观察序列|隐藏状态的组合）  P r （ 观 察 序 列 | 隐 藏 状 态 的 组 合 ）

例如，对于网格中所显示的观察序列，最可能的隐藏状态序列是下面这些概率中最大概率所对应的那个隐藏状态序列：

Pr(dry,damp,soggy|sunny,sunny,sunny),Pr(dry,damp,soggy|sunny,sunny,cloudy),Pr(dry,damp,soggy|sunny,sunny,rainy),....Pr(dry,damp,soggy|rainy,rainy,rainy)  P r ( d r y , d a m p , s o g g y | s u n n y , s u n n y , s u n n y ) , P r ( d r y , d a m p , s o g g y | s u n n y , s u n n y , c l o u d y ) , P r ( d r y , d a m p , s o g g y | s u n n y , s u n n y , r a i n y ) , . . . . P r ( d r y , d a m p , s o g g y | r a i n y , r a i n y , r a i n y )

这种方法是可行的，但是通过穷举计算每一个组合的概率找到最可能的序列是极为昂贵的。与前向算法类似，我们可以利用这些概率的时间不变性来降低计算复杂度。

#### 2.使用递归降低复杂度 ####

给定一个观察序列和一个隐马尔科夫模型（HMM），我们将考虑递归地寻找最有可能的隐藏状态序列。我们首先定义局部概率δ  δ ,它是到达网格中的某个特殊的中间状态时的概率。然后，我们将介绍如何在t=1和t=n(>1)时计算这些局部概率。  
　　这些局部概率与前向算法中所计算的局部概率是不同的，因为它们表示的是时刻t时到达某个状态最可能的路径的概率，而不是所有路径概率的总和。

##### 2a.局部概率delta’s和局部最佳途径 #####

考虑下面这个网格，它显示的是天气状态及对于观察序列干燥，湿润及湿透的一阶状态转移情况：  
　![这里写图片描述][70 6]  
　对于网格中的每一个中间及终止状态，都有一个到达该状态的最可能路径。举例来说，在t=3时刻的3个状态中的每一个都有一个到达此状态的最可能路径，或许是这样的：  
　![这里写图片描述][70 7]  
　我们称这些路径局部最佳路径(partial best paths)。其中每个局部最佳路径都有一个相关联的概率，即局部概率或δ  δ 。与前向算法中的局部概率不同，δ  δ 是到达该状态（最可能）的一条路径的概率。  
　　因而δ(i,t)  δ ( i , t ) 是t  t 时刻到达状态i i的所有序列概率中最大的概率，而局部最佳路径是得到此最大概率的隐藏状态序列。对于每一个可能的i和t值来说，这一类概率（及局部路径）均存在。  
　　特别地，在t=T时每一个状态都有一个局部概率和一个局部最佳路径。这样我们就可以通过选择此时刻包含最大局部概率的状态及其相应的局部最佳路径来确定全局最佳路径（最佳隐藏状态序列）。

##### 2b.计算t=1时刻的局部概率δ′s  δ ′ s  #####

我们计算的局部概率δ  δ 是作为最可能到达我们当前位置的路径的概率（已知的特殊知识如观察概率及前一个状态的概率）。当t=1的时候，到达某状态的最可能路径明显是不存在的；但是，我们使用t=1时的所处状态的初始概率及相应的观察状态k1的观察概率计算局部概率δ  δ ；即

δ1(i)=π(i)bik1  δ 1 ( i ) = π ( i ) b i k 1

——与前向算法类似，这个结果是通过初始概率和相应的观察概率相乘得出的。

##### 2c.计算t>1时刻的局部概率δ′s  δ ′ s  #####

现在我们来展示如何利用t-1时刻的局部概率delta计算t时刻的局部概率δ  δ 。  
　　考虑如下的网格：  
　　![这里写图片描述][70 8]  
　　我们考虑计算t时刻到达状态X的最可能的路径；这条到达状态X的路径将通过t-1时刻的状态A，B或C中的某一个。  
　　因此，最可能的到达状态X的路径将是下面这些路径的某一个  
　　　　　　　（状态序列），…，A，X  
　　　　　　　（状态序列），…，B，X  
或　　　　　　（状态序列），…，C，X  
　　我们想找到路径末端是AX,BX或CX并且拥有最大概率的路径。  
　　回顾一下马尔科夫假设：给定一个状态序列，一个状态发生的概率只依赖于前n个状态。特别地，在一阶马尔可夫假设下，状态X在一个状态序列后发生的概率只取决于之前的一个状态，即

Pr(到达状态A最可能的路径)⋅Pr(X|A)⋅Pr(观察状态|X)  P r ( 到 达 状 态 A 最 可 能 的 路 径 ) ⋅ P r ( X | A ) ⋅ P r ( 观 察 状 态 | X )

与此相同，路径末端是AX的最可能的路径将是到达A的最可能路径再紧跟X。相似地，这条路径的概率将是：

Pr(到达状态A最可能的路径).Pr(X|A).Pr(观察状态|X)  P r ( 到 达 状 态 A 最 可 能 的 路 径 ) . P r ( X | A ) . P r ( 观 察 状 态 | X )

因此，到达状态X的最可能路径概率是：

Pr(Xattimet)=maxi=A,B,CPr(iattime(t−1))×Pr(X|i)×Pr(obs.attimet|X)  P r ( X a t t i m e t ) = max i = A , B , C P r ( i a t t i m e ( t − 1 ) ) × P r ( X | i ) × P r ( o b s . a t t i m e t | X )

其中第一项是t-1时刻的局部概率  δ  δ  ，第二项是状态转移概率以及第三项是观察概率。  
　　泛化上述公式，就是在t时刻，观察状态是kt，到达隐藏状态i的最佳局部路径的概率是：  
　　　　　6.1.2.3\_b  
　　这里，我们假设前一个状态的知识（局部概率）是已知的，同时利用了状态转移概率和相应的观察概率之积。然后，我们就可以在其中选择最大的概率了（局部概率delta）。

[https_blog.csdn.net_daringpig_article_details_8072794]: https://blog.csdn.net/daringpig/article/details/8072794
[http_www.52nlp.cn_hmm-learn-best-practices-four-hidden-markov-models]: http://www.52nlp.cn/hmm-learn-best-practices-four-hidden-markov-models
[wiki_HMM]: http://www.52nlp.cn/hmm-concrete-example-on-wiki
[HMM]: http://www.52nlp.cn/hmm-learn-best-practices-and-cui-johnny-blog
[http_www.comp.leeds.ac.uk_roger_HiddenMarkovModels_html_dev_main.html]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
[http_blogcui.spaces.live.com_blog_cns_46BDB23E24219CE9_144.entry_c_BlogPart]: http://blogcui.spaces.live.com/blog/cns!46BDB23E24219CE9!144.entry?_c=BlogPart
[HMM 1]: http://www.52nlp.cn/several-different-programming-language-version-of-hmm
[http_htk.eng.cam.ac.uk]: http://htk.eng.cam.ac.uk/
[http_www.ghmm.org]: http://www.ghmm.org/
[http_www.kanungo.com_software_software.html]: http://www.kanungo.com/software/software.html
[http_code.google.com_p_jahmm]: http://code.google.com/p/jahmm/
[http_www.cs.ubc.ca_murphyk_Software_HMM_hmm.html]: http://www.cs.ubc.ca/~murphyk/Software/HMM/hmm.html
[http_www.ashrentum.net_jmcejuela_programs_cl-hmm]: http://www.ashrentum.net/jmcejuela/programs/cl-hmm/
[http_hackage.haskell.org_cgi-bin_hackage-scripts_package_hmm]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmm
[HMM 2]: http://www.52nlp.cn/hmm-learn-best-practices-one-introduction
[HMM 3]: https://engineering.leeds.ac.uk/info/20132/school_of_computing
[Link 1]: https://xycui.wordpress.com/2005/06/01/%E9%9A%90%E9%A9%AC%E5%B0%94%E7%A7%91%E5%A4%AB%E6%A8%A1%E5%9E%8Bhmm%E8%87%AA%E5%AD%A6-%EF%BC%881%EF%BC%89/
[hmm]: /images/20220524/c34e7976844741ae858c8c3651e0a046.png
[70]: /images/20220524/1656ee23a43241bdb652b16afc0864f2.png
[70 1]: /images/20220524/b194a68cb19c4de49b541b4bcfeea1d0.png
[70 2]: /images/20220524/03092e0f6ab547d8be0203cf0401def5.png
[hidden-weather-example]: /images/20220524/1344f9e26ff34e87861f845be6e301c3.png
[weather-b-matrix]: /images/20220524/59df1bd0e34b4251b8159aef80c9d10d.png
[70 3]: /images/20220524/5d3b3d59af4a4614941759e1881ac25a.png
[70 4]: /images/20220524/f964b8854cba4cfba807ac8066254e91.png
[paths.to.cloudy]: /images/20220524/bbc3eff3c2f148b39055dbbe984597f9.png
[alphas.at.t_eq_3]: /images/20220524/1d7b7f3682114fd48be124404422376d.png
[allpath]: /images/20220524/9d322c821195472c826f65b1e6a3ebdb.png
[example.forward]: /images/20220524/09160420178c401c84cbe7e6c9dda535.png
[70 5]: /images/20220524/0fdbca77a5d94e6a99be21e9a759a4e3.png
[70 6]: /images/20220524/66ab094a75b1402c81258498ad853791.png
[70 7]: /images/20220524/369588d706bf4d40bc6606bcca4d18de.png
[70 8]: /images/20220524/9be70b40ba294b319cbd57e53dbd84b7.png