楊佳諾,張麗萍,閆盛
(內蒙古師范大學 計算機科學技術學院,內蒙古 呼和浩特 010022)
在計算機教育認知領域通過機器理解編程題目是一個重要的研究方向,過程包括自然語言處理中的多種核心技術[1]。在求解編程問題時,若學習者無法將算法內容與實際題目相結合,則無法建立解題的編程思維,不能編寫代碼解決問題。而在初學者面對編程題目時,尚未形成系統(tǒng)的編程思維,不具備分析題目的基本能力。因此,將機器理解編程題目方法應用于解題過程中,將對編程學習者提供很大的幫助。目前,使用計算機理解自然語言的研究已經(jīng)比較成熟,但是與自然語言不同,學生編程題目具有較強的抽象性、復雜性特點,專業(yè)術語較多,因此對學生編程題目理解是一種對基礎知識、邏輯思維的綜合考察,根據(jù)題目文本材料,分析文本內容,抽象編程算法,提取求解編程題目所需的知識點信息和算法信息,幫助初學者提供解決編程問題的關鍵步驟,完成對編程題目理解的過程[2]。這將對計算機編程教育提供指導性幫助,對于促進編程課程的實踐過程有著重要的現(xiàn)實意義。
目前,自然語言處理對文本理解已有了成熟的解決辦法。包括針對四、六級聽力文本閱讀理解,通過抽取材料片段、問題、選項的語義信息并給出正確答案[3];針對航班訂票信息語料提取用戶意圖,通過分詞、訓練數(shù)據(jù)得到用戶的出發(fā)地與目的地等信息[4];針對問答系統(tǒng)中用戶提出的問題,通過分析用戶數(shù)據(jù),結合用戶歷史問題,對用戶產(chǎn)生指導性作用[5]。本文旨在對編程題目進行理解,在編程練習過程中,當學習者求解問題時,對題目的正確理解是編程訓練的關鍵步驟。如何通過智能化的方式幫助學習者理解編程題目、抽取關鍵信息是學生正確解題的關鍵。
文本理解系統(tǒng)中的關鍵信息抽取模塊多采用對文本提取部分關鍵詞并重新組合,形成新的可以由計算機識別的語句的方法[6],但是該方法并沒有對文本深層語義進行提取,不能準確理解文本?;谟脩魡栴}主題模型的方法[7],雖然避免了語義歧義性,對文本的深層語義進行提取,但是該方法針對的是特征主題的數(shù)據(jù),并不適用于具有上下文的數(shù)據(jù)。此外,傳統(tǒng)的機器學習方法將提取關鍵信息這一過程通過分類的方法解決[8],雖然最終結果在人類行為數(shù)據(jù)集上精度有一定提升,但隨著不同領域數(shù)據(jù)集的變化,需要重新設計特征并進行參數(shù)的學習,因此該方法不具備可行性。這些方法簡單易行,雖耗時耗力,不適于大數(shù)據(jù)時代,但為后續(xù)文本理解研究的發(fā)展奠定了基礎。
隨著深度學習的發(fā)展,使用構造深度神經(jīng)網(wǎng)絡來提取文本中關鍵信息的方法被提出。該方法不需考慮特定的句法要求,將文本分詞后的每一個單詞對應的詞向量作為輸入,設計特征工程從輸入中自動提取特征[9],所提取的特征可用于文本預測或者分類過程[10]。該方法主要分為以下三類:基本單神經(jīng)網(wǎng)絡模型[3,11]、擴展神經(jīng)網(wǎng)絡模型[12]和組合神經(jīng)網(wǎng)絡模型[13]。本文基于傳統(tǒng)深度學習方法提出了一種基于BiLSTM+CNN+CRF 聯(lián)合模型的學生基礎編程題目理解方法。主要對編程題目文本特點建模,充分學習編程題目文本語句,減弱編程題目文本的抽象性;通過神經(jīng)網(wǎng)絡模型與相應算法提取文本深層語義,解決編程題目文本含義單一問題。研究結果以期對編程學習者提供幫助。
由于學生編程題目文本具有特殊性,本文對編程題目理解過程進行建模,如圖1 所示。一方面,考慮到理解編程題目后所得信息大多為動詞、名詞,因此,需對編程題目文本進行詞性標注;另一方面,編程題目一般較為抽象,準確提取關鍵信息需提取文本特征。
當編程學習者求解編程問題時,需要理解題目本身的意圖,即該題目需要學習者“怎么做”才能保證解題過程的正確。因此,計算機需實現(xiàn)人腦理解編程題目的過程,得出人腦思考編程題目后的結果,且要保證結果的正確性。對編程題目理解的示例見表1。
由表1 可知,對編程題目進行理解后,所得關鍵信息中,算法關鍵詞一般為動詞,知識點關鍵詞一般為名詞,但算法關鍵詞更為抽象,需進一步分析編程題目文本的語義信息,提取語義特征。
表1 關鍵信息提取示例Tab.1 Example of extracting key information
基于上述分析對編程題目理解過程建模,在對數(shù)據(jù)預處理等操作后,分別對題目數(shù)據(jù)進行詞性標注和語義特征提取,在獲取到相應操作結果后,解碼獲取求解問題的關鍵信息。
詞性標注是將詞性含義與上下文內容結合對文本數(shù)據(jù)中的單詞進行標記處理的過程。本文使用雙向長短期記憶模型(BiLSTM)對編程題目進行詞性標注,其過程包括設計規(guī)則、模型設計與模型的訓練。
人在思考問題之前,大腦中會存放有關該問題的相關知識,這是大腦對信息的持久性作用。傳統(tǒng)的神經(jīng)網(wǎng)絡并不能實現(xiàn)這一特性,而循環(huán)神經(jīng)網(wǎng)絡(RNN)解決了這個難題,RNN 通過之前保存的信息并綁定到當前任務,決定當前的輸出。但由于RNN 在訓練過程中無法解決編程題目文本中的“長期依賴”問題[14],而LSTM 模型通過輸入門、遺忘門、輸出門成功解決這一問題[15]。BiLSTM 單元可通過前向、后向分別獲取輸入序列的上、下文信息。在學生編程題目理解任務中,BiLSTM 模型使當前狀態(tài)的輸入門、輸出門、遺忘門都與前一狀態(tài)、后一狀態(tài)息息相關(如“if”“number”“not”“get rid”等),從而保證學習效果的準確性更高。此外,BiLSTM 不僅可以捕獲到相近位置的信息,也可以捕獲到較遠位置的信息。在決定當前狀態(tài)信息時,影響因素更多,學習結果精確度更高。本文使用BiLSTM 模型為理解學生編程題目文本提供了便利的條件,不僅削弱了編程題目文本的結構性,而且有更精確的詞性標注結果。
特征提取是從文本數(shù)據(jù)中抽象出可以代表該文本的數(shù)據(jù),具有簡介性、抽象性。本文特征提取使用卷積神經(jīng)網(wǎng)絡(CNN),其過程包括文本掃描、提取特征和篩選特征。傳統(tǒng)的特征提取方法是機器學習,但是該方法不能很好地結合編程題目的結構特征,而且對文本的深層語義理解不足。目前,CNN 網(wǎng)絡在自然語言理解任務中已經(jīng)非常成熟[16]。提取特征過程如圖2所示,將每個單詞向量化后,通過過濾器對編程題目進行掃描,固定設置每個過濾器中有n個單詞。在過濾時,通過設計卷積層完成特征提取,在選擇局部特征時采用Relu 激活函數(shù)與最大池化方式,最后形成一個固定長度的全局特征向量,完成對編程題目的特征提取過程。
圖2 特征提取結構Fig.2 Structure of feature extraction
全句解碼是從模型處理過的眾多向量化數(shù)據(jù)中提取最為可靠的數(shù)據(jù)的過程。本文使用條件隨機場(CRF)[17]實現(xiàn)解碼,其過程包括單詞標簽與語義特征拼接、計算權重得分與搜索最優(yōu)路徑。CRF 是用來從所有向量化數(shù)據(jù)中選擇符合要求條件數(shù)據(jù)的概率性模型。通過充分考慮所標注單詞詞性間的線性關系,將全局最優(yōu)序列輸出,實現(xiàn)編程題目的解碼過程。相比于其他解碼模型,CRF 不再單獨識別每個標簽,而是通過局部特征的線性加權組合,使用指數(shù)模型表示標簽序列的聯(lián)合概率完成聯(lián)合建模解碼標簽序列。在對編程題目向量化數(shù)據(jù)解碼的過程中,給定文本序列X={X1,X2,…,Xn},其中n表示字符序號,Xi是第i個單詞的向量。通過BiLSTM 詞性標注與CNN 特征提取后,得到預測標簽序列y={y1,y2,…,yn},Y(u)表示x的所有可能預測標簽序列的集合。其預測標簽序列集Y(x)與給定文本序列x之間的條件概率見公式(1),其中W、b分別是權值向量與偏移量。
CRF 的訓練過程使用最大條件似然估計為函數(shù)代價,公式為
在預測過程中,為了輸出條件概率最大的序列,調節(jié)參數(shù)(W,b) 使得L(W,b) 最大化。因此,搜索具有最大條件概率的標簽序列y*,獲取全局最優(yōu)序列,完成對編程題目的解碼過程。公式為
本文針對BiLSTM+CNN+CRF 聯(lián)合模型的參數(shù)學習采用梯度下降算法(Adam)[18]。在模型訓練過程中,選取矩陣形式的交叉熵損失函數(shù)來對比本文模型與編程題目數(shù)據(jù)集的擬合效果,公式為
模型訓練前需要進行初始化操作,主要包括各部分模型參數(shù)的定義、聯(lián)合模型中間參數(shù)的定義、優(yōu)化方法定義以及損失函數(shù)定義等,由于每道編程題目文本之間無關聯(lián),本文使用單句訓練的方法,訓練步驟(1)梯度值與隱藏層參數(shù)的初始化:在模型訓練之前,將梯度值置為零,并對隱藏層參數(shù)使用隨機初始化方式賦值;(2)預測編程題目中的算法:通過使用自定義規(guī)則,為部分編程題目標注其中可能包含的算法與知識點;(3)誤差的計算與反向傳播:使用交叉熵損失函數(shù)計算出預測值與真實值間的誤差,再將誤差反向傳遞到聯(lián)合模型中的每一層中,完成梯度的更新;(4)計算模型下一次訓練的梯度值:使用優(yōu)化器更新聯(lián)合神經(jīng)網(wǎng)絡模型中的權重值,使梯度值更新至每一個神經(jīng)網(wǎng)絡權重矩陣。
為驗證本方法的有效性,設計BiLSTM+CNN+CRF 模型,在預處理后的英文編程題目數(shù)據(jù)集上進行實驗,通過算法優(yōu)化、模型性能等指標來評估。由于目前還沒有公認度較高的編程題目語料,本文從OJ(online judge)、PTA(https://pintia.cn/)等平臺爬取大約10 000 道編程題目為初始數(shù)據(jù),經(jīng)過去除停用詞、空格、空行、無效數(shù)據(jù)等預處理操作,得到符合要求編程題目8 000 余條數(shù)據(jù)。其中,訓練集約7 000 條,測試集約1 000 條。該數(shù)據(jù)集所包含10 種不同的算法和100 種不同的知識點內容,不同算法所含數(shù)據(jù)量見表2,由于知識點內容較多,不再列出對應表格。
表2 算法語料規(guī)模Tab.2 Algorithmic corpus
實驗結果使用自然語言處理技術中常用的評價指標,即準確率(P)、召回率(R)和F1 測度值。
為獲取更好的模型參數(shù),從訓練集中抽取10% 的數(shù)據(jù)作為驗證集。當模型在驗證集上測試獲得的準確率最大化時,該參數(shù)則為最優(yōu)參數(shù)。將模型參數(shù)修改為最優(yōu)參數(shù)后,再次使用訓練集訓練模型,從測試集上預測(關鍵信息)算法與知識點的準確率、召回率和F1 值,重復訓練10 次后,獲得三個評估指標的均值。之后再設計LSTM 模型、BiLSTM 模型、BiLSTM+CRF 模型、BiLSTM+CNN 模型與本文模型進行對比,結果見表3。
表3 各模型實驗結果Tab.3 Experimental results of different mode %
(1)獨立模型實驗結果:實驗②比實驗①的預測結果在精確率上有大幅度提升。在分析LSTM 模型中的錯誤序列后發(fā)現(xiàn),LSTM 識別錯誤的主要原因在于識別信息的部分丟失。其主要原因在于LSTM雖然解決了“長依賴”問題,但是僅實現(xiàn)從前向后的掃描,無法編碼從后向前的信息,導致部分關鍵信息無法與前面的詞匹配,而BiLSTM 彌補了這一缺陷,其所帶有的雙向機制可以充分學習文本的前后信息,保證信息的完整性。
(2)其他聯(lián)合模型實驗結果:實驗③相比于實驗②在三項指標上有小幅提高。原因在于CRF 充分利用單詞之間的關系,輸出全局最優(yōu)序列,BiLSTM+CRF 模型先獲取單詞間詞性關系,完成詞性標注后利用CRF 得到預測序列,挖掘文本語義信息,得到更精確結果。在實驗②中,分析預測錯誤的結果后發(fā)現(xiàn),BiLSTM 解碼過程是將每一個序列單獨計算,忽略了單詞之間的關系,而CRF 模型則充分考慮相鄰標簽之間的關系,這保證該模型能夠更為準確地識別關鍵信息。與BiLSTM+CRF 相對比,BiLSTM+CNN 模型在最終結果的獲取上有小部分提升。這是因為BiLSTM+CRF 模型中,通過人工的方法提取特征,而人工提取特征的過程耗時耗力且含有較高的主觀性,因此,特征提取結果不能對機器學習的過程提供較好的價值,導致對題目理解的準確性較低,而BiLSTM+CNN 模型使用CNN 網(wǎng)絡提取特征,對于相對重要的信息層層遞進,更高效獲取特征信息。本文提出的模型與BiLSTM+CRF、BiLSTM+CNN 相比在三項指標上有大幅度提高,其結果表明CNN 能有效抽取文本的局部特征,CRF 能充分考慮相鄰標簽間關系進行解碼,提升模型的識別效果。
通過將BiLSTM+CNN+CRF 聯(lián)合模型與上述實驗對比,結果顯示編程題目理解任務的準確率、召回率、F1 值相比其他實驗取得較好的結果。說明本文聯(lián)合模型很好地融合了BiLSTM 模型、CNN 模型和CRF 模型各自的優(yōu)勢,在編程題目理解任務中取得很好的效果。
由于聯(lián)合模型存在規(guī)模大、結構復雜、數(shù)據(jù)形式較多等問題,在完成題目理解后,通過分析聯(lián)合模型特點以及數(shù)據(jù)形式對聯(lián)合模型進行優(yōu)化,模型優(yōu)化的主要工作在于模型內部參數(shù)的界定。在對神經(jīng)網(wǎng)絡模型進行訓練并產(chǎn)生結果時,模型內容的參數(shù)有著至關重要的作用。如用來計算測試集中目標值的真實值與預測值之間的偏差程度、對部分數(shù)據(jù)所賦予的權重值等,這些參數(shù)決定了輸出結果的準確性,由這些參數(shù)構造出的函數(shù)為損失函數(shù)。因此,使用各種優(yōu)化策略來更新計算模型和影響模型輸出的參數(shù)、計算出損失函數(shù)的最優(yōu)值必不可少的。
本文通過前期調研,分別使用隨機梯度下降算法(SDG)、動量、Adagrad 方法、Adadelta 方法、RMSprop方法、Adamax 方法、Adam 方法對聯(lián)合模型進行優(yōu)化對比,結果見表4。
表4 優(yōu)化算法結果對比Tab.4 Comparison of optimization algorithm results %
根據(jù)上述實驗結果可以發(fā)現(xiàn),在聯(lián)合模型中,使用Adam 算法可以取得準確率最優(yōu)結果。對其結果分析,SDG 算法在每次執(zhí)行時對每個訓練樣本都進行一次更新,但是對偏差程度更新時,頻繁更新將導致?lián)p失函數(shù)波動較大,無法穩(wěn)定收斂;Momentum 方法通過減弱無關方向的震蕩并優(yōu)化相關方法的訓練解決了SDG 中無法收斂的問題,但Momentum 方法無法分辨訓練過程達到最優(yōu)值的時刻;Adagrad 方法通過調整模型學習率參數(shù)來達到最優(yōu)解,它對稀疏數(shù)據(jù)大幅度更新、對稠密數(shù)據(jù)小幅度更新,因此,Adagrad 方法對稀疏數(shù)據(jù)有更好的效果;RMSprop 方法對梯度計算了微分平方加權平均數(shù)進一步優(yōu)化了損失函數(shù)擺動較大的問題。以上兩類優(yōu)化方法中,一類通過積累物理動量使損失函數(shù)達到最優(yōu)值,另一類通過縮小收斂速度獲取最優(yōu)值,Adam結合了上述兩類優(yōu)化特點,提出新的優(yōu)化方法;Adamax 方法是Adam 的變體,它提供了學習率的上限范圍,但是在本文中,Adamax 方法無法將上限范圍確定于合適的區(qū)域,使得損失函數(shù)的收斂程度并不樂觀。因此,使用Adam 方法在本文模型中將取得更好的結果。
在提取的編程題目關鍵詞中,為了初學者能夠更好地掌握編程知識,將編程題目關鍵信息分為知識點關鍵詞與算法關鍵詞。分析不同關鍵詞結果,見表5。提取不同信息的準確率相差較大,使用本模型在提取編程題目中知識點信息的準確率較高,而在提取編程題目中的算法信息時結果較低。導致這一結果的原因可以分為以下兩方面。
表5 提取不同信息結果對比Tab.5 Comparison of different information extraction results%
(1)提取關鍵信息不同 在提取編程題目中關鍵信息時,知識點信息是基于編程題目文本的基礎上提取,所需提取內容已包含于待處理的文本中,僅需要做進一步的識別、提取即可。因此,最大概率提高詞性標注的正確率,則可保證提取知識點關鍵詞的正確率,所以提取知識點信息的準確率較高。算法信息的提取則基于模型訓練過程,通過神經(jīng)網(wǎng)絡學習編程題目文本,這不僅要求實驗模型的適應性,而且需要大量的訓練集對模型訓練。從編程題目文本中抽象出解題過程所需要的算法,這一過程是在文本的基礎上依賴于神經(jīng)網(wǎng)絡的學習過程,對模型有較高的要求,因此在本文訓練集較少的情況下對于抽象性較高的編程題目無法較準確提取算法信息。
(2)數(shù)據(jù)集性質不同 與其他模型相比較,本文模型提取知識點信息的準確率較高(表5)。究其原因,其他模型處理自然語言與本文所處理的編程題目數(shù)據(jù)集有本質的不同,本文針對學生編程題目數(shù)據(jù)特點,提出聯(lián)合模型對文本進行理解,學生編程題目數(shù)據(jù)特點見表6。
表6 不同語料特點Tab.6 Characteristics of different corpus
通過本文實驗可以實現(xiàn)對學生編程題目的理解,獲取求解編程問題的關鍵信息,但編程題目間存在著不同難度級別的劃分,為了界定本文實驗模型所使用的范圍,進一步分析不同難度的編程題目與題目理解準確率的相關性。在數(shù)據(jù)獲取階段,提取了編程題目的難度級別,將該題目與級別綁定后進行實驗。
通過分析實驗結果發(fā)現(xiàn),編程題目理解的準確率不會隨著題目難度的變化呈單一變化。究其原因,題目難度的級別劃分不僅考慮了題目描述的抽象性,而且綜合考慮了知識點、算法與實際題目情境的結合應用,1 級編程題目可能通過生活舉例描述算法過程,但這對編程題目的理解并不友好,因此對于此類編程題目理解準確率較低,而1 級編程題目中部分題目描述簡單,將取得較高的準確率。對于較難的編程題目,如4、5 級類型,它們不僅描述更抽象,而且使用不同算法、知識點的綜合應用較強,本文模型對其理解能力較弱。本實驗模型更適用于2、3 級編程題目,由于此類題目在于考查學生對算法、知識點的應用,在題目表述方面抽象程度較弱,對理解過程友好。
本文借鑒自然語言處理領域的深度神經(jīng)網(wǎng)絡模型,提出基于BiLSTM+CNN+CRF 的聯(lián)合模型用于學生編程題目的理解。其中,BiLSTM 用于將編程題目文本基于已有記憶生成帶有學習信息的向量;同時,使用CNN 中的卷積核和最大池化操作提取特征,組成全局特征來表示預測關鍵信息序列標簽;最后將攜帶學習信息的向量與預測序列標簽拼接輸入到CRF 層搜索全局最優(yōu)路徑解碼。該方法聚焦于文本語義建模,通過深度學習提取特征,省去大量繁瑣的人工特征過程,充分分析編程題目語義,消除文本的結構化形式;使用雙向結構進行詞性標注,將編程題目文本前后關聯(lián),縮小文本的抽象性。最后在學生編程題目數(shù)據(jù)集上進行實驗,測試集中達到91.9% 的準確率、87.43% 的召回率與89.60% 的F1 值,三項指標值相比于其他自然語言處理模型都有一定的提高。實驗結果表明對編程題目理解時,本文方法比其他聯(lián)合模型、單一模型具有更好的效果。
基于以上結果,研究不足和下一步工作如下:在數(shù)據(jù)集方面,由于目前本文的數(shù)據(jù)集仍然較少,這導致對模型的訓練準確度不高,并且數(shù)據(jù)集僅在英文編程題目上做出處理,數(shù)據(jù)集形式單一;在模型效果方面,本文的特征提取過程較簡單,所提特征精確度仍需提高。因此,未來工作中將繼續(xù)擴充數(shù)據(jù)集,將訓練模型達到更高的精確度;并且考慮將Attention 機制加入當前聯(lián)合模型的特征提取部分中,再進一步調整參數(shù)、優(yōu)化,完成模型契合,提高編程題目理解的準確率。