黃宏濤 梁存良 李大鵬 葉海智

人工智能和認知科學等領(lǐng)域的研究成果[1?3]正在不斷促進教學方式向更加智能、高效和個性化的方向發(fā)展[4?6].個性化教學的核心問題是通過計算機程序?qū)Ρ辉嚨闹R結(jié)構(gòu)[7]和能力水平進行測試,并根據(jù)測試結(jié)果開展資源推送和學習路徑規(guī)劃等計算機輔助教學活動.Tatsuoka[8]提出的規(guī)則空間模型(Rule space model,RSM)是對學生知識狀態(tài)進行認知診斷的有效方法之一.RSM 的主要特點是假設(shè)學生在解題過程中的錯誤反應是不確定的(可變的).因此,RSM 能夠有效處理學生作答過程中的可變性,更為準確地把學生實際反應模式轉(zhuǎn)換為認知過程與技能的掌握概率,從而實現(xiàn)對被試認知結(jié)構(gòu)的診斷[9].

RSM 在智能導師系統(tǒng)[10?12]和個性化學習系統(tǒng)[13?15]等領(lǐng)域中有著成功的應用.Im 等[16]使用RSM 對學生的統(tǒng)計假設(shè)檢驗知識和技能進行了診斷,并能夠根據(jù)診斷結(jié)果對學生進行教學指導.這種方法同樣適用于在線教學或計算機輔助學習.Xin等[17]使用RSM 對單一分數(shù)在三個認知屬性上進行分類,并對教師水平和學生認知技能間的關(guān)系進行分析.Badaracco 等[18]在計算機自適應診斷(Computerized adaptive test,CAT)中引入模糊語言建模的專家知識用于支持測試項目選擇,提高了RSM診斷結(jié)果的準確性.Qin 等[19]提出對Q 矩陣的推理和有效性檢驗的改進算法,能夠產(chǎn)生更合理的Q矩陣規(guī)范,進一步改善了RSM 診斷結(jié)果的有效性.

這些基于RSM 的方法雖然能夠?qū)Ρ辉囌J知結(jié)構(gòu)進行有效、準確的診斷,但規(guī)則空間構(gòu)造需要全局知識依賴關(guān)系的支持,導致時間代價較高,不適合用于日常教學中對學生進行小規(guī)模的單元診斷.而這種小規(guī)模的實時診斷是智能導師系統(tǒng)和個性化學習系統(tǒng)進行知識結(jié)構(gòu)推理的關(guān)鍵環(huán)節(jié).為了提高RSM 的靈活性和可擴展性,文獻[20?21]提出了一種使用BP 神經(jīng)網(wǎng)絡(luò)進行認知診斷建模的方法,使用期望反應模式對神經(jīng)網(wǎng)絡(luò)進行訓練,然后使用訓練后的神經(jīng)網(wǎng)絡(luò)對被試觀察反應模式進行識別,克服了RSM 模型進行參數(shù)估計時對大樣本數(shù)據(jù)的依賴,使基于RSM 的計算機自適應測驗應用于課堂教學成為可能.然而,在小規(guī)模測試的前提下,屬性層級關(guān)系約束下的測試項目數(shù)量有限,基于神經(jīng)網(wǎng)絡(luò)的RSM 能夠使用的期望反應模式規(guī)模也較小,無法保障總是獲得理想的訓練誤差.

此外,基于神經(jīng)網(wǎng)絡(luò)的RSM 雖然能夠在一定程度上降低規(guī)則空間構(gòu)造代價,但它沒有考慮領(lǐng)域內(nèi)所有知識之間的全局依賴關(guān)系.而在實際教學活動中,領(lǐng)域內(nèi)知識間的依賴關(guān)系是客觀存在的,使用依賴保持子圖(Dependency preserving subgraph,DPS)[22]構(gòu)造規(guī)則空間的方式能夠在認知診斷活動涉及的測試項目確定后,根據(jù)領(lǐng)域知識圖中的依賴關(guān)系生成知識圖的相關(guān)子圖,再由子圖出發(fā)構(gòu)造規(guī)則空間,這種方法可以顯著降低規(guī)則空間規(guī)模以及預設(shè)知識圖時的人工參與度.但是,當領(lǐng)域知識圖中依賴關(guān)系較為復雜時,DPS 生成相關(guān)子圖的過程中會引入較多和測試項目無關(guān)的屬性,容易導致相關(guān)子圖規(guī)模過大.相對于DPS 方法,使用頂點導出子圖(Vertex derived subgraph,VDS)[23]構(gòu)造規(guī)則空間時不會引入與測試項目無關(guān)的屬性.這種特性能夠保證總是獲得規(guī)模足夠小的規(guī)則空間,從而提高RSM 的可擴展性,但其代價是損失了部分領(lǐng)域知識圖中的傳遞依賴關(guān)系,會導致理想屬性模式集中大量不合理屬性模式無法被過濾,從而影響認知診斷的效率和診斷結(jié)果的準確率.

