概述

• 這節課和后面幾節課將詳細講述向量召回，矩陣補充是向量召回最簡單的一種方法，不過現在已經不太常用這種方法了
• 本節課的矩陣補充是為了幫助理解下節課的雙塔模型
• 上節課介紹了embedding，它可以把用戶ID和物品ID映射成向量

矩陣補充

模型結構

• 下面的模型圖是基于embedding做推薦
  
• 模型的輸入是一個用戶ID和一個物品ID，模型的輸出是一個實數，是用戶對物品興趣的預估值，這個數越大，表示用戶對物品越感興趣
• 左邊的結構只有一個embedding層，把一個用戶ID映射成向量，記作向量 a，這個向量是對用戶的表征
• 回憶一下上節課的內容：embedding 的參數是一個矩陣，矩陣中列的數量是用戶數量，每一列都是圖中 a 那么大的向量，embedding 層的參數數量等于用戶數量 × 向量 a 的大小

• 右邊的結構是另一個 embedding 層，把一個物品ID映射到向量，記作 b，大小和向量設置成一樣的，向量 b 是對物品的表征。embedding 層的參數是一個矩陣，輸出的向量 b 是矩陣的一列，矩陣中列的數量是物品的數量
  
• 模型一共用了兩個 embedding 層，它們不共享參數
  
• 對向量 a 和向量 b 求內積得到一個實數作為模型的輸出，這個模型就是矩陣補充模型
  

訓練

基本想法

• 用戶 embedding 參數矩陣記作 $A$。第 $u$ 號用戶對應矩陣第 $u$ 列，記作向量 $a_u$
• 第 $u$ 號用戶對應矩陣的第 $u$ 列，記作向量 $a_u$
  
• 物品 embedding 的參數矩陣記作 $B$。第 $i$ 號物品對應矩陣第 $i$ 列，記作向量 $b_i$
  
• 內積 $<a_u,b_i>$ 是第 $u$ 號用戶對第 $i$ 號物品興趣的預估值，內積越大，說明用戶 $u$ 對物品 $i$ 的興趣越強
• 訓練模型的目的是學習矩陣 $A$ 和 $B$ ，使得預估值擬合真實觀測的興趣分數。矩陣 $A$ 和 $B$ 是 embedding 層的參數

數據集

• 數據集：(用戶ID, 物品ID, 興趣分數) 的集合，記作 $\Omega =\{(u,i,y)\}$ 。含義為該用戶對該物品真實的興趣分數在系統里有記錄
• 數據集中興趣分數的記錄方法如下：
  • 曝光但是沒有點擊 → 0分
  • 點擊，點贊，收藏，轉法 → 各算 1 分，這些行為都說明用戶對物品感興趣
  • 分數最低是 0，最高是 4
• 訓練的目的是讓模型輸出擬合興趣分數

訓練

• 把用戶ID和物品ID映射成向量
  • 第 $u$ 號物品 → 向量 $a_u$
  • 第 $i$ 號物品 → $b_i$
• 求解優化問題，得到參數 $A$ 和 $B$ （它們是優化變量，embedding層的參數）
• 我們希望預估值和真實值的差越小越好，我們對其取平方。差越小，則預估值越接近真實值。對所有差的平方求和，作為優化的目標函數
• 求最小化可以用隨機梯度下降等方法，每次更新矩陣 $A$ 和 $B$ 的一列，這樣就可以學出矩陣 $A$ 和 $B$
  

矩陣補充

• 系統里面物品很多，一個用戶看過的物品只是系統的極少數
  
• 矩陣中大部分都是灰色，只有少部分是綠色，也即曝光給用戶的物品只是少數，而我們并不知道沒曝光給用戶的物品用戶感不感興趣
• 我們用綠色位置的數據去訓練模型，我們就可以知道灰色位置的分數，也就是把矩陣的元素給補全，這就是為什么模型叫矩陣補充
• 把矩陣元素補全之后我們就可以做推薦，給定一個用戶，我們選出對應用戶的行中分數較高的物品推薦給該用戶

在實踐中效果并不好…

• 缺點1：僅使用ID embedding，沒利用物品，用戶屬性
  • 物品屬性：類目，關鍵詞，地理位置，作者信息等等
  • 用戶屬性：性別，年齡，地理定位，感興趣的類目等等
  • 考慮以上的屬性，推薦可以更加精準
  • 雙塔模型可以看作矩陣補充的升級版，它不單單使用用戶ID和物品ID，還會結合各種物品屬性和用戶屬性，雙塔模型的實際表現是非常好的
• 缺點2：負樣本的選取方式不對
  • 樣本：用戶——物品的二元組，記作 $(u,i)$
  • 正樣本：曝光之后，有點擊，交互（正確的做法）
  • 負樣本：曝光之后，沒有點擊，交互（錯誤的做法）。這是一種想當然的做法，學術界的人可能以為這樣沒錯，但可惜在實踐中不 work。后面的課程會講解正負樣本怎么選。
