女朋友的心思你能猜得到吗？——马尔可夫链告诉你
马尔可夫模型（Markov Model）是一种统计模型，广泛应用在语音识别，词性自动标注，音字转换，概率文法等各个自然语言处理等应用领域。经过长期发展，尤其是在语音识别中的成功应用，使它成为一种通用的统计工具。
马尔科夫模型
包括我自己，很多人都不喜欢理论公式。可是，马尔科夫链作为数学分支随机过程的产物，理论部分这里不得不简单提一下。作为数学专业出身的我自己深知数学理论的严谨与描述事物的美妙。
随机过程最早是用于统计物理学的数学方法，研究空间粒子的随机运动。后来这门科学蓬勃发展，随机过程应用的领域越来越广。这里介绍随机过程的一种——马尔科夫链模型。
马尔科夫的无后效性：系统在t>t0时刻所处的状态与系统在t0时刻以前的状态无关，这就是马尔科夫性或者无后效性。
马尔科夫模型具体公式描述如下
有随机过程{Xn,n为整数}，对于任意n和I0,I1,In，满足条件概率：
就称为马尔科夫链。
但凡学过概率论的对这个条件概率应该都能看懂吧！
举例说明
下面是一个马尔科夫模型在天气预测方面的简单例子。如果第一天是雨天，第二天还是雨天的概率是0.8，是晴天的概率是0.2；如果第一天是晴天，第二天还是晴天的概率是0.6，是雨天的概率是0.4。问：如果第一天下雨了，第二天仍然是雨天的概率，第十天是晴天的概率；经过很长一段时间后雨天、晴天的概率分别是多少？
首先构建转移概率矩阵，初学者很容易构建错误：
雨天 | 晴天 | |
0.8 | 0.4 | 雨天 |
0.2 | 0.6 | 晴天 |
注意：每列和为1，分别对雨天、晴天，这样构建出来的就是转移概率矩阵了。
初始状态第一天是雨天，我们记为
这里【1，0】分别对于雨天，晴天。
初始条件：第一天是雨天，第二天仍然是雨天（记为P1）的概率为：
P1 = AxP0
得到P1 = 【0.8,0.2】，正好满足雨天~雨天概率为0.8，当然这根据所给条件就是这样。
下面计算第十天（记为P9）是晴天概率：
A= [0.8 0.4;0.2 0.6];
>> p = [1;0];
>> for i = 1:9
p = A*p;
end
p
p =
0.6668
0.3332
得到，第十天为雨天概率为0.6668，为晴天的概率为0.3332。
下面计算经过很长一段时间后雨天、晴天的概率，显然就是公式（1.1）
直接算A的n次方显然不行，我们知道任意一个可逆矩阵总可以化为（1.2）形式。其中，T为A的特征值对应的两个特征向量组成的矩阵，这两个特征向量分别为【2，1】、【1 -1】。D为一个对角矩阵（1.4）。
那么，我们可以这样算，就简单多了：
显然，当n趋于无穷即很长一段时间以后，Pn = 【0.67，0.33】。即雨天概率为0.67，晴天概率为0.33。并且，我们发现：初始状态如果是P0 =【0，1】，最后结果仍然是Pn = 【0.67，0.33】。这表明，马尔科夫过程与初始状态无关，跟转移矩阵有关。
在马尔可夫模型中，每一个状态都是可观察的序列，是状态关于时间的随机过程，也成为可视马尔可夫模型。隐马尔科夫模型中的状态是不可见的，我们可以看到的是状态表现出来的观察值和状态的概率函数。在隐马模型中，观察值是关于状态的随机过程，而状态是关于时间的随机过程，因此隐马模型是一个双重随机过程。
什么叫状态序列与观察序列呢？举个例子：
假如，有一对男生女生异地恋，根据电影里面情节女生一般会在国外异地，男生在国内。女生每天晚上会根据天气情况（可能会影响心情吧）去干不同的事情，然后会向男生汇报，随着时间的推移会产生一个一天为间隔的时间序列。
女生活动情况受天气影响，天气暂且定为可能为：晴天、多云、阴天，女生活动暂且定为：跑步与读书。
那么，女生只会跟她男友汇报自己跑步还是读书，却不说今天天气如何，对于男友来说，这就相当于知道了观察序列（跑步与读书已经告诉），天气情况（晴天、多云、阴天）确实伴随存在，但是自己不知道。
现在，假设女友告诉男友最近四天自己分别是：跑步、读书、跑步、读书，那么男友应该这样考虑。(这里手动推算很麻烦，只手动推到两天计算)
符号约定：
p1(...)代表第一天，p2(...)代表第二天；
比如：p(晴天，阴天)，代表前一天晴天==》后一天阴天的概率；
这是个条件概率问题：
第一天，跑步，天气可以分为三种情况：晴天、多云、阴天；
p1(晴天跑步) = p1(晴天)*p1(跑步|晴天)
p1(多云跑步) = p1(多云)*p1(跑步|多云)
p1(阴天跑步) = p1(阴天)*p1(跑步|阴天)
那么，第一天跑步概率就是：
p1(跑步)=p1(晴天跑步)+p1(多云跑步)+p1(阴天跑步)
第二天，读书，天气可以分为三种情况：晴天、多云、阴天；
比如第一天晴天，到第二天可能转变成三种状态，即：
晴天====》》》
|---晴天
|---多云
|---阴天
女友会再根据第二天天气决定日常活动是跑步还是读书。
这样推下去，对于第二天每一种天气隐含状态（对于男友来说）都由第一天三种中可能的一种天气转换而来。
那么，第一天跑步、第二天读书概率就会由三部分加起来组成：
同时，第二天晴天也由第一天三种天气状态转变而来，故也由三部分组成：
p2(晴天读书)=p2(晴天)*p2(读书|晴天)
=【p1(晴天跑步)*(晴天,晴天)+p1(多云跑步)*(多云,晴天)，p1(阴天跑步)*(阴天,晴天）】*p2(读书|晴天)
p2(多云读书)=p2(多云)*p2(读书|多云)
=【p1(晴天跑步)*(晴天,多云)+p1(多云跑步)*(多云,多云)，p1(阴天跑步)*(阴天,多云）】*p2(读书|多云)
p2(阴天读书)=p2(阴天)*p2(读书|阴天)
=【p1(晴天跑步)*(晴天,阴天)+p1(多云跑步)*(多云,阴天)，p1(阴天跑步)*(阴天,阴天）】*p2(读书|阴天)
最后，可得第一天跑步、第二天读书概率：
P(p1(跑步),p2(读书))=
p2(晴天读书)+p2(多云读书)+p2(阴天读书)
其实，这就是隐马尔科夫模型中的前向算法计算步骤。
那么，可以归结隐马尔科夫模型的5个组成：
(1)、模型中的状态个数N（例子中天气的三种状态）；
(2)、每个状态的可以输出的不同观测值M（例子中跑步和读书）；
(3)、状态转移矩阵A= {aij}(例子中aij表示从第i种天气转移到第j种天气的概率）；
(4)、发射矩阵B={bj(k)}，例子中表示当第j种天气时女友做第k种活动（跑步或者读书）的概率；
(5)、初始状态概率分布π = {πj}.(例子中第一天为第j种天气的概率）。
手动推演了两天，后面的就有谱了，下面通过Python实现这个问题：
女友告诉男友最近四天自己分别是：跑步、读书、跑步、读书
计算出理论上，四种观察状态的概率分别是多少：
条件是：
Python代码如下：
import numpy as np
A = np.array([[0.5,0.2,0.3],[0.3,0.5,0.2],[0.2,0.3,0.5]])
B = np.array([[0.5,0.5],[0.4,0.6],[0.7,0.3]])
π = np.array([0.2,0.4,0.4])
k = 3
a = B.T[0]*π
print('======================')
print('C语言的编码风格，比较麻烦')
print('第一天')
print(a)
b = [0,0,0]
for t in range(k):
print('第'+str(t+2)+'天')
for i in range(k):
s = 0
if(t%2 == 0):
for j in range(k):
s = s+a[j]*A[j,i]*B[i,1]
b[i] = s
else:
for j in range(k):
s = s+a[j]*A[j,i]*B[i,0]
b[i] = s
a = np.array(b)
print(a)
print('第四天读书概率为：')
print(sum(a))
print('======================')
print('Python语言线性代数运算，简单')
print('第一天')
a1 = B.T[0]*π
print(a1)
a11 = [0,0,0]
for t in range(k):
print('第'+str(t+2)+'天')
if(t%2 == 0):
for i in range(k):
a11[i] = sum(a1*A.T[i]*B.T[1][i])
else:
for i in range(k):
a11[i] = sum(a1*A.T[i]*B.T[0][i])
a1 = np.array(a11)
print(a1)
print('第四天读书概率为：')
print(sum(a1))
结果为：
=====================
C语言的编码风格，比较麻烦
第一天
[ 0.1 0.16 0.28]
第2天
[ 0.077 0.1104 0.0606]
第3天
[ 0.04187 0.035512 0.052836]
第4天
[ 0.0210779 0.02518848 0.01382442]
第四天读书概率为：
0.0600908
=====================
Python语言线性代数运算，简单
第一天
[ 0.1 0.16 0.28]
第2天
[ 0.077 0.1104 0.0606]
第3天
[ 0.04187 0.035512 0.052836]
第4天
[ 0.0210779 0.02518848 0.01382442]
第四天读书概率为：
0.0600908
猜你可能喜欢