結合圖卷積的在線編程系統成績預測模型

羅文劼，肖梓良

(河北大學 網絡空間安全與計算機學院，河北 保定 071002)

0 引 言

隨著在線教育的快速普及，各種在線編程系統(programming online judge，POJ)被廣泛應用于計算機科學教育的輔助教學和編程競賽的輔助培訓中[1]。在輔助教學中，教師借助POJ培訓并掌握學生的編程水平[2]，通常的交互順序如下：

(1)教師從POJ題庫中選擇要布置的題目，發布為題目集。

(2)學生接收題目集，編寫題目解決方案的源代碼并提交。

(3)POJ將代碼編譯成可執行文件，將輸出結果與標準答案進行比較。

(4)POJ反饋學生該方案是否正確。如果不正確，則提示錯誤，并允許學生對該題目再次解答。

(5)教師根據POJ提供的答題信息了解學生編程水平。

計算機科學考驗學生的抽象思維和實踐能力，許多學校相關課程期末不及格率超過30%[3]，一種解決方法是通過學生早期POJ測試的表現預測成績，對學生進行針對性輔導，也推進下游任務進行[4-6]。

POJ允許學生多次解答，因此存在提交記錄、重復提交次數、最終成績等特征。現有模型往往只利用最終成績特征，并需要大量的學生背景信息，對數據源要求較高[7-9]。也有模型利用了在線學習的特征[10-12]，但僅利用了進行了POJ測試且存在期末成績的有標簽學生的信息，未有效利用沒有期末成績的無標簽學生的信息。

為解決以上問題，本文提出一種結合圖卷積的在線編程系統成績預測模型DKT-GCN。通過改進深度知識追蹤模型(deep knowledge tracing，DKT)對學生提交記錄建模獲取知識狀態，然后結合圖卷積模型在POJ測試成績的基礎上嵌入知識狀態信息，利用融合后特征預測學生成績等級。該模型保留無標簽學生信息提升預測效果，教師可以根據模型的預測獲得學生的成績等級與知識狀態，以此設計個性化教育策略，對不同的學生進行個性化輔導，幫助學生更好地提高成績。

1 相關工作

1.1 深度知識追蹤模型

學生在給定的學習過程中解決相關問題，解決結果的時間序列為x0，x1，…，xt， 知識追蹤模型目的在于預測學生在下一個時間步上的解決結果xt+1。 深度知識追蹤模型是利用循環神經網絡建模學生知識狀態，避免了大量的特征標注，取得了最好的預測效果[13]。

近年來研究人員針對不同場景對DKT模型加以改進與應用，通過重構損失函數提高模型的穩定性[14]，利用學生的學習軌跡預測在下一次編程問題上的成功幾率[15]，結合協同過濾算法進行題目推薦[16]。

1.2 圖卷積模型

傳統的卷積神經網絡通過固定大小的卷積核抽取特征，難以直接應用于不規則空間結構數據。為此Kipf等提出適用于不規則圖結構數據的圖卷積神經網絡(graph convolutional network，GCN)并應用于結點的半監督分類任務[17]。GCN可以較好融合圖中的結點信息和結構信息，已被廣泛應用于推薦系統[18]、交通預測[19]和文本分類[20]等場景。

在線教育領域中，每個課程的前置課程數量不同，Hu等利用GCN將前置課程知識對目標課程的重要性加權進行成績預測[21]。交互式題庫中每個學生的題目交互不同，Li等利用GCN處理學生與題目的關系，并在隱含層之間增加殘差連接解決過平滑問題[22]。

本文參考以上模型處理不規則數據的思路，利用GCN處理不規則的學生相似關系，利用半監督特點挖掘無標簽學生的信息，將更多信息融入模型。

2 結合圖卷積的在線編程系統成績預測模型

針對POJ教學中成績預測模型的不足，本文提出一種結合深度知識追蹤與圖卷積的在線編程系統成績預測模型DKT-GCN，模型總體結構如圖1所示，具體流程如下：

圖1 DKT-GCN模型結構

(1)通過POJ題目的提交次數與正確解答次數計算題目正答率，并轉化為題目難度特征。

(2)將難度與學生提交記錄進行獨熱編碼，改進DKT模型輸入，訓練模型獲取學生知識狀態向量。

(3)使用熵權法挖掘不同知識對學生成績的影響，獲取學生的相似度矩陣。

