作者：qfan，騰訊 WXG 應用研究員

隨著深度學習在工業屆不斷火熱，Embedding 技術便作為“基本操作”廣泛應用于推薦、廣告、搜索等互聯網核心領域中。Embedding 作為深度學習的熱門研究方向，經歷了從序列樣本、圖樣本、再到異構的多特征樣本的發展過程。本文主要系統總結了現在主流的 Embedding 技術，簡單介紹它們的基本原理，希望對大家快速整理相關知識有所幫助。

一、引言

在提到 Embedding 時，首先想到的是“向量化”，主要作用是將高維稀疏向量轉化為稠密向量，從而方便下游模型處理。那什么是 embedding 呢？下面是大家對 embedding 的定義：

In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. -- Wikipedia

An embedding is a mapping from discrete objects, such as words, to vectors of real numbers. -- Tensorflow 社區

Embedding 是用一個低維稠密向量來表示一個對象，使得這個向量能夠表達相應對象的某些特征，同時向量之間的距離能反應對象之間的相似性。 -- 王喆《深度學習推薦系統》

將一個實例（instance）從復雜的空間嵌入（投射）到相對簡單的空間，以便對原始實例進行理解，或者在相對簡單的空間中進行后續操作。 -- chrisyi《Network embedding 概述》

我個人比較傾向于 Tensorflow 社區給出的定義，即Embedding是離散實例連續化的映射。如下圖所示，可以將離散型詞 embedding 成一個四維的連續稠密向量；也可以將圖中的離散節點 embedding 成指定維度的連續稠密向量。

Embedding 作為深度學習的熱門研究方向，經歷了從序列樣本、理圖樣本、再到異構的多特征樣本的發展過程。此外，由于 embedding 技術本身具有較強的綜合信息表示能力、較低的上線部署門檻，進一步加速了其在工業上的落地。

Embedding 對于推薦系統中深度學習方法的主要應用可以簡單總結如下：

• 作為 Embedding 層嵌入到深度模型中，實現將高維稀疏特征到低維稠密特征的轉換（如 Wide&Deep、DeepFM 等模型）；

• 作為預訓練的 Embedding 特征向量，與其他特征向量拼接后，一同作為深度學習模型輸入進行訓練（如 FNN）；

• 在召回層中，通過計算用戶和物品的 Embedding 向量相似度，作為召回策略（比 Youtube 推薦模型等）；

• 實時計算用戶和物品的 Embedding 向量，并將其作為實時特征輸入到深度學習模型中（比 Airbnb 的 embedding 應用）。

對于推薦場景中，什么數據可以采用 Embedding 來構造特征呢？下面簡單列了下我在做微信游戲中心場景游戲和內容推薦時主要采用 embedding 技術來處理的數據（本文只簡單列一下主要的點，后續會詳細文章來具體講如何處理以及其帶來的效果）。

• User 數據（用戶的基礎屬性數據，如性別、年齡、關系鏈、興趣偏好等）

• • 對于用戶興趣偏好，一般簡單地采用文本 embedding 方法來得到各標簽的 embedding 向量，然后根據用戶對個標簽的偏好程度做向量加權；

  • 對于關系鏈數據（如同玩好友、游戲中心相互關注等），構造用戶關系圖，然后 ?采用基于圖的 embedding 方法來得到用戶的 embedding 向量；

• Item 數據（Item 基本信息數據，如標題、作者、游戲簡介、標簽等）

• • 對于文本、簡介和標簽等可以采用基于文本的 embedding 方法來在已有語料上預訓練模型，然后得到對應的 embedding 向量（如 word2vec 或者 BERT）；

  • 此外對于有明確關系的（如 item->文本->標簽 or 關鍵詞）可以采用對關鍵詞/標簽的向量均值來表示 item 的文本向量（這里安利一下 FaceBook 開源的StarSpace）；

• User 行為數據（用戶在場景中的行為數據，如點擊、互動、下載等）

• • 針對用戶對 Item 的操作（如點擊、互動、下載）構造用戶->item+Item 標簽體系，構造用戶-item-tag 的異構網絡，然后可以采用 Metapath2vec 來得到各節點的 embedding 向量；

  • 通過記錄用戶在整個場景訪問 item，構造 Item-Item 關系圖，然后采用 DeepWalk 算法得到 item 的向量，用來挖掘 Item 間的關系特征；

• 額外數據（外部擴充數據，如用戶游戲行為、用戶微信其他場景活躍等）

