本文介紹的是ICDE 2020入選論文《AutoSF: Searching Scoring Functions for Knowledge Graph Embedding》，作者來自香港科技大學和第四範式。
作者 | 張永祺、姚權銘
| 戴文淵、陳 雷
- 論文地址：https://arxiv.org/pdf/1904.11682.pdf
- 代碼地址：https://github.com/yzhangee/AutoSF
- 幻燈片地址：https://github.com/yzhangee/research/blob/master/ICDE2020_slides.pdf
1 簡介
評分函數（Scoring Function，SF）是衡量知識圖譜（Knowledge Graph，KG）中三元組可編程性的重要指標，已成為知識圖譜嵌入的關鍵。近年來，大量的評分函數被設計出來，用於捕捉知識圖譜中的各種關係。然而，由於關係可能表現出複雜的模式，而這些模式在訓練前很難推斷，因此在現有的基準數據集上，沒有一個能比其他模式表現得更好。
本次工作年來自動化機器學習（AutoML）的啟發，提出了一種自動設計和發現知識圖譜嵌入（KG Embedding，KGE）中更好SF的AutoSF算法。通過使用一個由濾波器和具有特定領域知識的預測器增強的漸進貪婪搜索算法，可以有效地設計出新的、與數據相關、且性能優於人類最新設計模型的SF。邊預測和三元組分類結果表明，AutoSF搜索的評分函數具有KG依賴性，且比人最新設計的評分函數性能更優。
2 背景介紹
知識圖譜(KG)作為一種特殊的以實體為節點、以關係為邊的圖結構，可提供更高效的搜索結果、發現節點的潛在特性、並啟發瞭如結構化搜索等許多下游應用，對數據挖掘和機器學習都具有重要的意義。其目標是儘可能的保存原始圖譜信息，改善推薦、問答等下游機器學習任務。在知識圖譜中，每條邊都表示為一個三元組，其形式（頭實體、關係、尾實體）表示為（h、r、t）。近年來廣受關注的知識圖譜嵌入（KGE）是用於解決如何量化三元組合理性的有效方法之一，且極具前景。在一組三元組中，KGE可學習實體和關係的低維向量表示，從而使三元組的合理性可以量化。評分函數基於嵌入返回（h，r，t）的評分，用於度量合理性。一般來說，SF是由人類設計和選擇的，它對學習嵌入系統的質量有著重要的影響。
知識圖譜示例
自從知識圖譜嵌入發明以來，學術界提出了許多評分函數。例如知名的TransE和相關拓展模型TransH、TransR，將嵌入向量投影到不同的空間，並使嵌入能夠對一對多、多對一或多對多的關係建模。這些模型被歸類為平移距離模型（Translational Distance Models，TDMs）。然而，TDMs表達能力不強，實證性能不如其他模型。RESCAL、DistMult、ComplEx、Analogy和最近提出的SimplE使用雙線性函數h⊤Rt來建模三元組的合理性，其中R是與關係嵌入相關的平方矩陣。這些模型屬於雙線性模型BiLinear Models（BLMs）。不同的BLMs使用不同的約束條件對關係矩陣R進行正則化，以適應不同的數據集。受深度學習的啟發，MLP、NTM、Neural LP和convE等神經網絡模型（Neural Network Models，NNMs）也被用作SFs。儘管神經網絡功能強大，表達能力強，但由於沒有很好的正則化，NNMs在KGE中的性能並不理想。
在現有的SF中，基於BLM的SF是最有效的，這一點可以從最新的論文和關於表現力的理論保證中看出。然而，由於不同的KG在關係上有不同的模式，能夠很好適應一個KG的SF在其他KG上的表現可能不一致，所以設計新的SF以超過最先進的SF是一個挑戰，如何為某個KG選擇、設計一個好的SF更是難上加難。
3 本次工作的方法
近年來，自動化機器學習（AutoML）因可大幅降低機器學習的門檻和人力成本受到了學術界和工業界的廣泛關注。其在超參數優化、模型選擇、神經網絡搜索和特徵工程等方面顯示出其強大的功能。近年來很熱門的神經網絡搜索算法（Neural architecture search，NAS），設計出的模型，可以比人類設計的網絡具有更少的參數和更好的性能。
自動化機器學習（AutoML）示意圖 [Yao et.al. arvix 2018]
受AutoML的啟發，此次工作提出了自動評分函數（AutoSF），可以自動搜索給定KG的SF,其不僅可以適應不同的KG，還可降低門檻和成本。然而，要實現上述目標並非易事，其中需要考慮兩個重要方面：一是搜索空間，它有助於找出目標問題建模的重要性質；二是搜索算法，它決定了在空間搜索的效率。
該工作的解決思路是：針對不同的KG 結構自適應搜索調整BLMs，從而設計出新的數據相關的SF。此外，如何利用KG領域特有的性質，來幫助AutoSF的搜索是非常重要的。我們首先在常用的SF上確定一個統一的表示，用來建立AutoSF的搜索空間。然後，我們提出一個貪婪算法來有效地搜索SF，並通過濾波器和預測器進一步加快了算法的速度，避免了重複訓練具有相同表達能力的SF，有助於在模型訓練前的搜索過程中移除效果差的候選對象。
具體而言，不同的SF對KG中不同關係的建模能力是有區別的，如下表所示，DistMult只能針對對稱關係建模，而其他幾種SF對非對稱，反對稱等關係有著不同建模能力。同時他們的表達形式也是有區別的。
為了建立有效的搜索空間，AutoSF首先針對表中的幾種BLM建立了統一的表達形式，即不同SF都可以表達成的形式，其中h和t為頭尾實體的嵌入表達，R是一個跟關係嵌入相關的方陣，而這些SF的區別就在於R的形式不同。如下圖所示，這些SF的R都可以抽象成4x4的分塊矩陣，區別主要在如何將關係嵌入r填入其中每一塊，及它們的正負號。基於此觀察，AutoSF抽象除了下圖(e)所示的搜索空間，可以有效覆蓋已知的BLM，同時有能力探索新穎的模型。
考慮到這個搜索空間中有個不同結構，而訓練和評估每一個結構都需要花費數十分鐘的時間，如何快速有效地搜索更好的結構，是搜索算法所需要關心的問題。
AutoSF首先利用貪婪算法，從簡單模型漸進搜索更復雜的模型。
為進一步提高搜索效率，我們提出一個特殊的濾波器，可以把不滿秩的矩陣，以及等價的矩陣結構過濾掉，避免在這些不好的、等價的模型上花費時間去評估。同時，為了挖掘KG中對稱性等重要性質，採用預測器的技術，從矩陣結構提取對稱相關的特徵（如下圖），再利用評估過的結果，學習特徵與效果之間的映射，從而可以只利用矩陣結構，選出更值得訓練的模型。
基於貪心算法，濾波器，預測器的搜索算法，使得AutoSF可以在僅搜索上百個模型的基礎上，就能找到比現有模型更好的SF。
該工作的貢獻在於：
- 首先，該工作對現有的SF進行了重要的觀察，使我們能夠以統一的形式表示基於BLM的SF。在統一表示的基礎上，將SF的設計表示為AutoML問題（AutoSF），並建立相應的搜索空間，涵蓋了人類設計的優秀SF，且足夠廣泛。
- 其次，該工作發現不同的KG在對稱、不對稱、逆等關係上具有不同的性質，因此對KGE模型進行領域特定分析，並設計約束以有效地指導後續的空間搜索。
- 第三，該工作提出了一個漸進貪婪算法來搜索空間，通過建立一個濾波器以避免訓練冗餘的SF，並建立具有特定對稱相關特性（SRF）的預測器以選擇有效的SF。該算法通過捕獲候選SF的特定領域屬性，顯著減小搜索空間的大小。
- 最後，在五個流行的鏈接預測和三重集分類任務基準上的實驗結果表明，由AutoSF搜索的SF優於由人類設計的最新SF。此外，搜索到的SF具有KG依賴性。我們進一步對搜索到的SF進行了案例研究，為分析KG提供了方法，且為以後的研究提供了更好的理解。
4 實驗結果
該工作在五個流行的鏈接預測和三重集分類任務基準上進行了實驗。
驗證AutoSF的有效性
下圖中顯示了AutoSF和當前最先進SF的測試性能比較，可以看出，在BLMs中沒有絕對的贏家。
此外，論文中繪製了用AutoSF搜索到的最佳SF和基準模型DistMult、Analogy、ComplEx、SimplE的學習曲線。如下圖所示，搜索到的SF不僅優於基線，而且收斂速度更快，這可能是因為這些SF能夠更好地捕獲這些數據集中的關係。
Fig. 4. Comparison on clock time (in hours) of model training v.s testing MRR between search SFs (by AutoSF) and human-designed ones.
驗證AutoSF的特殊性
為了驗證搜索到的SFs對KG具有依賴性且是新穎的，我們將其繪製在下圖中。很明顯，這些SF是不同的，而且它們是不等價的。
如下表所示， WN18和FB15k有許多對稱、反對稱關係和逆關係對，在它們上面搜索的最佳SF非常相似並且具有相同的對稱性特徵。其他三個數據集更真實，包含的對稱、反對稱和逆關係較少，因此具有不同的對稱特徵，這也反應了預測器的重要性。
驗證AutoSF的效率
該工作將AutoSF與隨機搜索和Bayes算法、以及一個一般近似器進行了比較。如下圖所示，一般近似器的性能比BLM差得多，因為它太靈活，無法考慮領域特定的約束，以及容易過擬合。對於BLM的設置，Bayes算法可以提高隨機搜索的效率，但卻很容易陷入局部最優，而且沒有考慮KG的領域特有性質。綜合來看，AutoSF是最高效的，且具有最佳任意時間性能。
5 結語
本文提出了一種自動設計和發現KGE中更好SF算法AutoSF。通過使用一個由濾波器和具有特定領域知識的預測器增強的漸進貪婪搜索算法，AutoSF可以在巨大搜索空間中有效地設計出與KG相關的、新的、優於人類的SF。搜索算法中的每一個分量都是有意義的，並且搜索對於超參數不敏感。
在未來的工作中，一個有希望的方向是探索如何在特定領域約束下有效地搜索基於神經網絡模型的SF。AutoSF中使用的貪婪算法在某種程度上限制了對搜索空間的探索，這是一個有待解決的潛在問題。早停法等快速評估方法可以與該工作提出的方法相結合，以進一步提高搜索效率。
閱讀更多 AI科技評論 的文章
