基于程序性知识学习的项目状态转移函数与多分知识结构

孙晓燕 李进金,2

知识空间理论(Knowledge Space Theory, KST)源于Birkhoff[1-2]提出的关于拟序的定理,Doignon等[3-4]和Falmagne等[5]结合教育心理学将其发展完善．基于教育学和心理学等理论,KST建立一套反映教育教学规律的数学理论,为设计基于计算机网络的知识与学习评价系统提供有效的科学方法和数学框架[5-7]．

传统的二分KST假设个体对项目的回答为正确(用1表示)或错误(用0表示),在对知识和学习进行评价时具有局限性．针对这一局限性,Schrepp[8]将KST推广到有两个以上答案的问题,使用线性有序集评估解决方案的质量．Bartl等[9]讨论具有分级知识状态的知识空间．Stefanutti等[10]提出KST的多分推广,假设项目集上的水平集为完备格．在Stefanutti等[10]的基础上,Heller[11]将拟序知识空间推广到多分情形,提出多分知识结构的两个条件,并考虑项目特定的响应尺度．

技能代表潜在的认知能力,是人们利用知识和经验执行某些活动的能力．Falmagne等[5]建立问题和技能之间的联系．Doignon[12]将技能映射引入KST．Düntsch等[13]与Korossy[14]分别提出技能函数和技能空间．近年来,人们越来越重视知识和技能的评估及其程序化应用[15-22]．Heller等[15-16]研究分布式技能函数和知识结构的网格化,提出特殊技能评估的充要条件．程序性知识是解决问题的操作步骤,是关于“怎么做”的知识．Stefanutti等[17]应用KST,为程序性知识的评估提供数学概念和正式框架,提出解决问题和模拟学习环境的技能评价．Ste-fanutti[18]将这一工作进一步完善及推广,证明给定问题空间的所有可能知识状态的集合是一个学习空间,并给出从问题空间导出学习空间的算法．

在程序性知识的评估中,技能是指与项目的解决相关的解路径或操作路径[18]．李金海等[23]提出概念的渐进式认知,体现人们认识事物是一个从不完全到完全的逐步完善过程,能根据阶段性认知及时指导下一步的行动,并逐渐实现完全认知．同样地,对程序性知识的学习及其技能的掌握也是渐进式认知过程．概念格是形式概念分析理论中用于数据分析与处理的核心工具,也是一种挖掘数据关联的有效方法[24]．这为进一步研究程序性知识的学习与评价提供方法和工具．

1 预备知识

1.1 技能映射诱导的知识结构

在KST中,通过技能映射将知识域Q中的每个项目与有助于解决这个项目的技能联系起来,并从这个关联中推断知识状态．设非空的知识域Q,非空的技能集S,技能映射是三元组(Q,S,τ),其中,τ∶Q→2S{Ø},为从Q到S的非空幂集的映射.给定T⊆S,由T通过析取模型诱导的知识状态为

由T通过合取模型诱导的知识状态为

取遍T⊆S,所有通过析取模型诱导的知识状态的集合是由τ通过析取模型诱导的知识结构；所有通过合取模型诱导的知识状态的集合是由τ通过合取模型诱导的知识结构．由τ通过析取模型诱导的知识结构是知识空间；由τ通过合取模型诱导的知识结构是简单闭包空间．由同一技能映射通过析取模型和合取模型诱导的知识结构是对偶的．有关技能映射及其诱导的知识结构的详细背景参见文献[6]和文献[7]．

1.2 多分知识状态

在KST的多分推广中,知识域Q中的项目的解决质量由水平集L中的级别l∈L表示．在Schrepp[8]提出的KST多分推广中,L为线性有序集．Stefanutti等[10]设定L为完备格．

设X为非空集,≤为X上的偏序关系(即满足自反性、传递性、反对称性的二元关系),则称(X,≤)为偏序集．设(X,≤)为偏序集,对于∀A⊆X,A的最小上界称为A的上确界,记为supA或∨A；A的最大下界称为A的下确界,记为infA或∧A．若∀A⊆X,恒有supA与infA存在,则称(X,≤)为完备格．若∀a∈X,b∈X,恒有

sup{a,b}=a∨b,inf{a,b}=a∧b

存在,则称(X,≤)为格．有限格是完备格．有关格理论的详细背景知识参见文献[2]、文献[25]和文献[26].

