（应用数学专业论文）链图上lci模型的特征及其在不完全数据分析中的应用.pdf

上海交通大学硬士学位论文 链图上l c i 模型的特征及其在不完全数据分析中的应用 摘要 图模型在许多领域被认为是一个非常重要而有力的工具。它广泛地应用在诸 如遗传学、统计物理、专家系统、人工智能等领域它直观的将各种因素用图来描 述，其中图上的顶点表示影响个系统的各个因素，边描述这些因素之问的各种 复杂的关系l c i ( l a t t i c ec o n d i t i o n a lh d e p e n d e n c e ) 模型是图模型中的一个重要模 型通过它我们可以研究各个顶点所表示的各个因素之问的关系，弄清它们之间 的关系，可以达到把复杂问题简单化的目的 l c i 模型是由a n d e r m o n 等口r4 1 在研究多元正态分布时提出的，并且由a n d e f f s s o n 等【3 l 应用到非单调不完全数据分析中，在p e r l m a n 等咖j 一文指出在l c i 模型中， 单调和非单调数据模式的似然函数可以被分解成一系列条件概率分布的乘积，这 样我们更容易得到最大似然估计的解析表达式a n d e r s s o a 等 s l 是在有向不循环图 上定义和研究l c i 模型的，并给出有向不循环图上l c i 模型的图模型特征有向 不循环图是链图的一个特殊情况，我们可以把l c i 模型拓展到链图上来研究l c i 模型，本文将给出链图上l c i 模型的一些特征，。 在研究链图上l c i 模型的特征，我们主要主要工具是信息论和i - 测度，主要思 想借助于y e u n g 等m 文，该文利用信息论和i - 测度理论得出了m a r k o v 模型，即 m a r k o v 随机场的信息论特征而m a r k o v 模型又是l c i 模型的个子集( a n d e r s s o n 等 ) ，因此我们可以猜想从信息论方面来研究l c i 模型或许是可行的本文的一个 重要结论就是要给出l c i 模型的信息论特征 最后本文讨论了l c i 模型在不完全数据分析中的应用问题，在l c i 模型的条件 下，我们可以将列联表中单元格的概率分解为一系列相互独立条件概率的乘积， 然后，我们在做最大化的时候只要对各个独立的条件概率分别做最大化即可 关键词；格条件独立确模型，m a r k o v 模型，图模型，信息论。 i - 测度， m a r k o v 随机场，不完全数据，参款估计 。 。 、 a 丑s 了r a c l l t h ec h a r a c t e r i z a t i o n so fl c im o d e l so nc h a i ng r a p h sa n dt h e i r a p p l i c a t i o no na r i a l y s i so fm i s s i n gd a t a a b s t r a c t g m p h i o a lm o d e li s i m p o r t a n ta n du s e h dt o o li nm a n ys c i e n t h b ef i e l d s s u c ha sp o p u l a t i o n g e n e t i c s ，s t a t i s t i c a lp h y s i c s ，e x p e r ts y s t e m ，a r t i f i c i a li n t e l l i g e n c e ，a n ds oo n i ng r a p h i c a lm o d e l s ， f a c t o r st h a ta f f e c tt h er e s e a r c h e ds y s t e m ，a n dt h e i rr e l a t i o n s h i p sa r ed e s c r i b e db yag r a p h ，i n w h i c hv e r t i c e sp r e s e n tf a c t o r s ，a n de d g e sp r e s e n tt h e i rr e l a t i o n s h i p s a nl c i ( l a t t i c ec o n d i t i o n a l h d e p e n d o n c e ) m o d e li so r eo ft h e s eg r a p h i c a lm o d e l s ，i ti si m p o r t a n ti ng r a p h i c a lm o d e l s b y w h i c h ，m a n yc o m p l i c a t e dp r o b l e m sc a l lb es i m p l i 缸d ，i nt h ew a y so f a i 缄t h ei n d e p e n d e n c e r e t a t 删s h i p so ff a c t o r s l c im o d e lw a si n t r o d u c e db ya n d e r s o n 毹一3 一i n m u l t i p l en o r m a ld i s t r i b u t i o n a n dd e v e l - o p e db ya n d e r s s o ne t “剐a n da p p l i e di na n a l y z i l i go f m i s s l n gd a t & i ti ss t a t e dt h a t ，i np e r i m a n e t 删t h em 蛇l i h o o df u n c t i o no nm o l i o t o n ea n dn o n - m o n o t o n ed a t ap a t t e r nc a nb ef a c t o r i z e d t h e p r o d u c to fs o m ec o n d i t i o n a li n d e p e n d e n c ed i s t r i b u t i o n su n d e rl c im o d e l s a n dt h ee x p l i c i t m l e ( m a x l m u ml i k e l i h o o de s t i m a t i o n ) c b eo b t a i n e d i na r l d 目s s o ne ta 庐i 。t h el c im o d e l i sd e 丑n e da n ds t u d i e do i la d g s ( a c y l i oi ) m e c t e dg r a p h ) a n di t sg r a p h 删c h a r a c t e r i z a t i o n sa r e s t a t e d f t t r t h e r m o r e ，a d gi sas p e c i a lc a s eo fc h a i ng r a p h s i nt h i sp a p e r ，l c im o d e l sa r e e x t e n d e dt oc h a i ng r a p h sa n dt h e i ri n f o r m a t l o n - t h e m 窟t r cc h a r a c t e r i z a t i o ni so b t a i n e d 、v h w es t u d yl c im o d e l so i lc h a i ng r a p h s t h em a i nt o o li si n f o r m a t i o nt h e o r ya n di - m e a s l l r e n ei d e ac o m e sf r o my e u n ge t “3 ”，i nw h i c h ，t h ei n f o r m a t i o n - t h e o r e t i oc h a r a c t e r - i z a t i o a so fg r a p h i c a lm a r k o vm o d e l s ，i e ，m a r k o vr a n d o mf i e l d sw e r ee s t a b l i s h e d i nf a c t ta m a r k o vm o d e li sc o n t a i n e di ns o i l l c im o d e l ( a n d e r s s o ne ta 删) ，s ow ec a ns t u d yl c im o d e l s b yi n f o r m a t i o nt h e o r y a sac o n c l u s i o n ，w ed i s c u gt h ea p p l i c a t i o no fl c im o d e l so i la n a l y z i n go fm _ 岱i n gd a t a ， u n d 汀l c im o d e l s ，t h ep r o b a b i l i t yo fc e l l si nc o n t i g e n c yt a b l ec a nb ef a c t o r e da 8p r o d u c t so f s o m ec o n d i t i o n a li n d a p e n d e n c ed i s t r i b u t i o n s ，t h e nw e o n l yn e e dt om a x i m i z et h e s ed i s t r i b u t i o n s r e s p e c t i v e l yw h e nm d m i z _ m gt h ec e l lp r o b a b i l i t i e s k e yw o r d s l a t t i c ec o n d i t i o n a li n d e p e n d e n c e ( l c i ) m o d e l s ，m a r k o vm o d e l s ，g r a p h i c a l m o d e l s ，i n f o r m a t i o nt h e o r y , i - m e a s u r e ，m a r k o vr a n d o mf i e l d s ，m i s s i n gd a t a p a r a m e t r i ce s t i m a = t i o n i i 第一章绪论 1 1 历史、意义聂研究现状 要研究l c i 模型还得先从圈模型说起，因为l c i 模型是图模型的一十特殊模型圈模 型的起源可以追塑到s e w a l lw r i g h t j 的工作，s e w a l lw 秭曲d 删的思想是用图来表示随机变 量之间的条件独立关系迄今为止田模型巳经广迂应用在遗传学、专家系统、人工智能、图 象处理、统计物理等多十领域。图模型的理论中有向不循环圈和无向不循环圜方面的已经比较 成熟其中，基于有向不循环图的图模型使统计分析变得异常的筒单这使得它在许多其它的 领域中有覆广泛的应用，如在专寡系统中的概事推断( p e d i 州；l a u r i t z e s na n ds p i e g e l h a l t 日； n e a p o l i t a n ” ) ，条件概率的序贯更新( s p d g e l h a l t e ra n dl a u r i t z e n 2 ”，专家系统中贝叶斯 分析( s p i e g e l h a l t e r 等阳1 ) 专家系统中的模型选择、模型不确定性的计算( m a d i g na n d r a r e 珂 2 日) 因果关系的推断( s p i r t e s 等1 3 4 ；p e a d 2 。删；l a u r i t z e n 1 q ) ；基于无向不循环图 的图模型又叫m a z k o v 随机场，广泛应用在统计物理的数据分析，图象处理等颁域( m 螂l e y a n da 进叫d 【1 吼；b e s 础l ；s p e e d 【船i ：d a n o c h 等【1 2 1 ) 链图模型，作为无向不循环图模型和有向不循环图模型的一种推广它的应用相对比较 晚一些直到1 9 9 8 年，才被应用到人i e i 学上( m o h a m e d 等删) 在此之前，为链田模型的发 展作出贡献的有，f r y d e n b e r g “l ，l a u r l t z e n a n dw e r m u t h 2 链圈在统计依赖性关景的建 模中起薯很重要的作用，重要的参考文献有l a u r i t z e n 【l w e r m u t ha n dl a u r i t z e n s s l 以及 c o xa n dw e r m u t h 1 1 i 等 上述有向不循环图、无向不循环图以及链图在研究条件独立性时都是在各类圈上假设有 m a r k o v 性质虚立。如两两m a r k o v 性质、局部m a r k o v 性质、全局m a r k o v 性质等。m a r k o v 随机场就是在无向不循环圈上嵌有全局m 口k o v 性质1 9 8 8 年a n d e r s 目o n n 在研究正交 线性模型时挺出一种格的结构，也就是现在的l c i 模型的雏形，后来逐浙在a n d e r s s o na n d p e r h n a n 3 ，卅两篇文献中成形l c i 摸蛩是另一种在有向不循环图上定义有l c i 性质的有向 图模型它为不完全数据的推断提供了一个极其便利的工具，如a n d e r s s o na n dp e z l m a n q 一 文中讨论了l c i 模型中的检验问题黼出ld p e h u a na n dl a n gw i 妁一文中讨论了l c i 、 模型中非单调不完全数据的参数估计同题 5 a n d e r s s o n 等 t j 研究了有向不循环图、无向不循环图以及链图上m a r k o v 等价性这为进 一步的研究l c i 模曩奠定了基础，其后a n d e r s s o n 等 | j 研究了有向不循环田上l c i 模型 的图模型特征研究l a 模型的田模型特征无疑是有意义的，因为它为不完全数据中的数据 分析提供了一十有力的保证，呷是首先能够确认这个模型是否是l c i 模塑a n d e r s s o n 等【” 的局限性在于，他f 门是在有向不循环图上来研究l c i 模型的，因此，赢实际应用中就有局限忙 性，即只能在有向不循环圈上来使用l c i 模型，对于更一般的图如链图刚不能处理 实际上我们可以将l c i 模型推广到般的图如链图上再来研究其理论及应用，在有向 不循环图上l c i 模型包含m a r t m v 模塑( a n d e r s s s o n s ) 即l c i 模型比m a r k o v 模星的范围 上海交通大学硕士学位论文 更广迁另外y e u n g 等【l 在信息论中，利用i _ 测度理论给出m a r k o v 模型的信息论特征， 这使我们很容易想到，从信息论方面来研究l c i 模型应该是可行的本文将在信息论的基础 上给出链图上l c i 模型的信息论橹征这样我们就把l c i 模型的应用拓广到了链圈的范畴上 了并且通过信息论方法来判定l c i 模蛩也是一可计算的方法实际上通过信息论方法来翔 定个模型是否是l c i 棋就是要计算某些随机向量的i - 测度是否为零，在这方面，k e u n g p 5 3 6 1 中的i t i p 软件是个相当好的工具，它可以计算一个随机向量的l 测度，从这个意义 臼话说。通过信息论方 击来判定l c i 模型可以计算来实现与图模型特征相比可以说是另 辟蹊径 本文各章的安排如下- 第2 章主要介绍了图模型的基本概念各种图上的m a r k o v 性质以 及图的m a r k e r 等价性；第3 章中，我们讨论了有向不循环图上l c i 模蛩的圈模塑特征和有向 化算法，以及有向化算法在图的完备编号中的应用，这是我们的个重要结果；第4 章中 我们讨论了信息论中i _ 测度的，它是我们得出链图上l c i 模型的信息论特捱的主要工具此 外。我们还讨论了无向图上的m a r k o v 模型叩m a r k o v 随机场的信息论特征；第5 章是我们 的主薹结果，在这章中，我们引入一种新的棱它刻划出了链图上l c i 模型的信息论特征 第4 中m a r k o v 随机场的信息论特捱是该结果的十特倒第露简单讨论了l c i 模塑在不完 全鼓培分析中的应用； ： 岳 2 第二章图模型的基本概念和m a r k o v 性质 2 1 基本概念 夕i 固 图模型是由图来表示的模型，? 畿们用图g = ( h e ) 表示其中y 为有限顶点集，e = y - y = ( 口，口) l a ，卢y 为边的藻合称b 到卢的边为有向边若( 口，口) e e ，但垆口) g e ， 用口+ 芦表示稚。和卢之闻的边为无向边，若( 口，卢) e 且伊，o g ) e ，用口一卢表 示称图g 为有向圈，若其仅有有向边称它为无向田，若其仅有无向边个图g = ( k 目 的无向型是图g “；( u e ) ( 或者记为g 咀= ( k e 。) 其中e 或e u 是把e 中所有的有向 边用无向边代替，而其它的不变所得的边的集合如果在图g 的顶点集y 上定义个非自反 的偏序关系叫，对应的具有偏序关系的图g 一具有与圈g 相同的顶点集在图g 一上的两个 。r 璜点q ，卢之咆培边当且仅当它们在图g 上有边，并且如果有。叫卢，则其佩的边变为有向 i 岫边d + 卢，其它的边为无向边，如果图g 。为有向田则称它为图g 的有向型 、哼闽 设集合4 v 为顶点集的一个子集它在g 上的导出子田为图g = 孵r 互菊嚣中m e 闻a 都有= e 嗉n ( 有ax 向的a ) 嚣篡二急a 麓蔫鬻蔗黧芸 兹窆如闻都有条有向的或无向边相连；称个子集w ，若它的导出子田是完全的在集否萄：豫一已” 含的意义下，最大的完全子集称为团对于图g 中的两个顶点a 卢若有一个由。到芦 的箭头，即o + 卢，则称。为芦的父代，称口为。的子代称口为d 的邻点。若a 一 卢，并且称口和芦耜邻条驭点a 到点口的n 长的路是指，存在n + 1 个不同顶点序列 a = 8 0 ，a 1 ，= 卢，使得( 皿_ l i o ) e e 对所有的i = 1 ，n 成立，记作q p 叶口称顶 点n 为顶点卢的祖，卢为口的后代，若a _ 口但卢产+ a 为方便起见，我们把一些集 合记号归结如下。 1 m ( a ) ：顶点q 所有父代的集合； 2 t 舯( ) ：子集a 妄y 父代的集合，p a ( a ) = u 。e p a ( a ) a i 3 o h ( e ) ：顶点口所有子代的集合； 4 曲( ) ：子集a 至v 子代的集合c a ( a ) = u 。 c h ( a ； 5 m ( b ) ：顶点d 所有邻点的集合； 6 - 凇( ) ：于集a e y 邻点的集合，伸( a ) = u 。 n e 【曲a ； 7 ( o ) ：顶点n 所有祖的集合； 8 帆( a ) ：对子集且v a n ( a ) = 卢矿i 卢( 口) ，对某个o a u 4 9 d e c a ) ：顶点a 所有后代的集合； l o d e ( a ) ：子集a y 后代的集合，出) = u 。e d e ( a ； i i 删o ) ：顶点口非后代的集合，n d c 曲= y ( d e ( a ) u ( a ) ) ； 1 2 州( a ) ：子集 e y 非后代的集合，n d ( a ) = y ( d e ( a ) u ( a ) ) ； 3 上海交通大学硕士学位论文 1 3 配扣) ：顶点a 的边界集。定义为曲恤) u n e ( a ) n ( y 耐) ； 1 4 ( ) ：子集a y 的边界集，定义为忉口( a ) u n e ( a ) 】n ( v a ) ； 1 5 d 妇) ：c j ( 口) = 6 d ( 吐) u a k 1 6 c f ( ) ：对子集a v c f ( ) = 6 d ( ) u a 称一十有向不循环图d = ( k 日为转移有向不循环田( t a d g ) ，若a + 口d 且 卢+ 7 d = 辛口7 d ，其中口晟7 v 或者等价地，d 为转移的若对所有的 n e v ，有龃( a ) a ) = p a 陋) 如果一条n 长的路，其起点和终点相同，则称它为n 长的循环称它为有向，若它仅有 有向边，无向的，若它仅有无向边有向不循环田是指不古有有向循环的有向图一个图称为 链图，若它的顶点集可分成t 组子集，记为v = v ( 1 ) u u 矿口) ，使得在同一个子集里仅 有无向边而在不同子集之i 町仅有有向边，并且箭头方向是从序号低的指向序号高的，其中 y ( 1 ) ，y ( t ) 称为是链圈的链部分或者。等价地链圉就是一种不舍有向循环的图 对一个链匿g = e ) 其m o r a l 图伊定义为如下：首先g “是个无向图，它与图c 具有相同的顶点集，其次，在圈g 4 中，两个顶点a 和卢在圈g ”中相邻，当且仅当在图g 中 有，口+ 口或芦+ a 或者在同健部分中有两个顶点6 和1 使得a + d 且口+ 7 称一个链图是完备的若它的m c x a l 田是它的无向型称链图中的链部分c c 为终靖，若c c 中的每十顶点都没有子代，若c c 仅有一个顶点，则称其为终点 令u = 司为无向图，称子集a 至y 在u 中是连结的( c o n n e c t e d ) ，若对任意不同顶 点口卢a ，在u 中有一条由。通向卢的路对y 中两两不交的子集 ( o ) ，丑( 0 ) ，s ， 称s 在u 中分离a ，占若由a 中的顶点到b 中顶点的路都要经过s 若s = 0 ，则s 在矿中分离a 和口的充要条件是投有从 到口的路，这时，在c ，中，任意与且，b 不变的 子集都分离且和b 称无向图为完全的著每对顶点之闻都有边相连，显然，空田是完全的称y 的子集a y 在u 中是完全的，若它的导出子圈完全；称a 矿在无向圈u 中是单纯的若它的边界完 全设 ，曰为y 的两十非空子集称( ，日) 为，的个分解。若v = a u b a n 日是完全 的，且a n b 在u 中分离a b 和b a 此时称( a ，日) 将图u 分解成两十部分巩和c ，口 称一个无向圈为弦的，若每一个长度大于或等于4 的循环都会产生一个弦弦的一十重 要应用是甩来爿定无向圈的可分解性，l a u r i t z e n 等【删中指出无向图可分解的充要条件是它 是弦的 令g = ( m 曰) 为链田稚( 口，日，口) 为c 中旱 自? 体( c o m p l e x ) ，若口为莱十链部分r e 州g ) 的十连结子集口和卢是两个在嘁r ) n 配( b ) 中不相邻的顶点称联合体( a ，b ，口) 在e 中是最小联舍体，若不存在b 的真子集b cb 使得( q ，b 。，卢) 为一个联合体很容易看出， 每个联合体都至步有十鼍小联合体称个联舍俸为非义体( i m m m a i 埘) ，若b 仅有一个 顶点n y d 岫r s 【“j 中指出国，b 卢) 为圈c 的最小联台体当且仅当图g 日。 。，肿为如图2 1 所示的情形对y 的任意子集 s y ， 口l u b u 胪) a ，则( 口。b ，芦) 为0 中最小联合 体当且仅当它在g 中是最小联合体 4 第二章：田模型妁基本概念和m 打幻y 性质 设百= ( 矿，豆) c = ( v 功为两个链图，称0 太于c 若v 矿且e 亩，记作 c 0 b 圉2 1 ：( a ，b 们( a ，日，卢) 。( 卢，b ，1 ) 均是联合体，而且( q ，b ，芦) 为最小联台体 2 2 图模型中的m 盯k o v 性质 在这一节中，我们将着重讨论无向田，有向图以及链图上的m a r k o v 性质，实际上，围模 盈上的这些m 幽v 性质与随机过程中的m 幻v 链是有着某种潜在的联系，都是讨论在时向 轴上的随机变量或向量相互之| 可的条件独立关系，所以在讨论地r b v 性质之前，我们有必要 把条件独立关系弄清楚 设三个随机变量x ，t 三具有联合概率分布p 称x 在联合概率分布尸中给定z 下与 y 条件独立若对x 的抽样空问的任意可测集a ，都存在个条件概率分布p ( a l eg ) 仅是 z 的函数记作x 上y i z 若五x z 是离散随机变量则x 上y l z 当且仅当 p ( x = z ，y = f l z = ：) = p ( x = x l z = z ) p ( y = 训z = ；) ( 2 2 1 ) 对所有的：，当：满足p ( z = o ) 0 时成立 若x ，一z 是连续随机变量。且x ，y z 服从相应于概率滔度p 的联合概率密度，则 x 上v l z 当且仅当 h v l z ( z ，v i = ) = a i z ( = l z ) 厅i z ( ! f i z ) ( 2 2 2 ) 关于概率分布p 几乎处处成立 条件独立关系有下列性质。 ( c 1 ) 着x 上y l z ，则y 上x l z ( c 2 ) 若x 上y l z 且u = h ( x ) 则u 上y i z ( c 3 ) 若x 上y i z 且u = h ( x ) ，则x 上v l ( 互u ) ( c 4 ) 若x 上y i z 且工上w i ( z ) ，则工工( 哦r ) i z 其中h 为x 的样本空问上的任意可铡函数条件独立关系还有另外条常用的性质如下， ( c 5 ) 若x 上y l z 且x 上zj y ，则x 上( y ，z ) 但是( c 5 ) 在一般情况下是不成立的，下面的反倒就说明了这个事实，令x = y = z ，x 的 概率分布为p x = 1 = j p 工= o ) = 1 2 ，当加上以下条件，( c 5 ) 就可以成立 5 上海交通大学硕士学位论文 令囊2 2 1 如果z ，z 关于概率洲虚j c 的联合鼍事密度为正的连靖的，刖( c 5 ) 成立 定理2 2 1 的证明可参阅参考文献l a u i i t z e n ( c 5 ) 是下面定义的各种m a r k o v 性质等 价的个重要条件，因此在本文中，我们假设( c 5 ) 总是成立 考虑定义在概率空问n = 。e y x 。上的概率分布，其中y 为有限指标集，对妇e 矿 x 。为对应于随机变量矗的字母集记x _ - ( 矗l a v ) n 为n 上的随机向量对y 的 子集且y ，记x = ( 以l 口e ) ，为方便起见在不引起混蒲的情况下，戎们将x 。和 托分别简记为n 和 并且约定x o = 常效对y 中的两两不交的子集a ，b ，0 v ，记 且上b i c l p l ，若在概率分布p 下给定c ，x a 和舶条件独立 下面授们将给出在各种雷上的m a r k e r 性质的定义 定义2 2 2 夺u = ( k e ) 为无向圈称一个定义在概率宣闾n 上的概率分布尸关于圈 g 辅足， ( u p ) 两两m a r l r o v 性质著对任意一砷不相邮的( 口，卢) ，盘卢ey ，有 a 上口l n a ，口】 ( u l ) 局部m a r l c o v 性质著对任意a y ，有 a 上矿c l ( a ) i b d ( 口) ( 2 2 3 ) ( u g ) 垒局m a r , b v 蛀盾，若斗璜点桌y 中的任意两两不交的子集( a ，b ，s ) 由s 在g 中分离a 和b 可以得到 上b s ( 2 2 5 ) 定义2 2 3 令d = ( k 曰为有向圈。称定义在概率空闻n 上的概率分布p 关于有向囤 d 满足t f d p ) 两两胁咖”性质，若甘v 中任意两个不相郜的顶点( n ，历，且声耐( 盘) ，有 口上口l 似a 卢 ( d l ) 局部m a r l t o v 性质若对每个a v 有 n 上( 埘( q ) 辨( a ) ) l 舯( a ) 引； ( d g ) 奎局m a , 0 w 性质，若 上b i s p 1 当s 在( ( 。) 誓1 南 椰 ( d w ) 良序m a r k , o r 性质，若砷每一个k = 2 ，n ，有 a k 上( d 1 ，o i 1 ) 阻( n - ) ) i 瑚( 口i ) 【p l ( 2 2 6 ) ( 2 2 7 ) ( 2 2 8 ) ( 2 2 9 ) l 一一一一 第二章t 哥挂星的基丰概念和m a r l n o v 性质 其中n = i 卅，a l ，o 。主y 中顶点的一个盘序蝙号印r a 辛n ，刊( n ) 又因 为啦# 脾( 船) ，p a ( a k ) 口h ，n i l ，条件f 2 ，2 缈等价于 ( a t ) u 口t ) ) 上 m ，a 1 舯( 口i ) 【p l ，( 2 2 1 0 ) 在有向不循环图中。有如下结果- 定理2 2 4 令d 为有向不循环圈，冲定义在概率空间n 上的概率分布p 。有d g 甘 d l d w 定理2 2 4 说明了两个问题其一是说明了定义2 2 3 中的良序m a r k o v 性质与良序编号 是无关的即是对任何一种良序编号都是一样的i 其二是说明了在有向不循环田中上述三种 m a r k o v 性质等价。为有向不循环图中m a r k o v 模型的定义提供了依据 定义2 2 5 令c = ( h 四为链圈称定义在概率空间n 上的鼍丰分布j p 关于圉c 满 足一 ( p c ) 西西】l f 盯岛鲫性质，若矸y 中任意不相邻的两个填点( a ，芦) ，且声en 烈d ) 有 n 上卢i 埘( a ) 册；( 2 2 1 1 ) ( l c ) 局部m a r k a v 性质，若甘y 中任意质点n ，有 血上n d ( 口) l b 烈口) ；( 2 2 1 2 ) c c c ) 全局 如捕o 性质若甘矿的任意三个两两不史的子集( a ，b ，且s 在( g h ( u 口u 司) m 中分离a 和b ，有 上b i s( 2 2 1 3 ) 其中 ( g _ 。( u 口u s ，) m 为矿的包含a u b u s 的i 小祖子集的阳r 试图 2 3 链图的m a r k o v 等价性 链圈的m a r l 。o v 等价性既是链田上的十重要问题，又是l c i 模型的一个基本理论它 是图模型由有向不循环田扩展到链圈上提出的个很自然的问题，有向不循环田棋型有其极 其简单的统计性质，因此而有非常广泛的应用，特别地，在有向不循环图模型，联合概率密度 函数有非常瀑亮的递归分解l 而在多元正态的情况下，参数估计的似然函数( 即联合概率密度 函数和参数空间) 能够被分解，得到量太似然估计在无向图模型中，能够做劐这一点的就只 有可分解的无向田模型，而这种无向田恰恰是部些能够与有向不循环图m a e o v 等价( 具有相 同的m a r k o v 性质) 的无向圈由此可以看出，m a r k o v 等价性在研究圉粞在参数估计的数 据处理的应用中的重要性 个无向图是由它所对应的m a r k o v 模盟所唯一确定的，但是这对有向不循环图和链圈不 一定成立给定个链圈，它既可能与某个无向圈m a r k o v 等价，也可能与某些有向不循环图 等价特别地，着十链图与某个有向不循环田m a r k o v 等价。剐它的统计分析就会变得异常 的简单于是下面的问题就是很自然的问题了 7 上海交通大学硕士学位论文 1 在什么情况下链田g 与某个无向图( 唯- - ) m a r k o v 等价? 2 在什么情况下链冒与有向不循环图秆：一定唯) m a r k o v 等价? 在这种情况下是否有一 种有效的算法。从健图c 得到至少十或者全都与链圈cm a r k o v 等价的有向不循环图? 3 什么情况下链图与莱一可分解无向图( 唯) m a r k o v 等价? 脚d b e r g 【1 q 如8 4 8 ) 回答了问题1 ，l a u r i t z e n 和w e n n u t h 2 2 i 培出一十链圉与培定有 向不循环图m 目r k o v 等价的充分条件，a n d e r d m 等【7 j 统一的回答了以上兰十问题并且给 出一种算法，可以由所给链圈出发得到至步个与其m a r k o v 等价的有向不循环图 定义2 3 1 称两个链田a = ( v 最) g = ( k 岛) 是胁诚o 等价的，著对任意由v 确定的概率囊积空间x 。由a 确定的全局肘口r 蛔”模型和由岛确定的全局埘4 r b 口模型相 同，记作凸嚣岛，记 d 】为包含d 的村b ”等价夷 定理2 3 2 链圈a = ( h 蜀) 。u 2 = ( ke 2 ) m a r k o 口等价当且位当a 和岛有相同的无 向型和相同的i 小联合体 注解2 3 3 由定理2 3 2 立即可以得出t 两个无向田m a r k o v 午价当且便当这两个无向圉 为同一个圈目北无向圈由其相应的m 缸k o v 攫型所唯一确定由定理2 3 2 我们还可以得 列：如果一个链目0 与某个有向不循环周d m 且r k o v 等价，则c r 的所有的王小联合律均是非 义体。反过来却不成立( 这一点将在例2 3 7 得到说明) 以下三个定理( 定理2 3 4 ，2 3 5 、2 3 6 ) 分别说明在什么条件下链圈与无向图、有向不 循环图以及可分解无向图 定理2 3 4 夺g 为链圉。则下列条件等价一 ( a ) c 与某个无向图( 唯一) m a r k 口v 等价l ( b ) g 没有i 小联合体； ( c ) c 嚣c u 定理2 3 5 夸0 = ( k 日为链圈，且町下列两个条件等件： ( i ) c 与某个有向不椭环因d ( 不一定唯一) 午价； ( i i ) 对所有的链部分t t ( c ) ， ( c o f ，) ) “可分解 定理2 3 6 夺g 为链图，则下列紊件等价： ( i ) c 与某个可分f 无向圈u ( 唯一) 等价 ( i i ) c 没有i 小联台体且伊可分解； ( i ) g 兰c u 且c 可分并 倒2 3 7 如图2 2 所示，有口个图c 3 ，q ，c 5 岛岛_ 醍有i 小联合体，目而它 m a r k o v 等价于其无向型也就是o ；晚有一个量小联合体，由定理2 3 4 可知，它不击与 任何无向圈m a r k o v 等价i 岛宥一个非义体，因此它也不与任何无向国m a r k o v 午价 定理2 3 8 令g 为链圈。则 ( a ) g 没有i 小联备体，且 ( b ) 对所有的链部分r 丁( 研， ( g j ( 劫”可分解； 当且仅当 8 第二章，田键蕉妁基本概惫和m a r o v 性质 q 厂 - 一 凸 叫q 6 yd 6 ( c ) q ( d ) 岛 6 6 圈2 2 ：田示为n 十链田其中2 2 ( a ) 和2 2 ( b ) 为m a r k o v 等价的 ( c ) 0 没有i 小联奢体且伊可分解 下面的推论2 3 9 是定理2 3 4 、2 3 5 、2 3 6 、2 3 8 的直接结果 搬e2 3 0 耷c 为链圉，剐 ( a ) c 与某无向囤u m a r k o v 等价，且 ( b ) g 与某有向不箱环圈dm a r k o v 等价l 当且仅当 ( c ) c 与某可分井无向围即c “m a r k o v 等价 由定理2 3 2 ，若c 有至少个联合体( 该联合休不是非义体) ，则c 不与任何无向圈或 有向不循环图m a r k o v 等价，然而该条件不是必要的，反倒如圉2 3 所示，圈2 3 ( a ) 中的链图 凸和图2 3 ( b j 中的链田岛除非义体之外投有任何联合体，但由定理2 3 4 2 3 5 ，它们不 与任何无向圈或有向不循环圉m a r k o v 等价下面的定理2 3 1 0 罗列了几个链图不与任何无 向图或有向不循环图m a r k o v 等价有充要条件 定理2 3 1 0 耷c 为链圈，则下列条件等价t 1 c 不与任何无向圈直有向不抽罩= 圈m 础o y 等价 2 g 至少有一个i 小联台体，且至少有一个链部分r t ( c ) 使得( c k ( ，) ) ”不可分 解 3 g 至少有一个不是非义体的最小联合休；或 c 有至少一个非义体，且至少有一个链部分re 丁( c ) 使得( c a ( ，) ) m 不可分解 4 g 口口 上海交通大学硕士学位论文 ( a ) 西( b ) c b 田2 3 ：田示的两十链圈除非义体之外没有其它的联合体但乞们不与任何无向田或有向不循环圈m 甜k o v 辱 价 g 至少有一个不是非义体的i 小联合体；或 0 有至少一个非义体，且至少有一个链部分r 7 弋c ) ，使得下列条件之一成立： ( i ) g 不可分解； ( 豇) 存在一个琉最a 掘( 订和一对不抽邻的玩最砷7 ，d 旃，( 口) ，使得在r 中 有一条从7 到占的路百，且加 7 ，占 】n 以r ( o ) = o i ( 缸i ) 存在一对不同顶点时口，口eh 烈f ) ，存在1 c k ( 口) c k ( 所，d c k 妒) c k ( 口) 使得在r 中有一条从1 到d 的路 且陬 7 ，d ) 1 n i d l r ( a ) u c k ( 芦) l = o 1 0 第三章有向不循环图上的l c i 模型及其图模型特征 3 1l c i 模型简介 l c i 模型的思怒是由有限分布格论和偏序集中得来的，有关格论及偏序集的知识，读者 可以参考d a v e ya n dp r i e s t l e y _ f l q 的第八章这一思想是在a n d e r s s m n 中完善的 令c ；c ( v ， ) 为一其。元素的有限分布格，集合c 的固不可约元索的子集j ( c ) 定义如 下南 ( c ) ：= d c 旧o ，j = 七v l = 耷七o r j = l 在囊合c 中定义偏序“”的意义为一j 兰k 甘j 女= j 。剐( j ( c ) ，) 为一有限偏序集 称丑( c ) 的子集且为祖的，若由j j ( c ) ，k a 和，sk 能推导出j a 记a ( ( ( c ) ，s ) ) 为 偏序集( j ( c ) ，s ) 的所有祖子集的集合。则a ( ( j ( c ) ) ) 为个环，且等同与环a ( ( j ( c ) ，e ) ) 其中( j ( ) ，口) 为转移有向不循环田其边集为- e ：= ( k ) ( c ) j ( c ) | j 1 。习 1 有最工1 或 孟，其中r 和分别表示连续的和离散的顶点_ 粜合在此我们不区分连续的和离散的璜 点技而，我们把条件( 3 ) 击掉，而仍然称它们完奋的，在这个定义下，l a u r i t z e n 【删的蛄论