自然語言語義相關(guān)度計(jì)算模型的k枝剪求解法

劉運(yùn)通，梁燕軍

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

0 引 言

當(dāng)前，由于自然語言處理這個(gè)難題沒有得到很好的解決，越來越多的研究者在探索如何充分地利用語義信息，來取得更好的處理結(jié)果。

語義的作用越來越被重視，不少研究者使用Wordnet、Hownet、Framenet等詞匯語義知識(shí)庫(kù)作為語義分析的基礎(chǔ)性資源［1］；文獻(xiàn) ［2］研究了基于依存樹距離的語義角色標(biāo)注方法；HPSG方法研究了基于詞匯語義信息驅(qū)動(dòng)的語句處理方法［3］；文獻(xiàn) ［4］研究了將語料樹庫(kù)與framenet相結(jié)合的介詞短語消歧；文獻(xiàn) ［5］研究了在線語義資源的詞匯語義消歧；文獻(xiàn) ［6］研究了如何利用 Woednet來提高詞匯語義消歧的性能。這些研究取得不少成果，但還沒有形成一套系統(tǒng)地利用語義信息進(jìn)行自然語言處理的模型和方法。

為了能夠更為合理地利用語義來進(jìn)行自然語言處理，本文提出了一種自然語言語義相關(guān)度計(jì)算模型及該模型的k枝剪求解法，分析了語句的兩層語義結(jié)構(gòu)并給出其數(shù)學(xué)描述方法，采用自底向上的簡(jiǎn)單句歸結(jié)法來進(jìn)行模型求解。

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í)詞且?。╓i∈ ｛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)正比于語句的長(zhǎng)度。

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

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

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

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

2 語句的兩層語義結(jié)構(gòu)及描述方法

為了進(jìn)行語句分析，根據(jù)語義結(jié)構(gòu)的復(fù)雜程度，將語句劃分為兩個(gè)層次：簡(jiǎn)單句、復(fù)雜句。

（1）簡(jiǎn)單句：沒有從句的語句CS，用文法G1來描述 （表1）。

G1的設(shè)計(jì)思路 （見圖2）：假設(shè)V是謂語，S是V的施動(dòng)者，O是V的承受者，AB是前置定語，AA是后置定語，PD是狀語或補(bǔ)語，相當(dāng)于格語法［7］中的一組格，PC是一個(gè)的格內(nèi)容。

（2）復(fù)雜句：包含從句的語句CS，在文法G1中添加規(guī)則L→CS，形成文法G2。所添加的規(guī)則L→CS說明一個(gè)簡(jiǎn)單句可以作一個(gè)復(fù)雜句中任意成分，實(shí)現(xiàn)了對(duì)簡(jiǎn)單句遞歸，因此文法G2可以描述復(fù)雜句。

表1 文法G1的內(nèi)容

3 語句分析計(jì)算過程

3.1 自底向上的簡(jiǎn)單子句歸結(jié)法

在計(jì)算過程中，每次選擇一個(gè)簡(jiǎn)單子句 （從句），將其歸結(jié)為L(zhǎng)，反復(fù)進(jìn)行，直至整個(gè)語句成為簡(jiǎn)單句，具體方法如下：

步驟1 （數(shù)據(jù)預(yù)處理）：使用ICTCLAS算法［8］進(jìn)行分詞，并獲得其詞性；

步驟2 （找到所有子句）：針對(duì)語句CS，進(jìn)行文法G1的CYK算法［9］的運(yùn)算，可以找出滿足文法G1的簡(jiǎn)單子句集合 ｛CS1、CS2……CSm｝，如圖3所示；

步驟3 計(jì)算每個(gè)子句的最佳語義相關(guān)度，選擇計(jì)算結(jié)果最佳的簡(jiǎn)單子句CSi，歸結(jié)CSi；

步驟4 假如語句CS還不是簡(jiǎn)單句，則重復(fù)步驟2、3；否則，計(jì)算簡(jiǎn)單句CS的最佳語義相關(guān)度。

