基于動(dòng)態(tài)規(guī)劃的簡(jiǎn)單語義單元詞義消歧

劉運(yùn)通，孫 華

（安陽師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，河南安陽455000）

0 引 言

當(dāng)前，在自然語言處理領(lǐng)域，語義信息的作用越來越被重視，學(xué)者們對(duì)利用語義來進(jìn)行詞義消岐，做了許多有益的探索性研究。文獻(xiàn)［1］研究了基于利用How Net語義相關(guān)度進(jìn)行詞匯語義消岐方法；文獻(xiàn)［2］研究了基于Word Net語義相關(guān)度的詞匯語義消岐方法；文獻(xiàn)［3］研究了基于維基的兩階段語義消歧方法；文獻(xiàn)［4］研究了基于詞語距離的網(wǎng)絡(luò)圖的語義消歧；文獻(xiàn)［5］研究了基于知網(wǎng)的中文信息結(jié)構(gòu)消歧研究；文獻(xiàn)［6］研究了基于知網(wǎng)詞匯語義相關(guān)度計(jì)算的消歧方法；文獻(xiàn)［7］研究了基于語義相關(guān)度的語義模型求解；文獻(xiàn)［8］研究了基于Word Net的詞匯語義消岐模型；文獻(xiàn)［9］研究了基于Word Net語義樹的語義消岐方法；文獻(xiàn)［10］研究了基于Word Net語義關(guān)系網(wǎng)的信息處理。

這些研究雖然取得很多成果，但并沒有形成一個(gè)比較成熟、有效的計(jì)算方法，消岐效果依然有很大的提高余地。為了能夠通過語義計(jì)算，實(shí)現(xiàn)高效、準(zhǔn)確的語義消歧，我們提出了一種基于動(dòng)態(tài)規(guī)劃的簡(jiǎn)單語義單元詞義消歧方法。先闡述了語義相關(guān)度計(jì)算模型，提出簡(jiǎn)單語義單元的概念，分析了簡(jiǎn)單語義單元的特點(diǎn)；采用動(dòng)態(tài)規(guī)劃的方法，依次求出每個(gè)詞匯的所有義項(xiàng)的最大生成樹變量；最后求出語義修飾關(guān)系完全圖的最大生成樹；可以很容易地將最大生成樹轉(zhuǎn)化為最佳的語法分析方案和實(shí)現(xiàn)詞義消歧。

1 基本理論

1.1 語義相關(guān)度計(jì)算模型

假設(shè)一個(gè)語句（CS）中的任意實(shí)詞Wi（除去謂語中心詞）均語義修飾于另外一個(gè)實(shí)詞WGi，稱WGi是Wi語義修飾目標(biāo)，用函數(shù)match（Wi，WGi）來表示其語義相關(guān)度。

假設(shè)語句CS有m種不同的語法分析方案，在其中第i種語法分析方案Ai的情況下:假設(shè)V為謂語中心詞，S為V的施動(dòng)者，O為V的承受者，Wi是語句中的一個(gè)實(shí)詞且！（Wi∈｛S，V，O｝），WGi是Wi的語義修飾目標(biāo)，那么，語句的語義相關(guān)度fAi（針對(duì)語法分析方案Ai）可以用式（1）來表示（如圖1所示）

其中，S和O的語義修飾目標(biāo)是V，n是實(shí)詞的個(gè)數(shù)（不包括S、V、O），KSVO為權(quán)值系數(shù)（KSVO＞1），KSVO應(yīng)正比于語句的長度。

圖1 語義相關(guān)度計(jì)算模型

值得注意的是:虛詞不參與計(jì)算，副詞、代詞、數(shù)詞、量詞被按照實(shí)詞計(jì)算。

最佳結(jié)果選擇規(guī)則:假設(shè)一個(gè)語句具有m種語法分析方案，最符合語義邏輯的語法分析方案Ai滿足式（2）的條件

即語義相關(guān)度最大的語法分析方案是最佳語法分析方案。

1.2 簡(jiǎn)單語義單元

假設(shè)語句CS的語義結(jié)構(gòu)為:CS→LSLOLVL，S、V、O中間的段落為L（如圖2所示）；并假定分段L已經(jīng)被劃分到了“不包含從句”的程度，則可以根據(jù)L內(nèi)各部分語義作用的不同，將L劃分為:前置定語（用AB表示）、后置定語（用AA表示）、狀語（用PD表示）。

