基于近似子图的规则空间压缩算法

2019-09-15 23:58黄宏涛梁存良李大鹏叶海智

自动化学报 2019年8期

黄宏涛梁存良李大鹏叶海智

人工智能和认知科学等领域的研究成果[1−3]正在不断促进教学方式向更加智能、高效和个性化的方向发展[4−6].个性化教学的核心问题是通过计算机程序对被试的知识结构[7]和能力水平进行测试,并根据测试结果开展资源推送和学习路径规划等计算机辅助教学活动.Tatsuoka[8]提出的规则空间模型(Rule space model,RSM)是对学生知识状态进行认知诊断的有效方法之一.RSM 的主要特点是假设学生在解题过程中的错误反应是不确定的(可变的).因此,RSM 能够有效处理学生作答过程中的可变性,更为准确地把学生实际反应模式转换为认知过程与技能的掌握概率,从而实现对被试认知结构的诊断[9].

RSM 在智能导师系统[10−12]和个性化学习系统[13−15]等领域中有着成功的应用.Im 等[16]使用RSM 对学生的统计假设检验知识和技能进行了诊断,并能够根据诊断结果对学生进行教学指导.这种方法同样适用于在线教学或计算机辅助学习.Xin等[17]使用RSM 对单一分数在三个认知属性上进行分类,并对教师水平和学生认知技能间的关系进行分析.Badaracco 等[18]在计算机自适应诊断(Computerized adaptive test,CAT)中引入模糊语言建模的专家知识用于支持测试项目选择,提高了RSM诊断结果的准确性.Qin 等[19]提出对Q 矩阵的推理和有效性检验的改进算法,能够产生更合理的Q矩阵规范,进一步改善了RSM 诊断结果的有效性.

这些基于RSM 的方法虽然能够对被试认知结构进行有效、准确的诊断,但规则空间构造需要全局知识依赖关系的支持,导致时间代价较高,不适合用于日常教学中对学生进行小规模的单元诊断.而这种小规模的实时诊断是智能导师系统和个性化学习系统进行知识结构推理的关键环节.为了提高RSM 的灵活性和可扩展性,文献[20−21]提出了一种使用BP 神经网络进行认知诊断建模的方法,使用期望反应模式对神经网络进行训练,然后使用训练后的神经网络对被试观察反应模式进行识别,克服了RSM 模型进行参数估计时对大样本数据的依赖,使基于RSM 的计算机自适应测验应用于课堂教学成为可能.然而,在小规模测试的前提下,属性层级关系约束下的测试项目数量有限,基于神经网络的RSM 能够使用的期望反应模式规模也较小,无法保障总是获得理想的训练误差.

此外,基于神经网络的RSM 虽然能够在一定程度上降低规则空间构造代价,但它没有考虑领域内所有知识之间的全局依赖关系.而在实际教学活动中,领域内知识间的依赖关系是客观存在的,使用依赖保持子图(Dependency preserving subgraph,DPS)[22]构造规则空间的方式能够在认知诊断活动涉及的测试项目确定后,根据领域知识图中的依赖关系生成知识图的相关子图,再由子图出发构造规则空间,这种方法可以显著降低规则空间规模以及预设知识图时的人工参与度.但是,当领域知识图中依赖关系较为复杂时,DPS 生成相关子图的过程中会引入较多和测试项目无关的属性,容易导致相关子图规模过大.相对于DPS 方法,使用顶点导出子图(Vertex derived subgraph,VDS)[23]构造规则空间时不会引入与测试项目无关的属性.这种特性能够保证总是获得规模足够小的规则空间,从而提高RSM 的可扩展性,但其代价是损失了部分领域知识图中的传递依赖关系,会导致理想属性模式集中大量不合理属性模式无法被过滤,从而影响认知诊断的效率和诊断结果的准确率.

为了在保障诊断结果准确率的前提下尽可能提高RSM 方法的可扩展性,使其能够适用于小规模的、及时的课堂教学认知诊断,本文提出一种基于近似子图的RSM 规则空间生成方法.该方法借鉴了文献[24]中通过构建守恒依赖图计算质量守恒集的方法,在守恒依赖图构建过程中忽略了状态空间中的反应状态,有效缩减了待检查候选集的数量,达到了提高守恒集计算效率的目的;同时通过抽取反应状态和已连接组件间的依赖关系,保持了守恒状态间的依赖关系.受文献[24]的启发,本文通过构建近似子图实现对规则空间的压缩,近似子图的构建不需要根据测试项目涉及的属性集合从领域知识图中计算先序依赖关系的传递子图,而是通过忽略先序依赖关系中与测试项目无关的属性来生成领域知识图的近似子图.生成的近似子图能够通过构建虚拟边模拟领域知识图上的依赖关系,从而在不影响生成补救教学路径的前提下显著降低规则空间规模量级,进而提高RSM 的可扩展性.

