贝叶斯网络中基于联合树算法的学生模型更新方法研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇贝叶斯网络中基于联合树算法的学生模型更新方法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:在已建立的覆盖型贝叶斯网络学生模型的基础上,用联合树算法来实现推理更新.通过建立Moral图、构造三角化图、区分团节点,然后将学生模型转化为联合树的结构,最后通过消息传递来完成整个学生模型的更新.

关键词:贝叶斯网络；学生模型；联合树算法

中图分类号:TP301

文献标识码:A文章编号:1672-8513(2010)01-0063-04

Bayesian Network Research Based on a Joint Tree

Algorithm for Updating the Student Model

CHEN Lihua

（Information School, Yunnan University of Finance and Economics, Kunming 650221, China)

Abstract:

Based on the coverage-typed Bayesian-network student model, the joint tree algorithm is used to achieve reasoning update. Through the establishment of Moral map and the triangular structure of map nodes to distinguish between corporations, this research turns the student model into the Joint Tree Algorithm for updating the student model through information transmission.

Key words:

Bayesian network; student model; joint tree algorithm

贝叶斯网络的推理是贝叶斯网络研究的重要内容,研究人员提出了多种精确和近似推理算法,比如多树传播算法［1］、团树传播算法［2］、图约简算法［3］等,而联合树（Junction Tree）算法是目前计算速度最快,应用最广的贝叶斯网络精确推理算法.该算法最初是由Lauritzen 和Spiegelhalter于1988年提出的,此后Jensen（1990）和Dawid（1992）又对其进行了改进.联合树算法以其容易理解,计算推理结果精确、高效的特点,得到广泛应用,许多有关贝叶斯网络研究和应用的软件都将其作为默认的推理算法.

1 学生模型更新方法概述

在覆盖型知识表示的框架上,通过加入先验关系,确定图中的合理方向,确定条件概率的值,确定节点间的因果关系,经过一系列操作将之转换为一个贝叶斯网络的结构.学生在进行学习的时候,系统会不断地收集反馈信息,此时,我们需要根据这些信息来更新学生模型.如图1所示是设计好有关《Delphi程序设计》这门课程部分知识项的覆盖型贝叶斯网络学生模型的一部分［4-5］.图中的节点是知识项节点,由该门课程的专家给出了各个知识项的先验概率.下面通过它来解释学生模型更新的具体算法步骤.图1中A表示学生对特定知识项已完全熟练掌握；B表示学生对知识项基本掌握,但是仍有一些问题；C表示学生处在初级阶段,有许多问题；D表示学生对该知识项完全不了解.

对于用贝叶斯建立的覆盖型学生模型,首先将其转化为树状的二级结构,称之为联合树；然后用知识项节点间条件概率将这棵联合树初始化.此时就可以在该联合树上利用消息传递算法对学生模型更新.图2是学生模型更新的一个流程图.

2 学生模型转换为联合树结构

我们将首先给出联合树的概念,然后讨论如何将学生模型转换成易于消息传递的联合树结构.

2.1 联合树定义

联合树是一个无向树,树中的每一个节点称为团,由原贝叶斯网络中的一组随机变量构成,是无向图中最大的全连通子图.连接2个相邻团节点的称为分隔节点,假设分隔节点S将2个相邻的团节点Ci和Cj相连,则S中的随机变量是团节点Ci和Cj中包含的随机变量集合的交集：S =Ci ∩Cj.将贝叶斯网络转化为联合树后,必须将贝叶斯网络中的条件概率表(CPT)转换到联合树中,即：为联合树的所有节点指定参数.联合树中的每个节点C(包括团节点和分隔节点)对应的参数称为该节点的分布函数,它将团节点中随机变量的每一种取值组合映像为一个大于等于0的数,用ΦC表示,且满足：

P(U)=∏C∈ClusterΦC∏S∈SeperaterΦS,

P(U)是贝叶斯网络表示的联合概率分布.

