基于程序性知識學(xué)習(xí)的項目狀態(tài)轉(zhuǎn)移函數(shù)與多分知識結(jié)構(gòu)

孫曉燕 李進金,2

知識空間理論(Knowledge Space Theory, KST)源于Birkhoff[1-2]提出的關(guān)于擬序的定理,Doignon等[3-4]和Falmagne等[5]結(jié)合教育心理學(xué)將其發(fā)展完善．基于教育學(xué)和心理學(xué)等理論,KST建立一套反映教育教學(xué)規(guī)律的數(shù)學(xué)理論,為設(shè)計基于計算機網(wǎng)絡(luò)的知識與學(xué)習(xí)評價系統(tǒng)提供有效的科學(xué)方法和數(shù)學(xué)框架[5-7]．

傳統(tǒng)的二分KST假設(shè)個體對項目的回答為正確(用1表示)或錯誤(用0表示),在對知識和學(xué)習(xí)進行評價時具有局限性．針對這一局限性,Schrepp[8]將KST推廣到有兩個以上答案的問題,使用線性有序集評估解決方案的質(zhì)量．Bartl等[9]討論具有分級知識狀態(tài)的知識空間．Stefanutti等[10]提出KST的多分推廣,假設(shè)項目集上的水平集為完備格．在Stefanutti等[10]的基礎(chǔ)上,Heller[11]將擬序知識空間推廣到多分情形,提出多分知識結(jié)構(gòu)的兩個條件,并考慮項目特定的響應(yīng)尺度．

技能代表潛在的認(rèn)知能力,是人們利用知識和經(jīng)驗執(zhí)行某些活動的能力．Falmagne等[5]建立問題和技能之間的聯(lián)系．Doignon[12]將技能映射引入KST．Düntsch等[13]與Korossy[14]分別提出技能函數(shù)和技能空間．近年來,人們越來越重視知識和技能的評估及其程序化應(yīng)用[15-22]．Heller等[15-16]研究分布式技能函數(shù)和知識結(jié)構(gòu)的網(wǎng)格化,提出特殊技能評估的充要條件．程序性知識是解決問題的操作步驟,是關(guān)于“怎么做”的知識．Stefanutti等[17]應(yīng)用KST,為程序性知識的評估提供數(shù)學(xué)概念和正式框架,提出解決問題和模擬學(xué)習(xí)環(huán)境的技能評價．Ste-fanutti[18]將這一工作進一步完善及推廣,證明給定問題空間的所有可能知識狀態(tài)的集合是一個學(xué)習(xí)空間,并給出從問題空間導(dǎo)出學(xué)習(xí)空間的算法．

在程序性知識的評估中,技能是指與項目的解決相關(guān)的解路徑或操作路徑[18]．李金海等[23]提出概念的漸進式認(rèn)知,體現(xiàn)人們認(rèn)識事物是一個從不完全到完全的逐步完善過程,能根據(jù)階段性認(rèn)知及時指導(dǎo)下一步的行動,并逐漸實現(xiàn)完全認(rèn)知．同樣地,對程序性知識的學(xué)習(xí)及其技能的掌握也是漸進式認(rèn)知過程．概念格是形式概念分析理論中用于數(shù)據(jù)分析與處理的核心工具,也是一種挖掘數(shù)據(jù)關(guān)聯(lián)的有效方法[24]．這為進一步研究程序性知識的學(xué)習(xí)與評價提供方法和工具．

1 預(yù)備知識

1.1 技能映射誘導(dǎo)的知識結(jié)構(gòu)

在KST中,通過技能映射將知識域Q中的每個項目與有助于解決這個項目的技能聯(lián)系起來,并從這個關(guān)聯(lián)中推斷知識狀態(tài)．設(shè)非空的知識域Q,非空的技能集S,技能映射是三元組(Q,S,τ),其中,τ∶Q→2S{?},為從Q到S的非空冪集的映射.給定T?S,由T通過析取模型誘導(dǎo)的知識狀態(tài)為

由T通過合取模型誘導(dǎo)的知識狀態(tài)為