(4)結合POJ測試成績構建GCN預測網絡，融合多層特征預測學生期末成績。

2.1 學生相似度矩陣

2.1.1 學生知識狀態向量

本文嘗試利用GCN挖掘無標簽學生的信息，因此通過DKT模型建模學生知識狀態，構建全體學生相似關系。設POJ測試中共有M個學生，N個題目。原始DKT模型輸入考慮當前時刻提交的編程題目編號和學生解答結果，輸出學生答對相關題目的概率。但是原始DKT模型認為每個題目是等價的，忽略了題目本身的特征。題目的難度特征對解答狀況有較強的影響，例如高難度的題目學生答對的概率更低，所以引入題目難度信息有助于模型訓練。因此本文將題目的難度特征引入提交記錄，改進DKT模型的輸入。引入難度特征后模型結構如圖2所示，dt是學生在t時刻提交題目的難度特征，xt是學生提交記錄的獨熱編碼，ht是模型的隱含層狀態，kst是模型輸出的學生知識狀態。

圖2 引入難度的深度知識追蹤模型

在POJ場景下，題目一旦被提交到題庫，系統就會統計所有解答過該題目學生的答題情況。難度被映射為題目的正答率，即題目統計中正確解答次數與提交次數的比值。題目難度越小，學生在越少的提交次數內正確解答；難度越大，學生在越多的提交次數內正確解答或者錯誤解答。具體來說，首先通過式(1)計算題目n的正答率acrn，n∈N

(1)

式中：ACCn是題目n統計中POJ反饋為正確解答的提交次數的總數；SUBn是題目n統計中的提交次數的總數，無論POJ反饋為正確解答還是錯誤解答。所有題目至少有一次正確解答記錄，因此0

之后對正答率acrn進行等寬離散化處理，劃分成固定個數且寬度相同的區間。結合常用的難度劃分方法，如式(2)將題目正答率acrn劃分為十級難度，獲取難度特征d(n)，1≤d(n)≤10

(2)

最后使用獨熱編碼將題目的難度融入學生提交記錄。學生在t時刻提交題目的編號表示為nt，題目難度為dt。POJ反饋狀態at以0、1表示正確解答和錯誤解答。設交記錄的獨熱編碼長度為2N+10，若POJ反饋學生正確解答題目nt，即at=0，則提交記錄中第nt個位置與2N+dt個位置值為1，其余位置為0；若POJ反饋學生錯誤解答題目nt，即at=1，則第N+nt個位置與2N+dt個位置值為1，其余位置為0。學生正確解答與錯誤解答題目的獨熱編碼xt如圖3所示。

圖3 引入難度后的獨熱編碼表示

獨熱編碼的長度取決于數據集中題目的數量，因此在小型數據集中可以直接使用獨熱編碼訓練網絡，而在大型數據集中可以通過全連接網絡、自編碼器與壓縮感知算法進行降維處理，避免網絡過擬合。

改進后模型輸入為學生在POJ測試中的記錄xt及對應題目的難度dt，模型輸出KSt是長度為N的向量，ht為隱含層狀態。ht、KSt表達式如式(3)所示

ht=tanh(Whx(xt，dt)+Whhht-1+bt)KSt=σ(Wyhht+by)

(3)

式中：Whx為輸入權重矩陣，Whh為循環權重矩陣，Wyh為輸出權重矩陣，bt為隱藏層偏置。相較于原始模型，改進DKT模型的輸入挖掘了題目的難度信息，包含更多的特征信息。

改進DKT模型的損失函數如式(4)所示

(4)

通過優化損失函數L訓練網絡模型，獲得t時刻模型輸出的KS=[ks1，ks2，ks3，…，ksN]， 其中ksn是學生答對題目n的概率，代表相關知識掌握度，0≤ksn≤1。ks值越接近0，學生答對該題目的概率越小，相關知識的掌握度越低；反之學生答對該題目的概率越高，相關知識掌握度越高。因此將KS視為學生的知識狀態向量，以描述學生的知識掌握度。

2.1.2 知識狀態熵權計算

熵權法利用信息熵對某個指標的不確定性與離散程度客觀地進行度量[23]。信息熵是事件所包含的不確定性的度量，某個指標的信息熵越小，所能提供的信息越多，表明變異程度越大，在綜合評價中越重要。