3.2 簡(jiǎn)單句的最佳語義相關(guān)度

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

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

sim（Wi，WGi）表示它們之間的語義相似度，rel（Wi，WGi）表示它們之間的語義關(guān)聯(lián)度，且系數(shù)α＋β＝1，具體細(xì)節(jié)可參考文獻(xiàn) ［10］。

3.2.2 SVO的多個(gè)選擇方案

在計(jì)算簡(jiǎn)單句的最佳語義相關(guān)度時(shí)，需要先確定SVO的位置，對(duì)于簡(jiǎn)單句，一般情況下，V的位置是確定的，而S和O的位置不易確定，在進(jìn)行最佳語義相關(guān)度計(jì)算時(shí)，具有多個(gè)不同的選擇方案，如圖4所示。

圖4 SVO的多個(gè)選擇方案

3.2.3 分段L的多個(gè)語義修飾方案

SVO的位置確定后，需要針對(duì)每個(gè)分段L，確定出L中的每個(gè)詞匯 Wi的語義修飾目標(biāo) WGi，并計(jì)算出每一組match（Wi，WGi）的值，并求和。顯然，L中具有多個(gè)不同的選擇方案，如圖5所示。

圖5 分段L的多個(gè)語義修飾方案

3.3 k枝剪法

k枝剪法實(shí)質(zhì)上是貪心法的一種變形和推廣，每當(dāng)面臨多種選擇時(shí)，貪心法僅僅選擇一種當(dāng)前最佳方案，進(jìn)入下一階段的搜索；在本文的k枝剪法中，每次選擇k個(gè)最佳方案，進(jìn)入下一階段的搜索，舍棄了其余的可能較小的方案。

3.3.1 k枝剪法原理

從3.1和3.2的分析中，可以看出：

（1）每次子句歸結(jié)時(shí)，都有多種備選方案；

（2）每次確定子句的SVO時(shí)，也有多種備選方案；

（3）針對(duì)每個(gè)分段L，也有多種備選方案。

整個(gè)求解過程，會(huì)形成了一個(gè)狀態(tài)空間樹。假如我們窮舉計(jì)算每種備選方案，在理論上，我們可以找到最符合語義邏輯的語法分析方案。但這種方法，在計(jì)算復(fù)雜度上是很難實(shí)現(xiàn)的。

為了解決這個(gè)難題，我們采用了k枝剪法進(jìn)行計(jì)算，可以求得一個(gè)近似解，具體方法是：

每當(dāng)碰到有多種備選方案的情況，都不再進(jìn)行窮舉式樣的搜索，而是僅僅選擇k個(gè)可能性最高的方案進(jìn)行計(jì)算，從而可以極大地降低計(jì)算復(fù)雜度，當(dāng)然，所得到的結(jié)果是一個(gè)近似結(jié)果，其原理可以用圖6表示。

圖6 k枝剪 （k＝3）

3.3.2 枝剪函數(shù)

整個(gè)求解過程，形成了一個(gè)狀態(tài)空間樹，在對(duì)狀態(tài)空間樹進(jìn)行搜索時(shí)，需要有一個(gè)枝剪函數(shù)，針對(duì)狀態(tài)空間樹中的每一層，來選定該層的k個(gè)最佳備選方案；舍棄其余的備選方案。在計(jì)算過程中，我們選用平均語義相關(guān)度來作為枝剪函數(shù)見式 （4）

在搜索狀態(tài)空間樹時(shí)，目標(biāo)分段L（可能是一個(gè)從句）可能有多種語法分析方案 ｛A1，A2…，Am｝，n是L中詞匯的個(gè)數(shù)，fAi（L）是L在語法分析方案Ai情況下的語義相關(guān)度，通過公式 （3），可以計(jì)算出m個(gè)語義相關(guān)度 ｛fA1（L），fA2（L）… （L）fAm（L）｝，選擇其中最大的k個(gè)所對(duì)應(yīng)的狀態(tài)，進(jìn)入下一步的搜索。

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

