基于神經網絡的相似編程題目推薦

王小良，鄭 巍，夏傳林

(南昌航空大學 軟件學院，江西 南昌 330063)

0 引 言

隨著計算機技術的不斷發展和普及，越來越多的人傾向于通過在線平臺學習[1]。在這些在線教育編程平臺中，推薦相似的編程題目供給學生練習就是一個很重要的任務[2-4]。一般來說，編程題目的內容包括題目知識點、題目文本信息以及題目源代碼信息，如圖1所示。相似的題目是指那些題目的難度相當，知識點相似和題目內容的語義表示相似[5]。例如，圖2顯示了3個編程題目，其中，圖2(a)和圖2(b)有著相同的目的，即評估學生對數組的掌握程度。如何從題目的內容中自動理解題目的語義是一個迫切需要解決的問題。目前已經有采用了文本相似度的方法[4]。但是，一些現有的解決方案可以綜合利用異構數據[6,7]來準確理解題目的語義信息；有一些根據學生的學習偏好來推薦合適的資料[8]。不同的題目有著相似的知識點，但是有著不同的目的，這類不應該歸類為同一種題目，但是有可能這類會被分類同一種相似的題目。

圖1 編程題目包含的數據信息

總的來說，設計一個有效的推薦相似題目的解決方案仍然存在著許多挑戰。首先，題目包含著多個異構數據，如何將這些異構數據表示題目的異構數據特征相關聯，是一個亟待解決的問題。其次，找到一個合適的模型去準確度量題目知識點、題目代碼和題目的文本信息是關鍵一步。最后，通過深入理解語義關系來衡量每組題目的相似部分也是很重要的。為了解決上述的挑戰，在本文中，我們開發了一個基于異構數據的注意力的神經網絡(HANN)框架，用于在大規模的在線編程平臺中通過學習異構數據的統一語義表示來推薦相似的題目。根據在線編程平臺上的真實數據顯示，HANN框架推薦相似的題目的精確度較高。

1 相關工作

一般來說，相關工作可以分為以下3類，即推薦相似的題目的研究、異構數據的學習和對題目對建模的研究。

1.1 推薦相似題目的研究

在現有的文獻中利用題目的概念來推薦相似的題目(RSE)。例如，向量空間模型(VSM)，結合TF-IDF和余弦相似度來度量題目文本的相似度，這種方法是在線教育系統中比較常用的方法。Zheng L I等[5]開發了一種結合VSM和余弦相似函數的方法來對文本進行分類。然而，這些解決方案很少能綜合利用異構的信息來精確理解和表示每個題目的語義。Pragya Dwivedi等[8]根據學生的學習偏好(學習風格、知識水平)來推薦合適的學習資料。但是，沒有針對題目信息來推薦。最近，另一個方向是嘗試利用學生的表現數據，通過獲得題目簇來測量類似的題目。然而，學生的相似表現并不能保證題目的相似。Qi Liu等[9]通過數學題目的圖像和題目概念以多模態方式尋找相似的題目。多模態學習是處理多種模態的強大方法，例如聲音和視頻[10]、視頻和文本[11]、或圖像和文本[6,7]。

1.2 異構信息網絡學習

異構信息網絡[12]作為新興的方向在推薦系統中可以自然地建模復雜的對象及其豐富的關系，其中對象的類型不同，對象之間的鏈接表示不同的關系。最近，Shi等[13]提出了加權異構信息網絡的概念，設計了一種基于元路徑的協同過濾模型，靈活地集成異構信息進行個性化推薦。在Shi等[14]和Zheng等[14-16]論文中，用戶和物品的相似度都是通過不同語義的元路徑下的基于路徑的相似度度量來評價的，并提出了基于雙正則化框架的矩陣因子分解來進行評價預測[17]。

在本文框架中，最重要的步驟之一就是以循環神經網絡的方式整合異構的數據材料。結合文本內容和題目源代碼，構造題目的異構信息網絡。通過深度學習學習題目異構數據信息，從而達到尋找相似題目的目的。

1.3 相似成對建模