熵權法是客觀賦權法，精準性更強，但缺點在于僅憑數據的波動程度計算指標權重，不考慮數據的實際意義，而且不能減少評價指標的維數。DKT模型輸出的知識狀態向量KS中每個維度的知識掌握度實際意義相似，但在實際場景中影響學生成績的往往是部分關鍵知識，直接使用知識狀態向量計算學生相似關系平等對待所有知識，忽略了知識的差異性。

為了剔除知識狀態向量中對學生成績預測貢獻較小的維度，本文使用熵權法處理知識狀態向量，使熵權法與DKT模型發揮各自的優勢。具體計算過程如下：

(1)構建知識狀態向量矩陣

熵權法要求對各個指標進行無量綱的標準化處理，使得數據的大小能夠直觀地描述評估對象的優劣情況。DKT模型輸出的知識狀態中知識掌握度ks值的取值范圍均為[0，1]，且值越大越好，屬于正向指標，因此使用式(5)進行數據標準化

(5)

式中：ks′mn是學生m標準化后的ksn值，ksmn是學生m知識狀態中ksn值，max(ksn) 是所有學生知識狀態中最大的ksn值，min(ksn) 是最小的ksn值。

通過M個學生的N維知識狀態向量構建原始知識狀態向量矩陣KS′， 如式(6)所示

(6)

(2)確定知識掌握度的權重

對于知識狀態中每個知識掌握度的離散程度，僅考慮知識本身的重要性。依據信息熵的定義，確定各知識掌握度的熵值，如式(7)所示。其中En是第n維知識掌握度的信息熵，且0≤En≤1

(7)

在熵權法中，信息熵En被定義為潛在信息的期望值，因此定義信息效用值Dn=1-En， 則信息效用值越大，已有信息量越多，對綜合評價越重要。計算第n維知識掌握度的熵權ωn*， 并構建知識掌握度熵權矩陣WE，如式(8)所示

(8)

(3)計算學生的加權知識狀態向量

(9)

2.1.3 相似度矩陣構建

(10)

獲取所有學生的鄰居學生，整體上定義學生相似度矩陣A如式(11)所示

(11)

2.2 GCN預測模型的結構

在構建學生相似度矩陣之后，將該矩陣與POJ測試成績輸入到GCN預測網絡中進行特征提取與預測，模型結構如圖4所示。由于每個學生的鄰居學生數量不同，難以直接使用傳統卷積提取特征，因此本文使用GCN層處理不規則的鄰居關系。因為單層GCN難以解決非線性問題，而層數過多會造成過平滑現象導致精度下降，并且運算量也會隨之增大，不利于訓練，所以設置兩層GCN結構。

圖4 預測網絡模型

相似等級的用戶在特征表現上應該相近，因此利用GCN對結點特征進行傳播，特征值的信息沿著圖的邊之間進行傳遞和轉換，利用鄰居學生更新自身狀態，本質上是聚合鄰居學生信息。每一層GCN僅傳播一階鄰居學生的特征信息，通過疊加多層GCN實現多階鄰居學生之間的信息傳遞，將未知標簽學生結點的特征傳播到已知標簽學生的結點，因此能夠利用無標簽學生的鄰居關系傳播特征。最后使用已知標簽學生的分類器計算損失函數，反向傳播優化參數。

為了實現對學生的圖卷積操作，本文將學生視為圖中的結點，學生的POJ測試成績視為結點特征，學生之間的相似度視為結點的連接關系，構建了學生相似度圖G。通過傳播式(12)融合了學生結點的POJ測試成績與結點間的相似度關系

(12)

DKT-GCN的兩次圖卷積操作使得結點特征可以在其二階結鄰居之間傳遞，使得相似的學生結點具有相似度的特征表現。學生結點的初始成績特征H(0)在卷積操作前僅攜帶自身信息，在經過第一層GCN后，學生結點加權聚合一階鄰居學生的POJ測試成績特征信息，得到特征H(1)， 再經過第二層GCN加權聚合二階鄰居學生的POJ測試成績特征，得到特征H(2)。

但在進行期末成績預測任務時，僅使用最終層輸出的特征H(2)并不能達到理想的效果。因為GCN的數學本質是拉普拉斯平滑的特殊形式，通過對結點的特征進行了低頻濾波，鄰居結點的特征和中心結點的特征會趨于相似，便于預測任務進行。但學生集合通常較小，隨著多次使用拉普拉斯平滑之后，也就是采用了多層GCN之后，學生結點的聚合半徑變大，不同學生結點的特征將趨于同質化，導致每個學生結點的局部網絡結構的多樣性大大降低，弱化了學生初始特征的表達，不利于結點自身特征的學習，造成過擬合。

