584 控制理论 与应用 第20卷 G(S,S·）=(S,S).这样抽样序列中的下一个 iiP氏灯1m,,s) 样本点定是其有较大后验概率的S”,也就是说， m=11.1. 式(4)所示的抽样序列有着向网络结构模型空间屮 川iP(xW1,i.s) 具有较大后验概率的模型靠近的趋势，因此可以将 m=【1=1 MCMC方法作为一种搜索算法来使用. .s) 4网络结构先验概率P(S)和接受概率A m■【=1 P(X1,©i,S) (S',S·)的计算（Computation of prior PX1m,⊙，S)P(X探1m,⊙.S) P(S)and acceptance probability A(S'. 形=1 P(1,⊙，S)P(x1R,©，) $) (7) 在Metropolis-.Hastings算法中，需要给出网络结 上式表明，在计算P(DIS·)/P(DIS)时，只需要 构的先验概率P(S)和计算两个网络结构模型下样 两个结点X,X在两种网络结构S,S·下的4组网 本似然的比值P(DIS·)/P(DIS). 络参数的MLE估计6，白：，和©就足够了，与 4.1网络结构的先验概率P(S)(The prior probabil- 其它节点是无关的 ity P(S)for the network structure) 5算法性能与实例(Function and example of 利用不同的先验概率分布，能够灵活地控制网 algorithm) 络结构模型的某些特性，例如网络中弧的个数、树络 以Alam网络.)为例来说明本文所提出的算 中自由参数的个数等，事实上，在以某种准则作为模 法的性能.首先使用此网络抽样出10,000个数据样 型评价标准的模型选择方法中，本文的先验概率相 本，然后使用本文的MCMC方法在不同样本容量的 当于那里的惩罚项，本文使用Bayes信总准则(BIC) 数据下抽样得到·个网络结构的序列，在本例中抽 中的惩罚函数作为网络结构的先验概率 出5000个网络结构样本.其中在网络结构的生成 log P(S)=-og (-)+c, 中，弧的添加、删除、反向操作以及保持原网络结构 不变这4种情况是等可能发牛的，因此在各种情况 (6) 下，产生概率G(,S‘)都为1/4.数据样本的容量 其中c是归-一化常数，∑：(：-1)是网络中自由 出1000变化到10000，每增加1000个数据进行一次 4e1 计算.接下来在这5000个树络结构样本中找出具有 参数的个数，是节点X;的状态数，9：是Ⅱ，的状念 最大后验概率的网络结构，以此计算数据样本的似 数.显然，网络结构越复杂，式(6)所赋予的先验概率 然函数值，结果如图1所示.图中的横轴为样本容 越小.虽然式(6)给出的先验概率不是」·化的，但 量，纵轴为数据样本的似然值.图1的另一条曲线是 对于式(5)已经足够了.同时式(6)的另·个特性是 在相同的数据样本上使用B搜索算法所得的结果 它是可分解的，这使得接受概率的计算非常方便和 相对于模型空间的维数而言，MCMC方法在进行了 葡单， 非常少的5000次抽样中，就得到了与B-搜索算法相 4.2接受概率A(S,S)的计算(Computation ac 当的结果，而后者仅仅在搜索网络的第一条弧时就 ceptance probability A(,S)) 需要对37×36=1332种可能的情况进行计算 在给出产生概率G(S,S)时所定义的3种操 0104 作—一弧的别除、反向和添加一对于网络结构 而言都是一种局部性的操作，它最多只改变两个结 -2 点的父结点集合，这大大简化了接受概率A(S, -4 S)的计算. -6 假设在进行弧的删除、反向或添加时所对应的 -8 两个结点是X和X,同时在网络结构为时它们的 -10 父结点集合分别为几，和几，在S·下的父结点集合 -12 200040006000800010000 为Ⅱ；和，出式(3)，样本似然的比值P(D 图】样本似然 S‘)/P(DIS)为 Fig.1 The likelihood of the data P(DIS') P(DIS)= (下转第588页) 万方数据控 制 理 论 与 应 用 G(S，．S、)：c=(S 2，S‘)．这样抽样序列【}】的下一个 样本点-定是具有较大后验概率的S’，也就是说， 式(4)所示的抽样序列有着向网络结构模型空间中 具有较大后验概率的模型靠近的趋势，因此可以将 MCMC h-法作为一种搜索算法来使用． 4网络结构先验概率P(S)和接受概率A (s‘，S”)的计算(Computation of prior P(S)and acceptance probability A(S 7， S+)) 在Metropolis．Hastings算法中，需要给出网络结 构的先验概率P(S)和计箅两个网络结构模型下样 本似然的比值JD(D S’)／P(D S‘)． 4．1网络结构的先验概率P(S)(The prior probabil— ity P(S)for the network structure) 利用不|百J的先验概率分布，能够灵活地控制网 络结构模型的某些特性，例如网络中弧的个数、}c)!|络 中自由参数的个数等事实上．在以某种准则作为模 型评价标准的模型选择方法中，术文的先验概率相 当于那里的惩罚项．奉文使用Bayes信息准则(BIC) 中的惩罚函数作为网络结构的先验概率 1 ．Ⅳ， log P(s)=一音hg ‘ M·∑q，(‘一1)+c， j一1 (6) ．n， 其中c是归一化常数，∑q。(_一1)是网络中自由 I—I 参数的个数，_足节点x，的状态数，q。是仃。的状态 数显然，网络结构越复杂．式(6)所赋予的先验概率 越小虽然式(6)给出的先验概率不是归·化的，但 对于式(5)已经足够了．同时式(6)的另-，个特性是 它是nJ分解的，这使得接受概率的汁算非常方便和 简单． 4．2接受概率A(s‘，s。)的计算(Computation ac— ceptance probability A(S。，S‘)) 存给出产生概率c(S‘，S”)时所定义的3种操 作一一弧的删除、反向和添加——对于网络结构 而言都足一种局部性的操作，它最多H改变两个结 点的父结点集合，这大大简化了接受概率A(S1， S“)的计算． 假没在进行弧的删除、反向或添加时所对应的 两个结点是x．和飘，同时在网络结构为s2时它们的 父结点集台分别为Ⅱ，和盯女，在5、F的父结点集合 为Ⅱj和盯；，由式(3)，样本似然的比值P(D S。)，7P(D 1Ⅳ)为 ￡i旦l!j— P(D S z)一 第20卷 |I『1 P(研l』玎，自；，Si) *11l P(矸l仃f～，国?，s’) ?!，是j P(胛l玎，，0；，S2) 一 l’P(F I仃『“”，国i，s。)P(xZ‘I聊”，@j，S) 刊P(卵I田，@；，S‘)P(孵l盯f，@I，s‘) (7) 上式表明，在汁算，，(D s。)／P(D S2)时，只需要 两个结点■h也在阿种网络结构S4，s。下的4组网 络参数的MLE估计自?，自；，白；和园；就足够丁，与 其它节点是无关的 5算法·陡能与实例(Function and example of algorithm) 以Alarm网络_^-71为例来说明本文所提出的算 法的性能首先使用此网络抽样出10，000个数据样 本，然后使用本文的MCMC方法在不同样本容最的 数据卜抽样得到·个网络结构的序列，在本例中抽 出5000个网络结构样本．其中在网络结构的，l成 中，弧的添加、删除、反向操作以及保持原网络结构 不变这4种情况是等可能发牛的，因此在各种情况 下，产生概率c(s2，S‘)都为1／4．数据样本的容量 由1000变化到10000，每增加1000个数据进行一次 计算接F来在这5000个网络结构样本中找出恩有 最大后验概率的网络结构，以此计算数据样本的似 然函数值，结果如图l所示．【冬l中的横轴为样本容 量，纵轴为数据样本的似然值．图l的另一条曲线是 在相同的数据样本E使用B．搜索算法所得的结果． 相对于模型空间的维数而言，MCMC方法在进仃了 非常少的5000次抽样中，就得到r与B。搜索算法相 当的结果，而后者仅仅在搜索网络的第一条弧时就 需要对37×36=1332种可能的情况进行计算． 蚓1样本似然 Fig．1 The likelihood of_the data (下转第588页) 必 型 万方数据