1 引用
Min Wang1,2, Yanzhen Zou1,2(B), Yingkui Cao1,2, and Bing Xie1,2,Searching Software Knowledge Graph with Question,1 Key Laboratory of High Confidence Software Technologies, Peking University, Ministry of Education, Beijing 100871, China {wangmin1994,zouyz,caoyingkui,xiebing}@pku.edu.cn2 School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
2 摘要
研究人員在不同的領域建立了各種知識庫，這些知識庫通常使用圖形數據庫（Neo4j）來管理異構和聯繫較為寬泛的領域數據，提供結構化查詢接口，比如Cypher。然而，構造一個結構化查詢是非常耗時和消耗人力的，特別是當查詢非常複雜或知識圖譜的規模很大時。這篇論文提出了一種面向軟件知識圖譜的自然語言問題接口。它提取軟件知識庫的元模型，構造與問題相關的推理子圖，然後自動將自然語言問題轉換為結構化的Cypher查詢並返回相應的答案。該項目在兩個著名的開源軟件項目上進行了實驗，建立了它們的知識圖，驗證了其所採用的方法確實能夠準確地回答相應知識圖譜上的幾乎所有問題。
3 介紹
軟件重用是一種避免軟件開發重複效應的解決方案，它可以提高軟件工程的效率和質量。近年來，隨著開源軟件的迅速發展，互聯網上出現了大量可重用的軟件項目，如Apache Lucene、Apache POI、jfreeChart等，這些軟件項目除了源代碼外，還經常包含不同類型的自然語言文本資源，如用戶手冊、郵件列表等，問題報告、用戶論壇討論等。為了利用和分析這些文檔和源代碼，研究人員提出並構建了各種領域專用的軟件知識庫和知識圖譜。典型地，北京大學提出了特定領域的軟件項目知識圖譜，復旦大學提出了軟件項目API知識圖譜等等。
這些知識庫或知識圖譜通常使用Neo4j和其他支持形式查詢（即Cypher）的圖形數據庫存儲，要求用戶熟悉Cypher語法，並由用戶手動將其查詢意圖轉換為Cypher查詢語句。同時，手工構造Cypher查詢語句需要對知識圖譜的元模型有一個清晰的認識，比如知識圖譜中的知識實體類型。當元模型規模很大時，構造Cypher查詢的成本也很大。因此，有必要提供一個基於自然語言的知識庫或知識圖譜查詢接口，能夠自動將用戶的自然語言問題轉化為形式化的查詢語句。
圖 1查詢問題和相關推理子圖（ISG）
為了解決這一問題，現有的自然語言問題解析過程中的工作往往依賴於Internet上的大型通用領域知識庫（如WordNet、DbPydia、FrutBASE、Yago等），其計算非常複雜。典型地，Percy Liang等人利用Lambda-DCS（Dependency-Based Composition Semantics）獲得自然語言問題的邏輯表示，並基於其邏輯表示構造知識庫或知識圖譜的形式化查詢。然而，所有這些方法都面臨著自然語言描述精確轉換的挑戰。在我們的研究中，我們發現由於特定領域軟件的特性，軟件知識圖譜中的概念與一般開放領域知識庫中的概念有很大的不同。因此，匹配特定的謂語短語並不重要。相反，我們應該更加註重對問題整體語義的精確分析。上面圖1給出了一個來自開發人員的自然語言問題及其相應的結構化Cypher查詢語句的構造過程。當軟件開發人員重用ApacheLucene的開源項目時，他們會提出這樣的問題：“Alex寫的哪個問題修改了IndexWriter調用的方法?“，此語句中包含的關鍵字是issue、Alex、modify、method、call、IndexWriter等。每個關鍵字在知識圖上都有幾個概念與之對應。例如，Alex可以匹配到知識圖譜上具有name屬性的Person實體，但是知識圖譜有兩個相似的概念實體，即gitAuthor:Alex developers和SoUser:Alex（stackOver flow users）。類似地，IndexWriter可以與知識圖譜上實體的軟件項目源代碼知識相匹配，但它可以與類、方法和字段這三個級別的實體相匹配。那麼開發人員想要傳達的概念是什麼呢？哪些概念對應於知識圖譜實體？為了解決自然語言標記與知識圖譜實體之間的精確匹配問題，我們提出了一種在自然語言問題對應的知識圖譜中推理和定位子圖的方法，稱為推理子圖。推理子圖是從自然語言問題到Cypher查詢語句的中間橋樑：推理子圖的生成需要深入分析，需要利用知識圖譜信息和知識圖譜元模型來“匹配”自然語言問題中的語義。
在此基礎上，提出了一種基於軟件知識圖譜的自然語言查詢方法。通過提取軟件知識圖譜元模型，構造推理子圖，將自然語言問題精確地轉化為結構化的Cypher查詢，並在知識圖譜上顯示相應的答案。與當前工作相比，本文的主要貢獻有兩點：
\\1. 提出了一種將自然語言問題轉化為形式Cypher查詢的新方法。與傳統的語義分析不同，該算法生成一個推理子圖作為自然語言和形式查詢之間的轉換橋樑，能夠更準確地表達自然語言的深層含義。另一方面，通過測量推理子圖可以顯著地解決自然語言的歧義問題；
\\2. 實現了一個自然語言問題接口，並在Apache Lucene和Apache Nutch的開源項目的軟件項目知識圖譜上驗證了該方法。在軟件使用過程中，對於每一個知識圖譜提供了66個真實的自然語言問題，準確率為93.9%。
4 綜述：
在這篇論文中提出並實現了一種基於軟件知識圖譜的自然語言問答方法和系統：提出了推理子圖的概念，並通過生成和度量推理子圖，在自然語言問題和形式查詢語句之間建立了一個轉換橋樑。一方面，與傳統的語義分析邏輯形式系統相比，子圖轉換方法更容易表達自然語言的語義信息。另一方面，推理子圖的生成和度量可以解決自然語言的歧義問題。圖2顯示了本文所述方法的工作流程。該方法主要包括四個部分：（1）提取知識圖譜元模型；（2）自然語言問題的解析與匹配；（3）推理子圖的生成與度量；（4）構造Cypher查詢語句。
圖 2自然語言問答解決方案的工作流
4.1提取軟件項目知識圖譜元模型
為了適應不同的軟件項目知識圖譜，該方法定義了以下概念：（1）實體類型：知識圖譜中的每個實體都有一個類型。它定義為：{Entity Type}={Entity.Type}。（2）關係類型：知識圖譜中的每種關係類型由關係本身的名稱和關係兩端的實體類型決定。它定義為：{Relation Type}={（Relation.start.Type，Relation.end.Type，Relation.name）}。（3）屬性類型：知識圖譜中每個屬性的類型由其關聯的實體類型和屬性名決定。它定義為：{Attribute Type}={（Attribute.entity.Type，Attribute.name）}。（4）元模型：實體類型為節點，關係類型為邊，屬性類型為實體類型屬性的模式圖。它定義為：元模型={實體類型}，{關係類型}。基於上述概念，遍歷軟件項目知識圖譜，存儲其中的所有實體，並將所有實體類型記錄為元模型的實體，然後遍歷軟件項目知識圖譜，將所有關係存儲在其中，並將所有關係類型記錄為元模型的關係。
4.2分析和匹配自然語言問題
在本小節中，使用斯坦福NLP工具分析自然語言問題，包括標記段、詞性和過濾停用詞，然後將這些標記與知識圖譜中的元素進行匹配，提出了一種基於優先級的匹配算法，即將每個令牌（即自然語言問題的解析）與來自知識圖譜或知識圖譜元模型的元素進行分層匹配。每個令牌可以匹配到知識圖譜的任何元素，包括：實體、實體類型、屬性、屬性類型以及關係、關係類型等，基於軟件工程特定領域的知識手動構造同義詞表，例如，自然語言問題是：“何時Yonik Seeley更改了調用updatependingmerge方法的類？”顯然，我們可以將類與知識圖譜中的實體類型—類匹配，同樣，也可以將updatependingmerge與知識圖譜中的實體—名為updatependingmerge的方法匹配。但是，因為不能直接使用call和changd來匹配任何元素，所以使用同義表來匹配某些同義詞（例如，使用關係“call method”調用匹配，使用關係“commit”匹配changed等等），顯然，一個令牌可能匹配多個元素。為了解決這個問題，使用了最小編輯距離算法來計算令牌和元素之間的相似度，這樣就可以過濾一些不相關的元素。但是，該方法仍然保留了一些模糊匹配對，在後一種方法中可以消除這種模糊。最後如上文圖1所示，得到一個{tokens，elements}匹配圖。
4.3生成和度量推理子圖
由於自然語言的模糊性和複雜性，基於自然語言處理的令牌可以與不同的知識圖形元素相匹配，從而得到具有多種語義的候選子圖。為了保證候選子圖的質量，提出了一種擴展隱節點和隱邊的推理子圖生成算法，並計算了每個候選推理子圖的特徵值。測量特徵包括三個方面：文本相似度、結構相似度和推理子圖結構複雜度，然後根據測量結果向開發者推薦最優推理子圖。在這個過程中，一方面，建立了自然語言與形式查詢語句之間的中間轉換橋樑，另一方面，通過測量最優子圖來解決自然語言的歧義問題。最後，將最優推理子圖轉換為Cypher查詢語句並返回查詢結果。為了防止可能的語義理解偏差，還支持交互過程中推理子圖的可視化。在下一節中，將詳細介紹推理子圖的生成和度量。
4.4構造Cypher查詢語句
將推理子圖轉換為一個Cypher查詢語句。構造Cypher的過程可以分為三個部分，分別對應於Match、Where和Return語句。–Match語句對應於推理子圖的圖結構。然而，推理子圖表示二維結構信息，一個Match語句只描述一維結構信息—鏈。因此，我們採用啟發式的方法將推理子圖上的路徑劃分為若干個鏈和集合。–Where語句對應於推理子圖中節點的所有屬性值，每個屬性值是實體的過濾條件，因此屬性被添加到Where語句中。–Return語句由返回的節點屬性確定。返回的節點屬性由問題中的疑問詞確定。
5 生成和度量推理子圖
在第2.2節中，解析自然語言問題後，它們的標記可以匹配到多個知識圖譜元素。為了保證句子整體意義的正確性，提出了推理子圖的概念，並給出了相應的推理子圖生成和度量算法。推理子圖：推理子圖是知識圖譜中的一個子圖，包括：實體和邊，該子圖是由自然語言問題和知識圖譜中的{tokens，elements}對推斷出來的，因此該子圖包含與自然語言問題相似的語義。
5.1生成推理子圖
推理子圖是知識圖譜元模型上的一個子圖。由於自然語言的模糊性，自然語言的語義往往是不完整的。如圖1所示，在自然語言問題“Alex編寫的修改IndexWriter調用方法的問題”的例子中，我們需要在實體類（即IndexWriter）和IndexWriter調用的實體方法之間擴展一個隱藏的方法實體節點（即method）和一個隱藏的關聯關係（即have_method）。也就是說，自然語言問題的完整語義應該是：由於Alex提出的問題而修改方法，並且該方法由類IndexWriter中的方法成員方法調用。為了解決這個問題，我們提出了一種新的方法，稱為推理子圖。算法1說明了推理子圖的生成過程。輸入是一組斷開連接的子圖，根據{tokens，elements}匹配圖從知識圖譜中提取（第2.2節）。輸出是一組連通的推理子圖。首先，如第2-6行的算法所示，通過解析自然語言問題和知識圖譜中的匹配元素，得到一個匹配圖。由於自然語言的模糊性，每一個自然語言標記可能對應於多個知識圖相關元素。我們在前一個過程中保留了這些含糊不清之處。使用Bean搜索算法連接所有可能的{token，elements}匹配圖，從而獲得一組候選的斷開子圖，即Sdisconnect=Gdisconnect。每個集合表示與自然語言問題相對應的知識圖譜元素集合的可能性。然後，在算法1的第7-11行中，通過推理知識圖來擴展斷開子圖的隱藏節點，得到具有隱藏節點和隱藏邊的圖，即Shidden=Ghidden。最後，在算法1的第12-17行中，使用最小生成樹算法連接這些斷開的子圖，從而得到一組連接的推理子圖，即Sconnect。
圖 3-算法1
5.2測量推理子圖
在上述步驟中，生成了一組推理子圖，必須從中選擇最優推理子圖作為帶有Cypher查詢語句的橋。
文中提出了一系列啟發式規則來計算被測特徵：（1）第2.2節中推理子圖與NL問題的文本相似度，如圖1所示，保留了一些與令牌匹配的候選元素，即每個令牌都有一個候選元素列表，此列表中的每個元素都有一個與令牌相似的秩，因此，我們可以計算推理子圖與自然語言問題之間的相似性，如下所示：
在上面的公式中，t表示解析自然語言問題（第4.2節）中的標記，t.mapping.rank表示候選列表中元素的秩，k表示匹配圖中所有元素的數目，ωt-similar表示特徵集中文本相似性的權重，可以手動指定權重值。
（2）推理子圖與自然語言問題的結構相似性
計算推理子圖與自然語言問題的結構相似性，我們將推理子圖中節點對之間的相對距離與自然語言問題中對應詞的相對距離之差作為度量因子。結構相似性計算如下：
6 實驗與評價
基於上述解決方案，設計並實現了一個軟件項目知識圖的自然語言問答系統SnowSearch（software knowledge Search）。該實驗用於回答以下研究問題：
研究問題1：SnowSearch是否有效地回答了自然語言問題？
當開發人員輸入一個自然語言問題時，該方法是否能夠有效地返回正確的查詢結果。
研究問題2：推理子圖解決了自然語言和Cypher查詢之間的轉換嗎？
提出了一種基於知識圖的推理子圖方法，作為自然語言與形式化查詢語句之間的橋樑。該方法關心的是推理子圖能否更有效、更準確地表達自然語言。
研究問題3:推理子圖的三個度量特徵是否合理？
提出了文本相似度、結構相似度和推理子圖複雜度的三個度量指標來度量推理子圖，從而得到最優子圖。
6.1軟件項目知識圖譜
以下工作是基於Lin等人提出的軟件項目知識圖譜。軟件知識圖譜被定義為表示軟件領域、項目和系統中相關知識的圖。在軟件知識圖譜中，節點表示軟件知識實體（例如類、問題報告和業務概念），有向邊表示這些實體之間的各種關係（例如方法調用和可追溯性鏈接）。基於他們的工具，可以自動構建一個軟件項目知識圖譜。為了評估所用方法，構建了兩個著名的開源軟件項目Apache Lucene和Apache Nutch的知識圖譜。開源項目Lucene是一個Java實現的信息檢索程序庫；開源項目Nutch是一個Java實現的開源搜索引擎。我們在互聯網上的Lucene和Nutch上收集了大量的多源異構數據，包括軟件源代碼、郵件列表、問題報告和StackOver-flow帖子。相關資源統計見下面的表1。例如，開源項目Lucene是一個用Java語言實現的廣為人知的信息檢索庫。我們在互聯網上收集了超過8GB的Lucene項目數據，包括67個版本、80多萬行源代碼、24.4萬封電子郵件、7500多份問題報告以及大量相關的StackOver Flow帖子。最後構造了Apache-Lucene的知識圖譜，圖的統計如下面表2所示。
表 1--Apache-Lucene的資源統計表
表 2--軟件項目知識圖譜的元模型
6.2問題示例
邀請了四位熟悉Apache Lucene和Nutch的開發人員來問一些與這兩個項目相關的自然語言問題。這些問題主要涉及事實問題，如誰、什麼、何時和列表。最後，四位開發人員提出了關於Lucene項目的66個問題和關於Nutch項目的66個問題。如下表3所示，隨機選擇了22個開發人員向Lucene開源項目提出的示例問題。其中，推理子圖中與What或Which類型、Who類型和When類型相關的實體數平均約為4個，推理子圖中的邊數平均約為3個。列表型問題對應的推理子圖中的實體數平均約為97個，推理子圖中的邊數平均為96左右，22個自然語言問題實例的數據分析結果表明，軟件重用過程中開發人員提出的自然語言問題客觀存在，對知識庫查詢具有一定的推理複雜度和問答能力。
表3--使用Lucene知識圖譜搜索的問題
表 4--Lucene and Nutch項目的132個精確結果展示
6.3 研究問題1：問答效果評估
僅需考慮TOP-1和TOP-2的每一項精度，即可進行問答效果評估。也就是說，生成的正確的Cypher查詢在所有可能的Cypher候選集中排名在前k位，因此問答結果是正確的。實驗結果見上表4。由此可見，Lucene項目知識圖的66個問題中，有62個問題返回了正確的Cypher queryintop-1，64個問題返回了正確的Cypher queryintop-2。Nutch項目知識圖譜的66個問題得到了相同的實驗結果，這表明不同軟件項目的大多數自然語言問題都可以返回正確的Cypher queryintop-1回答正確。實驗結果表明，本文提出的基於軟件項目知識圖譜的自然語言問答方法的正確率達到93.3%以上。考慮到列表型問題的自然語言語法比較複雜，推理子圖中對應的實體比較複雜，自然語言問題的解析和匹配可能會產生一定的錯誤。例如：在自然語言問題“列出所有提到IndexWriter的JiraIssue”中，由於JiraIssue和IndexWriter涉及大量實體，導致自然語言問題的回答失敗。對於其他問題，比如什麼或哪一個，什麼時候，誰，這種方法都有很好的問答效果。
6.4 研究問題2：推理子圖有效性評價
推理子圖是自然語言和形式查詢語句之間的橋樑。為了更好地表達自然語言問題的完整語義，在生成推理子圖的過程中，我們必須擴展隱藏節點和隱藏邊，例如，在自然語言問題示例中，如圖1所示“Alex編寫的修改IndexWriter調用的方法的問題”，需要添加三個隱藏節點，即method、gitAuthor和Commit，以及兩個隱藏邊，即方法和代碼說明。為了驗證推理子圖在自然語言到形式查詢轉換中的作用，該方法統計分析了推理子圖中添加的隱藏節點元素的數量。如圖3所示，Apache Lucene中64%的問題需要在推理子圖中添加隱藏節點，如圖4所示，Apache Lucene中55%的問題需要在推理子圖中添加隱藏邊。Apache Nutch項目中也提供了相同的統計數據。這說明在將自然語言問題轉換為形式化查詢語句的過程中，超過一半的自然語言問題需要擴展。如果不使用推理子圖來擴展隱藏的節點和邊，而只是簡單地組合自然語言標記並構造形式化查詢，那麼一半以上的自然語言問題就無法得到正確的答案。因此，本文提出的推理子圖可以有效地解決自然語言與Cypher查詢之間的轉換問題。
圖3 Lucene搜索問題時推理子圖中隱藏節點和邊的分佈
圖4 Nutch搜索問題時推理子圖中隱藏節點和邊的分佈
6.5 研究問題3：測量策略比較評價
該方法設計了一系列的比較實驗，以比較三個度量的測量結果：“文本相似度+結構相似性”、“文本相似度+結構複雜性”、“結構相似性+結構複雜性”，從而驗證了度量中的每個度量。下圖5實驗結果表明：如下圖圖5所示，考慮到top-1中正確的Cypher，僅兩個測量特徵的精度就約為50%，而本方法（三個測量特徵的組合）的精度高達94%，考慮到top-2中正確的Cypher，“文本相似度+結構相似性”、“文本相似度+結構複雜度”和“結構複雜性+結構相似性”的測量策略的準確率分別為55%、63%和59%，而本方法的準確率可以達到97%。這意味著，如果我們放棄任何度量特徵，問題回答的準確性將急劇下降。這也證明了我們提出的三個指標是合理的。
圖 5三種測量方法比較分析的精確結果
7 相關工作
許多工作試圖為圖形數據庫或知識構建一個自然語言查詢接口，該接口大多采用NoSQL數據庫。現有的研究主要包括：（1）基於句法分析的方法；（2）基於機器學習的方法。基於句法分析的方法的基本過程是：首先對自然語言查詢進行解析，構造自然語言查詢的句法依賴樹，然後通過節點匹配、規則擴展等方法進行查詢轉換，得到最終的形式化查詢語句。通常，Berant等人提出訓練一個語義解析器，用於在知識庫上進行自然語言問答。其基本過程是：利用經過訓練的語義分析器將輸入的自然語言問題解析成一個邏輯形式系統，然後基於結構化邏輯表達式從知識庫中搜索答案；基於DCS-L、Yao等的工作。在知識庫中定位候選實體，構建主題圖作為候選答案，為自然語言問題和候選答案實體建立特徵向量，並將原始問題轉化為候選答案的二元分類。這種方法的優點之一是基於形式化查詢結果，用戶可以確定查詢結果的可靠性。但是在這些研究工作中，用戶在自然語言查詢中輸入的單詞仍然需要與數據庫表中的某個信息（表名、屬性名、記錄等）顯式對應，否則語法樹不完整，無法得到正確的答案。
在基於機器學習方法的自然語言查詢應答庫的研究中，早期的工作主要是在用戶進行查詢時記錄信息，並根據歷史查詢信息輔助下一次查詢。Freitas等人利用交互式算法優化查詢結果，設計用戶反饋方法，提高查詢精度。其基本思想是在用戶輸入查詢時記錄反饋信息，然後利用歷史查詢輔助下一次查詢輸入。此方法可以優化大多數方法，但需要更頻繁地使用它來累積用戶的使用歷史。Tunstall Pedoe等人在生成模板的過程中利用人的因素，從雅虎和其他社區的現有問題中提取正確的自然語言問題模板。最近的其他代表性工作主要依賴於機器學習，包括序列模型、神經網絡模型、注意機制等。尤其是深度學習已經成為知識庫自然語言問答的主要技術之一。 Wen-tauYih 等人定義了一種查詢子圖方法，查詢子圖可以直接從知識庫轉換為邏輯形式系統，語義解析的任務是生成查詢子圖，利用知識庫進行物理前鏈索引，並用Deep-CNN計算問題與邏輯謂詞的匹配度，得到顯著效果。
8 結論
這篇論文提出並實現了軟件項目知識圖譜的自然語言問題接口。它提取軟件知識庫的元模型，構造與問題相關的推理子圖，然後自動將自然語言問題轉換為結構化的Cypher查詢並返回相應的答案。利用開源軟件項目Lucene和開源軟件項目Nutch的知識圖來評估該方法。結果表明，這種方法能夠有效地回答開發人員提出的自然語言問題，從而實現軟件重用。在未來，作者及其團隊也將嘗試通過增加人機交互來解決更復雜的自然語言問答問題。
致謝
本文由南京大學軟件學院2019級碩士王悅翻譯轉述。
感謝國家重點研發計劃（2018YFB1403400）和國家自然科學基金（61690200）支持！
閱讀更多 慕測科技 的文章