在Heller[11]提出的KST多分推广中,个体对知识域Q中各项目的掌握程度用有限的响应值集V表示,且设非空有限响应值集V是格,由于V是有限的,所以V是完备格．

多分知识状态是Q到V的映射K∶Q→V,表示将Q中每个项目对应V中的一个响应值．一切这样的映射的集合记为

1.2.1 多分知识状态的表示法

多分知识状态有两种表示形式,分别由Heller[11]和Stefanutti等[10]提出．

集合表示法[11].多分知识状态K为Q×V的特定子集,即对于∀K∈VQ,K⊆Q×V,记

pv=(p,v)∈Q×V,

对于∀K∈VQ,规定

pv∈K⟺K(p)=v,

则

K={pv|p∈Q,K(p)=v∈V}⊆Q×V．

向量表示法[10].在给定的有限知识域Q中,设|Q|=n,当固定各项目的顺序时,多分知识状态K可简记为以V中的响应值为分量的n维向量．设Q={q1,q2,…,qn},对于∀K∈VQ,记

K=v1v2…vn=(v1,v2,…,vn)∈Vn,

其中vi=K(qi),i=1,2,…,n．

例如,设Q={a,b,c},V={0,1,2},多分知识状态K∶Q→V定义为K(a)=1,K(b)=2,K(c)=0,则多分知识状态K的集合形式为

K={a1,b2,c0}⊆Q×V．

固定各项目顺序为q1=a,q2=b,q3=c,则多分知识状态K的向量形式为

K=120=(1,2,0)∈V3．

为了避免记号的混乱,在下述论述与推导中,本文均采用多分知识状态的集合表示法,向量表示法仅出现在图形中．

1.2.2 多分知识状态的集合表示法的扩展

设(V,≤)为偏序集,v∈V,v的下集记为

↓v={u∈V∶u≤v},

V的所有下集的集合记为

Oπ(V)={↓v∶v∈V},

则(V,≤)与(Oπ(V),⊆)同构[11]．将多分知识状态K∶Q→V扩展到映射K*∶Q→Oπ(V),其中,对于所有的p∈Q,K*(p)=↓K(p),称K*为K的扩展多分知识状态[11]．K*的集合形式为

{pv∈Q×V|∀pw∈K,v∈↓w}．

例如,设Q={a,b,c},V={0,1,2,3},多分知识状态K∶Q→V定义为

K(a)=0,K(b)=3,K(c)=1,

则多分知识状态K的集合形式为

K={a0,b3,c1}⊆Q×V,

由于

↓0={0}, ↓3={0,1,2,3}, ↓1={0,1},

故K的扩展多分知识状态为

K*={a0,b0,b1,b2,b3,c0,c1}⊆Q×V．

2 程序性知识的项目状态转移

函数

程序性知识是一种经过学习自动化的关于行为步骤的知识,如运算法则、解题步骤、操作程序等．在Stefanutti[18]提出的程序性知识的评估中,问题的解决过程被描述为从操作集合中获取操作序列,操作序列应用于问题的某初始状态,产生一个最终状态,由此定义问题空间,并诱导知识空间．本节基于程序性知识的评估框架,通过项目状态转移函数将项目的状态与相关的操作程序对应,将问题空间推广到多分情形．

2.1 项目特定的响应值集

inf(Vi)=∧i(Vi)

称为Vi的底元,记为丄i；

sup(Vi)=∨i(Vi)

称为Vi的顶元,记为丅i．特别地,对于Ø⊆Vi,规定

∨i(Ø)=丄i,∧i(Ø)=丅i,i=1,2,…,n．

例1设Q={q1,q2},

项目q1：已知等腰三角形的腰长为5 cm,底边长比腰长多1 cm,周长为多少？

项目q2：已知等腰三角形的一条边长为5 cm,另一条边长为6 cm,周长为多少？

根据项目解答过程的类型设定响应值集,两个项目的响应值集的格结构是不同的．

q1的解答：

由于q1的解答过程是层层递推的,所以设定V1为有限线性序集,即V1={0,1,2}．V1的底元为丄1=0,V1的顶元为丅1=2．

由于q2的解答中有分类讨论,所以V2不是线性序集．设V2={0,a,b,c},其中

0≤2a, 0≤2b,a≤2c,b≤2c,

a与b不可比较,且a∨2b=c,如图1所示．V2的底元为丄2=0,V2的顶元为丅2=c．

