本文從經(jīng)典算法開始介紹了知識圖譜中結(jié)點(diǎn)的嵌入表示，學(xué)習(xí)嵌入的過程及各類屬性，探索了PGB在知識圖譜表示中的表現(xiàn)和作用。
作者 | Sergey Zelvenskly
編譯 | Xiaowen
原文鏈接:
https://towardsdatascience.com/extracting-knowledge-from-knowledge-graphs-e5521e4861a0
機(jī)器學(xué)習(xí)使我們能夠訓(xùn)練模型，模型可以將數(shù)據(jù)轉(zhuǎn)換為標(biāo)簽，使類似的數(shù)據(jù)映射到相似或相同的標(biāo)簽。
例如，我們正在為電子郵件消息構(gòu)建垃圾郵件過濾器。我們有很多電子郵件，其中一些標(biāo)記為垃圾郵件，一些標(biāo)記為收件箱。我們可以構(gòu)建一個模型，學(xué)習(xí)識別垃圾郵件。要標(biāo)記為垃圾郵件的消息在某種程度上類似于已標(biāo)記為垃圾郵件的消息。
相似性的概念對機(jī)器學(xué)習(xí)至關(guān)重要。在現(xiàn)實(shí)世界中，相似的概念是非常具體的主題，它取決于我們的知識。
另一方面，大多數(shù)數(shù)學(xué)模型假設(shè)定義了相似性的概念。通常，我們將數(shù)據(jù)表示為多維向量并測量向量之間的距離。
特征工程是將我們關(guān)于現(xiàn)實(shí)世界對象的知識轉(zhuǎn)換為這些對象的數(shù)字表示的過程。我們認(rèn)為相似的對象表示為附近的向量。
例如，我們正在估算房價。我們的經(jīng)驗(yàn)告訴我們，房子的定義是由臥室的數(shù)目，浴室的數(shù)目，年齡，平方。地點(diǎn)等位于同一社區(qū)、大小和年齡相似的房屋，其價格應(yīng)大致相同。我們把對住房市場的了解轉(zhuǎn)化為描述房屋的數(shù)字，并利用它來估計房屋的價格。
遺憾的是，如上所述，手動特征工程在我們將知識轉(zhuǎn)換為描述性特征方面具有局限性。
有時，知識僅限于相似性原則，而不是使對象相似的確切特征。通常，我們對現(xiàn)實(shí)世界的了解比以簡單的表格格式表示的要復(fù)雜得多。它通常是相互關(guān)聯(lián)的概念和關(guān)系的圖表。
嵌入模型允許我們獲取原始數(shù)據(jù)并根據(jù)我們對原理的了解自動將其轉(zhuǎn)換為特征。
Word2Vec可能是最著名的嵌入模型，它為單詞構(gòu)建相似性向量。在這種情況下，我們對世界的認(rèn)識以敘事的形式呈現(xiàn)，其表示為文本，是文本的序列。
經(jīng)過幾十年的努力，人們試圖用手工定義的特征來描述單詞，但效果有限。這些解決方案通常無法擴(kuò)展到全部知識，或僅在有限的情況下發(fā)揮作用。
當(dāng)Tomas Mikolov和他的Google團(tuán)隊(duì)決定建立一個基于眾所周知的相似原則的模型時，一切都發(fā)生了變化。在類似的上下文中使用的詞通常是相似的，在這種情況下，上下文由位于附近的單詞定義。
我們所看到的是，考慮到這些原則，我們可以通過簡單地將每個單詞與其鄰居在預(yù)定義窗口（通常為5個單詞）內(nèi)連接起來，從文本中構(gòu)建圖形。
現(xiàn)在我們有一個基于我們的知識連接到圖形中的真實(shí)單詞對象（單詞）的圖形。
我們?nèi)匀粺o法構(gòu)建任何模型，因?yàn)閱卧~不以表格或向量表示。
如果我們只需要將單詞轉(zhuǎn)換為數(shù)字，那么就有一個簡單的解決方案。讓我們拿字典并將每個單詞分配給字典中的位置。
例如，如果我有三個詞：貓，毛毛蟲，小貓。
我的矢量表示如下：cat- [1]，caterpillar- [2]和kitten- [3]。
不幸的是，這沒什么用。通過分配這樣的數(shù)字，我們隱含地引入了單詞之間的距離。貓和毛蟲之間的距離是1，貓和小貓之間的距離是2.我們說貓更像毛毛蟲而不是小貓，這與我們的知識相矛盾。
有一種替代的表示，也稱為one-hot編碼執(zhí)行此操作：
貓 - [1,0,0]
毛毛蟲 - [0,1,0]
小貓 - [0,0,1]
該模式表明所有單詞彼此正交。我們承認(rèn)沒有先入為主的詞語相似性概念。我們將依賴我們的知識圖譜（如上所述），它結(jié)合了我們的詞匯相似原則來構(gòu)建嵌入。
在現(xiàn)實(shí)世界中，字典大小遠(yuǎn)遠(yuǎn)大于3。典型的維度從數(shù)萬到數(shù)百萬。不僅這些矢量并不真正代表我們的相似概念，而且這些矢量也非常龐大笨重，不能在實(shí)踐中真正使用。
我們的知識圖譜為我們提供了大量的圖形邊，每條邊可以解釋為輸入數(shù)據(jù)作為邊的起點(diǎn)，標(biāo)簽作為邊的末端。我們正在建立一個模型，它試圖用它周圍的單詞作為標(biāo)簽來預(yù)測這個詞。 我們要么從它的鄰居之和重建單詞向量，要么通過嘗試從單詞中預(yù)測鄰居來做相反的事情。
https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
從根本上說，上述模型使用基本的編碼器/解碼器模型來學(xué)習(xí)從高維空間（數(shù)百萬維度）到有限維度空間（通常為300）并返回高維空間的投影。訓(xùn)練的目標(biāo)是在壓縮過程中盡可能多地保留信息（最小化交叉熵）。
這種從稀疏正交數(shù)據(jù)集學(xué)習(xí)低維投影到更密集的低維空間的概念是許多其他嵌入訓(xùn)練模型的基礎(chǔ)。
該模型通常在google crawl，twitter dataset或Wikipedia等資源上進(jìn)行訓(xùn)練。我們正在消耗知識并從中構(gòu)建我們的詞匯嵌入。
Word2Vec的重要屬性是保持關(guān)系和揭示結(jié)構(gòu)等價的能力。
下圖顯示了國家和首都之間的聯(lián)系，
基本上它允許對這樣的單詞進(jìn)行代數(shù)運(yùn)算：
國王 - 男人+女人=女王。
Word嵌入大大改善了文本分類，命名實(shí)體識別，機(jī)器翻譯等任務(wù)。
以下是更多信息：http：//www.wildml.com/2015/11/understanding-convolutional-neural-networks-for-nlp/
Node2Vec是由A. Grover和J. Leskovec撰寫的模型，它通過擴(kuò)展Word2Vec的思想來分析同質(zhì)加權(quán)圖。本文背后的想法是，我們可以通過探索其周圍環(huán)境來表征圖形節(jié)點(diǎn)。我們對世界的理解基于兩個原則 - 同質(zhì)性和結(jié)構(gòu)等價性。
類似的節(jié)點(diǎn)位于附近。
例子：
社交網(wǎng)絡(luò) - 我們與像我們這樣的人聯(lián)系更緊密。
商業(yè)地點(diǎn) - 金融公司，醫(yī)生辦公室或營銷公司似乎通常位于同一條街道上
組織結(jié)構(gòu) - 同一團(tuán)隊(duì)中的人具有相似的特征
不同的社區(qū)共享相同的結(jié)構(gòu)：
組織結(jié)構(gòu) - 雖然團(tuán)隊(duì)的連接能力較弱，但團(tuán)隊(duì)的結(jié)構(gòu)（經(jīng)理，高級成員，新成員，初級成員）會在團(tuán)隊(duì)之間重復(fù)出現(xiàn)。
https://arxiv.org/pdf/1607.00653.pdf
為了將這兩個原則融入我們的嵌入表示中，Node2Vec論文的作者提出了一種隨機(jī)游走方法，結(jié)合廣度優(yōu)先采樣來捕獲同質(zhì)性和深度優(yōu)先采樣以捕獲結(jié)構(gòu)等價性。
我們可以看到，節(jié)點(diǎn)（u）充當(dāng)組內(nèi)的中心（s1，s2，s3，s4），類似于s6是（s7，s5，s8，s9）的中心。我們通過BFS發(fā)現(xiàn)（s1，s2，s3，s4）社區(qū)，并通過DFS發(fā)現(xiàn)（u）< - >（s6）相似性。
我們通過探索周圍環(huán)境來了解每個節(jié)點(diǎn)。這種探索將圖形轉(zhuǎn)換為由隨機(jī)游走產(chǎn)生的大量序列（句子），其結(jié)合了BFS和DFS探索。BFS和DFS混合由圖形邊的權(quán)重以及模型的超參數(shù)控制。
一旦我們擁有完整的序列（句子），我們就可以像應(yīng)用于文本一樣應(yīng)用Word2Vec方法。它產(chǎn)生的圖形節(jié)點(diǎn)嵌入，是基于我們定義的原則以及圖的知識。
Node2Vec表示改進(jìn)了用于節(jié)點(diǎn)的聚類和分類的模型。嵌入的學(xué)習(xí)相似性將有助于欺詐檢測等任務(wù)。
由node2vec生成的LESMISérables共形網(wǎng)絡(luò)的互補(bǔ)可視化，標(biāo)簽顏色反映了同質(zhì)性(頂部)和結(jié)構(gòu)等價性(底部)。https://arxiv.org/pdf/1607.00653.pdfhttps://arxiv.org/pdf/1607.00653.pdf
Node2vec顯示了連接預(yù)測方面的顯著改進(jìn)。它能夠提高重建圖形的能力，其中一些邊被刪除。本文還對連接預(yù)測評價過程進(jìn)行了深入的探討。
下面我們將討論P(yáng)YTORCH-BIGGRAPH：一個大型圖譜嵌入系統(tǒng)（PBG）。
知識圖譜是特殊類型的圖，它包含已知實(shí)體以及不同類型的邊，它代表結(jié)構(gòu)知識。
在知識圖譜中，節(jié)點(diǎn)通過不同類型的關(guān)系連接。
訓(xùn)練的目標(biāo)是生成代表我們知識的嵌入表示。一旦我們有了節(jié)點(diǎn)的嵌入，就應(yīng)該很容易通過特定的關(guān)系類型確定相應(yīng)的節(jié)點(diǎn)是否在我們的知識圖譜中有連接（或應(yīng)該連接）。
不同的模型提出了比較嵌入矢量的不同方法。最簡單的模型使用余弦或矢量乘積距離比較嵌入矢量。更復(fù)雜的模型在比較之前對矢量的元素應(yīng)用不同的加權(quán)方案。加權(quán)方案表示為矩陣，具體到特定的關(guān)系類型。作為訓(xùn)練的一部分，我們可以學(xué)習(xí)加權(quán)矩陣。
https://www.sysml.cc/doc/2019/71.pdf
我們需要找到一種方法來測量邊之間的相似性得分，并使用此分?jǐn)?shù)來估計這些節(jié)點(diǎn)連接的可能性。
知識圖譜可以表示為鄰接張量。為了構(gòu)建它，我們將為每種類型的關(guān)系提供一個方陣。每個矩陣具有與圖中的節(jié)點(diǎn)一樣多的列或行。矩陣的值為1，這些節(jié)點(diǎn)中有1個是通過這種關(guān)系連接的，如果沒有，則為0。很明顯，這個矩陣將非常大，非常稀疏。
要學(xué)習(xí)我們的嵌入表示，我們需要將每個節(jié)點(diǎn)轉(zhuǎn)換為固定大小的向量。我們來討論討論“好”嵌入的屬性。
好的嵌入代表了我們以圖譜邊的形式表達(dá)的知識。位于“附近”的嵌入向量應(yīng)代表更可能連接的節(jié)點(diǎn)。基于這種觀察，我們將以這樣的方式訓(xùn)練我們的模型：在鄰接張量中標(biāo)記為1的連接節(jié)點(diǎn)的相似性得分將更高并且在鄰接張量中標(biāo)記為0的連接節(jié)點(diǎn)的相似性得分將更低。
我們正在訓(xùn)練嵌入表示，以便從節(jié)點(diǎn)嵌入中重建知識圖譜的邊，同時最小化信息損失。
我們的訓(xùn)練方法有點(diǎn)問題。我們正在嘗試使用圖數(shù)據(jù)來區(qū)分1（節(jié)點(diǎn)已連接）和0（節(jié)點(diǎn)未連接）。然而，我們實(shí)際擁有的唯一數(shù)據(jù)是連接的節(jié)點(diǎn)。這就像通過只看貓來學(xué)習(xí)區(qū)分貓和狗。
負(fù)抽樣是一種擴(kuò)展我們的數(shù)據(jù)集并通過非常簡單的觀察提供更好的訓(xùn)練數(shù)據(jù)的技術(shù)。任何隨機(jī)選擇的節(jié)點(diǎn)（未作為圖的一部分連接）將代表標(biāo)簽為0的樣本數(shù)據(jù)。出于訓(xùn)練目的，PBG論文建議讀取圖的每個邊，然后提出負(fù)樣本，其中一個用隨機(jī)選擇的節(jié)點(diǎn)來替換。
對于每個邊，我們可以指定正相似度得分和負(fù)相似度得分。基于節(jié)點(diǎn)嵌入和邊關(guān)系類型權(quán)重計算正相似度。負(fù)相似度的計算方法相同，但邊的一個節(jié)點(diǎn)被破壞，并被隨機(jī)節(jié)點(diǎn)替換。
排序損失函數(shù)將在訓(xùn)練期間進(jìn)行優(yōu)化。它是為了在圖中的所有節(jié)點(diǎn)和所有關(guān)系類型的正、負(fù)相似度之間建立一個可配置的邊界。排序損失是節(jié)點(diǎn)嵌入和特定關(guān)系權(quán)重的函數(shù)，通過尋找最小排序損失來學(xué)習(xí)。
現(xiàn)在我們擁有訓(xùn)練嵌入模型所需的一切：
數(shù)據(jù) - 負(fù)邊和正邊
標(biāo)簽 - （1或0）
函數(shù)優(yōu)化（可以是排序損失，更傳統(tǒng)的邏輯回歸損失或word2vec中使用的交叉熵softmax損失）
我們的參數(shù)，即嵌入以及相似性得分函數(shù)的權(quán)重矩陣。
現(xiàn)在，使用微積分來找到參數(shù) - 嵌入，優(yōu)化我們的損失函數(shù)。
隨機(jī)梯度下降的本質(zhì)是逐漸調(diào)整損失函數(shù)的參數(shù)，使損失函數(shù)逐漸減小。為此，我們以小批量讀取數(shù)據(jù)，使用每個批次來計算損失函數(shù)參數(shù)的更新以最小化它。
有多種方法可以進(jìn)行隨機(jī)梯度下降。PB論文使用ADAGrad，它是隨機(jī)梯度下降的一種類型，可以找到參數(shù)從而最大限度地減少損失函數(shù)。我強(qiáng)烈推薦大家閱讀這個博客了解所有梯度下降的類型：
http：//ruder.io/optimizing-gradient-descent/index.html#adagrad
像tensorflow和pytorch這樣的軟件包提供了不同類型的實(shí)現(xiàn)。
梯度下降的關(guān)鍵因素是多次更新模型參數(shù)的過程，直到我們最小化損失函數(shù)。在訓(xùn)練結(jié)束時，我們希望擁有嵌入和評分功能，以滿足我們的知識整合目標(biāo)。
隨機(jī)梯度下降分布是一個挑戰(zhàn)。如果我們通過調(diào)整參數(shù)來同時訓(xùn)練以最小化損失函數(shù)，則需要某種鎖定（Locking）機(jī)制。在傳統(tǒng)的多線程開發(fā)中，我們通過悲觀或樂觀方式來鎖定更新期間的數(shù)據(jù)。鎖定會減慢進(jìn)度，但會確保結(jié)果的正確性。
幸運(yùn)的是，hogwild論文證明我們不需要鎖定機(jī)制。我們可以簡單地批量讀取數(shù)據(jù)，計算參數(shù)調(diào)整，只需將它們保存在共享參數(shù)空間中，而不考慮正確性。HogWild算法就是這樣做的?？梢苑植际接?xùn)練，每個HogWild線程都可以更新我們的參數(shù)，而無需考慮其他線程。
我推薦閱讀這個博客來獲取有關(guān)HogWild的更多信息：
https：//medium.com/@krishna_srd/parallel-machine-learning-with-hogwild-f945ad7e48a4
當(dāng)圖跨越數(shù)十億個節(jié)點(diǎn)和數(shù)萬億個邊時，很難將所有參數(shù)都放在一臺機(jī)器的內(nèi)存中。如果我們在開始另一批次之前等待每批次結(jié)束完成計算，也需要花費(fèi)很多時間。我們的圖譜非常大，能夠并行訓(xùn)練并同時學(xué)習(xí)參數(shù)是相當(dāng)有用的。Facebook團(tuán)隊(duì)發(fā)布了PBG論文，解決了這個問題。
節(jié)點(diǎn)按實(shí)體類型拆分，然后組織成分區(qū)：
https://torchbiggraph.readthedocs.io/en/latest/data_model.html
節(jié)點(diǎn)被劃分為P個部分，邊被劃分為PxP部分。具有小基數(shù)的實(shí)體類型不必進(jìn)行分區(qū)。
訓(xùn)練與以下約束并行完成：
對于除第一個之外的每個邊部分（p1; p2），重要的是在先前的迭代中訓(xùn)練邊（p1; *）或（*; p2）。 只要多個邊部分在不相交的分區(qū)集上操作，就可以并行訓(xùn)練多個邊部分。
https://www.sysml.cc/doc/2019/71.pdf
在多臺機(jī)器上并行進(jìn)行訓(xùn)練，每臺機(jī)器都有多個線程。每個線程根據(jù)分配的存儲和批量數(shù)據(jù)計算參數(shù)更新。Locker服務(wù)器根據(jù)建立的約束分配訓(xùn)練。請注意，Locker服務(wù)器僅控制跨hogwild線程的數(shù)據(jù)批處理，而不控制參數(shù)更新。
知識嵌入可以通過兩種方式使用：
連接預(yù)測 Link Prediction
連接預(yù)測通過查找可能已連接或即將連接的節(jié)點(diǎn)來幫助填補(bǔ)我們的知識空白。
示例：該圖表代表客戶和客戶購買的產(chǎn)品。邊是定購單。嵌入可以用來形成下一個購買建議。
學(xué)習(xí)節(jié)點(diǎn)的屬性
嵌入可以用作特征向量，作為各種分類模型的輸入。學(xué)習(xí)的類可以填補(bǔ)我們關(guān)于對象屬性的知識空白。
該過程在論文“Learning Structured Embeddings of Knowledge Bases ”中有介紹，后來被用作衡量嵌入模型質(zhì)量的方法，包括Facebook PBG在內(nèi)的許多其他論文中。
該算法采用測試邊的子集并執(zhí)行以下操作：
通過用負(fù)采樣邊替換邊的開頭或結(jié)尾來破壞邊
在部分損壞的數(shù)據(jù)集上訓(xùn)練模型
計算測試數(shù)據(jù)集邊的聚合MRR和Hits10指標(biāo)
MRR或平均倒數(shù)排名是衡量搜索質(zhì)量的指標(biāo)。我們采用一個未損壞的節(jié)點(diǎn)，找到距離定義為相似度得分的“最近鄰居”。我們通過相似性得分對最近鄰居進(jìn)行排名，并期望連接的節(jié)點(diǎn)出現(xiàn)在排名的頂部。如果節(jié)點(diǎn)沒有在頂部，MRR會降低準(zhǔn)確度分?jǐn)?shù)。
替代指標(biāo)是Hits10，我們期望損壞的節(jié)點(diǎn)出現(xiàn)在前10個最近鄰居中。
PBG論文表示，在我們將資源分配到訓(xùn)練中時，在許多數(shù)據(jù)集上，MRR指標(biāo)逐漸增加。并行性不會影響排名的質(zhì)量，但能節(jié)省大量時間。
可以通過簡單地探索和可視化圖來執(zhí)行進(jìn)一步的評估。
上圖是從Freebase知識圖譜構(gòu)建的嵌入的二維投影。我們可以看到，類似的節(jié)點(diǎn)被組合在一起。國家，數(shù)字，科學(xué)期刊專業(yè)似乎甚至在精心準(zhǔn)備的二維投影上也有集群。
如上所述的知識圖譜僅表示我們知識的“靜態(tài)快照”。它并不反映知識建立的過程。在現(xiàn)實(shí)世界中，我們通過觀察時間模式來學(xué)習(xí)。雖然可以了解節(jié)點(diǎn)A和節(jié)點(diǎn)B之間的相似性，但很難看到節(jié)點(diǎn)A和節(jié)點(diǎn)C三年之前的相似性。
例如，如果我們在森林中觀察一天，我們將看到兩棵大型紅杉樹之間的相似性。然而，如果沒有對森林的長期觀察，很難理解哪棵樹苗會長成一棵大的紅杉樹。
理想情況下，我們需要探索在不同時間點(diǎn)構(gòu)建的一系列知識圖譜，然后構(gòu)建嵌入表示，這將增長的相似性（generational similarities）。
