前不久，來自第四范式的資深研究員姚權(quán)銘博士和大家分享了其參與并被 NeurIPS 2020 接收的論文《Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding》。

這項(xiàng)研究受神經(jīng)架構(gòu)搜索（NAS）的啟發(fā)，提出將 Interstellar 作為一種處理關(guān)系路徑中信息的循環(huán)架構(gòu)。此外，該研究中的新型混合搜索算法突破了 stand-alone 和 one-shot 搜索方法的局限，并且有希望應(yīng)用于其他具有復(fù)雜搜索空間的領(lǐng)域。

視頻鏈接：https://v.qq.com/x/page/n3207ugke4j.html?start=6

知識(shí)圖譜嵌入（Knowledge Graph Embedding）目前在學(xué)習(xí)知識(shí)圖譜（KG）中的知識(shí)表達(dá)上具有很強(qiáng)的能力。在以往的研究中，很多工作主要針對(duì)單個(gè)三元組（triplet）建模，然而對(duì) KG 而言，三元組間的長鏈依賴信息在一些任務(wù)上也很重要。

在第四范式、香港科技大學(xué)這篇被 NeurIPS 2020 會(huì)議接收的論文中，研究者基于由三元組組成的關(guān)系路徑（relational path）提出 Interstellar 模型，通過搜索一種遞歸神經(jīng)網(wǎng)絡(luò)，來處理關(guān)系路徑中的短鏈、長鏈信息。

論文鏈接：https://arxiv.org/pdf/1911.07132.pdf

代碼鏈接：https://github.com/AutoML-4Paradigm/Interstellar

首先，該研究通過一組模擬實(shí)驗(yàn)分析了用單一模型對(duì)不同任務(wù)中關(guān)系路徑建模的難度，并由此提出通過搜索的方式對(duì)不同任務(wù)針對(duì)性地建模。為了提高搜索效率，該研究提出了一種混合搜索算法（hybrid-search algorithm），在鏈接預(yù)測（link prediction）和結(jié)點(diǎn)匹配（entity alignment）任務(wù)上，能高效地搜索到具有更好效果的模型。

背景介紹

知識(shí)圖譜嵌入（KG Embedding）旨在把圖譜中的結(jié)點(diǎn)（entities）和關(guān)系（relations）映射到一個(gè)低維空間，同時(shí)保留圖中的重要性質(zhì)。在目前學(xué)術(shù)領(lǐng)域，一些工作基于單個(gè)三元組(s,r,o)建模，如 TransE、RESCAL、DistMult、RotatE、ConvE、SimplE 等，它們在鏈接預(yù)測任務(wù)（即給定頭結(jié)點(diǎn) s 和關(guān)系 r ，預(yù)測尾結(jié)點(diǎn) o ）上表現(xiàn)良好，而在結(jié)點(diǎn)匹配任務(wù)（即給定兩個(gè) KG，預(yù)測哪些結(jié)點(diǎn)有相同含義）上性能一般。另一類基于關(guān)系路徑的工作，如 IPTransE、Chains、RSN 等則在結(jié)點(diǎn)匹配任務(wù)上表現(xiàn)更好。

研究人員觀察到，關(guān)系路徑包含多種重要信息，如單個(gè)三元組的短鏈信息、多個(gè)關(guān)系的復(fù)合、多個(gè)三元組之間的長鏈信息等等。基于此，該研究提出 Interstellar 模型，通過搜索的方式來根據(jù)不同任務(wù)，有針對(duì)性地對(duì)關(guān)系路徑進(jìn)行建模。

動(dòng)機(jī)

為了驗(yàn)證不同模型對(duì)不同任務(wù)的擬合能力不同，研究人員設(shè)計(jì)了一組模擬實(shí)驗(yàn)。Countries 數(shù)據(jù)集有 S1-S3 三個(gè)不同任務(wù)，預(yù)測難度逐一增大，需要模擬的預(yù)測路徑逐漸變長。為此研究者基于先驗(yàn)知識(shí)（prior knowledge）設(shè)計(jì)了 4 類模式 P1-P4，分別用于建模單個(gè)三元組、連續(xù)的兩個(gè)三元組、多重關(guān)系的復(fù)合，以及全遞歸連接。直觀上看，P4 的建模能力更強(qiáng)，但在有限的樣本上，樣本復(fù)雜度同樣重要，選擇更能擬合數(shù)據(jù)規(guī)律的模型能夠獲得更好的效果。

