1.摘要

在使用搜索引擎或其他工具时经常会用到搜索词联想功能，对于这个功能究竟是怎样实现的却一直是一知半解。本系列文章介绍了一种使用隐马尔可夫过程实现搜索词提示的算法模型，提供了这类问题的一种可能的思路。本文是系列文章的第一篇，主要介绍隐马尔可夫过程的基本概念及应用。

2. 引言

前几日，QQ群里有个人提了两个问题：

1、现有一组关键词，如：{internet; music; video…}，给定一篇文章，请统计出文章中这些关键词分别出现的词频。请描述数据结构、算法，相应的时间复杂度，可以用伪代码加注释或者文字辅助说明的方式。
2、实现搜索的联想功能，比如“liu”出现刘德华，刘若英，在继续输入刘德，就剩1个了。

对于这两个问题，我的第一反应是：
1、做hash，扫描一遍统计次数。
2、字典树，输入的时候遍历字典树当前节点下的子节点，之后将拼音转化为中文。

我认为问题2的答案优化空间很大，但是想了一会又始终不得要领。群里有人回复“马尔可夫链”，在网上搜索一通，似乎和这个问题风马牛不相及，直到找到一篇论文：《基于Markov链的整句输入算法研究与实现》，研究一番，不由得感慨：自己的过去对问题的认识实在太肤浅。

因为精力有限，这里只把马尔可夫链的概念、拼音数据存储的思路整理出来，详细内容还得待以后继续完善。

3. 初识马尔可夫链

1913年1月23日，数学家马尔可夫（Andrey A. Markov）在圣彼得堡发表演讲，讨论了今天被称为马尔可夫链的计算技术。当时他的概率建模理论未受重视，但今天却是科学、统计学和计算科学的基石。任何试图基于海量数据模拟概率事件——如天气、Google搜索和液体行为——都依赖于马尔可夫链。计算复杂系统可能结果的马尔可夫链和马尔可夫性质今天还在进化和扩展。马尔可夫在概率中加入了相互依赖的概念，创作了某种“事件链”。世界不只是一连串的随机事件，世界是复杂的事物，数学帮助揭示出其中隐藏的关联和可能的概率。

马尔可夫链，因俄罗斯数学家安德烈·马尔可夫（俄语：Андрей Андреевич Марков）得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，只有当前的状态用来预测将来，过去（即当前以前的历史状态）对于预测将来（即当前以后的未来状态）是无关的。

在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态,也可以保持当前状态。状态的改变叫做过渡，与不同的状态改变相关的概率叫做过渡概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的(无论之前漫步路径是如何的)。

4. 马尔可夫链的概念

4.1. 马尔可夫性(无后效性)

过程或（系统）在时刻t0所处的状态为已知的条件下，过程在时刻t > t0所处状态的条件分布，与过程在时刻t0之前年处的状态无关的特性称为马尔可夫性或无后效性。

即：过程“将来”的情况与“过去”的情况是无关的。

4.2. 马尔可夫过程

具有马尔可夫性的随机过程称为马尔可夫过程。

考虑一个系统，它在任意时刻t，可能处于N个不同的状态S₁….Sn中的某一个。系统的变化服从某种统计规律，现在我们用q₁…q_t表示系统在t=1,2…时所处的状态，则它们是一个随机变量序列。在t=1时刻，系统所在的状态q₁取决于初识概率矢量π=[π₁,π₂…π_n]，它的每一个分量π_i表示q₁等于S_i的概率，即：
π_i=P(S_i|t=1),i=1…N

4.3. 离散马尔可夫过程

如果马尔科夫过程满足马尔科夫后无效性条件，即：

P[q_t+1=S_j|q_t=S_i,q_t-1=S_k,…]=P[q_t+1=S_j|q_t=S_i]

任一时刻t的状态st都是不可见的。观察者无法观测到一个状态序列:s1,s2……st来推测转移概率等参数。但是每个时刻t会输出一个符号ot，而且ot和st相关且仅与st相关。这个称为独立输出假设。隐含的的状态s1,s2……st是一个典型的马尔科夫链。
则称q_t,t≥1为离散的马尔可夫过程。
如果进一步有P[q_t+1=S_j|q_t=S_i]与时刻t无关，这时称相应的马尔可夫过程是齐次的或时齐的，并引入记号：

a_ij:==P[q_i+1=S_j|q_i=S_i],1≤i,j≤N

有时也简记为P[S_j|S_i]，并称它为相应的马尔可夫过程转移概率，因为它表示处于S_i的系统的下一时刻转移到状态S_j的概率。

4.4. 马尔可夫链

时间和状态都是离散的马尔可夫过程称为马尔可夫链。

4.5. 隐马尔可夫过程

隐马尔可夫过程是一个双重的随机过程，不仅其状态之间的转移是一个随机事件，而且在某一状态转移中表现出的输出也是一个随机事件。隐马尔可夫模型由状态集S'(其中包含初始状态)、输出符号集A*、转移概率P(S_j|S_i)，输出概率q(x|S_i→S_j）以及初始概率π来定义。而转移概率和输出概率满足：

我们可以通过等价转换，使马尔可夫链“可视化”。当某一个状态转移S_i→S_j发生时，输出x的取值空间为{a1,a2…ak}⊂A*，此转移表现出输出ai，其概率分布为：

另一种较为容易理解的表述是：

HMM(Hidden Markov Model,隐马尔科夫模型)是一种用参数表示的用于描述随机过程统计特性的概率模型，是一个双重随机过程, 由两个部分组成:马尔可夫链和一般随机过程。 其中马尔可夫链用来描述状态的转移，用转移概率描述。一般随机过程用来描述状态与观察序列间的关系，用观察值概率描述。 

5. 隐马尔可夫过程的应用

5.1. 评估

根据已知的HMM找出一个观察序列的概率。
这类问题是假设我们有一系列的HMM模型，来描述不同的系统（比如夏天的天气变化规律和冬天的天气变化规律），我们想知道哪个系统生成观察状态序列的概率最大。反过来说，把不同季节的天气系统应用到一个给定的观察状态序列上，得到概率最大的哪个系统所对应的季节就是最有可能出现的季节。（也就是根据观察状态 序列，如何判断季节）。在语音识别中也有同样的应用。
我们会用forward algorithm 算法来得到观察状态序列对应于一个HMM的概率。

5.2. 解码

根据观察序列找到最有可能出现的隐状态序列
例如水藻和天气的例子，一个盲人隐士只能通过感受水藻的状态来判断天气状况，这就显得尤为重要。我们使用viterbi algorithm 来解决这类问题。
viterbi算法也被广泛的应用在自然语言处理领域。比如词性标注。字面上的文字信息就是观察状态，而词性就是隐状态。通过HMM我们就可以找到一句话上下文中最有可能出现的句法结构。

5.3. 学习

从观察序列中得出HMM
这是最难的HMM应用。也就是根据观察序列和其代表的隐状态，生成一个三元组HMM ( ,A,B)。使这个三元组能够最好的描述我们所见的一个现象规律。
我们用forward-backward algorithm 来解决在现实中经常出现的问题–转移矩阵和混淆矩阵不能直接得到的情况。

6. 相关文章

无

7. 参考资料

[1]吴鹏：《基于Markov链的整句输入算法研究与实现》
[2]wiki百科：马尔可夫链
[3]北京大学：隐马尔科夫模型课件
[4]http://blog.sciencenet.cn/blog-641976-533895.html