取遍T?S,所有通過析取模型誘導(dǎo)的知識狀態(tài)的集合是由τ通過析取模型誘導(dǎo)的知識結(jié)構(gòu)；所有通過合取模型誘導(dǎo)的知識狀態(tài)的集合是由τ通過合取模型誘導(dǎo)的知識結(jié)構(gòu)．由τ通過析取模型誘導(dǎo)的知識結(jié)構(gòu)是知識空間；由τ通過合取模型誘導(dǎo)的知識結(jié)構(gòu)是簡單閉包空間．由同一技能映射通過析取模型和合取模型誘導(dǎo)的知識結(jié)構(gòu)是對偶的．有關(guān)技能映射及其誘導(dǎo)的知識結(jié)構(gòu)的詳細(xì)背景參見文獻[6]和文獻[7]．

1.2 多分知識狀態(tài)

在KST的多分推廣中,知識域Q中的項目的解決質(zhì)量由水平集L中的級別l∈L表示．在Schrepp[8]提出的KST多分推廣中,L為線性有序集．Stefanutti等[10]設(shè)定L為完備格．

設(shè)X為非空集,≤為X上的偏序關(guān)系(即滿足自反性、傳遞性、反對稱性的二元關(guān)系),則稱(X,≤)為偏序集．設(shè)(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,≤)為格．有限格是完備格．有關(guān)格理論的詳細(xì)背景知識參見文獻[2]、文獻[25]和文獻[26].

在Heller[11]提出的KST多分推廣中,個體對知識域Q中各項目的掌握程度用有限的響應(yīng)值集V表示,且設(shè)非空有限響應(yīng)值集V是格,由于V是有限的,所以V是完備格．

多分知識狀態(tài)是Q到V的映射K∶Q→V,表示將Q中每個項目對應(yīng)V中的一個響應(yīng)值．一切這樣的映射的集合記為

1.2.1 多分知識狀態(tài)的表示法

多分知識狀態(tài)有兩種表示形式,分別由Heller[11]和Stefanutti等[10]提出．

集合表示法[11].多分知識狀態(tài)K為Q×V的特定子集,即對于?K∈VQ,K?Q×V,記

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

對于?K∈VQ,規(guī)定

pv∈K?K(p)=v,

則

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

向量表示法[10].在給定的有限知識域Q中,設(shè)|Q|=n,當(dāng)固定各項目的順序時,多分知識狀態(tài)K可簡記為以V中的響應(yīng)值為分量的n維向量．設(shè)Q={q1,q2,…,qn},對于?K∈VQ,記

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

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

例如,設(shè)Q={a,b,c},V={0,1,2},多分知識狀態(tài)K∶Q→V定義為K(a)=1,K(b)=2,K(c)=0,則多分知識狀態(tài)K的集合形式為

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

固定各項目順序為q1=a,q2=b,q3=c,則多分知識狀態(tài)K的向量形式為

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

為了避免記號的混亂,在下述論述與推導(dǎo)中,本文均采用多分知識狀態(tài)的集合表示法,向量表示法僅出現(xiàn)在圖形中．

1.2.2 多分知識狀態(tài)的集合表示法的擴展

設(shè)(V,≤)為偏序集,v∈V,v的下集記為

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

V的所有下集的集合記為

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

則(V,≤)與(Oπ(V),?)同構(gòu)[11]．將多分知識狀態(tài)K∶Q→V擴展到映射K*∶Q→Oπ(V),其中,對于所有的p∈Q,K*(p)=↓K(p),稱K*為K的擴展多分知識狀態(tài)[11]．K*的集合形式為

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

例如,設(shè)Q={a,b,c},V={0,1,2,3},多分知識狀態(tài)K∶Q→V定義為

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

則多分知識狀態(tài)K的集合形式為

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

由于

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

故K的擴展多分知識狀態(tài)為

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

2 程序性知識的項目狀態(tài)轉(zhuǎn)移

函數(shù)