• • 標簽型（主要是用戶在各場景的興趣偏好）：

  • 關系鏈型（如游戲中心好友、游戲內好友、開黑好友）可以采用用戶關系構造用戶關系圖，采用 Graph embedding 方法（如 GraphSAGE）來表示用戶抽象特征

當然，這些處理方法只是我個人這一年多的經驗，可能有些地方用的并不是很合理，歡迎大家一起交流。

下面開始本文正文“介紹現在主流的 Embedding 技術”，主要分三大塊：

• 經典的矩陣分解方法：這里主要是介紹 SVD 方法

• 基于內容的 embedding 方法：這部分主要涉及到 NLP 相關的文本 embedidng 方法，包括靜態向量 embedding（如 word2vec、GloVe 和 FastText）和動態向量 embedding（如 ELMo、GPT 和 BERT）

• 基于 Graph 的 embedding 方法：這部分主要是介紹圖數據的 embedding 方法，包括淺層圖模型（如 DeepWalk、Node2vec 和 Metapath2vec）和深度圖模型（如基于譜的 GCN 和基于空間的 GraphSAGE）

二、經典矩陣分解法

1、奇異值分解

SVD（Singular value decomposition，奇異值分解）是一種矩陣分解的方法，任何矩陣，都可以通過SVD的方法分解成幾個矩陣相乘的形式。

其中和是正交矩陣，是特征值矩陣。

對于機器學習，SVD一個主要優點是對矩陣降維，對于高維矩陣可以通過SVD表示成三個維度相對較低的矩陣、和。

在推薦系統中，可以將用戶行為構造成User-Item的評分矩陣 ，其中m和n分別表示平臺的User數和Item數。 表示用戶對物品的評分（也可以是點擊、互動、播放、下載等行為），用于刻畫User對Item的有效操作。采用SVD算法將分解成 、和。

雖然，從形式上看SVD分解簡單直接，但由于日常User-Item的評分矩陣事高度稀疏的，而SVD分解要求矩陣是稠密的，通常采用對評分矩陣中的缺失值進行補全（比如補0、全局平均值、用戶物品平均值補全等）得到稠密矩陣。再用SVD分解并降維。但實際過程中，元素缺失值是非常多的，導致了傳統SVD不論通過以上哪種方法進行補全都是很難在實際應用中起效果。此外傳統SVD在實際應用中還有一個嚴重的問題——計算復雜度（時間復雜度是，空間復雜度是）。當用戶數和物品總量過大（如千上萬級），對矩陣做SVD分解是非常耗時。這是得傳統的SVD分解方法很難在實際業務中應用起來。

研究者們做了大量工作來解決傳統SVD的稀疏數據不適用和高計算復雜度的問題，其中主要的有FunkSVD、BiasSVD和SVD++算法。

2、隱語義模型（Latent Factor Model）

LFM主要代表是2006年由Simon Funk在博客上公開的算法FunkSVD，將評分矩陣分解成兩個低維矩陣（P和Q）相乘，可直接通過訓練集中的觀察值利用最小化均方根學習P，Q矩陣。

用戶對物品的評分可以表示為，其中和分別是矩陣和對應第和的列向量，表示用戶和物品的隱向量。FunkSVD核心思想是將在原始SVD上加了線性回歸，使得我們可以用均方差作為損失函數來尋找P和Q的最佳值：

上式可以通過梯度下降法來求解，損失函數求偏導為：

參數更新如下：

在Funk-SVD獲得巨大成功之后，研究人對其進行進一步優化工作，提出了一系列優化算法。其中BiasSVD就是在原始FunkSVD模型中添加三項偏移項優化得到的：

• 物品偏移量 ()：表示了物品接受的評分和用戶沒有多大關系，物品本身質量決定了的偏移；

• 用戶偏移量 ()：有些用戶喜歡打高分，有些用戶喜歡打低分，用戶決定的偏移；

• 全局偏移量 ()：根據全局打分設置的偏移，可能和整體用戶群和物品質量有相對應的關系。

BiasSVD的預測結果為：

損失函數為：

SVD++算法是在BiasSVD的基礎上引入隱式反饋（如用戶歷史瀏覽、用戶歷史評分、電影歷史瀏覽、電影歷史評分等）作為新的參數，其預測結果為：

其優化如下：

雖然矩基于矩陣分解的方法原理簡單，容易編程實現，具有較好的擴展性，在小規模數據上也有不錯的表現。但對于如今互聯網推薦場景的數據量級，矩陣分解方法很難與深度學習算法一戰。

三、基于內容的Embedding方法

