??? 摘 要：文字類主觀題的自動(dòng)評(píng)分是實(shí)現(xiàn)遠(yuǎn)程教育中在線考試系統(tǒng)的一個(gè)關(guān)鍵技術(shù)，由于其自動(dòng)評(píng)判具有相當(dāng)難度，使自動(dòng)評(píng)分系統(tǒng)中在對(duì)語(yǔ)句結(jié)構(gòu)、關(guān)鍵字匹配、詞性、詞義以及語(yǔ)義方面的判斷還存在很多問(wèn)題。通過(guò)對(duì)已有的算法分析，提出了一種方法，采用淺層次句法結(jié)構(gòu)分析和深層次語(yǔ)義分析相結(jié)合的算法計(jì)算相似度，該方法可以提高主觀題自動(dòng)評(píng)分的效率和準(zhǔn)確度，具有一定的實(shí)用價(jià)值。
??? 關(guān)鍵詞：自動(dòng)評(píng)分；動(dòng)態(tài)規(guī)劃；語(yǔ)句相似度；語(yǔ)義相似度

?

??? 目前，在線考試系統(tǒng)正在逐漸代替?zhèn)鹘y(tǒng)的考試系統(tǒng)，能否實(shí)現(xiàn)主觀題自動(dòng)評(píng)分是在線考試系統(tǒng)中一個(gè)重要環(huán)節(jié)。對(duì)于主觀題的考查，由于它的答題涉及到人工智能、模式識(shí)別以及自然語(yǔ)言理解等方面的理論知識(shí)，評(píng)閱時(shí)就需要解決很多技術(shù)上的問(wèn)題，因而成為阻礙在線考試系統(tǒng)發(fā)展的一個(gè)技術(shù)難點(diǎn)。
??? 當(dāng)前的主觀題自動(dòng)評(píng)分算法中，多數(shù)使用的是對(duì)學(xué)生答案和標(biāo)準(zhǔn)答案中關(guān)鍵字匹配來(lái)計(jì)算語(yǔ)句相似度，如基于向量空間模型TF-IDF方法、詞性詞序相結(jié)合的方法以及基于語(yǔ)義依存樹(shù)等^[1-4]。已有的這些方法要么從句子的表層結(jié)構(gòu)信息進(jìn)行匹配而忽略了語(yǔ)句語(yǔ)義分析，要么就是從語(yǔ)義分析而影響了整體語(yǔ)句的相似性，這些都會(huì)影響到自動(dòng)評(píng)分計(jì)算的精確度。由于漢語(yǔ)語(yǔ)言的結(jié)構(gòu)和語(yǔ)義的復(fù)雜性，一種意思可以用多種形式和多種關(guān)鍵字表達(dá)，單從一方面很難對(duì)語(yǔ)句的意思作出準(zhǔn)確的判斷，因此提出了一種新的主觀題自動(dòng)評(píng)分算法策略，主要思想是采用淺層次句法結(jié)構(gòu)分析和深層次語(yǔ)義分析相結(jié)合的算法計(jì)算相似度，將這兩種思想結(jié)合起來(lái)使用可以互補(bǔ)不足，提高了主觀題自動(dòng)評(píng)分的準(zhǔn)確度。
1 語(yǔ)句相似度計(jì)算算法
??? 在主觀題自動(dòng)批改系統(tǒng)中，語(yǔ)句相似度是用來(lái)評(píng)價(jià)學(xué)生答案和標(biāo)準(zhǔn)答案的接近程度。針對(duì)漢語(yǔ)的特殊性和機(jī)器翻譯領(lǐng)域內(nèi)一些對(duì)語(yǔ)句相似度的研究，采用動(dòng)態(tài)規(guī)劃法來(lái)計(jì)算語(yǔ)句相似度，主要思想是對(duì)語(yǔ)句進(jìn)行層次句法分析。首先用正向最大匹配（MM）和基于詞頻統(tǒng)計(jì)的方法對(duì)句子分詞，將分詞后得到的語(yǔ)句視為詞的向量，分別對(duì)各個(gè)關(guān)鍵詞進(jìn)行匹配。然后在此基礎(chǔ)上利用動(dòng)態(tài)規(guī)劃算法求出最優(yōu)路徑及語(yǔ)句相似度^[5]。
1.1 相關(guān)定義
??? 令P表示標(biāo)準(zhǔn)答案中的某一語(yǔ)句，Q表示學(xué)生答案中的某一語(yǔ)句。P和Q分別表示如下：P={P₁,P₂,…,P_m},Q={Q₁,Q₂,…,Q_m},其中P_i表示P語(yǔ)句中的一個(gè)關(guān)鍵詞，Q_j表示語(yǔ)句Q語(yǔ)句中的一個(gè)關(guān)鍵詞，且P_i=P_mi U P_gi, Q_j=Q_mj U Q_gj，其中P_mi表示語(yǔ)句P中第i個(gè)詞的詞義集合，P_gi表示語(yǔ)句P中第i個(gè)詞的詞性集合；同理Q_mj表示語(yǔ)句Q中第j個(gè)詞的詞義集合，Q_gj表示語(yǔ)句Q中第j個(gè)詞的詞性集合。為了便于進(jìn)一步討論給出以下幾個(gè)定義：
??? 定義1：詞義、詞性相似度。詞義、詞性相似度可分別表示為：SM_ij=SM(P_mi,Q_mj)，SG_ij=SM(P_gi,Q_gj)。
??? 定義2：關(guān)鍵詞相似度。關(guān)鍵詞相似度W_ij=a×SM_ij+β×SG_ij其中a、β分別為詞義、詞性相似度的權(quán)值。
??? 定義3：詞向量的相似矩陣。用定義2計(jì)算出語(yǔ)句P和Q的所有關(guān)鍵詞的相似度W_ij(i=1,2,…,m;j=1,2,j=i=1,2,…,n),形成一個(gè)m×n矩陣M,稱該矩陣為語(yǔ)句向量的相似矩陣。