1 相关概念

在介绍近似子图生成算法前先给出属性、领域知识图、初始路径、路径片段和划分标准的概念.

属性是对程序性知识或陈述性知识的描述,是构成认知结构的基本元素,直接反映了被试的认知技能.属性及其内部依赖关系是构成规则空间的基础.本文使用领域知识图[25]表示属性及其联系.

定义1.四元组G=(V,E,I)为一个领域知识图,其中

1)顶点集合V是属性的有限非空集合;

2)E ⊆V×V为边的有限集合,(v1,v2)∈E表示知识点v2依赖于v1,其中v1∈V,v2∈V;

3)I ⊆V为初始状态集合,对任意vi ∈V,vi∈I当且仅当不存在vj ∈V使得(vj,vi)∈E,ij.

顶点集合V为规则空间模型中的属性集合,边集E是定义在属性集上的二元关系,反映了属性间的先序依赖关系.因此,E是定义在V上的偏序关系,即E是自反、反对称和传递的.在忽略自环的情况下可知G为有向无环图(Directed acyclic graph,DAG).

定义2.称领域知识图G上的顶点序列p=v1v2···vn为连接v1和vn的路径,当且仅当对任意vi和vi+1存在(vi,vi+1)∈E,其中,1≤i

路径是先序依赖关系下的属性序列,是合理的认知技能学习序列.在图1 所示的领域知识图G中,顶点序列“角、三角形、三角形底”是连接“角”和“三角形底”的路径,它说明如果属性“三角形底”已经被掌握,则属性“三角形”必然已经被掌握;同理,属性“角”也已经被掌握.而顶点序列“相交线、角、三角形、三角形底”是初始路径,它是可行的认知技能序列,是理想属性模式的构成元素.

图1 领域知识图GFig.1 Domain knowledge graph

定理1.对于领域知识图G=(V,E,I)上的任意点v,G上存在初始路径p使得p经过v.

证明.如果v不依赖于任何顶点,由定义1 知v ∈I,于是由定义2 可得p=v为初始路径;否则G上存在顶点v1使得v依赖于v1,则p=v1v为经过v的路径,如果v1不依赖于任何顶点,同理可得p=v1v为初始路径;否则G上存在顶点v2使得v1依赖于v2,此时,如果v2不依赖于任何顶点,则p=v2v1v为初始路径.

进行归纳可得,对于经过v的路径p=vn−1···v2v1v,当n −1=|V|−1 时,如果vn−1不依赖于任何顶点,则p=vn−1···v2v1v为初始路径;否则必然存在顶点vn使得vn−1依赖于vn,此时p=vnvn−1···v2v1v的长度大于|V|,这意味着路径p上必然存在环路,这与G为DAG 图矛盾.于是可得G上不存在顶点vn使得vn−1依赖于vn.

综上所述,对于领域知识图G上的任意点v,G上必然存在初始路径p使得p经过v且1≤|p|≤|V|.

定义3.va和vb为领域知识图G上的两个顶点,如果G中存在顶点序列v0v1···vj,使得p=vav0v1···vjvb为G上的路径,则G上存在从va到vb的路径片段,此时va和vb是连通的,其中,a,b,j为自然数.

顶点间的连通性反映了属性间的先序依赖关系.为了从领域知识图中选择部分内容开展小规模测试,需要根据测试涉及的属性及其依赖关系从领域知识图中划分出相关子图,从而达到生成测试所需的小规模规则空间的目的.下面给出子图划分标准的定义.

定义4.Q为领域项目集合,Qsub⊆Q为测试项目集,对任意q ∈Qsub,k(q)⊆V表示项目q涉及的属性集合,称

为子图划分标准,其中函数k的定义域为测试项目集Qsub,函数K的定义域为领域项目集Q的幂集,值域为领域知识图顶点集V的幂集.

子图划分标准K(Qsub)直接决定了规则空间的规模.由于属性模式依赖于属性间的先序关系,所以在进行小规模测试时需要从领域知识图中抽取测试属性集及其关系,也就是从子图划分标准出发计算领域知识图的相关子图.

2 基于近似子图的规则空间生成算法

2.1 近似子图生成

为了尽可能压缩规则空间的规模,同时避免直接计算领域知识图导出子图出现孤立点,本文通过计算领域知识图的近似子图生成规则空间.

定义5.Gsub=(Vsub,Esub,Isub)为G=(V,E,I)关于子图划分标准K(Qsub)的近似(Overapproximate)子图,其中

1)Esub⊆E为近似子图边集合,(v1,v2)∈Esub当且仅当(v1,v2)∈E,其中v1∈K(Qsub),v2∈K(Qsub);