對于基于內容的embedding方法，主要是針對文本類型數據（對圖像、音視頻等多媒體數據embedding方法，感興趣的可以自行查閱相關技術）。下圖是從word2vec到BERT的發展歷史（最新已經發展到了GPT3了，模型更新太快，還沒來得及用，就已經過時了），從圖中可以看出自從2013年word2vec橫空出世后，文本embedding方法不斷被優化。從最開始的靜態向量方法（如word2vec、GloVe和FastText）發展為能根據上下文語義實現動態向量化的方法如（ELMo、GPT和BERT）。下面主要從分靜態向量和動態向量兩個方面來介紹相應的方法。

1、靜態向量

所謂靜態向量指的是一旦訓練完成后，對應的向量便不再發生改變，比如一個詞經過向量化之后，在后續的場景中該詞對應的向量不會發生改變。這些方法主要包括Word2Vec、GloVe和FastText。

A) Word2vec

Word2vec是2013年Google發布的無監督詞向embedding模型。該模型采用CBOW或Skip-gram模型來訓練詞向量，將詞從one-hot編碼的向量映射成d維稠密向量：

其中CBOW是采用詞的上下文來預測該詞，而Skip-gram則是采用詞來預測其上下文。兩者網絡結構相似，通常所得到的詞向量效果相差不大；但對于大型語料，Skip-gram要優于CBOW。

B) GloVe

GloVe（Global Vectors for Word Representation）是2014年由斯坦福大學提出的無監督詞向量表示學習方法，是一個基于全局詞頻統計（count-based & overall statistics）的詞表征工具。由它得到的詞向量捕捉到單詞之間一些語義特性，比如相似性、類比性等。GloVe主要分為三步：

• 基于語料構建詞的共現矩陣

  表示詞和詞在特定大小的窗口內共同出現的次數。如對于語料：I play cricket, I love cricket and I love football，窗口為2的的共現矩陣可以表示為：

構造詞向量和貢獻矩陣之間的關系：

其中，和是要求解的詞向量，和是兩個詞向量的偏差項。

• 最終 GloVe 的 loss function 如下：

其中，表示語料庫中詞個數。在語料庫中，多個單詞會一起出現多次，表示權重函數主要有以下原則：

• • 非遞減函數，用于確保多次一起出現的單詞的權重要大于很少在一起出現的單詞的權重

  • 權重不能過大，達一定程度之后應該不再增加

  • ，確保沒有一起出現過的單詞不參與loss的計算

在論文中，作者給出了如下分段函數：

通過實驗，作者得到了效果相對較好的 ，，此時對應 曲線如下圖：

CBOW和Skip-gram是local context window的方法，缺乏了整體的詞和詞的關系，負樣本采樣會缺失詞的關系信息。此外，直接訓練Skip-gram類型的算法，很容造成高曝光詞匯得到過多的權重。

Global Vector融合了矩陣分解Latent Semantic Analysis (LSA)的全局統計信息和local context window優勢。融入全局的先驗統計信息，可以加快模型的訓練速度，又可以控制詞的相對權重。

C) FastText

FastText是FaceBook在2017年提出的文本分類模型（有監督學習）。詞向量則是FastText的一個副產物。FastText模型結果如下圖所示：

其中表示一個文本中的n-gram向量，每個特征是詞向量的平均值。從模型結構可以看出，FastText與CBOW模型的結構相似，不同在于FastText預測的是全部的n-gram去預測指定類別，而CBOW預測的是中間詞。

2、動態向量

由于靜態向量表示中每個詞被表示成一個固定的向量，無法有效解決一詞多義的問題。在動態向量表示中，模型不再是向量對應關系，而是一個訓練好的模型。在使用時，將文本輸入模型中，模型根據上下文來推斷每個詞對應的意思，從而得到該文本的詞向量。在對詞進行向量表示時，能結合當前語境對多義詞進行理解，實現不同上下文，其向量會有所改變。下面介紹三種主流的動態向量表示模型：ELMo、GPT和BERT。

A) ELMo

ELMo（Embeddings from Language Models）是2018年3月發表，獲得了NAACL18的Best Paper。ELMo的模型結構如下圖所示：

由于當時并沒有提出現在火熱的Transformer結構，ELMo采用的是多層雙向LSTM來搭建模型。在給定一個包含N個token的文本(t1, t2, ..., tN)：

• 前向語言模型用于計算給定句子t1,t2,...,tk-1，目標為tk的概率：

• 后向語言模型與前向相反，對于給定tk+1,tk+2,...,tN，目標為tk的概率：

最終目標函數為：

其中，是輸入token的embedding，表示softmax層的參數，和分別是雙向LSTM的參數。