為了在保障診斷結(jié)果準確率的前提下盡可能提高RSM 方法的可擴展性,使其能夠適用于小規(guī)模的、及時的課堂教學認知診斷,本文提出一種基于近似子圖的RSM 規(guī)則空間生成方法.該方法借鑒了文獻[24]中通過構(gòu)建守恒依賴圖計算質(zhì)量守恒集的方法,在守恒依賴圖構(gòu)建過程中忽略了狀態(tài)空間中的反應狀態(tài),有效縮減了待檢查候選集的數(shù)量,達到了提高守恒集計算效率的目的;同時通過抽取反應狀態(tài)和已連接組件間的依賴關(guān)系,保持了守恒狀態(tài)間的依賴關(guān)系.受文獻[24]的啟發(fā),本文通過構(gòu)建近似子圖實現(xiàn)對規(guī)則空間的壓縮,近似子圖的構(gòu)建不需要根據(jù)測試項目涉及的屬性集合從領(lǐng)域知識圖中計算先序依賴關(guān)系的傳遞子圖,而是通過忽略先序依賴關(guān)系中與測試項目無關(guān)的屬性來生成領(lǐng)域知識圖的近似子圖.生成的近似子圖能夠通過構(gòu)建虛擬邊模擬領(lǐng)域知識圖上的依賴關(guān)系,從而在不影響生成補救教學路徑的前提下顯著降低規(guī)則空間規(guī)模量級,進而提高RSM 的可擴展性.

1 相關(guān)概念

在介紹近似子圖生成算法前先給出屬性、領(lǐng)域知識圖、初始路徑、路徑片段和劃分標準的概念.

屬性是對程序性知識或陳述性知識的描述,是構(gòu)成認知結(jié)構(gòu)的基本元素,直接反映了被試的認知技能.屬性及其內(nèi)部依賴關(guān)系是構(gòu)成規(guī)則空間的基礎(chǔ).本文使用領(lǐng)域知識圖[25]表示屬性及其聯(lián)系.

定義1.四元組G=(V,E,I)為一個領(lǐng)域知識圖,其中

1)頂點集合V是屬性的有限非空集合;

2)E ?V×V為邊的有限集合,(v1,v2)∈E表示知識點v2依賴于v1,其中v1∈V,v2∈V;

3)I ?V為初始狀態(tài)集合,對任意vi ∈V,vi∈I當且僅當不存在vj ∈V使得(vj,vi)∈E,ij.

頂點集合V為規(guī)則空間模型中的屬性集合,邊集E是定義在屬性集上的二元關(guān)系,反映了屬性間的先序依賴關(guān)系.因此,E是定義在V上的偏序關(guān)系,即E是自反、反對稱和傳遞的.在忽略自環(huán)的情況下可知G為有向無環(huán)圖(Directed acyclic graph,DAG).

定義2.稱領(lǐng)域知識圖G上的頂點序列p=v1v2···vn為連接v1和vn的路徑,當且僅當對任意vi和vi+1存在(vi,vi+1)∈E,其中,1≤i

路徑是先序依賴關(guān)系下的屬性序列,是合理的認知技能學習序列.在圖1 所示的領(lǐng)域知識圖G中,頂點序列“角、三角形、三角形底”是連接“角”和“三角形底”的路徑,它說明如果屬性“三角形底”已經(jīng)被掌握,則屬性“三角形”必然已經(jīng)被掌握;同理,屬性“角”也已經(jīng)被掌握.而頂點序列“相交線、角、三角形、三角形底”是初始路徑,它是可行的認知技能序列,是理想屬性模式的構(gòu)成元素.

圖1 領(lǐng)域知識圖GFig.1 Domain knowledge graph

定理1.對于領(lǐng)域知識圖G=(V,E,I)上的任意點v,G上存在初始路徑p使得p經(jīng)過v.

證明.如果v不依賴于任何頂點,由定義1 知v ∈I,于是由定義2 可得p=v為初始路徑;否則G上存在頂點v1使得v依賴于v1,則p=v1v為經(jīng)過v的路徑,如果v1不依賴于任何頂點,同理可得p=v1v為初始路徑;否則G上存在頂點v2使得v1依賴于v2,此時,如果v2不依賴于任何頂點,則p=v2v1v為初始路徑.

進行歸納可得,對于經(jīng)過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上必然存在環(huán)路,這與G為DAG 圖矛盾.于是可得G上不存在頂點vn使得vn?1依賴于vn.

綜上所述,對于領(lǐng)域知識圖G上的任意點v,G上必然存在初始路徑p使得p經(jīng)過v且1≤|p|≤|V|.

定義3.va和vb為領(lǐng)域知識圖G上的兩個頂點,如果G中存在頂點序列v0v1···vj,使得p=vav0v1···vjvb為G上的路徑,則G上存在從va到vb的路徑片段,此時va和vb是連通的,其中,a,b,j為自然數(shù).

頂點間的連通性反映了屬性間的先序依賴關(guān)系.為了從領(lǐng)域知識圖中選擇部分內(nèi)容開展小規(guī)模測試,需要根據(jù)測試涉及的屬性及其依賴關(guān)系從領(lǐng)域知識圖中劃分出相關(guān)子圖,從而達到生成測試所需的小規(guī)模規(guī)則空間的目的.下面給出子圖劃分標準的定義.

定義4.Q為領(lǐng)域項目集合,Qsub?Q為測試項目集,對任意q ∈Qsub,k(q)?V表示項目q涉及的屬性集合,稱

為子圖劃分標準,其中函數(shù)k的定義域為測試項目集Qsub,函數(shù)K的定義域為領(lǐng)域項目集Q的冪集,值域為領(lǐng)域知識圖頂點集V的冪集.

子圖劃分標準K(Qsub)直接決定了規(guī)則空間的規(guī)模.由于屬性模式依賴于屬性間的先序關(guān)系,所以在進行小規(guī)模測試時需要從領(lǐng)域知識圖中抽取測試屬性集及其關(guān)系,也就是從子圖劃分標準出發(fā)計算領(lǐng)域知識圖的相關(guān)子圖.

