贝叶斯网络学生模型中存在无向环的更新

贝叶斯网络学生模型中存在无向环的更新陈晶（琼州学院电子信息工程学院，海南三亚572022）摘要;本文采用贝叶斯网络的思想设计学生模型，由于建好的学生模型中存在无向环，使学生模型的推理成为一个N-P难题。在参考贝叶斯网络的更新算法的同时改进了算法，用联结树算法来实现对建好的学生模型的推理更新。关键词:学生模型；贝叶斯网络；更新；联结树中图分类号：TP391文献标识码：ABayesiannetworksofstudentmodelundirectingringsupdatesCHENJing(CollegeofElectronicsandinformationengineering,QiongZhouUniversity,SanyaHainan572022)Abstract:Thispapesays,BayesianNetworkscandesignastudentmodel,however，undirectedloopsareembeddedinthemodel,reasoningonthemodelisaNPhardquestioninfact。Tosolvethisproblem，arevisedclusteringalgorithmisenhancedbymeansofthejointtreeduringreasoningprocess。KeyWords：StudentModel；BayesianNetworks；Updating;；Junctiontree1引言适应性教学系统为提供适应性，做到因材施教，需要收集关于学生的信息，而存储关于学生信息的是学生模型，因此学生模型对开展适应性教学起着重要的作用。由于学生学习过程中存在大量的不确定性因素及信息，Villano首先建议应用贝叶斯网络[1]到教学系统中。2更新算法文中采用联结树算法：即从一个有向图的表示出发，将其转变为无向图，同时保持所有最初的依赖关系，该无向图称为道义图；然后它被弦化以形成局部节点聚类，这一结构是联结树型的。观测得到的证据通过保证聚类的交集的边缘概率一致来从一个聚类传到另一个聚类，而不用考虑哪个聚类是要计算的。最后，当传播过程稳定下来，变量的后验概率通过把所在聚类的概率分布投影到这个变量上来计算出来。收稿日期：2012-08-09作者简介：陈晶(1981年—)，女，汉族，黑龙江省巴彦县人。琼州学院电子信息工程学院讲师，研究方向：计算机辅助教育。3学生模型本文设计学生模型时采用覆盖模型，考虑自身系统学生模型的建立需求，采用了改进的覆盖式模型进行教学资源信息的构建，将一门课程划分为若干个知识项，给每个知识项附加4个权值(E，F，A，N)来表示学生对某个知识项的掌握情况：E表示学生对知识项完全熟练掌握；F表示学生对知识项基本掌握，但仍有一些问题；A表示学生处在初级阶段，有许多问题；N表示学生对该知识项完全不了解。每一等级对应一个条件概率值(值的加权和为l)，该值是基于对学生的观测值得到的对知识项的掌握程度。此模型重点考虑学生动态信息，较好的反应了相对复杂的学生学习过程，从而体现出系统的适应性教学的特点。学生模型的设计中运用贝叶斯网络进行了教学资源信息的展示和描述，对于学生所学内容的知识状态信息通过贝叶斯网络进行抽象化的表示，并可在学生动态学习过程中随着学习的进行，不断更新学生所学知识点的知识状态(抽象化表示)，在学生重新学习时予以记忆。4学生模型的更新在覆盖型知识表示的框架上，通过加入先验关系，确定图中的合理方向、条件概率的值、节点间的因果关系，经过一系列操作后转换为一个贝叶斯网络的结构。学生在进行学习的时候，系统会不断地收集反馈信息，此时，需要根据这些信息来更新学生模型。以《C++程序设计教程》[2]为例，为简化只选取了部分知识内容做来说明，整体结构可依次类推。按照课程的章节安排列出课程的知识结构，如图4-1所示，是设计好的覆盖型贝叶斯网络学生模型的一部分。图中的节点是知识项节点，由该门课程的专家给出了各个知识项的先验概率。下面通过它来解释有环时学生模型更新的具体算法步骤。结构化编程E:0.600F:0.200A:0.150N:0.050Switch语句E:0.448F:0.370A:0.141N:0.041For语句E:0.460F:0.320A:0.150N:0.070While语句E:0.579F:0.230A:0.100N:0.091Do-while语句E:0.531F:0.272A:0.097N:0.100条件表达式E:0.433F:0.382A:0.150N:0.045循环条件E:0.658F:0.160A:0.172N:0.010嵌套语句E:0.544F:0.304A:0.100N:0.052图4-1学生模型的先验概率分布对于用贝叶斯建立的覆盖型学生模型，根据文献[3]，首先将其转化为联结树，然后用知识项节点间条件概率将其初始化，在该联结树上利用消息传播算法对学生模型更新。4.1转换为联结树结构本文把覆盖型贝叶斯网络的学生模型的一部分作为实例，应用以下一系列的图形转换算法，得到一棵联结树。整个步骤如下：1、建立一个无向图，称之为道义图；2、在道义图中加入弧，使之变成弦化图；3、从弦化图中，确定并选择节点子集，结成小圈子；4、建立联结树：首先把小圈子当作聚类，把聚类连接起来形成满足联结树特性的无向树，然后插入合适的分离集。为了建立最佳联结树，必须把小圈子连起来，这样构成的小圈子树满足联结树的特性和最优性标准，最优性标准有助于缩短联结树最小化推理的计算时间。建立最优联结树算法分为两部分：首先，通过反复选择和插入候选分离集的方法形成最优联结树；然后选择分离集。这样，学生模型就从知识表示框架的形式转变为联结树的结构。这种联结树形式的学生模型虽然不能像知识表示框架那样体现出各个知识项之间的逻辑关系，但是更有利于学生模型的更新。当某门课程的学生模型建立起来后，根据上述步骤，一次性地将其转换为联结树结构，当学生模型在正常工作时就以这种联结树的形式进行消息的传播、参数性能估计等任务。4.2消息传播在建立了联结树结构后，首先对联结树形式的学生模型初始化，使之满足联结树的定义的条件，在有观测值加入下对学生模型进行更新，然后用联结树结构计算任意知识项N的概率分布。现在进行全局传播以使得到的联结树局部一致。全局传播包括一系列的局部操作，称为消息传播。消息传播发生在聚类X和它的一个邻聚类Y之间。全局传播使得每个聚类给它的每个邻聚类发送一条消息，这些消息的传递是有顺序的，从而保证传递的消息能保持与先前传递过的消息的一致性。当全局传播完成后，每个聚类-分离集对都是一致的，联结树也是局部一致的，从而完成了推理的过程。通过消息传播的算法，可以得到当某个学生学习“条件表达式”和“循环条件”这两个知识项的掌握程度为E时，图4-1中各个知识项有如下图4-2概率分布。图4-2消息传播后的学生模型的概率分布当再次有新的观测值进入时，因为新的观测并未否定原有观测的有效性，同时整个学生模型的结构也没有改变，所以要把观测状态被更新为V=v的变量加入联结树中，再通过执行全局传播以恢复联结树结构的一致性，这样就将新信息加入到模型当中。小结本文针对建立的覆盖型贝叶斯网络的学生模型有无向环时，给出了学生模型的更新的方法，即：首先将网络化的学生模型转换为一种易于消息传播的联结树结构，然后在这种结构下，简单的通过消息传递来完成整个学生模型的更新。参考文献[1]于长慧,孟令奎,潘和平.基于贝叶斯网络的不确定知识处理研究[J].计算机工程与设计，2004,1.25(1)：1-4[2]P.Brusilovsky.Adaptiveandintelligenttechnologiesforweb-basededucation[J].KI-Kunstligenz,1999,(13):19-25[3]边联。适应性学习系统中的适应性策略研究[D].东北师范大学硕士论文。2010.5[4刘振安编著.《C++程序设计教程》[M].北京：科学出版社，2005.2[5]陈仕品，张剑平。适应性学习支持系统的学生模型研究[J]。中国电化教育，2010.5（280）：112-117[6]王岚.适应性学习系统中学习模型迁移方法的研究[D]，天津大学硕士论文.2004年结构化编程E:0.789F:0.154A:0.054N:0.003Switch语句E:0.777F:0.222A:0.001N:0.000For语句E:0.717F:0.197A:0.085N:0.071While语句E:0.610F:0.301A:0.088N:0.001Do-while语句E:1.000F:0.000A:0.000N:0.000条件表达式式条件表达式E:1.000F:0.000A:0.000N:0.000循环条件E:1.000F:0.000A:0.000N:0.000嵌套语句E:0.654F:0.257A:0.086N:0.003