如下表所示，在 S1 這個(gè)簡單任務(wù)上，基于單個(gè)或兩個(gè)三元組的模型 P1 和 P2 表現(xiàn)更好，在 S2 上 P1-P3 均優(yōu)于 P4，而在 S3 上，遞歸模型 P4 由于能模擬更長路徑而勝出。由此我們可以得出，關(guān)系路徑上的建模應(yīng)該是模型相關(guān)的，如果我們能夠通過搜索的方式把專家的先驗(yàn)知識(shí)融入到建模能力中，那么針對(duì)不同任務(wù)，模型就可以自動(dòng)地找到更優(yōu)解。

問題定義與搜索空間

首先，研究者將 Interstellar 定義為一個(gè)遞歸式地處理關(guān)系路徑的模型，在每一個(gè)遞歸步中，模型關(guān)注到一個(gè)三元組，信息在三元組之內(nèi)、之間以不同方式穿梭。與傳統(tǒng) RNN 不同，這里的每一步有兩個(gè)輸入，同時(shí)由于需要考慮知識(shí)圖譜相關(guān)的領(lǐng)域知識(shí)，單純地使用 RNN 對(duì)其建模是不合適的。為了利用好知識(shí)圖譜領(lǐng)域的先驗(yàn)知識(shí)，同時(shí)使模型可以適用于不同任務(wù)，受神經(jīng)網(wǎng)絡(luò)搜索技術(shù)（Neural Architecture Search）的啟發(fā)，該研究把建模問題定義為搜索問題，來自適應(yīng)地對(duì)不同任務(wù)建模。

通過對(duì)知識(shí)圖譜嵌入領(lǐng)域相關(guān)模型的總結(jié)，該研究提出上圖的搜索空間，利用運(yùn)算單元 O_s 來處理結(jié)點(diǎn)嵌入 s_t ，用 O_r 來處理關(guān)系嵌入 r_t ，用 O_v 來輸出向量 v_t 從而預(yù)測下一個(gè)結(jié)點(diǎn) s_t+1 。具體而言，該研究在 macro-level 搜索不同單元間的連接方式（connections）和復(fù)合方式（combinators），在 micro-level 搜索激活函數(shù)（activation）與權(quán)重矩陣（weight matrix）。

搜索算法

該研究的目標(biāo)是更快地在搜索空間中找到能在驗(yàn)證集上達(dá)到更好性能的模型，這可以通過 bi-level 優(yōu)化方式來定義。為了求解這個(gè)優(yōu)化問題，學(xué)術(shù)界目前有兩類方法。一類是 stand-alone 算法，對(duì)每個(gè)模型單獨(dú)訓(xùn)練參數(shù) F 至收斂，這樣可以得到準(zhǔn)確的性能評(píng)估 Μ ，但訓(xùn)練代價(jià)較高；另一類是 one-shot 算法，建立一個(gè)包含所有網(wǎng)絡(luò)的超網(wǎng)絡(luò)（supernet），不同模型在超網(wǎng)絡(luò)中采樣，同時(shí)可以參數(shù)共享，這樣的評(píng)估方式更高效，但不總能保證可靠性。研究人員觀察到在 Interstellar 的建模上，one-shot 方式并不可靠。

為了解決這些問題，該研究提出 Hybrid 搜索算法，在 macro-level 采用 stand-alone 方式，給定 α_2 ，從 Α_1 中采樣不同的 α_1 ，訓(xùn)練模型參數(shù)至收斂，拿到對(duì) α_1 的可靠評(píng)估；在 micro-level 采用 one-shot 方式，給定 α_1 ，從 Α_2 中采樣不同的 α_2 ，同時(shí)讓不同 α_2 對(duì)應(yīng)的模型在超網(wǎng)絡(luò)中共享參數(shù)，加速訓(xùn)練評(píng)估的過程。二者結(jié)合，即保證了搜索準(zhǔn)確性，又保證了搜索效率。

實(shí)驗(yàn)結(jié)果

在搜索效果上，該方法在結(jié)點(diǎn)匹配和鏈接預(yù)測任務(wù)中，都能針對(duì)不同數(shù)據(jù)任務(wù)搜索到更好的模型，這得益于 Interstellar 上合理的搜索空間和高效的搜索算法。

在搜索效率上，Hybrid 算法能夠比隨機(jī)搜索（Random）、強(qiáng)化學(xué)習(xí)（Reinforce）、貝葉斯優(yōu)化（Bayes）算法更快地得到更好的模型，同時(shí)下圖中的兩條虛線（表示單獨(dú)的 one-shot 算法）表明其在這個(gè)問題上性能并不好。在搜索時(shí)間上，Hybrid 算法和調(diào)參（如 learning rate、batch size 等參數(shù)）時(shí)間是相當(dāng)?shù)模f明這個(gè)搜索方法代價(jià)并不高。在新的問題中，先搜索模型再進(jìn)行調(diào)參是一個(gè)不錯(cuò)的選擇。