定義1（簡(jiǎn)單語義單元） 在把S、V、O中間的“不包含從句”的分段L劃分為AB、AA或PD的情況下，AB＋S（或O）、AA＋S（或O）、PD＋V就是簡(jiǎn)單語義單元（如圖2所示，假定L的語義結(jié)構(gòu)為:L→AAPDAB）。

1.3 簡(jiǎn)單語義單元的語義特征

簡(jiǎn)單語義單元的特點(diǎn):

（1）除了所附加的S、V、O外，其它任何詞匯Wi的語義修飾目標(biāo)WGi都在簡(jiǎn)單語義單元內(nèi)部；

（2）在語義分析時(shí)，可以作為一個(gè)整體來處理，其內(nèi)部語法結(jié)構(gòu)對(duì)語句的其余部分沒有影響；

（3）由于其中不包含從句，在語義計(jì)算時(shí)，每個(gè)詞的權(quán)重相同，無需考慮S、V、O的影響。

本文的算法，正是針對(duì)這種特點(diǎn)而提出的。

圖2 簡(jiǎn)單語義單元的語義特征

1.4 AA、PD、AB的最佳界限劃分

假定一個(gè)分段L的語義結(jié)構(gòu)為:L→AAPDAB，且L包含m個(gè)詞匯；則AA、PD、AB的不同界限劃分方案共有種；可以根據(jù)式（1）與式（2）的方法，分別計(jì)算出每一種界限劃分方案的語義相關(guān)度值，然后選擇具有最佳語義相關(guān)度值的界限劃分方案作為AA、PD、AB的最佳界限劃分方案。

1.5 多義詞的語義相關(guān)度計(jì)算

針對(duì)兩個(gè)詞匯Wi和Wj（假設(shè)其為多義詞），依據(jù)How Net計(jì)算其語義相關(guān)度時(shí)，有兩種情況:

（1）按義項(xiàng)計(jì)算；

（2）詞匯作為一個(gè)整體進(jìn)行計(jì)算。

1.5.1 義項(xiàng)之間的語義相關(guān)度

針對(duì)一個(gè)樹狀詞匯語義庫（在本文的實(shí)驗(yàn)中，采用了How Net），兩個(gè)詞匯Wi與其語義修飾目標(biāo)WGi之間的語義相關(guān)度可用式（3）計(jì)算

1.5.2 詞匯之間的語義相關(guān)度

假如把詞匯Wi和WGi當(dāng)做一個(gè)整體，可根據(jù)式（4）來計(jì)算其語義相關(guān)度

其值為所有義項(xiàng)之間語義相似度的最大值。

2 簡(jiǎn)單語義單元的語義消歧

2.1 最佳語法分析方案的語義修飾關(guān)系圖

在不考慮一詞多義的情況下:假如把簡(jiǎn)單語義單元中的m個(gè)實(shí)詞當(dāng)做m個(gè)頂點(diǎn)，任意詞匯Wi與其語義修目標(biāo)WGi之間畫一條邊；由于Wi只有一個(gè)語義修飾目標(biāo)（最后一個(gè)詞匯沒有語義修飾目標(biāo)）；所以，每種語法分析方案都對(duì)應(yīng)于“m完全圖中的一顆生成樹”，如圖3所示。

圖3 每種語法分析方案都對(duì)應(yīng)于完全圖的一顆生成樹

假如“把Wi和WGi之間的邊的權(quán)值設(shè)置為Match（Wi，WGi）”，則最佳語法分析方案就對(duì)應(yīng)于“完全圖的最大生成樹”。這可以很容易地求出。

但這種方法不能實(shí)現(xiàn)“多義詞的語義消歧”，因此，也不能求出多義詞的最佳語法分析方案。

2.2 多義詞的語義修飾關(guān)系圖

自然語言中，大多數(shù)詞匯是多義詞，對(duì)簡(jiǎn)單語義單元進(jìn)行語法分析和語義消歧時(shí)，可以先畫出其語義修飾關(guān)系圖，其中，多義詞的所有義項(xiàng)形成一個(gè)集合，每個(gè)義項(xiàng)是該義項(xiàng)集合中的一個(gè)點(diǎn)。假設(shè)其的詞匯序列L＝Wm…Wi…W…Wp…W…W0，如圖4所示，在某個(gè)語法分析方案中，Wi的語義是其第j個(gè)義項(xiàng)，Wp的語義是其第q個(gè)義項(xiàng)，并且語義修飾于；則在語義修飾關(guān)系圖中的和之間，畫一條有向線段；在詞匯序列L上也畫一條有向線段。

圖4 多義詞的語義修飾關(guān)系

