马尔可夫模型用于哪些方面的预测（从马尔可夫模型到贝叶斯网络）

概率知识：

1--P(a,b)=p(a|b)p(b)

2--P(a,b,c)可以看成p(a,y)其中y为b，c

P(a,y)=p(a|y)p(y)将y为b，c带回去

P(a,b,c)=p(a|b,c)p(b,c)=p(a|b,c)p(b|c)p(c)

3—p(A|B)=p(A)则表示A与B之间是独立的

4—p(AB|C)=p(A|BC)p(B|C)

这个公式如果把C去掉就可以看成P(AB)=P(A|C)P(B)

贝叶斯网络(有向无环图)：把某个研究系统中涉及到的随机变量根据是否条件独立绘制在一个有向图中，这就形成了贝叶斯网络。每个变量作为一个结点，如果变量和变量不独立，那么就连接一条边，独立那就没有边，这样一个图就叫做贝叶斯网络。

全连接贝叶斯网络：每一对结点之间都有变量来连接，我们看一下k个变量的联合分布怎么表示：

但是我们需要知道一个问题：在实际操作中，一个正常的贝叶斯网络有些边是缺失的。例如下面这个：

对应的表达式为：

直观上看，x1和x3独立。

下面介绍三种在贝叶斯网络中判断条件独立的情况：

为了说清楚这个问题，需要引入D-Separation（D-分离）这个概念。D-Separation是一种用来判断变量是否条件独立的图形化方法。换言之，对于一个DAG(有向无环图)E，D-Separation方法可以快速的判断出两个节点之间是否是条件独立的。

tail-to-tail

在x1给定的条件下，x2、x3被阻断，是独立的。

条件独立：tail-to-tail

head-to-tail

在x2给定的条件下，x1、x3被阻断，是独立的。

条件独立：head-to-tail

无条件独立（head-to-head）

在x3未知的情况下，x1、x2被阻断，x1、x2无条件独立。

算法过程

选择变量的一个合理顺序：x1，x2,……xn

对于i=1到n

在网络中添加xi节点

在x1，x2……xn中选择xi的父母，使得：

这种构造方法，显然保证了全局的语义要求：

样本属性值缺失（EM算法）

结构已知，样本不完整，可采用EM算法：

初始化：随机各节点的条件概率分布

E-step：根据各节点已有条件概率分布，补全样本（如果连续则补全为均值，离散补全为出现概率最大的值）

M-step：根据“完整”的观测值使用最大似然估计或者统计来得到新的各节点概率分布，替换原有值。

特殊的贝叶斯网络：马尔可夫模型：

结点形成一条链式的网络，称为马尔可夫模型（伪随机数发生器就是使用这个原理的），Aj 1只与Aj有关，与A1到Ai-1没有关系。任何一个结点都与它的前驱有关。

贝叶斯网络也称为概率图，它的任务就是如何对一个联合概率分布p(x1,x2,x3……xn)有效表示。因为只要知道了联合分布，就会知道所有的信息,比如任何一个变量的概率，或者任何一个变量在其它变量条件下的概率等。

如果我们直接对这个联合分布进行建模，那么我们的参数就会以指数级别的形式增长，这是维度灾难，比如我们三个变量的联合分布p(x1,x2,x3)，prob为此时条件下的联合概率，全部情况下的prob相加的值为1：

我们每个事件都有0不发生的和1发生这两种情况，那我们最终这个联合分布的情况就有2³，如果要是有n个变量的话，那这个联合分布的参数真的是太大了（2的n次方），所以不能对联合分布的每一种情况都进行存储，那么我们的概率图模型实际上就是想解决这个问题。

那么概率图模型是怎么解决这个问题的呢？而实际上，x1，x2，x3之间可能会有一些关系，比如x1取决于x2，x2取决于x3，所以我们可以以图的形式来对每一个变量来进行建模，如果我们不知道x1、x2、x3之间的关系的时候，我们得硬求这个联合分布，但现在假如我们有这种知识时候（x1，x2，x3之间的关系），我们就可以减少这个存储的空间，那么我们就可以建立有向无环的概率图模型，我们来看一个例子，就可以清楚的知道了概率图模型做了什么？

这是原始的概率分布的图像，它一共有四个变量，因为每个变量都有0和1两种情况，所以我们的联合分布P（c，s，r，w）有16种情况，但是如果我们要是使用概率图模型的话，根据变量之间的关系，这种先验知识，我们可以将上面的原始分布表示为：