本文的實(shí)驗(yàn)中，以hownet作為詞匯語義計(jì)算時(shí)所依據(jù)的資源。實(shí)驗(yàn)分為兩個(gè)階段：

（1）KSVO取值實(shí)驗(yàn)；

（2）枝剪過程中k取值的實(shí)驗(yàn)。

4.1 KSVO取值實(shí)驗(yàn)

首先，由于SVO的重要性要比普通的詞匯大，因此需要通過實(shí)驗(yàn)，來確定KSVO的取值。進(jìn)行7組實(shí)驗(yàn)，分別設(shè)定KSVO＝0.9n，0.8n，0.7n，0.6n，0.5n，0.4n，0.3n （n是語句中的詞匯個(gè)數(shù)），選取100個(gè)簡(jiǎn)單句 （可以降低計(jì)算復(fù)雜度，不影響計(jì)算結(jié)果），采用完全搜索法求解；實(shí)驗(yàn)結(jié)果見表2；根據(jù)實(shí)驗(yàn)結(jié)果，可以畫出KSVO取值與正確率之間的關(guān)系圖7。

表2 KSVO取值與正確率的實(shí)驗(yàn)結(jié)果

圖7 KSVO取值與正確率的關(guān)系

由實(shí)驗(yàn)結(jié)果可知，KSVO取0.5到0.6之間的值，正確率可以到達(dá)最大。

4.2 枝剪過程中k取值的實(shí)驗(yàn)

顯而易見，k的值越大，計(jì)算越復(fù)雜，結(jié)果越正確。因此需要通過實(shí)驗(yàn)，來確定k的值。進(jìn)行5組實(shí)驗(yàn)，分別設(shè)定k＝2，3，4，5，6；選取100個(gè)復(fù)雜句，采用k枝剪法搜索法求解 （設(shè)KSVO＝0.55）。實(shí)驗(yàn)結(jié)果如下：

4.2.1 k的取值與平均所需時(shí)間之間的關(guān)系

表3中的數(shù)據(jù)是k枝剪法平均所需時(shí)間；根據(jù)實(shí)驗(yàn)結(jié)果，可以畫出k與平均所需時(shí)間的關(guān)系圖8（測(cè)試機(jī)：windows xp，Xeon E5－2403四核，主頻2.2GHz，8G內(nèi)存）。

表3 k枝剪法平均所需時(shí)間

圖8 k與平均所需時(shí)間之間的關(guān)系

從實(shí)驗(yàn)結(jié)果可以看出，所需時(shí)間T與k的階乘成正比：T≈k！。因此，不能隨意擴(kuò)大k的取值，枝剪所選的分支一般應(yīng)有k≤6，否則，求解計(jì)算所需的時(shí)間將以階乘的速度增加，其時(shí)間復(fù)雜度將變得難以接受。

4.2.2 k與正確率之間的關(guān)系

表4中的數(shù)據(jù)是k枝剪法的正確率；根據(jù)實(shí)驗(yàn)結(jié)果，可以畫出k與正確率之間的關(guān)系圖9。

表4 k枝剪法的正確率

圖9 k與正確率之間的關(guān)系

從實(shí)驗(yàn)結(jié)果可以看出，當(dāng)k從1增加到4的過程中，正確率快速增加；當(dāng)k＞4時(shí)，正確率繼續(xù)緩慢增加，增加量的絕對(duì)值越來越小，并且正確率可以取得較為滿意的效果。

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

從實(shí)驗(yàn)情況可以看出，使用k枝剪法進(jìn)行模型求解，有以下特點(diǎn)：

（1）k不能過大，否則時(shí)間復(fù)雜度將會(huì)難以接受；一般情況下，應(yīng)有k≤6；

（2）k不能過小，一般情況下，應(yīng)有k≥4，否則，正確率會(huì)急劇下降；

（3）k＝4或者5，較為合適，時(shí)間復(fù)雜度不是太高，正確率也不是太低，能夠取得較為滿意的效果。