2 基于近似子圖的規(guī)則空間生成算法

2.1 近似子圖生成

為了盡可能壓縮規(guī)則空間的規(guī)模,同時避免直接計算領(lǐng)域知識圖導出子圖出現(xiàn)孤立點,本文通過計算領(lǐng)域知識圖的近似子圖生成規(guī)則空間.

定義5.Gsub=(Vsub,Esub,Isub)為G=(V,E,I)關(guān)于子圖劃分標準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 所示的領(lǐng)域知識圖G為例介紹近似子圖計算過程.如果測試項目集Qsub共有5 個項目,這些項目及其對應的屬性集合如表1 所示.

圖2 G 關(guān)于K(Qsub)的近似子圖Fig.2 The approximate subgraph of G on division criteria K(Qsub)

表1 測試項目及其對應的屬性Table 1 Test item and its attributes

根據(jù)定義4,子圖劃分標準K(Qsub)={相交線,三角形,三角形高,三角形面積}.由定義5 條件1)得,邊(三角形,三角形高)、(三角形高,三角形面積)屬于Esub,如圖2(a)所示;由條件2)可知,頂點“三角形”、“三角形高”、“三角形面積”屬于Vsub,如圖2(b)所示;由于G上存在由頂點“相交線”到頂點“三角形高”、由頂點“相交線”到頂點“三角形”以及由頂點“三角形”到頂點“三角形面積”的路徑片段,故根據(jù)條件3)可得,邊(相交線,三角形高)、(相交線,三角形)、(三角形,三角形面積)屬于Esub,雖然也存在“相交線”到“三角形面積”的路徑片段,但這條路徑需要經(jīng)過“三角形”或“三角形高”,不符合條件3)的要求,因此忽略該近似邊,圖2(c)給出了添加近似邊后的結(jié)果;再次應用條件2)可得,Vsub={相交線,三角形,三角形高,三角形面積},如圖2(d)所示;再次應用條件3)時,(K(Qsub)?Vsub)=?,所以Esub不再變化,近似子圖求解結(jié)束,最后由條件5)可得,初始狀態(tài)集合Isub={相交線}.于是可得G=(V,E,I)關(guān)于子圖劃分標準K(Qsub)的近似子圖Gsub=(Vsub,Esub,Isub),如圖2(d)所示.

Gsub對應于規(guī)則空間模型的鄰接矩陣,由鄰接矩陣可計算出可達矩陣.可達矩陣反映了屬性間的間接依賴關(guān)系,即Gsub上頂點間的可達關(guān)系.本文通過對近似子圖Gsub進行可達性分析,計算鄰接矩陣的可達矩陣,其時間復雜度為O(ne),其中,n=|Vsub|,e=|Esub|.

2.2 期望反應模式構(gòu)建

構(gòu)建規(guī)則空間的目的是通過模式匹配建立觀察反應模式與期望反應模式之間的映射,進而通過期望反應模式確定理想屬性模式.因此,構(gòu)建規(guī)則空間需要由近似子圖確定理想屬性模式、期望反應模式及兩者間的關(guān)系.

屬性模式是一組認知技能的集合,即知識狀態(tài).為了對被試的認識結(jié)構(gòu)進行分類,需要由Gsub的頂點集Vsub生成對應的屬性模式.理論上屬性模式集合是屬性集合的冪集.下面給出屬性模式[3]的形式定義.

定義6.屬性模式是一個有序n元布爾序列m=b1b2···bn,其中n=|Vsub|,bi為布爾值,表示對應屬性是否被掌握,bi為1 表示屬性i成立,0 表示不成立,1≤i≤n.

圖2 所示實例中,Vsub包含“相交線,三角形,三角形高,三角形面積”4 個屬性,可能的屬性模式有16 種.考慮到屬性之間的偏序關(guān)系,這16 種可能屬性模式中有一部分是不合理的,例如屬性模式(0100),它反映了被試掌握了屬性“三角形”卻未掌握屬性“相交線”,這種知識狀態(tài)是不可接受的.而屬性模式(1100)是合理的,它反映了被試同時掌握了屬性“相交線”和屬性“三角形”.這種合理的屬性模式為理想屬性模式[5],它是可行的認知技能序列.

定義7.令M為理想屬性模式集合,L:M →為標記函數(shù),任意m ∈M為理想屬性模式當且僅當

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

上述定義給出了判斷一個屬性模式是否合理的標準,根據(jù)定義7 可得Gsub生成的理想屬性模式集合M={0000,1000,1100,1010,1110,1111}.表2給出了理想屬性模式及其標記的對應關(guān)系.

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

表2 列出的屬性模式反映了被試的潛在認知結(jié)構(gòu).認識診斷的最終目標是建立觀察反應模式和理想屬性模式之間的映射,從而產(chǎn)生對被試的認知診斷.觀察反應模式是指被試對測試項目的實際反應結(jié)果,是在有噪音(存在失誤)情況下得出的測試結(jié)果序列.認知診斷主要任務是在規(guī)則空間中對觀察反應模式進行模式識別,從而過濾噪音干擾并找出對應的期望反應模式(無噪音干擾下的反應模式),最后由期望反應模式獲取理想屬性模式映射,從而給出認知診斷結(jié)果.因此,需要建立理想屬性模式與期望反應模式間的對應關(guān)系.下面給出期望反應模式的定義.