• 缺點3：做訓練的方法不好
  • 內積不如余弦相似度，工業界普遍用余弦相似度而不是內積
  • 用平方損失（回歸）不如用交叉熵損失（分類）。工業界一般做分類來判斷一個樣本是正樣本還是負樣本

線上服務

在訓練好模型后，可以將模型用于推薦系統中的召回通道。比如在用戶刷小紅書的時候，快速找到這個用戶可能感興趣的一兩百篇筆記

模型存儲

做完訓練之后，要把模型存儲在正確的地方便于做召回。

1. 訓練得到矩陣 $A$ 和 $B$ ，它們是 embedding 層的參數。這輛個矩陣可能會很大，比如小紅書有幾億個用戶和幾億篇筆記，那么這幾個矩陣的列數都是好幾億。為了快速讀取和快速查找，需要特殊的存儲方式
   • $A$ 的每一列對應一個用戶
   • $B$ 的每一列對應一個物品
2. 把矩陣 $A$ 的列存儲到 key-value 表。
   • key 是用戶的ID，value 是 $A$ 的一列
   • 給定用戶ID，返回一個向量（用戶的embedding）
3. 矩陣 $B$ 的存儲和索引比較復雜。不能簡單地用 key-value 表

線上服務

在訓練好模型，并且把 embedding 向量做存儲之后，可以開始做線上服務，某用戶刷小紅書的時候，小紅書開始在后臺做召回：

1. 把用戶ID作為 key，查詢 key-value 表，得到該用戶的向量，記作 $a$
2. 最近鄰查找：查找用戶最有可能感興趣的 k 個物品，作為召回結果
   • 第 $i$ 號物品的 embedding 向量記作 $b_i$
   • 內積 $<a,b_i>$ 是對第 $i$ 號物品興趣的預估
   • 返回內積最大的 k 個物品

這種最近鄰查找有一個問題：如果枚舉所有物品，時間復雜度正比于物品數量，這種計算量是不可接受的。比如小紅書有幾億篇筆記，逐一計算向量 $a$ 和每一個向量 $b$ 的內積是不現實的，做不到線上的實時計算

近似最近鄰查找（ANN）

• 有很多種算法加速最近鄰查找，這些算法非常快，即使有幾億個物品也只需要幾萬次內積，這些算法的結果未必是最優的，但是不會比最優結果差多少

• 支持的系統有：Milvus, Faiss, HnswLib等等

• 衡量最近鄰的標準：

  • 歐氏距離最小（L2距離）
  • 向量內積最大（內積相似度）
  • 向量夾角余弦最大（cosine相似度，推薦系統最常用），把所有向量都做歸一化，讓它們的二范數都等于 1，那么此時內積等于余弦相似度

• 如下圖，其中 a 是一個用戶的embedding，我們需要召回用戶感興趣的物品，這就需要計算 a 與所有點的相似度。如果用暴力枚舉，計算量正比于點的數量，即物品的數量

• 想要減少最近鄰的查找的計算量，必須避免暴力枚舉

• 我們在查找之前，先對數據做預處理，對數據進行如下圖的劃分：對于如何劃分取決于最近鄰的標準
  • 如果是余弦相似度，那么劃分結果就是這樣的扇形
  • 如果是歐式距離，那么結果就是多邊形

• 劃分之后，每個區域用一個向量表示，比如下面的藍色區域用那個藍色箭頭的向量表示。黃色區域用圖中黃色的向量表示。
• 這些向量的長度都是 1。
• 劃分之后建立索引，把每個區域的向量作為 key，區域中所有點的表作為 value。給定一個藍色向量，就應該取回藍色扇形中所有的點

• 現在在劃分之后，每個區域都用一個單位向量來表示。那么如果我們劃分成 1w 個區域，索引上就會一共有 1w 個 key 值。每個向量是一個區域的key值

• 給定一個向量，就可以快速取回區域中的所有點。這樣我們就可以快速做召回了
  
• 現在我們要做推薦，給定一個用戶的 embedding 向量 a。我們首先把向量 a 和索引中的向量做對比，計算它們的相似度
• 如果物品數量是幾億，索引中的 key 數量也只有幾萬而已，這一步的計算開銷不大

• 計算相似度之后，我們會發現橙色的向量和 a 最相似
• 通過索引，我們可以找到這個區域內所有的點，每個點對應一個物品
• 接下來計算 a 和區域內所有點的相似度。如果一共有幾億個物品被劃分到了幾萬個區域，平均每個區域只有幾萬個點，所以這一步只需要計算幾萬次相似度，計算量不大

• 假如我們想要找到和向量 a 夾角最小的三個點，那么我們會找到藍色框住的三個點，代表三個物品。這三個物品就是最近鄰查找的結果
• 哪怕有幾億個物品，用這種方法查找，最終也只需要幾萬次查找，比暴力枚舉快 1w 倍

總結