對于每個輸入的token，一個L層的雙向LSTM輸出有2L+1個向量：

其中，表示第層中底個節點的輸出（和分別表示前向和反向）,表示token layer，表示雙向LSTM layer。

在下游的任務中， ELMo把所有層的R壓縮在一起形成一個向量：

具體步驟如下：

預訓練biLM模型，通常由兩層bi-LSTM組成，之間用residual connection連接起來。

在任務語料上fine tuning上一步得到的biLM模型，這里可以看做是biLM的domain transfer。

利用ELMo提取word embedding，將word embedding作為輸入來對任務進行訓練。

B) GPT

GPT-1（Generative Pre-Training）是OpenAI在2018年提出的，采用pre-training和fine-tuning的下游統一框架，將預訓練和finetune的結構進行了統一，解決了之前兩者分離的使用的不確定性（例如ELMo）。此外，GPT使用了Transformer結構克服了LSTM不能捕獲遠距離信息的缺點。GPT主要分為兩個階段：pre-training和fine-tuning

Pre-training（無監督學習）

預訓練模型采用前向Transformer結構如下圖所示：

GPT采用auto regressive language model對大量文本進行無監督學習，目標函數就是語言模型最大化語句序列出現的概率，其損失函數為：

其中，k為上文的窗口，表示參數為的神經網絡模型。

表示左側窗口的上下文詞向量，表示Transformer的層數，表示詞向量矩陣，表示position embedding矩陣（作者對position embedding矩陣進行隨機初始化并訓練學習）。

Fine-tuning（有監督學習）

采用無監督學習預訓練好模型后后，可以把模型模型遷移到新的任務中，并根據新任務來調整模型的參數。

假設數據集的一個樣本為，則將輸入到預訓練好的模型中，得到文本的embedding向量，最后采用線性層和softmax來預測標簽，輸出和損失分別為：

其中，為下游任務的參數。

為避免在Fine-Tuning時，模型陷入過擬合和加速收斂，添加了輔助訓練目標的方法，就是在使用最后一個詞的預測結果進行監督學習的同時，前面的詞繼續上一步的無監督訓練。最終的損失函數為：

其中，用于控制無監督目標權重，一般取。

總體來說，Fine-tuning階段需要的額外參數是和以隔符token的embedding。其他任務遷移的輸入格式可參考下張圖：

C) BERT

BERT (Bidirectional Encoder Representations from Transformers)是Goole在2018年10月發表的，當時刷新了11項NLP任務，從此成為NLP領域“最靚的仔”。BERT、ELMo和GPT模型結構對比圖如下圖所示：

相較于ELMo，BERT采用句子級負采樣來得到句子表示/句對關系，使用Transformer模型代替LSTM，提升模型表達能力，Masked LM解決“自己看到自己”的問題。相較于GPT，BERT采用了雙向的Transformer，使得模型能夠挖掘左右兩側的語境。此外，BERT進一步增強了詞向的型泛化能力，充分描述字符級、詞級、句子級甚至句間的關系特征。

BERT的輸入的編碼向量（長度為512）是3種Embedding特征element-wise和，如下圖所示：

這三種Embedding特征分別是：

• Token Embedding (WordPiece)：將單詞劃分成一組有限的公共詞單元，能在單詞的有效性和字符的靈活性之間取得一個折中的平衡。如圖中的“playing”被拆分成了“play”和“ing”；

• Segment Embedding：用于區分兩個句子，如B是否是A的下文（對話場景，問答場景等）。對于句子對，第一個句子的特征值是0，第二個句子的特征值是1；

• Position Embedding：將單詞的位置信息編碼成特征向量，Position embedding能有效將單詞的位置關系引入到模型中，提升模型對句子理解能力；

最后，[CLS]表示該特征用于分類模型，對非分類模型，該符合可以省去。[SEP]表示分句符號，用于斷開輸入語料中的兩個句子。

在模型預訓練階段，BERT采用兩個自監督任務采用來實現模型的多任務訓練：1）Masked Language Model；2）Next Sentence Prediction

Masked Language Model (MLM)

MLM的核心思想早在1953年就被Wilson Taylor[Wilson]提出，是指在訓練時隨機從輸入語料中mask掉一些單，然后通過該詞上下文來預測它（非常像讓模型來做完形填空），如下圖所以：

在論文實驗中，只有15%的Token會被隨機Mask掉。在訓練模型時，一個句子會被多次輸入模型中用于參數調優，對于某個要被Mask的Token并不是每次都一定會被Mask掉：

• 80%概率直接替換為[MASK]，如my dog is hairy -> my dog is [mask]