程序性知識是一種經(jīng)過學(xué)習(xí)自動化的關(guān)于行為步驟的知識,如運算法則、解題步驟、操作程序等．在Stefanutti[18]提出的程序性知識的評估中,問題的解決過程被描述為從操作集合中獲取操作序列,操作序列應(yīng)用于問題的某初始狀態(tài),產(chǎn)生一個最終狀態(tài),由此定義問題空間,并誘導(dǎo)知識空間．本節(jié)基于程序性知識的評估框架,通過項目狀態(tài)轉(zhuǎn)移函數(shù)將項目的狀態(tài)與相關(guān)的操作程序?qū)?yīng),將問題空間推廣到多分情形．

2.1 項目特定的響應(yīng)值集

inf(Vi)=∧i(Vi)

稱為Vi的底元,記為丄i；

sup(Vi)=∨i(Vi)

稱為Vi的頂元,記為丅i．特別地,對于??Vi,規(guī)定

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

例1設(shè)Q={q1,q2},

項目q1：已知等腰三角形的腰長為5 cm,底邊長比腰長多1 cm,周長為多少？

項目q2：已知等腰三角形的一條邊長為5 cm,另一條邊長為6 cm,周長為多少？

根據(jù)項目解答過程的類型設(shè)定響應(yīng)值集,兩個項目的響應(yīng)值集的格結(jié)構(gòu)是不同的．

q1的解答：

由于q1的解答過程是層層遞推的,所以設(shè)定V1為有限線性序集,即V1={0,1,2}．V1的底元為丄1=0,V1的頂元為丅1=2．

由于q2的解答中有分類討論,所以V2不是線性序集．設(shè)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設(shè)Q={q1,q2},

項目q1：計算7+4×2；

項目q2：計算7+(4-2)×6．

對于層層遞推的項目解答或操作過程,根據(jù)步驟數(shù)設(shè)定響應(yīng)值集,響應(yīng)尺度可能不同．

q1的解答是層層遞推的,步驟數(shù)為2,所以設(shè)定V1為三分的線性序集,即V1={0,1,2}．

q2的解答是層層遞推的,步驟數(shù)為3,所以設(shè)定V2為四分的線性序集,即V2={0,1,2,3}．

2.2 多分知識結(jié)構(gòu)

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

Ω稱為知識域Q的狀態(tài)集．

其中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續(xù)例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不是多分知識結(jié)構(gòu)．

由

知,K3滿足定義3中條件1)；由

知,K3滿足定義3中條件2)．

如圖2所示,K3是多分知識結(jié)構(gòu)．

圖2 例3中多分知識結(jié)構(gòu)(K3,)的Hasse圖Fig.2 Hasse diagram of polytomous knowledge structure(K3,) in example 3

其中

K1與K2的逐項交是

其中

特別地,對于??K,規(guī)定

例如,在例3中,K1和K2都不是多分知識結(jié)構(gòu),所以K1和K2都不是多分知識空間．K3是多分知識結(jié)構(gòu),由

2.3 項目狀態(tài)轉(zhuǎn)移函數(shù)與項目的相關(guān)技能

設(shè)程序性知識域Q={q1,q2,…,qn},根據(jù)各項目的解答或操作過程設(shè)定響應(yīng)值集．為了保證操作步驟的有限性,下述論述中均假定各項目的解答或操作是非循環(huán)的．?qi∈Q,項目qi的操作集是由其解答或操作過程的每個步驟構(gòu)成的集合,記為Πi．在這里,本文僅考慮每個項目的某個特定的解法,對于一題多解的情形將在能力模型中考慮．

命題1對于?q∈Q,設(shè)q的解答或操作非循環(huán)且步驟數(shù)有限,則項目q的操作集Π是有限集．設(shè)Π={π1,π2,…,πr},根據(jù)每步操作逐一設(shè)定響應(yīng)值,得到項目q的響應(yīng)值集V是有限格．

1)如果項目q的解答或操作是層層遞推的,且步驟數(shù)為r,記第k步操作為πk,k=1,2,…,r,則q的操作集Π={π1,π2,…,πr}．設(shè)項目q的初始狀態(tài)為q0,即q的響應(yīng)值集V的底元為0,根據(jù)每步操作逐一設(shè)定響應(yīng)值,即每步操作產(chǎn)生新的項目狀態(tài),對應(yīng)的響應(yīng)值加1,則項目q的響應(yīng)值集V是有限線性序集,且V={0,1,…,r}．

