马尔可夫与隐马尔可夫模型
写在前面，小学生往往不需要知道极限，二阶导数，高阶导数，他只需要知道怎么求解。
Background requirements：
1、基础的概率学知识
2、动态规划是加分项
3、有实际运用Markov Model的应用会帮助学以致用
NOTE：
对于下面的介绍，我们依据这个节奏， 参考。
1）指定模型参数
2）如何估计这些参数 【这个没有进行介绍】
3）利用这些参数进行预测
这三大类适用于任何统计机器学习模型
马尔可夫链
马尔可夫链（英语：Markov chain），又称离散时间马尔可夫链（discrete-time Markov chain，缩写为DTMC[ 1]），因俄国数学家 安德烈·马尔可夫（俄语：Андрей Андреевич Марков）得名，为 状态空间中经过从一个状态到另一个状态的转换的 随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作 马尔可夫性质。马尔科夫链作为实际过程的统计模型具有许多应用。
一阶马尔可夫如下：
NOTE：下一刻状态如果只由当前状态决定，就叫一阶马尔可夫，如果由当前和前一刻，那就叫二阶，同理。所以有m阶马尔可夫链。m阶马尔可夫如下：
我就不给出很多公式了，就给这几个，理论上这些应该比较好懂了。好了我就不多说了。我个人觉得别的概念这里没有必要说。接下来我们来看隐马尔可夫模型
隐马尔可夫模型
在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中，状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一 概率分布。因此输出符号的序列能够透露出状态序列的一些信息。
HMM有三个典型(canonical)问题:
- 预测(filter)：已知模型参数和某一特定输出序列，求最后时刻各个隐含状态的概率分布，
通常使用 前向算法解决.
- 平滑(smoothing)：已知模型参数和某一特定输出序列，求中间时刻各个隐含状态的概率分布，即求
通常使用 前向-后向算法解决.
- 解码(most likely explanation): 已知模型参数，寻找最可能的能产生某一特定输出序列的隐含状态的序列. 即求
, 通常使用 Viterbi算法解决.【我们这里只关心这个问题，前面的两个不操心】【BTW，HMM是生成模型。。。in case you are interested】
预警
我要抄袭了（整个都是抄的）。这个例子来自维基百科，我们来理解一下隐马尔可夫链，以及Verterbi解码算法怎么运行的。
整个流程是这样的，我们遇到一个问题，他刚好满足了隐马尔可夫的特性，然后我们将问题建模，抽象为一个隐马尔可夫的求解问题，怎么求解呢？使用Viterbi算法。
想象一个乡村诊所。村民有着非常理想化的特性，要么健康要么发烧。他们只有问诊所的医生的才能知道是否发烧。 聪明的医生通过询问病人的感觉诊断他们是否发烧。村民只回答他们感觉正常、头晕或冷。
假设一个病人每天来到诊所并告诉医生他的感觉。医生相信病人的健康状况如同一个离散 马尔可夫链。病人的状态有两种“健康”和“发烧”，但医生不能直接观察到，这意味着状态对他是“隐含”的。每天病人会告诉医生自己有以下几种由他的健康状态决定的感觉的一种：正常、冷或头晕。这些是观察结果。 整个系统为一个隐马尔可夫模型(HMM)。
医生知道村民的总体健康状况，还知道发烧和没发烧的病人通常会抱怨什么症状。 换句话说，医生知道隐马尔可夫模型的参数。我在这里讲解一下隐马尔可夫模型究竟有哪些参数：
H（Hidden state）：隐藏状态集合
O（Observations state）：观测状态集合
SP（Start Probability）：隐藏状态初始化的概率值
HT（Hidden Transition_Probability）：隐藏状态概率转移矩阵
HO（Hidden to Observations Probability，又叫做 emission_probability）：隐藏状态对应到某种观测状态概率集合【我认为emission概率在这里不太好记忆】
这些初始参数这可以用 Python语言表示如下:
Hidden_states = ('Healthy', 'Fever') # 隐状态集合
Observations_states = ('normal', 'cold', 'dizzy') # 观测状态集合
Start_probability = {'Healthy': 0.6, 'Fever': 0.4} # 表示病人第一次到访时医生认为其所处的HMM状态，他唯一知道的是病人倾向于是健康的（可以理解为这是基于一个对大众身体信息的了解得出的初始状态）
Hidden_transition_probability = { # 隐马尔可夫链中身体状态的状态转移概率，我们能够看到，当天健康的人，第二天有30%的概率会发烧
'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
'Fever' : {'Healthy': 0.4, 'Fever': 0.6},
}
Hidden_observations_probability = { # 原来叫emission_probability。这里表示病人每天的感觉的可能性。即，如果他是一个健康人，有50%的可能会感觉正常，40%觉得冷，10%觉得头晕
'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
下面的图片是对代码中的数据的一个刻画，看看就好。
故事继续：病人连续三天看医生，医生发现第一天他感觉正常，第二天感觉冷，第三天感觉头晕。 于是医生产生了一个问题：怎样的健康状态序列最能够解释这些观察结果。维特比算法解答了这个问题。
# Helps visualize the steps of Viterbi.
def print_dptable(V): # 打印dp矩阵
print (" "),
for i in range(len(V)):
print("%7d" % i)
print()
for y in V[0].keys():
print ("%.5s: " % y)
for t in range(len(V)):
print ("%.7s" % ("%f" % V[t][y]))
print()
def viterbi(obs, states, start_p, trans_p, h2o_p): # Viterbi算法
V = [{}]
path = {}
# Initialize base cases (t == 0)
#
for y in states:
V[0][y] = start_p[y] * h2o_p[y][obs[0]]
# 初始状态，由start的概率，对应乘上发射概率，即由隐状态到观测状态的可能性
path[y] = [y] # 记录下相应的路径
# Run Viterbi for t > 0，每天都要更新计算一遍
for t in range(1,len(obs)):
V.append({})
newpath = {}
for y in states:
# 对于每个状态，计算其由前一天的各个状态，到达今天的y的概率大小，与y0自身相比较，取最大值
# 前一天到达今天的每个状态对应的路径大小都计算了，取最大值。作为V[t][y]的值，并更新路径
(prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * h2o_p[y][obs[t]], y0) for y0 in states])
V[t][y] = prob
newpath[y] = path[state] + [y]
# Don't need to remember the old paths
path = newpath
print_dptable(V)
# 最后一天
(prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
return (prob, path[state])函数viterbi 具有以下参数: obs 为观察结果序列, 例如 ['normal', 'cold', 'dizzy']； states 为一组隐含状态； start_p 为起始状态概率; trans_p 为隐藏状态转移概率; 而 h2o_p 为隐藏状态到观测状态的放射概率。 为了简化代码，我们假设观察序列 obs 非空且 trans_p[i][j] 和 h2o_p[i][j] 对所有状态 i,j 有定义。
在运行的例子中正向/维特比算法使用如下:
def example():
return viterbi(Observations_states,
Hidden_states,
Start_probability,
Hidden_transition_probability,
Hidden_observations_probability)
print(example())完整代码，参考：
an维特比算法揭示了观察结果 ['normal', 'cold', 'dizzy'] 最有可能由状态序列 ['Healthy', 'Healthy', 'Fever']产生。 换句话说，对于观察到的活动, 病人第一天感到正常，第二天感到冷时都是健康的，而第三天发烧了。
下图是一个计算过程：
P(finalstate) = P(y_{1})*P(x_{1}|y_{1})\prod_{i=2}^{n}P(y_{i}|y_{i-1})P(x_{i}|y_{i})
其中，P(y1)是初始状态（即医生假设的身体状态分布），P（x1|y1）是第一天的观测状态，即我们这里说的病人第一天说自己是正常的。最后我们要求的就是概率最大的那个finalstate。每一天都累乘，最后求得的结果就是最后的状态对应的概率。
最后我们得到，健康的概率是：0.00588，发烧的概率是：0.01512。相信医生就可以很容易的做出诊断了。
分词实例：
请同学麻烦将观测结果换成标注结果，状态序列换成汉字。然后代入，理论上就可以理解了。
拼音输入法：
看到一个哥们写了一个拼音输入法的code，很有意思，感觉没太看明白解析，就在这里做了一步步的推导。当然，代码不能这么写，不然跑不动。。。解码要用viterbi。
NOTE：
在实现维特比算法时需注意许多编程语言使用 浮点数计算，当 p 很小时可能会导致结果 下溢。 避免这一问题的常用技巧是在整个计算过程中使用 对数概率，在 对数系统中也使用了同样的技巧。 当算法结束时，可以通过适当的幂运算获得精确结果。
之后我们还要继续了解CRF。
本质上，CRF和HMM都是试图从训练数据中统计找到发射概率和转移概率。但是CRF可以定义更多的特征来学习【以下内容取自李宏毅老师的ppf】
而且其学习过程更加优化：
文章被以下专栏收录