2)Vsub为顶点集合,如果(v1,v2)∈Esub,则有v1∈Vsub,v2∈Vsub;

3)对任意vi ∈K(Qsub),如果∃vj ∈K(Qsub)使得G上存在从vi到vj(或vj到vi)的路径片段,并且vi到vj(或vj到vi)的路径片段上除vi和vj以外不存在其他顶点属于K(Qsub),则(vi,vj)∈Esub或(vj,vi)∈Esub,其中vi和vj不同;

4)有限次应用2)和3),直至Vsub和Esub不再变化;

5)Isub⊆Vsub为初始顶点集合,对任意vi ∈Vsub,vi ∈Isub,当且仅当不存在vj ∈Vsub,使得(vj,vi)∈Esub,ij.

上述定义给出了近似子图的最小不动点求解方法.下面以图1 所示的领域知识图G为例介绍近似子图计算过程.如果测试项目集Qsub共有5 个项目,这些项目及其对应的属性集合如表1 所示.

图2 G 关于K(Qsub)的近似子图Fig.2 The approximate subgraph of G on division criteria K(Qsub)

表1 测试项目及其对应的属性Table 1 Test item and its attributes

根据定义4,子图划分标准K(Qsub)={相交线,三角形,三角形高,三角形面积}.由定义5 条件1)得,边(三角形,三角形高)、(三角形高,三角形面积)属于Esub,如图2(a)所示;由条件2)可知,顶点“三角形”、“三角形高”、“三角形面积”属于Vsub,如图2(b)所示;由于G上存在由顶点“相交线”到顶点“三角形高”、由顶点“相交线”到顶点“三角形”以及由顶点“三角形”到顶点“三角形面积”的路径片段,故根据条件3)可得,边(相交线,三角形高)、(相交线,三角形)、(三角形,三角形面积)属于Esub,虽然也存在“相交线”到“三角形面积”的路径片段,但这条路径需要经过“三角形”或“三角形高”,不符合条件3)的要求,因此忽略该近似边,图2(c)给出了添加近似边后的结果;再次应用条件2)可得,Vsub={相交线,三角形,三角形高,三角形面积},如图2(d)所示;再次应用条件3)时,(K(Qsub)−Vsub)=∅,所以Esub不再变化,近似子图求解结束,最后由条件5)可得,初始状态集合Isub={相交线}.于是可得G=(V,E,I)关于子图划分标准K(Qsub)的近似子图Gsub=(Vsub,Esub,Isub),如图2(d)所示.

Gsub对应于规则空间模型的邻接矩阵,由邻接矩阵可计算出可达矩阵.可达矩阵反映了属性间的间接依赖关系,即Gsub上顶点间的可达关系.本文通过对近似子图Gsub进行可达性分析,计算邻接矩阵的可达矩阵,其时间复杂度为O(ne),其中,n=|Vsub|,e=|Esub|.

2.2 期望反应模式构建

构建规则空间的目的是通过模式匹配建立观察反应模式与期望反应模式之间的映射,进而通过期望反应模式确定理想属性模式.因此,构建规则空间需要由近似子图确定理想属性模式、期望反应模式及两者间的关系.

属性模式是一组认知技能的集合,即知识状态.为了对被试的认识结构进行分类,需要由Gsub的顶点集Vsub生成对应的属性模式.理论上属性模式集合是属性集合的幂集.下面给出属性模式[3]的形式定义.

定义6.属性模式是一个有序n元布尔序列m=b1b2···bn,其中n=|Vsub|,bi为布尔值,表示对应属性是否被掌握,bi为1 表示属性i成立,0 表示不成立,1≤i≤n.

图2 所示实例中,Vsub包含“相交线,三角形,三角形高,三角形面积”4 个属性,可能的属性模式有16 种.考虑到属性之间的偏序关系,这16 种可能属性模式中有一部分是不合理的,例如属性模式(0100),它反映了被试掌握了属性“三角形”却未掌握属性“相交线”,这种知识状态是不可接受的.而属性模式(1100)是合理的,它反映了被试同时掌握了属性“相交线”和属性“三角形”.这种合理的属性模式为理想属性模式[5],它是可行的认知技能序列.

定义7.令M为理想属性模式集合,L:M →为标记函数,任意m ∈M为理想属性模式当且仅当

成立,其中pi为Gsub上的初始路径,Γ(pi)表示pi上所有属性的集合,n≥1.

上述定义给出了判断一个属性模式是否合理的标准,根据定义7 可得Gsub生成的理想属性模式集合M={0000,1000,1100,1010,1110,1111}.表2给出了理想属性模式及其标记的对应关系.