• 10%概率替換為其他任意Token，如my dog is hairy -> my dog is apple

• 10%概率保留為原始Token，如my dog is hairy -> my dog is hairy

這樣做的好處主要有：

• 如果某個Token100%被mask掉，在fine-tuning的時候會這些被mask掉的Token就成為OOV，反而影響模型的泛化性;

• 加入隨機Token是因為Transformer要保持對每個輸入Token的分布式表征，否則模型就會記住這個[MASK]=“hairy”

• 雖然加入隨機單詞帶來的負面影響，但由于單詞被隨機替換掉的概率只有15%*10% =1.5%，負面影響可以忽略不計

Next Sentence Prediction (NSP)

許多重要的下游任務譬如QA、NLI需要語言模型理解兩個句子之間的關系，而傳統的語言模型在訓練的過程沒有考慮句對關系的學習。BERT采用NSP任務來增強模型對句子關系的理解，即給出兩個句子A、B，模型預測B是否是A的下一句，如下圖所示：

訓練數據集構造上，從平行語料中隨機抽取連續的兩句話：50%保留抽取的兩句話（label=IsNext）；50%的第二句話隨機從語料中抽取（label=NotNext）

Fine-tuning

在https://github.com/google-research/bert.git中有N多種預訓練模型，大家可以根據需要下載對應的模型，下面主要給出兩個常用的模型：

• BERT-Base_L-12_H-768_A-12，總參數為110M

• BERT-Large_L-24_H-1024_A-16，總參數為340M

其中，L表示網絡層數（Transformer blocks數量），A表示Multi-Head Attention中self-Attention數，filter的尺寸是4H

BERT提供了4中不同的下游任務的微調方案，大家根據自己的語料在預訓練好的模型上采用這些任務來微調模型：

• 句對關系判斷：第一個起始符號[CLS]經過編碼后，增加Softmax層，即可用于分類；

• 單句分類任務：實現同“句對關系判斷”；

• 問答類任務：問答系統輸入文本序列的question和包含answer的段落，并在序列中標記answer，讓BERT模型學習標記answer開始和結束的向量來訓練模型；

• 序列標準任務：識別系統輸入標記好實體類別（人、組織、位置、其他無名實體）文本序列進行微調訓練，識別實體類別時，將序列的每個Token向量送到預測NER標簽的分類層進行識別。

BERT是截止至2018年10月的最新的的SOTA模型，通過預訓練和精調可以解決11項NLP的任務。采用Transformer作為算法的主框架，能更好地捕捉更長距離的依賴和語句中的雙向關系。與之前的預訓練模型相比，BERT能捕捉到正意義上的bidirectional context信息。采用MLP+NSP多任務方法使模型具有更強的泛化能力。最后，強大的計算資源+更大的數據造就了更強更復雜的模型。

四、基于Graph的Embedding方法

基于內容的Embedding方法（如word2vec、BERT等）都是針對“序列”樣本（如句子、用戶行為序列）設計的，但在互聯網場景下，數據對象之間更多呈現出圖結構，如1）有用戶行為數據生成的物品關系圖；2）有屬性和實體組成的只是圖譜。

對于圖結構數據，基于內容的embedding方法不太好直接處理了。因此，為了解決土結構數據的問題，Graph Embedding開始得到大家的重視，并在推薦系統領域流行起來。

Graph Embedding是一種將圖結構數據映射為低微稠密向量的過程，從而捕捉到圖的拓撲結構、頂點與頂點的關系、以及其他的信息。目前，Graph Embedding方法大致可以分為兩大類：1）淺層圖模型；2）深度圖模型。

1、淺層圖模型

淺層圖模型主要是采用random-walk + skip-gram模式的embedding方法。主要是通過在圖中采用隨機游走策略來生成多條節點列表，然后將每個列表相當于含有多個單詞（圖中的節點）的句子，再用skip-gram模型來訓練每個節點的向量。這些方法主要包括DeepWalk、Node2vec、Metapath2vec等。

A) DeepWalk

DeepWalk是第一個將NLP中的思想用在Graph Embedding上的算法，輸入是一張圖，輸出是網絡中節點的向量表示，使得圖中兩個點共有的鄰居節點（或者高階鄰近點）越多，則對應的兩個向量之間的距離就越近。

DeepWalk得本質可以認為是：random walk + skip-gram。在DeepWalk算法中，需要形式化定義的是random walk的跳轉概率，即到達節點后，下一步遍歷其鄰居節點的概率：