定義8.對于給定測試項目集Qsub,稱n元布爾序列r=R(m)=B(q1|m)B(q2|m)···B(qn|m)為一個期望反應模式,其中k(qi)?L(m)成立時,B(qi|m)=1,否則B(qi|m)=0,n=|Qsub|,qi ∈Qsub,m ∈M,0≤i≤n,R(M)表示期望反應模式集合.

由定義8 可知,期望反應模式是理想屬性模式的函數(shù).表3 列出了期望反應模式與理想屬性模式間的映射關(guān)系.第1 行中R(M)=00000 表示被試在5 個項目上的反應結(jié)果全部錯誤,對應的理想屬性模式m=0000 說明4 個屬性都沒有掌握,所以相應的L(m)為空集.同理,第4 行R(m)=11101說明被試掌握了項目q1,q2,q3和q5對應的屬性,所以有m=1110 和L(m)={相交線,三角形,三角形高}.

表3 理想屬性模式與期望反應模式的對應關(guān)系Table 3 Expected response pattern corresponding to ideal attribute pattern

2.3 規(guī)則空間生成

規(guī)則空間是定義在觀察反映模式和期望反應模式上的關(guān)系,是兩者笛卡爾積的子集.構(gòu)建規(guī)則空間的核心問題是由理想屬性模式構(gòu)建期望反映模式,從而確定規(guī)則空間中的純規(guī)則點,即分類中心.在計算分類中心之前,需要先由領(lǐng)域知識圖和測試項目集計算近似子圖(Approximate subgraph,AS),算法1 描述了AS 的計算過程.

算法1.AS 算法

輸入.領(lǐng)域知識圖G=(V,E,I)和測試項目集Qsub?Q

輸出.近似子圖Gsub=(Vsub,Esub,Isub)

AS 算法1～4 行由測試項目集Qsub生成子圖劃分標準K(Qsub),第6 行的是Vsub在K(Qsub)下的補集,初始為K(Qsub).第7～18 行的主要功能是生成近似子圖中的直接依賴關(guān)系,9～14行對中的每個頂點的直接關(guān)聯(lián)關(guān)系進行處理,根據(jù)頂點的直接關(guān)聯(lián)關(guān)系生成近似子圖中相應的邊(圖2(a)).15～17 行根據(jù)頂點是否存在直接關(guān)聯(lián)關(guān)系決定是否把該頂點加入近似子圖頂點集(圖2(b)).20～24 行的功能是判斷是否存在從Vsub中的頂點vi到中頂點vj的路徑片段,如果存在,說明vj間接先行依賴于vi,這是一種近似依賴關(guān)系,所以在近似子圖中建立vi到vj的邊,同時把vj加入近似子圖的頂點集(圖2(c),2(d)).

近似子圖能夠模擬子圖結(jié)點在領(lǐng)域知識圖上的依賴關(guān)系,排除屬性模式中的不合理因素,縮減合理屬性模式集規(guī)模.算法2 給出了由近似子圖計算理想屬性模式(AS based ideal attribute mode,ASIAM)的過程.

算法2.ASIAM 算法

輸入.近似子圖Gsub=Vsub,Esub,Isub

輸出.理想屬性模式集合M

算法2 的核心思想是按照定義7 給出的標準,從近似子圖的初始節(jié)點開始,依次尋找頂點個數(shù)為1～|Vsub|的初始可達子圖的過程(4～17 行).這里初始可達子圖是近似子圖的子圖,且初始可達子圖中的任意頂點至少屬于一條初始路徑.算法第1 行的Γ1用于存儲上次迭代過程中找到的理想屬性模式,Γ2存儲當前迭代找到的理想屬性模式.由于可能有多個初始結(jié)點,為了把搜索問題簡化為單源路徑搜索,設(shè)置初始頂點E,使其能夠到達Isub中的所有頂點.5～15 行依次從上一輪迭代產(chǎn)生的理想屬性模式中的頂點出發(fā)展開搜索,如果能夠找到1 條新邊且能夠引入1 個新頂點,則產(chǎn)生一個長度增1 的理想屬性模式(8～13 行),將其存入Γ2(第9 行).一輪迭代結(jié)束,產(chǎn)生一組長度增1 的理想屬性模式.算法2 最后返回集合M.注意到M中的元素實際上是理想屬性模式對應的標簽集合,可由定義7 直接導出理想屬性模式.

期望反映模式和理想屬性模式是一一對應的,所以可以根據(jù)定義8 直接導出M對應的期望反應模式集合,從而生成規(guī)則空間中的純規(guī)則點,完成規(guī)則空間的構(gòu)建.由于規(guī)則空間模型的重要假設(shè)是被試在進行測試時會出現(xiàn)失誤,造成觀察反應模式與期望反應模式間的誤差.因此,如何把被試的觀察反應模式映射到期望反應模式是進行認知診斷的關(guān)鍵.可以通過計算被試實際規(guī)則點和純規(guī)則點的馬氏距離進行模式識別,得出學生對知識的掌握情況,詳細計算過程見文獻[8,16?17].

2.4 算法分析

1)規(guī)則空間壓縮能力