???

??? 定義4：拓展詞向量相似矩陣,對(duì)矩陣M進(jìn)行如下拓展，形成矩陣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+W_ij, M'_i,j-1+γ,M'_i-1,j+γ},其中，γ表示詞位置不對(duì)應(yīng)時(shí)的懲罰系數(shù)。
1.2 語(yǔ)句相似度求解算法
??? （1）利用動(dòng)態(tài)規(guī)劃法先求出M'矩陣^[6]。
??? （2）M'矩陣的初始化
??? 創(chuàng)建一個(gè)(m+1,n+1)矩陣，矩陣的行表示標(biāo)準(zhǔn)答案語(yǔ)句P的每個(gè)詞，矩陣的列表示學(xué)生答案語(yǔ)句Q的每個(gè)詞，利用定義4進(jìn)行初始化，將M'矩陣的M'_i,0,M'_0,j設(shè)置為0.其中i=0,1,2,…,m; j=0,1,2,…,n。
??? （3）利用定義1、2、3、4依次求解M'矩陣中的每個(gè)元素M'_i,j。
??? （4）求解最優(yōu)相似矩陣
??? 先從點(diǎn)(m,n)開(kāi)始，到(1,1)結(jié)束。在點(diǎn)（i,j）上選擇M'_i-1,j-1+W_ij,M'_i,j-1+γ,M'_i-1,j+γ最大者為最優(yōu)點(diǎn)，所對(duì)應(yīng)的M_{x, y}作為路徑的前一個(gè)節(jié)點(diǎn)(x,y)。如果出現(xiàn)三者中兩部分值相同且最大時(shí)，若該值在斜路徑上則選擇斜路徑上(i-1,j-1)作為路徑的前一個(gè)節(jié)點(diǎn)；若不在斜路徑上，優(yōu)選水平方面(i-1,j)作為路徑的前一個(gè)節(jié)點(diǎn)；依次遞推則選擇一條最優(yōu)路徑。這樣得到的路徑上就是一條最優(yōu)的路徑，路徑上最后一個(gè)點(diǎn)的值M'_m,n表示了語(yǔ)句中所以詞的相似度之和。
??? 設(shè)L是標(biāo)準(zhǔn)答案語(yǔ)句的詞數(shù)，則語(yǔ)句相似度為Sim=M’_m,n/L。
2 語(yǔ)義相似度計(jì)算算法
??? Dekang Lin^[7]認(rèn)為任何兩個(gè)事物的相似度取決于它們的共性(Commonality)和個(gè)性(Differentces)，然后從信息理論的角度給出任意兩個(gè)事物相似度的通用公式:

???