图1 有限格V2={0,a,b,c}的Hasse图Fig.1 Hasse diagram of finite lattice V2={0,a,b,c}

例2设Q={q1,q2},

项目q1：计算7+4×2；

项目q2：计算7+(4-2)×6．

对于层层递推的项目解答或操作过程,根据步骤数设定响应值集,响应尺度可能不同．

q1的解答是层层递推的,步骤数为2,所以设定V1为三分的线性序集,即V1={0,1,2}．

q2的解答是层层递推的,步骤数为3,所以设定V2为四分的线性序集,即V2={0,1,2,3}．

2.2 多分知识结构

K1=K2⟺K1(qi)=iK2(qi),i=1,2,…,n；

Ω称为知识域Q的状态集．

其中vi∈Vi,i=1,2,…,n．特别地,

例如,在例2中,

Q={q1,q2},V1={0,1,2},V2={0,1,2,3}．

于是

K(pv)={K∈K∶pv∈K}≠Ø．

例3续例1．

Q={q1,q2},V1={0,1,2},V2={0,a,b,c},

其中,0≤2a,0≤2b,a≤2c,b≤2c,则

由于

所以K2不满足定义3中条件2),K2不是多分知识结构．

由

知,K3满足定义3中条件1)；由

知,K3满足定义3中条件2)．

如图2所示,K3是多分知识结构．

图2 例3中多分知识结构(K3,)的Hasse图Fig.2 Hasse diagram of polytomous knowledge structure(K3,) in example 3

其中

K1与K2的逐项交是

其中

特别地,对于Ø⊆K,规定

例如,在例3中,K1和K2都不是多分知识结构,所以K1和K2都不是多分知识空间．K3是多分知识结构,由

2.3 项目状态转移函数与项目的相关技能

设程序性知识域Q={q1,q2,…,qn},根据各项目的解答或操作过程设定响应值集．为了保证操作步骤的有限性,下述论述中均假定各项目的解答或操作是非循环的．∀qi∈Q,项目qi的操作集是由其解答或操作过程的每个步骤构成的集合,记为Πi．在这里,本文仅考虑每个项目的某个特定的解法,对于一题多解的情形将在能力模型中考虑．

命题1对于∀q∈Q,设q的解答或操作非循环且步骤数有限,则项目q的操作集Π是有限集．设Π={π1,π2,…,πr},根据每步操作逐一设定响应值,得到项目q的响应值集V是有限格．

1)如果项目q的解答或操作是层层递推的,且步骤数为r,记第k步操作为πk,k=1,2,…,r,则q的操作集Π={π1,π2,…,πr}．设项目q的初始状态为q0,即q的响应值集V的底元为0,根据每步操作逐一设定响应值,即每步操作产生新的项目状态,对应的响应值加1,则项目q的响应值集V是有限线性序集,且V={0,1,…,r}．

2)如果q的解答或操作中有n个分支,则V不是线性序集．先按各分支的层层递推的步骤数设定各分支上线性有序的响应值集,再将任意k(2≤k≤n)个不可比较的响应值的上确界(称为分支定向并[11])设为新的响应值,规定：当n=2时,设a1与b1不可比较,a2与b2不可比较,且

a1∨b1=c,a2∨b2=d,

如果a1≤a2且b1≤b2,则c≤d．当n>2时,若∀l∈A,恒有m∈B,使得l≤m,则∨A≤∨B．这样得到的项目q的响应值集V是有限格．

例如,例1中的项目q1的解答步骤是层层递推的,步骤数为2,所以V1={0,1,2}．项目q2的解答中有分支,2个分支的步骤数均为1,所以2个分支上的响应值集分别{0,a}和{0,b},其中

0≤2a, 0≤2b．

由于a和b不可比较,于是设响应值c=a∨2b,得到项目q2的响应值集V2={0,a,b,c}．V2是有限格．

如果项目的解答或操作中有分支,且至少一个分支的步骤数大于1,则按照命题1中2)的规定给出各分支定向并的序关系,如例4所示．

例4设项目q：解方程|x-3|=3x-5．q的解答中有2个分支,各分支的步骤数均为2,即

则

0≤1a≤2a, 0≤1b≤2b．

将{1a,2a,1b,2b}中任意2个不可比较的响应值的上确界设为新的响应值,即

1a∨1b=2c, 2a∨1b=3d, 1a∨2b=3e, 2a∨2b=4．

由1a≤2a,1b≤1b得