壓縮規(guī)則空間的實質(zhì)是縮減理想屬性模式集的規(guī)模.當測試項目集確定后,屬性模式涉及的屬性集合也就確定了.為了縮減理想屬性模式集的規(guī)模,需要從領(lǐng)域知識圖中提取屬性間的依賴關(guān)系.如果通過計算領(lǐng)域知識圖的依賴保持子圖提取屬性依賴關(guān)系,會引入和測試項目集無關(guān)的額外屬性,導致理想屬性模式集的規(guī)模呈指數(shù)級增長,如圖3(a)所示.直接計算頂點導出子圖能夠避免引入額外屬性,其對傳遞依賴關(guān)系的忽略會導致理想屬性模式集規(guī)模過大,因為大量不合理屬性模式無法被過濾,如圖3(b)所示.本文通過計算領(lǐng)域知識圖關(guān)于測試項目集的近似子圖(Approximate subgraph,AS)生成屬性間的依賴關(guān)系,相對于VDS,計算近似子圖能夠在不引入額外屬性的前提下進一步壓縮理想屬性模式集的規(guī)模,從而達到壓縮狀態(tài)空間規(guī)模的目的.以第3.1 節(jié)給出的測試項目集為例,圖3(a)是由測試項目集計算出的依賴保持子圖,圖3(b)為頂點導出子圖,圖3(c)為由測試項目集計算出的近似子圖.

圖3 測試項目集的導出子圖Fig.3 Subgraphs exported from test item set

由圖3 知,為了避免在傳遞依賴子圖中引入額外頂點,頂點導出子圖只保留了領(lǐng)域知識圖中與測試項目直接相關(guān)的依賴關(guān)系,忽略了知識圖中的間接依賴關(guān)系.事實上,在領(lǐng)域知識圖上存在“相交線”通過“垂線”到“三角形高”路徑、“相交線”通過“角”到“三角形”的路徑以及“三角形”通過“三角形底”到“三角形面積”的路徑,也即“相交線”和“垂線”是“三角形高”的先行知識點、“相交線”和“角”是“三角形”的先行知識點以及“三角形”和“三角形底”是“三角形面積”的先行知識點.頂點導出子圖對這種間接依賴關(guān)系的忽略是不合理的,同時也會導致理想屬性模式集規(guī)模膨脹,表4 給出了由VDS 導出的理想屬性模式集,其規(guī)模為8.而近似子圖保持了“相交線”到“三角形高”、“相交線”到“三角形”以及“三角形”到“三角形面積”的傳遞依賴關(guān)系,雖然還存在“相交線”到“三角形面積”的間接依賴關(guān)系,但需要通過“三角形高”或“三角形”實現(xiàn),根據(jù)定義5 條件3)近似子圖中不建立該依賴關(guān)系.近似子圖能夠在不引入額外屬性的前提下保持屬性間的間接依賴關(guān)系,從而實現(xiàn)對理想屬性模式規(guī)模的進一步壓縮.本例中由近似子圖導出的理想屬性模式規(guī)模僅為5,如表2 所示.

通過上述實例可以看出,近似子圖能夠顯著縮減理想屬性模式集的規(guī)模,從而實現(xiàn)對規(guī)則空間的壓縮.相對于VDS 而言,這種壓縮能力是通過構(gòu)造領(lǐng)域知識圖中不存在的虛擬邊實現(xiàn)的.

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

2)依賴關(guān)系保持能力

近似子圖中引入的虛擬邊描述了頂點間的間接依賴關(guān)系,目的是使近似子圖盡可能保持領(lǐng)域知識圖中知識間的依賴關(guān)系.近似子圖中引入的這些新的依賴關(guān)系是否能夠保持領(lǐng)域知識圖上的依賴關(guān)系是影響認知診斷結(jié)果正確性的關(guān)鍵因素.為了證明近似子圖依賴關(guān)系保持能力,下面先參考文獻[26]給出的DAG 圖間模擬關(guān)系的定義.

定義9.令Gi=(Vi,Ei,Ii)為DAG 圖,其中i=1,2,V2?V1,模擬關(guān)系是定義在G1,G2上的二元關(guān)系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出發(fā)的路徑片段u1∈I1,un=v,使得成立,其中,u1=v2,

如果存在定義在G1和G2上的模擬關(guān)系R,則稱G2模擬G1或G1被G2模擬,記為G1?ST G2.

定理2.如果Gsub=(Vsub,Esub,Isub)為G=(V,E,I)關(guān)于子圖劃分標準K(Qsub)的近似子圖,則有G ?ST Gsub成立.

證明.令R ?V×Vsub為定義在G和Gsub上的二元關(guān)系,由定義4 和定義5 可知,Isub?Vsub=K(Qsub)?V.

a)對任意v ∈Isub,由定義9 條件a)可知,如果v ∈I,則(v,v)∈R,否則,由定理1 可知,G上存在從初始節(jié)點到v的初始路徑u1u2···un,使得u1∈I,un=v成立,其中,1≤i≤n,于是可得(ui,v)∈R;

b)對任意(v1,v2)∈R,對任意v2的直接后繼節(jié)點由v2∈Vsub,可知,v2∈V,根據(jù)定義5 條件3)可得,G上存在從v2到的路徑片段u1u2···un,使得u1=v2,un=其中,n≥1,1≤i≤n,于是有

定理2 證明了領(lǐng)域知識圖G能夠被近似子圖Gsub模擬.但是近似子圖中引入了領(lǐng)域知識圖上不存在的間接依賴關(guān)系,這種模擬關(guān)系是否能夠使Gsub保持G上頂點間的依賴關(guān)系是影響規(guī)則空間正確性的決定因素.下面通過引入定義在路徑上的Stutter 等價關(guān)系來說明這個問題.

定義10.令Gi=(Vi,Ei,Ii)為兩個DAG圖,pi為Gi上的路徑,其中i=1,2.其中,p1=

