自然語言語義相關度計算模型的k枝剪求解法

劉運通，梁燕軍

（安陽師范學院 計算機與信息工程學院，河南 安陽455000）

0 引 言

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

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

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

1 語句的語義相關度計算模型

假設一個語句 （CS）中的任意實詞 Wi（除去謂語中心詞）均語義修飾于另外一個實詞WGi，稱WGi是Wi語義修飾目標，用函數match（Wi，WGi）來表示其語義相關度。

假設語句CS有m種不同的語法分析方案，在其中第i種語法分析方案Ai的情況下：假設V為謂語中心詞，S為V的施動者，O為V的承受者，Wi是語句中的一個實詞且！（Wi∈ ｛S，V，O｝），WGi是 Wi的語義修飾目標，那么，語句的語義相關度fAi（針對語法分析方案Ai）可以用式 （1）來表示 （見圖1）

S和O的語義修飾目標是V，n是實詞的個數 （不包括S、V、O），KSVO為權值系數 （KSVO＞1），KSVO應正比于語句的長度。

圖1 語義相關度計算模型

值得注意的是：虛詞不參與計算，副詞、代詞、數詞、量詞被按照實詞計算。

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

即語義相關度最大的語法分析方案是最佳語法分析方案。

2 語句的兩層語義結構及描述方法

為了進行語句分析，根據語義結構的復雜程度，將語句劃分為兩個層次：簡單句、復雜句。

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

G1的設計思路 （見圖2）：假設V是謂語，S是V的施動者，O是V的承受者，AB是前置定語，AA是后置定語，PD是狀語或補語，相當于格語法［7］中的一組格，PC是一個的格內容。

（2）復雜句：包含從句的語句CS，在文法G1中添加規則L→CS，形成文法G2。所添加的規則L→CS說明一個簡單句可以作一個復雜句中任意成分，實現了對簡單句遞歸，因此文法G2可以描述復雜句。

表1 文法G1的內容

3 語句分析計算過程

3.1 自底向上的簡單子句歸結法

在計算過程中，每次選擇一個簡單子句 （從句），將其歸結為L，反復進行，直至整個語句成為簡單句，具體方法如下：

步驟1 （數據預處理）：使用ICTCLAS算法［8］進行分詞，并獲得其詞性；

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

步驟3 計算每個子句的最佳語義相關度，選擇計算結果最佳的簡單子句CSi，歸結CSi；

步驟4 假如語句CS還不是簡單句，則重復步驟2、3；否則，計算簡單句CS的最佳語義相關度。

3.2 簡單句的最佳語義相關度

3.2.1 詞匯間的語義相關度

針對一個樹狀詞匯語義庫 （在本文的實驗中，采用了hownet），兩個詞匯Wi與其語義修飾目標 WGi之間的語義相關度可用式3計算

sim（Wi，WGi）表示它們之間的語義相似度，rel（Wi，WGi）表示它們之間的語義關聯度，且系數α＋β＝1，具體細節可參考文獻 ［10］。

3.2.2 SVO的多個選擇方案

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

圖4 SVO的多個選擇方案

3.2.3 分段L的多個語義修飾方案

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

圖5 分段L的多個語義修飾方案

3.3 k枝剪法

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

3.3.1 k枝剪法原理

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

（1）每次子句歸結時，都有多種備選方案；

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

（3）針對每個分段L，也有多種備選方案。

整個求解過程，會形成了一個狀態空間樹。假如我們窮舉計算每種備選方案，在理論上，我們可以找到最符合語義邏輯的語法分析方案。但這種方法，在計算復雜度上是很難實現的。

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

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

圖6 k枝剪 （k＝3）

3.3.2 枝剪函數

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

在搜索狀態空間樹時，目標分段L（可能是一個從句）可能有多種語法分析方案 ｛A1，A2…，Am｝，n是L中詞匯的個數，fAi（L）是L在語法分析方案Ai情況下的語義相關度，通過公式 （3），可以計算出m個語義相關度 ｛fA1（L），fA2（L）… （L）fAm（L）｝，選擇其中最大的k個所對應的狀態，進入下一步的搜索。

4 實驗結果及分析

本文的實驗中，以hownet作為詞匯語義計算時所依據的資源。實驗分為兩個階段：

（1）KSVO取值實驗；

（2）枝剪過程中k取值的實驗。

4.1 KSVO取值實驗

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

表2 KSVO取值與正確率的實驗結果

圖7 KSVO取值與正確率的關系

由實驗結果可知，KSVO取0.5到0.6之間的值，正確率可以到達最大。

4.2 枝剪過程中k取值的實驗

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

4.2.1 k的取值與平均所需時間之間的關系

表3中的數據是k枝剪法平均所需時間；根據實驗結果，可以畫出k與平均所需時間的關系圖8（測試機：windows xp，Xeon E5－2403四核，主頻2.2GHz，8G內存）。

表3 k枝剪法平均所需時間

圖8 k與平均所需時間之間的關系

從實驗結果可以看出，所需時間T與k的階乘成正比：T≈k！。因此，不能隨意擴大k的取值，枝剪所選的分支一般應有k≤6，否則，求解計算所需的時間將以階乘的速度增加，其時間復雜度將變得難以接受。

4.2.2 k與正確率之間的關系

表4中的數據是k枝剪法的正確率；根據實驗結果，可以畫出k與正確率之間的關系圖9。

表4 k枝剪法的正確率

圖9 k與正確率之間的關系

從實驗結果可以看出，當k從1增加到4的過程中，正確率快速增加；當k＞4時，正確率繼續緩慢增加，增加量的絕對值越來越小，并且正確率可以取得較為滿意的效果。

4.3 實驗結果分析

從實驗情況可以看出，使用k枝剪法進行模型求解，有以下特點：

（1）k不能過大，否則時間復雜度將會難以接受；一般情況下，應有k≤6；

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

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

5 結束語

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

［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）.［王鑫，穗志方.基于依存樹距離識別論元的語義角色標注系統 ［J］.中文信息學報，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）.［劉宇紅.從格語法到框架語義學再到構式語法 ［J］.解放軍外國語學院學報，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］.中文信息學報，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］.計算機應用，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）.［王廣正，王喜鳳.基于知網語義相關度計算的詞義消歧方法 ［J］.安徽工業大學學報（自然科學版），2008，25 （1）：71－75.］