表2 由Qsub生成的理想属性模式Table 2 Ideal attribute pattern generated by Qsub

表2 列出的属性模式反映了被试的潜在认知结构.认识诊断的最终目标是建立观察反应模式和理想属性模式之间的映射,从而产生对被试的认知诊断.观察反应模式是指被试对测试项目的实际反应结果,是在有噪音(存在失误)情况下得出的测试结果序列.认知诊断主要任务是在规则空间中对观察反应模式进行模式识别,从而过滤噪音干扰并找出对应的期望反应模式(无噪音干扰下的反应模式),最后由期望反应模式获取理想属性模式映射,从而给出认知诊断结果.因此,需要建立理想属性模式与期望反应模式间的对应关系.下面给出期望反应模式的定义.

由定义8 可知,期望反应模式是理想属性模式的函数.表3 列出了期望反应模式与理想属性模式间的映射关系.第1 行中R(M)=00000 表示被试在5 个项目上的反应结果全部错误,对应的理想属性模式m=0000 说明4 个属性都没有掌握,所以相应的L(m)为空集.同理,第4 行R(m)=11101说明被试掌握了项目q1,q2,q3和q5对应的属性,所以有m=1110 和L(m)={相交线,三角形,三角形高}.

表3 理想属性模式与期望反应模式的对应关系Table 3 Expected response pattern corresponding to ideal attribute pattern

2.3 规则空间生成

规则空间是定义在观察反映模式和期望反应模式上的关系,是两者笛卡尔积的子集.构建规则空间的核心问题是由理想属性模式构建期望反映模式,从而确定规则空间中的纯规则点,即分类中心.在计算分类中心之前,需要先由领域知识图和测试项目集计算近似子图(Approximate subgraph,AS),算法1 描述了AS 的计算过程.

算法1.AS 算法

输入.领域知识图G=(V,E,I)和测试项目集Qsub⊆Q

输出.近似子图Gsub=(Vsub,Esub,Isub)

AS 算法1∼4 行由测试项目集Qsub生成子图划分标准K(Qsub),第6 行的是Vsub在K(Qsub)下的补集,初始为K(Qsub).第7∼18 行的主要功能是生成近似子图中的直接依赖关系,9∼14行对中的每个顶点的直接关联关系进行处理,根据顶点的直接关联关系生成近似子图中相应的边(图2(a)).15∼17 行根据顶点是否存在直接关联关系决定是否把该顶点加入近似子图顶点集(图2(b)).20∼24 行的功能是判断是否存在从Vsub中的顶点vi到中顶点vj的路径片段,如果存在,说明vj间接先行依赖于vi,这是一种近似依赖关系,所以在近似子图中建立vi到vj的边,同时把vj加入近似子图的顶点集(图2(c),2(d)).

近似子图能够模拟子图结点在领域知识图上的依赖关系,排除属性模式中的不合理因素,缩减合理属性模式集规模.算法2 给出了由近似子图计算理想属性模式(AS based ideal attribute mode,ASIAM)的过程.

算法2.ASIAM 算法

输入.近似子图Gsub=Vsub,Esub,Isub

输出.理想属性模式集合M

算法2 的核心思想是按照定义7 给出的标准,从近似子图的初始节点开始,依次寻找顶点个数为1∼|Vsub|的初始可达子图的过程(4∼17 行).这里初始可达子图是近似子图的子图,且初始可达子图中的任意顶点至少属于一条初始路径.算法第1 行的Γ1用于存储上次迭代过程中找到的理想属性模式,Γ2存储当前迭代找到的理想属性模式.由于可能有多个初始结点,为了把搜索问题简化为单源路径搜索,设置初始顶点E,使其能够到达Isub中的所有顶点.5∼15 行依次从上一轮迭代产生的理想属性模式中的顶点出发展开搜索,如果能够找到1 条新边且能够引入1 个新顶点,则产生一个长度增1 的理想属性模式(8∼13 行),将其存入Γ2(第9 行).一轮迭代结束,产生一组长度增1 的理想属性模式.算法2 最后返回集合M.注意到M中的元素实际上是理想属性模式对应的标签集合,可由定义7 直接导出理想属性模式.

期望反映模式和理想属性模式是一一对应的,所以可以根据定义8 直接导出M对应的期望反应模式集合,从而生成规则空间中的纯规则点,完成规则空间的构建.由于规则空间模型的重要假设是被试在进行测试时会出现失误,造成观察反应模式与期望反应模式间的误差.因此,如何把被试的观察反应模式映射到期望反应模式是进行认知诊断的关键.可以通过计算被试实际规则点和纯规则点的马氏距离进行模式识别,得出学生对知识的掌握情况,详细计算过程见文献[8,16−17].

2.4 算法分析

1)规则空间压缩能力

