《转移矩阵&马尔科夫链.doc》由会员分享，可在线阅读，更多相关《转移矩阵&马尔科夫链.doc（6页珍藏版）》请在金锄头文库上搜索。
1、转移概率矩阵转移概率矩阵（又叫跃迁矩阵，英文名：transition matrix）是俄国数学家马尔科夫提出的，他在20世纪初发现：一个系统的某些因素在转移中，第n次结果只受第n-1的结果影响，即只与当前所处状态有关，而与过去状态无关。 在马尔科夫分析中，引入状态转移这个概念。所谓状态是指客观事物可能出现或存在的状态；状态转移是指客观事物由一种状态转移到另一种状态的概率。 例如对应于一个天气预报的问题，若天气状态转移概率表如左下： （其中列表示今天的状态，行表示明天的状态。注意每一列之和为1，因为已假设明天仅这三种状态。）图1.天气转移概率矩阵明/今晴阴雨晴3/41/21/4阴1/81/41/
2、2雨1/81/41/4写作矩阵形式为图1所示。其中转移矩阵 A的每一个元素都表示从今天的一种状态到明天的一种状态的概率，例如，第2行第3列的值为1/2，这表示今天下雨而明天转阴的概率是1/2。称A为转移矩阵。马尔可夫链1原理简介马尔可夫链（Markov Chain），描述了一种状态序列，其每个状态值取决于前面有限个状态1。马尔可夫链是具有马尔可夫性质的随机变量的一个数列。这些变量的范围，即它们所有可能取值的集合，被称为“状态空间”，而的值则是在时间n的状态。如果对于过去状态的条件概率分布仅是的一个函数，则这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。2理论发展马尔可夫在19
3、06年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）。马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。3过程马尔可夫过程的定义：设是一个随机过程，如果在在时刻所处的状态为已知时，与它在时刻之前所处的状态无关，则称具有马尔可夫性。设的状态空间为S,如果对于任意的n2,任意的,在条件下,X(tn)的条件
4、分布函数恰好等于在条件下的条件分布函数，即则称为马尔可夫过程。马尔可夫过程，能为给定样品文本，生成粗略，但看似真实的文本：他们被用于众多供消遣的“模仿生成器”软件。马尔可夫链还被用于谱曲。它们是后面进行推导必不可少的条件：尺度间具有马尔可夫性质.随机场从上到下形成了马尔可夫链，即 的分布只依赖于 ,与其他更粗 糙的尺度无关，这是因为 已经包含了所有位于其上层的尺度所含有的信息. 随机场像素的条件独立性.若 中像素的父节点已知，则 中的像素彼此独立.这一性质使我们不必再 考虑平面网格中相邻像素间的关系，而转为研究尺度间相邻像素（即父子节点）间的关系. 设在给定的情况下,Y 中的像素彼此独立. 可
5、分离性.若给定任一节点 ,则以其各子节点为根的子树所对应的变量相互独立.从只有一个节点的根到和图像大小一致的叶子节点，建立了完整的四叉树模型，各层间的马尔可夫链的因 果关系使我们可以由非迭代的推导过程快速计算出 X 的最大后验概率或后验边缘概率.4模型完整的四叉树模型也存在一些问题. 因概率值过小，计算机的精度难以保障而出现下溢，若层次多，这一 问题更为突出.虽然可以通过取对数的方法将接近于 0 的小值转换成大的负值，但若层次过多、概率值过小，该 方法也难以奏效，且为了这些转换所采用的技巧又增加了不少计算量. 当图像较大而导致层次较多时，逐层的计算甚为繁琐。下溢现象肯定会出现，存储中间变量也会
6、占用大量空间，在时间空间上都有更多的开销. 分层模型存在块效应，即区域边界可能出现跳跃，因为在该模型中，同一层随机场中相邻的像素不一定有同 一个父节点，同一层的相邻像素间又没有交互，从而可能出现边界不连续的现象.5 MRF为了解决这些问题，我们提出一种新的分层 MRF 模型半树模型，其结构和图15类似，仍然是四叉树，只是层数比完整的四叉树大大减少，相当于将完整的四叉树截为两部分，只取下面的这部分.模型最下层仍和图像 大小一致，但最上层则不止一个节点.完整的四叉树模型所具有的性质完全适用于半树模型，不同点仅在于最上层,完整的树模型从上到下构成 了完整的因果依赖性，而半树模型的层间因果关系被截断，
7、该层节点的父节点及祖先均被删去，因此该层中的各 节点不具有条件独立性，即不满足上述的性质2,因而对这一层转为考虑层内相邻节点间的关系.半树模型和完 整的树模型相比，层次减少了许多，这样，层次间的信息传递快了，概率值也不会因为过多层次的逐层计算而小 到出现下溢.但第 0 层带来了新的问题，我们必须得考虑节点间的交互，才能得出正确的推导结果，也正是因为在 第 0 层考虑了相邻节点间的影响，使得该模型的块现象要好于完整的树模型.对于层次数的选取，我们认为不宜多，太多则达不到简化模型的目的，其优势体现不出来，但也不能太少，因为第0 层的概率计算仍然要采用非迭代的算法，层数少表明第0 层的节点数仍较多，
8、计算费时，所以在实验中将 层数取为完整层次数的一半或一半稍少.MPM 算法3半树模型的 MPM 算法图像分割即已知观测图像 y,估计 X 的配置，采用贝叶斯估计器，可由一个优化问题来表示：?x = arg min E C ( x,x ） | Y = y,x其中代价函数 C 给出了真实配置为 x 而实际分割结果为 x时的代价.在已知 y 的情况下，最小化这一代价的期 望，从而得到最佳的分割.代价函数取法不同得到了不同的估计器，若 C(x,x）=1?(x,x）（当 x=x时(x,x）=1,否则 (x,x）=0)得到的是 MAP 估计器，它意味着 x 和 x只要在一个像素处有不同，则代价为 1,对误
9、分类的惩罚比较重，汪西莉 等：一种分层马尔可夫图像模型及其推导算法而在实际中存在一些误分类是完全允许的.若将半树模型的 MPM 算法记为 HT-MPM,它分为向上算法和向下算法两步，向上算法自下而上根据式、 式 逐层计 算P(yd(s)|xs)和 P(xs,x(s)|yd(s)），对最下层 P(yd(s)|xs)=P(ys|xs). 向下算法自上 而下根据 式 逐层计算 P(xs|y)，对最上层由 P(x0|y)采样 x0，,x0(n),6详细说明马尔可夫链，因安德烈马尔可夫(A.A.Markov,18561922)得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信
10、息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。时间和状态都是离散的马尔可夫过程称为马尔可夫链，简记为Xn = X(n),n = 1,2,3,4。马尔可夫链是随机变量的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而Xn的值则是在时间n的状态。如果Xn + 1对于过去状态的条件概率分布仅是Xn的一个函数，则P(Xn+1=x|X0,X1,X2,.Xn)=P(Xn+1=x|Xn)马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。马尔可夫链
11、是满足下面两个假设的一种随机过程：1、t+l时刻系统状态的概率分布只与t时刻的状态有关，与t时刻以前的状态无关；2、从t时刻到t+l时刻的状态转移与t的值无关。一个马尔可夫链模型可表示为=(S,P,Q)，其中各元的含义如下：1)S是系统所有可能的状态所组成的非空的状态集，有时也称之为系统的状态空间，它可以是有限的、可列的集合或任意非空集。本文中假定S是可数集（即有限或可列）。用小写字母i,j（或Si,Sj)等来表示状态。2)P是系统的状态转移概率矩阵，其中Pij表示系统在时刻t处于状态i,在下一时刻t+l处于状态j的概率,N是系统所有可能的状态的个数。对于任意is,有。3)Q是系统的初始概率分
12、布,qi是系统在初始时刻处于状态i的概率，满足。基本性质马尔可夫链模型的性质马尔可夫链是由一个条件分布来表示的P(Xn + 1 | Xn)这被称为是随机过程中的“转移概率”。这有时也被称作是“一步转移概率”。二、三，以及更多步的转移概率可以导自一步转移概率和马尔可夫性质：同样：这些式子可以通过乘以转移概率并求k1次积分来一般化到任意的将来时间n+k。边际分布P(Xn)是在时间为n时的状态的分布。初始分布为P(X0)。该过程的变化可以用以下的一个时间步幅来描述：这是Frobenius-Perron equation的一个版本。这时可能存在一个或多个状态分布满足：其中Y只是为了便于对变量积分的一个
13、名义。这样的分布被称作是“平稳分布”(Stationary Distribution)或者“稳态分布”(Steady-state Distribution)。一个平稳分布是一个对应于特征根为1的条件分布函数的特征方程。平稳分布是否存在，以及如果存在是否唯一，这是由过程的特定性质决定的。“不可约”是指每一个状态都可来自任意的其它状态。当存在至少一个状态经过一个固定的时间段后连续返回，则这个过程被称为是“周期的”。离散状态离散状态空间中的马尔可夫链模型如果状态空间是有限的，则转移概率分布可以表示为一个具有(i,j)元素的矩阵，称之为“转移矩阵”：Pij = P(Xn + 1 = i | Xn =
14、j)对于一个离散状态空间,k步转移概率的积分即为求和，可以对转移矩阵求k次幂来求得。就是说，如果是一步转移矩阵，就是k步转移后的转移矩阵。平稳分布是一个满足以下方程的向量：在此情况下，稳态分布 * 是一个对应于特征根为1的、该转移矩阵的特征向量。如果转移矩阵不可约，并且是非周期的，则收敛到一个每一列都是不同的平稳分布 * ，并且，独立于初始分布。这是由Perron-Frobenius theorem所指出的。正的转移矩阵（即矩阵的每一个元素都是正的）是不可约和非周期的。矩阵被称为是一个随机矩阵，当且仅当这是某个马尔可夫链中转移概率的矩阵。注意：在上面的定式化中，元素(i,j)是由j转移到i的概
15、率。有时候一个由元素(i,j)给出的等价的定式化等于由i转移到j的概率。在此情况下，转移矩阵仅是这里所给出的转移矩阵的转置。另外，一个系统的平稳分布是由该转移矩阵的左特征向量给出的，而不是右特征向量。转移概率独立于过去的特殊况为熟知的Bernoulli scheme。仅有两个可能状态的Bernoulli scheme被熟知为贝努利过程7现实应用马尔可夫链模型的应用科学中的应用马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算法编码。马尔可夫链最近的应用是在地理统计学(geostatistics)中。其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟。这一应用类似于“克里金”地理统计学(Kriging geostatistics)，被称为是“马尔可夫链地理统计学”。这一马尔可夫链地理统计学方法仍在发展过程中。应用示例马尔可夫链模型主要是分析一个人在某一阶段内由一个职位调到另一个职位的可能性，即调动的概率。该模型的一个基本假设就是，过去的内部人事变动的模式和概率与未来的趋势大体相一致。实际上，这种方法是要分析企业内部人力资源的流动趋势和概率，如升迁、转职、调配或离职等方面的情况，以便为内部的人力资源的调配提供依据。它的基本思想是