為此本文將每層GCN的輸出都與最終的聚合層相連，采用特征拼接的融合方法，將H(0)、H(1)與H(2)融合為最終成績特征H(f)。 聚合后的結點最終成績特征H(f)擁有混合性的聚合半徑，對于任意一個學生結點而言，既不會因為聚合半徑過大而出現過平滑的問題，也不會因為聚合半徑過小，使得結點的結構信息不能充分學習。

最后使用式(13)計算學生的成績組別為L的概率值TL，取其中最大概率所對應類別為預測結果。如式(14)計算所有已知標簽結點的交叉熵損失函數Loss，使用Adam算法優化權重矩陣W(0)和W(1)， 輸出未知標簽結點的預測結果

(13)

Loss=-∑L∈leveltLlog(TL)

(14)

3 實驗與結果

3.1 實驗設置

為了驗證模型的性能，本文某大學計算機學院2018級與2019級本科生的真實記錄作為數據集，兩個年級的學生整體知識狀態相近。學生成績數據集涵蓋457名學生的POJ測試成績與數據結構課程期末成績，原始數據見表1。

表1 成績數據集

提交數據集涵蓋學生在POJ測試中的15 208條提交記錄，部分原始數據見表2，其中POJstate為POJ反饋，1為錯誤解答，0為正確解答；proid為題目編號，具有唯一性。

表2 提交數據集

成績數據集中期末成績數據均為0～100的數值數據。通過對成績數據集中期末成績X的樣本量與數值分布進行分析，在已有等級劃分方法的基礎上將學生m在期末考試中的成績Xm按照式(15)分為5個等級

(15)

學生成績數據集中存在不同場次的POJ測試滿分數值不同的情況，如第一次POJ測試滿分成績為100分，而第九次POJ測試滿分成績為150分。為降低不同滿分成績對預測結果影響，提高預測模型的通用性，本文對POJ成績進行標準化操作，標準化具體計算方法為式(16)

(16)

式中：POJ′mu是學生m第u次POJ測試標準化后的成績，POJmu學生m在第u次POJ測試中的原始成績，max(POJu)是第u次POJ測試中所有學生的最高成績，min(POJu)是最低成績。

對學生成績數據集與提交數據集進行觀察分析，發現部分學生僅存在期末考試數據，其余場次的POJ成績均為0，且提交數據集中也無對應提交記錄，因此該類學生對成績預測無意義，視為無特征結點并進行刪除。同時觀察到部分學生存在POJ成績與提交記錄，但期末成績為0或者不存在數據，該部分無標簽學生僅用于DKT-GCN中圖卷積層。

選擇了4種傳統的用于學生成績預測的機器學習模型進行了比較，以評估本文構建模型的性能。基線模型包括邏輯回歸模型(logistic regression，LR)、CART決策樹、支持向量機(support vector machine，SVM)、多層感知機(multilayer perceptron，MLP)。

(17)

3.2 實驗結果

3.2.1 參數選取

在構建學生相似度矩陣的過程中，本文通過引入閾值p定義鄰居學生結點，p的取值范圍為[0，1]。當p越大時，學生結點的鄰居學生結點越多，通過卷積獲取更多鄰居學生的信息；當p越小時，學生結點的鄰居學生結點越少，卷積后更多的表達自身結點信息。特別的，p=0時保留相似度最大的結點作為唯一連接，避免出現孤立結點。

圖5顯示了在不同p值時，RMSE值與閾值p之間的變化關系。實驗結果表明p的取值對預測準確率有明顯影響，并且在p=0.2時預測效果最佳，因此選擇0.2作為相似度閾值。

圖5 數據集RMSE變化

3.2.2 結果與分析

為比較不同時期模型預測結果的準確性，按照POJ測試時間順序分別取前30%、前60%與所有POJ測試數據進行實驗，所有實驗均重復進行10次，取RMSE的平均結果作為最終預測效果。

首先僅將U次POJ測試成績作為特征輸入基線模型，而不考慮學生之間關系信息，實驗結果見表3。