在圖4中，假如把每個(gè)詞匯的“義項(xiàng)集合”看成一個(gè)“廣義頂點(diǎn)”，義項(xiàng)看成一個(gè)“義項(xiàng)頂點(diǎn)”，則有以下特點(diǎn):

（1）任意“廣義頂點(diǎn)”只有一個(gè)語義修飾目標(biāo)，其出度為1，最后一個(gè)“廣義頂點(diǎn)”除外；

（2）每種語法分析方案，其語義修飾關(guān)系圖必然為一個(gè)“廣義頂點(diǎn)完全圖”的一顆“生成樹”；

（3）在每個(gè)“義項(xiàng)集合”中，“生成樹”的所有邊，必須關(guān)聯(lián)同一個(gè)“義項(xiàng)頂點(diǎn)”；

（4）根據(jù)語義計(jì)算模型，具有最大語義相關(guān)度的語法分析方案，其語義修飾關(guān)系圖是“廣義頂點(diǎn)完全圖”的“最大生成樹”。

2.3 最大生成樹變量

可以用窮舉法直接求取“廣義頂點(diǎn)完全圖”的“最大生成樹”，但其計(jì)算復(fù)雜度將是指數(shù)級(jí)別的，理論上不可行。

為了解決這個(gè)問題，我們采用了動(dòng)態(tài)規(guī)劃法，可以解決這個(gè)問題。首先，需要定義一個(gè)“最大生成樹變量”（如圖5所示），其含義為:針對(duì)詞匯Wi，其第j個(gè)義項(xiàng)有多個(gè)生成樹，其中各邊權(quán)值之和最大的生成樹，用MT（）表示，MT（）必須包含所對(duì)應(yīng)的點(diǎn)。

圖5 最大生成樹變量

2.4 求最大生成樹的動(dòng)態(tài)規(guī)劃算法

先將所有“廣義頂點(diǎn)”劃分為U、V兩個(gè)集合:

U＝｛所有未計(jì)算出MT的“廣義頂點(diǎn)”｝

V＝｛已經(jīng)計(jì)算出MT的“廣義頂點(diǎn)”｝

動(dòng)態(tài)規(guī)劃算法（算法1）:

步驟1 初始化

設(shè)置V＝｛W1，W0｝，其中的W0只有一個(gè)義項(xiàng)，就是簡(jiǎn)單語義單元中的S或V或O；由于只有兩個(gè)“廣義頂點(diǎn)”，因此很容易算出W1的任意義項(xiàng)的最大生成樹:

MT（）＝｛到W0的邊｝

MT（W0）＝max｛WT（）｝所對(duì)應(yīng)的生成樹。

步驟2 計(jì)算U中詞匯Wi的最大生成樹變量

針對(duì)U中最后一個(gè)詞匯Wi，其每個(gè)義項(xiàng)與V中的任意義項(xiàng)之間，都可以計(jì)算出一個(gè)語義相關(guān)度，按照式（5），選擇能夠使MT（）達(dá)到最大的那個(gè)義項(xiàng)（如圖6所示），更新的最大生成樹變量MT（）的值

步驟3 對(duì)Wi的所有生成樹進(jìn)行逆排序

在求Wi的最大生成樹變量的過程中，需要窮舉Wi的所有生成樹，在窮舉的時(shí)候，按照由大到小的順序，保存Wi的所有生成樹序列，用TList表示，則

圖6 計(jì)算集合U中義項(xiàng)的最大生成樹變量

步驟4 更新V中所有義項(xiàng)的最大生成樹變量

當(dāng)求出U中最后一個(gè)詞匯Wi的每個(gè)義項(xiàng)的最大生成樹變量后，可以考慮把Wi加入集合V；但這將致使V中每個(gè)義項(xiàng)的最大生成樹變量發(fā)生極大的變化，因此，在將Wi加入集合V之前，必須更新V中所有義項(xiàng)的最大生成樹變量。

更新算法的思路如圖7所示，從TList中找到Wi的最大生成樹（用粗線畫出），其在V中所相關(guān)的6個(gè)義項(xiàng)，就是“第1次更新的義項(xiàng)集合”；接下來，從TList中找到W i的第2大生成樹，其在V中所相關(guān)所有義項(xiàng)中，有4個(gè)義項(xiàng)沒有更新過，這4個(gè)義項(xiàng)就是“第2次更新的義項(xiàng)集合”；以此類推，直至V中的所有義項(xiàng)都被更新過。其過程可以用算法2來描述。

圖7 更新集合V中所有義項(xiàng)的最大生成樹變量

