揭開知識庫問答KB-QA的面紗6·深度學習中篇

01-29

內容速覽

語義解析方法的再思考
什麼是查詢圖
查詢圖的階段生成
各階段的特徵
論文實驗與總結

在上期，我們介紹了深度學習對傳統向量建模KB-QA方法進行提升的一篇代表論文，可以看出它的效果擊敗了當時所有的傳統方法。本期，我們將以深度學習提升語義解析方法的一篇代表作為例，作為深度學習篇的中篇，為大家進一步揭開知識庫問答的面紗。

我們在揭開知識庫問答KB-QA的面紗2·語義解析篇中介紹了傳統方法之一的語義解析（Semantic Parsing）方法，該方法相比向量建模方法有更強的解釋性，具有一定的推理能力。今天，我們將介紹一篇利用深度學習對該語義解析方法進行提升的論文，來自Microsoft公司的Semantic Parsing via Staged Query Graph Generation:Question Answering with Knowledge Base（文章發表於2015年的ACL會議，是當年的Outstanding Paper）。

該文章分析了傳統語義解析方法的不足，受信息抽取和向量建模方法的啟發，將語義解析過程轉化成查詢圖（Query graph）分階段生成的過程，使用了卷積神經網路來提升自然語言到知識庫關係的映射。該方法在WebQuestion數據集上測試，取得了52.5的F1-score，該性能遠超當時的所有方法。

語義解析方法的再思考

讓我們先回想一下傳統的語義解析方法，它的思想是把自然語言問題轉化為邏輯形式，通過邏輯形式轉化為查詢語句，在知識庫中查詢得出最終答案。在進行語義解析生成邏輯形式的過程中，主要是在提取自然語言問題中的信息和利用訓練好的語法解析器進行解析，這一過程幾乎沒有使用到知識庫里的信息。而在向量建模和信息抽取方法中，我們不僅對問題進行了特徵提取，還藉助知識庫確定了候選答案範圍（相比語義解析中的辭彙映射要在大範圍的知識庫實體關係中尋找映射，這樣的方式使得搜索範圍大大減小），並將候選答案在知識庫中的信息作為特徵。相比之下，可以看出傳統的語義解析方法和知識庫本身的聯繫是不夠緊密的（Decoupled from KB），也就是說，傳統語義解析方法對知識庫的利用還不夠。

再看看語義解析的第一步，辭彙映射（Lexicon）。要將自然語言中的謂語關係映射到知識庫中的實體關係，是一件很困難的事情，僅僅通過統計方式進行映射，效果並不好。如果我們能考慮知識庫的信息，是不是能將辭彙映射的範圍縮小？使用深度學習的辦法通過分散式表達來代替基於統計方法的辭彙映射，會不會取得更好的效果？

在語義解析的過程中，如何更好的去利用知識庫的知識，縮小語義解析樹的搜索範圍，並獲取更多有益的特徵信息？就讓我們帶著疑問，看一下本文的作者是如何解決這些問題的。

什麼是查詢圖

我們來考慮這樣一個問句「Who first voiced Meg on Family Guy?" (誰是第一個為Family Guy里的MegGriffin角色配音的人，註：Family Guy是美國的一部動畫片，MegGriffin是其中的一個角色，有兩個人先後為其配音過)

可以看出，這個問題是有一定難度的，我們在前一期談到，對於深度學習的向量建模法來說，first這種時序敏感（Time-Aware）詞常常會被模型忽略而得出錯誤答案。語義解析方法可以將first解析為邏輯形式的聚合函數（arg min），但它又難以將問題中的Meg這一縮寫詞通過辭彙表映射為知識庫中的MegGriffin。

想一想我們人如果給定知識庫會怎麼去尋找答案？首先我們也許不知道Meg具體是指哪個角色，但是我們可以先去知識庫里搜Family Guy，在它對應的知識庫子圖中搜索和Meg很接近的實體，也就是說我們一開始就藉助知識庫，幫我們縮小了範圍，這樣我們就很容易找到Meg其實對應的是MegGriffin。我們可以藉助這樣的思想來對我們的語義解析進行改進。

為了更好的去利用知識庫，我們用一種圖的形式來代替語法解析樹表示邏輯形式，這個圖被稱為查詢圖（query graph）。

問句「Who first voiced Meg on Family Guy?"對應的查詢圖如下圖所示：

查詢圖可以分為以下四個部分：

