（计算机系统结构专业论文）高斯均值场变分推理的算法研究.pdf

中文摘要 图模型是人工智能学科表示、处理不确定知识的重要方法。图模型精确推 理的计算复杂性是指数的，促使发展出变分方法、采样方法、环传播方法、定性 方法等图模型近似推理方法。由于图模型变分近似推理方法具有坚实的理论基 础、较快的收敛速度、简单的计算复杂性和严格的上下界等特点，故而受到概率 推理研究界的重视。现有变分推理研究工作主要从统计学观点研究变分推理的 方法、理论和性质，较少从计算角度研究变分推理的基本算法及其基本性质。 针对以上问题，本文在高斯马尔可夫随机场基本模型上，研究了变分推理的 基本算法及其基本性质，具体工作包括： 1 给出了图模型的八元组定义。完整地表示了随机变量的条件独立性和联合 概率分布，统一地定义了有向图模型和无向图模型。 2 设计了变分推理基本算法。在高斯马尔可夫随机场基本模型上，设计了精 确变分推理算法和均值场变分推理算法。 3 研究了算法的基本性质。证明了算法的收敛性，讨论了算法的精确性，分 析了算法的复杂性。 4 开展了实验研究。设计了数值模拟实验，验证了理论分析结果。 关键词：图模型变分推理均值场收敛性精确性 a b s t r a c t g r a p h i c a lm o d e l sa r ei m p o r t a n tm e t h o d sf o ru n c e r t a i nk n o w l e d g er e p r e s e n t a t i o n a n dr e a s o n i n gi na r t i f i c i a li n t e l l i g e n c e s i n c et h ec o m p l e x i t i e so fe x a c ti n f e r e n c e s o ng r a p h i c a lm o d e la r ee x p o n e n t i a l ，m a n ya p p r o x i m a t ei n f e r e n c e s ，s u c ha sv a r i a t i o n a l m e t h o d ，s a m p l i n gm e t h o d ，l o o p yp r o p a g a t i o n ，a n dq u a l i t a t i v em e t h o d , h a v eb e e nd e v e l o p e d ，a n dt h ev a r i a t i o n a lm e t h o dh a sb e c o m et h ef a v o u r i t eo fa p p r o x i m a t ei n f e r e n c e c o m m u n i t y d u et oi t ss o u n dt h e o r e t i c a lf o u n d a t i o n ，l o wc o m p u t a t i o n a lc o m p l e x i t y , h i g h c o n v e r g e n c er a t e ，a n dt i g h tu p p e ra n dl o w e rb o u n d s c u r r e n t l yt h em a j o r i t yo fe x i s t i n g r e s e a r c h e so f v a l i a t i o n a li n f e r e n c em e t h o do ng r a p h i c a lm o d e l sc o n c e r nw i t ht h em e t h o d s ，t h e o r i e sa n dp r o p e r t i e sf r o ms t a t i s t i c a lp o i n t so fv i e w , a n dl i t t l ea t t e n t i o nh a sb e e n p a i dt ot h eb a s i ca l g o r i t h m sa n de l e m e n t a r yp r o p e r t i e si nc o m p u t a t i o n a lp e r s p e c t i v e i nt h i st h e s i s ，a na l g o r i t h m i ca p p r o a c hi sa d o p t e dt ov a r i a t i o n a li n f e r e n c eo ng a u s s i a nm a r k o vr a n d o mf i e l dm o d e l s f o l l o w i n ga r et h em a i nr e s u l t s f i r s t ，af o r m a ld e f i n i t i o no fg r a p h i c a lm o d e l si sp r o p o s e d ，w h i c hr e p r e s e n t st h e c o n d i t i o n a li n d e p e n d e n c ea n dj o i n t p r o b a b i l i s t i cd i s t r i b u t i o no fr a n d o mv a r i a b l e si na n 8 - t u p l ef o r m a l i s m s e c o n d ，t h eg a u s s i a ne x a c tv a r i a t i o n a li n f e r e n c ea l g o r i t h ma n dt h e g a u s s i a nm e a nf i e l dv a r i a t i o n a li n f e r e n c ea l g o r i t h ma r ed e s i g n e db a s e do nt h eg a u s s i a nm a l k o vr a n d o mf i e l dm o d e l s 1 1 1 砌，t h ee l e m e n t a r yp r o p e r t i e s ，s u c ha sc o n v e r = g e n c e ，a c c u r a c ya n dc o m p l e x i t y , o ft h ea l g o r i t h m sd e s i g n e di nt h i st h e s i sa r ei n v e s t i - g a t e d f i n a l l y , t h et h e o r e t i c a lr e s u l t sa l ed e m o n s t r a t e db yn u m e r i c a ls i m u l a t i o ne x p e r - i m e n t s k e yw o r d s ：g r a p h i c a lm o d e lv a r i a t i o n a li n f e r e n c e m e a nf i e l d c o n v e r g e n c e a c c u r a c y 主要符号对照表 图模型 图模型的有限顶点集 图模型的边集 图模型上的变量集 概率分布族 变量集s 上的分配函数 配分函数 矩阵么，b 的内积 对数配分函数 侈y e x 尹哪z 锕 插图索弓 插图索引 图2 - 1精确概率推理6 图2 2无向有环图模型上运行消元算法8 图2 3联合树9 图4 1一阶均值参数的收敛过程3 4 图4 2对数配分函数的收敛过程3 5 3 7 算法索引 算法索引 算法2 1 消元算法6 算法2 2 和积算法7 算法2 - 3 联合树算法1 0 算法3 - 1g e v i 算法。2 4 算法3 2g a u s s s e i d e l 迭代算法2 5 算法3 3g m f v 算法，2 6 3 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位做储躲咖啼签字吼口刁年6 月，户 学位论文版权使用授权书 本学位论文作者完全了解鑫鲞盘鲎有关保留、使用学位论文的规定。 特授权盘洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位敝储虢豫嘶 签字日期：劢呷年石月仁日 导师签名： 签字日期：幻d 年 古 6 f 尹日 痧月 第一章绪论 第一章绪论弟一早强下匕 本章概述研究背景和论文主要工作。 1 1 工作背景 图模型起源于2 0 世纪8 0 年代，由统计学家s p i e g e l h a l t e r 和l a u r i t z e n 1 , 2 】， 与计算机科学家p e a r l 独立提出 3 】。随后，j o r d a n ，b i s h o p ，c o w e l l 等对图模型理 论及其应用做了进一步研究，使图模型逐步成为人工智能学科的研究热点 “】。 国内也开展了贝叶斯网络、链图等学习与推理的图模型研究工作 7 - 1 0 】。 图模型涵盖了隐马尔可夫模型、卡尔曼滤波、主组件分析、独立组件分析、 马尔可夫随机场和b o l t z m a n n 机等模型，是一种重要的知识表示方法，可根据条 件独立性对联合概率分布进行模块化表示，降低了不确定性知识表示和推理的 计算复杂性。 图模型精确推理的计算复杂性随图模型团的规模而指数级增加，故提出了 各种近似推理方法，如采样方法 1 l 】、变分方法【1 2 】等。采样推理方法是根据己知 概率分布生成样本，利用样本计算目标概率分布，实现简单，应用广泛，但计算 量较大且较难判断算法的收敛性。变分推理方法将概率推理问题转化为泛函极 值问题，通过近似求解泛函极值计算目标函数的上下界。该方法不仅克服了采 样方法的缺点，同时具有坚实的理论基础和严格的上厂f 界计算特性，受到图模 型近似推理研究界的广泛关注。 变分推理可追溯到统计物理的自由能量。s a u l 等在s i g m o i d 模型上奠定了 近似变分推理的统计学理论基础 1 3 , 1 4 ，并应用于n o i s y o r 网络、贝叶斯神经网 络、隐马尔可夫等模型中。j o r d a n 从凸分析角度给出了指数族变分推理的一般 表示形式，并发展出多种图模型近似变分推理方法 1 5 。目前，图模型变分推理 研究主要集中于以下三个方面：第一，研究变分推理理论，改进近似变分推理方 法，如辅助变分 16 1 、b e t h e k i k u c h i 变分 1 7 ，1 8 】、凸松弛变分 1 9 - 2 1 、对数行列式松 弛方法【2 0 等。第二，扩展变分推理方法的应用领域，包括方法应用和实际应用。 第一章绪论 方法上，变分推理己应用于各种模型的参数学习，如隐马尔可夫模型【2 2 1 、混合 模型 2 3 1 、混合因子模型【2 4 】、状态空间模型 2 5 】，取得了较好的近似结果；实际中， 变分推理已应用于医疗诊断 2 6 1 、通讯编码 2 7 】、生物信息学 2 8 】和图像识别等领 域。变分推理的发展方向之一即是拓展应用的深度和广度。第三，研究变分推理 的统计性质。现已开展了关于变分近似学习的收敛性、一致性、随机复杂性等问 题的研究 2 l 】。其中影响较大的是英国格拉斯哥大学统计学系的t i t t e r i n g t o n 教 授研究组，在状态空间模型、高斯混合模型、指数族等模型上，关于变分贝叶斯 参数学习的一致性、收敛性、收敛速度等研究工作【3 4 】。 可见，现有变分推理理论研究工作主要从统计观点来研究变分推理方法，很 少专门地研究变分推理的算法及其基本性质。 1 。2 本文工作 本文在高斯马尔可夫随机场模型上对最基本的均值场变分推理算法及算法 的基本性质进行了研究。首先给出了图模型统一的形式定义，总结了图模型变 分推理框架，然后设计了高斯精确变分推理算法和高斯均值场变分推理算法，研 究了高斯均值场变分推理算法的收敛性、精确性和复杂性，最后通过实验验证 了上述理论结果。 2 第二章图模型 第二章图模型 本章给出图模型形式定义，概述图模型精确推理、变分推理和指数族模型， 分析图模型研究现状。 2 1 形式定义 满足条件独立性的概率分布族与满足相应概率公理的概率分布族是等价的。 图模型体现了这一等价性。 定义2 1 ：条件独立 设x 是随机变量集，尹是一概率分布，x 尹，尺，s ，丁x 。若 p 僻，s l y ) = p ( r i t ) p ( s i t ) ， 则称给定丁时尺与s 条件独立，记为r 且si 丁。 定义2 2 ：图模型缪是一八元组 多= ( k e ，五b ，d ，s ，q ，功， 其中， i v ：非空有限顶点集； 2 e ：ecv xv 是边集； 3 x ：离散随机变量集x = x l ，x 2 ，确 ； 4 6 ：b ：x _ y 是顶点与随机变量的一一对应； 5 d ：记d f 是x f 的值域，则d = d f i x i 椰； 6 s ：变量族，阍= m ，s 2 x 由条件独立性确定； 7 q ：对s s ，分配函数c o s ：n x ，酣d i _ r 非负，q = c o sis s l ； 8 尹：模型上的概率分布族表示为：尹= p ， 聃= 学，配分函数z ：i - - i c o s ( s ) 。 3 第二章图模型 图模型分为有向图模型和无向图模型。有向图模型又称贝叶斯网络，它的 分配函数是所有父节点到子节点随机变量间的条件概率分布。 定义2 3 ：有向图模型 侈= ( k e ，x 6 ，d ，s ，q ，即， 是一个图模型，其中， 1 e 是有向边集，( “，1 ，) e 表示从甜到1 ，的有向边； 2 蛳表示s 中所有父顶点到子顶点随机变量间的条件概率，即 蛳( s ) = p ( x il 确f ) ) ， 其中， x i u x t r ( i ) = s ，且s 的结构满足 v s x ( o 【j s q 3 x ( x sa 咖( ) ，sa y x e ) ) ) ； 3 联合概率分布为： p = 兀p ( 磁i 碱d ) 。 f = 1 无向图模型又称马尔科夫随机场( m a r k o vr a n d o mf i e l d ，m r f ) ，它的分配函 数是势函数。 定义2 4 ：无向图模型 缪= ( k e ，x b ，d ，5 ，q ，即， 是一个图模型，其中， 1 e 是无向边集，( 甜，v ) e 表示 ，之间的无向边； 2 蛳表示极大团s 上的势函数，即娜 ) = 蜘 ) 。s 的结构满足 v s 五，( o ) s q v x v y ( x ，y s ( 6 ( 功，6 0 ，) ) e ) ) ； 3 联合概率分布为： 聃= i - i i m _ _ 丁l 妒s i ( s i ) ， 4 d s l s 妒 所兀脚 = z 第二章图模型 在概率推理过程中，通过父化过程( m o r a l i z a t i o n ) 可将有向图模型转化为等 价的无向图模型【3 5 1 ，所以仅考虑无向图模型上的概率推理问题即可。 2 2 精确推理 下面简要介绍图模型精确推理方法一消元算法、和积算法、联合树算法，详 细分析可参考 3 5 - - 3 8 。 2 1 2 1 消元算法 消元算法是根据消元次序，将除目标变量以外的其余变量通过求和从联合 概率中消去，计算出目标变量的边缘概率分布。求和消元过程是消息在图模型 的分配函数之间传播的过程，故又称消息传播过程。在图2 1 ( a ) 所示的有向图 模型中，根据消元次序( 1 ，2 ，4 ，3 ) ，计算边缘概率分布p ( x s ) 。消元算法的消息传 播过程如图2 - 1 ( b ) 所示。且 p ( x s ) = 尸( 砣，x 3 ，泓，x s ) x 3x 4x 2工l = l 以x 5x 3 j ：一 工3 = y p ( x 5ix 3 j 一 x 3 = p ( x 5 x 3 x 4 x 4 尸( 泓i 爿弘i 砣 只泓ix 3 ) m 2 3 ( x 3 ) x 3x 4 - - e p ( x 5x 3 ) m 2 3 ( x 3 ) 肌4 3 ( 扔) x 3 = m 3 5 ( x 5 ) 。 砣) p ( x 1 ) p ( x 2x 1 ) x 1 x 2 ) m 1 2 ( x 2 ) 根据图模型定义，树型结构图模型的联合概率分布为尸= z 1 兀f u 却( x i ) i - i ( 切u 即 f ，x j ) 。令m u ( x j ) 表示变量x i 传递给变量x j 的消息， 则 m u ( x j ) = o ) x i ( x 加圳( 。) 几m k i ( x i ) 。 x i k n ( i ) j 5 x x 以 以 砣 、，、， z x 第二章图模型 在上述符号下，树型结构上消元算法的伪码描述如算法2 - 1 所示。 算法2 - 1 消元算法 算法： e l i m i n a t i o n ( g ，p ( x ，) ，d 输入： 图模型缪= ( e e ，五6 ，d ，s q ，研， 目标节点变量鲫， 消元次序，。 输出： 边缘概率分布尸( 勋) 。 过程： 1 循环消元：根据消元次序，对f j 进行消元， m i j ( x j ) , , - - o j 柳( x i ) o - l 呐j ( x i , x ) 几m k f ( x i ) 。 x i 托( d j 2 归一化输出：p ( x f ) = 夏l - ，i 兀s n 。( 州t ) m 。s m t ( 。x t ( ) 历。 消元算法存在两个问题：首先算法的计算复杂性在最优情况下由树宽决定， 但找出达到树宽的消元次序是n p 难问题【3 9 】；其次每运行一次消元算法仅得到 单个变量的边缘概率，运行多次消元算法时消息被重复计算，降低了算法的效 率。 x 4 x 5 x 4 ( a ) x 4x 5 ( c ) 图2 1 ：( a ) 有向图模型，( b ) 按照( 1 ，2 ，4 ，3 ) 的序列运行消去算法，( c ) 和积算法中生成 的消息集 6 第二章图模型 2 2 2 和积算法 和积算法( s u m - p r o d u c ta l g o r i t h m ) 是在树结构模型上计算出所有消息，如 图2 1 ( c ) 所示，然后充分利用消息，计算节点的边缘概率。节点变量辫传递给 节点变量x ，的消息聊f ， ，) 为 m i j ( x j ) = ( x i ) o g x i , x j ( x i ，巧) 几m k i ( x i ) ，( 2 - 1 ) x ik e n ( i ) j 其中，( 力表示变量f 的相邻变量集合，m i j ( x j ) 表示变量f 到变量的消息。在 树型结构中，节点变量的边缘概率分布可以通过相邻节点间消息的乘积计算，即 尸( x i ) c i cu 柳l ( x f ) l l m k i ( x i ) 。( 2 - 2 ) k e 。n 1 ( 。i ) 称公式( 2 1 ) ，( 2 2 ) 为和积算法。和积算法共需要计算2 1 e i 条消息，假如节点变 量为离散变量，其势为r ，则和积算法的计算复杂性为o ( i e i p ) 。但和积算法仅适 用于树型结构的图模型。和积算法的伪码描述如算法2 2 所示。 算法2 2 和积算法 算法： s u m p r o d u c t i o n ( 侈，p ( x f ) ) 输入： 图模型够= ( k e ，x b ，d ，s ，q ，尹) 。 输出： 所有消息m j i ( x i ) ， 所有节点的边缘概率p ( x ：o 。 过程： 1 循环计算消息： m j i ( x i ) 哟( 一) 协竹 ( x j ) 几m k j ( x j ) 。 x j k e n ( j ) l i 2 循环计算边缘概率： p ( x f ) o cc o x y ( x f ) 几m “跏。 睢 3 归一化输出： e ( x y ) = m x f b dn e 州) m e f ( x f ) 7 第二章图模型 x 4 x 3x 5x 3x 5 、 ( 口)( 6 ) 图2 2 ( a ) 无向有环图模型，( b ) 按照( 5 ，4 ，3 ，2 ) 的序列运行消去算法 2 2 - 3 联合树算法 联合树算法( j u n c t i o n t r e ea l g o r i t h m ) 结合了消元算法和和积算法，是有环图 模型上概率推理的有效方法。它首先根据消元算法将有环图模型转化为三角化 图模型，然后在三角化图模型上构建联合树，最后在联合树上运行和积算法。 如图2 2 ( a ) 所示的无向有环图，在消元次序( 5 ，4 ，3 ，2 ) 下采用消元算法计算 边缘概率p ( x 1 ) ，则 雌) = 三( x 2 ) z t 0 1 3 ( 礼x 3 ) z t 0 2 4 ( x 2 川蝴( x 3 , x 5 ) 0 ) 4 5 ( x 4 ，x s ) - ! 一yo , 1 2 ( 礼砣) ( 札x 3 ) z 0 9 2 4 ( 砣，x 4 ) m 3 2 ( 泓) = z 1 u 1 2 l ，砣) 叫1 3 ( x 1 ，x 3 ) m 2 1 ( x 2 ，扔) 。 显然，消去变量x 5 后产生从变量x 5 传递到变量集i x 3 ，x 4 ) 上的消息m 3 2 ( x 3 ，x 4 ) 。 同理，消去变量x 4 后产生消息m 2 1 ( x 2 ，x 3 ) 。此时无向有环图2 - 2 ( a ) 转化为三角 化图模型2 2 ( b ) 。 在三角化图模型下形成的团分别为c l = x l ，x 2 ，x 3 ，c 2 = x 2 ，x 3 ，x 4 ，c 3 = x 3 ，x 4 ，x 5 ) ，定义相应的势函数 t o c l ( x l ，x 2 ，x 3 ) = 0 ) 1 2 ( x l ，x 2 ) t 0 1 3 ( x 1 ，x 3 ) ， w c ：( x 2 ，x 3 ，x 4 ) = t 0 2 4 ( x 2 ，x 4 ) ， t o c 3 ( x 3 ，x 4 ，x 5 ) = 4 0 3 5 ( x 3 ，x s ) o l ，4 5 ( x 4 ，x s ) 。 8 第二章图模型 联合概率分布的表示形式 图2 3 联合树 尸( 曲= 乏1u 1 2 1 ，砣) 1 3 1 ，x 3 ) t 0 2 4 ( 砣，x 4 ) o u 3 5 ( x 3 ，x 5 ) c 出5 ( 鞠，x 5 ) = 刍a - ，勉，秘q 阮，秘，弘) q ( 毛，弘，x s ) 。 联合树结构是由团节点构成的树型结构，如图2 3 所示。团节点之间的“边“一 一团之间的消息一由两团的交集组成。例如m 2 3 ( x 3 ，x 4 ) 表示团c 2 传递给团g 的消息，且是变量秘和弘的函数。 联合树算法是在团之间传播消息，得到团的边缘概率。团g 到团0 的消息 可以形式化表示为： m i j ( x s 玎) = u g ( c f ) 几m k i ( x s 船) ，( 2 - 3 ) c i s q 艇( f ) v 其中，s q = g n c j ；聊玎表示团c i 传递给团c i 的消息；( f ) 表示团c i 在联合树 中的邻节点( 团) 的集合。联合树中边缘概率分布可以形式化表示为： p ( x c i ) o c 叫g ( c f ) iim u ( x s 蔚) 。 ( 2 4 ) 稿皈力 公式( 2 3 ) ，( 2 4 ) 称为联合树算法。伪代码描述如算法2 3 所示。联合树算法显 然是和积算法的一般化形式。联合树算法有两个困难：第一，找到最优消元次序 是n p 难问题，故找到最优三角化转换也是n p 难问题；第二，该算法的计算复 杂度随团的规模而指数级增加，在稠密图中联合树算法是难解的，需借助近似推 理方法。下面详细分析确定性近似推理方法变分推理方法。 2 3 变分推理 变分推理是重要的确定近似推理。下面分析变分原理，给出凸对偶原理基 9 第二章图模型 算法2 - 3 联合树算法 算法： j u n c t i o n - t r e e ( 9 ，1 ，尸( g ) ) 输入： 图模型够= ( g , e ，x , b ，d ，s ，q ，尹) 。 输出： 团节点的边缘概率分布p ( g ) 。 过程： 1 三角化图模型多。 2 循环计算团之间的消息： m i j ( x s i l ) 卜( g ) 几m k i ( x s k i ) 。卜乞c ，( g ) j l 。 c i s u k n ( o k 3 计算团的边缘概率： m c i ) o c 几m k i ( x s 甜) 。 艇( f ) 4 归一化输出： p ( x c i ) = t o c f ( c i ) il k n ( i ) m k i ( x s 肼) c i 0 9 c 。i ( c i ) i 。- i k e n ( i ) m k i ( x s k i ) 。 础上的变分推理框架。 2 3 1 变分原理 泛函极值问题又称变分问题，寻求泛函极值的方法称为变分法。几何学和 物理学中的最短线程问题、最短降落线问题、最小回转曲面等经典问题都属于 变分问题。变分推理的基本思想是，根据凸对偶原理把概率推理问题转化为泛 函极值问题，通过近似求解泛函极值计算出目标函数的上厂f 界。 凸对偶原理是变分变换的基础，它通过引入共轭参数和共轭对偶函数对目 标函数进行变分变换。凸对偶原理下，凸函数厂( 劝的最优化表示形式或变分表 示形式为 厂( 功= m a x i x lx 一厂( ” ，( 2 5 ) t ，、 其中，九表示共轭参数，a 表示共轭空间，广( 九) 为函数以砷的共轭对偶函数，且 厂( 九) = m a x x 。x 一八曲l 。( 2 6 ) l o 第二章图模型 显然，当九= v f ( x ) 成立时，最优式( 2 6 ) 取得最值。故变分式( 2 5 ) 中的共轭空 间a 为函数f ( x ) 的梯度空间。对凹函数可以进行类似的分析，只需将上式中的 最大化问题换成最小化问题，计算出函数的上界。变分变换将非线性函数厂( 曲 转化为一组线性函数上的最优化问题，通过近似求解线性函数计算出厂( z ) 的上 下界，降低了计算复杂性。 在图模型毋中，概率推理的关键是计算配分函数z z = 2iit o s f f ) 。 ( 2 - 7 ) 。i 。x 。) i 1 图模型变分推理分为分配函数方法和配分函数方法。分配函数变分推理根据分 配函数t o s 的凹凸性，对t o s 进行变分变换，再根据不同的近似策略计算出目标 函数z 的上下界。配分函数变分推理根据配分求和函数的对数凸性质，直接对 l n z 进行变分变换，再通过近似求解变分式计算出l n z 的上下界。 2 3 2 分配函数方法 分配函数变分推理方法是根据分配函数娜的凹凸性对其进行变分变换，计 算出t o s 的上下界，分别记为叫乡q u ) 和( 舻) ；再根据不同的近似策略求解配 分函数z 。现有两种近似策略，一是对配分函数z 中所有的分配函数t o s ，进行变 分变换，再计算出配分函数z 的上下界。以上界为例，此时配分函数上界表示形 式为 求解式( 2 - 8 ) 右端即可计算出配分函数z 的上界，对下界可以进行类似的分析。 这种近似策略实现简单但精度不高。一是仅对部分分配函数进行变分变换。即 按某种顺序依次对分配函数螂，进行变分变换，当“剩余”分配函数的乘积可以 进行精确推理时停止变换，对剩余模型结构进行精确推理。这种方法不仅控制 了计算复杂性，而且提高了近似的精确性。 分配函数变分推理方法要求图模型的分配函数具有对数凹凸性，能根据 82 u a 、_ v 。 蝴 耀 兀，m兀，x x i i + 爿& t h e ) ) 。( 2 1 6 ) z 6 l o c a l ( g ) y e d i d i a 通过引入拉格朗日乘子求解上式，并证明b e t h e 近似变分推理的求 解过程等价于l o o p y 环传播算法【1 7 , 4 8 】 k i k u c h i 近似变分方法是b e t h e 近似变分方法的一般化形式，它是以超 树为基础进行近似变分推理【1 7 ，1 8 。k i k u c h i 近似变分方法采用满足超图局 部约束条件的约束外集l o c a l ，( 缪) 作为变分参数的约束域；采用超树熵 耽p p 来近似表示原概率分布的熵函数。则k i k u c h i 近似变分表示形式为 s u p ( 口，p - a a p p ( 1 1 ) 。 ( 2 - 1 7 ) t e l o c a l t ( ：缪) 理论证明可以通过构建一般信念传播算法( g e n e r a l i z e db e l i e f p r o p a g a t i o n ， 简称g b p ) 来求解k i k u c h i 变分问题 1 8 ，4 9 ，5 0 。 b e l e k i k u c h i 近似变分方法主要存在以下问题：首先，b p g b p 近似 变分方法不一定收敛至稳定的不动点；其次，b e t h e k i k u c h i 近似变分方法 成对马尔可夫随机场，批所有的分配函数o a s ，最多包含两个随机变量，即相应的充分统计量c s ，只有 两种表示形式： 即 或妒f 即以l 其中工七 l ，撑l ，疗为图模型中随机变量的个数 1 6 第二章图模型 只能计算出配分函数的近似值，而非上下界；再次，由于b e t h e k i k u c h i 近似 变分推理的非凸性，故求解过程会出现局部最优值。之后发展出多种解决 这些问题的方法，如c c c p 算法 1 8 】、u p s 算法【5 1 1 、凸约束算法【5 2 】等。 3 凸松弛变分推理 凸松弛变分推理是以b e t h e k i k u c h i 近似变分推理方法为基础，它克服 了b e t h e k i k u c h i 变分方法的缺点，不仅可以计算出配分函数的上界，而且 可以计算出全局最优值【l 她1 。凸松弛变分方法的基本思想是，采用外凸集 l o c a l ( g ) 作为变分参数的约束域；采用图模型生成树的熵的凸组合近似 表示概率分布熵函数，它同时是所求熵函数的下界。令扣p ) 表示生成树凸 组合的边的概率分布，则概率分布的熵函数的下界可以表示为 坝x ；眦) ) 阴+ ( 丁) ) 】= e p 风帆) _ s t ( u ，f ) ， 一 j 矿 ( 文t ) e e 凸松弛近似变分推理的形式化表示为 一 、， 钺d 代l 。m c a a l x ( 缈 ( 9 j ) + ；风p 一( 髻s 如。力 o 可以通过构建加权树信念传播算法( t r e e r e w e i g h t e db e l i e f p r o p o g a t i o n ) 来 求解上述凸松弛变分推理问题。基于k i k u c h i 变分方法的凸松弛变分方法， 是以图模型的生成超树为基础进行近似变分推理，是凸松弛方法的一般化 表示形式 2 1 1 。 4 对数行列式松弛变分推理 对数行列式松弛变分推理方法是以高斯分布模型为基础，采用半正定 外边界o u t ( k ) 作为变分参数的约束域，它是精确约束域的凸外集；采用 具有相同协方差的高斯分布的熵来近似表示概率分布的熵函数，此时可以 计算出对数配分函数的上界 2 0 】。