我们看一下此时有几种情况，c有1种情况，s由c决定有2种（0，1）情况，r由c决定有2种（0，1）情况，w由s和r决定所以有4种（00，01，10，11）情况，所以我们用上面的这种概率图表示的话，我们只有9种情况，比16种情况少了7种，但是它表达的就是16种情况的意思。

我们可以将此时的联合分布表示为：P(c,s,r,w)=p(c)p(s|c)p(r|c)p(w|s,r)

如果我们现在知道了P(c,s,r,w)=p(c)p(s|c)p(r|c)p(w|s,r)其实我们现在应该就已经可以求出一切了。

比如我们可以求p（s=1），我们发现无论是原始的分布还是现在的概率图我们都很难直接看出p(s=1),那么它怎样可以求出来呢？

方式一：直接使用原始的分布方式：

我们只看s这一列，其它的我们不看，我们看s=1时prop加起来一共为多少，我们使用概率的方式来表示就是：

这个表示我们要求p(s=1)，那就相当于将联合概率p(c,R,w,s=1)的c，R，W全部忽略掉（积分），然后求和。

我们使用这个方法可以得到p(s=1)，问题是我们一般应该使用的是概率图（贝叶斯网络）而不是原始概率图,那么我们概率图的联合概率是p(c)p(s|c)p(r|c)p(w|s,r)，那么我们要在这个联合概率的基础上求p(s=1),可以得出：

这个表示，在概率图的形式下求p(s=1)，也就是将c、R、w全部都积掉。那么它具体怎么求呢？

这种计算的方式很暴力，我们知道s=1是固定的，但是c、r、w确不是，所以c、r、w一共有8中组合，我们算出这8中组合的prop，然后加起来就是p(s=1)的了。 就是三个for循环：

这个就很好求了，因为比如p（w=0|s=1,R=0）这样的条件概率我们都可以在我们贝叶斯网络的小概率表查到：

这样我们就通过这种方式来算出了p(s=1)的情况，但是此时其实还是有一个问题，就是算得太费事了，所以我们可以使用动态规划（变量消除）的方式来完成这个任务：

P(c=0)=0.5

P(s=1 | c=0)=0.5

P(s=1 | c=1)=0.1

P(c=1)=0.5

我们来简要分析一下这个过程，它是先对w，所以我们就将①这一部分中有w来拿出来：

因为w在|前面，我们将w消掉，那么|前面什么都没有了，所以这部分为1，

然后它又对r，所以我们将此时将②这部分中和r有关的单独放到一边，我们可以得到这部分也是1

所以最终我们的式子变成了：

那么c有两种可能0或1，我们将其展开就好了，那么此时我们的for循环就不是嵌套的了，而是：

嵌套for循环算也好，这样的for循环算也好，虽然算出来是精确值，但是总的来说计算成本算是比较高的，我们可以使用Gibbs采样来算出一个近似值。

概率图的应用一：朴素贝叶斯（简单的概率图模型）

上图就是朴素贝叶斯对应的贝叶斯网络图，它的变量x1到xn都是独立的没有任何关系，这个可以看成是垃圾邮件的分类例子，就是说是y否是垃圾邮件取决于它是否出现x1，是否出现x2，是否出现xn，这就是朴素贝叶斯的概率图表示，对应全概率公式就是：

这个概率公式就是垃圾邮件的朴素贝叶斯公式了

概率图应用二：马尔科夫模型（Markov model）

我们可以写出它的全概率公式p(A1,A2,…,An)=p(A1)P(A2|A1)…P(An|An-1)

我们有了全概率公式了，那么我们就有了一切了。

假如我们现在有一个这样的马尔可夫模型：

这个模型此时的全概率公式就是p(x1,x2,x3,x4)=p(x1)p(x2|x1)p(x3|x2)p(x4|x3)

有了这个全概率公式我们就可以求出所有我们想要求出来的东西：

比如我们想p（x4）我们可以使用那么求法如下（暴力方式）：

或者使用动态规划的方法来计算：

最终我们可以看出x4只和x3有关系

因为x1在|后面所以消掉x1之后，整体并不会变成1，而是变成了p(x2)

举一个马尔可夫模型的例子，一个城市的天气只能是天晴和下雨，现在我们拿到了前一天的天气情况和今天天气情况的关系，那么我们可以使用它来建立马尔科夫模型。

