马尔可夫过程的研究及其应用

马尔可夫过程的研究及其应用概率论的思想通常都很微秒，即使在今天看来仍没有被很好地理解。尽管构成概率论的思想有点含糊，但是概率论的结果被应用在整个社会当中，当工程师估计核反应堆的安全时，他们用概率论确定某个部件及备用系统出故障的似然性。当工程师设计电话网络时，他们用概率论决定网络的容量是否足够处理预期的流量。当卫生部门的官员决定推荐或不推荐公众使用一种疫苗时，他们的决定部分的依据概率分析，即疫苗对个人的危害及保证公众健康的益处。概率论在工程实际、安全分析，乃至整个文化的决定中，都起着必不可少的作用。关于概率的信息虽然不能让我们肯定的预测接下来发生个什么，但是它允许我们预测某一事件或时间链的长期频率，而这个能力十分有用。概率论的思想不断渗透到我们的文化当中，人们逐渐熟悉运用概率论的语言思考大自然。世界并不是完全确定的，不是每个“事件”都是已知“原因”的必然结果。当科学家们对自然了解的更多，他们才能认知现象—例如，气体或液体中分子的运动，或液体的波动。由此引入了人们对布朗运动的定性与定量描述。在人们思考布朗运动的同时，俄国数学家马尔可夫开始研究现在所谓的随机过程。在实际中遇到的很多随机现象有如下的共同特性：它的未来的演变，在已知它目前状态的条件下与以往的状况无关。描述这种随时间推进的随机现象的演变模型就是马尔可夫过程。例如森林中动物头数的变化构成——马尔可夫过程。在现实世界中，有很多过程都是马尔可夫过程，如液体中微粒所作的布朗运动、传染病受感染的人数、车站的候车人数等，都可视为马尔可夫过程。关于该过程的研究，1931年A.H.柯尔莫哥洛夫在《概率论的解析方法》一文中首先将微分方程等分析的方法用于这类过程，奠定了马尔可夫过程的理论基础。1951年前后，伊藤清建立的随机微分方程的理论，为马尔可夫过程的研究开辟了新的道路。1954年前后，W.费勒将半群方法引入马尔可夫过程的研究。流形上的马尔可夫过程、马尔可夫向量场等都是正待深入研究的领域。安德烈•马尔可夫（A.A.Markov，1856－1922），1856年6月14日生于梁赞；1922年7月20日卒于圣彼得堡。马尔可夫上中学时，大部分课程学得不好，惟独数学成绩常常都得满分，并开始自学微积分，有一次他独立地发现了一种常系数线性常微分方程的解法，就写信给著名数学家布尼亚科夫斯基，信被转到彼得堡数学系科尔金和佐洛塔廖夫手里，从此马尔可夫与彼得堡大学的数学家建立了联系。1874年考入彼得堡大学数学系学习，在学习期间他深受切比雪夫、科尔金、佐洛塔廖夫等数学家的启发和影响，1878年大学毕业，并以《用连分数求微分方程的积分》一文获金质奖章。1880年以题目为《论行列式为正的二元二次齐次》的论文取得硕士学位并在彼得堡大学任教。1884年获物理数学博士学位，1886年成为教授，1890年当选为彼得堡科学院候补院士，1896年当选为院士，1905年退休时彼得堡大学授予他功勋教授称号。马尔可夫研究的范围很广，对概率论、数理统计、数论、函数逼近论、微分方程、数的几何等都有建树。在概率论方面，他深入研究并发展了其老师切比雪夫的矩方法，使中心极限定理的证明成为可能。他推广了大数定律和中心极限定理的应用范围。他提出并研究了一种能够用数学分析方法研究自然过程的一般图式，这种图式后人即以他的姓氏命名为马尔可夫链。他还开创了一种无后效性随机过程的研究，即在已知当前状态的情况下，过程的未来状态与其过去状态无关，这就是现在大家耳熟能详的马尔可夫过程。马尔可夫的工作极大的丰富了概率论的内容，促使它成为自然科学和技术直接有关的最重要的数学领域之一。20世纪50年代以前，研究马尔可夫过程的主要工具是微分方程和半群理论（即分析方法）；1936年前后就开始探讨马尔可夫过程的轨道性质，直到把微分方程和半群理论的分析方法同研究轨道性质的概率方法结合运用，才使这方面的研究工作进一步深化，并形成了对轨道分析必不可少的强马尔可夫性概念。1942年，伊藤清用他创立的随机积分和随机微分方程理论来研究一类特殊而重要的马尔可夫过程──扩散过程，开辟了研究马尔可夫过程的又一重要途径。近年来，鞅论方法也已渗透到马尔可夫过程的研究中，它与随机微分方程结合在一起，已成为目前处理多维扩散过程的工具。此外，马尔可夫过程与分析学中的位势论有密切的联系。对马尔可夫过程的研究，推动了位势理论的发展，并为研究偏微分方程提供了概率论的方法。最近十多年发展起来的吉布斯随机场和无穷粒子随机系统，是由于统计物理的需要而提出的。马尔可夫随机场（MarkovRandomField）包含两层意思。一是什么是马尔可夫，二是什么是随机场。马尔可夫性（无后效性）的定义为：过程或系统在时刻0t所处的状态为已知的条件下，过程在时刻0tt所处状态的条件分布，与过程在时刻0t之前所处的状态无关的特性成为马尔可夫性或无后效性。即：过程“将来”的情况与“过去”的情况是无关的。马尔可夫一般是马尔可夫性质的简称。拿天气来打个比方。如果我们假定天气是马尔可夫的，其意思就是我们假设今天的天气仅仅与昨天的天气存在概率上的关联，而与前天及前天以前的天气没有关系。其它如传染病和谣言的传播规律，就是马尔可夫的。随机场包含两个要素：位置（site），相空间（phasespace）。当给每一个位置中按照某种分布随机赋予相空间的一个值之后，其全体就叫做随机场。我们不妨拿种地来打个比方。“位置”好比是一亩亩农田；“相空间”好比是种的各种庄稼。我们可以给不同的地种上不同的庄稼，这就好比给随机场的每个“位置”，赋予相空间里不同的值。所以，俗气点说，随机场就是在哪块地里种什么庄稼的事情。还是拿种地打比方，如果任何一块地里种的庄稼的种类仅仅与它邻近的地里种的庄稼的种类有关，与其它地方的庄稼的种类无关，那么这些地里种的庄稼的集合，就是一个马尔可夫随机场。马尔可夫链，因安德烈•马尔可夫（A.A.Markov，1856－1922）得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。马尔可夫链是随机变量X_1,X_2,X_3...的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而X_n的值则是在时间nt的状态。如果X_{n+1}对于过去状态的条件概率分布仅是X_n的一个函数，则P(X_{n+1}=x|X_0,X_1,X_2,…X_n)=P(X_{n+1}=x|X_n)。这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。在数学中，马尔可夫链式最简单的一种马尔可夫过程，这里用实际例子对其进行解释。想象一个粒子沿实数轴以离散步骤来回移动。假设它从0点开始运动，并且只能向左或向右移动一个单位长度，假设它向右移动的概率是p，那么向左移动的概率就是1-p。如果我们令p=0.5，那么就可以把这个马尔可夫过程简化为下面的模型：粒子沿一条直线移动，每次只能移动一步，通过投掷硬币决定走哪个方向，正面代表向前，反面代表向后。投掷一次硬币，走一步，不断的重复这个过程。这就是以为布朗运动的数学模型。用马尔可夫链创建一维布朗运动的数学模型后，我们可以问，移动n步后，粒子在0点的概率是多少，或者投掷硬币足够多次以后，粒子不在0点并且永远不回到0点的概率是多少。人们已经深入的研究过马尔可夫链。虽然它很简单，但是有许多复杂的推广。在物理上，这些推广可以用来研究“扩散”现象，这一过程是不同气体或液体混合后分子的随机运动的结果。扩散过程也出现在生命科学，例如有事用扩散方程描述物种的运动。在数学上，一维马尔可夫链已经被广泛推广，其中最明显的是把粒子的一维运动变为二维或更高维的运动。一个更精细的推广则是改变上述模型，使粒子在时间、空间上连续的运动。换言之，就是不存在离散步骤，粒子随机的从一处游动到另一处。这种类型的运动叫做连续马尔可夫过程。马尔可夫过程也是研究数学交换理论的基础知识。第二次世界大战后不久，由于工程师、数学家香农的工作，数字交换理论诞生了。1948年，当香农还在贝尔实验室工作的时候，他发表了一系列关于交换的数学模型的论文。这些文章的目标是从数学上刻画信息的传递。当然，这样做需要定义数学上可以接受的信息的概念。这个定义必须可以应用到任何我们想称之为“信息”的事物上。香农喜欢具体的例子，不过他的工作实际上比例子显示的内容要深刻的多。香农的信息定义实际上是叙述了任一消息中顺序或可预言性的数量表示。根据香农的定义，信息传输要求有：信息源、传送者、通道、接收者。香农模型的核心是通道中噪音的存在，其中噪音表示信息流中偶尔出现的随机变化。在香农的数学模型中，信息源产生的符号序列是马尔可夫过程。在很长的消息序列中，下一个符号出现的概率由刚接收到的符号序列决定。从接收到的符号集合变成下一个新符号的概率，通常被描述为是一种马尔可夫链。香农证明，他所给的信息定义服从某些定理，这些定理在一定程度上类似那些描述质量、动量、能量等物理量变化率的定理。通过使用概率论，尤其是马尔可夫链理论，香农证明，当通道有噪音时，如果传送者正确编译了信息，那么就能以极高的准确性传输信息。马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。它们是后面进行推导必不可少的条件:(1)尺度间具有马尔可夫性质。随机场从上到下形成了马尔可夫链,即Xi的分布只依赖于Xi,与其他更粗糙的尺度无关,这是因为Xi已经包含了所有位于其上层的尺度所含有的信息。(2)随机场像素的条件独立性。若Xi中像素的父节点已知,则Xi中的像素彼此独立。这一性质使我们不必再考虑平面网格中相邻像素间的关系,而转为研究尺度间相邻像素(即父子节点)间的关系。(3)设在给定Xn的情况下,Y中的像素彼此独立。(4)可分离性。若给定任一节点xs,则以其各子节点为根的子树所对应的变量相互独立。从只有一个节点的根到和图像大小一致的叶子节点,建立了完整的四叉树模型,各层间的马尔可夫链的因果关系使我们可以由非迭代的推导过程快速计算出X的最大后验概率或后验边缘概率。完整的四叉树模型也存在一些问题。(1)因概率值过小,计算机的精度难以保障而出现下溢,若层次多,这一问题更为突出。虽然可以通过取对数的方法将接近于0的小值转换成大的负值,但若层次过多、概率值过小,该方法也难以奏效,且为了这些转换所采用的技巧又增加了不少计算量。(2)当图像较大而导致层次较多时,逐层的计算甚为繁琐下溢现象肯定会出现,存储中间变量也会占用大量空间,在时间空间上都有更多的开销。(3)分层模型存在块效应,即区域边界可能出现跳跃,因为在该模型中,同一层随机场中相邻的像素不一定有同一个父节点,同一层的相邻像素间又没有交互,从而可能出现边界不连续的现象。为了解决这些问题,我们提出一种新的分层MRF模型——半树模型,仍然是四叉树,只是层数比完整的四叉树大大减少,相当于将完整的四叉树截为两部分,只取下面的这部分。模型最下层仍和图像大小一致,但最上层则不止一个节点。完整的四叉树模型所具有的性质完全适用于半树模型,不同点仅在于最上层。完整的树模型从上到下构成了完整的因果依赖性,而半树模型的层间因果关系被截断,该层节点的父节点及祖先均被删去,因此该层中的各节点不具有条件独立性,即不满足上述的性质2,因而对这一层转为考虑层内相邻节点间的关系。半树模型和完整的树模型相比,层次减少了许多,这样,层次间的信息传递快了,概率值也不会因为过多层次的逐层计算而小到出现下溢。但第0层带来了新的问题,我们必须得考虑节点间的交互,才能得出正确的推导结果,也正是因为在第0层考虑了相邻节点间的影响,使得该模型的块现象要好于完整的树模型。对于层次数的选取,我们认为不宜多,太多则达不到简化模型的目的,其优势体现不出来,但也不能太少,因为第0层的概率计算仍然要采用非迭代的算法,层数少