對成對的相似度分析有很多研究，例如句子對、圖像對、視頻句子對。通常，成對建模的方法是試圖學習成對中兩個實例之間的關系。如Xu等[11]設計了聯合視頻語言嵌入模型，把學習視頻“與”匹配的關系用來描述視頻句子對的關系。Mueller等[18]利用LSTM架構提取語義表示，對句子進行相似關系分析。Yin等[19]在CNN中加入了注意策略，從單詞、短語到句子觀點捕捉句子對的相關部分。但是，這些方法并不關注具有多個異構數據的實例的成對建模。因此，應該設計新的方法來測量題目對之間的關系。

2 具體框架

在本節中，首先給出推薦相似的編程題目(RSE)任務的正式定義。然后介紹了HANN框架的技術細節。最后，指定了一個成對損失函數來訓練HANN。

2.1 問題定義

相似的題目之間有著共同的目的，這也與題目的語義相關，對于任意的兩個題目Ea和Eb來說，本文用S(Ea,Eb) 評價兩者之間的相似性。S(Ea,Eb) 的分數越高，這就說明Ea和Eb的相似度越高。在沒有損失值得情況下，推薦相似的編程題目(RSE)可以表述為

F(E,R,Θ)→Rs

(1)

圖3 具體的工作流程

2.2 異構數據的注意力神經網絡(HANN)

在本節中，本節將介紹HANN框架的技術細節。如圖4 所示，HANN主要包括3個部分，即，題目的異構數據表示層(HERL)、注意力層(SA)和預測得分層(SL)。具體來說，HERL利用其結構化數據和異構數據，結合長短時記憶神經網絡輸出每個題目的統一語義表示。注意力機制通過語義表征在兩個練習之間測量相似部分。預測得分層計算題目對的相似度得分，可用于對相似的題目集進行排序，以便為所有的題目找到其相似的題目信息。

圖4 HANN框架的具體流程

2.2.1 HERL層

對于HERL的輸入，首先提取題目文本特征，題目知識點轉化為知識點矩陣(Q矩陣)，并且將題目代碼進行one-hot編碼，提取代碼特征。然后，設計了一個基于注意力的長短時記憶網絡(attention-based LSTM)，通過長短時記憶神經網絡整合不同的題目數據來學習每個題目的統一語義表示。具體細節如圖5所示。

(1)題目輸入：對于HERL框架的輸入是題目E的數據，例如文本 (ET)、 題目源代碼 (EC) 和題目知識點矩陣 (EQ)， 將(ET) 形式化為N對詞序列ET=(w1,w2,…wN) 其中wi∈d0， 由一個d0訓練的詞嵌入初始化的Word2vec。對于題目代碼，提取代碼的關鍵詞信息，然后進行one-hot編碼，題目中E的代碼可以用一個矩陣表示EC=(k1,k2,…kL)∈{0,1}L×Lall， 其中ki是一個one-hot向量，其維數等于題庫中所有代碼中的關鍵詞的總個數，Lall為題目E中代碼關鍵詞的個數。題目的知識點將會表示為Q矩陣信息EQ=(q1,q2,…qL)∈{0,1}M×Nall。

(2)源代碼嵌入(Embedding)：因為代碼的關鍵詞的one-hot表示過于稀疏而無法訓練，因此，本文利用一種嵌入(Embedding)操作將代碼的關鍵詞的信息的初始化向量轉化為具有密集值的低維向量。形式上，對于代碼的關鍵詞ki， 轉化為向量ui

ui=kiWu

(2)

其中，Wu∈Lall×d2是嵌入層的參數，ui∈d2為嵌入層的輸出參數。從而，源代碼關鍵詞EC被轉化為一個矩陣u=(u1,u2,…uL)∈L×d2

(3)基于注意力的LSTM在得到知識點和代碼的特征表示后，通過整合輸入題目E的所有的異構數據，即，文本表征、Q矩陣和代碼表征。在每個題目中，文本的不同部分與不同的源代碼和知識點相關聯。因此，本文設計了基于注意力的LSTM結構，以神經網絡的方式學習每個題目的表示，其中本文使用兩種注意力策略，一種是文本-源代碼(TCA)和文本-知識點(TQA)，分別捕獲文本-源代碼(TCA)和文本-知識點(TQA)關聯。細節如圖6所示。