联合树算法采用了消息传递的思想,在推理过程中,消息会依次传遍联合树的每个节点.若联合树中由分隔节点S相连的任意2个相邻团结点Ci和Cj满足:

∑Ci\ SφCi=φS=∑Cj\ SφCj,

则称该联合树满足全局一致性.通过节点间的消息传递可以使联合树满足全局一致性.

当联合树满足全局一致性后,系统达到稳态,可以计算原贝叶斯网络中任意随机变量V的概率分布.利用任意一个包含变量V的团节点C的分布函数ΦC,通过P(V)=∑C＼{V}ΦC,可计算出变量V的概率分布.若求P (V/E),则利用条件概率公式:

P(V=v|E=e)=P(V=v|E=e)P(E=e) ,

和相应团节点分布函数,即可求出结果.构造联合树的过程如图3.

2.2 转换为联合树的步骤

我们把覆盖型贝叶斯网络学生模型的一部分作为实例(图4),应用以下一系列的图形转换算法［6-8］得到一棵联合树.整个步骤如下:

1） 构造Moral图（GM）：从图4建立一个无向图,称之为Moral图；

2） 三角化图（GT）：在Moral图中加入弧,使之变成三角化图；

3） 区分团节点：从三角化图中,确定并选择节点子集,每个团节点都是无向图的子图；

4） 建立联合树（JT）:建立的联合树必须包含所有团节点,交集作为连接2个团节点的分隔节点.

下面依次解释各个步骤的细节问题.

1) 建立Moral图

用G表示图4,对应的Moral图GM建立过程如下:

(1） 复制图G,同时去掉边的方向,建立无向图G′；

(2） 在G′中,对每个节点xi确定它在G中的父节点集pa(xi),给pa(xi)中每对节点增加无向边.得到图5.

2) 三角化Moral图

一个无向图被三角化,条件是对包含4个及以上个节点数的环,增加1条无向边将环中2个非相邻节点连接起来,建立过程如下:

(1)复制在上一步骤中所得到的Moral图GM,记为GM ′；

(2)在GM′中存在节点时:

a.从GM′中选取一个节点x,x使在b中引起加入最少边；

b.节点x和x在GM′中的邻节点组成一个聚类(非空集合),连接聚类中的所有节点,对于加到GM′上的所有边也对应加到GM上；

c.从GM′中删除x.

注:一个节点x的权重是x的数字值；一个聚类的权重是它的组成节点的权重的乘积.

图6经过三角化算法后得到的结构与图5一样.

3) 区分团节点

在无向图G中的团节点是G的子图,它满足即是完全的又是最大的特性.所谓完全的表明每对不同的节点之间都有边相连；最大的表明团节点不能完全包括在一个更大的完全子图中.确定团节点的算法是改造三角化过程得来的,基于以下2个事实:①从三角化的图中确定的每个团节点都是从步骤2）中b推出的聚类；②一个推导出的聚类不可能是随后推导出来的聚类的子集.为简化表示,将图3中的知识项节点用字母表示.A:循环结构；B:While循环；C:For循环；D:关系运算符；E:变量.图6中包含3个团节点ABC、BCE、BD.

4) 建立最佳联合树

(1) 2个概念

聚类(Cluster)：是无向图中顶点的1个简单子集.

分离集(Sepset)：给定3个聚类A, B, C；定义C分离聚类A与B,当且仅当图中的所有从A中的节点到B中的节点的路径都经过聚类C中的节点,则C被称为分离集(Sepset,或Shorter Sepset).

(2) 联合树的建立

为了建立最佳联合树,必须把团节点连起来,这样构成的团节点树满足联合树的特性和最优性标准,最优性标准有助于缩短联合树最小化推理的计算时间.下面将对最优性标准进行定义.

给定一个n个团节点的集合,可以按以下方法组成团节点树,反复在各个团节点间插入边,直到这些团节点被n-1条边连接起来.也可以在每对团节点之间反复插入分离集,直到团节点之间被n-1各分离集连接.我们在确定建立最优联合树时使用后一种方法.算法分为2部分:

