基于動態規劃和流形排序的知識庫問答未登錄詞處理

何儒漢 萬方名 胡新榮 劉軍平

1(武漢紡織大學數學與計算機學院 湖北 武漢 430200)

2(武漢紡織大學湖北省服裝信息化工程技術研究中心 湖北 武漢 430200)

0 引 言

近年來,隨著人工智能領域的高速發展,知識圖譜成為了計算機科學領域的研究熱點。知識圖譜通過資源描述框架,高效地組織非結構化語料中的結構化信息,其特點是數據均以三元組的形式保存。比較成熟的英文知識圖譜有Freebase[1]、DBpedia[2]和YAGO[3]等,中文知識圖譜有Zhishi.me[4]、CN-DBpedia[5]等。知識譜圖被廣泛應用于工業界,例如,知識庫問答(KBQA)是知識圖譜結合自然語言處理技術,實現自動問答的任務,該任務通過自然語言處理技術獲取問句的語義信息,結合實體檢測、識別和關系抽取,最后在知識庫中檢索,得到最終答案。

目前知識庫問答研究方法主要分為兩條路線。第一條路線旨在圍繞通過語義解析尋找一種中間表達,再將其轉化為查詢語句如SPARQL在知識庫搜索實體得到最終答案[6-7];第二種思路去除了這種中間表達,致力于使用深度學習的方法直接進行問句與三元組的匹配,這種方法是近幾年比較常見的做法[8-11]。而這類KBQA方法大多基于APA(Alignment-Prediction-Answering)框架。該框架把問答任務分解為實體識別、實體鏈指、關系檢測等子任務,每個子任務負責獨立的任務,但在現有的這兩種思路中,都沒有考慮到未登錄詞(Out-Of-Vocabulary,OOV)。

現有的智能問答工作大多基于一個叫作Glove的詞向量庫[12],這是一個由40 000個長度為300的向量組成的詞表,每個單詞對應一個向量,在進行實體鏈接等流程之前需要將問題和關系中的單詞轉化為對應的向量,但因詞表大小限制等原因,在詞庫中匹配不到的詞就是未登錄詞。根據檢測,現在常見的KBQA系統中未登錄詞的比例高達38%以上[10,13]。

目前針對未登錄詞的研究主要有基于規則的方法和基于統計的方法?；谝巹t的方法綜合未登錄詞的詞性、前綴詞素以及后綴詞素等信息來為未登錄詞分配最可能的標簽[14],這種方法的準確率一般較低;基于統計的方法是統計大量語料中的未登錄詞并將其表示放入一個詞表中,然后在其他語料中遇到該詞就使用這些未登錄詞在詞表中的表示[15],這種方法的缺點是時間成本高,并且還是解決不了層出不窮的新詞;在其他領域如機器翻譯還有使用同義詞來代替未登錄詞等方法,但這些方法都沒有解決建表成本高等問題。

未登錄詞很難完全避免,原因有兩點：① 命名實體包含重要信息,但很多命名實體也是低頻詞,通常不能包含在詞匯表中;② 網絡新詞層出不窮,舊詞表無法及時更新,特別是在當前模型越來越大的情況下,添加新單詞后對模型再次訓練的成本非常高昂。為了解決上述問題,本文提出了一種基于動態規劃和流形排序的問答模型DPQA(Dynamic Programming-based Question Answering),首先在維基百科上抓取了大量英文文本并對其進行分析得到126 136個單詞,通過詞語出現的頻次進行排序,然后根據奇夫定律對其生成一個代價詞典,根據代價詞典使用動態規劃的方法找到最優子串序列,最后使用一種簡易但有效的基于流形排序的重排序算法[16]定位最終子串,使用子串表示代替關系和問句中的隨機向量。通過實驗驗證了DPQA在多個問答數據集上均具有良好的表現,在單關系數據集上效果尤為突出,進一步提升了知識庫問答任務的準確度。

1 DPQA模型

1.1 任務定義

本文提出的方法基于英文知識庫Freebase[1],對其實體和關系進行匹配搜索。Freebase知識庫中每個條目通過(subject,relation,object)的形式表示。SimpleQuestion和WebQuestion分別為Facebook公司公開的單關系與多關系的知識庫問答數據集,其中的數據均為人工標注,并且數據集中的每個問句與Freebase知識庫中的一個條目相對應。