(1a∨1b)≤(2a∨1b),

即2c≤3d．同理可得

2c≤3e, 3d≤4, 3e≤4．

由于1a≤2a,1b≤2b,所以2a∨1b与1a∨2b不可比较,即3d与3e不可比较．如图3所示,项目q的响应值集

V={0,1a,2a,1b,2b,2c,3d,3e,4}

是有限格．

图3 例4中有限格V的Hasse图Fig.3 Hasse diagram of finite lattice V in example 4

表示项目qi的错误状态集．

项目qi的单个操作对项目状态转移的作用可用定义4中的项目状态转移函数φi表示．

定义4设程序性知识域Q={q1,q2,…,qn},项目qi的非空有限操作集为Πi,根据每步操作逐一设定响应值,得到qi的响应值集Vi,i=1,2,…,n．记

且响应值k保持不变．

例5续例2,考察q1、q2的项目状态转移函数．假设学生已掌握加、减、乘的单独运算,项目q1、q2是为了考察学生掌握四则运算顺序的情况．项目q1的操作集Π1={π1,π2},项目q2的操作集Π2={π1,π2,π3},其中,π1表示“先乘、除”,π2表示“从左往右依次计算”,π3表示“计算括号内的运算”．项目q1、q2的解答是层层递推的,由命题1中1)知,

V1={0,1,2},V2={0,1,2,3}．

项目q1的初始状态为

q1的项目状态转移如图4所示．由图4得以下状态转移函数：

q1的终止状态．

图4 例2中项目q1的状态转移图Fig.4 State transition diagram of item q1in example 2

q2的项目状态转移如图5所示．q2的初始状态为

图5 例2中项目q2的状态转移图Fig.5 State transition diagram of item q2in example 2

定义5[18]设非空有限操作集Π,由Π中s个操作元组成的操作序列π1π2…πs∈Πs,称为Π的一个长度为s的操作序列．具有任意长度的所有操作序列(包括空操作序列ε,即s=0)的集合记为Π∧,即

其中,空操作序列ε表示不施以任何操作,ε为Π∧的单位元,即

∀π∈Π∧,επ=πε=π．

对于∀qi∈Q,补充定义

注4[18]设程序性知识域Q={q1,q2,…,qn},任意项目qi的状态转移满足如下性质：

记

则

传递性具体说明如图6所示．

图6 项目状态转移的传递性Fig.6 Transitivity of item state transitions

定义7设非空有限操作集Π,操作序列集Π∧,对于∀s∈Z+,任意给定长度为s的操作序列π1π2…πs∈Πs,π1π2…πs的子序列是操作序列πiπi+1…πi+t,其中,1≤i≤s,0≤t≤s-i．

定义8设非空有限操作集Π,操作序列集Π∧,对于任意2个非空操作序列σ1∈Π∧{ε},σ2∈Π∧{ε},规定σ1≤σ2当且仅当σ1是σ2的子序列．任意给定非空操作序列σ∈Π∧{ε},σ的所有子序列中关于“≤”的极小者称为σ的极小子序列．

命题2设操作序列

σ=π1π2…πs∈Π∧{ε},

其中s∈Z+,则σ的极小子序列为πj,j=1,2,…,s．

例如,设非空操作序列σ=π1π2π3,σ的所有子序列为π1,π1π2,π1π2π3,π2,π2π3和π3．由于

π1≤π1π2≤π1π2π3,

取关于“≤”的极小者得π1；由于

π2≤π2π3≤π1π2π3,

取关于“≤”的极小者得π2；由于

π3≤π2π3≤π1π2π3,

取关于“≤”的极小者得π3．所以σ的极小子序列为π1、π2和π3．

由定义4可知,项目状态转移函数φi表示项目qi的单个操作对项目状态的作用,而由注4可知,项目qi的一个操作序列对给定项目状态的作用由定义9中的过程函数Φi表示．

则

所以空操作序列ε为任意项目的正确操作序列．但是ε未实现状态的转移,因此下述分析中均不考虑空操作路径．

例6续例5,考察项目q1的正确非空操作路径．由图4看出,对于操作序列π1、π2和π1π2,有过程函数：

推论1对于解答或操作步骤数较多的复杂项目q,将q的操作过程划分为t个正确非空操作序列,以此构成q的操作元集

Σ={σ1,σ2,…,σt}⊆Π∧．