2)如果q的解答或操作中有n個分支,則V不是線性序集．先按各分支的層層遞推的步驟數(shù)設(shè)定各分支上線性有序的響應(yīng)值集,再將任意k(2≤k≤n)個不可比較的響應(yīng)值的上確界(稱為分支定向并[11])設(shè)為新的響應(yīng)值,規(guī)定：當(dāng)n=2時,設(shè)a1與b1不可比較,a2與b2不可比較,且

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

如果a1≤a2且b1≤b2,則c≤d．當(dāng)n>2時,若?l∈A,恒有m∈B,使得l≤m,則∨A≤∨B．這樣得到的項目q的響應(yīng)值集V是有限格．

例如,例1中的項目q1的解答步驟是層層遞推的,步驟數(shù)為2,所以V1={0,1,2}．項目q2的解答中有分支,2個分支的步驟數(shù)均為1,所以2個分支上的響應(yīng)值集分別{0,a}和{0,b},其中

0≤2a, 0≤2b．

由于a和b不可比較,于是設(shè)響應(yīng)值c=a∨2b,得到項目q2的響應(yīng)值集V2={0,a,b,c}．V2是有限格．

如果項目的解答或操作中有分支,且至少一個分支的步驟數(shù)大于1,則按照命題1中2)的規(guī)定給出各分支定向并的序關(guān)系,如例4所示．

例4設(shè)項目q：解方程|x-3|=3x-5．q的解答中有2個分支,各分支的步驟數(shù)均為2,即

則

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

將{1a,2a,1b,2b}中任意2個不可比較的響應(yīng)值的上確界設(shè)為新的響應(yīng)值,即

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的響應(yīng)值集

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的錯誤狀態(tài)集．

項目qi的單個操作對項目狀態(tài)轉(zhuǎn)移的作用可用定義4中的項目狀態(tài)轉(zhuǎn)移函數(shù)φi表示．

定義4設(shè)程序性知識域Q={q1,q2,…,qn},項目qi的非空有限操作集為Πi,根據(jù)每步操作逐一設(shè)定響應(yīng)值,得到qi的響應(yīng)值集Vi,i=1,2,…,n．記

且響應(yīng)值k保持不變．

例5續(xù)例2,考察q1、q2的項目狀態(tài)轉(zhuǎn)移函數(shù)．假設(shè)學(xué)生已掌握加、減、乘的單獨運算,項目q1、q2是為了考察學(xué)生掌握四則運算順序的情況．項目q1的操作集Π1={π1,π2},項目q2的操作集Π2={π1,π2,π3},其中,π1表示“先乘、除”,π2表示“從左往右依次計算”,π3表示“計算括號內(nèi)的運算”．項目q1、q2的解答是層層遞推的,由命題1中1)知,

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

項目q1的初始狀態(tài)為

q1的項目狀態(tài)轉(zhuǎn)移如圖4所示．由圖4得以下狀態(tài)轉(zhuǎn)移函數(shù)：

q1的終止?fàn)顟B(tài)．

圖4 例2中項目q1的狀態(tài)轉(zhuǎn)移圖Fig.4 State transition diagram of item q1in example 2

q2的項目狀態(tài)轉(zhuǎn)移如圖5所示．q2的初始狀態(tài)為

圖5 例2中項目q2的狀態(tài)轉(zhuǎn)移圖Fig.5 State transition diagram of item q2in example 2

定義5[18]設(shè)非空有限操作集Π,由Π中s個操作元組成的操作序列π1π2…πs∈Πs,稱為Π的一個長度為s的操作序列．具有任意長度的所有操作序列(包括空操作序列ε,即s=0)的集合記為Π∧,即

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

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

對于?qi∈Q,補充定義

注4[18]設(shè)程序性知識域Q={q1,q2,…,qn},任意項目qi的狀態(tài)轉(zhuǎn)移滿足如下性質(zhì)：

記

則

傳遞性具體說明如圖6所示．

圖6 項目狀態(tài)轉(zhuǎn)移的傳遞性Fig.6 Transitivity of item state transitions

