贝叶斯网络参数的在线学习算法及应用

第H卷第;#期小型微型计算机系统7.LHa7);###E年;#月=IaI2=IJKcdcA*=cK81)##E贝叶斯网络参数的在线学习算法及应用张少中’杨南海’王秀坤:大连理工大学计算机科学与工程系’辽宁大连;;&#$摘要!以*=算法为基础’在给定贝叶斯网络结构情况下’研究分析了71-?@*=算法并利用该算法对防洪决策贝叶斯网络进行在线参数学习’将该算法与*=算法的学习结果进行了比较分析’结果表明71-?@*=算法不但能够进行在线参数学习’而且也具有较高的学习精度)关键词!贝叶斯网络9参数学习9*=算法971-?@*=算法中图分类号!AB$C;文献标识码!D文章编号!;###%;#:##E;#%;FCC%#$GHHIJKLMJNONPQOIJORSRLTOJOUGIUNTJMVWPNTXLYRZJLO[RM\NT]^LTLWMRT_‘Dabc6,7%367?@’dDaba,?%6,-’eDabf-0%g0?:hijklmniompqrpnjsmiltuvioui’hkwvkoxovyilzvm{pq|iu}opwp~{’hkwvko;;&#$r}vokG!ZMTLKM!D71-?@*=,.@7-16+#6-86-$%,$&/*=-$/-$80$$&/,?/,’’.-&/-?16&’,,+&1&7?.-?&.&,?-?@-?(.77//&8-$-7?$0’’71-?@),*&$-,??&1#7g$-?16-$’,’&))716*=,.@7-16+,?/71-?@*=,&,’’.-&/-?(.77//&8-$-7?),*&$-,??&1#7g$1787+’,&16&-’&(7+,?8&)A6&&$0.1-?/-8,1&$16,116&71-?@*=8,?%&0$&/-?7?.-?&.&,?-?@(7),*&$-,??&1#7g’,,+&1&,?/-1,.$76,$+7&’&8-$&.*16,?1,/-1-7?,.*=,.@7-16+)+RY\NT,Z!%,*&$-,??&1#7g$9’,,+&1&.&,?-?@9*=,.@7-16+971-?@*=,.@7-16+-引言贝叶斯网络是根据各个变量之间的概率关系’使用图论方法表示变量集合的联合概率分布的图形模型)该模型是一个有向无环图’其中每个结点代表一个随机变量’并通过给定结点的条件概率与其父结点相关.;/)贝叶斯网络的学习可划分为两个方面!结构学习和参数学习)结构学习是利用训练样本集’尽可能结合先验知识’确定合适的贝叶斯网络拓扑结构9参数学习是在给定贝叶斯网络拓扑结构的情况下’确定各结点处的条件概率密度)一般情况下’利用批量样本数据的参数学习是离线进行的’其参数值并不能随新数据集的实时增加而及时地在线进行参数的更新和调整’这样就不能实现数据的充分利用’并影响参数学习的精度.’$/)因此我们需要一种当新数据到来后’能够及时进行参数学习和调整的贝叶斯网络在线参数学习方法)0贝叶斯网络和参数学习0)-贝叶斯网络在贝叶斯网络的有向无环图中’结点代表论域中的变量’有向弧代表变量的关系’变量之间的关系强弱由结点与其父结点之间的条件概率来表示)通过贝叶斯网络可以准确的反映实际应用中变量之间的依赖关系)关于一组变量12;’2’)))’2?3的贝叶斯网络由以下两个部分组成!;一个表示f中变量的条件独立断言的网络结构c9与每一个变量相联系的局部概率分布集合B’c是一个有向无环图’c中的结点一对一地对应于f中的变量’结点之间缺省弧线表示条件独立’c和B定义的f的联合概率分布)根据条件独立的性质’联合概率分布为!oj:4;’4’54o6789j:4;’4’54v2;’7:;v8;对于每个变量2-’令:-;12;’2’5’2-2;3是2-的父结点’12;’2’5’2-2;3条件独立’则!j:4v64;’4’54v2;’78j:4v6v’7:0)0贝叶斯网络的参数学习贝叶斯网络的参数学习人们已经做了大量的研究工作.’$/)给定数据变量集和贝叶斯网络结构4’5’43’$o对于网络结构中的每个变量4’v其值域为l54v3’=81’’5’;+3为数据样本’v为变量2-的父结点集则表示?@给定父节点集为第种可能取值时’’j:4v6v!vA结点2-为第g种取值的概率’记为!Bv@?)贝叶斯网络参数学习的目标是!给定网络拓扑结构c和训练样本集=’利用先验知识’确定贝叶斯网络模型各结点处的条件概率密度’记为!j:B6h’t)0)CDE算法*=算法是一种计算最大似然函数:=F的通用算法.&/’F,0-1&?已经提出它可以应用于贝叶斯网络的参数学习)在该算法中’对于所有的参数集合=和所有的变量2-’计算条件概率:m给定数据集其似然函数为!j:4v’v6hw’B)=’?@:$w:B6h8G.?j:h6B8Gq:4@’v.?Bv@?wv@?万方数据14;v’4v’c’814;’4’收稿日期!##$%#$%#&作者简介!张少中’博士研究生’研究方向为数据库的知识发现(决策支持系统)*%+,-.!/.0123445671+,-.87+9王秀坤’教授’博士生导师’研究方向为数据库系统’决策支持系统9杨南海’硕士’研究方向为数据库的知识发现(决策支持系统)5e11小型微型计算机系统o11.年这里$%表示当且时在数据集中的取!#%&’()#(*$’(*%值&最大似然函数+可以由下式得到,+(%$*!#%$&’(%).)-!#%$&’(%)/0算法的主要思想是在开始设定一个初始估计1)然+&后不断地修正它2从当前的估计+&到下一个估计+需要3)345)两个步骤,期望计算和最大化2期望计算是计算给定6时&当前+的似然函数期望,3)3)?)78++)*99:;=7&78)+78=7&+)7#(对于所有的&应满足8345))@83))&根据式A)+7++7++有,3)$%(%$)B)7+8+)*9!3#(&’():;+(&%&$这里&)9&8&3)!3#(’(#(C(=7+7最大化计算是通过最大化当前期望似然函数值&选择下一个估计+345)),345)3)+(%$*DEFGDHIJK=8+)8=&+&LM*d&n)*59#)cn#))opn#)51)o#因此‘Z‘%‘Z55)d+&+*99K+’(*’)(d+(%+(%)(%O2qPQRSTUVW算法给定样本数据集=*[\5&]&\r_&初始参数定义为Z+&根据函数‘‘‘Z则参数学习由下式实a+)*b7+8=)cd+&+)&现JA&.M,‘‘+*DEFGDH+Ja+)M8‘Z‘5o)*DEFGDH+Jb7+=)cd+&+))M对于所有的s和t&$+(%$*5有&根据文献J.M有,‘ZI+ZJ#($&’(%8=M)I+ZJ’(%8=M)Z+(%$*+(%$4bcv+(%$5A)u%u%其中,K’()K’()Z$%5g$%5.)I+J#(&’(8=M*9K#(&’(8\7+)u%为g7*5Z%的一个估计值表示为,K’()K+’(*’()&u%Z%5g%Z5?)K’)*(I+’8=(_*9K’8\&(7+)g7*5!#($&’(%)N)9%!#($&’(%)式B和式N分别为/0算法的期望计算和最大化计算等式2OPQRSTUVW在线学习算法描述和分析O2X基本定义假定有当前模型Y&条件概率参数为Z+&数据集为=*[\&]&\^_&每个数据集\7可能为网络中变量的部分赋值&在线学习就是根据数据集=和参数为Z+的模型构造新的模型‘+2在通常情况下&‘是可以通过似然函数来获得的&如算法+/0中的‘8)&但是当模型为在线情况时&似然函数并不是影7+=响‘+的唯一参数&此外还应包括旧模型本身2这是由于我们所得到的模型已经是前面学习过程的结果&不能完全忽略该结果而完全依赖似然函数2因此&应该同时考虑似然函数和当前模型共同的影响2定义函数a表示似然函数和当前模型的共同影响新模型的函数记为‘&a+),‘‘‘Ze)a+)*b7+8=)cd+c+)7+‘8=)为新模型+‘f数据集=的标准似然函数&根据似然函数的定义有,‘5g‘i)7+8=)*9:hFK+\)7g7*5参数b为学习的速率且bj1&其大小决定参数调整前后新旧模型的依赖程度2b接近于5&则表示参数调整偏重于当前数据而轻于原来模型&参数调整的速率就快&新模型变化显著kb趋近于1&则表示参数调整偏重于原来模型而轻视当前数据参数调整缓慢&模型变化较小&本文不考虑bj5的情况2d‘+cZ+)为参数学习前后新旧两个模型参数距离的估计值&其功能是使得新模型更接近于旧模型&减少新旧模型间的落差2该距离万是方一数种据平方距离&记为,d‘Z+&+)2两概率分布lfm的平方距离表示为,该算法可以用于离线的处理批数据的情形&也可以进行在线参数学习2当处于离线批处理数据时&数据集6中包含多个数据&参数b取值为5&则该算法变成类似/0算法&期望计算是计算等式5.&最大化计算是计算条件概率等式5A2采用whxs;F/0算法的在线参数学习按以下规则JAM,$%zc5当u%时zzc5K#(&’(8\z&+)5)K’()y1&+(%$*+(%$4bJu%cK’()%zc5K’(8\z&+)3c7u%v+(%$MK’()当u%zzc7o)K’()*1&+(%$*+(%$ku%是旧模型的概率估计u%%zc5K’()&K’()*K’(8\z&+)当数据不完整时&应用上述规则可以很好地进行处理&根据具体应用选择合适b&就可以完成贝叶斯网络参数的在线学习2当数据完整时&上述规则可以简化为,5)当K’%8\)*5且K#$8\)*5时&(z(zzzc5+(%$*b45cb)+(%$ko)当K’%8\)*5且K#$8\)*1时&(z(zzzc5+(%$*5cb)+(%$k否则zzc5A)&+(%$*+(%$k简化的在线参数学习规则解释为,当变量(在第%个状态的值可以观测到并且(等于其第$个值时&增加参数+(%$的值k当变(量在第%个状态的值可以观测但(不等于其第$个值时&减少参数+(%$的值k当变量(的第%个状态的值不可以观测时&不进行更改2{PQRSTUVW算法在防洪决策贝叶斯网络在线参数学习中的应用和性能分析{2X在线参数学习的条件概率密度在防洪决策贝叶斯网络中&给定包含^|个样本的训练样本集=*[d5&do&]&d^|_和贝叶斯网络拓扑结构L&需要确定贝叶斯网络模型各个结点处的参数&采用文献J?M中的结果&$J期张少中等%贝叶斯网络参数的在线学习算法及应用$sJ$利用黑龙江省某水库防洪数据库数据!相关样本数据经过离散化!采用#算法得到的防洪决策贝叶斯网络结构见图$%图$防洪决策贝叶斯网络结构拓扑图&’()$*+,-.+-,./001//22.3’4’/564-77/,+’5(89:.4’955.+;/,4地区降雨量=$?@入库流量=#?@出库流量=A?@水位=B?@坝高=C?@出险=D?@灾情损失=E?!属性参见文献FCG)图#条件概率值=实线为HIJ)J$@虚线为HIJ)JC?&’()#K/52’+’/5917,/L9L’1’+’.4=4/1’21’5.’4;M.5NIJ)J$952O/’21’5.NIJ)JC?利用上述防洪决策贝叶斯网络结构!假定数据是完整的!网络结点为E个!每个数据集中的记录为DJJ个)采用P/+’5(QR算法获得的结点D的条件概率结果如图#=其它结点略?)S)T参数学习的质量评估标准采用参数学习算法从训练样本中获得的条件概率密度为UV=WXY=Z??!由于实际结点处的条件概率密度U=WXY=Z??是已知的!于是作为结果的条件概率密度UV=WXY=Z??与真实的条件概率密度U=WXY=Z??之间的差别可以用来作为评价参数学习结果的测度)这里采用[-1L936\.’L1.,距离进行计算![-1L936\.’L1.,距离定义为%]=U!UV?I^^=_=WXY=W?1/(=_=‘XY=W????Y=W?W=_V=WXY=W??=#$?这里[\距离大于