??? 其中分子是描述A、B共性所需要的信息量的大小;分母是完整地描述出A、B所需要的信息量大小。劉群^[8]認(rèn)為兩個(gè)詞語(yǔ)的相似度是它們?cè)诓煌纳舷挛闹锌梢曰ハ嗵鎿Q且不改變文本的句法語(yǔ)義結(jié)構(gòu)的可能性大小。在本文中計(jì)算語(yǔ)義相似度是利用《知網(wǎng)》中詞語(yǔ)相似度的定義[9]，可以把詞語(yǔ)語(yǔ)義相似度的計(jì)算歸結(jié)為“概念”相似度的計(jì)算;“概念”的相似度由描述它的“義原”的相似度得到。詞語(yǔ)存在著一詞多義的現(xiàn)象,知網(wǎng)中的一詞多義表現(xiàn)為單個(gè)詞語(yǔ)有多個(gè)概念,每個(gè)概念由一項(xiàng)定義來(lái)描述。比如:“打”在“打架”，“打太極”，“打獵”中的意義各不相同,知網(wǎng)中對(duì)應(yīng)的概念描述分別是:
??? DEF = fight| 爭(zhēng)斗
??? DEF = exercise| 鍛煉,sport| 體育
??? DEF = catch| 捉住, # animal| 獸
??? 詞語(yǔ)語(yǔ)義相似度的計(jì)算,嚴(yán)格來(lái)講應(yīng)該是計(jì)算概念之間的語(yǔ)義相似度。本文中采用劉群的思路,認(rèn)為兩個(gè)詞語(yǔ)的語(yǔ)義相似度是其所有概念之間相似度的最大值。
??? Sim(c1,c2)=maxSim(C_1i,C_2j)(i=1,2,…,m;j=1,2,…,n)
??? 其中, C_1i是詞C₁的m項(xiàng)概念,C_2j是C₂的n項(xiàng)概念。這樣就把兩個(gè)詞語(yǔ)之間的相似度問(wèn)題歸結(jié)到了兩個(gè)概念之間的相似度問(wèn)題。本文利用語(yǔ)句相似度中分詞方法將詞語(yǔ)標(biāo)注為概念,然后再對(duì)概念計(jì)算相似度。
2.1 義原相似度的計(jì)算
??? 由于所有的概念都最終歸結(jié)于用義原來(lái)表示, 詞語(yǔ)整體相似度由部分相似度合成的，所以義原的相似度計(jì)算是概念相似度計(jì)算的基礎(chǔ)。所有的義原根據(jù)上下位關(guān)系構(gòu)成了一個(gè)樹(shù)狀的義原層次體系,這里采用劉群的公式計(jì)算語(yǔ)義相似度的方法。

???

??? 其中，S₁、S₂表示兩個(gè)義原, distance(S₁, S₂)表示它們的路徑長(zhǎng)度，a是一個(gè)可調(diào)節(jié)的參數(shù)。在知網(wǎng)的知識(shí)描述語(yǔ)言中,在一些義原出現(xiàn)的位置都可能出現(xiàn)一個(gè)具體詞(概念),并用圓括號(hào)( )括起來(lái)。所以本文在計(jì)算相似度時(shí)還要考慮到具體詞和具體詞、具體詞和義原之間的相似度計(jì)算。理想的做法應(yīng)該是先把具體詞還原成知網(wǎng)的語(yǔ)義表達(dá)式,然后再計(jì)算相似度。這樣做將導(dǎo)入函數(shù)的遞歸調(diào)用,有可能導(dǎo)致死循環(huán),反而使算法變得很復(fù)雜。由于具體詞在知網(wǎng)的語(yǔ)義表達(dá)式中只占很小的比例,因此可以作如下處理:具體詞與義原的相似度定義為一個(gè)比較小的常數(shù)γ。具體詞和具體詞的相似度按兩個(gè)詞相同則為1否則為0。
2.2 概念相似度的計(jì)算
??? 由義原相似度可以計(jì)算概念相似度，詞語(yǔ)整體相似要建立在部分相似的基礎(chǔ)上。把一個(gè)復(fù)雜的整體分解成部分,通過(guò)計(jì)算部分之間的相似度得到整體的相似度。假設(shè)兩個(gè)整體A和B都可以分解成以下部分:A分解成A₁, A₂,…, A_n, B分解成B₁, B₂,…,B_m ,那么這些部分之間的對(duì)應(yīng)關(guān)系就有m ×n 種。但并不是這些部分之間的相似度都對(duì)整體的相似度發(fā)生影響,所以應(yīng)該選擇那些發(fā)生影響的部分之間的相似度,選擇出來(lái)后再進(jìn)一步得到整體的相似度。在比較兩個(gè)整體的相似性時(shí),首先要做的工作是對(duì)這兩個(gè)整體的各個(gè)部分之間建立起一一對(duì)應(yīng)的關(guān)系,然后在這些對(duì)應(yīng)的部分之間進(jìn)行比較。如果某一部分的對(duì)應(yīng)物為空則將任何義原(或具體詞)與空值的相似度定義為一個(gè)比較小的常數(shù)δ;其他整體的相似度通過(guò)部分的相似度加權(quán)平均得到^[10]。對(duì)于實(shí)詞概念的語(yǔ)義表達(dá)式,可以將其分成四個(gè)部分:
??? 第一獨(dú)立義原描述式:將兩個(gè)概念的這一部分的相似度記為Sim1(S1,S2);
??? 其他獨(dú)立義原描述式:語(yǔ)義表達(dá)式中除第一獨(dú)立義原以外的所有其他獨(dú)立義原(或具體詞),將兩個(gè)概念的這一部分的相似度記為Sim2(S1,S2);
??? 關(guān)系義原描述式:語(yǔ)義表達(dá)式中所有的關(guān)系義原描述式,將兩個(gè)概念的這一部分的相似度記為Sim3(S1,S2);
??? 符號(hào)義原描述式:語(yǔ)義表達(dá)式中所有的符號(hào)義原描述式,將兩個(gè)概念的這一部分的相似度記為Sim4(S1,S2)。
??? 于是兩個(gè)概念語(yǔ)義表達(dá)式的整體相似度記為:
??? 　　
??? 其中,β_i(1≤i≤4)是可調(diào)節(jié)的參數(shù),且有β₁+β₂+β₃+β₄=1,β₁≥β₂≥β₃≥β₄ 。后者反映了Sim1到Sim4對(duì)于總體相似度所起到的作用依次遞減。由于第一獨(dú)立義原描述式反映了一個(gè)概念最主要的特征,所以應(yīng)該將其權(quán)值定義得相對(duì)比較大,一般應(yīng)在0.5 以上。
3 實(shí)驗(yàn)測(cè)試與分析
??? 以《操作系統(tǒng)》課程為實(shí)驗(yàn)素材，選取2006級(jí)計(jì)算機(jī)專業(yè)學(xué)生的90份考卷中4道簡(jiǎn)答題為例。每道試題的分?jǐn)?shù)是10分，分別通過(guò)計(jì)算機(jī)自動(dòng)評(píng)分和人工閱卷，所得到的評(píng)分結(jié)果進(jìn)行分析，得到如下表所示：