根据每个操作元σk(k=1,2,…,t)逐一设定响应值,得到项目q的响应值集V是有限格．

1)如果q的解答或操作是层层递推的,则q的响应值集V为有限线性序集．操作元σk(k=1,2,…,t)作用于qk-1产生新的项目状态qk,响应值由k-1变为k,即φ(qk-1,σk)=qk,称(qk-1,σk,qk)是以qk-1为初始状态,σk为操作元,qk为终止状态的正确单一操作路径,简记为qk-1σk,k=1,2,…,t．于是,得到项目q的响应值集V={0,1,…,t}．

2)如果q的解答或操作中有分支,对q的操作过程进行不同划分,可能使V具有不同的格结构．

例7设项目q：解方程|x2-6|=x2-2x+2．项目q的解答中有2个分支,解答过程如下：

项目q的操作集

Π={π1,π2,π3,π4,π5,π6},

其中,π1表示“当x≥0时,|x|去绝对值”,π2表示“方程移项与合并同类项”,π3表示“解一元一次方程”,π4表示“当x≤0时,|x|去绝对值”,π5表示“一元二次多项式的因式分解”,π6表示“解一元二次方程”．

1)将q的操作过程划分成5个正确非空操作序列,构成操作元集

Σ={π1,π2π3,π4,π2π5,π6}．

根据各分支上的每个操作元逐一设定响应值,得到2个分支上的响应值集{0,1a,2a}和{0,1b,2b,3b},其中

0≤1a≤2a, 0≤1b≤2b≤3b．

取分支定向并,即

1a∨1b=2c, 2a∨1b=3d, 1a∨2b=3e, 2a∨2b=4f, 1a∨3b=4g, 2a∨3b=5．

依照命题1中2)的规定得到{2c,3d,3e,4f,4g,5}的序,于是有限格

V1={0,1a,2a,1b,2b,3b,2c,3d,3e,4f,4g,5}

为q的响应值集,如图7所示．

图7 例7中响应值集V1的Hasse图Fig.7 Hasse diagram of response value set V1in example 7

2)将q的操作过程划分成4个正确非空操作序列,构成操作元集

Σ={π1π2,π3,π4π2,π5π6},

则q的响应值集

V2={0,1a,2a,1b,2b,2c,3d,3e,4}

为有限格,如图3所示．

3)将q的操作过程划分成3个正确非空操作序列,构成操作元集

Σ={π1π2π3,π4π2,π5π6},

则

V3={0,1a,1b,2b,2c,3}

为有限格,如图8所示．

图8 例7中响应值集V3的Hasse图Fig.8 Hasse diagram of response value set V3in example 7

命题1是推论1的特殊情形,即将每个操作步骤划分为一个操作元σk=πk,k=1,2,…,r,得到操作元集

Σ={σ1,σ2,…,σr}=Π⊆Π∧．

因此,过程函数Φi的定义9可做如下推广．

定义10设程序性知识域Q={q1,q2,…,qn},qi的操作元集Σi={σ1,σ2,…,σti},

2)任意操作序列

则

如果项目q的解答或操作中有分支,Vq不是线性序集,需要考虑操作组合对项目状态的作用．

例8续例7．记

σ1=π1π2π3,σ2=π4π2,σ3=π5π6,

取q的操作元集Σ={σ1,σ2,σ3},由例7中3)可知,q的响应值集

V={0,1a,1b,2b,2c,3}．

q的项目状态转移图如图9所示．由图可知,q的正确非空操作序列为σ1、σ2、σ3和σ2σ3．由

Φ(q0,σ1)=q1a,Φ(q0,σ2)=q1b,

1a与1b不可比较,1a∨1b=2c,可知,

Φ(q0,{σ1,σ2})=q2c,

即{σ1,σ2}为q的正确操作组合,其中q0σ1和q0σ2是q0{σ1,σ2}的极小子路径．同理,

Φ(q0,{σ1,σ2σ3})=q3,

即{σ1,σ2σ3}为q的正确操作组合,其中q0σ1、q0σ2和q1bσ3为q0{σ1,σ2σ3}的极小子路径．

图9 例7中3)的项目状态转移图Fig.9 Item state transition diagram in 3) of example 7

定义12设程序性知识域Q={q1,q2,…,qn},项目qi的操作元集Σi={σ1,σ2,…,σti},响应值集Vi为有限格,i=1,2,…,n．对于∀qi∈Q,qi的操作程序是由其正确非空操作序列或正确非空操作组合构成的序列δ=ω1ω2…ωl,其中

