基于動態(tài)規(guī)劃和流形排序的知識庫問答未登錄詞處理

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

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

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

0 引 言

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

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

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

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

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

1 DPQA模型

1.1 任務(wù)定義

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

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

1.2 單元定義

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

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

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

1.3 模型結(jié)構(gòu)

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

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

2 未登錄詞檢測層

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

圖2 未登錄詞檢測模塊

2.1 構(gòu)建代價詞典

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

(1)

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

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

表1 維基百科詞頻分布

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

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

(2)

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

表2 代價詞典

2.2 動態(tài)規(guī)劃

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

首先計算該詞的代價數(shù)組C_array,置代價數(shù)組第一位C_array[0]為0,然后計算第一個字符“w”的代價,并與該字符所有可能的字符串的代價相比較,取最小的放入代價數(shù)組,例如“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”的代價數(shù)組：[[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]]。

然后回溯恢復(fù)代價最低的字符串,可獲得“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”,以此類推得到最優(yōu)子詞序列[white,coffee]。動態(tài)規(guī)劃的流程如圖3所示。

圖3 動態(tài)規(guī)劃流程

2.3 重排序

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

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

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

y=[y1,y2,…,yn]

(3)

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

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

(4)

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

(5)

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

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

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

(6)

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

(7)

流形排序算法的優(yōu)化函數(shù)定義為：

(8)

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

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

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

輸出：子詞重要性排序。

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

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

end

3 DPQA實驗分析

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

3.1 數(shù)據(jù)集與評測指標

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

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

3.2 實驗與結(jié)果分析

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

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

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

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

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

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

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

3.3 時間性能實驗

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

表6 關(guān)系抽取時間 單位：s

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

4 結(jié) 語

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