5 結(jié)束語

本文提出了一個(gè)自然語言語義相關(guān)度計(jì)算模型，并研究了模型求解的k枝剪算法，可以對(duì)模型進(jìn)行較為有效的近似求解；通過實(shí)驗(yàn)，對(duì)模型中的權(quán)重系數(shù)KSVO的最佳取值范圍進(jìn)行了初步研究；對(duì)k枝剪算法中k的取值范圍進(jìn)行了研究，得到了k與算法復(fù)雜度、正確率之間關(guān)系。但在論文的研究中，語法規(guī)則的設(shè)置較為簡(jiǎn)單，還不能覆蓋一些特殊的漢語語法現(xiàn)象，實(shí)驗(yàn)數(shù)據(jù)量也較小，所依據(jù)的詞匯語義庫(kù)的語義信息還不能夠完全滿足計(jì)算需要，在下一步研究中，需要對(duì)語法規(guī)則進(jìn)行完善，構(gòu)建語義信息更準(zhǔn)確、合理的詞匯語義庫(kù)作為語義計(jì)算的依據(jù)，并且擴(kuò)大實(shí)驗(yàn)數(shù)據(jù)量。

［1］WEI Xue，XU Xinshun，REN Zhaochun.Word net－based lexical unit induction for FrameNet ［J］.Journal of Computational Information Systems 2012，8 （3）：1047－1054.

［2］WANG Xin，SUI Zhifang.Semantic role labeling system based on dependency tree distance method for arguments identification［J］.Journal of Chinese Information Processing，2012，26（2）：40－45（in Chinese）.［王鑫，穗志方.基于依存樹距離識(shí)別論元的語義角色標(biāo)注系統(tǒng) ［J］.中文信息學(xué)報(bào)，2012，26（2）：40－45.］

［3］Levine R，Detmar M.Head－driven phrase structure grammar：Linguistic approach，formal foundations，and computational realization ［M］.2nd ed.Encyclopedia of Language and Linguistics.Oxford：Elsevier，2008.

［4］Tom O，Janyce W.Exploiting semantic role resources for preposition disambiguation ［J］.Computational Linguistics，2008，35（2）：151－184.

［5］Imdadi N，Syed A，Rizvi M.Automating reuse of online semantic resources by concept extraction using word sense disambiguation［J］.Journal of Algorithms ＆ Computational Technology，2012，6（3）：435－446.

［6］Deepesh K，Choudhury J，Chakrabarty A.Improvement in word sense disambiguation by introducing enhancements in English WordNet structure ［J］.International Journal on Computer Science and Engineering，2012，7 （4）：1366－1370.［7］LIU Yuhong.From case grammar through frame semantics to construction grammar ［J］.Journal of PLA University of Foreign Languages，2011，34 （1）：5－9 （in Chinese）.［劉宇紅.從格語法到框架語義學(xué)再到構(gòu)式語法 ［J］.解放軍外國(guó)語學(xué)院學(xué)報(bào)，2011，34 （1）：5－9.］

［8］ZHANG Huaping，LIU Qun.Model of Chinese words rough segmentation based on N－shortest－paths method ［J］.Journal of Chinese Information Processing，2002，16 （5）：1－7 （in Chinese）.［張華平，劉群.基于N－最短路徑方法的中文詞語粗分模型 ［J］.中文信息學(xué)報(bào)，2002，16 （5）：1－7.］

［9］LI Yongliang，HUANG Shuguang，LI Yongcheng，et al.Improved CYK algorithm based on shallow parsing ［J］.Journal of Computer Applications，2011，31 （5）：1335－1338 （in Chinese）.［李永亮，黃曙光，李永成，等.基于淺層剖析的CYK改進(jìn)算法 ［J］.計(jì)算機(jī)應(yīng)用，2011，31 （5）：1335－1338.］

［10］WANG Guangzheng，WANG Xifeng.Word sense disambiguating method based on HowNet 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.］