则

例9设项目q：已知直角三角形的两条边长分别为4 cm和6 cm,第三条边长为多少？项目q的解答过程如下：

项目q的操作集Π={π1,π2,π3,π4},其中,π1表示“勾股定理”,π2表示“将x=4,y=6代入方程x2+y2=z2”,π3表示“解一元二次方程”,π4表示“将x=4,z=6代入方程x2+y2=z2”．记

σ1=π1,σ2=π2π3,σ3=π4π3,Σ={σ1,σ2,σ3},

则q的响应值集V={0,1,2a,2b,3},q的项目状态转移图如图10所示．

图10 例9的项目状态转移图Fig.10 Item state transition diagram of example 9

由图10可知,q的正确非空操作序列为σ1、σ2、σ3、σ1σ2和σ1σ3；正确非空操作组合为{σ2,σ3}．显然,每个正确的非空操作序列和正确的非空操作组合都是正确的非空操作程序．由于

Φ(q0,σ1)=q1,Φ(q1,{σ2,σ3})=q3,

所以

Φ(q0,σ1{σ2,σ3})=q3,

σ1{σ2,σ3}为项目q的正确操作程序,操作路径q0σ1{σ2,σ3}的极小子路径为q0σ1、q1σ2和q1σ3．因此,项目q的所有正确操作路径为q0σ1、q1σ2、q1σ3、q0σ1σ2、q0σ1σ3、q1{σ2,σ3}和q0σ1{σ2,σ3}．

定义 13设程序性知识域Q={q1,q2,…,qn},项目qi的操作元集Σi={σ1,σ2,…,σti},响应值集Vi是有限格,i=1,2,…,n．在合取模型中,对于∀qi∈Q,项目qi的一个正确操作路径的极小子路径称为qi的一个相关技能．qi的所有相关技能的集合Si称为qi的技能集,i=1,2,…,n．

由于项目qi的任意一个正确操作路径的极小子路径为Σi中的构成该路径的操作元对应的正确单一操作路径,所以,qi的技能集为Σi中的各操作元对应的正确单一操作路径的集合．

例10续例8,考察项目q的技能集．记

σ1=π1π2π3,σ2=π4π2,σ3=π5π6,

q的操作元集Σ={σ1,σ2,σ3},响应值集

V={0,1a,1b,2b,2c,3}．

由图9可知,q的所有正确操作路径为q0σ1、q0σ2、q1bσ3、q0σ2σ3、q0{σ1,σ2}和q0{σ1,σ2σ3}．取所有正确操作路径的极小子路径,得q0σ1、q0σ2和q1bσ3．所以,项目q的技能集为Sq={q0σ1,q0σ2,q1bσ3}．

定义14设程序性知识域Q={q1,q2,…,qn},项目qi的操作元集Σi={σ1,σ2,…,σti},响应值集Vi是有限格,i=1,2,…,n．记

对于∀σ∈Σ,

表示以σ为操作元的正确单一操作路径的等价类,知识域Q的技能集为

S={[σ]|∀σ∈Σ}．

例11续例5,考察例2的项目q1、q2的技能集,以及知识域Q的技能集．记

σ1=π1,σ2=π2,σ3=π3,Σ1={σ1,σ2},Σ2={σ3,σ1,σ2},

则

Σ=Σ1∪Σ2={σ1,σ2,σ3}．

因此,记

则Q的技能集

3 基于程序性知识的多分知识

结构

3.1 由操作路径导出的合取的技能映射

定义16设程序性知识域Q={q1,q2,…,qn}

记

记

则

另一方面,∀i∈H,记

则

由

知,∀s∈τ(K),必定存在i∈H,使得

即

从而

因此

例13续例12．

同理可得

定义17设程序性知识域Q={q1,q2,…,qn}

命题3设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø},则对于∀qi∈Q,τ满足如下2个条件：

2)差异性.∀v∈Vi{0},w∈Vi{0},v与w不可比较,则

3.2 由合取的技能映射诱导的多分知识结构

定义18设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．给定技能状态T⊆S,T表示个体掌握的技能的集合,由T通过合取模型诱导的多分知识状态为

定理2设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．取遍所有的技能状态T⊆S,所有通过合取模型诱导的多分知识状态的集合

是多分知识结构．

由于