表3 使用POJ成績的預測結果

將提交記錄輸入DKT模型獲取知識狀態向量，使用知識狀態向量與POJ測試成績訓練模型，實驗結果見表4。

表4 引入提交記錄的預測結果

將題目難度輸入DKT模型，將引入難度的知識狀態向量與POJ測試成績輸入模型，實驗結果見表5。

表5 引入難度的預測結果

利用熵權法計算知識狀態向量中每個維度的權值得到加權知識狀態向量，將加權知識狀態向量與POJ測試成績輸入模型，實驗結果見表6。

表6 引入熵權法的預測結果

實驗結果顯示，僅使用POJ測試成績特征的模型預測效果較差，平均RMSE值為1.82，這是因為不同于傳統的線下測試，POJ測試允許學生多次提交代碼獲得及時反饋，雖然最終結果相同，但是實際學生解答難度不同，僅使用POJ測試成績特征忽略了學生提交記錄，難以挖掘這些重要信息。

將學生提交記錄通過DKT模型輸出為知識狀態向量后，傳統模型綜合考慮POJ測試成績特征與知識狀態特征，使得預測效果均有較大提升，平均提升13%，驗證學生提交記錄對使用POJ輔導教育的期末成績預測有重要意義。

利用題目難度與熵權法對知識狀態處理后預測結果更加準確，是因為通過難度特征引入了更多信息，并利用客觀表現計算了不同知識掌握度的權重，使模型更關注學生區分度較大的關鍵知識。

GCN-DKT在所有模型中表現最為優秀，為所有預測結果中的最優值1.187，這是因為GCN能在特征傳播過程中利用到無標簽的學生結點，并且在模型中設置了多層特征融合，綜合考慮了各個深度的特征輸出，更充分地挖掘了學生做題記錄中的隱藏信息。

同時發現在早期POJ測試數據的實驗中DKT-GCN更具優勢，這可能是因為在課程早期的POJ測試中題目往往較簡單，后期表現較差的學生雖然不適應題目，但仍與表現較好的學生擁有類似的成績特征，因此早期的測試中學生提交記錄比POJ測試成績更加重要。DKT-GCN通過對相似知識狀態的鄰居學生分配權重，利用圖傳播并約束學生特征，挖掘無標簽學生的信息，降低了學生超常發揮或失誤造成的POJ測試成績波動影響，更好地預測期末成績。

3.3 個性化教育策略

POJ的提交記錄等特征難以直接量化為學生的能力水平，對于教師來說，面對不同能力水平學生的教育需要，如何進行個性化教育一直是一個難點。DKT-GCN將特征建模為加權知識狀態與成績等級，教師可以對學生進行個性化的輔導。

具體來說，成績等級為L5與L4的學生期末不及格概率較高，教師可以在早期發現這兩類高風險學生，發出風險預警并引導學生系統學習基礎知識，推動其學科能力的整體提升。針對成績等級為L3與L2的學生，教師可以分析其加權知識狀態中低于平均值的部分知識，挖掘學生薄弱知識中的關鍵困惑因素，引導學生進行長期的與針對性的補缺學習。成績等級為L1的學生成績突出，遠高于平均成績，因此可以對該學生的學習需求進行升級，挖掘知識狀態中較高的部分，鼓勵學生圍繞個人的興趣點進行拓展學習，進一步發揮個人優勢。

4 結束語

本文通過結合圖卷積構建了一個在線編程系統學生成績預測模型，幫助教師進行個性化教育。利用引入題目難度的深度知識追蹤模型將學生的提交記錄轉化為知識狀態特征向量，結合熵權法對題目重要性賦權。以加權知識狀態計算學生相似度，將做題信息融入模型，綜合考慮學生自身特征與鄰居特征影響，降低了學生噪音成績的影響。通過在真實數據集上的實驗，驗證了本文提出的學生成績預測模型在POJ場景下有較好的預測效果，教師可以通過學生的知識狀態與期末預測成績，對不同成績等級的學生進行差異輔導，提高教學質量。

后續的研究中將關注以下幾點：針對不同POJ平臺引入更多的個性化特征，例如通過自編碼器將學生做題時間特征融入深度知識追蹤模型；當前模型僅考慮知識狀態的數值波動，使用更科學的度量方法可以進一步細化學生相似度結構；將結合圖卷積的成績預測模型推廣到在線教育的下游任務中。