定義7設(shè)非空有限操作集Π,操作序列集Π∧,對于?s∈Z+,任意給定長度為s的操作序列π1π2…πs∈Πs,π1π2…πs的子序列是操作序列πiπi+1…πi+t,其中,1≤i≤s,0≤t≤s-i．

定義8設(shè)非空有限操作集Π,操作序列集Π∧,對于任意2個非空操作序列σ1∈Π∧{ε},σ2∈Π∧{ε},規(guī)定σ1≤σ2當(dāng)且僅當(dāng)σ1是σ2的子序列．任意給定非空操作序列σ∈Π∧{ε},σ的所有子序列中關(guān)于“≤”的極小者稱為σ的極小子序列．

命題2設(shè)操作序列

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

其中s∈Z+,則σ的極小子序列為πj,j=1,2,…,s．

例如,設(shè)非空操作序列σ=π1π2π3,σ的所有子序列為π1,π1π2,π1π2π3,π2,π2π3和π3．由于

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

取關(guān)于“≤”的極小者得π1；由于

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

取關(guān)于“≤”的極小者得π2；由于

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

取關(guān)于“≤”的極小者得π3．所以σ的極小子序列為π1、π2和π3．

由定義4可知,項目狀態(tài)轉(zhuǎn)移函數(shù)φi表示項目qi的單個操作對項目狀態(tài)的作用,而由注4可知,項目qi的一個操作序列對給定項目狀態(tài)的作用由定義9中的過程函數(shù)Φi表示．

則

所以空操作序列ε為任意項目的正確操作序列．但是ε未實現(xiàn)狀態(tài)的轉(zhuǎn)移,因此下述分析中均不考慮空操作路徑．

例6續(xù)例5,考察項目q1的正確非空操作路徑．由圖4看出,對于操作序列π1、π2和π1π2,有過程函數(shù)：

推論1對于解答或操作步驟數(shù)較多的復(fù)雜項目q,將q的操作過程劃分為t個正確非空操作序列,以此構(gòu)成q的操作元集

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

根據(jù)每個操作元σk(k=1,2,…,t)逐一設(shè)定響應(yīng)值,得到項目q的響應(yīng)值集V是有限格．

1)如果q的解答或操作是層層遞推的,則q的響應(yīng)值集V為有限線性序集．操作元σk(k=1,2,…,t)作用于qk-1產(chǎn)生新的項目狀態(tài)qk,響應(yīng)值由k-1變?yōu)閗,即φ(qk-1,σk)=qk,稱(qk-1,σk,qk)是以qk-1為初始狀態(tài),σk為操作元,qk為終止?fàn)顟B(tài)的正確單一操作路徑,簡記為qk-1σk,k=1,2,…,t．于是,得到項目q的響應(yīng)值集V={0,1,…,t}．

2)如果q的解答或操作中有分支,對q的操作過程進行不同劃分,可能使V具有不同的格結(jié)構(gòu)．

例7設(shè)項目q：解方程|x2-6|=x2-2x+2．項目q的解答中有2個分支,解答過程如下：

項目q的操作集

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

其中,π1表示“當(dāng)x≥0時,|x|去絕對值”,π2表示“方程移項與合并同類項”,π3表示“解一元一次方程”,π4表示“當(dāng)x≤0時,|x|去絕對值”,π5表示“一元二次多項式的因式分解”,π6表示“解一元二次方程”．

1)將q的操作過程劃分成5個正確非空操作序列,構(gòu)成操作元集

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

根據(jù)各分支上的每個操作元逐一設(shè)定響應(yīng)值,得到2個分支上的響應(yīng)值集{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)的規(guī)定得到{2c,3d,3e,4f,4g,5}的序,于是有限格

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

為q的響應(yīng)值集,如圖7所示．

圖7 例7中響應(yīng)值集V1的Hasse圖Fig.7 Hasse diagram of response value set V1in example 7

2)將q的操作過程劃分成4個正確非空操作序列,構(gòu)成操作元集

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

則q的響應(yīng)值集

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

為有限格,如圖3所示．

3)將q的操作過程劃分成3個正確非空操作序列,構(gòu)成操作元集

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

則

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

為有限格,如圖8所示．

圖8 例7中響應(yīng)值集V3的Hasse圖Fig.8 Hasse diagram of response value set V3in example 7