所以,K满足多分知识结构的定义3中2)．综上所述,取遍所有的T⊆S,所有通过合取模型诱导的多分知识状态的集合K为多分知识结构．

定义19设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．取遍所有的技能状态T⊆S,所有通过合取模型诱导的多分知识状态的集合K称为由技能映射τ通过合取模型诱导的多分知识结构．

例14续例13．

合取的技能映射τ定义为

取遍所有的技能状态T⊆S,得到如下通过合取模型诱导的多分知识状态：

所以,由τ通过合取模型诱导的多分知识结构为

图11 例14中多分知识结构(K,)的Hasse图Fig.11 Hasse diagram of polytomous knowledge structure(K,) in example 14

注5命题3中1)对于通过合取模型诱导多分知识结构是必要的．如果技能映射τ不满足该条件,则由τ通过合取模型诱导的多分知识状态的集合可能不满足定义3中2)．

例如,在例14中,若定义技能映射τ′为

由于

所以K′不满足定义3中2),K′不是多分知识结构．

根据项目qi的操作元集Σi逐一设定响应值,得到qi的响应值集Vi不一定是线性有序集．

例15续例1．

Q={q1,q2},Π1={π1,π2},Π2={π2,π3}．

记

σ1=π1,σ2=π2,σ3=π3,Σ1={σ1,σ2},Σ2={σ2,σ3},

则

由项目状态转移(图12)可得

则S={s1,s2,s3}．由操作路径导出的合取的技能映射τ为

图12 例1的项目状态转移图Fig.12 Item state transition diagram of example 1

取遍所有的技能状态T⊆S,得到由τ通过合取模型诱导的多分知识结构为

图13 例15中多分知识结构(K,)的Hasse图Fig.13 Hasse diagram of polytomous knowledge structure(K,) in example 15

注6命题3中2)对于通过合取模型诱导多分知识结构是必要的．如果技能映射τ不满足该条件,则由τ通过合取模型诱导的多分知识状态的集合可能不满足定义3中2)．

例如,在例15中,若定义技能映射τ′为

其中,a与b不可比较,

但是

不满足命题3中2)．由τ′通过合取模型诱导的所有多分知识状态的集合为

由于

所以K′不满足定义3中2),K′不是多分知识结构．

命题5设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．给定技能状态T⊆S,T表示个体掌握的技能的集合,由T诱导的个体能达到的项目状态的集合记为

记

由命题5和定义18可得推论2．

推论2设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．给定技能状态T⊆S,T表示个体掌握技能的集合,由T通过合取模型诱导的多分知识状态为

证明对于∀K1∈K,K2∈K,其中Ki是由技能状态Ti通过合取模型诱导的多分知识状态,即

记

记

因为

3.3 对偶性

推论3设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．给定技能状态T⊆S,T表示个体没有掌握技能的集合,由T诱导的个体没达到的项目状态的集合记为

则

例如,在例14中,取个体没有掌握技能的集合T={s2},则

记

则

推论4设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．T⊆S表示个体没有掌握技能的集合．取遍T⊆S,由τ诱导的个体没达到的项目状态的集合为

L={Lτ(T)|∀T⊆S}．

L满足集合并∪-封闭．

例如,在例14中,由τ通过合取模型诱导的多分知识结构为

则K的扩展多分知识结构为

所以,由推论3可知,取遍个体没有掌握的技能状态,所有由τ诱导的个体没达到的项目状态的集合为

如图14所示,由于

同理可得,

所以L满足集合并∪-封闭．但是,因为

所以L不满足集合交∩-封闭．

图14 例14中多分知识结构的对偶(L,)的Hasse图Fig.14 Hasse diagram of the dual (L,) of polytomous knowledge structure in example 14

定义20[27]称三元组(U,A,I)为一个形式背景,其中U={x1,x2,…,xn}为对象集,每个xi(1≤i≤n)称为一个对象；A={a1,a2,…,am}为属性集,每个aj(1≤j≤m)称为一个属性；I⊆U×A为U和A之间的二元关系,若(x,a)∈I,则称对象x具有属性a,若(x,a)∉I,则称对象x不具有属性a．

用1表示(x,a)∈I,用0表示(x,a)∉I,则形式背景可表示为只有0和1的表格,如表1所示．

表1 形式背景表Table 1 Formal background

设合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{Ø}．将Ω+视为对象集,S视为属性集,I⊆Ω+×S是Ω+和S之间的二元关系,规定