算法2:

步驟5 將詞匯Wi加入V

更新完V中的所有義項(xiàng)的最大生成樹變量之后，就可以將Wi加入集合V了。

步驟6 循環(huán)處理，直至U為空

返回步驟2，進(jìn)行循環(huán)，直至U為空。最后選出詞匯Wm的最大生成樹即可。

2.5 計(jì)算復(fù)雜度分析

假設(shè)簡(jiǎn)單語義單元包含m個(gè)詞匯，每個(gè)詞匯平均有t各義項(xiàng)。假如用窮舉法求解:理論計(jì)算復(fù)雜度為O（m2＊tm）。

假如用動(dòng)態(tài)規(guī)劃法求解:

（1）共有m個(gè)詞匯；

（2）求Wi的最大生成樹變量時(shí)，平均有t個(gè)義項(xiàng)；

因此，本方法的理論計(jì)算復(fù)雜度為:O（m＊t＊（m＊t/2））＝O（（m＊t）2）。

3 實(shí)驗(yàn)結(jié)果及分析

本文的實(shí)驗(yàn)中，以How Net作為詞匯語義計(jì)算時(shí)所依據(jù)的資源。選取了100個(gè)語句進(jìn)行實(shí)驗(yàn)，先人工對(duì)其分析，將其劃分為406個(gè)簡(jiǎn)單語義單元，并得到語義消歧的正確結(jié)果，然后與算法計(jì)算所得到的結(jié)果進(jìn)行對(duì)比。實(shí)驗(yàn)情況如下:

（1）不分義項(xiàng)計(jì)算:用Prim算法求最大生成樹，得到最佳語法分析方案，不能實(shí)現(xiàn)語義消歧。

（2）分義項(xiàng)計(jì)算:分別使用窮舉法、動(dòng)態(tài)規(guī)劃法進(jìn)行計(jì)算，可以得到最佳語法分析方案，還可以確定多義詞的義項(xiàng)，從而實(shí)現(xiàn)語義消歧。

3.1 語法分析實(shí)驗(yàn)情況

語法分析指的是“求出每個(gè)詞匯W的語義修飾目標(biāo)WG”的過程。實(shí)驗(yàn)環(huán)境為:Windows XP，Xeon E5－2403四核，主頻2.2GHz，8G內(nèi)存，實(shí)驗(yàn)情況見表1、圖8與圖9。

在表1中，窮舉法、動(dòng)態(tài)規(guī)劃法的正確率計(jì)算標(biāo)準(zhǔn)有兩個(gè):

表1 每個(gè)簡(jiǎn)單語義單元平均計(jì)算時(shí)間（毫秒，語義消歧正確率閥值＝0.5）

圖8 正確率對(duì)比

圖9 窮舉法時(shí)間/動(dòng)態(tài)規(guī)劃法時(shí)間

（1）語法分析方案正確；

（2）語義消歧的正確率大于設(shè)定的閥值0.5。表1每個(gè)簡(jiǎn)單語義單元平均計(jì)算時(shí)間（毫秒，語義消歧正確率閥值＝0.5）。

從實(shí)驗(yàn)結(jié)果可以看出:

（1）不分義項(xiàng)計(jì)算的情況下，由于它沒有實(shí)現(xiàn)語義消歧，正確率最高。

（2）窮舉法、動(dòng)態(tài)規(guī)劃法的計(jì)算結(jié)果一致，因?yàn)閷?shí)現(xiàn)了語義消歧，其正確率有所降低。

（3）隨著簡(jiǎn)單語義單元長度的增加，正確率逐漸下降。

（4）隨著簡(jiǎn)單語義單元長度的增加，窮舉法計(jì)算所需的時(shí)間急劇增加；而動(dòng)態(tài)規(guī)劃法所需時(shí)間一直保持在可以接受的范圍內(nèi)，實(shí)踐上可行。

3.2 語義消歧實(shí)驗(yàn)情況

窮舉法和動(dòng)態(tài)規(guī)劃法的計(jì)算結(jié)果一致，可以實(shí)現(xiàn)語義消歧。語義消歧的實(shí)驗(yàn)情況見表2與圖10。

表2 語義消歧實(shí)驗(yàn)情況（總個(gè)數(shù)＝406）

由實(shí)驗(yàn)結(jié)果可知，雖然本方法能實(shí)現(xiàn)語義消歧，但其正確率還不太高，有待進(jìn)一步的提高。

4 結(jié)束語

