論文閱讀 Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks
6 Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks
link://arxiv.org/abs/1908.01207
Abstract
本文提出了一種在嵌入空間中顯示建模用戶/項目的未來軌跡的模型JODIE。該模型基於RNN模型，用於學慣用戶和項目的嵌入軌跡。JODIE可以進行未來軌跡的預測。本文還提出了 t-Batch演算法，利用該方法可以創建時間相同的batch，並使訓練速度提高9倍。
Conclusion
在本文中，提出了一個稱為JODIE的rnn模型，該模型從一系列時間交互中學慣用戶和項目的動態嵌入。JODIE學習預測用戶和項目的未來嵌入，這使得它能夠更好地預測未來用戶項目交互和用戶狀態的變化。還提出了一種訓練數據批處理方法，使JODIE比類似基準線快一個數量級
未來的工作有幾個方向。學習單個用戶和項目的嵌入是昂貴的，可以學慣用戶或項目組的軌跡，以減少參數的數量。另一個方向是描述相似實體的軌跡。最後，一個創新的方向是根據許多用戶可能與之交互的缺失預測項目設計新項目。
Figure and table
圖1 左邊是一個時序交互網路（二部圖），包含三個用戶和四個物品。連線表示在時間t和特徵向量f下的交互。右邊是用戶和物品的嵌入軌跡圖，通過訓練一個嵌入預測操作（可訓練參數矩陣）預測用戶的特徵軌跡。圖中虛線就是用戶的估計預測。
表1 對比了已存在的各種演算法和JODIE的用途，JODIE全部滿足（自己論文肯定全部滿足啊。。。）
圖2 JODIE模型：JODIE在一次交互\((u,i,t,f)\)後，通過\(RNN_U\)和\(RNN_I\)兩個模組更新\(u\)和\(i\)的動態嵌入，接著預測操作去預測\(t+∆\)時間的用戶嵌入
表2 符號的含義
圖3 展示了預測操作。這裡預測了用戶在三個間隔時間的嵌入位置，其中\(∆_1 < ∆_2 < ∆\)。隨著時間的推移，預測的嵌入會漂移得更遠。當觀察到下一次交互時，嵌入將再次更新。
表3 交互預測實驗：這張表展示了各類演算法在不同的數據集上表現，用MRR和recall作為指標
表4 用戶狀態更改預測：用auc做指標
圖4 運行時間對比
圖5 魯棒性對比
圖6 動態嵌入尺寸的魯棒性對比
Introduction
本文提出了一個工業場景中實際的四個問題
先前的方法都是等到用戶有交互才會去更新他的嵌入。比如一個今天購買的用戶，其嵌入已更新。如果在第二天、一周後甚至一個月後返回平台，嵌入將保持不變。因此，無論她什麼時候回來，都會對她做出同樣的預測和建議。然而，用戶的意圖會隨著時間的推移而改變，因此她的嵌入需要更新（預測）到查詢時間。這裡的挑戰是如何隨著時間的推移準確預測用戶/項目的嵌入軌跡。
實體有隨時間改變的屬性，也有不隨時間改變的屬性。現有的方法一般只會考慮二者其一
許多現有方法通過為每個用戶的所有項目打分來預測用戶項目交互。複雜性過高，推薦相關場景需要較低的時間複雜度（原文近乎恆定時間：near-constant time）
現在的大多數模型都是通過將交互串列化依次處理，以保證時間順序資訊。同樣時間代價較大。
本文模型JODIE學習從時間交互中生成所有用戶和項目的嵌入軌跡。在使用用戶的嵌入進行交互預測時，並不會直接使用上一次的用戶嵌入，而是先通過一個預測，預測用戶在所需時間的嵌入位置，通過通過預測預測的嵌入進行下一步的操作。（解決了第一個問題）
本文提出的模型JODIE學習從時間交互中生成所有用戶和項目的嵌入軌跡。每個用戶和項目都有兩個嵌入屬性：靜態嵌入和動態嵌入。靜態嵌入表示實體的長期平穩特性，而動態嵌入表示時變特性，並使用JODIE演算法進行學習。（解決了第二個問題）
JODIE模型由兩個主要組件組成：更新操作和預測操作。JODIE的更新操作有兩個RNN來生成用戶和項目嵌入。至關重要的是，這兩個RNN被耦合起來，以合併用戶和項目之間的相互依賴性。耦合的含義是：再一次交互後，用戶RNN根據交互項目的嵌入去更新用戶嵌入。同樣的，項目RNN使用用戶嵌入去更新項目嵌入。（這就帶來了特徵交叉）
在以往的工作中如果想預測用戶下一步的交互項目，通常會對所有項目進行打分，這樣將會帶來線形時間的複雜度。本文提出的方案是利用模型預測的嵌入，在嵌入空間找儘可能接近的嵌入，使用位置敏感哈希（LSH）技術在固定時間內高效完成。（解決了第三個問題）
作者還提出了t-batch的操作。大多數現有模型通過依次處理每個交互來學習嵌入，以保持交互之間的時間依賴性。在本文中，通過創建獨立交互的訓練batch來訓練JODIE，這樣每個batch中的交互都可以並行處理。操作為迭代地從交互網路中選擇獨立的邊集，在每個批次中，每個用戶和項目最多出現一次，用每個用戶（和項目）的交互時序排序遞增增作為順序。（解決了第四個問題）
Method
3 JODIE: JOINT DYNAMIC USER-ITEM EMBEDDING MODEL
在本節，將提出JODIE其具體模型。該模型學慣用戶的嵌入\(\boldsymbol{u}(t) \in \mathbb{R}^{n},\forall u \in \mathcal{U}\)和項目嵌入\(\boldsymbol{i}(t) \in \mathbb{R}^{n},\forall i \in \mathcal{I}\)，其中\(\forall t \in[0, T]\)來自時序用戶項交互的有序序列\(S_{r}=\left(u_{r}, i_{r}, t_{r}, f_{r}\right)\)。該交互由用戶\(u_r \in \mathcal{U}\)和項目\(i_r \in \mathcal{I}\)在時間\(t_r \in \mathbb{R}^+，0<t_{1} \leq t_{2} \ldots \leq f_{r}\)產生，每個交互都有一個相關的特徵向量\(f_r\)（例如，表示帖子文本的向量）。
JODIE由用戶和物品的交互去訓練更新操作。JODIE訓練一個預測操作，該操作使用以前觀察到的狀態和經過的時間來預測用戶未來的嵌入。當觀察到用戶和項目的下一次交互時，它們的嵌入會再次更新。
為每個用戶和項目分配了兩個嵌入：靜態嵌入和動態嵌入。我們使用這兩種嵌入來編碼實體的長期靜態特性和動態特性。
靜態嵌入：\(\overline{\boldsymbol{u}} \in \mathbb{R}^{d} \forall u \in \mathcal{U} \text { , } \overline{\boldsymbol{i}} \in \mathbb{R}^{d} \forall i \in \mathcal{I}\)不會隨時間變化。這些用於表示固定屬性，例如用戶的長期興趣。本文使用獨熱碼作為用戶和項目的靜態嵌入。
動態嵌入：為每個用戶\(u\)和項目\(i\)分配一個動態嵌入，表示為\(u(t) \in \mathbb{R}^{n} \text { , } i(t) \in \mathbb{R}^{n}\)分別位於時間\(t\)的嵌入。這些嵌入會隨著時間的推移而變化，以模擬其隨時間變化的行為和屬性。用戶/項目的動態嵌入順序是指其軌跡。
接下來介紹更新和預測操作
*3.1 Embedding update operation
在更新操作中，用戶\(u\)和項目\(i\)在時間t之間的交互\(S=（u，i，t，f）\)用於生成它們的動態嵌入\(u（t）\)和\(i（t）\)。圖2示出了更新操作。
我們的模型使用兩個遞歸神經網路進行更新，所有用戶共享\(RNN_U\)來更新用戶嵌入，所有項目共享\(RNN_I\)來更新項目嵌入。用戶RNN和項目RNN的隱藏狀態分別表示用戶和項目嵌入。
這兩個RNN是相互遞歸（mutually-recursive）的。當用戶\(u\)與項目\(i\)交互時，\(RNN_U\)在時間\(t\)將嵌入\(i(t)\)作為輸入項目，更新嵌入\(u(t^−)\) 。$i(t^−) $表示為上一個時刻的項目嵌入。
作者提到了原來普遍用的使用項目獨熱碼來訓練的缺點
a） 獨熱碼只包含關於項的id的資訊，而不包含項的當前狀態
b）當實際數據集有數百萬項時，獨熱碼的維度變得非常大，不利於訓練
本文使用項目的動態嵌入，因為它反映了項目的當前狀態，從而導致更有意義的動態用戶嵌入和更容易的訓練。出於同樣的原因，\(RNN_I\)使用動態用戶嵌入\(u（t）\)更新項目\(i\)的動態嵌入$i(t^−) \(（這是時間\)t\(之前\)u$的嵌入）。這會導致嵌入之間的相互遞歸依賴關係。見下式
\boldsymbol{u}(\boldsymbol{t})=\sigma\left(W_{1}^{u} \boldsymbol{u}\left(\boldsymbol{t}^{-}\right)+W_{2}^{u} \boldsymbol{i}\left(\boldsymbol{t}^{-}\right)+W_{3}^{u} f+W_{4}^{u} \Delta_{u}\right) \\
\boldsymbol{i}(\boldsymbol{t})=\sigma\left(W_{1}^{i} \boldsymbol{i}\left(\boldsymbol{t}^{-}\right)+W_{2}^{i} \boldsymbol{u}\left(\boldsymbol{t}^{-}\right)+W_{3}^{i} f+W_{4}^{i} \Delta_{i}\right)
\end{array}
\]
其中
\(∆_u\)表示自u上次交互（與任何項目）以來的時間，\(∆_i\)表示自i上次交互（與任何用戶）以來的時間。（引入了時間間隔資訊）。
$ f$是交互特徵向量
\(W^u_1 , . . .W^u_4\)和\(W^i_1 , . . .W^i_4\)是可訓練矩陣
$ σ $是激活函數sigmoid
RNN的變體，如LSTM、GRU和T-LSTM，在實驗上表現出類似的性能，有時甚至更差，因此在模型中使用RNN來減少可訓練參數的數量。（所以不是模型越新越好，不能單純迷戀新技術）
*3.2 Embedding projection operation
在本節 作者介紹了自己模型的另外一個核心工作，預測操作。通過這個操，模型預測了用戶未來的嵌入軌跡。該操作可以用於下游任務，例如鏈接預測等。
圖3展示了預測操作的想法。在t時刻，\(u(t)\)表示用戶的嵌入，假設有三個時間間隔\(∆_1 < ∆_2 < ∆\)，對於每個時間間隔，預測他們的嵌入軌跡\(\hat{u}(t+∆_1),\hat{u}(t+∆_2),\hat{u}(t+∆)\)，由圖3可以看到作者認為時間間隔和嵌入平移距離成正比。
接著通過\({u}(t+∆)\)的真實位置和\(\hat{u}(t+∆)\)的預測位置去訓練預測操作里的可訓練矩陣。
該操作需要兩個輸入，\(u(t)\)和\(∆\)，但是這裡並不是簡單的將嵌入和時間間隔拼接起來，而是通過哈達瑪積的操作將時間和嵌入結合，因為先前的研究表明，神經網路對處理拼接特徵的效果不是很好。
本文首先將\(∆\)通過線性層\(W_p\)計算，輸出時間上下文向量\(\boldsymbol{w}:w = W_p∆\)。\(W_p\)初始化為0均值的高斯分布。然後，將預測嵌入作為時間上下文向量與先前嵌入的元素乘積，如下所示
\]
向量\(1+w\)作為時間注意向量來縮放過去的用戶嵌入。若\(∆ = 0\)，則\(w=0\)，投影嵌入與輸入嵌入向量相同。\(∆\)值越大，預測嵌入向量與輸入嵌入向量的差異越大。
作者發現，線性層最適合預測嵌入，因為它等效於嵌入空間中的線性變換。將非線性添加到變換中會使投影操作非線性，在實驗中發現這會降低預測性能。因此，我們使用如上所述的線性變換。（本來我打算說是不是非線性的會更好的一點，結果在這就解釋了為什麼不用非線性層）
3.3 Training to predict next item embedding
本節作者將會介紹如何去預測下一個項目嵌入
在之前說過，本文的模型和之前大多數模型的區別並不是去計算兩個嵌入之間的連接概率的（類似CTR），而是輸出一個嵌入。這樣做的優點是可以將計算量從線性（每個項目數一個概率）減少到接近常數。JODIE只需要對預測層進行一次前向傳遞，並輸出一個預測項嵌入。然後，通過使用位置敏感哈希（LSH）技術，可以在近乎恆定的時間內返回嵌入最接近的項。為了維護LSH數據結構，會在項目的嵌入更新時對其進行更新。
因此JODIE通過訓練模型，最小化預測嵌入\(\tilde{j}(t+\Delta)\)和真實嵌入\(\left[\bar{j}, j\left(t+\Delta^{-}\right)\right]\)的L2距離 寫作\(\left\|\tilde{j}(t+\Delta)-\left[\bar{j}, j\left(t+\Delta^{-}\right)\right]\right\|_{2}\)。此處$ [x, y]\(代表拼接操作。上標「-」表示時間\)t$之前的嵌入.（符號定義見表2）
在時間\(t + ∆\)之前使用用戶預測嵌入\(\widehat{\boldsymbol{u}}(t+\Delta)\)和項目嵌入\(i(t+\Delta^{-})\)進行預測。
使用項目嵌入\(i(t+\Delta^{-})\)有兩點原因
（a）項目i可能在t到t+∆時間之間和其他用戶進行交互，因此，嵌入包含了更多的最新資訊
（b）用戶經常連續地與同一項目交互，包含項目嵌入有助於簡化預測。
我們使用靜態和動態嵌入來預測預測項j的靜態和動態嵌入。
使用完全連接的線性層進行預測，如下所示
\]
其中\(W1…W4\)和偏置向量\(B\)構成線性層。
綜上 損失如下
\text { Loss }=& \sum_{(u, j, t, f) \in S}\left\|\tilde{j}(t)-\left[\overline{\boldsymbol{j}}, \boldsymbol{j}\left(\boldsymbol{t}^{-}\right)\right]\right\|_{2} \\
&+\lambda_{U}\left\|u(t)-\boldsymbol{u}\left(t^{-}\right)\right\|_{2}+\lambda_{I}\left\|\boldsymbol{j}(t)-\boldsymbol{j}\left(t^{-}\right)\right\|_{2}
\end{aligned}
\]
第一個損失項使預測的嵌入誤差最小化。添加最後兩個術語是為了規範損失，並防止用戶和項目的連續動態嵌入分別變化過大。\(λ_U\)和\(λ_I\)是縮放參數，以確保損耗在相同範圍內。值得注意的是，在訓練期間不使用負取樣，因為JODIE直接輸出預測項的嵌入。
如何將損失擴展到分類預測
可以訓練另一個預測函數：\(Θ :\mathbb{R}^{n+d}→ C\)（靜態嵌入是d維，動態嵌入是n維）在交互後使用用戶的嵌入來預測標籤。其中還是會加入縮放參數將損失來防止過擬合，不只是訓練最小化交叉熵損失。
*3.4 t-Batch: Training data batching
這個方法將使模型並行化訓練，且保持原有的時間依賴性。即對於交互\(S_r\)，需要在\(S_k\)的前面 ,其中\(∀_r < k\)。
現有的並行方法都是利用用戶用戶分成不同的批次然後並行處理。但是JODIE由於兩個RNN模型是相互遞歸（mutually-recursive）的，所以這會在與同一項目交互的兩個用戶之間創建相互依賴關係，從而防止將用戶拆分為單獨的批並並行處理它們。
所以提出了在構建批次時應該滿足的兩個條件
1：可並行訓練
2：若按照索引的遞增順序處理，應保持交互的時間順序
t-batch提出了通過選擇交互網路的獨立邊緣集來創建每個批次，即同一批次中的兩個交互不共享任何公共用戶或項目。
具體說一下這個演算法的流程，分兩步
1 選擇：這一步將會從邊集中選擇互無公共節點的邊出來，並且保證每個邊\(（u，i）\)的時間戳都是最小的。
2 減少：在一次的batch訓練後，這一步將吧上一步選出來的邊從圖中刪除。接著回到1。
Experiment
4 EXPERIMENTS
靜態向量和動態嵌入維度為128，eopch選擇50
選擇三個種類的演算法baseline：
(1) Deep recurrent recommender models
RRN：C.-Y. Wu, A. Ahmed, A. Beutel, A. J. Smola, and H. Jing.Recurrent recommender networks. In WSDM, 2017.
LatentCross ：A. Beutel, P. Covington, S. Jain, C. Xu, J. Li, V. Gatto, and E. H. Chi. Latent cross: Making use of context in recurrent recommender systems. In WSDM, 2018.
Time-LSTM：Y. Zhu, H. Li, Y. Liao, B. Wang, Z. Guan, H. Liu, and D. Cai. What to do next:modeling user behaviors by time-lstm. In IJCAI, 2017.
(2) Dynamic co-evolution models
DeepCoevolve：H. Dai, Y. Wang, R. Trivedi, and L. Song. Deep coevolutionary network: Embedding user and item features for recommendation. arXiv:1609.03675, 2016.
(3) Temporal network embedding models
CTDNE：G. H. Nguyen, J. B. Lee, R. A. Rossi, N. K. Ahmed, E. Koh, and S. Kim. Continuous-time dynamic network embeddings. In WWW BigNet workshop, 2018.
數據集：
Reddit post dataset：這個公共數據集由用戶在subreddits上發布的一個月的帖子組成。我們選擇了1000個最活躍的子站點作為項目，選擇了10000個最活躍的用戶。這導致672447次交互。我們將每篇文章的文本轉換為表示其LIWC類別的特徵向量。
Wikipedia edits：他的公共數據集是維基百科頁面編輯一個月的編輯數據。選擇編輯次數最多的1000個頁面作為項目和編輯，這些編輯至少以用戶身份進行了5次編輯（總共8227個用戶）。這產生了157474個交互。與Reddit數據集類似，我們將編輯文本轉換為LIWC特徵向量。
LastFM song listens：這個公共數據集有一個月的WhoListen（誰聽哪首歌）資訊。我們選擇了所有1000名用戶和1000首收聽最多的歌曲，產生了1293103次互動。在此數據集中，交互沒有功能。
4.1 Experiment 1: Future interaction prediction
sota見表三
4.2 Experiment 2: User state change prediction
sota見表4
4.3 Experiment 3: Runtime experiment
運行時間見圖4
4.4 Experiment 4: Robustness to the proportion of training data
sota見圖5
4.5 Experiment 5: Embedding size
sota見圖6
Summary
這篇文章的重點是在做用戶和項目之間的預測時，不是直接用用戶的嵌入來做，而是經過一個預測操作後先預測用戶的動態嵌入隨時間的移動結果，在利用這個結果去和項目做預測（項目亦然）。整個論文simple but effective，結構明確，而且適當解釋了為什麼，例如為什麼要用rnn，為什麼要用線性變化的∆，讀下來賞心悅目！
