一種改進(jìn)的句子相似度計(jì)算模型

1、第35卷第6期電子科技大學(xué)學(xué)報(bào)V ol.35 No.62006年12月 Journal of University of Electronic Science and Technology of China Dec. 2006一種改進(jìn)的句子相似度計(jì)算模型楊思春(安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院安徽馬鞍山 243002【摘要】在基于實(shí)例的機(jī)器翻譯中,句子相似度計(jì)算是實(shí)例匹配的有效機(jī)制。該文對基于相同詞的句子相似模型作進(jìn)一步的改進(jìn),包括關(guān)鍵詞抽取,以及在句子相似度的定義中引入同義詞的情形。實(shí)驗(yàn)結(jié)果表明,改進(jìn)方法比原方法具有較高的準(zhǔn)確率。關(guān)鍵詞自然語言處理; 基于實(shí)例的機(jī)器翻譯; 句子相似度; 基于詞中圖分類

2、號TP391 文獻(xiàn)標(biāo)識碼 AAn Improved Model for Sentence Similarity ComputingYANG Si-chun(School of Computer, Anhui University of Technology Maanshan Anhui 243002Abstract In example based machine translation, sentence similarity computing is an effective mechanism for example matching. Aiming at a sentence simi

3、larity model based on same words, an improved method is put forward, including the extraction of keywords, and the induction of synonyms in sentence similarity definition. Experiment result shows that the improved method has better accuracy than the former.Key words natural language processing; exam

4、ple based machine translation; sentence similarity; based on word基于實(shí)例的機(jī)器翻譯(Example Based Machine Translation,EBMT是以雙語對齊的實(shí)例庫為主要知識源,輸入一個(gè)待翻譯的源語言句子,從實(shí)例庫中查找與輸入句最相似的例句,再模仿例句的譯文來實(shí)現(xiàn)輸入句的翻譯。在EBMT中,實(shí)例匹配是關(guān)鍵,直接關(guān)系到系統(tǒng)本身的翻譯質(zhì)量。實(shí)現(xiàn)實(shí)例匹配的有效機(jī)制是進(jìn)行句子相似度計(jì)算1-2,目前主要有基于詞3-5和基于句法語義分析6-7的兩類方法。兩類方法各有優(yōu)缺點(diǎn),基于詞的方法簡單、流行,但由于僅利用句子的表層信息,

5、即組成句子的有關(guān)詞匯的詞法和語義信息,因此,在判斷句子整體結(jié)構(gòu)相似方面有欠缺;基于句法語義分析的方法折衷考慮句子的組成詞匯語義信息與整體框架結(jié)構(gòu)信息,但在折衷考慮的層次上較難把握。本文研究基于詞的句子相似度計(jì)算問題,并在文獻(xiàn)5的基礎(chǔ)上提出了一種改進(jìn)的方法。1 基于詞的句子相似度計(jì)算基于詞的方法是目前最簡單、最流行的方法,依據(jù)詞的形態(tài)變化、同義詞、反義詞以及更進(jìn)一步的語義距離來判斷孤立詞之間的相似度,再通過這種詞間相似度的不同組合來確定句子間的相似度。文獻(xiàn)3利用同義詞表計(jì)算兩句詞之間的語義距離,進(jìn)而計(jì)算兩句之間的相似度。文獻(xiàn)4通過正反雙向比較兩句相同詞的個(gè)數(shù)及其位置關(guān)系,得到一個(gè)轉(zhuǎn)換表達(dá)式和子塊

6、庫,再通過系統(tǒng)預(yù)定義的翻譯模式和限制條件實(shí)現(xiàn)兩句相似度的計(jì)算。文獻(xiàn)5通過比較兩句相同詞的個(gè)數(shù)及其位置關(guān)系,得到兩句的詞形相似度和詞序相似度,再通過詞形相似度和詞序相似度計(jì)算兩句的相似度。文獻(xiàn)4-5采用的方法實(shí)質(zhì)上是相同的,均通過比較相同詞的個(gè)數(shù)及其位置關(guān)系來計(jì)算兩句的相似度。但在相似度的定義中,僅考慮了形態(tài)上相同的詞,而沒有考慮同義詞的情形。例如,對兩個(gè)簡單的句子“我/ 是/ 老師/ 。/”與“他/ 為/ 學(xué)生/。/”,按照文獻(xiàn)5中的方法計(jì)算則相似度很低(只有0.1,實(shí)際上這兩句收稿日期:2004 09 01基金項(xiàng)目:安徽省教育廳自然科學(xué)基金資助項(xiàng)目(2004kj060;安徽省高等學(xué)校青年教師

7、科研計(jì)劃資助項(xiàng)目(2004jq131作者簡介:楊思春(1970 ,男,碩士,副教授,主要從事自然語言處理與機(jī)器翻譯方面的研究.第6期 楊思春: 一種改進(jìn)的句子相似度計(jì)算模型 957 是比較相似的。究其原因,主要是沒有考慮兩句中的同義詞“是”和“為”。另外,也沒有考慮任何句法結(jié)構(gòu)信息。因此,在算法實(shí)現(xiàn)上雖然較為簡單,但準(zhǔn)確率卻不高。基于詞的方法依據(jù)句子的表層信息,通過對這些表層信息的加工也可以獲得一些有用的句法結(jié)構(gòu)信息,如抽取一些能夠近似表達(dá)部分句法結(jié)構(gòu)信息的關(guān)鍵性的詞(以下簡稱關(guān)鍵詞。在此基礎(chǔ)上進(jìn)行句子相似度計(jì)算,就會具有較高的準(zhǔn)確率。本文針對以上兩點(diǎn)作了進(jìn)一步的改進(jìn)。2 一種改進(jìn)的方法本文對

8、文獻(xiàn)5中的句子相似模型作了進(jìn)一步改進(jìn),包括關(guān)鍵詞抽取,以及在句子相似度的定義中考慮同義詞的情形。令inp 為待翻譯的輸入句,exa 為對應(yīng)的m 個(gè)例句中的一個(gè),先分別抽取inp 和exa 中所有的名詞、代詞、動詞或形容詞,并組成相應(yīng)的關(guān)鍵詞序列,再求出inp 和exa 中關(guān)鍵詞序列的相似度,最后選取大于規(guī)定閾值的最大相似度例句作為輸入句的最相似例句。2.1 關(guān)鍵詞抽取由語言學(xué)知識可知,任何句子都是由關(guān)鍵成分(主、謂、賓等和修飾成分(定、狀、補(bǔ)等構(gòu)成的。關(guān)鍵成分對句子起主要作用,修飾成分對句子起次要作用。進(jìn)行句子相似度計(jì)算時(shí),只要考慮句中的關(guān)鍵成分?；谠~的方法不考慮句法結(jié)構(gòu)分析,因此,不能確定

9、句子的內(nèi)部成分,包括關(guān)鍵成分和修飾成分。在通常情況下,一個(gè)句子中作主語和賓語的多為名詞或代詞,作謂語的多為動詞或形容詞。因此,可以將一個(gè)句子中的所有名詞、代詞、動詞和形容詞作為關(guān)鍵詞,并在計(jì)算句子相似度時(shí)只考慮這些關(guān)鍵詞。例如,句子“我/ 當(dāng)然/ 愿意/ 了解/ 她們/ 的/ 要求/ 。/”的關(guān)鍵詞序列為 “我/ 愿意/ 了解/ 她們/ 要求/ 。/”。對于特定句中的某個(gè)名詞、代詞、動詞或形容詞,不一定就是該句中的主語、賓語或謂語成分,但相對于句中所有的詞構(gòu)成的詞序列而言,關(guān)鍵詞序列卻具有一定的句法結(jié)構(gòu)信息表達(dá)能力,至少可以了解句子中的哪些詞在組成句子框架結(jié)構(gòu)方面是比較重要的。在此基礎(chǔ)上進(jìn)行相

10、似度計(jì)算,比一般基于詞的方法準(zhǔn)確一些。對句子進(jìn)行關(guān)鍵詞抽取的算法如下:算法 1 關(guān)鍵詞抽取算法令S 為句子,w 為S 中任一詞,S 為S 中關(guān)鍵詞序列。(1 for S 中任一詞w do ;if w 為名詞、代詞、動詞或形容詞,then 抽取w ;讀入下一詞;end for 。(2 由S 中抽取的所有關(guān)鍵詞組成關(guān)鍵詞序列S 。2.2 有關(guān)定義和計(jì)算按上述方法對句子進(jìn)行關(guān)鍵詞抽取以后,可以依據(jù)文獻(xiàn)5中的句子相似模型實(shí)現(xiàn)任意兩個(gè)句子之間的相似度計(jì)算。本文在文獻(xiàn)5定義的句子相似度基礎(chǔ)上進(jìn)一步考慮了同義詞的情形,有關(guān)定義和計(jì)算如下:定義 1 詞形相似度反映兩個(gè)句子形態(tài)上的相似程度,以兩個(gè)句子中所含相同

11、詞或同義詞的個(gè)數(shù)來衡量。設(shè)S 1、S 2為兩個(gè)句子,則S 、S 的詞形相似度為:12 (S , S Sim word 12=2*(SameWord(S 1, S 2/(Len(S 1+ Len(S 2式中 SameWord(S , S 12為S 、S 中所含相同詞或同義詞的個(gè)數(shù);Len(S 為句子S 中所含詞的個(gè)數(shù)。12定義 2 詞序相似度反映兩個(gè)句子中所含相同詞或同義詞在位置關(guān)系上的相似程度,以兩個(gè)句子中所含相同詞或同義詞的相鄰順序逆向的個(gè)數(shù)來衡量。設(shè)S 1、S 為兩個(gè)句子,OnceWord(S , S 212為S 1、S 2中所含僅一次的相同詞或同義詞的集合,P first (S 1, S

12、 2為OnceWord(S 1, S 2中的詞在S 1中的位置序號構(gòu)成的向量,P second (S 1, S 2為P first (S 1, S 2中的分量按對應(yīng)詞在S 為P 中的次序排序生成的向量,RevOrd(S 21, S 2second (S 1, S 各相鄰分量的逆序數(shù),則S 21、S 的詞序相似度為:2電子科技大學(xué)學(xué)報(bào)第35卷9581(RevOrd(S1, S2 /(|OnceWord(S1, S2|1|OnceWord(S1, S2|>1Sim ord(S1, S2 =1|OnceWord(S1, S2|=10|OnceWord(S1, S2|=0定義 3 句子相似度反映

13、兩個(gè)句子之間的相似程度。通常為一個(gè)01之間的數(shù)值,0表示不相似,1表示完全相似,數(shù)值越大表示兩句越相似。令S為兩個(gè)句子,則句子相似度為:、S12Sim(S121*Sim word122* Sim ord(S1, S 2, S=(S, S+ 式中 Sim word(S1, S(S, S為S、S2的詞形相似度;Sim ord12為詞序相似度;1、2為常數(shù),且滿足1+2=1。本21文取1=0.9,2=0.1。2.3 算法描述算法 2 一種改進(jìn)的算法令輸入句為inp,例句為exa(個(gè)數(shù)為m個(gè),輸入句inp中關(guān)鍵詞序列為inp,例句exa中關(guān)鍵詞序列為exa,(1 抽取輸入句inp中的關(guān)鍵詞,得到inp

14、中的關(guān)鍵詞序列inp;抽取每個(gè)例句exa中的關(guān)鍵詞,得到exa中的關(guān)鍵詞序列exa;(2 求出inp、exa的詞形相似度和詞序相似度;(3 求出inp、exa的句子相似度;(4 選擇大于規(guī)定閾值的最大相似度例句作為輸入句的最相似實(shí)例。與原算法相比,該算法中的關(guān)鍵詞抽取部分涉及分詞與詞性標(biāo)注(原算法僅涉及分詞,在計(jì)算詞形相似度時(shí)還需要借助一部同義詞詞典。該算法具有以下特點(diǎn):(1 簡單,所利用的信息仍為句子的表層信息。(2 保留了原算法的優(yōu)點(diǎn),可以保證句子中的分句或短語整體移動后仍與原來的句子相似。(3 比原算法準(zhǔn)確一些,所抽取的關(guān)鍵詞可以近似地表達(dá)部分句法結(jié)構(gòu)信息。2.4 舉例下面給出說明算法的

15、實(shí)現(xiàn)和處理流程的例子。inp:我/ 當(dāng)然/ 愿意/ 了解/ 她們/ 的/ 要求/ 。/exa1:我/ 認(rèn)為/ 我/ 當(dāng)然/ 愿意/ 了解/ 她們/ 的/ 要求/ 。/exa2:當(dāng)然/ 我/ 想/ 知道/ 你/ 的/ 意見/ 。/exa3:我/ 很/ 想/ 知道/ 他/ 的/ 決定/ 是/ 什么/ 。/第1步分別抽取inp與exai(i=1,2,3中的關(guān)鍵詞,組成相應(yīng)的關(guān)鍵詞序列。inp:我/ 愿意/ 了解/ 她們/ 要求/ 。/exa1:我/ 認(rèn)為/ 我/ 愿意/ 了解/ 她們/ 要求/ 。/exa2:我/ 想/ 知道/ 你/ 意見/ 。/exa3:我/ 想/ 知道/ 他/ 決定/ 是/ 什么

16、/ 。/第2步分別求出inp與exai(i=1,2,3的相似度。inp與exa1的相似度為:0.9×2×6÷(6+8+0.1×1=0.874;inp與exa2的相似度為:0.9×2×3÷(6+6+0.1×1=0.550 (考慮“了解”與“知道”是同義詞;inp與exa3的相似度為:0.9×2×3÷(6+8+0.1×1=0.485 (考慮“了解”與“知道”是同義詞;因此,inp與exa1相似。3 實(shí)驗(yàn)結(jié)果以人工分詞的50個(gè)漢語句子作為測試集,平均句長為11.2,并按相似程度分為

17、16類,每類有34個(gè)彼此相似的句子。對測試集中每個(gè)句子,分別以文獻(xiàn)5中的方法和本文的方法計(jì)算其與其他所有句子的相似度,僅當(dāng)相似度最大的句子與人工評判的最相似句子一致時(shí),才認(rèn)為該句的相似度計(jì)算結(jié)果正確。第6期楊思春: 一種改進(jìn)的句子相似度計(jì)算模型959實(shí)驗(yàn)結(jié)果如表1所示。由此可見,改進(jìn)方法的準(zhǔn)確率明顯高于原方法,這主要得益于改進(jìn)方法是基于關(guān)鍵詞抽取來進(jìn)行相似度計(jì)算,近似地考慮了部分句法結(jié)構(gòu)信息。通過對相似度計(jì)算結(jié)果不正確的另外15個(gè)句子的分析,發(fā)現(xiàn)錯(cuò)誤的原因主要在于這些句子的長度較長、結(jié)構(gòu)較為復(fù)雜,所抽取的關(guān)鍵詞在近似表達(dá)句法結(jié)構(gòu)信息方面能力減弱,進(jìn)而在句子相似度計(jì)算方面,準(zhǔn)確率也隨之降低。同時(shí)

18、,通過關(guān)鍵詞抽取的方法計(jì)算句子相似度,僅在一定程度上改善了基于詞的方法的準(zhǔn)確率,要實(shí)現(xiàn)準(zhǔn)確率的全面提高,必須借助較完全的句法語義分析,例如骨架依存分析表1 實(shí)驗(yàn)結(jié)果結(jié)果正確的句子數(shù)準(zhǔn)確率/ (%計(jì)算方法測試句子數(shù)50 31 62 原方法50 35 70 改進(jìn)方法6和語義依存分析7。4 結(jié)論通過關(guān)鍵詞抽取可以明顯地提高基于詞的句子相似度計(jì)算方法的準(zhǔn)確率。自動分詞和詞性標(biāo)注的質(zhì)量直接影響該方法的準(zhǔn)確率;關(guān)鍵詞的抽取質(zhì)量直接影響該方法的準(zhǔn)確率。本文研究工作得到了南京大學(xué)計(jì)算機(jī)系機(jī)器翻譯研究室陳家駿教授的幫助,在此表示感謝。參考文獻(xiàn)1 Satoshi S, Francis B, Yamato T. A

19、 hybrid rule and example based method for machine translationC/Proceedings of the 4thNatural Language Processing Pacific Rim Symposium, Puket, 1997.2 Malavazos C, Piperidis S. Application of analogical modeling to example based machine translationC/Proceedings of the 18thInternational Conference of

20、Computational Linguistics, Saarbrucken, 2000.3 張民, 李生, 趙鐵軍, 等. 一種漢語句子間相似度的度量算法及其實(shí)現(xiàn)C/計(jì)算語言學(xué)進(jìn)展與應(yīng)用, 北京, 1995.4 王長勝, 劉群. 基于實(shí)例的漢英機(jī)器翻譯系統(tǒng)研究與實(shí)現(xiàn)J. 計(jì)算機(jī)工程與應(yīng)用, 2002, 38(8: 126-127.5 呂學(xué)強(qiáng), 任飛亮, 黃志丹, 等. 句子相似模型和最相似句子查找算法J. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版, 2003, 24(6: 531-534.6 穗志方, 俞士汶. 基于骨架依存樹的語句相似度計(jì)算模型C/中文信息處理國際會議(ICCIP98, 北京, 1998.7 李彬, 劉挺, 秦兵, 等. 基于語義依存的漢語句子相似度計(jì)算J. 計(jì)算機(jī)應(yīng)用研究,