給定一個問題,它的實體和關系在知識庫中,問題、關系使用Glove詞向量庫表示,詞表中沒有的單詞即未登錄詞使用隨機向量表示。知識庫問答模型的目標是找到連接主題實體和知識庫中指向答案的關系。對于候選關系集中的每個關系,模型計算與問題的語義相似度,并選擇得分最高的關系路徑作為答案路徑[13]。

1.2 單元定義

本文對模型中會用到的單元有如下定義：

(1) 問題集定義為Q={q1,q2,…,qq_n},其中每個單元qi(i∈{1,2,…,q_n})都是問題集中的一個問題,q_n為問題集中所有問題的數量。

(2) 關系集R={r1,r2,…,rr_n},其中每個單元r都是關系集中的一個關系,r_n為關系集中所有關系的數量行。

1.3 模型結構

該方法主要解決知識庫問答中的未登錄詞問題,模型中實體檢測部分結合了[10,13,17]的注意力機制模塊(撰寫本文時準確率最高的模型)和MOYU的BiLSTM模塊[10]。引入未登錄詞處理模塊后模型如圖1所示。

圖1 加入了未登錄詞模塊的知識庫問答模型

2 未登錄詞檢測層

本節描述DPQA的未登錄詞檢測層,該層由三個部分組成,結構如圖2所示。

圖2 未登錄詞檢測模塊

2.1 構建代價詞典

本文利用奇夫定律(Zipf’s law)為詞表構建代價詞典。其思想是在自然語言文本集中,單詞出現的頻率與該文本集中所有單詞的頻率排名成反比,定律具體為頻率排名第一的單詞出現的頻率大約是排名第二位單詞的兩倍,而排名第二位的單詞則是出現排名第四單詞的兩倍,其公式為：

(1)

式中：P(r)表示排名為r的單詞頻率;r表示一個單詞出現頻率的排名,單詞頻率分布中C約等于0.1,α約等于1。

本文在維基百科上爬取大量英文語料并做了清洗與分析,得到一個長度為126 136的詞表,并根據詞頻進行排序,詞表如表1所示。

表1 維基百科詞頻分布

根據奇夫定律與詞表,構建了代價詞典。首先有詞表W={w1,w2,…,wn},n為詞表的長度,wi是詞表W中的詞頻排第i位的詞,則有：

Costi=log((i+1)×log(n))

(2)

代價詞典Cost={Cost1,Cost2,…,Cost126136},部分數據如表2所示。

表2 代價詞典

2.2 動態規劃

生成代價詞典后,本文使用動態規劃的方法為未登錄詞生成子詞序列。以未登錄詞“whitecoffee”為例。

首先計算該詞的代價數組C_array,置代價數組第一位C_array[0]為0,然后計算第一個字符“w”的代價,并與該字符所有可能的字符串的代價相比較,取最小的放入代價數組,例如“w”只有一種情況,所以C_array[1]為Cost[w]=9.227 322 4,第二個字符“h”的代價因為有兩個字符串的情況“w”+“h”和“wh”,Cost[w]+Cost[h]=9.227 322 4+8.786 002 7=18.013 325 1,而Cost[wh]=13.096 018 351,取其中最小值13.096 018 351,以此類推可得到未登錄詞“whitecoffee”的代價數組：[[0,9.227 322 400 521 313,13.096 018 351 828 421,19.670 329 707 960 61,13.599 631 067 643 815,8.262 530 146 419 405,15.902 117 370 952 112,17.530 582 158 440 907,19.058 702 043 470 937,24.217 757 342 685 466,29.297 030 357 217 277,18.529 402 695 330 45]]。

然后回溯恢復代價最低的字符串,可獲得“whitecoffee”的C_space為：[(37.167 639 620 636 27,1),(36.000 389 611 532 61,2),(30.252 829 901 108 456,3),(inf,4),(inf,5),(18.529 402 695 330 45,6),(inf,7),(inf,8),(inf,9),(inf,10),(inf,11)],inf代表詞表中無該詞,所以代價為無限大,最后取代價最小的值(18.529 402 695 330 45,6)為分隔處,可獲得第一個子詞“coffee”,以此類推得到最優子詞序列[white,coffee]。動態規劃的流程如圖3所示。