在方法上，基于注意力的LSTM是傳統LSTM架構的一個變體[20]。因為LSTM可以處理任何長序列，并學習跨輸入序列的長范圍依賴關系，本文使用基于LSTM的體系結構來學習任何長度的單詞序列題目的表示。具體而言，本文LSTM網絡的輸入為序列x=(x1,x2,…xN) 每個題目的所有數據，將第t步輸入步驟的隱藏狀態ht更新為如下

圖5 題目的異構表示層(HERL)

圖6 異構數據的語義表示

it=σ(WXixt+Whiht-1+bi),ft=σ(WXfxt+Whfht-1+bf),ot=σ(WXoxt+Whoht-1+bo),ct=ftct-1tanh(WXcxt+Whcht-1+bc),ht=ottanh(ct)

(3)

其中，i·、f·、c·、o·分別為LSTM的輸入門、遺忘門、存儲單元、輸出門。W·和b·是學習過的權值矩陣和偏值。

顯然，在每一個輸入步驟中，xt是一個集文本、知識點和源代碼于一起的多模態向量，即

(4)

(5)

其中，Vac和Wac是TCA的學習參數，而在題目E中， (uj,wt,ht-1) 衡量的是第j步源代碼關鍵詞uj和wt之間的聯系，αj表示的是經歸一化后的φ(uj,wt,ht-1) 的注意力參數。

TQA的目標是捕捉文本-知識點的關聯。與TCA類似，在TQA中，小波變換相關的知識點表示qt可以建模為式(5)的形式，其中可以簡單地使用qj和學習過的TQA參數Vaq和Waq來代替uj、Vac和Wac。

通過基于注意力的LSTM，可以得到隱藏狀態序列h=(h1,h2,…hN) 結合輸入序列x。 此外,這個方法來自于LSTM應用于自然語言處理中[18],最后隱藏狀態hN擁有題目E整體的語義信息的輸入序列x, 所以采用hN的語義表示r(E), 即r(E)=hN。 另外第t步隱藏狀態ht只保存序列的信息 (x1,x2,…xt)。 因此，進一步將h(E)=h表示為題目E異構數據的表示，從而得到E的統一語義表示 (r(E),h(E))。

2.2.2 注意力機制(SA)

如圖4所示，對于每個編程題目對 (Ea,Eb) 統一的表示形式,即 (r(Ea)，h(Ea)) 和 (r(Eb)，h(Eb)), 通過HERL獲得,注意力機制的目標是通過Ea和Eb的統一語義特征表示。如圖2所示，雖然E1和E2是類似的題目，但是它們有不同的文本、源代碼和知識點，這一證據表明，類似的題目可能由不同的數據材料組成。因此，在尋找相似的練習時，有必要捕捉兩個練習中語義相似的部分。因此，本文設計了相似注意力機制來測量兩個練習的相似部分，并學習它們的注意力表征。

在注意力機制方面，使用注意力矩陣A來度量輸入題目對 (Ea,Eb) 的相似部分，方法是計算Ea和Eb各部分與h(Ea)和h(Eb)之間的余弦相似度。A∈NEa×NEb可以表示為

(6)

當我們悉心傾聽一個人的幽幽訴說，當我們沉醉于慷慨激昂的演講，當我們傾訴自己真實的心靈，當我們復述一個幽默的故事，當我們聚在一起夸夸其談一個觀點，當我們描述一個人的形象，當我們索要今天的晚報，當我們隨意看到一個新穎的廣告或標語，當我們醉心于時尚雜志的動聽詞匯，這些都離不開語文。

(7)

2.2.3 預測得分(SL)

(8)

其中，W1、b1、W2、b2為網絡參數。因此，該方法通過平衡異構信息，精確地測量了題目對的相似度得分。那些具有最大相似度得分的候選人將作為給定練習的相似練習返回。

2.3 HANN學習

在本節中，為了訓練HANN指定了一個成對損失函數。在訓練階段，假設有一個子集的題目已經標記了幾個相似的題目。對于題目E， 使用Sim(E) 來表示標記過的相似題目，并將未標記的題目視為不是相似的題目DS(E)， 考慮到相似對 (E，Es) 的相似度得分要高于不相似對 (E，Eds)， 其中Es∈Sim(E),Eds∈DS(E)， 如圖3所示，進一步構建成對損失函數為