知識庫實體，在圖中用圓角矩形表示。中間變數，在圖中用白底圓圈表示。聚合函數，用菱形表示。lambda變數（答案），在圖中用灰底圓圈表示。圖中實體節點到答案變數的路徑可以轉化為一系列join操作，不同路徑可以通過intersection操作結合到一起，因此，該查詢圖在不考慮聚合函數argmin的情況下可以轉化為一個lambda表達式，即： $lambda x.exists y.cast(FamilyGuy, y) wedge actor(y,x) wedge character(y,MegGriffin)$

（如果你不懂 lambda表達式，沒有關係，上式表示我們要尋找x，使得在知識庫中存在實體y，滿足 1. y和FamilyGuy存在cast關係；2. y和x存在actor關係；3.y和MegGriffin存在character關係，這裡我們可以把y想像成是一個中間變數，通過對它增加約束來縮小它的範圍，通過它和答案x的關係來確定答案x）

有了查詢圖，通過將其轉化為lambda表達式就可以在知識庫中查詢得到答案。那麼，如何去構造查詢圖呢？

查詢圖的階段生成

我們先看看查詢圖的構成成分。

問題中的主題詞（可以看作是一個根節點）到答案變數的這條路徑（如Family Guy - y - x）包含了所有的中間變數，這條路徑可以看作是從問題到答案的一個核心推導過程，我們將其稱作核心推導鏈（coreninferential chain）。

而對於核心推導鏈里的中間變數，我們可以對它加一些約束（要求它與其他實體具有一定的關係，如 y - character -> Meg Griifin）和聚合函數（如 y - from -> arg min）。

因此我們查詢圖的生成，可以分為以下幾個步驟：確定主題詞，確定核心推導鏈，是否增加約束和聚合。整個過程可以用下面的這個有限狀態機自動機表示：

其中狀態集合 $S={phi,S_e,S_p,S_c}$ 分別表示空集、僅含主題詞節點、含核心推導鏈、含約束節點。而動作集合 $A={A_e,A_p,A_a,A_c}$ 分別表示選擇主題詞節點、選擇核心推導鏈、加入聚合函數、加入約束。

因此我們查詢圖可以分階段生成，這個生成的過程實質上是一個搜索。依照我們的有限狀態自動機，根據圖所處的狀態 $s$ ，我們可以確定在該狀態下可以採取的動作的集合 $Pi (s)$ （比如當前我們處在狀態 $phi$ ，根據有限自動機我們的動作為選擇主題詞節點，假設檢測出來問句中有3個主題詞候選，那麼我們的動作集合大小為3）。因此，我們的查詢圖生成實際上是一個搜索過程，如果對這個搜索不加任何限制，那麼這個搜索是指數級複雜度的。因此對於每一個狀態 $s$ ，我們可以用獎勵函數（reward function）對它進行評估，獎勵函數 $gamma$ 得分越高表示這個狀態對應的查詢圖和正確的語義解析表達越接近。我們用一個對數線性（log-linear）模型來學習獎勵函數（這裡涉及的一些概念不禁讓人想起增強學習）。有了獎勵函數，我們用best-first的策略利用優先隊列進行啟發式搜索，演算法流程如下：

其中 $T(s,a)$ 代表在 $s$ 狀態下採取動作 $a$ 後得到的新狀態，我們將優先隊列的大小 $N$ 限制為1000。上述演算法可以簡單概括為：每次從隊列中取出得分最高的狀態分別執行動作集中的每一個動作生成一批新的狀態並壓入優先隊列，始終記錄得分最高的狀態，最終將得分最高的狀態作為最後的查詢圖。

接下來，我們來看看每一種動作是怎麼執行的，以及如何去構造獎勵函數。我們依舊以問題「Who first voiced Meg on Family Guy?"為例。

主題詞鏈接

我們的第一種動作（action），就是從問題中確定主題詞，這個操作稱為主題詞鏈接（Linking Topic Entity）。作者使用了S-MART作為實體鏈接系統，該系統是針對帶噪音的短文本設計的，適合用於對問句提取主題詞，它會為相應的實體-自然語言短語鏈接對給出鏈接得分（Linking Score）。我們最多保留得分最高的10個實體作為候選，第一步如圖所示：

核心推導鏈

接下來，我們確定核心推導鏈。對於每一個候選的主題詞，將它在知識庫中對應的實體節點周圍長度為1的路徑（如下圖 $s_5$ ）和長度為2且包含CVT節點的路徑（如下圖 $s_3,s_4$ ）作為核心推導鏈的候選（CVT，即複合值類型 Compound Value Types，是freebase中用於表示複雜數據而引入的概念，不了解的朋友可以點擊該鏈接）。如下圖：