p1Stutter 等價于p2當且僅當存在二元關(guān)系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)關(guān)于子圖劃分標準K(Qsub)的近似子圖,對于Gsub上的任意初始路徑psub,G上存在初始路徑p,使得ppsub.

證明.由定理2 可知,G ?ST Gsub,令R ?V×Vsub為定義在G和Gsub上的模擬關(guān)系,psub=v1v2v3···為Gsub上的初始路徑.由于v1∈Isub,根據(jù)定義9 條件1)可知,G上存在路徑片段u11u12···其中,u11∈I,=v1,n1≥1,1≤i1≤n1,此時有∈R成立.

假設(shè)vm為psub上的頂點(m≥1),且G上存在路徑片段其中,=vm,nm≥1,此時有∈R成立,1≤im≤nm.

對于psub上的頂點vm+1,由于vm+1直接依賴于vm,由定義9 條件b)可知,G上存在從vm出發(fā)的路徑片段使得(ui(m+1),vm+1)∈R成立,其中,u(m+1)1=vm,=vm+1,nm+1≥2,1≤im+1≤nm+1.

經(jīng)歸納可得,G上存在初始路徑p=v11v12······Stutter 等價于psub.

定理3 保證了近似子圖上的路徑在其生成知識圖上存在Stutter 等價路徑,說明近似子圖保持了領(lǐng)域知識圖上的依賴關(guān)系,即近似子圖引入的額外依賴關(guān)系能夠模擬領(lǐng)域知識圖上的依賴關(guān)系.這個性質(zhì)保證了理想屬性模式及規(guī)則空間的合理性.也就是說,近似子圖不僅能夠有效壓縮規(guī)則空間的規(guī)模,而且能夠保持領(lǐng)域知識圖上的依賴關(guān)系.

3)算法性能分析

給定領(lǐng)域知識圖G=(V,E,I)和測試項目集Qsub.對于AS 算法,最壞情況是初始時K(Qsub)中頂點間不存在直接依賴關(guān)系,此時AS 算法需要探測Vsub中任意頂點到中頂點的路徑是否滿足定義5 第5)項的要求.因此,AS 算法的最壞時間復雜度為(|V|+|E|)×|K(Qsub)|.而DPS 算法為保持領(lǐng)域知識圖中與K(Qsub)相關(guān)的全部依賴關(guān)系,最壞時間復雜度也為(|V|+|E|)×|K(Qsub)|.由于VDS 算法只從領(lǐng)域知識圖中抽取與K(Qsub)中頂點相關(guān)的直接依賴關(guān)系,所以最壞時間復雜度為|V|+|E|.從消耗的存儲空間角度來看,AS,DPS和VDS 三種算法在計算過程中都需要存儲生成子圖的頂點集和邊集.由于AS 算法和VDS 算法生成的子圖都不引入K(Qsub)以外的頂點,所以它們在最壞情況下的空間復雜度為|K(Qsub)|+|E|,DPS算法的最壞空間復雜度為|V|+|E|.

3 實驗結(jié)果與分析

本文開展了兩組實驗分別用于驗證基于近似子圖的規(guī)則空間生成算法的空間壓縮能力及其在實時課堂教學認知診斷中的有效性.兩組實驗使用基于認知診斷的可編程教學輔助系統(tǒng)(Cognitive diagnosis based programmable teaching support system,CDPTSS)開展教學認知診斷,該系統(tǒng)在CETE(Center for educational testing and evaluation)實驗室設(shè)計的認知診斷評價工具提供的開放接口上實現(xiàn)了基于近似子圖的規(guī)則空間生成算法,并提供實現(xiàn)規(guī)則空間壓縮的可編程接口.系統(tǒng)運行操作系統(tǒng)為Ubuntu Server 14.04,處理器為Intel xeon e5-262,主頻2.0 GHz,內(nèi)存32 GB.

3.1 實驗方案

第1 組實驗的目的是對比DPS,VDS 和AS 算法在相同測試項目集下的子圖規(guī)模以及由這些子圖生成的理想屬性模式集的規(guī)模,從而驗證近似子圖對規(guī)則空間的壓縮能力.使用的標準測試集為AAAS(American Association for the Advancement of Science)提供的數(shù)學知識圖1http://www.project2061.org/publications/bsl/online/index.php.實驗數(shù)據(jù)僅涉及由該數(shù)學知識圖中知識間依賴關(guān)系構(gòu)成的DAG 圖.實驗用測試項目集從知識圖配套單元測試集中抽取.為了滿足AS 算法的初始條件,在DAG圖中建立節(jié)點0 作為所有初始節(jié)點的依賴節(jié)點.實驗抽取10 組測試項目,在相同環(huán)境下使用DPS,VDS 和AS 算法由各組測試項目生成知識子圖,進而應用ASIAM 算法計算理想屬性模式.

第2 組實驗通過開展實際教學認知診斷應用分析DPS,VDS 和AS 的性能差異.評價指標和實驗過程與第一組實驗相同.實驗涉及的課程為《Java語言程序設(shè)計》,領(lǐng)域知識圖由該課程中的83 個相關(guān)知識點生成,測試項目庫規(guī)模為223.共開展8 次認知診斷測驗,根據(jù)實際教學單元涉及的知識點確定測試項目.為了評價三種算法在課堂教學認知診斷應用中的實際效果,每次測試項目的規(guī)模由所選教學小節(jié)的實際內(nèi)容確定.此組實驗首先根據(jù)所選測試項目集分別由三種算法生成規(guī)則空間,并記錄相關(guān)結(jié)果數(shù)據(jù).進一步選擇一個教學班共56 人作為實驗對象,使用AS 算法生成的規(guī)則空間對學生知識狀態(tài)進行診斷,并由實驗對象對評價結(jié)果進行評價反饋,以驗證AS 算法生成的規(guī)則空間的合理性以及應用該規(guī)則空間開展認知診斷的準確率.

