利用 Pytorch-BigGraph 從知識圖中提取知識詳解
雷鋒網 AI 科技評論按,機器學習使我們能夠訓練一個模型,該模型可以將數據行轉換為標籤,從而使相似的數據行映射到相似或相同的標籤。
以我們為電子郵件構建垃圾郵件過濾器為例。我們有很多電子郵件,其中一些被標記為垃圾郵件,一些被歸類到收件箱。我們可以建立一個模型去學習識別垃圾郵件。要標記為垃圾郵件的郵件在某種程度上與已標記為垃圾郵件的郵件相似。
相似性的概念對於機器學習至關重要。在現實世界中,相似性的概念是非常具體的主題,它取決於我們的知識。
另一方面,大多數數學模型都假定相似性的概念是被定義的。通常,我們將數據表示為多維向量,並測量向量之間的距離。
打開今日頭條,查看更多圖片
圖片來源:https://www.quora.com/Why-do-we-use-cosine-similarity-on-Word2Vec-instead-of-Euclidean-distance
特徵工程是將我們對現實物體的認知轉化為這些數值表示的過程。我們將認為相似的物體表示為鄰近的向量。
例如,我們要對房價進行評估。我們的經驗告訴我們,房子是由卧室的數量,浴室的數量,房齡,面積,位置等來定義的。購買位於同一個街區,面積和年限相似的房子應該花費差不多的金額。我們根據對房地產市場的了解,將房子的描述轉化為數字,並用這些數字來估計房子的價格。
不幸的是,如上所述,手動特性工程在將我們的知識轉換為可以描述的特性的能力方面存在局限性。
有時知識只能局限於相似性原則,而不局限於使事物相似的確切特徵。通常,我們對現實世界的了解遠比簡單的表格內容更為複雜。它通常是一個相互關聯的概念和關係圖。
嵌入模型允許我們獲取原始數據,並根據我們對原理的了解將其自動轉換為特性。
word2vec
word2vec 可能是最著名的 embedding 模型,它為單詞構建相似向量。在這種情況下,我們對世界的了解是以故事的形式呈現的,以文本的形式表示,而文本是一系列的單詞。
幾十年來,人們一直在努力用人工定義的特徵來描述單詞,但成功率有限。這些解決方案通常無法擴展到完整的知識體系或在條件有限的情況下工作。
當 Tomas Mikolov 和他在谷歌的團隊決定建立一個模型時,一切都發生了變化,這個模型基於眾所周知的相似性原則。在類似的上下文中,使用的單詞通常是相似的。在本例中,上下文由附近的單詞定義。
單詞序列的圖表示法
我們看到的是,考慮到這些原則,我們可以通過在一個預先定義的窗口(通常是 5 個詞)內簡單地將每個詞與其相鄰詞連接起來,從文本中構建一個圖。
現在,我們有了一個圖,它是基於我們的知識連接起來的真實單詞對象(單詞)的圖。
最簡單/複雜的單詞表示法
我們仍然無法建立任何模型,因為單詞沒有以固定的形式或向量表示。
如果我們需要做的只是把單詞轉換成數字,那麼有一個簡單的解決方案。讓我們拿著我們的字典,把每個單詞在字典中的位置分配給它們。
例如,如果我有三個詞:cat, caterpillar, kitten。
我的矢量表示方法如下:cat-[1], caterpillar-[2] 和 kitten-[3]。
不幸的是,這行不通。通過指定這樣的數字,我們隱式地引入了單詞之間的距離。cat 和 caterpillar 之間的距離是 1,cat 和 kitten 之間的距離是 2。我們說貓更像是 caterpillar,而不是 kitten,這與我們的認知相矛盾。
另一種表示被稱為「獨熱編碼(one-hot encoding)」的方法也可以做到這一點:
cat — [1,0,0]
caterpillar — [0,1,0]
kitten — [0,0,1]
這個模式表示所有單詞都是正交的。我們承認,沒有預想到單詞相似性的概念。我們將依靠我們的知識圖譜(如上所述),它結合了我們的單詞相似性原則,來構建 embedding。
在現實世界中,字典的大小遠遠大於 3。典型的維度是從數萬到數百萬。這些向量不但不能真正代表我們相似性的概念,而且它們也非常龐大,不能真正用於實踐。
構建單詞 embedding
我們的知識圖譜為我們提供了大量的圖邊,對每個邊來說,輸入數據為其起點,標籤為其終點。我們正在建立一個模型,試圖用某個單詞周圍的單詞作為標籤來預測它。這通常有兩種方式。我們可以根據鄰接詞重建詞向量,也可以做相反的事情,即嘗試通過這個詞預測鄰接詞。
圖片來源:https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
從根本上講,團隊使用基本的編解碼器模型,學習從高維空間(數百萬維)到有限維空間(通常為 300 維)的映射以及返回高維空間的映射。訓練的目標是在壓縮過程中儘可能多地保存信息(最小化交叉熵)。
圖片來源:http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/
從稀疏正交數據集的低維投影學習到更密集的低維空間的概念是許多其他 embedding 訓練模型的基礎。
該模型通常是針對谷歌爬蟲、Twitter 數據集或維基百科等資源進行訓練的。我們正在學習世界的知識,並以此為基礎構建我們的詞 embedding。
word2vec embedding 的屬性
word2vec 的重要特性是保持關係和公開結構的能力。
下面的圖表顯示了國家和首都之間的聯繫。
或者其它不同的概念
圖片來源:https://www.tensorflow.org/tutorials/representation/word2vec
本質上,它允許在單詞上做這樣的代數運算:
king — man+woman=queen
使用單詞 embedding
單詞 embedding 大大改進了諸如文本分類、命名實體識別、機器翻譯等任務。
這裡可以看到更多信息:http://www.wildml.com/2015/11/understanding-convolutional-neural-networks-for-nlp/
Node2Vec
A.Grover 和 J.Leskovec 提出的 Node2Vec 是一個模型,它通過擴展 Word2Vec 的思想來分析同一類別的加權圖。本文背後的思想是,我們可以通過探索圖節點周圍的元素來描述它。我們對世界的理解基於兩個原則——同質性和結構等效。
同質性
相似的節點所在的位置相近。
示例:
社交網路:我們與和我們相似的人有更多的聯繫。
商業地點:金融公司、醫生辦公室或營銷公司通常位於同一條街上。
組織結構:同一團隊中的人具有相似的特徵。
結構等效
不同的社區共享相同的結構:
從組織結構來看,雖然團隊之間的連通性很弱,但團隊的結構(經理、高級成員、新成員、初級成員)在團隊之間是相似的。
圖片來源:https://arxiv.org/pdf/1607.00653.pdf
為了將這兩個原理結合到我們的 embedding 中,Node2Vec 論文的作者提出了一種將廣度優先抽樣與深度優先抽樣相結合的 random walk 方法來捕獲結構等效性。
如我們所見,節點(U)在一個組(s1、s2、s3、s4)中充當中心,類似於作為(s7、s5、s8、s9)中心的 s6。我們發現(s1,s2,s3,s4)和(u)(s6)用深度優先演算法和廣度優先演算法都是類似的。
我們通過探索每個節點的周圍的元素來了解它。這種探索將圖轉換成大量 random walk 產生的序列(句子),它將深度優先(DFS)和廣度優先(BFS)的探索結合起來。BFS 和 DFS 的結合由圖邊緣的權重以及模型的超參數控制。
一旦我們有了完整的序列(句子),我們就可以像應用於文本一樣應用 word2vec 方法。它基於我們定義的原則以及從圖中獲得的知識,它產生了圖節點 embedding。
Node2Vec 屬性
Node2Vec 表示改進了節點的聚類和分類模型。所學的 embedding 相似性將有助於執行欺詐檢測等任務。
Node2Vec 生成的 Les-Mis_rables 共現網路的互補可視化,其標籤顏色反映同質性和結構等效(底部)。
圖片來源:https://arxiv.org/pdf/1607.00653.pdf
Node2Vec 在鏈路預測方面有顯著改進。它能夠提高重建圖的能力,去除部分邊緣。本篇文章將進一步討論鏈路預測評估過程。
知識圖
下面我們將討論「PYTORCH-BIGGRAPH: A LARGE-SCALE GRAPH EMBEDDING SYSTEM」這篇論文(下面將論文簡寫為 PBG),以及和它有關聯的系列論文。
知識圖是包含已知實體和不同類型邊的特殊類型的圖。它代表結構化的知識。
在知識圖中,節點通過不同類型的關係進行連接。
圖片來源:https://arxiv.org/pdf/1503.00759.pdf
訓練的目標是產生代表我們知識的 embedding。一旦我們有了節點的 embedding,就可以很容易地通過特定類型的關係確定相應的節點是否在我們的知識圖中連接(或應該連接)。
不同的模型提出了不同的 embedding 比較方法。最簡單的模型使用餘弦或向量積距離比較 embedding 向量。更複雜的模型在比較之前對向量的元素應用不同的權重方案。加權方案表示為矩陣,並且對於不同的關係類型來說,這個矩陣是特定的。作為訓練的一部分,我們可以學習加權矩陣。
圖片來源:https://www.sysml.cc/doc/2019/71.pdf
我們需要找到一種方法來測量邊緣之間的相似性分數,並使用該分數來評估這些節點連接的可能性。
知識圖的表示
知識圖可以表示為鄰接 tensor。要建立它,我們需要為每一種關係建立一個平方矩陣。每個矩陣的列或行與圖中的節點一樣多。如果這些節點通過這種關係連接,那麼矩陣的值將為 1,如果不是,則為 0。很明顯,這個矩陣非常大,非常稀疏。
為了學習 embedding,我們需要將每個節點轉換為固定大小的向量。讓我們討論一下「好」的 embedding 的特性。
好的 embedding 是以圖的邊緣的形式來表示我們的知識的。位於「附近」的 embedding 向量應該表示更可能連接的節點。基於這一觀察,我們將訓練我們的模型,使相鄰 tensor 中標記為 1 的連接節點的相似性得分更高,相鄰 tensor 中標記為 0 的連接節點的相似性得分更低。
圖片來源:https://arxiv.org/pdf/1503.00759.pdf
我們正在訓練我們的 embedding 以最小的信息損失從節點 embedding 重構知識圖的邊緣。
負採樣
我們的訓練方法有點問題。我們試圖學習使用圖數據區分 1(節點已連接)和 0(節點未連接)。然而,實際上我們擁有的唯一數據是連接節點的數據。這就像只看貓就要學會區分貓和狗一樣。
負採樣是一種擴展數據集並通過簡單的觀察提供更好的訓練數據的技術。任何隨機選擇的節點,如果沒有作為我們圖的一部分連接,將會被表示一個標籤為 0 的示例數據。為了訓練的目的,PBG 提出讀取圖的每一個邊緣,然後提出一個負樣本,其中一個節點被隨機選擇的節點替換。
對於每個邊,我們可以指定一個正相似性得分和一個負相似性得分。基於節點 embedding 和邊緣關係類型權重可以計算正相似性得分。負相似度得分的計算方法相同,但邊緣的一個節點損壞,被隨機節點替換。
排名損失函數將會在訓練時被優化。它的產生是為了在圖中所有節點和所有關係類型的正相似度得分和負相似度得分之間建立一個可配置的邊界。排名損失是節點 embedding 和關係特定權重的函數,是通過尋找最小排名損失來學習的。
訓練
現在我們有了訓練 embedding 模型所需的一切:
數據:正負邊
標籤:1 或 0
優化函數:可以是排名損失、更傳統的邏輯回歸損失或 word2vec 中使用的交叉熵 Softmax 損失
我們的參數是 embedding 以及相似度得分函數的權重矩陣
現在使用微積分來尋找 embedding 參數,優化我們的損失函數。
隨機梯度下降演算法
隨機梯度下降的本質是逐步調整損失函數的參數,使損失函數逐漸減小。為了做到這一點,我們以小批量讀取數據,使用每批數據計算其對損失函數參數的更新,以將其最小化。
隨機梯度下降有多種方法。在 PBG 這篇論文裡面,採用了隨機梯度下降的一種方式——ADAGRAD 來尋找參數,使損失函數最小化。我強烈推薦你閱讀這個博客來理解梯度下降的所有風格:http://ruder.io/optimizing gradient depression/index.html adagrad
像 TensorFlow 和 PyTorch 這樣的軟體包為不同的風格提供現成的實現。
梯度下降的關鍵是多次更新模型參數,直到損失函數最小化。在訓練結束時,我們希望有 embedding 和評分功能,以滿足合併我們的知識的目標。
HogWild-分散式隨機梯度下降
隨機梯度下降的分布是一個挑戰。如果我們同時通過調整參數來進行訓練,以最小化損失函數,就需要某種鎖定機制。在傳統的多線程開發中,我們通過悲觀鎖或樂觀鎖在更新期間鎖定數據。鎖定會減慢進度,但可以確保結果的正確性。
幸運的是,「HogWild」這篇論文證明我們不需要鎖定機制。我們可以簡單地批量讀取數據,計算參數調整,並將其保存在共享的參數空間中,而不考慮正確性。HogWild 演算法就是這麼做的。培訓可以分發,每個 HogWild 線程可以更新我們的參數,而不需要考慮其他線程。
我推薦你閱讀這個博客來獲取更多關於 HogWild 的信息:https://medium.com/@krishna_d/parallel-machine-learning-with-hogwild-f945ad7e48a4
分散式訓練
當圖形跨越數十億個節點和數萬億個邊時,很難將所有參數都放入一台機器的內存中。如果我們在開始另一個 batch 之前等待每個 batch 結束來完成計算,那也需要很多時間。我們的圖太大了,所以,能夠同時並行訓練和學習參數是很有好處的。這個問題由發布 PBG 論文的 Facebook 團隊解決。
節點按實體類型拆分,然後組織到分區:
圖片來源:https://torchbiggraph.readthedocs.io/en/latest/data_model.html
圖片來源:https://torchbiggraph.readthedocs.io/en/latest/data_model.html
圖片來源:https://www.sysml.cc/doc/2019/71.pdf
1.節點被劃分為 P 個 bucket,邊緣被劃分為 PxP 個 bucket。基數較小的實體類型不必進行分區。
2.訓練與以下限制條件同時進行:
對於除第一個外的每個邊 bucket(p1;p2),在前一個迭代中對邊 bucket(p1;*)或(*;p2)進行訓練是很重要的。
多個邊 bucket 可以平行訓練,只要它們在不相交的分區集上操作。
圖片來源:https://www.sysml.cc/doc/2019/71.pdf
訓練在多台機器上並行進行,每台機器有多個線程。每個線程根據分配的存儲 bucket 和數據 batch 計算參數更新。鎖伺服器根據已建立的約束分配訓練 bucket。注意,鎖伺服器只控制數據 batch 在 HogWild 線程之間的分布,而不控制參數更新。
PBG embedding 的特點
知識 embedding 有兩種方式:
1.鏈接預測
鏈接預測通過找到可能連接或即將連接的節點,幫助填補我們知識上的空白
示例:該圖表示客戶和客戶購買的產品,邊緣是採購訂單。embedding 可用於生成下一個採購建議。
2.學習節點的屬性
embedding 可以用作提供給各種分類模型的輸入的特徵向量。所學的類可以填補我們對對象屬性的知識空白。
使用 MRR/Hits10 評估鏈路預測
論文「Learning Structured Embeddings of Knowledge Bases」中描述了這一過程,隨後將其作為衡量 embedding 模型在許多其他論文(包括 Facebook PBG)中質量的方法。
該演算法獲取測試邊緣的子集,並執行以下操作:
通過用負採樣邊替換邊的首尾來破壞邊
在部分損壞的數據集上訓練模型
從測試數據集中計算邊緣的聚合 MRR(Mean reciprocal rank)和 HITS10 度量
平均倒數秩(Mean reciprocal rank)
MRR(平均倒數秩)是一種度量搜索質量的方法。我們取一個未損壞的節點,找到距離定義為相似性分數的「最近鄰」。我們根據相似性得分對最近的節點進行排名,並期望連接的節點會出現在排名的頂部。如果節點沒有傾斜在頂部,MRR 會降低精度分數。
另一種方法是 Hits10,我們期望損壞的節點出現在前 10 個最近的節點中。
圖片來源:https://www.sysml.cc/doc/2019/71.pdf
PBG 論文表明,在許多數據集上,隨著我們將資源分配到訓練中,MRR 度量逐漸增加。並行性不會影響排名的質量,但可以節省大量的時間。
進一步的評估可以通過簡單地探索和可視化圖形來執行。
圖片來源:https://ai.facebook.com/blog/open-sourcing-pytorch-biggraph-for-faster-embeddings-of-extremely-large-graphs/
上圖是由 Freebase 知識圖譜構建的 embedding 的二維投影。如我們所見,相似的節點被分在一組。國家、數字、專業科學期刊甚至在精心準備的二維投影圖上似乎也有集群。
知識圖模型的局限性
如上所述的知識圖表示的是我們知識的靜態快照。它並沒有反映知識是如何建立起來的。在現實世界中,我們通過觀察時間模式來學習。雖然可以了解節點 A 和節點 B 之間的相似性,但是很難看到節點 A 和三年前的節點 C 之間的相似性。
例如,如果我們觀察森林一整天,我們會發現兩棵大紅杉之間的相似性。然而,如果沒有對森林的長期觀察,我們很難理解哪個樹苗會長成一棵巨大的紅杉樹。
理想情況下,我們需要探索在不同時間點構建的一系列知識圖,然後構建 embedding,這些 embedding 將包含這一系列知識圖的相似點。
via:https://www.kdnuggets.com/2019/05/extracting-knowledge-graphs-facebook-pytorch-biggraph.html
雷鋒網雷鋒網
※解讀 | 為什麼蘋果 Mac Pro 只能在中國組裝?
※小米入局AI教育硬體:小愛同學終於當了「老師」
TAG:雷鋒網 |