压缩规则空间的实质是缩减理想属性模式集的规模.当测试项目集确定后,属性模式涉及的属性集合也就确定了.为了缩减理想属性模式集的规模,需要从领域知识图中提取属性间的依赖关系.如果通过计算领域知识图的依赖保持子图提取属性依赖关系,会引入和测试项目集无关的额外属性,导致理想属性模式集的规模呈指数级增长,如图3(a)所示.直接计算顶点导出子图能够避免引入额外属性,其对传递依赖关系的忽略会导致理想属性模式集规模过大,因为大量不合理属性模式无法被过滤,如图3(b)所示.本文通过计算领域知识图关于测试项目集的近似子图(Approximate subgraph,AS)生成属性间的依赖关系,相对于VDS,计算近似子图能够在不引入额外属性的前提下进一步压缩理想属性模式集的规模,从而达到压缩状态空间规模的目的.以第3.1 节给出的测试项目集为例,图3(a)是由测试项目集计算出的依赖保持子图,图3(b)为顶点导出子图,图3(c)为由测试项目集计算出的近似子图.

图3 测试项目集的导出子图Fig.3 Subgraphs exported from test item set

由图3 知,为了避免在传递依赖子图中引入额外顶点,顶点导出子图只保留了领域知识图中与测试项目直接相关的依赖关系,忽略了知识图中的间接依赖关系.事实上,在领域知识图上存在“相交线”通过“垂线”到“三角形高”路径、“相交线”通过“角”到“三角形”的路径以及“三角形”通过“三角形底”到“三角形面积”的路径,也即“相交线”和“垂线”是“三角形高”的先行知识点、“相交线”和“角”是“三角形”的先行知识点以及“三角形”和“三角形底”是“三角形面积”的先行知识点.顶点导出子图对这种间接依赖关系的忽略是不合理的,同时也会导致理想属性模式集规模膨胀,表4 给出了由VDS 导出的理想属性模式集,其规模为8.而近似子图保持了“相交线”到“三角形高”、“相交线”到“三角形”以及“三角形”到“三角形面积”的传递依赖关系,虽然还存在“相交线”到“三角形面积”的间接依赖关系,但需要通过“三角形高”或“三角形”实现,根据定义5 条件3)近似子图中不建立该依赖关系.近似子图能够在不引入额外属性的前提下保持属性间的间接依赖关系,从而实现对理想属性模式规模的进一步压缩.本例中由近似子图导出的理想属性模式规模仅为5,如表2 所示.

通过上述实例可以看出,近似子图能够显著缩减理想属性模式集的规模,从而实现对规则空间的压缩.相对于VDS 而言,这种压缩能力是通过构造领域知识图中不存在的虚拟边实现的.

表4 由VDS 导出的理想属性模式集Table 4 Ideal attribute set exported from VDS

2)依赖关系保持能力

近似子图中引入的虚拟边描述了顶点间的间接依赖关系,目的是使近似子图尽可能保持领域知识图中知识间的依赖关系.近似子图中引入的这些新的依赖关系是否能够保持领域知识图上的依赖关系是影响认知诊断结果正确性的关键因素.为了证明近似子图依赖关系保持能力,下面先参考文献[26]给出的DAG 图间模拟关系的定义.

定义9.令Gi=(Vi,Ei,Ii)为DAG 图,其中i=1,2,V2⊆V1,模拟关系是定义在G1,G2上的二元关系R ⊆V1×V2当且仅当下列条件成立:

a)对任意v ∈I2,如果G1上存在路径片段u1u2···un,其中,u1∈I1,un=v,n≥1,1≤i≤n,此时(ui,v)∈R;

b)对任意(v1,v2)∈R,如果存在直接依赖于v2,则G1上存在从v2出发的路径片段u1∈I1,un=v,使得成立,其中,u1=v2,

如果存在定义在G1和G2上的模拟关系R,则称G2模拟G1或G1被G2模拟,记为G1≺ST G2.

定理2.如果Gsub=(Vsub,Esub,Isub)为G=(V,E,I)关于子图划分标准K(Qsub)的近似子图,则有G ≺ST Gsub成立.

证明.令R ⊆V×Vsub为定义在G和Gsub上的二元关系,由定义4 和定义5 可知,Isub⊆Vsub=K(Qsub)⊆V.

a)对任意v ∈Isub,由定义9 条件a)可知,如果v ∈I,则(v,v)∈R,否则,由定理1 可知,G上存在从初始节点到v的初始路径u1u2···un,使得u1∈I,un=v成立,其中,1≤i≤n,于是可得(ui,v)∈R;

