论文浅尝 | 基于知识图谱的子图匹配回答自然语言问题
本文轉載自公眾號：珞珈大數據。
? ? ? ? 本次論文講解的是胡森? 鄒磊? ?于旭? 王海勛? 趙東巖等作者寫的論文-Answering Natural Language Questions by Subgraph Matching over Knowledge Graphs，主要是分享一些閱讀論文的收獲，希望能對正在學習自然語言的初學者帶來一些啟發。本次ppt的參考資料主要是論文和北京大學鄒磊教授的面向知識圖譜的自然語言問答。
? ? ? 目前基于KG的問答模式有兩種，一種是基于信息檢索的方式，一種是基于語義分析的方式。前者較之于后者，沒有真正關心語義，主要是ranker算法，擅于處理簡單問題，后者則是從語義的角度將用戶的自然語言問題轉化為邏輯形式，再在KG中執行查詢。
? ? ? ?ganswer 就是基于語義分析的方法，區別于傳統的語義解析的方法，它是一種新穎的面向知識圖譜的自然語言問答系統，以圖數據驅動的視角回答RDF知識庫上的自然語言問題，本文解決了查詢匹配時自然語言問題的模糊性，如果找不到匹配，則會保存消除歧義的陳本，稱之為RDF Q / A的圖數據驅動方法。
? ? ? 雖然本文的方法中仍然存在兩個階段“問題理解”和“查詢評估”，但本文并不像現有解決方案那樣在問題理解步驟中生成SPARQL。 正如本文所知，SPARQL查詢也可以表示為查詢圖，它不包含任何歧義。?相反，構建了一個表示用戶查詢意圖的查詢圖，但它允許在問題理解階段存在歧義，例如短語鏈接和查詢圖結構的模糊性。?
? ? ? ?圖數據驅動解決方案的核心在于兩個方面：一個是如何精確構建語義查詢圖Q^s，另一個是如何有效地找到匹配。為了解決上述問題，本文提出了兩個不同的框架：第一個被稱為“關系（邊）優先”。這意味著總是從自然語言問句N中提取關系，并將它們表示為邊。然后，組裝這些邊形成一個語義查詢圖。第二個框架采用了另一個角度，稱為“節點優先”。它從查找節點（實體/類短語和通配符）開始，嘗試引入邊來連接它們以形成語義查詢圖Q^s。此外，兩個框架之間的另一個主要區別是，當問題句子中存在一些隱含或不確定的關系時，節點優先框架定義了Q^s的超級圖（稱為Q^u）。換句話說，節點優先框架并不是像關系優先框架那樣在子圖匹配評估之前修復Q^s的結構。
? ? ?
? ? ? 除了KG以外，我們在離線階段，構建了兩個字典，它們是實體提及字典和關系提及字典。 它們將用于在線階段從用戶的問題句子中提取實體和關系。實體提及字典有助于實體鏈接，關系提及字典將自然語言關系短語映射到RDF數據集中的謂詞。實體提及字典的構建不是本文的貢獻，本文采用CrossWikis詞典。關系提及字典借用TF-IDF計算映射關系rel的置信概率。
? ? ?
? ? ? 首先先介紹下關系優先框架，看整體的框架圖，首先給定一個自然語言問題：What is the budget of the film directed by Paul Anderson?，之后進行關系抽取構建語義查詢圖，進行短語映射到RDF中G上的實體或者謂詞邊徑，根據top-k子圖匹配算法計進行打分。
? ? ?
? ? ? 本文兩個框架都存在兩個階段：“問題理解”和“查詢評估”，在關系優先框架中，問題理解的目標是建立一個語義查詢圖來表示用戶在N中的查詢意圖，接下來我們詳細講一下如何構建一個語義查詢圖。
? ? ? 首先是關系識別，如何從一個自然語言問題識別關系提及，本文通過為關系提及字典中的所有關系提及建立倒排索引。對于上述具體問題，我們識別出buget of和direct by兩種關系。
? ? ?
? ? ?? ?在Y中找到關系后，我們查找兩個相關的節點。如果一個短語被認為是實體/類的提及，它就被認為是一個節點。? ? ? 外，節點也基于嵌入周圍的語法主語和類似對象的關系來識別，這些關系如ppt中所示。
? ? ? 假設我們找到一個關系rel的嵌入子樹y。我們通過檢查節點w中的每個短語w來確認arg1是否是實體/類提及，或者w和它的一個子元素之間是否存在上述主體類關系（通過檢查依賴樹中的邊標簽），如果存在主體關系，我們將該子項添加到arg1。同樣，arg2被類對象關系所識別。
? ? ? ?另一方面，當arg1 / arg2在這一步之后為空時，我們引入幾個啟發式規則如ppt中所示。如果在應用上述啟發式規則后，我們仍然無法找到節點短語arg1 /arg2，我們只需在進一步考慮丟棄關系提及rel。
? ? ? 在獲得了自然語言N的所有語義關系后，我們需要建立一個語義查詢圖。如上圖中的例子，兩個語義關系?“budget of”, “what”, “film”?和?“direct by”, “film”, “Paul Anderson”?表示為邊，兩個邊共享一個公共端點film，則這兩條邊共享一個公共端點，
? ? ?
? ? ? 討論如何將關系提及和節點短語映射到候選謂詞/謂詞路徑和實體/類，給定語義查詢圖中的節點vi，如果vi是一個實體短語或類短語，我們可以使用基于實體字典的實體鏈接算法來檢索所有可能對應于vi的實體/類（在RDF圖G中），標記為C（vi），例如v3（“Paul Anderson”）對應于“Paul Anderson（actor）”，“Paul Anderson”和“Paul ·W·S·Anderson”，?;如果vi是一個通配符（如wh-word），我們假設C（vi）包含RDF圖G中的所有頂點。使用δ（arg，u）或δ（arg，c）來表示置信概率。
? ? ? ?同樣，根據關系提及字典將Q^S中的每個邊vivj映射到候選預測列表，表示為?Cvivj。? 每個映射與置信概率? ? ? δ（rel，L）相關聯? ?和邊徑“v2v3”映射到?director?，?writer?和?producer?。? ?
? ? ?閱讀本文的時候是帶著問題去讀的，就是語義查詢圖需要轉換為sparql查詢語言，其實本文中有一句話寫到：SPARQL查詢也可以表示為查詢圖，它不包含任何歧義。 下面走進代碼。
? ? ?在ganswer的源碼中查找到關于如何去數據庫gstore中查找，也只是一種形式上的轉換。
? ? ? ?本文定義了子圖匹配的定義，需要滿足三個條件，假設所有候選列表都按置信概率的非遞減順序排列。Q^s的每個子圖匹配都有一個分數。 它是從每個邊和頂點映射的置信概率計算出來的。 計算公式如上，權重α的默認值是0.5，這意味著實體分數和關系分數具有相同的權重。
? ? ? ?一旦我們確定中每個候選人名單的候選人，我們就會獲得一個“選擇”。該選擇由n長度向量表示，其中n是候選列表的總數（算法3中的第3行）。最初矢量值為0，這意味著我們為每個候選列表選擇第一個候選（第4-5行）。每次我們從H的堆頂獲得最佳選擇時。我們可以使用所選候選項（第6-7行）替換中的所有頂點/邊界標簽來構建查詢圖。第8行應用VF2等現有的子圖同構算法來查找上G的所有子圖匹配。然后我們保持最大堆H，以保證從H得到的每個選擇在所有未嘗試選擇中得分最高，如第9行所示。對于每個候選列表Li，我們在當前選擇Γ的第i位添加一個以獲得新的選擇Γ并將其放入H.因此，當我們找到k個匹配時，我們可以提前終止。
? ? ? ?目前關系優先框架有兩個主要的障礙：一是高度依賴解析器和啟發式規則，如果句法依賴樹存在某些錯誤，就會導致錯誤的語義查詢圖的結構和錯誤的答案。另一個是無法識別隱含關系。如果關系沒有明確出現在問題句子中，則很難說明這種語義關系，因為我們的關系抽取依賴于關系提及字典中的關系提及。例如中國女孩。
? ? ? 考慮到上述兩個障礙，我們設計了一個健全的框架，即使存在隱含關系和依賴關系解析樹中的錯誤。 第二個框架中有兩個關鍵點：
? ? ? ? 1）第一步是從問句N中提取節點短語（如實體短語，類短語和wh-詞），而不是第一個框架中的關系提取。
? ? ? ? 2）我們不打算在問題理解步驟中構建語義查詢圖Q^s。 相反，我們構建了一個超語義查詢圖Q^u，它可能具有一些不確定或隱含的關系（即邊）。 換言之，我們允許在問題理解步驟中查詢圖的結構模糊性，這將在查詢評估步驟中解決。
? ? ? ? ?節點優先框架也存在問題理解和查詢執行兩個階段。問題理解部分的目標是構建超級語義查詢圖Q^u，超語義查詢圖與類似，但允許明確或不確定的關系。
? ? ?
? ? ?例如問題：What is the budget of the film directed by Paul Anderson and starred by a Chinese actor?? ? ? 通常，我們提取實體，類和通配符作為節點。 我們采用基于字典的實體鏈接方法來查找實體和類。 我們收集所有不能映射到任何實體和類作為通配符的wh-詞和名詞。節點識別結果如圖所示即“what”，“film“，”Paul Anderson“，”chinese“，”actor“等。
? ? ? 鑒于所有節點都已被識別，下一步是構建一個超語義查詢圖,? ? ? 給定一個節點集合V（已經在第一步中被識別）和問題句子的依賴樹Y，對于任意兩個 節點vi和vj（∈V），當且僅當vi和vj之間的簡單路徑不包含V中的其他節點時，引入vi和vj之間的邊。
? ? ? 依賴關系樹中“what”和“film”之間的路徑包含三個詞：“is”，“budget”和“of”，因此v1和v2之間的邊緣標簽（在中）是“…budget of “。 如果簡單路徑不包含任何單詞（例如“actor”和“Chinese”之間的路徑），則邊標簽為空。
? ? ? 映射節點和標記邊的方法與的短語映射相同,關注如何將未標記的邊映射到RDF圖G中的謂詞。首先vi與vj之間滿足以上兩個假設。
? ? ? ?如果兩個節點都是常數（即，實體或類），例如“中國演員”，則我們將兩個節點定位在RDF圖G處并找出它們之間的謂詞。如果一個節點vi是一個通配符，另一個vj是一個實體或類，我們在RDF圖G中定位vj，并選擇最頻繁的相鄰謂詞作為匹配邊緣的候選謂詞。
? ? ? 節點優先框架的算法采用自下而上的算法，具有四個特點，下面詳細介紹下算法。
? ? ? 與基線算法不同，我們在開始時不決定查詢圖。相反，我們試圖通過擴展當前的部分結構來構建“正確”的圖形結構。通常，在每一步中，我們通過擴展一個更多的邊來擴展當前的部分結構Q，（算法5中的第6行）。最初，Q僅包含中的一個起始頂點。我們選擇候選數量最少的頂點作為起始頂點。如果新的擴展的部分結構Q可以通過RDF圖G找到匹配（第7-11行），我們繼續搜索分支。此外，如果Q已經是的一個跨越子圖（第9-11行），我們記錄Q的匹配以及答案集RS中的匹配分數。我們只保留RS中的當前top-k匹配和當前閾值δ。如果Q無法通過RDF圖G找到匹配（第12-13行），我們回溯搜索分支。
? ? ? 我們分別使用兩個基準評估我們的DBpedia和Freebase系統。 對于DBpedia，我們使用QALD-6作為基準。 我們知道，QALD是一系列開放式域名問答系列活動，主要基于DBpedia。?
? ? ? NFF方法加入了QALD-6比賽，并以F-1的方式獲得第二名8。 NFF可以正確回答68個問題，而關系優先框架（RFF）可以正確回答40個問題。請注意，CANaLI旨在回答受控的自然語言問題，其中用戶需要在問句中指定精確的實體和謂詞（用URI表示）。換句話說，CANaLI要求用戶為短語鏈接做消歧任務，而CANaLI不是一個完全自然的語言問答系統。
? ? ? 對于Freebase，我們使用WebQuestions [17]作為基準，我們系統的平均F1（49.6％）略低于最先進的工作[21]（52.5％）和Yavuz等人。 [22]（52.6％）。? ? 這是因為WebQuestions中的問題比QALD更簡單，大多數問題可以轉化為“一個三重”的查詢，即只有一個實體和一個關系。實際上，我們的方法的優勢在于回答復雜的問題（即多跳關系問題），例如QALD基準測試中的一些問題。?
? ? ? 列出了在線演示的網址：http://ganswer.gstore-pku.com/，大家有興趣的可以在網站上嘗試一下。我試了關系優先框架和節點優先框架的兩個問題，并點擊查詢，獲得結果如ppt中所示。
分享至此接近尾聲，歡迎感興趣人士留言一起探討。
OpenKG.CN
中文開放知識圖譜（簡稱OpenKG.CN）旨在促進中文知識圖譜數據的開放與互聯，促進知識圖譜和語義技術的普及和廣泛應用。
點擊閱讀原文，進入 OpenKG 博客。
總結
以上是生活随笔為你收集整理的论文浅尝 | 基于知识图谱的子图匹配回答自然语言问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Dockerfile构建docker镜像
- 下一篇： python编程之如何判断某个元素在不在