马尔科夫模型中前后结点的关系就是我们上表表的内容了。它可以理解为我们现在知道昨天是天晴（概率1，百分百天晴）然后今天是晴天的概率是0.9，昨天是天晴（概率1，百分百天晴）然后今天是下雨（概率1，百分百天下雨）的概率是0.1，昨天是下雨（概率1，百分百天下雨）然后今天是天晴的概率是0.3，昨天是下雨然后今天下雨的概率是0.7

我们将上面的用状态图来表示一下：

注意这个并不是马尔科夫模型，它只是p(ti|ti-1)的一种比较方便的表达形式而已，或者这样表达也行：

马尔可夫模型我们知道，xi只与xi-1有关，所以我们得到马尔可夫模型的全概率公式之后，我们想要得到某一个结点的概率，我们对其进行积分我们可以看出该结点只与该结点前驱有关，所以p(x2)等于（可以弄出联合分布，然后把没有用的x全部积分）

P(x2)=p(x1=1)P(x2|x1=1) p(x1=0)p(x2|x1=0)

如果P(x2)求的是x2=0也就是天气晴朗的概率

其中p(x2|x1=1)=p(x2=0|x1=1)=0.3

P(x2|x1=0)= p(x2=0|x1=0)=0.9

这个可以根据我们的先验知识来获取出来

而p(x1=1)p(x1=0)这个是我们马尔可夫链第一个结点的情况，这个我们也应该提前知道，因为这个不知道我们就没有办法来建立我们的马尔可夫链。

所以只要有了联合分布，我们可以求出所有的东西

我们上面计算p(x2)我们可以从全概率的角度，然后积掉所有没有用的变量，使用这种方式来求p(x2)。

我们试着想一下，我们求p(x2)我们只需知道：p(x1=1)P(x2|x1=1) p(x1=0)p(x2|x1=0)，所以p(x2)是很好求的。

如果我们要求p(x100)的那么我们需要知道：p(x99=1)P(x100|x99=1) p(x99=0)p(x100|x99=0)

但是问题是我们要想知道p（x99）还需要p(x98),所以我们可以说马尔可夫模型虽然t结点只和t-1结点有关，但是t-1结点和t-2结点有关，所以要想求p(x98)肯定还需要前面的所以我们的各个结点的情况实际上得从第一个结点开始一步一步的来求。

我们构建一个马尔可夫模型我们一般知道两个方面，一个方面是第一个结点的概率情况，还有上一个结点和这一个结点之间的条件概率情况。只要知道这两个方面的情况我们就可以构建出马尔可夫模型了。

上一个结点和这一个之间的条件概率我们可以写成马尔可夫矩阵的形式：

使用这个马尔可夫矩阵，我们可以将第二个结点和第一个结点之间的关系表示为：

这个表示x1结点的概率情况左乘马尔可夫矩阵就是x2结点的概率情况，我们来实际算一下假如x1结点的p(x1=0)=1，而p(x1=0)=0，那么x2结点的情况是p(x2=1)=0.9而p(x2=0)=0.1

所以我们使用马尔可夫矩阵 初始结点x1的概率情况我们就可以建立马尔可夫链

我们来看两条马尔可夫链：

第一条链中初始结点x1是百分百晴天，第二条链中初始结点x2百分百是下雨天，我们的马尔可夫矩阵都是一样的：

我们可以发现最后一个结点两条马尔可夫链竟然是一样的，我们称为稳定态，这说明马尔可夫链会走着走着忘记自己是怎么来的，它是无记忆性的。

证明：马尔可夫模型为什么初始状态不一样，但是最终的状态确是一样的？

再次之前，我们先来补充一点数学上的知识

AX=λX，则A是矩阵，X是A矩阵的特征向量，λ是矩阵A的特征值。

矩阵的幂：

AX=λX-> A²X=λ²X-> A³X=λ³X

那么我们在来看一下我们的第一条马尔可夫链：

这条链是这样的出来的：

A表示马尔可夫矩阵

X2=AX1

X3=AX2=AAX1=A²X1

X4=AX3=AAX2=AAAX1=A³X1

……

Xn=An-1（A的n次方）x1

我们再来看一下我们的马尔可夫矩阵，假如这个矩阵有n个特征向量（c1，c2，c3……cn），如果n个特征向量是线性独立的，那么，马尔可夫模型是有稳定态的。