?

??? 其中誤差為自動(dòng)評(píng)分與人工評(píng)分所得分?jǐn)?shù)之差。由于系統(tǒng)中分詞詞典中缺少某些專用詞匯或由于語(yǔ)句繁瑣較長(zhǎng)，可能導(dǎo)致得分的偏差。但是對(duì)于主觀題來(lái)說(shuō),在人工評(píng)閱時(shí)，也受到教師情緒等諸多因素的影響，因此認(rèn)為只要誤差小于1分的就認(rèn)為得到了正確的評(píng)分。
???
??? 本文綜合運(yùn)用了語(yǔ)句層次結(jié)構(gòu)、句法、詞性、語(yǔ)義等特征來(lái)計(jì)算相似度，不僅考慮詞語(yǔ)的局部相似，還從語(yǔ)句的整體出發(fā)，考查了語(yǔ)句語(yǔ)義整體相似性，大大提高了相似度計(jì)算性能，降低了計(jì)算的時(shí)間復(fù)雜度，同時(shí)也提高了主觀題自動(dòng)評(píng)分的準(zhǔn)確性，具有一定的實(shí)用價(jià)值。
參考文獻(xiàn)
[1]?孟愛(ài)國(guó)，勝賢.一種網(wǎng)絡(luò)考試系統(tǒng)中主觀題自動(dòng)評(píng)分的算法設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)與數(shù)字工程，2005，33(7):147-150
[2]?李彬，劉挺，秦兵.基于語(yǔ)義依存的漢語(yǔ)句子相似度計(jì)算[J]. 計(jì)算機(jī)應(yīng)用研究, 2003，20(12): 15-17.
[3]?李素建.基于語(yǔ)義計(jì)算的語(yǔ)句相關(guān)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2002,38(7):75-76.
[4]?李明琴，李涓子，王作英，等. 語(yǔ)義分析和結(jié)構(gòu)化語(yǔ)言模型[J]. 軟件學(xué)報(bào), 2005,16(9): 1523-1533.
[5]?高思丹,袁春風(fēng). 語(yǔ)句相似度計(jì)算在主觀題自動(dòng)批改技術(shù)中的初步應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用, 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] 劉群，李素建.基于《知網(wǎng)》的詞匯語(yǔ)義相似度計(jì)[C]//第三屆漢語(yǔ)詞匯語(yǔ)義學(xué)研討會(huì)，臺(tái)北,2002，5.
[9]?董振東,董強(qiáng).“知網(wǎng)”網(wǎng)站[DB/OL].http://www.keenage.com.
[10]?朱征宇,苑昆峰,陳杏環(huán).一種基于最大權(quán)匹配計(jì)算的信息檢索方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2007,43(33):176-179.