L(Θ)=∑E,Es,Edsmax(0,μ-(S(E，Es)-S(E，Eds)))+λΘ||Θ||2

(9)

在上式中，S(..，..) 由式(8)計算;Θ為HANN的所有參數，λΘ為正則化的超參數;μ是一個邊緣參數，迫使S(E，Es) 大于S(E，Eds)。 這樣，可以通過使用Adam[22]直接最小化損失函數L(Θ) 來學習HANN。

由于每個標上標簽的題目E的不同題目數量巨大，如果在訓練過程的每次迭代中都使用它們，將花費大量的時間來訓練HANN。因此，受工作[23,24]的啟發，在每次迭代中只選取不同練習的一個數字(例如50)作為E的DS(E)。 具體來說，在本文的工作中，本文有兩種抽樣方法。

按照知識點隨機抽樣(Q-Random)：在每次迭代中，對于每個給定的題目E， 從那些與E至少有一個共同知識點的題目中隨機選擇一些不同的題目。

3 實 驗

在本節中，首先評估HANN在RSE任務上的表現與其它幾個方法進行比較。然后，通過個案研究來形象化HANN的解釋能力。

3.1 數據描述

本文的實驗數據是從我們大學在線實驗編程平臺提供，專為本校大學生提供編程的平臺。其中，我們的實驗平臺包含4354道真實的編程題目。我們的編程題目被分類成10個知識點信息。

3.2 實驗參數配置

為了驗證HANN算法的有效性，本文對數據集中標記的練習采用了5組交叉驗證，其中5組中的1組用于構建測試集，其余的用于構建訓練集。實驗參數根據基于直觀或經驗達到最優解。

Word Embedding 預訓練：使用維數d0=100的Word2vec工具[25]，在數據集中對HERL的題目輸入中使用的嵌入詞進行訓練。

HANN參數設置：本文將源代碼關鍵詞的嵌入表示的大小(d2)設為100，基于注意力的LSTM中隱藏狀態的維數(d3)設為300，第一個全連接網絡的輸出大小設為200。

訓練的詳細細節。本文在HANN中使用標準偏差為0.1的截斷正態分布初始化參數。在式(9)中將mini-batches 設置為64，μ=0.5和λΘ=0.00004。 式(9)用于訓練HANN，除訓練過的Word2vec中的參數外，可以在訓練過程中調整HANN的參數。本文還使用概率為0.2的dropout來防止過度擬合，而使用梯度裁剪來避免梯度爆炸問題。

測試的詳細細節。由于類似的練習通常有共同的知識點，因此對于給定的題目，必須選擇至少有一個共同知識點的題目作為候選，以查找其相似的知識點。然而，這些題目的數量仍然非常大，并且將所有的題目都作為候選題目是不切實際的，因此，與訓練過程類似，對于測試集中的每個給定練習，隨機抽取至少有一個公共知識點的未標記題目，并將它們與標記的相似題目混合作為候選題目。當測量模型的性能時，多次重復這個過程并報告平均結果。

3.3 比較方法

為了驗證HANN算法的有效性，本文將與幾種方法進行了比較，包括HANN的一些變體、RSE任務的傳統方法以及用于配對建模和異構數據學習的模型。

VSM:基于題目文本的TF-IDF和余弦相似度相結合的向量空間模型(VSM)，是一種簡單、有效、無監督的方法。它在許多教育系統中被廣泛應用于RSE任務。

LSTM：LSTM用于學習基于文本的句子之間的語義相似度。

HANN-T：HANN-T是HANN的一種變體，僅使用題目的文本。

HANN-TCA：HANN-TCA是HANN的一種變體，僅使用編程的文本和源代碼答案，并考慮文本-源代碼與TCA的關聯。

HANN-TQA：HANN-TQA是HANN的一種變體，僅使用題目文本和題目的知識點，并考慮文本-知識點與TQA的關聯。

3.4 評價標準

