基于自编码器的贝叶斯网嵌入及概率推理.pdf

基于自编码器的贝叶斯网嵌入及概率推理*杜斯1,2,祁志卫1,2,岳昆1,2,段亮1,2,王笳辉1,21(云南大学信息学院,云南昆明650500)2(云南省智能系统与计算重点实验室(云南大学),云南昆明650500)通信作者:岳昆,E-mail:摘要:贝叶斯网(BN)是不确定性知识表示和推理的基本框架,广泛用于社交网络、知识图谱和医疗诊断等领域.特定领域中基于 BN 的分析诊断和决策支持,其核心计算任务是基于 BN 进行多次概率推理.然而,使用传统的概率推理方法,基于同一 BN 的多次概率推理其中间过程存在很多重复的计算结果,具有较高的时间复杂度.为了提高多次概率推理的效率,提出易于重用和易于计算的贝叶斯网嵌入及相应的概率推理方法.首先,借鉴图嵌入的基本思想,使用点互信息矩阵来表示 BN 的有向无环图结构和条件概率参数,提出基于自编码器和注意力机制的 BN嵌入方法.其中,自编码器的每一编码层利用节点与其邻居节点(父节点和子节点)的相关性生成节点嵌入,从而在嵌入向量中保存 BN 节点间的概率依赖关系.然后,使用嵌入向量之间的距离来度量节点之间的联合概率,提出基于嵌入向量的 BN 概率推理方法.实验证明,针对 BN 的多次概率推理,所提方法的效率高于现有方法,且能得到准确的推理结果.关键词:贝叶斯网;高效概率推理;图嵌入;自编码器;注意力机制中图法分类号:TP18中文引用格式:杜斯,祁志卫,岳昆,段亮,王笳辉.基于自编码器的贝叶斯网嵌入及概率推理.软件学报,2023,34(10):48044820.http:/ Bayesian Network Embedding and Probabilistic InferencesDUSi1,2,QIZhi-Wei1,2,YUEKun1,2,DUANLiang1,2,WANGJia-Hui1,21(SchoolofInformationScienceandEngineering,YunnanUniversity,Kunming650500,China)2(YunnanKeyLaboratoryofIntelligentSystemsandComputing(YunnanUniversity),Kunming650500,China)Abstract:Bayesiannetwork(BN),asapreliminaryframeworkforrepresentingandinferringuncertainknowledge,iswidelyusedinsocialnetwork,knowledge graph,medical diagnosis,etc.The centric computing task of BN-based analysis,diagnosis,and decision-support inspecific fields includes multiple probabilistic inferences.However,the high time complexity is doomed on the same BN by using thetraditional inference methods,due to the several intermediate results of probability calculations that cannot be shared and reused amongdifferentinferences.Therefore,toimprovetheoverallefficiencyofmultipleinferencesonthesameBN,thisstudyproposesthemethodofBN embedding and corresponding probabilistic inferences.First,by incorporating the idea of graph embedding,the study proposes a BNembedding method based on the autoencoder and attention mechanism by transforming BN into the point mutual information matrix topreserve the directed a cyclic graph and conditional probability parameters simultaneously.Specifically,each coding layer of theautoencodergeneratesnodeembeddingbyusingthecorrelationbetweenanodeanditsneighbors(parentandchildnodes)topreservethe*基金项目:国家自然科学基金(62002311);云南省基础研究计划杰出青年项目(2019FJ011);云南省重大科技专项(202002AD080002);云南省基础研究项目(202001BB050052)收稿时间:2021-10-01;修改时间:2021-12-22;采用时间:2022-02-26;jos 在线出版时间:2023-04-04CNKI 网络首发时间:2023-04-06软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(10):48044820doi:10.13328/ki.jos.006670http:/中国科学院软件研究所版权所有.Tel:[phone]probabilistic dependencies.Then,the method for probabilistic inferences to measure the joint probability by using the distance betweenembedding vectors is proposed.Experimental results show that the proposed method outperforms other state-of-the-art methods inefficiency,achievingaccurateresultsofprobabilisticinferences.Key words:Bayesiannetwork(BN);efficientprobabilisticinference;graphembedding;autoencoder;attentionmechanism贝叶斯网(Bayesiannetwork,BN)作为一种典型的用于不确定性知识表示和推理的概率图模型,广泛用于医疗诊断1、社交网络2和知识图谱3,4等领域.BN 由有向无环图(directedacyclicgraph,DAG)和条件概率表(conditionalprobabilitytable,CPT)组成,每个节点表示一个随机变量,每一条有向边代表两个节点之间的概率依赖关系,其依赖程度由 CPT 中的概率参数值来描述.基于 BN 的分析诊断和决策支持应用,以 BN 的概率推理为基本计算任务,即针对给定证据计算查询变量取值的条件概率.例如,基于图 1 中用于肺病诊断的 BN,针对患者存在“呼吸困难(dyspnea,D)”症状来推测其患“肺癌(lungcancer,L)”的概率,这一任务可转换为针对证据 D=T(即dyspnea 值为真)计算查询变量 lungcancer 为真(T)的概率,即 P(L=T|D=T).从实际应用的角度,图 1 所示 BN 反映了一段时期内肺病诊断中相关变量之间存在的依赖关系,基于该 BN 的诊断分析和决策支持,实质上是基于该BN 进行多次概率推理.考虑以下两个肺病诊断任务,在患者“X 射线”检查结果存在异常(即 X=T)的条件下患者“抽烟”的可能性,以及 X=T 且患者存在“呼吸困难”症状(即 D=T)的条件下“抽烟”的可能性,可将其转换为计算P(S=T|X=T)和 P(S=T|X=T,D=T)的概率推理任务,其计算过程涉及的中间结果为 P(S=T,X=T,D=T),不难看出,两次概率推理任务重复计算 P(S=T,X=T,D=T),而 P(S=T,X=T,D=T)的计算又涉及联合概率 P(S=T,X=T,D=T,L,B)的计算.因此多次概率推理中 BN 变量个数越多且变量的可能取值(即变量的势)越多时,重复计算的中间结果也就越多,对概率推理效率的影响越显著.因此,如何避免多次概率推理中的重复计算、高效地实现诊断分析,是基于 BN 的智能系统真正走向实用的重要保证,也是本文拟研究解决的问题.SmokerLung cancerBronchitisSLBXDSTFP(S)0.30.7STTBTFP(B|S)0.20.8FFTF0.40.6ST.LT.P(L|S)0.2.LT.XT.P(X|L)0.9.TFDTT.P(D|L,B)0.980.15.XrayDyspneaL图1肺病诊断贝叶斯网BN 概率推理主要分为精确推理和近似推理两类,以变量消元法(variableelimination)为代表的精确推理算法和以吉布斯采样(Gibbssampling)为代表的近似推理算法.这两类 BN 概率推理方法的时间复杂度都随 BN 中节点数呈指数增长,且均被证明为 NP 难问题5,6.如前所述,基于同一 BN 的多次概率推理过程中存在大量重复的计算结果.这意味着概率推理次数越多,时间复杂度越高;重复计算的中间结果越多,效率就越低.因此,为了高效地实现基于同一 BN 的多次概率推理,本文旨在研究中间结果易于重用和关键步骤易于计算的 BN 概率推理方法.图嵌入(graphembedding,GE)7,8作为经典的图表示学习方法,广泛应用于图节点分类、聚类和链接预测等图分析任务中.GE 旨在保存图结构和属性的条件下,将图中的节点或边表示为低维向量913,其高效性和易于计算性在许多图分析任务中都得到了验证13.针对 BN 多次概率推理效率低、中间结果重复计算等问题,本文借鉴GE 的思想,将 BN 表示为一组低维嵌入向量,通过使用嵌入向量保存节点间的概率依赖关系,将概率推理转换为向量之间的计算,以此提高 BN 多次概率推理的效率.BN 中 DAG 和 CPT 分别从定性和定量的角度反映了节点间的概率依赖关系,子节点依赖于父节点的概率由条件概率参数表示,不同的节点取值对应 CPT 中不同的条件概率参数;此外,相邻节点中父节点也可能依赖于其子节点,不直接相邻的两个节点之间也可能存在概率依赖关系.然而,现有的 GE 模型不能完整地表示 BN 中的概率依赖关系,而目前研究人员提出的基于矩阵分解的 BN 嵌入及其概率推理方法14,其嵌入过程中仍未考虑不相杜斯等:基于自编码器的贝叶斯网嵌入及概率推理4805邻节点之间的概率依赖关系,且多次概率推理效率受限于概率推理次数.为了有效表示 BN 中节点不同取值对应的不同条件概率参数值,本文基于 BN 构建带权有向图,使用图中的节点表示 BN 中节点的不同取值状态,基于点互信息(pointwisemutualinformation,PMI)15将相邻节点之间的概率依赖关系转化为边上的权重.为了高效地构建带权有向图、且尽可能地保存 DAG 和 CPT 的信息,本文以各节点条件概率作为节点取值的采样概率,提出基于最大似然估计(maximumlikelihoodestimation)的 BN 采样方法,并近似计算 PMI 值,从而得到图中各边上的权重.基于自编码器的 GE 方法,利用多个堆叠的非线性层来获取节点之间的复杂关系13.针对 BN 中相邻节点间的双向概率依赖关系,基于上述带权有向图中的带权邻接矩阵(PMI 矩阵),本文借鉴基于自编码器的 GE 思想来生成 BN 节点的嵌入.为了进一步保存 BN 中不相邻节点之间的概率依赖关系,本文提出结合注意力机制16的BN 嵌入方法.其中,每个编码层都利用节点与其邻居节点的注意力系数,根据邻居节点来生成新的节点表示.由于 PMI 矩阵有效描述了 BN 中节点间的相关性,本文直接使用 PMI 矩阵中的值作为相邻节点的注意力系数.为了保存 BN 中概率依赖关系的方向性,分别使用父节点的向量表示和子节点的向量表示来生成新的节点向量表示.每个编码层均传递节点及其相邻节点的概率信息,经过堆叠的编码层,在各节点的向量表示中均保存了该节点与其他不同节点之间的概率依赖关系.进一步,基于 BN 的嵌入向量,本文提出使用欧式距离来衡量节点之间相似性的方法,从而得到节点之间的联合概率,然后根据贝叶斯公式计算得到条件概率.BN 嵌入实现了使用一组低维向量来表示高维的概率图模型的方法,使得基于 BN 的概率计算更易于实现,BN 节点的嵌入向量可重复用于多次概率推理计算,通过向量间距离的计算,可高效地实现基于 BN 的概率推理.本文第 1 节介绍 BN 概率推理及图嵌入相关工作.第 2 节给出自编码器和注意力机制的 BN 嵌入方法.第 3节给出基于嵌入向量的 BN 概率推理方法.第 4 节给出实验结果及性能分析.第 5 节总结全文并展望未来的工作.1 相关工作 1.1 BN 概率推理传统的 BN 概率推理,主要包括精确推理和近似推理两类算法.变量消元法和团树传播(clique-treepropagation)是经典的精确推理算法,变量消元法通过不断分解联合概率来消去非证据变量和非查询变量,从而得到推理结果,而团树传播通过概率的局部传播实现概率推理,这两种算法均需要花费指数级计算时间5,因此不适用于实际中规模较大 BN 之上的多次概率推理.对此,人们提出以吉布斯采样和前向采样(forwardsampling)为代表的近似推理算法,其根据 BN 中的先验分布来生成样本,通过对合格样本计数来得到近似概率推理结果6.近似推理算法在一定程度上解决了大规模 BN 的推理问题,但是这两种算法的有效性与样本的数量成正比、效率与样本数量成反比,多次概率推理涉及 CPT 上的重复查询和计算,且不同概率推理的中间结果不能重用.为了提高多次概率推理的效率,文献 14 提出基于矩阵分解的 BN 嵌入及其概率推理方法,但其效率优势受限于概率推理的次数.1.2 图嵌入GE 作为经典的图表示学习方法,旨在保留图结构或属性的条件下将图中的每个节点或边映射为低维向量,以便用于后续图分析任务.基于矩阵分解的 GE 方法根据节点对之间的相似性来保持图的性质.基于随机游走的方法主要通过随机游走获得训练样本,利用 Skip-Gram 模型将每个节点映射到低维空间,早期主要以基于 DeepWalk17和 Node2vec18方法为代表;在此基础上,dynnode2vec19通过 Node2vec 初始化快照,对动态变化的节点执行随机游走,从而更新动态变化信息;tNodeEmbed20以类似句子嵌入的方式实现节点嵌入,获取节点角色和边的动态变化.为了获取高度非线性图结构,研究人员提出基于深度学习的 GE 方法,例如,SDNE13利用深度堆叠自编码器来保持网络的一阶和二阶相似性,通过非线性函数获得最终嵌入向量;DNGR21使用堆叠去噪自编码器来获得图结构信息和嵌入向量;GALA22采用完全对称的图卷积自编码器模型生成图的低维嵌入表示,编码器和解码器分别使用拉普拉斯平滑和拉普拉斯锐化,使得生成的嵌入向量能够同时保存图的结构信息和节点特征;DySAT23通过4806软件学报2023 年第 34 卷第 10 期邻域结构和时间两个维度的联合自注意力来计算节点嵌入;GraphAIR24通过领域聚合模块通过组合邻域特征来构建节点特征表示,各邻域交互模块通过乘法运算来显示建模邻域信息的交互,使得生成的节点嵌入向量能保留属性信息.而目前考虑节点属性信息的 GE 方法中涉及的节点属性大多是文本属性、所属类别和节点标签等.因此直接使用基于自编码器的 GE 方法不能保存 BN 的 CPT.2 基于自编码器的贝叶斯网嵌入 2.1 PMI 矩阵的构建B=(G,)G=(V,E)Xi=Xikimiki=1miXikiXiW(Xiki,Xjkj)=PMI(Xiki,Xjkj)(Xiki,Xjkj)W(Xiki,Xjkj),W(Xjkj,Xiki)XikiXjkjW(Xiki,Xjkj)给定一个 BN,其中表示 BN 的 DAG 结构,表示 BN 中参数的集合,V 中每一个节点均有,表示节点的势,表示节点的取值.BN 中节点不同取值对应不同的条件概率参数,每个条件概率参数表示在其父节点的当前取值下该节点当前取值的概率.为了同时保留 BN 中节点取值及其条件概率参数,本文将 BN 转换为带权有向图,其中节点表示 BN 中取不同值的节点,边的权重由 BN 的 CPT 转换而来.由于 PMI 值衡量了两个随机变量之间的相关性,因此将 BN 中节点对的 PMI 值作为边的权重.具体而言,用 PMI 值来表示有向边的权重,考虑到带权有向图的方向性,有,节点到节点的有向边的权重的计算方法如下:W(Xiki,Xjkj)=PMI(Xiki,Xjkj)=logP(Xiki,Xjkj)P(Xiki)P(Xjkj)(1)P(Xiki,Xjkj)(Xiki,Xjkj)#(Xiki,Xjkj)W(Xiki,Xjkj)其中,表示节点对中两节点同时出现的概率,用来表示,因此的计算公式可转换为:W(Xiki,Xjkj)=PMI(Xiki,Xjkj)=logP(Xiki,Xjkj)P(Xiki)P(Xjkj)=log#(Xiki,Xjkj)#(Xiki)#(Xjkj)(2)Xip=P(Xi=0)p=P(Xi=0|(Xi)=j)(Xi)=jXi(Xi)r 0,1r 0,pki=0r (p,1ki=1Xi为了将 BN 中节点间的 CPT 转换为 PMI 值,本文将 BN 中节点 CPT 中的条件概率参数作为节点采样概率,提出基于最大似然估计的 BN 采样方法.首先,使用 BN 节点的拓扑排序作为节点采样顺序,针对待采样的节点,假设节点的势为 2,记或,表示节点的父节点集合的取值组合数为 j,根据 p 值生成随机数,若,则采样节点的取值为,若则采样节点的取值为,当节点的势大于 2 时以此类推.为了保证采样样本能尽可能地包含 BN 中的全部信息,将基于最大似然估计得到的条件概率参数与原 CPT 中的各参数进行比较,若两者较为接近,则说明采样样本足以描述原 BN 中的信息,从而确定采样算法的生成样本数 ns.最大似然估计计算公式如下:ijki=#(Xijki)#(Xij)(3)#(Xij)(Xi)=j#(Xijkj)Xi=kj(Xi)=j其中,表示满足的样本数,表示满足和的样本数.#(Xiki,Xjkj)#(Xiki)#(Xjkj)#(Xiki,Xjkj)Xi=kiXj=kj#(Xiki)#(Xjkj)Xi=kiXj=kj基于采样得到的样本可计算、和,其中,表示同时满足和的样本数,和分别表示满足和的样本数.带权有向图中有向边和权重保存了 BN 的 DAG和 CPT,因此使用带权邻接矩阵 W(PMI 矩阵)来表示图的初始向量.值得注意的是,在构建 PMI 矩阵过程中,将不存在有向边相连的节点对的 PMI 值设置为 0,而存在有向边的节点对 PMI 值根据公式(2)来计算.2.2 基于自编码器的 BN 节点嵌入基于构建的带权有向图及生成的 PMI 矩阵,本节引入注意力机制,给出基于自编码器的 BN 嵌入方法(auto-encoderbasedBayesiannetworkembedding,ANE),如图 2 所示,包括自编码器输入、编码和解码 3 个阶段.(1)输入Xikix(0)iki=Wiki,WTikiPMI 矩阵中的行向量表示每个节点作为父节点时与其子节点间的相关信息,列向量表示每个节点作为子节点时与其父节点间的相关信息.为了同时保留节点作为父节点和节点作为子节点与其他节点的相关性,将 PMI 矩阵及其转置拼接在一起作为自编码器的输入.具体针对节点来说,输入自编码器的向量为.杜斯等:基于自编码器的贝叶斯网嵌入及概率推理4807合并(0)xck0(0)xjk0(1)xjk0(1)xiki(0)xikiWiki(0)xjk1(0)xjk1(0)xck0公式(6)公式(6)(0)xck1(0)xck1(1)xjk0(0)xjk1(out)xiki(0)xiki(in)xikixiki公式(8)公式(8)(0)xck0(0)xck1(M)xck0(M)xck1DecoderEncoder(M)xjk0(M)xjk1yiki=xiki(M)xiki(1)TWiki图2基于自编码器的 BN 嵌入模型(2)编码XikiXjkjekikjij=W(Xiki,Xjkj)为了在编码阶段保存相邻节点间的双向概率依赖关系和不相邻节点间的概率依赖关系,本文扩展了传统的注意力机制,直接使用 PMI 矩阵中的值作为注意力机制中节点与其相邻节点的注意力系数.由于 BN 中的相邻节点包括父节点和子节点,且节点之间存在方向性,因此分别利用子节点和父节点的向量表示来共同生成该节点的向量表示.BN 中节点与其子节点的相关表示为,为了使该节点在其多个子节点中的相关系数可比,使用 Softmax 函数对节点与所有子节点的相关系数做正则化处理:kikjij=Softmaxj(ekikjij)=exp(ekikjij)lNi(out)exp(ekiklli)(4)Ni(out)XikiXiki其中,表示以节点为父节点时所包含的子节点及节点本身构成的集合.ekckici=WT(Xiki,Xckc)XikiXckc类似地,表示节点与其父节点的相关性,对其父节点的相关系数做正则化处理:kckici=Softmaxc(ekckici)=exp(ekckici)lNi(in)exp(eklkili)(5)Ni(in)XikiXiki其中,表示以节点为子节点时所包含的父节点及节点本身构成的集合.Xikix(0)ikiXiki节点输入自编码器的初始向量为,第 m 层编码层通过整合父节点和子节点信息,得到节点的第 m层输出:x(m)iki=jNi(out)(m)ij(W(m)px(m1)iki)+cNi(in)(m)ci(W(m)cx(m1)iki)(6)m 1,2,.,MW(m)pW(m)c()Xikiyiki=x(M)iki其中,和分别为第 m 层编码层的参数,表示激活函数.经过 M 层编码层的编码,得到节点的嵌入向量表示,即.2g(g=ni=1mXi)d(d g)OikiXikiOiki=nl=1W(Xiki,Xlkl)IjkjXjkjIjkj=nl=1W(Xlkl,Xjkj)XikiXjkjXikiXjkj(Oiki+1)(Ijkj+1)XikiXjkjPMI 矩阵的维度为 BN 中各节点势的总和,因此自编码器输入维度为 PMI 矩阵维度的两倍,表示为,得到节点嵌入矩阵维度为.带权有向图中 PMI 值越大的相邻节点,表示节点间的相关性越大,使用表示节点作为父节点与其子节点边的权重之和,即,表示节点作为子节点时与其所有父节点边的权重之和,即.相邻节点和中,若父节点与子节点边的权重越大且子节点与其父节点边的权重越大,则说明这两节点间存在概率依赖关系程度越强,两个节点也就越相似.因此本文使用来近似表示父节点和子节点之间的相似指标,使用嵌入向量内积近似表示嵌入向量相似性,为了保证相邻节点嵌入向量的相似性,使用 Sigmoid 函数对两相似性数值进行规范化,通过对数函数来最小化损失,定义如下:L1st=ni=1jNi(out)logSigmoid(yTikiyjkj)Sigmoid(Oiki+1)(Ijkj+1)(7)4808软件学报2023 年第 34 卷第 10 期yikiyjkjXikiXjkj其中,和分别表示节点和节点的嵌入向量.(3)解码 x(M)iki=x(M)ikiXiki为了在解码阶段生成有效的节点嵌入,使用层数与编码器相同的解码器重构嵌入向量,编码器的输出即为解码器的输入,即,每个解码层都尝试重构相对应的编码层,即每个解码层分别利用子节点和父节点的表示,根据节点与其父节点和子节点间的相关性来重构节点表示.针对节点,第 m1 层解码器重构了第 m 层的节点表示,其输出为:x(m1)iki=jNi(out)kikjij(W(m1)p x(m)iki)+cNi(in)kckici(W(m1)p x(m)iki)(8)m 1,2,.,MW(m1)pW(m1)c其中,和为第 m1 层解码层的参数.x(0)iki x(0)iki x(in)iki x(out)iki xiki=x(in)iki x(out)iki经过 M 层解码器后得到输出.为了加快自编码器的训练速度、更好地提取 BN 方向性,本文改进了解码器的解码网络结构,将解码向量分别经过两个规模完全相同的全连接网络,得到节点作为子节点的解码向量表示和节点作为父节点的解码向量表示,使用向量积作为最终的解码向量.自编码器的目标是最小化编码输入和解码输出的重构损失,损失函数如下:L2nd=ni=1 xikixiki22(9)PMI 矩阵具有稀疏性,输入矩阵 X 中的非零元素数量远远小于零元素的数量,导致在训练过程中更容易重构X 中零元素,因此,对非零元素的重构误差施加比零元素更大的惩罚,修改后的目标函数如下:L2nd=ni=1(xikixiki)bi22=?(XX)B?22(10)bi=bi,jnj=1Xi,j=0bi,j=0Xi,j 0bi,j=1其中,表示哈达马积,若,则;若,则.为了在嵌入向量中保存 BN 中相邻节点相似性,同时最小化自编码器中的重构损失,结合公式(7)和公式(10),得到的最终的损失函数为:L=L2nd+L1st(11)其中,为控制自定义损失函数的参数,取值为 1.2.3 基于自编码器的 BN 嵌入基于自编码器的 BN 嵌入方法主要包括采样样本、生成 PMI 矩阵和基于自编码器生成嵌入向量 3 个部分,具体实现见算法 1.算法 1.基于自编码器的 BN 嵌入.B=(G,)ns输入:,BN;P,训练迭代次数;M,编码器层数;,生成样本数;D,基于最大似然估计的 BN 采样得到的样本集合;X输出:Y,嵌入向量矩阵;,重构矩阵.Wp=W(1)p,.,W(M)p,W(M)p,.,W(1)pWc=W(1)c,.,W(M)c,W(M)c,.,W(1)cWf1.初始化参数、和2.根据 D 和公式(2)计算 PMI 矩阵中的值,构建 PMI 矩阵 WX(0)W,WT3.输入矩阵:4.FOR epoch=1TO PDO5.FOR m=1TO MDOijC(p)6.根据公式(4)计算每个节点的,构成矩阵ciC(c)7.根据公式(5)计算每个节点的,构成矩阵X(m)(W(m)pX(m1)C(p)+(W(m)cX(m1)C(c)8.9.END FORX(M)X(M)10./解码器的第 M 层输入杜斯等:基于自编码器的贝叶斯网嵌入及概率推理480911.FOR m=MDOWNTO1DOX(m1)(W(m)pX(m)C(p)+(W(m)cX(m)C(c)12.13.END FORX(0)WfX(in)X(out)14.通过自定义解码器结构结合该层参数分别得到和X X(in)X(out)15.LWpLWcLWf16.根据公式(11),使用、和进行反向传播,更新编码器和解码器的参数17.END FORY X(M)18.X19.RETURNY,O(nsn)O(nsn)O(nslogns)g(g=ni=1mXi)ggO(g2)O(n2)O(n2d)O(n2)nsO(nsn)O(nsn)算法 1 的第 1 行生成样本的时间复杂度为,空间复杂度为;第 2 行中 PMI 矩阵的构造时间复杂度为,若 BN 中每个节点的势的总和为,则 PMI 矩阵的大小为,PMI 矩阵构造的空间复杂度就为;基于自编码器的 BN 嵌入,首先对 PMI 矩阵的相关系数进行归一化,时间复杂度为,自编码层生成节点向量的时间复杂度为,空间复杂度为.由于采样样本的数量远大于 n、g 和 d,因此,算法 1 的时间复杂度为,空间复杂度为.3 基于嵌入向量的概率推理通过 BN 嵌入,使得节点间的概率依赖关系被保存在嵌入向量中,这种概率依赖关系越大,相应的 PMI 值就越大,两个节点的嵌入向量就越接近,意味着相关嵌入向量的空间距离就越短.而空间距离越短,说明两个节点所对应变量同时出现的概率越大,则这两个节点的联合概率可近似表示为它们同时出现的概率,因此,我们使用嵌入向量之间的归一化欧式距离来近似表示节点对的联合概率.(Xiki,Xjkj)首先,节点对嵌入向量之间的欧式距离定义如下:D(yiki,yjkj)=vtdl=1(ylikiyljkj)2(12)进而将以上欧式距离归一化到 0,1,有效表示 BN 节点对之间的联合概率:P(Xiki,Xjkj)sim(yiki,yjkj)=11+D(yiki,yjkj)(13)nEXEkE=XekenEe=1y=yekenEe=1XqkqyqkqmqP(Xqkq|XEkE)P(Xqkq|XEkE)=P(Xqkq,XEkE)P(XEkE)P(Xqkq,Xeke)假设概率推理中证据变量个数为,对应的证据变量及其取值集合为,则证据变量对应的嵌入向量集合为,查询变量为,取值为,对应的嵌入向量为,表示查询变量的势.BN 的概率推理就是在给定证据变量的情况下计算查询变量的概率.由于,根据公式(13)计算联合概率,则使用如下方法实现概率推理:P(Xqkq|XEkE)=P(Xqkq,XEkE)P(XEkE)=nEe=1P(Xqkq,Xeke)mqkq=1nEe=1P(Xqkq,Xeke)=nEe=1sim(yqkq,yeke)mqkq=1nEe=1sim(yqkq,yeke)(14)综上,基于嵌入向量的概率推理(autoencoderbasedBayesiannetworkembeddingandprobabilisticinference,ANEI)思想见算法 2.算法 2.基于嵌入向量的概率推理.B=(G,)XEkE=XekenEe=1XqkqXqkq输入:,BN;,证据变量集合及其取值;,查询变量及其取值;Y,BN 中节点嵌入向量矩阵;P(Xqkq|XEkE)输出:条件概率.4810软件学报2023 年第 34 卷第 10 期mq|Xq|Xqmq1./得到查询变量的势yekenEe=1yqkq2.从嵌入向量矩阵 Y 得到证据变量嵌入向量集合及查询变量的嵌入向量P(Xqkq,XEkE)nEe=111+D(yeke,yqkq)3./根据公式(13)计算证据变量和查询变量的联合概率P(XEkE)mqq=1P(Xqkq,XEkE)4./计算证据变量的边缘分布P(Xqkq|XEkE)P(Xqkq,XEkE)P(XEkE)5.P(Xqkq|XEkE)6.RETURNO(nEmq)nEmqO(n2)算法 2 的时间复杂度是,其中和的大小远远小于 n,因此算法 2 的时间复杂度远远小于.4 实验结果本节使用 5 个不同领域的真实 BN 数据集,测试基于自编码器的 BN 嵌入方法(ANE)和基于嵌入向量的概率推理方法(ANEI)的效率和有效性.4.1 实验数据集选取用于癌症诊断的 CANCERBN(小型网络)、警报监控系统的 ALARMBN(中型网络)、肝病诊断的HEPAR2BN(大型网络)、在线指导学生问题解决的 ANDESBN(超大型网络)和大型谱系中链接分析的 LINKBN(超大型网络)这 5 个 BN 数据集,其统计信息如表 1 所示.表1BN 数据集的统计信息BN数据集节点数边数参数个数CANCER5410ALARM3746509HEPAR2701231453ANDES2203381157LINK724112514211 4.2 对比算法、实验参数及实验指标4.2.1对比算法使用经典的 BN 精确推理方法 VE 和近似推理方法 GS、BNERS 与 ANEI 进行比较.(1)变量消元法(VE):VE 是一种精确推理的概率推理算法,通过搜索最优的消元顺序逐一进行变量消去,最终得到概率推理结果25.本文将基于 VE 的 BN 概率推理结果作为标准结果.(2)吉布斯采样(GS):GS 作为近似推理的一种经典算法,给定证据变量取值条件下,根据 BN 中的先验分布采样足够多的样本,通过统计样本的数量来计算概率推理结果,采样过程中对采样节点及其马尔可夫覆盖中节点的 CPT进行重复比较和查询,拥有指数级别的时间复杂度26.(3)基于 BN 嵌入的推理(BNERS):基于矩阵分解生成 BN 的节点嵌入向量,保存了 BN 的 DAG 和 CPT,根据节点嵌入向量之间的相似性来生成对应的样本,统计样本计算得到近似概率推理结果14.4.2.2评估指标将规模不同 BN 下的 ANE 执行时间作为 ANE 效率的评估指标;为了测试 ANE 的有效性,比较 ANE 的重构损失函数值与基于矩阵分解的 BN 嵌入的损失函数值,从而验证 ANE 的有效性.为了测试 ANEI 的效率,比较 ANEI 与 VE、GS、BNERS 的多次概率推理的执行时间;为了测试 ANEI 的有效性,使用平均绝对误差(meanabsoluteerror,MAE)、近似度、精度、召回率和 F1 分数来作为评估指标.(1)平均绝对误差(MAE):用来衡量 ANEI、GS 和 BNERS 概率推理结果和标准结果(VE)间的误差.杜斯等:基于自编码器的贝叶斯网嵌入及概率推理4811tANEItGStANEItGS0,+(2)近似度:用来度量 ANEI 比 GS 概率推理结果更接近于标准推理结果的比例.表示 ANEI 推理结果比GS 更接近于标准结果的次数,表示 GS 推理结果比 ANEI 更接近于标准结果的次数,基于实现近似计算.近似度的取值范围为,其值为 1 时表示 ANEI 的性能和 GS 相同,其值大于 1 时表示 ANEI 性能优于 GS,其值小于 1 时表示 ANEI 性能低于 GS.(3)精度(Precision)、召回率(Recall)和 F1 分数(F1-score):精度是计算预测为正样本中实际为正样本的概率,召回率是计算预测实际为正样本中预测为正样本的概率,F1 分数是精度和召回率综合考虑两者的一个度量指标,预测为真的正样本(truepositive,TP)表示 ANEI 推理结果与标准值均为正向偏向的推理结果数量,预测为负的正样本(falsenegative,FN)表示推理结果为负向偏向而标准值为正向偏向的概率推理结果数量,预测为正的负样本(falsepositive,FP)表示推理结果为正向偏向而标准值为负向偏向的概率推理结果数量.4.2.3参数设置本文使用 Python3.7 实现所有算法.通过实验测试将训练迭代次数 epoch 设置为 200,初始学习率设置为 0.01,嵌入向量维度 d 均设置为 10,CANCERBN 和 ALARMBN中自编码器层数设置为 2;HEPAR2BN 和 ANDESBN中自编码器层数设置为 4;LINKBN 中自编码器层数设置为 4.4.3 实验结果4.3.1效率为了测试概率推理的效率,对比 VE、GS、BNERS 和 ANEI 在不同 BN 中多次概率推理的执行时间,以此评估多次概率推理的效率以及 BN 规模对 ANEI 效率的影响;通过改变 BN 大小、迭代次数 epoch、嵌入向量维度 d、自编码器层数、损失函数以及是否改变自编码器结构作为主要参数,记录 ANE 的执行时间,以此测试 ANE 的效率.(1)推理次数对概率推理效率的影响为了测试基于 ANEI 的多次概率推理效率,通过改变推理次数 t 来比较执行时间,从图 3(a)(e)可以看出:当在同一个 B