b)对任意(v1,v2)∈R,对任意v2的直接后继节点由v2∈Vsub,可知,v2∈V,根据定义5 条件3)可得,G上存在从v2到的路径片段u1u2···un,使得u1=v2,un=其中,n≥1,1≤i≤n,于是有

定理2 证明了领域知识图G能够被近似子图Gsub模拟.但是近似子图中引入了领域知识图上不存在的间接依赖关系,这种模拟关系是否能够使Gsub保持G上顶点间的依赖关系是影响规则空间正确性的决定因素.下面通过引入定义在路径上的Stutter 等价关系来说明这个问题.

定义10.令Gi=(Vi,Ei,Ii)为两个DAG图,pi为Gi上的路径,其中i=1,2.其中,p1=

p1Stutter 等价于p2当且仅当存在二元关系R⊆V1×V2,使得···成立,其中,1≤i1≤m1,1≤i2≤m2,1≤i3≤m3,···,1≤j1≤n1,1≤j2≤n2,1≤j3≤n3,···,p1Stutter 等价于p2记为p1p2.

定理3.如果Gsub=(Vsub,Esub,Isub)为G=(V,E,I)关于子图划分标准K(Qsub)的近似子图,对于Gsub上的任意初始路径psub,G上存在初始路径p,使得ppsub.

证明.由定理2 可知,G ≺ST Gsub,令R ⊆V×Vsub为定义在G和Gsub上的模拟关系,psub=v1v2v3···为Gsub上的初始路径.由于v1∈Isub,根据定义9 条件1)可知,G上存在路径片段u11u12···其中,u11∈I,=v1,n1≥1,1≤i1≤n1,此时有∈R成立.

假设vm为psub上的顶点(m≥1),且G上存在路径片段其中,=vm,nm≥1,此时有∈R成立,1≤im≤nm.

对于psub上的顶点vm+1,由于vm+1直接依赖于vm,由定义9 条件b)可知,G上存在从vm出发的路径片段使得(ui(m+1),vm+1)∈R成立,其中,u(m+1)1=vm,=vm+1,nm+1≥2,1≤im+1≤nm+1.

经归纳可得,G上存在初始路径p=v11v12······Stutter 等价于psub.

定理3 保证了近似子图上的路径在其生成知识图上存在Stutter 等价路径,说明近似子图保持了领域知识图上的依赖关系,即近似子图引入的额外依赖关系能够模拟领域知识图上的依赖关系.这个性质保证了理想属性模式及规则空间的合理性.也就是说,近似子图不仅能够有效压缩规则空间的规模,而且能够保持领域知识图上的依赖关系.

3)算法性能分析

给定领域知识图G=(V,E,I)和测试项目集Qsub.对于AS 算法,最坏情况是初始时K(Qsub)中顶点间不存在直接依赖关系,此时AS 算法需要探测Vsub中任意顶点到中顶点的路径是否满足定义5 第5)项的要求.因此,AS 算法的最坏时间复杂度为(|V|+|E|)×|K(Qsub)|.而DPS 算法为保持领域知识图中与K(Qsub)相关的全部依赖关系,最坏时间复杂度也为(|V|+|E|)×|K(Qsub)|.由于VDS 算法只从领域知识图中抽取与K(Qsub)中顶点相关的直接依赖关系,所以最坏时间复杂度为|V|+|E|.从消耗的存储空间角度来看,AS,DPS和VDS 三种算法在计算过程中都需要存储生成子图的顶点集和边集.由于AS 算法和VDS 算法生成的子图都不引入K(Qsub)以外的顶点,所以它们在最坏情况下的空间复杂度为|K(Qsub)|+|E|,DPS算法的最坏空间复杂度为|V|+|E|.

3 实验结果与分析

本文开展了两组实验分别用于验证基于近似子图的规则空间生成算法的空间压缩能力及其在实时课堂教学认知诊断中的有效性.两组实验使用基于认知诊断的可编程教学辅助系统(Cognitive diagnosis based programmable teaching support system,CDPTSS)开展教学认知诊断,该系统在CETE(Center for educational testing and evaluation)实验室设计的认知诊断评价工具提供的开放接口上实现了基于近似子图的规则空间生成算法,并提供实现规则空间压缩的可编程接口.系统运行操作系统为Ubuntu Server 14.04,处理器为Intel xeon e5-262,主频2.0 GHz,内存32 GB.

3.1 实验方案

第1 组实验的目的是对比DPS,VDS 和AS 算法在相同测试项目集下的子图规模以及由这些子图生成的理想属性模式集的规模,从而验证近似子图对规则空间的压缩能力.使用的标准测试集为AAAS(American Association for the Advancement of Science)提供的数学知识图1http://www.project2061.org/publications/bsl/online/index.php.实验数据仅涉及由该数学知识图中知识间依赖关系构成的DAG 图.实验用测试项目集从知识图配套单元测试集中抽取.为了满足AS 算法的初始条件,在DAG图中建立节点0 作为所有初始节点的依赖节点.实验抽取10 组测试项目,在相同环境下使用DPS,VDS 和AS 算法由各组测试项目生成知识子图,进而应用ASIAM 算法计算理想属性模式.