3.2 規(guī)則空間壓縮能力實驗結(jié)果與分析

第1 組和第2 組實驗生成的近似子圖及理想屬性模式規(guī)模分別如表5 和表6 所示.從表5 給出的子圖頂點集規(guī)模來看,AS 和VDS 算法沒有引入與測試項目集無關(guān)的頂點,所以它們計算獲得的子圖頂點集只與測試項目集生成的劃分標準有關(guān).因此,AS 和VDS 算法計算得到的子圖頂點集相同.而DPS 算法計算得到的子圖頂點集規(guī)模依賴于測試項目集涉及的知識點間的依賴關(guān)系.測試項目集生成的劃分標準規(guī)模越大,知識點間的依賴關(guān)系就越復雜,DPS 生成的子圖引入的額外頂點越多,導致子圖頂點集規(guī)模迅速增大,導致DPS 算法計算得到的邊集規(guī)模顯著大于AS 和VDS 算法.而子圖規(guī)模的增長會導致理想屬性模式集規(guī)模呈指數(shù)級增長,最終導致DPS 算法計算得到的理想屬性模式集規(guī)模與AS 和VDS 算法計算得到的理想屬性模式集不在一個量級上.從實驗結(jié)果數(shù)據(jù)來看,AS 和VDS算法相較DPS 算法而言,能夠在計算子圖過程中忽略與測試項目無關(guān)的頂點,從而實現(xiàn)對子圖規(guī)模的壓縮.從表5 給出的實驗結(jié)果來看,AS 和VDS 最大的差別在于AS 計算得到的子圖邊集規(guī)模大于VDS 計算得到的邊集,原因是VDS 計算得到的頂點導出子圖只保留與劃分標準直接相關(guān)的知識依賴關(guān)系,這種方法能夠保證總是獲得最小化的子圖邊集,不足之處是忽略了知識點間存在的間接依賴關(guān)系.為了在壓縮子圖規(guī)模的同時盡可能保證知識點間依賴關(guān)系的完整性,AS 算法在VDS 算法基礎(chǔ)上,通過構(gòu)建頂點間的虛擬邊模擬知識點間的傳遞依賴關(guān)系,從而在保證子圖頂點集最小化的前提下保留了知識點間的間接依賴關(guān)系,這是AS 生成的子圖邊集規(guī)模大于VDS 生成的子圖邊集的原因.這些保留下來的間接依賴關(guān)系能夠在計算理想屬性模式集時縮減更多不合理屬性模式,從而使AS 算法計算得到的理想屬性模式集顯著小于VDS 算法計算得到的理想屬性模式集.從實驗結(jié)果來看,相較于DPS 和VDS 算法,AS 算法能夠獲得規(guī)模更小的理想屬性模式集.

表5 第1 組實驗中子圖及理想屬性模式規(guī)模Table 5 Scale of subgraphs and ideal attribute pattern in the first experiment

表6 第2 組實驗中子圖及理想屬性模式規(guī)模Table 6 The scale of subgraphs and ideal attribute pattern in practical teaching cogonitive diagnosis in the second experiment

表6 給出了第2 組實驗中依據(jù)實際教學內(nèi)容生成規(guī)則空間部分的實驗結(jié)果數(shù)據(jù).從表6 可以看出,8 次測驗涉及的測試項目集規(guī)模在6～8 之間,子圖劃分標準規(guī)模也在5～8 之間.DPS,VDS 和AS 對子圖規(guī)模的壓縮能力也與第一組實驗一致.DPS 對子圖規(guī)模的壓縮能力最弱,但能夠精確地保持領(lǐng)域知識圖中的所有依賴關(guān)系;VDS 對子圖規(guī)模的壓縮能力最強,但不能保持完備的知識依賴關(guān)系;AS 創(chuàng)建的子圖點集規(guī)模與VDS 相同,但邊集略大,總體上兩者創(chuàng)建的子圖規(guī)模處于同一水平,但AS 創(chuàng)建的子圖通過引入模擬間接依賴關(guān)系的虛擬邊使子圖保持了領(lǐng)域知識圖上的依賴關(guān)系.相對VDS 而言,由AS 創(chuàng)建的子圖能夠削減掉更多不合理的屬性模式,從而實現(xiàn)對規(guī)則空間最大限度的壓縮.

3.3 規(guī)則空間生成時間實驗結(jié)果與分析

第1 組和第2 組實驗生成的近似子圖及理想屬性模式規(guī)模分別如圖4 和圖5 所示.圖4 給出了ASIAM 算法使用三種算法生成的知識子圖構(gòu)建規(guī)則空間消耗的時間代價.圖中方塊、實心圓點和三角分別表示由DPS,VDS 和AS 構(gòu)建的子圖生成規(guī)則空間所需時間代價.從圖4 可以看出,在子圖規(guī)模較小的情況下,三者生成規(guī)則空間消耗的時間代價差異不明顯.隨著子圖規(guī)模的增長,由DPS 構(gòu)建的子圖生成規(guī)則空間所需時間代價呈指數(shù)級增長,原因是生成規(guī)則空間所需時間代價隨子圖規(guī)模呈指數(shù)級增長,這也是DPS 算法不適用于大規(guī)模認知診斷的直接原因.

