http://blog.csdn.net/u011274209/article/details/50991385

一、引言

? ? ? ?網絡上已經存在了大量知識庫（KBs），比如OpenCyc，WordNet，Freebase，Dbpedia等等。這些知識庫是為了各種各樣的目的建立的，因此很難用到其他系統上面。為了發揮知識庫的圖（graph）性，也為了得到統計學習（包括機器學習和深度學習）的優勢，我們需要將知識庫嵌入（embedding）到一個低維空間里（比如10、20、50維）。我們都知道，獲得了向量后，就可以運用各種數學工具進行分析。深度學習的輸入也是向量。（考慮一下，word2vec，我們訓練出一個向量后，可以做好多事情，深度學習的輸入也往往是一個矩陣。另可見：詞嵌入的類比特性有實用意義嗎？）。

二、基礎背景

? ? ? ?一條知識圖譜可以表示為一個三元組(sub,rel,obj)。舉個例子：小明的爸爸是大明，表示成三元組是（小明，爸爸，大明）。前者是主體，中間是關系，后者是客體。主體和客體統稱為實體（entity）。關系有一個屬性，不可逆，也就是說主體和客體不能顛倒過來。

? ? ? ?知識圖譜的集合，鏈接起來成為一個圖（graph），每個節點是一個一個實體，每條邊是一個關系，或者說是一個事實（fact）。也就是有向圖，主體指向客體。

? ? ? ?具體的用處和知識圖譜提取方式可見劉知遠大神的文章http://www.36dsj.com/archives/31317（ps，最好是買本他的書）

? ? ? Freebase的例子：

(Barack Obama, place of birth, Hawai) ? (Albert Einstein, follows diet, Veganism) ? ? (San Francisco, contains, Telegraph Hill)

上面三條都是知識圖譜的例子。

? ? ?

三、TransE的提出

? ? ? ? TranE是一篇Bordes等人2013年發表在NIPS上的文章提出的算法。它的提出，是為了解決多關系數據（multi-relational data）的處理問題。我們現在有很多很多的知識庫數據knowledge bases (KBs)，比如Freebase、 Google Knowledge Graph 、 GeneOntology等等。

? ? ? ? TransE的直觀含義，就是TransE基于實體和關系的分布式向量表示，將每個三元組實例（head，relation，tail）中的關系relation看做從實體head到實體tail的翻譯（其實我一直很納悶為什么叫做translating，其實就是向量相加），通過不斷調整h、r和t（head、relation和tail的向量），使（h + r） 盡可能與 t 相等，即 h + r = t。

? ? ? ? 以前有很多種訓練三元組的方法，但是參數過多，以至于模型過于復雜難以理解（作者表達的意思就是，我們的工作效果和你們一樣，但我們的簡單易擴展）。（ps：作者以前也做過類似的工作，叫做Structured Embeddings，簡稱SE，只是將實體轉為向量，關系是一個矩陣，利用矩陣的不可逆性反映關系的不可逆性。距離表達公式是1-norm）。

? ? ? ? ?如下圖，作者的目的是將向量轉為這種形式（此圖是2維）

為此，作者定義了距離公式為

四、TransE的訓練

注釋：

1、

直觀上，我們要前面的項（原三元組）變小（positive），后面的項（打碎的三元組）變大（negative）。就跟喂小狗一樣，它做對了，就給骨頭吃；做錯了，就打兩下。前面的項是對的（來自于訓練集），后面的項是錯的（我們隨機生成的）。不同時打碎主體和客體，隨機挑選一個打碎，另一個保持不變，這樣才能夠有對照性。

2、圖上的加號是大于0取原值，小于0則為0。我們叫做合頁損失函數(hinge loss function)，這種訓練方法叫做margin-based ranking criterion。是不是聽起來很熟悉？對的，就是來自SVM。支持向量機也是如此，要將正和負盡可能分開，找出最大距離的支持向量。同理，TransE也是如此，我們盡可能將對的和錯的分開。margin值一般設為1了。

3、關于模型的參數：參數θ是所有實體的向量。設一共有 |E| 個實體和 |R| 個關系，每個實體/關系的向量長度為d維，因此，一共有（ |E| + |R| ） * ?d 個參數。

4、關于參數的更新：我們使用的是隨機梯度下降（Stochastic Gradient Descent，SGD）訓練方法。SGD不用對所有的和求梯度，而是對一個batch求梯度之后就立即更新theta值。

? ? ? ?對于數據集大的情況下，有速度。但是每一次更新都是針對這一個batch里的三元組的向量更新的，也就是意味著，一次更新最多更新(3+2)*batch_size*d 個參數（設一個batch的長度為batch_size）。并不是把所有的theta值都更新了，或者說不用更新整個（ |E| + |R| ） * ?d?矩陣，只需要更新sample里抽出來的batch里的向量即可。為什么可以這樣呢（也就是為什么可以不用把參數全更新了，而是只更新一部分）？因為參數之間并沒有依賴（或者說沖突conflict），對于此，可以參考論文?Hogwild!: A Lock-Free Approach to Parallelizing Stochastic。

5、對SGD多說兩句：SGD的收斂沒有GD好，但是，這反而是優點，因為在機器學習領域，過于best的結果反而是害處，因為用于過擬合（overfitting）。也就是，盡管叫做D（下降），但整個過程我們難保一直D下去。只能保證在forever可以做到D。

6、歸一化公式的分母是向量的平方和再開方；而對于距離公式，是向量的平方和（沒有開方）。公式的錯誤書寫，會引起收斂的失敗。

7、對于每一次迭代，每一次的歸一化約束（constraint）實體長度為1（減少任意度量（scaling ?freedoms（SE）），使得收斂有效（避免 trivially minimize（transE）），但對關系不做此要求。（然而我自己試驗的結果是，歸一化關系，會使精度加大和收斂加強）

tranE的python代碼（github）

總結

以上是生活随笔為你收集整理的TransE算法（Translating Embedding）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。