首先,通过反复选择和插入候选分离集的方法形成最优联合树；然后选择分离集.

建立最佳联合树算法描述如下:

①开始有n棵树的集合,每棵树只包含1个团节点和1个空集S；

②对于每个单独的团节点对Ci和Cj:

a.建立一个候选分离集Ci∩Cj,记为Sij；

b.把Sij插入S；

③重复下面的步骤,直到n-1个分离集入到森林中；

a.根据选择合适的分离集定义的标准,从S中选择一个分离集Sij,将其删除；

b.当Ci和Cj是在森林中不同的树上时,在团节点Ci和Cj之间插入分离集Sij,其结果是使两棵树融合成更大一些的树.

注:选择合适的分离集的标准:

为了描述如何选择下一个候选分离集,我们先定义质量(weight)和代价(cost)如下:

在这些定义的基础上,我们可以得出如何选择合适的分离集.①为了使结果团节点能够满足联合树的特性,必须选择具有最大质量的候选分离集；②当2个或者更多质量相等的分离集可被选择时,可通过选择有最小代价的候选分离集来优化形成最终联合树的推理时间.图7是经过最佳联合树生成算法得到的联合树结构.这样,学生模型就从知识表示框架的形式转变为联合树的结构.这种联合树形式的学生模型虽然不能像知识表示框架那样体现出各个知识项之间的逻辑关系,但是更有利于学生模型的更新.当某门课程的学生模型建立起来后,根据上述步骤,一次性地将其转换为联合树结构,当学生模型在正常工作时就以这种联合树的形式进行消息的传递、参数性能估计等任务.

通过以上的算法,并在联合树中进行消息传递可以得到当某个学生学习“循环结构”知识项的掌握程度为A时,图1中各个知识项有如图8所示概率分布.

3 结语

本文针对建立的覆盖型贝叶斯网络的学生模型实例,参考贝叶斯网络的联合树传递算法,给出了学生模型的更新和参数估计的方法,即:首先将网络化的学生模型转换为一种易于消息传递的联合树结构；然后在这种结构下,简单地通过消息传递来完成整个学生模型的更新.通过该联合树更新算法,当某学生学习了某知识项的掌握程度即概率发生变化时,通过消息传递,可以推知其他各个知识项的掌握程度（即概率分布）［9］.

参考文献:

［1］PEARL J. Fusion, propagation,and structuring in belief networks［J］. Artificial Intelligence,1986,29(9):241-288.

［2］COPER G F. The computational complexity of probabilistic inference using bayesian belief Networks［J］.Artificial Intelligence,1990, 42(7):393-405.

［3］LAURITZEN S L,SPIEGELHALTER D J. Local computations with probabilities on graphical structures and their application to expert systems［J］. Joumal of the Royal Statistical Society(B),1988, 50(2):157-224.

［4］刘伟娜,霍利民,张立国.贝叶斯网络精确推理算法的研究［J］.网络与通信，2006,22(10):92-94.

［5］余东峰,孙兆林.基于贝叶斯网络不确定推理的研究［J］.微型电脑应用，2004,20(8):6-8.

［6］胡兆勇,屈梁生.一种贝叶斯诊断网络拓扑结构［J］.西安交通大学学报，2003,11(1):47-49.

［7］胡玉胜,涂序彦,崔晓瑜,等. 基于贝叶斯网络的不确定性知识的推理方法［J］.计算机集成制造系统-CIMS，2001,7(9):65-67.

［8］胡兆勇,屈梁生.贝叶斯网络推理的一种仿真算法［J］.系统仿真学报，2004,2(6):286-301.

［9］赵波,吴庆畅,高联雄,等.学生就业贝叶斯网模型的构建与推理［J］. 云南民族大学学报:自然科学版，2008,17(1):86-88.