第2 组实验通过开展实际教学认知诊断应用分析DPS,VDS 和AS 的性能差异.评价指标和实验过程与第一组实验相同.实验涉及的课程为《Java语言程序设计》,领域知识图由该课程中的83 个相关知识点生成,测试项目库规模为223.共开展8 次认知诊断测验,根据实际教学单元涉及的知识点确定测试项目.为了评价三种算法在课堂教学认知诊断应用中的实际效果,每次测试项目的规模由所选教学小节的实际内容确定.此组实验首先根据所选测试项目集分别由三种算法生成规则空间,并记录相关结果数据.进一步选择一个教学班共56 人作为实验对象,使用AS 算法生成的规则空间对学生知识状态进行诊断,并由实验对象对评价结果进行评价反馈,以验证AS 算法生成的规则空间的合理性以及应用该规则空间开展认知诊断的准确率.

3.2 规则空间压缩能力实验结果与分析

第1 组和第2 组实验生成的近似子图及理想属性模式规模分别如表5 和表6 所示.从表5 给出的子图顶点集规模来看,AS 和VDS 算法没有引入与测试项目集无关的顶点,所以它们计算获得的子图顶点集只与测试项目集生成的划分标准有关.因此,AS 和VDS 算法计算得到的子图顶点集相同.而DPS 算法计算得到的子图顶点集规模依赖于测试项目集涉及的知识点间的依赖关系.测试项目集生成的划分标准规模越大,知识点间的依赖关系就越复杂,DPS 生成的子图引入的额外顶点越多,导致子图顶点集规模迅速增大,导致DPS 算法计算得到的边集规模显著大于AS 和VDS 算法.而子图规模的增长会导致理想属性模式集规模呈指数级增长,最终导致DPS 算法计算得到的理想属性模式集规模与AS 和VDS 算法计算得到的理想属性模式集不在一个量级上.从实验结果数据来看,AS 和VDS算法相较DPS 算法而言,能够在计算子图过程中忽略与测试项目无关的顶点,从而实现对子图规模的压缩.从表5 给出的实验结果来看,AS 和VDS 最大的差别在于AS 计算得到的子图边集规模大于VDS 计算得到的边集,原因是VDS 计算得到的顶点导出子图只保留与划分标准直接相关的知识依赖关系,这种方法能够保证总是获得最小化的子图边集,不足之处是忽略了知识点间存在的间接依赖关系.为了在压缩子图规模的同时尽可能保证知识点间依赖关系的完整性,AS 算法在VDS 算法基础上,通过构建顶点间的虚拟边模拟知识点间的传递依赖关系,从而在保证子图顶点集最小化的前提下保留了知识点间的间接依赖关系,这是AS 生成的子图边集规模大于VDS 生成的子图边集的原因.这些保留下来的间接依赖关系能够在计算理想属性模式集时缩减更多不合理属性模式,从而使AS 算法计算得到的理想属性模式集显著小于VDS 算法计算得到的理想属性模式集.从实验结果来看,相较于DPS 和VDS 算法,AS 算法能够获得规模更小的理想属性模式集.

表5 第1 组实验中子图及理想属性模式规模Table 5 Scale of subgraphs and ideal attribute pattern in the first experiment

表6 第2 组实验中子图及理想属性模式规模Table 6 The scale of subgraphs and ideal attribute pattern in practical teaching cogonitive diagnosis in the second experiment

表6 给出了第2 组实验中依据实际教学内容生成规则空间部分的实验结果数据.从表6 可以看出,8 次测验涉及的测试项目集规模在6∼8 之间,子图划分标准规模也在5∼8 之间.DPS,VDS 和AS 对子图规模的压缩能力也与第一组实验一致.DPS 对子图规模的压缩能力最弱,但能够精确地保持领域知识图中的所有依赖关系;VDS 对子图规模的压缩能力最强,但不能保持完备的知识依赖关系;AS 创建的子图点集规模与VDS 相同,但边集略大,总体上两者创建的子图规模处于同一水平,但AS 创建的子图通过引入模拟间接依赖关系的虚拟边使子图保持了领域知识图上的依赖关系.相对VDS 而言,由AS 创建的子图能够削减掉更多不合理的属性模式,从而实现对规则空间最大限度的压缩.

3.3 规则空间生成时间实验结果与分析