圖3 動態規劃流程

2.3 重排序

獲取了最優特征詞序列后,使用一種基于流行排序方法對特征詞進行排序[18]。流形排序[19-20]是一種基于樣本數據集的流形分布假設的排序算法,該算法是一個半監督學習的方法,即對于一個圖模型,給定一些種子節點,根據節點之間的內在流行結構對每個節點進行排序,得到每個節點的最終排序得分。流形排序方法根據多個語料之間的流形結構對單詞之間的相似度進行計算,首先根據語料庫的結構,對流行結構圖中的各節點做相似度排序。相似性排序的主要思想是對每個節點計算該節點與其他節點的相似度,此過程實質上是一種圖學習的過程。流形排序算法用上述過程計算相似度最后進行排序,主要由圖初始化及相似度計算與排序兩個模塊組成?；诹餍闻判蚴悄壳靶Ч^好的特征詞排序算法[18-19]。

本文根據流形排序方法,綜合考慮統和語義結構兩個維度的信息,為多個候選詞進行重要度排序。該方法具體步驟,如下所示：

1) 各候選詞的重要度基于詞頻進行初始化。已有研究發現,相比于如IG、CHI等傳統監督學習方法,詞頻排序的特征詞選擇方法的效果反而更加突出。本方法根據統計維基百科語料的詞頻給候選詞進行初始化,有：

y=[y1,y2,…,yn]

(3)

式中：yi表示語料c中第i個單詞在c中的詞頻;n表示語料中所有單詞的數量。

2) 本方法通過結合語料中候選詞的語義信息與位置信息構建語料網絡圖G=(V,E),其中V表示語料d的單詞列表,其中每個單詞表示語料圖G中的一個節點v;E表示各個邊e的集合,每條邊e連接各個節點v,兩個節點之間是否存在邊取決于以下兩點：① 在原語料某一段落中是否有同時出現兩個節點對應的特征詞的情況出現;② 比較兩個節點條件共現度是否超過算法提前設定的閾值。條件共現度矩陣方法是魏偉等[21]于2019年提出的一種詞共現表示方法。相比于傳統的詞共現表示,條件共現度矩陣方法增加了對語料語義粒度信息和事實在相同段落中的相關詞表示等因素的考量,也就是它保存了更多的語義結構信息,使得穩定性和效果都得到了比較明顯的提升。條件共現度矩陣方法在傳統方法的框架上計算候選詞相對語料特征空間的條件概率。使用矩陣W=(ccodmij)n×n表示語料c,第i個候選詞A與第j個候選詞B的條件共現度ccodmij計算方法如下：

(4)

式中：p(B|A)表示候選詞A與候選詞B的共現概率,p(A)為候選詞A在語料c里出現的概率,使用comij表示語料c中第i與第j個單詞的共現次數,即：

(5)

式中：S為語料c中的所有段落;fsj為語料中第j個單詞在第s個段落中的出現頻次;n表示候選詞列表的長度。由此可知條件共現度矩陣為不對稱矩陣：ccodmij≠ccodmji。此外,設定ccodmij=0。

二次排序的本質是轉移了語料圖結構中候選詞的權值。候選詞以一定的概率將該詞的重要度傳遞給與該詞有邊相連的多個候選詞。使用詞頻來為語料中單詞重要度進行初始化：y=[y1,y2,…,yn]。后續各候選詞權重排序過程為：

f(t+1)=αNf(t)+(1-α)y

(6)

式中：α的值域為[0,1]。候選詞列表最初通過詞頻排序,在之后的每次計算中根據α計算重要度然后傳遞給鄰接的所有單詞。根據以上方法不斷迭代,直到算法收斂,收斂結果為：

(7)

流形排序算法的優化函數定義為：

(8)

該函數的核心思想是使語料中距離相近的單詞相似度更高。μ是算法的正則化參數,其值域為(0,∞)。

算法1基于流形排序的子詞排序算法

輸入：子詞序列、語料詞頻。

輸出：子詞重要性排序。

step1計算序列中所有特征詞詞頻,并將詞頻序列作為特征詞初始重要性排序y。

step4結合相似度矩陣N以及在step1中初始化的排序y,根據函數f(t+1)=αNf(t)+(1-α)y不斷迭代計算出最終子詞重要性排序。