核心推導鏈其實就是將自然語言問題映射為一個謂語序列（如cast-actor），因此我們可以用卷積神經網路來對這個映射進行打分，如下圖所示：

我們將自然語言和謂語序列分別作為輸入，分別經過兩個不同的卷積神經網路得到一個300維的分散式表達，利用表達向量之間的相似度距離（如cosine距離）計算自然語言和謂語序列的語義相似度得分。由於我們上期我們已對卷積神經網路做過介紹，因此這裡我們對它不再贅述。需要注意的是，這裡的輸入採用的是字母三元組（letter-trigram）的方式，這是一個非常有趣的方式，類似於character-CNN。每個單詞都將它拆分成幾個字母三元組，作為CNN的輸入。比如單詞who可以拆為#-w-h，w-h-o，h-o-#。每個單詞通過前後添加符號#來區分單詞界限（並且單詞最短只含一個字母，添加兩個#可以保證能形成至少一個字母三元組）。

採用字母三元組的好處在於：1.減小輸入維度，這樣輸入維度可以穩定在字母集大小+1(#號)的三次方，即 $27^3$ ，而不是字典大小（同時可以處理一些字典中不存在的詞和一些低頻詞，如縮寫詞等等）。2.相同語義的詞語可能因為詞根等緣故，前綴或者後綴會比較相似，這樣能更好的提取單詞語義的特徵。3.對於現實生活中的用戶，有時候可能會發生單詞拼寫錯誤，但錯誤拼寫不會對這種輸入方式造成太大影響。

增加約束和聚合函數

我們通過增加約束和聚合函數的方式擴展查詢圖，縮小答案的範圍，以增加準確率，如下圖

如何去增加約束和聚合函數呢？作者採用了基於一些簡單規則的方式，比如當實體鏈接檢測到句子中出現其他實體，那麼我們可以增加一個約束。又比如句子中出現了first等時序敏感詞，我們可以增加聚合節點。具體來說，根據以下規則確定是否要為CVT節點添加約束節點或者聚合節點：

1.約束實體出現在問句中

2.約束謂詞表示事件的結束時間，但沒有值（這表示它是當前事件）

3.問題中出現約束實體名稱的一些單詞

4.謂語是people.marriage.type_of_union（這說明關係是否是家庭伴侶關係、婚姻關係還是民事關係）

5.問句中包含單詞 first 或者 oldest，並且謂語是from形式的謂語（表明事件的起始時間）

6.問句中包含單詞 last, latest 或 newest ，並且謂語是to形式的謂語（表明事件的結束時間）

而對於答案節點，如果包含以下之一的謂語，我們會添加一個約束節點：

people.person.gender / common.topic.notable types / common.topic.notable_for

獎勵函數的特徵定義

我們用對數線性模型訓練獎勵函數，因此我們要確定輸入向量，和信息抽取以及傳統語義解析方法一樣，我們手工定義一個特徵向量來表徵整個查詢圖的信息，將它作為對數線性模型的輸入。我們先來對特徵有個主觀上的感受，例如問題「Who first voiced Meg on Family Guy?」對應的查詢圖，它的特徵如下圖所示：

具體來說，我們從 主題詞鏈接、核心推導鏈、增加約束聚合三個方面定義特徵。

a.主題詞鏈接特徵：實體鏈接得分（EntityLinkingScore），由實體鏈接系統給出。

如 EntityLinkingScore(FamilyGuy,"Family Guy")=0.9

b.核心推導鏈特徵：

1.PatChain：將問句中的主題詞替換為實體符號，和謂語序列同時輸入兩個不同的CNN，根據CNN輸出的表達求語義相似度作為特徵。

如: PatChain("Who first voiced Meg on <e>", cast-actor) =0.7

2.QuesEP：將謂語序列和主題詞的規範名稱（canonical name）連接（concatenate）起來作為輸入，和問題求語義相似度。

如: QuesEP(q,「family guy cast-actor」) = 0.6

3.ClueWeb：用ClueWeb來訓練一個更加in-domain的模型。如果一句話包含兩個實體和謂語，那麼就把這句話和謂語作為一組數據對輸入模型進行訓練。注意：ClueWeb的輸入和PatChain是一樣的，但是其模型是用不同數據訓練的。

從這定義的三個特徵可以看出，這其實是一個ensemble模型，將三種模型的輸出結果進行了一個log-linear組合。

c.約束聚合特徵：

對於CVT節點有以下特徵：

1.約束實體是否出現在問句中如ConstraintEntityInQ("Meg Griffin",q)=1

2.是否是當前發生的事件

3.是否是當前發生的事件，且問句中包含關鍵詞「currently」,n「current」, 「now」, 「present」和「presently」

4.約束實體單詞出現在問句中的百分比如ConstraintEntityWord("Meg Griffin",q)=0.5

5.約束謂語的類型是people.marriage.type_of_union

6.問題中是否包含「first」或「oldest」，謂語是from形式謂語，並且CVT節點按該from性質排序是第一

7.問題中是否包含「last」, 「latest」或「newest」，謂語是to形式謂語，並且CVT節點按該to性質排序是最後

對於答案節點有以下特徵：

1.性別一致性（男性）：約束謂語是gender，並且問句中出現了以下男性關鍵詞中的一個{「dad」, 「father」,n「brother」, 「grandfather」, 「grandson」, 「son」,n「husband」}

2.性別一致性（女性）：約束謂語是gender，並且問句中出現了以下女性關鍵詞中的一個{「mom」, 「mother」,n「sister」, 「grandmother」, 「granddaughter」,n「daughter」, 「wife」}

3.當約束謂語是 notable_types 或 notable_for 時，約束實體單詞出現在問題中的百分比

d.總體特徵

查詢圖對應的答案數量NumAns和查詢圖的節點數NumNodes

模型學習

在信息抽取中，我們的模型是在進行二分類（根據特徵向量判定候選答案是否是正確答案），而在本文中，我們對模型不進行二分類，而是根據查詢圖對應的實體和真實答案的F1-score進行排名。基於lambda-rank演算法對一個一層的神經網路進行訓練。這樣做的好處是，有些查詢圖雖然查詢得到的答案和真實答案不完全相同，但根據它的相同程度（F1-score）也可以說它比完全錯誤的查詢圖要好。

論文實驗與總結

在訓練數據上，通過實體鏈接系統確定候選實體，候選實體到正確答案的知識庫路徑（長度限制為2）作為核心推導鏈的正樣本，錯誤查詢圖中的路徑作為負樣本。根據訓練數據，作者生成了17,277個F1-score不為0的查詢圖（正樣本）和1.7M完全錯誤的查詢圖（負樣本）對卷積神經網路進行訓練。

對於獎勵函數的訓練，為每個問題生成了4000個樣例（包含所有正確的查詢圖和隨機選擇的負樣本）以F1-score作為排名標準來訓練排名器（ranker）。

該方法與當時的所有baseline進行了比較，效果如下

可以看出該方法取得了相當大的提升，也因此獲得了當年的Outstanding paper。

本方法使用到了外部的實體鏈接系統，作者也比較了使用Freebase Search API時的性能，F1-score會下降約4.1。同時，作者也對核心推導鏈所涉及的三個特徵的性能進行了比較，核心推導鏈三個特徵的性能如下表：

我們可以發現，其實只使用PatChain的性能就已經很好了（達到了驚人的49.6），原因是WebQuestion里50%的問題可以只是用核心推導鏈就可以得出正確答案。

最後作者進行了錯誤分析，隨機選擇100個答錯的問題，發現35%的錯誤來自核心推導鏈構建錯誤，23%來自約束錯誤，8%來自實體鏈接錯誤，剩下34%的錯誤來自於標籤錯誤或不完整已經問題中的實體有歧義等。也就是說有34%的錯誤是數據的問題，這再一次顯示出了該方法的強大。

由於本期內容較多，我們再做一個快速的回顧：

1.考慮到傳統語義解析與KB結合不夠緊密，作者提出了查詢圖的概念

2.查詢圖的構造由實體鏈接系統確定主題詞，核心推導鏈，增加約束和聚合這幾種操作構成

3.對於查詢圖的每一個狀態，我們都用一個獎勵函數對它進行評價，使用優先隊列進行啟發式搜索構建查詢圖

4.通過查詢圖的實體鏈接得分、核心推導鏈三個特徵、約束聚合手工特徵以及全局特徵作為輸入向量，訓練單層神經網路作為排名器得到獎勵函數

5.核心推導鏈使用卷積神經網路（letter-trigram作為輸入）進行訓練，並且ensemble了三個不同數據訓練的模型

總的來說，我們可以看出，該方法幾乎融合了傳統語義解析、深度學習、信息抽取等方法的優點，還使用了部分手工特徵（對數據進行了仔細觀察和分析），確實是一個很令人驚嘆的方法。

在深度學習篇的中篇和上篇，我們可以看到都使用了卷積神經網路對模型進行提升。下一期，我們將進入深度學習篇的下篇，看如何使用更加複雜的深度學習模型進行KB-QA，為大家進一步揭開KB-QA的面紗。

敬請期待。