命題1是推論1的特殊情形,即將每個操作步驟劃分為一個操作元σk=πk,k=1,2,…,r,得到操作元集

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

因此,過程函數(shù)Φi的定義9可做如下推廣．

定義10設(shè)程序性知識域Q={q1,q2,…,qn},qi的操作元集Σi={σ1,σ2,…,σti},

2)任意操作序列

則

如果項目q的解答或操作中有分支,Vq不是線性序集,需要考慮操作組合對項目狀態(tài)的作用．

例8續(xù)例7．記

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

取q的操作元集Σ={σ1,σ2,σ3},由例7中3)可知,q的響應(yīng)值集

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

q的項目狀態(tài)轉(zhuǎn)移圖如圖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)的項目狀態(tài)轉(zhuǎn)移圖Fig.9 Item state transition diagram in 3) of example 7

定義12設(shè)程序性知識域Q={q1,q2,…,qn},項目qi的操作元集Σi={σ1,σ2,…,σti},響應(yīng)值集Vi為有限格,i=1,2,…,n．對于?qi∈Q,qi的操作程序是由其正確非空操作序列或正確非空操作組合構(gòu)成的序列δ=ω1ω2…ωl,其中

則

例9設(shè)項目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的響應(yīng)值集V={0,1,2a,2b,3},q的項目狀態(tài)轉(zhuǎn)移圖如圖10所示．

圖10 例9的項目狀態(tài)轉(zhuǎn)移圖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設(shè)程序性知識域Q={q1,q2,…,qn},項目qi的操作元集Σi={σ1,σ2,…,σti},響應(yīng)值集Vi是有限格,i=1,2,…,n．在合取模型中,對于?qi∈Q,項目qi的一個正確操作路徑的極小子路徑稱為qi的一個相關(guān)技能．qi的所有相關(guān)技能的集合Si稱為qi的技能集,i=1,2,…,n．

由于項目qi的任意一個正確操作路徑的極小子路徑為Σi中的構(gòu)成該路徑的操作元對應(yīng)的正確單一操作路徑,所以,qi的技能集為Σi中的各操作元對應(yīng)的正確單一操作路徑的集合．

例10續(xù)例8,考察項目q的技能集．記

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

q的操作元集Σ={σ1,σ2,σ3},響應(yīng)值集

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設(shè)程序性知識域Q={q1,q2,…,qn},項目qi的操作元集Σi={σ1,σ2,…,σti},響應(yīng)值集Vi是有限格,i=1,2,…,n．記

對于?σ∈Σ,

表示以σ為操作元的正確單一操作路徑的等價類,知識域Q的技能集為

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

例11續(xù)例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 基于程序性知識的多分知識

結(jié)構(gòu)

3.1 由操作路徑導(dǎo)出的合取的技能映射

定義16設(shè)程序性知識域Q={q1,q2,…,qn}

記

記

則

另一方面,?i∈H,記

則

由

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

即

從而

因此

例13續(xù)例12．

同理可得

定義17設(shè)程序性知識域Q={q1,q2,…,qn}

命題3設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?},則對于?qi∈Q,τ滿足如下2個條件：

2)差異性.?v∈Vi{0},w∈Vi{0},v與w不可比較,則

3.2 由合取的技能映射誘導(dǎo)的多分知識結(jié)構(gòu)

定義18設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．給定技能狀態(tài)T?S,T表示個體掌握的技能的集合,由T通過合取模型誘導(dǎo)的多分知識狀態(tài)為

定理2設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．取遍所有的技能狀態(tài)T?S,所有通過合取模型誘導(dǎo)的多分知識狀態(tài)的集合

是多分知識結(jié)構(gòu)．

由于

所以,K滿足多分知識結(jié)構(gòu)的定義3中2)．綜上所述,取遍所有的T?S,所有通過合取模型誘導(dǎo)的多分知識狀態(tài)的集合K為多分知識結(jié)構(gòu)．

定義19設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．取遍所有的技能狀態(tài)T?S,所有通過合取模型誘導(dǎo)的多分知識狀態(tài)的集合K稱為由技能映射τ通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)．

例14續(xù)例13．