其中，表示及節點的所有出邊連接的節點集合，表示由節點連接至節點的邊的權重。由此可見，原始DeepWalk算法的跳轉概率是跳轉邊的權重占所有相關出邊權重之和的比例。算法具體步驟如下圖所示：

DeepWalk算法原理簡單，在網絡標注頂點很少的情況也能得到比較好的效果，且具有較好的可擴展性，能夠適應網絡的變化。但由于DeepWalk采用的游走策略過于簡單（BFS），無法有效表征圖的節點的結構信息。

B) Node2vec

為了克服DeepWalk模型的random walk策略相對簡單的問題，斯坦福大學的研究人員在2016年提出了Node2vec模型。該模型通過調整random walk權重的方法使得節點的embedding向量更傾向于體現網絡的同質性或結構性。

• 同質性：指得是距離相近的節點的embedding向量應近似，如下圖中，與節點相連的節點、、和的embedding向量應相似。為了使embedding向量能夠表達網絡的同質性，需要讓隨機游走更傾向于DFS，因為DFS更有可能通過多次跳轉，到達遠方的節點上，使游走序列集中在一個較大的集合內部，使得在一個集合內部的節點具有更高的相似性，從而表達圖的同質性。

• 結構性：結構相似的節點的embedding向量應近似，如下圖中，與節點結構相似的節點的embedding向量應相似。為了表達結構性，需要隨機游走更傾向于BFS，因為BFS會更多的在當前節點的鄰域中游走，相當于對當前節點的網絡結構進行掃描，從而使得embedding向量能刻畫節點鄰域的結構信息。

在Node2vec中，同樣是通過控制節點間的跳轉概率來控制BFS和DFS傾向性的。如下圖所示，當算法先由節點跳轉到節點，準備從節點跳轉至下一個節點時（即 ），各節點概率定義如下：

其中，是節點和邊的權重，定義如下：

這里表示節點與的最短路徑，如與的最短路徑為1（即），則。作者引入了兩個參數和來控制游走算法的BFS和DFS傾向性：

• return parameter p：值越小，隨機游走回到節點的概率越大，最終算法更注重表達網絡的結構性

• In-out parameter q：值越小，隨機游走到遠方節點的概率越大，算法更注重表達網絡的同質性

當時，Node2vec退化成了DeepWalk算法。

下圖是作者通過調整p和q，使embedding向量更傾向于表達同質性和結構性的可視化結果：

從圖中可以看出，同質性傾向使相鄰的節點相似性更高，而結構性相似使得結構相似的節點具有更高的相似性。Node2vec的算法步驟如下：

相較于DeepWalk，Node2vec通過設計biased-random walk策略，能對圖中節點的結構相似性和同質性進行權衡，使模型更加靈活。但與DeepWalk一樣，Node2vec無法指定游走路徑，且僅適用于解決只包含一種類型節點的同構網絡，無法有效表示包含多種類型節點和邊類型的復雜網絡。

C) Metapath2vec

為了解決Node2vec和DeepWalk無法指定游走路徑、處理異構網絡的問題，Yuxiao Dong等人在2017年提出了Metapath2vec方法，用于對異構信息網絡（Heterogeneous Information Network, HIN）的節點進行embedding。

Metapath2vec總體思想跟Node2vec和DeepWalk相似，主要是在隨機游走上使用基于meta-path的random walk來構建節點序列，然后用Skip-gram模型來完成頂點的Embedding。

作者首先給出了異構網絡（Heterogeneous Network）的定義：

即，存在多種類型節點或邊的網絡為異構網絡。

雖然節點類型不同，但是不同類型的節點會映射到同一個特征空間。由于異構性的存在，傳統的基于同構網絡的節點向量化方法很難有效地直接應用在異構網絡上。

為了解決這個問題，作者提出了meta-path-based random walk：通過不同meta-path scheme來捕獲不同類型節點之間語義和結構關系。meta-path scheme定義如下：

其中表示不同類型節點和之間的關系。節點的跳轉概率為：

其中，，表示節點的類型的鄰居節點集合。me ta-path的定義一般是對稱的，比如user-item-tag-item-user。最后采用skip-gram來訓練節點的embedding向量：

其中：表示節點的上下文中，類型為的節點，

通過分析metapath2vec目標函數可以發現，該算法僅在游走是考慮了節點的異構行，但在skip-gram訓練時卻忽略了節點的類型。為此，作者進一步提出了metapath2vec++算法，在skip-gram模型訓練時將同類型的節點進行softmax歸一化：

metaptah2vec和metapath2vec++的skip-gram模型結構如下圖所示：