第1 组和第2 组实验生成的近似子图及理想属性模式规模分别如图4 和图5 所示.图4 给出了ASIAM 算法使用三种算法生成的知识子图构建规则空间消耗的时间代价.图中方块、实心圆点和三角分别表示由DPS,VDS 和AS 构建的子图生成规则空间所需时间代价.从图4 可以看出,在子图规模较小的情况下,三者生成规则空间消耗的时间代价差异不明显.随着子图规模的增长,由DPS 构建的子图生成规则空间所需时间代价呈指数级增长,原因是生成规则空间所需时间代价随子图规模呈指数级增长,这也是DPS 算法不适用于大规模认知诊断的直接原因.

图4 第1 组实验规则空间生成时间Fig.4 Time performance of rule space generation in the first experiment

图5 第2 组实验规则空间生成时间Fig.5 Time performance of rule space generation in the second experiment

由于AS 和VDS 算法生成的子图点集相同,区别仅在于边集规模,它们生成的子图规模处于同一量级.但VDS 算法构建的子图边集规模较小,导致计算合理属性模式所需运算量较小.因此,由VDS算法构建的子图生成规则空间所需时间代价略低于由AS 算法构建的子图生成规则空间所需时间代价.总体上来看,两者所需时间代价处于同一量级.结合表5 实验结果来看,AS 算法能够在不显著降低时间性能的前提下,使构建的子图生成的理想属性模式集规模更小,从而达到压缩规则空间的目的.

图5 给出了由三种算法创建的子图生成规则空间的时间代价.由于8 次教学认知诊断涉及的测试项目集规则较小,三者时间性能在纵轴上的落差远小于图4.总体来看,图5 反映的时间性能与图4 一致,由DPS 算法创建的子图生成规则空间的时间性能最差;由AS 算法创建的子图生成规则空间的时间代价略高于由VDS 算法创建的子图生成规则空间的时间代价,但两者处于同一量级.图5 中在个别点上由三种算法创建的子图生成规则空间的时间代价差异并不明显,这是由于本次测验使用的测试项目涉及的知识点比较集中,DPS 创建子图时没有引入过多的额外顶点,而VDS 和AS 创建子图时不会引入无关顶点,三者生成的子图规则差异不大,所以由三个子图生成规则空间时的时间性能也基本相当.

3.4 诊断结果准确率实验结果与分析

上述实验通过标准测试集和实际教学认知诊断应用,对AS 算法的规则空间压缩能力进行验证和分析,证明AS 相较VDS 和DPS 具有更好的规则空间压缩能力.为了进一步观察由AS 算法创建的近似子图生成的规则空间的合理性,即使用该规则空间开展认知诊断时的准确率,在第2 组实验中进一步使用由AS 算法生成的规则空间对56 名实验对象开展认知诊断,诊断结束后由实验对象对诊断结果的准确性进行主观评价,评价结果由CDPTSS系统回收和统计,如表7 所示.

表7 诊断结果准确率Table 7 Accuracy of diagnostic results

表7 中Valid 表示有效评价结果数量,H,M,L分别表示诊断结果准确率在91∼100%、81∼90%和0∼80% 三个区间的实验对象比例.从实验对象的主观评价结果来看,平均有90.26% 的实验对象的诊断结果准确率在H区间,6.76% 的实验对象的诊断结果准确率在M区间,2.98% 的实验对象的诊断结果准确率在L区间.总体来看,使用AS 算法创建的近似子图生成的规则空间能够有效支持教学认知诊断,诊断结果准确率较高,从被测试对象的主观角度反映了近似子图的依赖关系保持能力.

4 结论

本文提出一种使用似子图压缩规则空间的方法.近似子图能够忽略与测试项目无关的属性,同时通过构建顶点间的虚拟边模拟领域知识图上的传递依赖关系.这种方法在有效缩减规则空间规模的同时,使近似子图保持了领域知识图上的依赖关系.通过构建DAG 图上的模拟关系证明了近似子图对依赖关系的保持能力.使用标准测试集验证了近似子图构建规则空间的时间代价与VDS 算法处于同一量级,但近似子图对依赖关系的保持能力使其能够更为彻底地过滤不合理属性模式,从而实现对规则空间规模的压缩.近似子图在实际教学认知诊断中的应用,进一步验证了近似子图能够在不影响诊断结果准确率的同时,使规则空间模型有效支持小规模、实时教学认知诊断.然而,使用近似子图生成规则空间开展认知诊断产生的知识状态图中存在虚拟边,如何从包含虚拟边的知识状态图中生成补救教学路径是影响诊断结果易用性的关键因素.文献[27−30]提出的由抽象路径生成具体路径的方法为解决该问题提供了可借鉴的思路,今后,将进一步研究如何把包含虚拟边的补救教学路径在领域知识图上具体化.