又由推论2可知,由τ通过合取模型诱导的多分知识结构为

3.4 从状态空间导出多分知识结构的算法

n)为起点的所有操作路径导出合取的技

能映射(Ω+,S,τ)．

初始设置.由qi的所有正确单一操作路径构成队列

并将Wi中任意有限条起点相同的路径的组合添加到Wi中,得

其中,σk1,σk2,…,σks为操作程序δ的所有极小子程序．

的对偶性得到由τ通过合取模型诱导的多

分知识结构K．

step 1 在形式背景(Ω+,S,I)中,规定

step 2 取个体没有掌握的技能状态Ti={si},由(Ω+,S,I)导出Ti诱导的没达到的项目状态Lτ(Ti),i=1,2,…,m．由{Lτ(T1),Lτ(T2),…,Lτ(Tm)}取集合并∪-封闭,张成所有由τ诱导的个体没达到的项目状态的集合L．

算法1采用起点固定的广度优先路径搜索算法(Breadth First Search, BFS)．这是基于队列这种数据结构的搜索方式,特点是由每个状态扩展出许多状态,然后再以此扩展,直到处理完毕队列中所有状态．算法1中step 1的时间复杂度为O(|S|+|Ω+|)．算法2中step 2的时间复杂度为O(|Ω+|·|S|)．在算法2中,可考虑结合形式背景或概念格中的已有结果,如对象约简或属性约简,从而去除计算中的冗余部分,达到算法的简化．

例16设Q={q1,q2},项目q1是例7中的q：解方程|x2-6|=x2-2x+2；项目q2：已知x>1,且|x-1|=x2-4x+5,求x．q2的解答：

x>1：|x-1|=x2-4x+5

⟹x-1=x2-4x+5 操作步骤π1

⟹x2-5x+6=0 操作步骤π2

⟹(x-2)(x-3)=0 操作步骤π5

⟹x=2或x=3 操作步骤π6

记

σ1=π1π2,σ2=π3,σ3=π4π2,σ4=π5π6,

由例7中2)可知,

V1={0,1a,2a,1b,2b,2c,3d,3e,4},V2={0,1,2}．

Σ={σ1,σ2,σ3,σ4},

记

项目状态转移如图15所示．

图15 例16的项目状态转移图Fig.15 Item state transition of example 16

由算法1中step 1可得

再由算法1中step 2可得,导出的合取的技能映射τ为

由于1a∨11b=2c,且

由算法2得到由形式背景(Ω++,S,I)导出的个体没达到的项目状态的集合L,从而得到由τ通过合取模型诱导的多分知识结构K．

1)在形式背景(Ω++,S,I)中,规定

表2 例16中技能映射(Ω++,S,τ)的形式背景表Table 2 Formal background of skill map(Ω++,S,τ) in example 16

2)由表2导出个体没达到的项目状态.取

Ti={si},i=1,2,3,4,

则

由{Lτ(T1),Lτ(T2),Lτ(T3),Lτ(T4)}取∪-封闭张成τ诱导的个体没达到的项目状态的集合:

3)取L的对偶,即

得到τ通过合取模型诱导的Ω++上的扩展多分知识结构:

图16 例16中多分知识结构(K,)的Hasse图Fig.16 Hasse diagram of polytomous knowledge structure(K,) of example 16

4 结 束 语

本文根据程序性知识域中各项目的操作元逐一设定响应值,得到项目特定的响应值集．基于程序性知识的学习评价[18],通过项目状态转移函数定义项目状态空间,并导出合取的技能映射,证明由技能映射通过合取模型诱导的多分知识结构满足逐项交封闭．最后讨论由合取的技能映射通过合取模型诱导的多分知识结构与所有没达到的项目状态的集合之间的对偶性,并给出诱导多分知识结构的算法步骤．值得注意的是,在本文框架中,仅考虑每个项目的某个特定解法,对于一题多解的情形将在后续的能力模型中考虑．为了保证操作集的有限性,假定各项目的解答或操作是非循环的,所以可在后续研究中考虑对循环解路径的约简．

知识空间的形式背景与形式概念分析[27-28]密切相关,因此可考虑将KST的多分推广与面向属性或面向对象概念格的相关结果[29-32]结合．程序性知识学习与形式概念分析中的概念认知学习有诸多关联,因此,基于程序性知识的学习评价与概念认知学习的交叉融合也是今后研究的方向．