metapath2vec++具體步驟如下圖所示：

2、深度圖模型

上一節講的淺層圖模型方法在世紀應用中是先根據圖的結構學習每個節點的embedding向量，然后再講得到的embedding向量應用于下游任務重。然而，embedding向量和下游任務是分開學習的，也就是說學得的embedding向量針對下游任務來說不一定是最優的。為了解決這個embedding向量與下游任務的gap，研究人員嘗試講深度圖模型是指將圖與深度模型結合，實現end-to-end訓練模型，從而在圖中提取拓撲圖的空間特征。主要分為四大類：Graph Convolution Networks (GCN)，Graph Attention Networks (GAT)，Graph AutoEncoder (GAE)和Graph Generative Networks (GGN)。

本節主要簡單介紹GCN中的兩個經典算法：1）基于譜的GCN (GCN)；2）基于空間的GCN (GraphSAGE)。

其他方法有興趣的同學可以參考。。。

提取拓撲圖的空間特征的方法主要分為兩大類：1）基于空間域或頂點域spatial domain(vertex domain)的；2）基于頻域或譜域spectral domain的。通俗點解釋，空域可以類比到直接在圖片的像素點上進行卷積，而頻域可以類比到對圖片進行傅里葉變換后，再進行卷積。

• 基于spatial domain：基于空域卷積的方法直接將卷積操作定義在每個結點的連接關系上，跟傳統的卷積神經網絡中的卷積更相似一些。主要有兩個問題：1）按照什么條件去找中心節點的鄰居，也就是如何確定receptive field；2）按照什么方式處理包含不同數目鄰居的特征。

• 基于spectral domain：借助卷積定理可以通過定義頻譜域上的內積操作來得到空間域圖上的卷積操作。

A) GCN

圖神經網絡的核心工作是對空間域(Spatial Domain)中節點的Embedding進行卷積操作（即聚合鄰居Embedding信息），然而Graph和Image數據的差別在于節點鄰居個數、次序都是不定的，使得傳統用于圖像上的CNN模型中的卷積操作不能直接用在圖上，因此需要從頻譜域(Spectral Domain)上重新定義卷積操作再通過卷積定理轉換回空間域上。

譜圖卷積是直接對圖結構數據及節點進行卷機操作，其定信號與卷積核（為參數化的濾波器）在傅立葉域上的乘積為：

其中，是歸一化的拉普拉斯矩陣的特征向量的矩陣：，和分別表示度矩陣和圖的鄰接矩陣。由于上述卷積運算的計算復雜度較高（相乘的計算復雜度為$O(N^2)，以及圖的拉普拉斯分解計算量較大），使得傳統的普卷積運算無法得到有效應用。

為了緩解計算問題，Hammond在2011年的論文《Wavelets on graphs via spectral graph theory - HAL-Inria》中提出可以用切比雪夫多項式近似核卷積：

其中， ，表示的最大特征值。是切比雪夫多項式系數向量。通過使用切比雪夫多項式展開，卷積運算可以通過遞歸近似：取多項式的前K項表示對k跳的領據及特征進行卷機運算。

Thomas等人在2017年對上式做了進一步簡化：限制每個卷積層僅處理一階鄰居特征，通過采用分層傳播規則疊加多層卷機，從而實現對多階鄰居特征的傳播。通過限制卷機核的一階近似能緩解節點度分布非常寬的圖對局部鄰域結構的過度擬合問題。如下圖所示，通過集聯多個卷積層，節點能聚合多個鄰居節點特征。

使用切比雪夫一階展開（K=1）的核卷積+非線性單元如下：

其中，表示第層卷積核的輸出，作為的數據，為各節點的特征。是卷積核的一階近似，可以簡單理解成鄰接節點特征的加權平均。為非線性激活函數，為第層的卷積核參數（每個節點共享）。

Thomas等人在設計卷積核時做了兩個trick：

• 每個節點增加了selp-loop，使在卷積計算時能考慮當前節點自身特征：

• 對進行對稱歸一化：。避免了鄰接節點數越多，卷積后結果越大的情況。此外這個操作還能考慮鄰接節點度大小對卷積核的影響。

B) GraphSAGE

GraphSAGE（Graph SAmple and aggreGatE）是基于空間域方法，其思想與基于頻譜域方法相反，是直接在圖上定義卷積操作，對空間上相鄰的節點上進行運算。其計算流程主要分為三部：

• 對圖中每個節點領據節點進行采樣

• 根據聚合函數聚合鄰居節點信息（特征）

• 得到圖中各節點的embedding向量，供下游任務使用