要為給定的題目推薦相似的題目，將返回該題目中相似度得分最大的候選者。因此，本文采用3個廣泛使用的top-n排序指標：精確度(Precision)、回收率(Recall)和F1測量標準，其中n表示從相似題目集中選擇的題目的多少。所以本文在實驗中設n=1、2、3、4、5。就這3個指標而言，規模越大越好。

3.5 實驗結果

3.5.1 性能比較

為了調查HANN和其它方法在RSE任務上的表現，本文以知識點抽樣的方式訓練模型。正如在測試細節中所討論的，本文設置m=50。構建測試集來計算3個度量的過程重復了20次，然后本文報告平均結果。

圖7～圖9顯示了所有模型的性能結果。可以發現，本文提出的HANN是最好的結果。與SVM和LSTM相比，HANN的精確度、回收率和F1值明顯有一個較大的提升。具體來說，首先，VSM表現不如其它的模型，因為VSM只關注題目的文本中常見的詞語，而不能從語義上理解題目。其次，本文發現HANN-T，只基于文本語義的要低于HANN-TQA和HANN-TCA，這說明，影響題目相似度的重要特征有題目的源代碼和題目的知識點信息。最后，HANN的表現最好，說明它結合文本、知識點和源代碼這些異構數據處理的很好，這也說明TCA和TQA的有效性。

圖7 RSE任務的精度比較

圖8 RSE任務的回收率比較

圖9 RSE任務的F1值比較

綜上所述，這些證據表明題目知識點與題目源代碼在題目中是重要的特征，對RSE任務是有用的。同時，這也意味著HANN可以通過將文本、知識點與題目源代碼的關鍵詞進行多模態整合，更有效地找到相似的題目，同時捕捉文本-知識點和文本-源代碼的關系，并通過語義表征來測量兩個題目之間的相似部分。

3.5.2 取樣方式對訓練的影響

如上文所述，本文有兩種訓練HANN的抽樣方法，即隨機采樣(Random)和根據知識點隨機采樣(Q-Random)。接下來，使用相同的測試集來研究不同的采樣方式對HANN有效性的影響。實驗過程重復了20次，并給出了平均結果。

平均結果如圖10～圖12所示。從圖中可以看出，接受知識點采樣訓練的題目比接受隨機采樣訓練的題目表現更好。本文猜測可能的原因是,在訓練HANN時，對于每一個給定的題目,其類似的題目非常不同于大多數樣本不同的隨機(隨機抽樣),而其類似的題目接近不同的知識點采樣,所以HANN可以關注其類似題目對之間的細微差別和不同的知識點。因此，對于RSE任務，以知識點采樣的方式訓練的模型可以更加強大。

圖10 不同采樣方式對HANN的精確度的影響

圖11 不同采樣方式對HANN的召回率的影響

圖12 不同采樣方式對HANN的F1值的影響

綜上所述，這些證據表明采用隨機采用的方法沒有根據知識點采用的效果好。因為根據知識點采樣，對于輸入的數據來說，就已經根據知識點分類好，根據學生對知識點的掌握情況，推薦更合適的相似題目也就更快。所以說接受知識點采樣數據更好，更符合相似題目的查找。

4 結束語

在本文中，著重研究在線教育編程系統中推薦相似的題目(RSE)。為了對非均勻題目材料進行語義建模，提出了利用題目的文本、知識點和源代碼作為題目的輸入，然后利用基于異構數據的注意力神經網絡框架進行建模。具體來說，首先生成題目知識點矩陣(Q矩陣)，然后使用文本表征表示題目源代碼信息。最后設計了一個基于注意的LSTM網絡，結合異構數據信息學習每個題目的統一語義表示，其中提出了兩種注意策略分別評估文本-知識點和文本-源代碼關聯。接下來，設計了相似注意來測量練習中相似的部分。最后，提出了一種成對訓練策略來返回相似的訓練。在大規模真實數據集上的實驗結果清楚地驗證了HANN的有效性和解釋力。本研究結果表明了對于編程題目相似性的自動分類，題目的文本內容、題目相關知識點和題目的源代碼信息對于判斷題目對之間的相似性有著重要的因素。而本研究的不足點就是沒有將題目對之間的難度信息作為判斷題目對之間的相似性重要因素。我們下一步工作就是將題目難度信息代入HANN框架中。