合取的技能映射τ定義為

取遍所有的技能狀態(tài)T?S,得到如下通過合取模型誘導(dǎo)的多分知識狀態(tài)：

所以,由τ通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)為

圖11 例14中多分知識結(jié)構(gòu)(K,)的Hasse圖Fig.11 Hasse diagram of polytomous knowledge structure(K,) in example 14

注5命題3中1)對于通過合取模型誘導(dǎo)多分知識結(jié)構(gòu)是必要的．如果技能映射τ不滿足該條件,則由τ通過合取模型誘導(dǎo)的多分知識狀態(tài)的集合可能不滿足定義3中2)．

例如,在例14中,若定義技能映射τ′為

由于

所以K′不滿足定義3中2),K′不是多分知識結(jié)構(gòu)．

根據(jù)項目qi的操作元集Σi逐一設(shè)定響應(yīng)值,得到qi的響應(yīng)值集Vi不一定是線性有序集．

例15續(xù)例1．

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

記

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

則

由項目狀態(tài)轉(zhuǎn)移(圖12)可得

則S={s1,s2,s3}．由操作路徑導(dǎo)出的合取的技能映射τ為

圖12 例1的項目狀態(tài)轉(zhuǎn)移圖Fig.12 Item state transition diagram of example 1

取遍所有的技能狀態(tài)T?S,得到由τ通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)為

圖13 例15中多分知識結(jié)構(gòu)(K,)的Hasse圖Fig.13 Hasse diagram of polytomous knowledge structure(K,) in example 15

注6命題3中2)對于通過合取模型誘導(dǎo)多分知識結(jié)構(gòu)是必要的．如果技能映射τ不滿足該條件,則由τ通過合取模型誘導(dǎo)的多分知識狀態(tài)的集合可能不滿足定義3中2)．

例如,在例15中,若定義技能映射τ′為

其中,a與b不可比較,

但是

不滿足命題3中2)．由τ′通過合取模型誘導(dǎo)的所有多分知識狀態(tài)的集合為

由于

所以K′不滿足定義3中2),K′不是多分知識結(jié)構(gòu)．

命題5設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．給定技能狀態(tài)T?S,T表示個體掌握的技能的集合,由T誘導(dǎo)的個體能達到的項目狀態(tài)的集合記為

記

由命題5和定義18可得推論2．

推論2設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．給定技能狀態(tài)T?S,T表示個體掌握技能的集合,由T通過合取模型誘導(dǎo)的多分知識狀態(tài)為

證明對于?K1∈K,K2∈K,其中Ki是由技能狀態(tài)Ti通過合取模型誘導(dǎo)的多分知識狀態(tài),即

記

記

因為

3.3 對偶性

推論3設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．給定技能狀態(tài)T?S,T表示個體沒有掌握技能的集合,由T誘導(dǎo)的個體沒達到的項目狀態(tài)的集合記為

則

例如,在例14中,取個體沒有掌握技能的集合T={s2},則

記

則

推論4設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．T?S表示個體沒有掌握技能的集合．取遍T?S,由τ誘導(dǎo)的個體沒達到的項目狀態(tài)的集合為

L={Lτ(T)|?T?S}．

L滿足集合并∪-封閉．

例如,在例14中,由τ通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)為

則K的擴展多分知識結(jié)構(gòu)為

所以,由推論3可知,取遍個體沒有掌握的技能狀態(tài),所有由τ誘導(dǎo)的個體沒達到的項目狀態(tài)的集合為

如圖14所示,由于

同理可得,

所以L滿足集合并∪-封閉．但是,因為

所以L不滿足集合交∩-封閉．

圖14 例14中多分知識結(jié)構(gòu)的對偶(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之間的二元關(guān)系,若(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

設(shè)合取的技能映射(Ω+,S,τ),其中τ∶Ω+→2S{?}．將Ω+視為對象集,S視為屬性集,I?Ω+×S是Ω+和S之間的二元關(guān)系,規(guī)定

又由推論2可知,由τ通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)為

3.4 從狀態(tài)空間導(dǎo)出多分知識結(jié)構(gòu)的算法

n)為起點的所有操作路徑導(dǎo)出合取的技

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