GraphSAGE生成Embedding向量過程如下：

其中K表示每個節點能夠聚合的鄰居節點的跳數（例如K=2時，每個頂點可以最多根據其2跳鄰居節點的信息來表示自身的embedding向量）。算法直觀上是在每次迭代中，節點聚合鄰居信息。隨著不斷迭代，節點得到圖中來自越來越遠的節點信息。

鄰居節點采樣：在每個epoch中，均勻地選取固定大小的鄰居數目，每次迭代選取不同的均勻樣本。

GraphSAGE的損失函數如下：

其中，和表示節點和的embedding向量，是固定長度的鄰居覺點，是sigmoid函數，和分別表示負樣本分布和數目。

對于聚合函數的，由于在圖中節點的鄰居是無序的，聚合函數應是對稱的（改變輸入節點的順序，函數的輸出結果不變），同時又具有較強的表示能力。主要有如下三大類的聚合函數：

• Mean aggretator：將目標節點和其鄰居節點的第k-1層向量拼接起來，然后對計算向量的element-wise均值，最后通過對均值向量做非線性變換得到目標節點鄰居信息表示：

• Pooling aggregator：先對目標節點的鄰居節點向量做非線性變換并采用pooling操作（maxpooling或meanpooling）得到目標節點的鄰居信息表示：

• LSTM aggretator：使用LSTM來encode鄰居的特征，為了忽略鄰居之間的順序，需要將鄰居節點順序打亂之后輸入到LSTM中。LSTM相比簡單的求平均和Pooling操作具有更強的表達能力。

五、總結

針對當前熱門的embedding技術，本文系統的總結了能處理各類型數據的embedding方法，如傳統基于矩陣分解的方法（如SVD分解）、處理文本的embedding方法（如Word2vec、FastText等）以及處理圖數據的embedding方法（如DeepWalk、GraphSAGE等）。在推薦系統中，針對于不同數據類型，可以靈活采用上述方法來實現對數據的抽象表示。如可以基于用戶行為，構造item列表，采用基于文本的方法對item進行向量化；也可以通過構建user和item關系圖，采用基于圖的方法來對user和item進行向量化。在實際過程中，不同的向量化方法得到的embedding結果也會有較大差異，需要根據具體業務需求來選擇相應的算法。如要挖掘用戶與用戶的同質性，可以嘗試采用Node2vec；此外，如果需要結合物品或Item的side-info，可以考慮GraphSAGE算法來對圖中節點進行embedding。跟深度學習煉丹術一樣，要熟練掌握各類embedding技術，需要根據具體應用場景不斷試錯積累經驗。最后，要司慶了，祝我們“煉丹人”能快樂搬磚！

參考文獻

Simon Funk. Netflix Update: Try This at Home. http://www.sifter.org/~simon/journal/20061211.html. 2006

Koren, Yehuda. "Factorization meets the neighborhood: a multifaceted collaborative filtering model." Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 2008

Mikolov, Tomas, et al. "Distributed representations of words and phrases and their compositionality." Advances in neural information processing systems. 2013.

Pennington, Jeffrey, et al. "Glove: Global vectors for word representation." Conference on empirical methods in natural language processin. 2014.

Bojanowski, Piotr, et al. "Enriching word vectors with subword information." Transactions of the Association for Computational Linguistics 5 (2017): 135-146.

Peters, Matthew E., et al. "Deep contextualized word representations." arXiv preprint arXiv:1802.05365 (2018). Radford, Alec, et al. "Improving language understanding by generative pre-training." (2018): 12.

Devlin, Jacob, et al. "Bert: Pre-training of deep bidirectional transformers for language understanding." arXiv preprint arXiv:1810.04805 (2018).

Perozzi, Bryan, et al. "Deepwalk: Online learning of social representations." ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.

Grover, Aditya, et al. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.

Dong, Yuxiao, et al. "metapath2vec: Scalable representation learning for heterogeneous networks." Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017.

Wilson L Taylor. 1953. cloze procedure: A new tool for measuring readability. Journalism Bulletin, 30(4):415–433.

Hammond, David K., Pierre Vandergheynst, and Rémi Gribonval. "Wavelets on graphs via spectral graph theory." Applied and Computational Harmonic Analysis 30.2 (2011): 129-150.

Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv:1609.02907 (2016).

Hamilton, Will, et al. "Inductive representation learning on large graphs." Advances in neural information processing systems. 2017.

云開發者專屬盛會

邀你一起「重新定義開發」

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的用万字长文聊一聊 Embedding 技术的全部內容，希望文章能夠幫你解決所遇到的問題。

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