??? 摘 要：文字類主觀題的自動評分是實現遠程教育中在線考試系統的一個關鍵技術，由于其自動評判具有相當難度，使自動評分系統中在對語句結構、關鍵字匹配、詞性、詞義以及語義方面的判斷還存在很多問題。通過對已有的算法分析，提出了一種方法，采用淺層次句法結構分析和深層次語義分析相結合的算法計算相似度，該方法可以提高主觀題自動評分的效率和準確度，具有一定的實用價值。
??? 關鍵詞：自動評分；動態規劃；語句相似度；語義相似度
?
??? 目前，在線考試系統正在逐漸代替傳統的考試系統，能否實現主觀題自動評分是在線考試系統中一個重要環節。對于主觀題的考查，由于它的答題涉及到人工智能、模式識別以及自然語言理解等方面的理論知識，評閱時就需要解決很多技術上的問題，因而成為阻礙在線考試系統發展的一個技術難點。
??? 當前的主觀題自動評分算法中，多數使用的是對學生答案和標準答案中關鍵字匹配來計算語句相似度，如基于向量空間模型TF-IDF方法、詞性詞序相結合的方法以及基于語義依存樹等[1-4]。已有的這些方法要么從句子的表層結構信息進行匹配而忽略了語句語義分析，要么就是從語義分析而影響了整體語句的相似性，這些都會影響到自動評分計算的精確度。由于漢語語言的結構和語義的復雜性，一種意思可以用多種形式和多種關鍵字表達，單從一方面很難對語句的意思作出準確的判斷，因此提出了一種新的主觀題自動評分算法策略，主要思想是采用淺層次句法結構分析和深層次語義分析相結合的算法計算相似度，將這兩種思想結合起來使用可以互補不足，提高了主觀題自動評分的準確度。
1 語句相似度計算算法
??? 在主觀題自動批改系統中，語句相似度是用來評價學生答案和標準答案的接近程度。針對漢語的特殊性和機器翻譯領域內一些對語句相似度的研究，采用動態規劃法來計算語句相似度，主要思想是對語句進行層次句法分析。首先用正向最大匹配（MM）和基于詞頻統計的方法對句子分詞，將分詞后得到的語句視為詞的向量，分別對各個關鍵詞進行匹配。然后在此基礎上利用動態規劃算法求出最優路徑及語句相似度[5]。
1.1 相關定義
??? 令P表示標準答案中的某一語句，Q表示學生答案中的某一語句。P和Q分別表示如下：P={P1,P2,…,Pm},Q={Q1,Q2,…,Qm},其中Pi表示P語句中的一個關鍵詞，Qj表示語句Q語句中的一個關鍵詞，且Pi=Pmi U Pgi, Qj=Qmj U Qgj，其中Pmi表示語句P中第i個詞的詞義集合，Pgi表示語句P中第i個詞的詞性集合；同理Qmj表示語句Q中第j個詞的詞義集合，Qgj表示語句Q中第j個詞的詞性集合。為了便于進一步討論給出以下幾個定義：
??? 定義1：詞義、詞性相似度。詞義、詞性相似度可分別表示為：SMij=SM(Pmi,Qmj)，SGij=SM(Pgi,Qgj)。
??? 定義2：關鍵詞相似度。關鍵詞相似度Wij=a×SMij+β×SGij其中a、β分別為詞義、詞性相似度的權值。
??? 定義3：詞向量的相似矩陣。用定義2計算出語句P和Q的所有關鍵詞的相似度Wij(i=1,2,…,m;j=1,2,j=i=1,2,…,n),形成一個m×n矩陣M,稱該矩陣為語句向量的相似矩陣。
??? 
??? 定義4：拓展詞向量相似矩陣,對矩陣M進行如下拓展，形成矩陣M',令M'0,0=0, M'i,0, M'0,j=0(i=1,2,…,m; j=1,2,…,n),則M'i,j=max{M'i-1,j-1+Wij, M'i,j-1+γ,M'i-1,j+γ},其中，γ表示詞位置不對應時的懲罰系數。
1.2 語句相似度求解算法
??? （1）利用動態規劃法先求出M'矩陣[6]。
??? （2）M'矩陣的初始化
??? 創建一個(m+1,n+1)矩陣，矩陣的行表示標準答案語句P的每個詞，矩陣的列表示學生答案語句Q的每個詞，利用定義4進行初始化，將M'矩陣的M'i,0,M'0,j設置為0.其中i=0,1,2,…,m; j=0,1,2,…,n。
??? （3）利用定義1、2、3、4依次求解M'矩陣中的每個元素M'i,j。
??? （4）求解最優相似矩陣
??? 先從點(m,n)開始，到(1,1)結束。在點（i,j）上選擇M'i-1,j-1+Wij,M'i,j-1+γ,M'i-1,j+γ最大者為最優點，所對應的Mx, y作為路徑的前一個節點(x,y)。如果出現三者中兩部分值相同且最大時，若該值在斜路徑上則選擇斜路徑上(i-1,j-1)作為路徑的前一個節點；若不在斜路徑上，優選水平方面(i-1,j)作為路徑的前一個節點；依次遞推則選擇一條最優路徑。這樣得到的路徑上就是一條最優的路徑，路徑上最后一個點的值M'm,n表示了語句中所以詞的相似度之和。
??? 設L是標準答案語句的詞數，則語句相似度為Sim=M’m,n/L。
2 語義相似度計算算法
??? Dekang Lin[7]認為任何兩個事物的相似度取決于它們的共性(Commonality)和個性(Differentces)，然后從信息理論的角度給出任意兩個事物相似度的通用公式:
??? 
??? 其中分子是描述A、B共性所需要的信息量的大小;分母是完整地描述出A、B所需要的信息量大小。劉群[8]認為兩個詞語的相似度是它們在不同的上下文中可以互相替換且不改變文本的句法語義結構的可能性大小。在本文中計算語義相似度是利用《知網》中詞語相似度的定義[9]，可以把詞語語義相似度的計算歸結為“概念”相似度的計算;“概念”的相似度由描述它的“義原”的相似度得到。詞語存在著一詞多義的現象,知網中的一詞多義表現為單個詞語有多個概念,每個概念由一項定義來描述。比如:“打”在“打架”，“打太極”，“打獵”中的意義各不相同,知網中對應的概念描述分別是:
??? DEF = fight| 爭斗
??? DEF = exercise| 鍛煉,sport| 體育
??? DEF = catch| 捉住, # animal| 獸
??? 詞語語義相似度的計算,嚴格來講應該是計算概念之間的語義相似度。本文中采用劉群的思路,認為兩個詞語的語義相似度是其所有概念之間相似度的最大值。
??? Sim(c1,c2)=maxSim(C1i,C2j)(i=1,2,…,m;j=1,2,…,n)
??? 其中, C1i是詞C1的m項概念,C2j是C2的n項概念。這樣就把兩個詞語之間的相似度問題歸結到了兩個概念之間的相似度問題。本文利用語句相似度中分詞方法將詞語標注為概念,然后再對概念計算相似度。
2.1 義原相似度的計算
??? 由于所有的概念都最終歸結于用義原來表示, 詞語整體相似度由部分相似度合成的，所以義原的相似度計算是概念相似度計算的基礎。所有的義原根據上下位關系構成了一個樹狀的義原層次體系,這里采用劉群的公式計算語義相似度的方法。
??? 
??? 其中，S1、S2表示兩個義原, distance(S1, S2)表示它們的路徑長度，a是一個可調節的參數。在知網的知識描述語言中,在一些義原出現的位置都可能出現一個具體詞(概念),并用圓括號( )括起來。所以本文在計算相似度時還要考慮到具體詞和具體詞、具體詞和義原之間的相似度計算。理想的做法應該是先把具體詞還原成知網的語義表達式,然后再計算相似度。這樣做將導入函數的遞歸調用,有可能導致死循環,反而使算法變得很復雜。由于具體詞在知網的語義表達式中只占很小的比例,因此可以作如下處理:具體詞與義原的相似度定義為一個比較小的常數γ。具體詞和具體詞的相似度按兩個詞相同則為1否則為0。
2.2 概念相似度的計算
??? 由義原相似度可以計算概念相似度，詞語整體相似要建立在部分相似的基礎上。把一個復雜的整體分解成部分,通過計算部分之間的相似度得到整體的相似度。假設兩個整體A和B都可以分解成以下部分:A分解成A1, A2,…, An, B分解成B1, B2,…,Bm ,那么這些部分之間的對應關系就有m ×n 種。但并不是這些部分之間的相似度都對整體的相似度發生影響,所以應該選擇那些發生影響的部分之間的相似度,選擇出來后再進一步得到整體的相似度。在比較兩個整體的相似性時,首先要做的工作是對這兩個整體的各個部分之間建立起一一對應的關系,然后在這些對應的部分之間進行比較。如果某一部分的對應物為空則將任何義原(或具體詞)與空值的相似度定義為一個比較小的常數δ;其他整體的相似度通過部分的相似度加權平均得到[10]。對于實詞概念的語義表達式,可以將其分成四個部分:
??? 第一獨立義原描述式:將兩個概念的這一部分的相似度記為Sim1(S1,S2);
??? 其他獨立義原描述式:語義表達式中除第一獨立義原以外的所有其他獨立義原(或具體詞),將兩個概念的這一部分的相似度記為Sim2(S1,S2);
??? 關系義原描述式:語義表達式中所有的關系義原描述式,將兩個概念的這一部分的相似度記為Sim3(S1,S2);
??? 符號義原描述式:語義表達式中所有的符號義原描述式,將兩個概念的這一部分的相似度記為Sim4(S1,S2)。
??? 于是兩個概念語義表達式的整體相似度記為:
??? 
??? 其中,βi(1≤i≤4)是可調節的參數,且有β1+β2+β3+β4=1,β1≥β2≥β3≥β4 。后者反映了Sim1到Sim4對于總體相似度所起到的作用依次遞減。由于第一獨立義原描述式反映了一個概念最主要的特征,所以應該將其權值定義得相對比較大,一般應在0.5 以上。
3 實驗測試與分析
??? 以《操作系統》課程為實驗素材，選取2006級計算機專業學生的90份考卷中4道簡答題為例。每道試題的分數是10分，分別通過計算機自動評分和人工閱卷，所得到的評分結果進行分析，得到如下表所示：
?
??? 其中誤差為自動評分與人工評分所得分數之差。由于系統中分詞詞典中缺少某些專用詞匯或由于語句繁瑣較長，可能導致得分的偏差。但是對于主觀題來說,在人工評閱時，也受到教師情緒等諸多因素的影響，因此認為只要誤差小于1分的就認為得到了正確的評分。
??? 
??? 本文綜合運用了語句層次結構、句法、詞性、語義等特征來計算相似度，不僅考慮詞語的局部相似，還從語句的整體出發，考查了語句語義整體相似性，大大提高了相似度計算性能，降低了計算的時間復雜度，同時也提高了主觀題自動評分的準確性，具有一定的實用價值。
參考文獻
[1]?孟愛國，勝賢.一種網絡考試系統中主觀題自動評分的算法設計與實現[J]. 計算機與數字工程，2005，33(7):147-150
[2]?李彬，劉挺，秦兵.基于語義依存的漢語句子相似度計算[J]. 計算機應用研究, 2003，20(12): 15-17.
[3]?李素建.基于語義計算的語句相關度研究[J]. 計算機工程與應用, 2002,38(7):75-76.
[4]?李明琴，李涓子，王作英，等. 語義分析和結構化語言模型[J]. 軟件學報, 2005,16(9): 1523-1533.
[5]?高思丹,袁春風. 語句相似度計算在主觀題自動批改技術中的初步應用[J].計算機工程與應用, 2004,40 (14): 132 -135.
[6]?Levitin A . The Design and Analysis of Algorithm [M]. Beijing: Electronics Industry Press, 2003.
[7] LIN De Kang. An Information2Theoretic Definition of Similarity Semantic distance in Word Net [A] .In: Proceedings of the Fifteenth International Conference on Machine Learning [C].1998.
[8] 劉群，李素建.基于《知網》的詞匯語義相似度計[C]//第三屆漢語詞匯語義學研討會，臺北,2002，5.
[9]?董振東,董強.“知網”網站[DB/OL].http://www.keenage.com.
[10]?朱征宇,苑昆峰,陳杏環.一種基于最大權匹配計算的信息檢索方法[J]. 計算機工程與應用, 2007,43(33):176-179.