本文研究了基于動(dòng)態(tài)規(guī)劃的簡(jiǎn)單語義單元詞義消歧方法，先把語句劃分、轉(zhuǎn)化為簡(jiǎn)單語義單元，通過態(tài)規(guī)劃的方法，求出其語義修飾關(guān)系完全圖的最大生成樹，并將其轉(zhuǎn)化為最佳的語法分析方案，同時(shí)也實(shí)現(xiàn)了詞義消歧。最后通過實(shí)驗(yàn)，對(duì)本文的方法進(jìn)行驗(yàn)證，結(jié)果表明本文的方法具有一定的效果。從理論上講，本方法可以較為有效地進(jìn)行語義消歧，但實(shí)際的計(jì)算效果并不十分理想，其主要原因是所依據(jù)的How Net的語義準(zhǔn)確度、多義詞的語義細(xì)致程度等，有很多欠缺和不足。另外，本文研究的前提是“不考慮簡(jiǎn)單語義單元中的任何語法規(guī)則”；這是不符合實(shí)際情況的，至少有3種情況需要考慮:①具有連接、分段作用的虛詞，其語法作用不容忽視；②后向修飾規(guī)則，這是漢語中最常見的默認(rèn)語義規(guī)則；③不越界規(guī)則，即W1～WG1之間的詞匯Wi的語義修飾目標(biāo)WGi，應(yīng)該位于W1～WG1之間。這些問題都有待在下一步研究中加以解決。

［1］WANG Guangzheng，WANG Xifeng.Word sense disambiguating method based on How Net semantic relevancy computation［J］.Journal of Anhui University of Technology（Natural Science），2008，25（1）:71－75（in Chinese）.［王廣正，王喜鳳.基于知網(wǎng)語義相關(guān)度計(jì)算的詞義消歧方法［J］.安徽工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，25（1）:71－75.］

［2］Deepesh Kumar Kimtani，Jyotirmayee Choudhury，Alok Chakrabarty.Improvement in word sense disambiguation by introducing enhancements in English Word Net structure［J］.International Journal on Computer Science and Engineering，2012，4（7）:1366－1370.

［3］Chenliang Li，Aixin Sun，Anwitaman Datta.TSDW:Twostage word sense disambiguation using Wikipedia［J］.Journal of the American Society for Information Science and Technology，2013，64（6）:1203－1223.

［4］YANG Zhizhuo，HUANG Heyan.Graph based word sense disambiguation method using distance between words［J］.Journal of Software，2012，23（4）:776－785（in Chinese）.［楊陟卓，黃河燕.基于詞語距離的網(wǎng)絡(luò)圖詞義消歧［J］.軟件學(xué)報(bào)，2012，23（4）:776－785.］

［5］ZHANG Ruixia，ZHUANG Jinlin，YANG Guozeng.Chinese message structures disambiguation based on How Net［J］.Journal of Chinese Information Processing，2012，26（4）:43－60（in Chinese）.［張瑞霞，莊晉林，楊國增.基于知網(wǎng)的中文信息結(jié)構(gòu)消歧研究［J］.中文信息學(xué)報(bào)，2012，26（4）:43－60.］

［6］LI Shengqi，TIAN Qiaoyan，TANG Cheng.Disambiguating method for computing relevancy based on How Net semantic knowledge［J］.Journal of the China Society for Scientific and Technical Information，2009，28（5）:706－711（in Chinese）.［李生琦，田巧燕，湯承.基于知網(wǎng)詞匯語義相關(guān)度計(jì)算的消歧方法［J］.情報(bào)學(xué)報(bào)，2009，28（5）:706－711.］

［7］LIU Yuntong，LIANG Yanjun.The k－pruning algorithm for semantic relevancy calculating model of natural language［J］.Computer Engineering and Design，2013，34（8）:2939－2943（in Chinese）.［劉運(yùn)通，梁燕軍.自然語言語義相關(guān)度計(jì)算模型的k枝剪求解法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（8）:2939－2943.］

［8］Kostas Fragos.Modeling Word Net glosses to perform word sense disambiguation［J］.International Journal on Artificial Intelligence Tools，2013，22（2）:1345－1352.

［9］Minca A，Diaconescu S.An approach to knowledge－based word sense disambiguation using semantic trees built on a Word Net lexicon network［C］//The 6th Conference on Speech Technology and Human－Computer Dialogue，2011:1－6.

［10］Suvitha D S，Janarthanan R.Enriched semantic information processing using Word Net based on semantic relation network［C］//International Conference on Computing，Electronics and Electrical Technologies，2012:846－851.