转移矩阵&马尔科夫链

《转移矩阵&马尔科夫链》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、转移概率矩阵转移概率矩阵（又叫跃迁矩阵，英文名：transitionmatrix）是俄国数学家马尔科夫提出的，他在20世纪初发现：一个系统的某些因素在转移中，第n次结果只受第n-1的结果影响，即只与当前所处状态有关，而与过去状态无关。在马尔科夫分析中，引入状态转移这个概念。所谓状态是指客观事物可能出现或存在的状态；状态转移是指客观事物由一种状态转移到另一种状态的概率。例如对应于一个天气预报的问题，若天气状态转移概率表如左下：（其中列表示今天的状态，行表示明天的状态。注意每一列之和为1，因为已假设

2、明天仅这三种状态。）  图1.天气转移概率矩阵明/今晴阴雨晴3/41/21/4阴1/81/41/2雨1/81/41/4写作矩阵形式为图1所示。其中转移矩阵A的每一个元素都表示从今天的一种状态到明天的一种状态的概率，例如，第2行第3列的值为1/2，这表示今天下雨而明天转阴的概率是1/2。称A为转移矩阵。马尔可夫链1原理简介马尔可夫链（MarkovChain），描述了一种状态序列，其每个状态值取决于前面有限个状态[1] 。马尔可夫链是具有马尔可夫性质的随机变量的一个数列。这些变量的范围，即它们所有可

3、能取值的集合，被称为“状态空间”，而的值则是在时间n的状态。如果对于过去状态的条件概率分布仅是的一个函数，则这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。2理论发展马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）。马尔可夫链也有众多的生物学应用，特别是人

4、口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。3过程马尔可夫过程的定义：⑴设是一个随机过程，如果在在时刻所处的状态为已知时，与它在时刻之前所处的状态无关，则称具有马尔可夫性。⑵设的状态空间为S,如果对于任意的n≧2,任意的,在条件下,X(tn)的条件分布函数恰好等于在条件下的条件分布函数，即则称为马尔可夫过程。马尔可夫过程，能为给定样品文本，生成粗略，但看似真实的文本：他们被用于众多供消遣的“模仿生成器”软件。马尔可夫链还被用于谱曲。它们是后

5、面进行推导必不可少的条件：⑴尺度间具有马尔可夫性质.随机场从上到下形成了马尔可夫链，即的分布只依赖于,与其他更粗糙的尺度无关，这是因为已经包含了所有位于其上层的尺度所含有的信息.⑵随机场像素的条件独立性.若中像素的父节点已知，则中的像素彼此独立.这一性质使我们不必再考虑平面网格中相邻像素间的关系，而转为研究尺度间相邻像素（即父子节点）间的关系.⑶设在给定的情况下,Y中的像素彼此独立.⑷可分离性.若给定任一节点,则以其各子节点为根的子树所对应的变量相互独立.从只有一个节点的根到和图像大小一致的叶子

6、节点，建立了完整的四叉树模型，各层间的马尔可夫链的因果关系使我们可以由非迭代的推导过程快速计算出X的最大后验概率或后验边缘概率.4模型完整的四叉树模型也存在一些问题.⑴因概率值过小，计算机的精度难以保障而出现下溢，若层次多，这一问题更为突出.虽然可以通过取对数的方法将接近于0的小值转换成大的负值，但若层次过多、概率值过小，该方法也难以奏效，且为了这些转换所采用的技巧又增加了不少计算量.⑵当图像较大而导致层次较多时，逐层的计算甚为繁琐。下溢现象肯定会出现，存储中间变量也会占用大量空间，在时间空间上

7、都有更多的开销.⑶分层模型存在块效应，即区域边界可能出现跳跃，因为在该模型中，同一层随机场中相邻的像素不一定有同一个父节点，同一层的相邻像素间又没有交互，从而可能出现边界不连续的现象.5MRF为了解决这些问题，我们提出一种新的分层MRF模型——半树模型，其结构和图15类似，仍然是四叉树，只是层数比完整的四叉树大大减少，相当于将完整的四叉树截为两部分，只取下面的这部分.模型最下层仍和图像大小一致，但最上层则不止一个节点.完整的四叉树模型所具有的性质完全适用于半树模型，不同点仅在于最上层,完整的树模

8、型从上到下构成了完整的因果依赖性，而半树模型的层间因果关系被截断，该层节点的父节点及祖先均被删去，因此该层中的各节点不具有条件独立性，即不满足上述的性质2,因而对这一层转为考虑层内相邻节点间的关系.半树模型和完整的树模型相比，层次减少了许多，这样，层次间的信息传递快了，概率值也不会因为过多层次的逐层计算而小到出现下溢.但第0层带来了新的问题，我们必须得考虑节点间的交互，才能得出正确的推导结果，也正是因为在第0层考虑了相邻节点间的影响，使得该模型的块现象要好于完整的树模型.对于层次数的选取，我们认