初始設(shè)置.由qi的所有正確單一操作路徑構(gòu)成隊列

并將Wi中任意有限條起點相同的路徑的組合添加到Wi中,得

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

的對偶性得到由τ通過合取模型誘導(dǎo)的多

分知識結(jié)構(gòu)K．

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

step 2 取個體沒有掌握的技能狀態(tài)Ti={si},由(Ω+,S,I)導(dǎo)出Ti誘導(dǎo)的沒達到的項目狀態(tài)Lτ(Ti),i=1,2,…,m．由{Lτ(T1),Lτ(T2),…,Lτ(Tm)}取集合并∪-封閉,張成所有由τ誘導(dǎo)的個體沒達到的項目狀態(tài)的集合L．

算法1采用起點固定的廣度優(yōu)先路徑搜索算法(Breadth First Search, BFS)．這是基于隊列這種數(shù)據(jù)結(jié)構(gòu)的搜索方式,特點是由每個狀態(tài)擴展出許多狀態(tài),然后再以此擴展,直到處理完畢隊列中所有狀態(tài)．算法1中step 1的時間復(fù)雜度為O(|S|+|Ω+|)．算法2中step 2的時間復(fù)雜度為O(|Ω+|·|S|)．在算法2中,可考慮結(jié)合形式背景或概念格中的已有結(jié)果,如對象約簡或?qū)傩约s簡,從而去除計算中的冗余部分,達到算法的簡化．

例16設(shè)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},

記

項目狀態(tài)轉(zhuǎn)移如圖15所示．

圖15 例16的項目狀態(tài)轉(zhuǎn)移圖Fig.15 Item state transition of example 16

由算法1中step 1可得

再由算法1中step 2可得,導(dǎo)出的合取的技能映射τ為

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

由算法2得到由形式背景(Ω++,S,I)導(dǎo)出的個體沒達到的項目狀態(tài)的集合L,從而得到由τ通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)K．

1)在形式背景(Ω++,S,I)中,規(guī)定

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

2)由表2導(dǎo)出個體沒達到的項目狀態(tài).取

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

則

由{Lτ(T1),Lτ(T2),Lτ(T3),Lτ(T4)}取∪-封閉張成τ誘導(dǎo)的個體沒達到的項目狀態(tài)的集合:

3)取L的對偶,即

得到τ通過合取模型誘導(dǎo)的Ω++上的擴展多分知識結(jié)構(gòu):

圖16 例16中多分知識結(jié)構(gòu)(K,)的Hasse圖Fig.16 Hasse diagram of polytomous knowledge structure(K,) of example 16

4 結(jié) 束 語

本文根據(jù)程序性知識域中各項目的操作元逐一設(shè)定響應(yīng)值,得到項目特定的響應(yīng)值集．基于程序性知識的學(xué)習(xí)評價[18],通過項目狀態(tài)轉(zhuǎn)移函數(shù)定義項目狀態(tài)空間,并導(dǎo)出合取的技能映射,證明由技能映射通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)滿足逐項交封閉．最后討論由合取的技能映射通過合取模型誘導(dǎo)的多分知識結(jié)構(gòu)與所有沒達到的項目狀態(tài)的集合之間的對偶性,并給出誘導(dǎo)多分知識結(jié)構(gòu)的算法步驟．值得注意的是,在本文框架中,僅考慮每個項目的某個特定解法,對于一題多解的情形將在后續(xù)的能力模型中考慮．為了保證操作集的有限性,假定各項目的解答或操作是非循環(huán)的,所以可在后續(xù)研究中考慮對循環(huán)解路徑的約簡．

知識空間的形式背景與形式概念分析[27-28]密切相關(guān),因此可考慮將KST的多分推廣與面向?qū)傩曰蛎嫦驅(qū)ο蟾拍罡竦南嚓P(guān)結(jié)果[29-32]結(jié)合．程序性知識學(xué)習(xí)與形式概念分析中的概念認(rèn)知學(xué)習(xí)有諸多關(guān)聯(lián),因此,基于程序性知識的學(xué)習(xí)評價與概念認(rèn)知學(xué)習(xí)的交叉融合也是今后研究的方向．