圖4 第1 組實驗規(guī)則空間生成時間Fig.4 Time performance of rule space generation in the first experiment

圖5 第2 組實驗規(guī)則空間生成時間Fig.5 Time performance of rule space generation in the second experiment

由于AS 和VDS 算法生成的子圖點集相同,區(qū)別僅在于邊集規(guī)模,它們生成的子圖規(guī)模處于同一量級.但VDS 算法構(gòu)建的子圖邊集規(guī)模較小,導致計算合理屬性模式所需運算量較小.因此,由VDS算法構(gòu)建的子圖生成規(guī)則空間所需時間代價略低于由AS 算法構(gòu)建的子圖生成規(guī)則空間所需時間代價.總體上來看,兩者所需時間代價處于同一量級.結(jié)合表5 實驗結(jié)果來看,AS 算法能夠在不顯著降低時間性能的前提下,使構(gòu)建的子圖生成的理想屬性模式集規(guī)模更小,從而達到壓縮規(guī)則空間的目的.

圖5 給出了由三種算法創(chuàng)建的子圖生成規(guī)則空間的時間代價.由于8 次教學認知診斷涉及的測試項目集規(guī)則較小,三者時間性能在縱軸上的落差遠小于圖4.總體來看,圖5 反映的時間性能與圖4 一致,由DPS 算法創(chuàng)建的子圖生成規(guī)則空間的時間性能最差;由AS 算法創(chuàng)建的子圖生成規(guī)則空間的時間代價略高于由VDS 算法創(chuàng)建的子圖生成規(guī)則空間的時間代價,但兩者處于同一量級.圖5 中在個別點上由三種算法創(chuàng)建的子圖生成規(guī)則空間的時間代價差異并不明顯,這是由于本次測驗使用的測試項目涉及的知識點比較集中,DPS 創(chuàng)建子圖時沒有引入過多的額外頂點,而VDS 和AS 創(chuàng)建子圖時不會引入無關(guān)頂點,三者生成的子圖規(guī)則差異不大,所以由三個子圖生成規(guī)則空間時的時間性能也基本相當.

3.4 診斷結(jié)果準確率實驗結(jié)果與分析

上述實驗通過標準測試集和實際教學認知診斷應用,對AS 算法的規(guī)則空間壓縮能力進行驗證和分析,證明AS 相較VDS 和DPS 具有更好的規(guī)則空間壓縮能力.為了進一步觀察由AS 算法創(chuàng)建的近似子圖生成的規(guī)則空間的合理性,即使用該規(guī)則空間開展認知診斷時的準確率,在第2 組實驗中進一步使用由AS 算法生成的規(guī)則空間對56 名實驗對象開展認知診斷,診斷結(jié)束后由實驗對象對診斷結(jié)果的準確性進行主觀評價,評價結(jié)果由CDPTSS系統(tǒng)回收和統(tǒng)計,如表7 所示.

表7 診斷結(jié)果準確率Table 7 Accuracy of diagnostic results

表7 中Valid 表示有效評價結(jié)果數(shù)量,H,M,L分別表示診斷結(jié)果準確率在91～100%、81～90%和0～80% 三個區(qū)間的實驗對象比例.從實驗對象的主觀評價結(jié)果來看,平均有90.26% 的實驗對象的診斷結(jié)果準確率在H區(qū)間,6.76% 的實驗對象的診斷結(jié)果準確率在M區(qū)間,2.98% 的實驗對象的診斷結(jié)果準確率在L區(qū)間.總體來看,使用AS 算法創(chuàng)建的近似子圖生成的規(guī)則空間能夠有效支持教學認知診斷,診斷結(jié)果準確率較高,從被測試對象的主觀角度反映了近似子圖的依賴關(guān)系保持能力.

4 結(jié)論

本文提出一種使用似子圖壓縮規(guī)則空間的方法.近似子圖能夠忽略與測試項目無關(guān)的屬性,同時通過構(gòu)建頂點間的虛擬邊模擬領(lǐng)域知識圖上的傳遞依賴關(guān)系.這種方法在有效縮減規(guī)則空間規(guī)模的同時,使近似子圖保持了領(lǐng)域知識圖上的依賴關(guān)系.通過構(gòu)建DAG 圖上的模擬關(guān)系證明了近似子圖對依賴關(guān)系的保持能力.使用標準測試集驗證了近似子圖構(gòu)建規(guī)則空間的時間代價與VDS 算法處于同一量級,但近似子圖對依賴關(guān)系的保持能力使其能夠更為徹底地過濾不合理屬性模式,從而實現(xiàn)對規(guī)則空間規(guī)模的壓縮.近似子圖在實際教學認知診斷中的應用,進一步驗證了近似子圖能夠在不影響診斷結(jié)果準確率的同時,使規(guī)則空間模型有效支持小規(guī)模、實時教學認知診斷.然而,使用近似子圖生成規(guī)則空間開展認知診斷產(chǎn)生的知識狀態(tài)圖中存在虛擬邊,如何從包含虛擬邊的知識狀態(tài)圖中生成補救教學路徑是影響診斷結(jié)果易用性的關(guān)鍵因素.文獻[27?30]提出的由抽象路徑生成具體路徑的方法為解決該問題提供了可借鑒的思路,今后,將進一步研究如何把包含虛擬邊的補救教學路徑在領(lǐng)域知識圖上具體化.