因为这n个特征向量是线性独立的所以我们可以用它们来表示一下向量x1（也就是初始结点的状态）

X1=a1c1 a2c2 …… ancn

同乘A的n-1次放

An-1 *x1

= An-1（a1c1 a2c2 …… ancn）

=a1λ1n-1c1 ……anλ1n-1cn

这里还有一个关键点是：马尔可夫矩阵终必有一个特征值是1，其它特征值小于1

那么我们可以假设λ1=1，其它lambda<1

所以λ1的n-1次方为1，而其它λ的n-1次方为0

= a1c1

最终An-1 *x1稳定态

=a1c1

所以总结一句话就是马尔可夫链的稳定态是马尔可夫矩阵中特征值为1的特征向量的非整数倍。

应用三HMM隐马尔可夫模型

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

我们先看一下隐马尔可夫模型中的一个子结构:

这个可以看为一个隐马尔可夫模型中的子结构，其中x是隐藏变量（这个是我们所不能现实看到的），而y是观测变量，这个是我们能够看到的。我们的目的就是通过观测到的变量来推测隐藏的变量。用概率表示就是p(x=?|y=?),这个表示为观测到y怎么样的时候，我们推测x怎么样？

我们可以看出这个子结构不就是概率图模型吗？而且是只有两个变量的概率图模型，那么P(XY)=P(X)P(Y|X),如果我们对P(X)和P(Y|X)建模的话，那么我们就知道了联合分布P(XY)了，只要知道了联合分布，我们就能解决所有的问题了。

我们把X看作是心情，把y看作是行为，一个人的行为是由心情决定的，心情好的时候和心情不好的时候行为是不一样的。所以当我们知道了P(X),心情好和心情不好的比率，以及p(Y=？|X=？)这个表示心情X时做y这件事情的比率，我们就可以知道了P(XY)，我们就可以返回过来推断p（X=？|Y=？）也就是我们观测到一个人行为Y的时候，我们推测这个人的心情X。

那么我们现在已经知道了一个马尔可夫模型的子结构也就是局部的模型，那么马尔可夫模型是什么样的呢？

如果我们只看到一个人刷了一次头条y，我们就判断这个人是开心x的这是不科学的，那么就说明一个子结构是不能解决我们对心情的预测的。

真正的应该是一个人看头条，然后看头条，然后看头条，我们通过这三个行为推断出这个人是好心情还是比较靠谱的，也就是说经过一系列的观测，从而得出心情的变化还是比较靠谱的，所以设计出来下面的这种概率模型：

X1表示t1时刻的心情，而y1表示t1时刻的行为，以此类推，每一刻都会有一个行为，对应一个心情，这就是隐马尔可夫模型，其中x表示隐变量。

我们实际上只能看到y，而yt仅仅取决于我此时的心情xt而和其它变量没有关系，我们写出上面模型的联合分布表达式：p(x1,x2,x3,y1,y2,y3)=p(x1)p(y1|x1)p(x2|x1)p(y2|x2)p(x3|x2)p(y3|x3),所以我们要得到这个联合分布，那么就能解决HMM的所有问题，我们要知道两个模型p(xt|xt-1),p(yt|xt),就可以获得联合分布了。

其实我们得到联合分布之后，我们主要解决的问题是p(xt|y1:t)也就是1到t时刻的行为决定t时刻的心情xt的问题。

我们要想计算p(xt|y1:t)分成两步：

首先我们需要计算p(Xt|Y 1:t-1),然后计算p(Xt|Y1:t),因为在计算p(Xt|Y1:t)的过程中需要使用p(Xt|Y 1:t-1)。

要想计算我们需要一些技巧：

这个技巧就是计算P(A|C)的时候，我们可以加上一个B，然后再积B，这二者是一致的，这个下面我们要用到，我们称它为技巧一

这个我们称为技巧二

具体过程如下所示：

第一步是我们使用了技巧1，加上了一个Xt-1，然后我们通过技巧2转成第二个式子

我们通过这个局部可以看出来只要Xt-1确定的时候，xt和yt-1独立的，所以可以将yt-1去掉，最终得到：

利用第一步的结果来计算p(xt|Y1:t)

计算出来这个之后，我们就解决了p(xt|Y1:t)的问题，这样是隐马尔可夫模型中最经典的问题。

,