end

3 DPQA實驗分析

本節通過實驗證明了DPQA模型的穩定性及有效性。首先介紹了本文方法所使用的知識庫等數據,然后對評測指標以及算法的實現細節進行闡述,最后對實驗結果做進一步的分析與解釋。

3.1 數據集與評測指標

本方法使用了Facebook在2016年發布的KBQA數據集SimpleQuestion(單關系,后文中用“SQ”表示),包含75 909條訓練數據,108 445條驗證數據及216 884條測試數據。在多關系問題上,本文采用了WebQuestion數據集(后文中使用“WQ”表示),WQ包含6 642個問答對。

該方法采用兩種方法作為評測指標,第一種是未登錄詞的比例,即所有的問題與關系中包含的未登錄詞數量和問題、關系總詞數的比值;第二種采用關系檢測的準確率。

3.2 實驗與結果分析

本文研究對比了通過動態規劃和流形排序后得到的詞向量與隨機向量的向量差異度,具體方法使用的對比兩向量的夾角。首先找出在原詞向量庫中沒有但在另一個含有219萬個詞向量的詞向量庫glove840中包含的單詞OOV,通過本文提出的方法得出最終子詞s,取該子詞在glove840中的向量Vs與該未登錄詞(相對于原詞向量庫)在glove840中的向量Voov做夾角計算,結果如表3所示。

表3 未登錄詞與其子詞的向量夾角對比

可以觀察到通過本文研究得出的向量相比之前的隨機向量與OOV的相似度更高,獲取到了以前模型沒有的信息。

如表4所示,本文研究把SQ中的未登錄詞比例降低了20.4百分點,將WQ中的未登錄詞比例降低了12.47百分點,可以看出本文研究對未登錄詞的檢測及補齊有很明顯的效果。經過分析,DPQA對WQ的未登錄詞效果沒有SQ明顯的原因首先是WQ中的未登錄詞本身較少,其次與兩個數據集中的詞語分布有關。

表4 SQ和WQ數據集上未登錄詞比例(%)

最終模型對關系檢測的準確率如表5所示,針對單關系數據集DPQA有比較好的提升,達到了93.84%,超過了其他幾種比較編碼框架的學習方法,證明了DPQA模型良好的建模效果,具體表現為未登錄詞比例降低了20.4百分點,在不依賴更大詞庫的情況下大幅減小了未登錄詞信息丟失對整個模型的影響,其次表現在最終的關系檢測中準確率獲得了目前最優成績。在多關系數據集WebQuestion上,DPQA比Bi-LSTM、HR-Bi-LSTM等模型效果都要好,并且訓練時間有明顯的減少。

表5 關系抽取準確率(%)

3.3 時間性能實驗

因為大幅減少未登錄詞,所以在對單詞做向量化的時候可以減少大量無用的稀疏表示,所以DPQA在訓練時間上有了不錯的優化,相比于用時最少的BiCNN,在相同超參數的情況下,DPQA在SQ和WQ數據集上分別有5.4 s(12.3%)和5.9 s(14.2%)的提升,具體如表6所示。

表6 關系抽取時間 單位：s

根據對實驗數據的詳細分析,對DPQA的優點有如下總結：(1) DPQA可以在同詞庫的情況下,顯著降低未登錄詞對整個問答系統的負面影響,最大限度地利用了問題和關系中的信息;(2) 由于未登錄詞的減少,數據預處理時的稀疏向量隨之減少,使模型訓練時間大幅下降;(3) 隨著社會的進步,在新詞層出不窮、未登錄詞越來越多的情況下,DPQA相比于其他沒有未登錄詞檢測層的模型,會具有越來越明顯的優勢。

4 結 語

近年來的KBQA算法大多集中在關系檢測和實體檢測上,較少有關注問題與關系中的未登錄詞問題,所以問答準確率不可避免地會碰到瓶頸。本文為知識庫問答領域提出了基于動態規劃與流形排序的新方法,為智能問答的解決方案提供了新的思路。通過實驗,DPQA在單關系和多關系問答集上都表現良好,特別是在單關系問題上表現突出,為解決通用知識庫問答系統中的未登錄詞問題提供了簡單可行的方案。