論文解讀：Query Graph Generation for Answering Multi-hop Complex Questions from Knowledge Bases（2020ACL）
簡要資訊：
| 序号 | 屬性 | 值 |
|---|---|---|
| 1 | 模型名稱 | - |
| 2 | 所屬領域 | 自然語言處理 |
| 3 | 研究内容 | KBQA |
| 4 | 核心内容 | Beam search；Query Graph Generation |
| 5 | GitHub源碼 | https://github.com/lanyunshi/Multi-hopComplexKBQA |
| 6 | 論文PDF | https://www.aclweb.org/anthology/2020.acl-main.91.pdf |
一、摘要：
先前的工作關于從知識庫中回答複雜的問題通常單獨處理兩類複雜的問題，分别是包含限制條件的問題和含有多跳推理的問題。本文目标是同時處理這兩類問題。我們發現較早的将限制條件加入到查詢圖中可以有效地縮減搜尋空間，受到該發現的動機，我們提出一種新的可編輯查詢圖生成方法（modified stage query graph generation），通過更加靈活的方法生成查詢圖。我們的方法在三個基準資料集上達到最有效果。
二、動機：
- 先前的KBQA工作關注于簡單的問題和單跳推理，但現實中，問題往往很複雜。我們總結了兩種複雜問題類型，包括：
（1）single-relation questions with constraint：問題的答案（answer entity）與主題詞（topic entity）是單跳關系，但其包含一些限制條件，例如“the first”、“in two years”等。這一類問題的解決方法稱為staged query graph generation method，其旨在首先識别出問題的答案與主題詞之間的關系（即relation detection），其次在所有與主題詞有該關系相連的候選的答案中根據限制條件進行篩選，最終形成一個查詢圖。
（2）Questions with multiple hops of relations：給定的問題對應的答案與主題詞之間存在多跳關系。回答此類問題，通常需要多跳推理，即從主題詞開始尋找一條到達答案實體的路徑。事實上，随着跳數的增加，搜尋空間也在不斷上升，是以如何降低搜尋空間？一種方法是使用集束搜尋（beam search）。
- 我們發現現階段的工作沒有同時解決這兩個問題，是以本文，我們同時處理包含限制條件和多跳關系的問題。我們提出一種方法同時将限制條件和關系路徑推理結合起來。
三、方法：
問題定義：給定一個知識庫，其由一系列三元組構成。給定一個問題 Q ，任務的目标是從知識庫中尋找答案。
3.1 staged query graph generation method
查詢圖包含四種類型的結點：（1）grounded entity：表示KB中存在的實體；（2）existential variable：代表虛拟的結點，該結點隻代表一個變量；（3）lambda variable：表示候選答案對應的變量；（4）aggregation function：一種操作函數，包括argmin、count等。一種查詢圖如下圖所示，可知，查詢圖類似于一種模闆，根據答案生成的查詢圖之後去知識庫中做比對。
是以，staged query graph generation method可以概括分為四個步驟：
- step1：從grounded entity（即主題詞）開始尋找一條查詢路徑；
- step2：在每一條路徑上，識别出相應的限制條件，限制條件可以是一個新的grounded entity實體，也可以是對應一類aggregation function；
- step3：根據前兩步得到的許多查詢圖，根據其與答案的相似度進行排序；
- step4：執行最相關的查詢圖，并從KB中進行比對以獲得答案；
問題動機：
- 作者發現，如果完全将這個方法用在多跳+限制類的問題上，很難有效生成查詢圖，且随着路徑的變長，搜尋空間或非常大。例如當跳數達到3個時，候選的路徑數量會超過10000個；
- 現階段解決這問題的有集束搜尋（beam search），但他們沒有考慮到限制條件。我們發現，當在集束搜尋中考慮到了限制條件時，可以進一步縮減空間，也可以指導查詢正确的路徑。
3.2 查詢圖生成
我們的方法是同時考慮限制條件和多跳路徑查詢兩個方面，在多跳路徑查詢時使用集束搜尋，每次搜尋時融入限制條件以縮減搜尋空間。每一跳相當于一次疊代：
**查詢圖生成的疊代步驟：**假設在第 t 次疊代，生成了 K 個查詢圖（K即為beam search的大小），記做 G t \mathcal{G}_t Gt ，則在第 t+1 時，對于每一個查詢圖 g ∈ G t g \in \mathcal{G}_t g∈Gt 我們從 extend、connect和aggregate三個動作中挑選一個動作用于對 g g g 進行擴張（擴張是指在此基礎上添加一個邊和一個節點， 三個動作對于三種擴張方式）。對于第 t 次疊代生成的所有查詢圖都分别執行這三個動作，形成 G 0 t + 1 \mathcal{G^{0}}_{t+1} G0t+1 (可知此時查詢圖數量是t時刻的3倍)。随後對這些查詢圖使用打分函數進行排序，并挑選分值最高的 K 個，最終形成 t+1 時刻的查詢圖 G t + 1 \mathcal{G_{t+1}} Gt+1。一直疊代下去使得得分不再身升高。
根據先前工作描述，這裡的三種擴張動作：
- extend：增加關系路徑，隻有該動作是增加多跳路徑的長度的
- connect：将其他的grounded entity或lambda variable連接配接到CVT結點（existential variable），該動作主要用于實體限制
-
aggregate：将aggregate function添加到lambda variable或CVT結點上，該動作主要将函數加入到限制中
為了保證多跳，本文允許extend動作在connect和aggregate動作之後執行
3.3 查詢圖排序
最後一次疊代，将所有的查詢圖進行特征提取。作者設計了7個特征，分别有：
- BERT-based semantic matching：将查詢圖對應的動作序列以及整個圖的實體/關系的token序列進行表征。例如上圖(a)對應的序列為（the, jeff, probst, show, nominated, for, nominee）；
- entity link score：實體連結工具提供的打分；
- grounded entity number：該類實體在目前查詢圖中的個數；
- entity type number：實體類型的種類數
- temporal expressions number：模式數量；
- superlative number；
- answer entity number：答案數量；
最終7個特征喂入一個全連接配接層并進行打分。在訓練過程中，由于每個查詢圖并不知道哪個是ground truth，是以選擇使用政策梯度進行訓練，其中獎勵函數為預測的答案為ground truth的F1值。（訓練的方法詳見論文：《Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning》）
四、實驗
實作細節：
- 使用現有的實體連結工具、實體類型工具等完成question與KB的連結；
- 初始化BERT base模型，dropout=0.1，hidden size=768，層數為6，多頭注意力頭數為12，将Freebase作為知識庫，beam search大小 K=3。
- 資料集使用ComplexWebQuestions（CWQ）、WebQuestions（WQSP）和ComplexQuestions（CQ）
- Freebase知識庫下載下傳位址：https://developers.google.com/freebase/
實驗結果：
（a）為資料集的統計；（b）為本文的模型與baseline的對比，（c）為消融實驗
錯誤分析： 作者随機挑選100個錯誤的樣例并進行分析：
- ranking error：有一些relation很難被識别檢測，導緻查詢圖的排序出現錯誤。例如一些表達關系的詞存在簡寫，比如““Who was VP for Nixon?”文具中，“VP”表達的是“vice president”，但很那被了解，是以這部分需要引入外部知識來輔助；
- topic linking error：實體連結工具對主題詞連結産生的誤差；
- generation limitation：查詢圖生成的方法有限，導緻有一些問題無法生成查詢圖（這個說明了目前的查詢圖方法還是有限的）
五、總結
優勢： 本篇文章主要的工作切入點是在生成查詢圖時，如何盡可能的縮小搜尋空間的同時，運用限制條件和集束搜尋同時解決複雜限制和多跳的KBQA，而對查詢圖的排序則使用簡單的神經網絡打分實作，是以該方法的解釋性很強（查詢圖的每一步疊代生成是确定的三種動作規則）；
缺點： 泛化能力有限，雖然能夠解決作者提出的問題，但是對于查詢圖的生成是過于規則化，泛化能力有限；
相關部落格： 實踐案例丨ACL2020 KBQA 基于查詢圖生成回答多跳複雜問題