1-3 推薦系統算法與應用.pdf

1、推薦系統算法報告人：連德富 教授郵箱：時間：2022年5月26日1中國科學技術大學 大數據分析與應用安徽省重點實驗室（Anhui Province Key Laboratory of Big Data Analysis and Application,USTC）研究背景及意義2根據學生考試歷史，分析知識掌握狀況，針對性地推薦試題，可以提升學習效率超過10億條商品超過2千萬試題庫 學生考試情況試題推薦海量題庫海量商品庫用戶購買歷史根據用戶購物歷史，分析用戶興趣偏好，個性化地推薦商品，可以滿足用戶需求商品推薦教育場景消費場景信息爆炸時代，信息過載日趨嚴重。個性化推薦是一種解決信息過載的主動信息過濾

2、技術，廣泛應用于教育、醫療、消費、交通、旅游等場景中。研究背景及意義3個性化推薦是智能教育、智能商務等國家迫切需求的重要支撐2017年國務院關于印發新一代人工智能發展規劃的通知指出：“（二）培育高端高效的智能經濟。（二）培育高端高效的智能經濟。個性化需求與定制成為消費新潮流個性化需求與定制成為消費新潮流”“智能智能商務商務 圍繞個人需求提供定制化商務智能決策服務圍繞個人需求提供定制化商務智能決策服務?！薄埃ㄈ┙ㄔO安全便捷的智能社會。圍繞教育等迫切民生需求（三）建設安全便捷的智能社會。圍繞教育等迫切民生需求，為公眾提供個性化為公眾提供個性化、多元化多元化、高品質服務高品質服務?！薄爸悄芙逃悄?/p>

3、教育提供提供精準推送的教育服務精準推送的教育服務，實現日常教育和終身實現日常教育和終身教育定制化教育定制化?！蓖扑]算法入選MIT技術評論十大突破性技術為互聯網信息服務算法推薦立法研究背景及意義4個性化推薦具有重要經濟價值和社會價值2016年網絡視頻點播公司Netflix通過推薦系統和個性化的用戶體驗，每年可以從取消的服務中節省了10億美元2018年天貓雙十一達成2135億元交易，背后產生了453億次AI個性化推薦，使消費者在海量商品中更容易找到真正需要的商品麥肯錫報告：亞馬遜超過35%的營收來自于推薦引擎，線上推薦(on-site recommendation)的銷售轉化率高達60%得益于先進

4、的推薦算法，TikTok全球月活躍用戶高達8億，平均每位用戶每天打開TikTok 8次，總停留時長為52分鐘研究背景及意義5好友推薦廣告推薦餐館推薦商品推薦視頻推薦音樂推薦新聞推薦應用推薦試題推薦論文推薦推薦系統已經普遍成為連接用戶與資源的紐帶推薦系統的發展歷史6線性、人工經驗、靜態92Tapestry94Grouplens97Fab內容過濾協同過濾簡單混合模型9800 01基于物品的協同過濾概率潛在語義分析簡單混合模型0607 08SVD+timeSVD+最大間隔矩陣分解概率矩陣分解貝葉斯矩陣分解1112 1315 隱性反饋 BPR-MF|WRMF結合機器學習的混合模型分解機(FM)SVDF

5、eature,XGBoost13 1617 深度學習模型Wide&DeepDSSM,NFM,DIN,DeepFM,xDeepFMDIEN,Bert4Rec,TDM非線性、自動化、自適應推薦系統的常見數據7點擊加入購物車加入收藏夾點評購買觀看推薦系統的技術體系8曝光、點擊購買、評分推薦正則物品召回推薦采樣推薦損失推薦模型推薦算法線上服務模型壓縮推薦數據推薦系統算法9推薦模型推薦損失推薦采樣推薦正則推薦算法之模型介紹10神經編碼器神經編碼器偏好得分情境向量物品向量物品情境偏好得分物品神經網絡 ,雙塔模型無塔模型為向量相似度函數如內積、歐式距離等情境MFDMFVAECF推薦算法之模型介紹（雙塔模型）

6、11物品序列用戶特征社交網絡知識圖譜物品特征交互數據用戶向量物品向量用戶數據物品數據向量表征偏好預測預測偏好計算損失推薦算法之模型介紹（無塔模型）12交互數據預測偏好計算損失物品序列用戶特征社交網絡知識圖譜物品特征用戶數據物品數據特征交叉非線性映射推薦算法之損失介紹（Softmax 損失）13softmax神經網絡神經網絡情境推薦物品,=exp,=1exp,=logexp,=1exp,最小化負對數似然：取負對數 log 問題：的梯度和損失計算開銷softmax分布推薦算法之損失（Sampled Softmax 損失）14神經網絡神經網絡情境推薦物品,=exp,exp,=logexp,exp,最

7、小化負對數似然：梯度和損失的計算開銷從 降到 采樣物品集Ssoftmax當 =Uniform(1,N)考慮Sampled Softmax的最簡單情形：采樣分布 =Uniform(1,N)問題：采樣分布和softmax分布的差異致梯度估計產生偏差，收斂變慢 =exp,=1exp,softmax分布取負對數 log 推薦算法之損失（BPR 損失）15負樣本采樣神經網絡神經網絡情境推薦物品,Uniform 1,優化目標：盡可能,=log ,最小化成對排序損失：問題：采樣分布簡單導致收斂慢推薦算法之損失對比損失名稱函數形式采樣分布計算(采樣)復雜度收斂速度指標關系Softmaxlogexp,=1exp

8、,不采樣()-快DCGSampled softmaxlogexp,log exp,log 均勻采樣流行度采樣(1)較快DCGBPRlog ,均勻采樣 1(1)慢AUCWARP 11 ,+,+拒絕采樣 1越來越慢慢PrecisionInfoNCElogexp,exp,流行度采樣 1較快DCGWRMF,2不采樣()-快無PRISexp,log exp,log log ,聚類采樣 快DCG16推薦算法之采樣 挑戰：難以直接從 中采樣 建表 建立概率表的時間是()，N為物品數 采樣 如果直接采樣，采樣n個樣本的時間復雜度是O 如果先建立別名表，再采樣n個樣本，時間復雜度是 +17核心難題：如何從 =e

9、xp,=1exp,高效采樣，以加快收斂速度呢？解決方案：設計采樣分布 使之盡可能接近softmax分布 推薦算法之采樣18 直接從中采樣：重要性重采樣用簡單分布來近似+糾偏 基于量化的采樣直接近似softmax分布解決方案：設計采樣分布 使之盡可能接近softmax分布 推薦算法之采樣重要性重采樣 重要性采樣不是采樣，是期望的估計技術 通過重要性重采樣，將其變成采樣過程19 從 采樣出L個樣本1,通過=exp,ln|=1exp,ln|計算每個樣本的權重 從離散分布 1,中重采樣L個樣本，每個樣本被采樣的概率為 1,采樣均勻分布加權采樣定理：當 ，重要性重采樣等價于從 =exp,exp,分布中采

10、樣Jin Chen,Defu Lian*,Binbin Jin,Kai Zheng and Enhong Chen.Learning Recommenders for Implicit Feedback with Importance Resampling.WWW 2022.推薦算法之采樣基于量化的精確采樣20 =exp,exp,=12+1第一子空間的聚類中心2第二子空間的聚類中心=exp,12+exp,12+=112213 1,211=1exp1,11exp1,112假設,=,221=1,2exp 2,221,exp 2,23 1,2=exp,1,2exp,1,21該假設在深度學習具有普遍性

11、在第一個子空間選中聚類1在第二個子空間選中聚類2在聚類1和2的交集1,2選中Jin Chen,Defu Lian*,Binbin Jin,Xu Huang,Kai Zheng and Enhong Chen.Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering.WWW 2022.推薦算法之采樣基于量化的近似采樣21 =112213 1,211=1exp1,11exp1,1在第一個子空間選中聚類1推薦算法之采樣基于量化的近似采樣22 =112213 1,211=1exp1,11exp1

12、,1在第一個子空間選中聚類1221=1,2exp 2,221,exp 2,21在第二個子空間選中聚類2推薦算法之采樣基于量化的近似采樣23 =112213 1,2均勻分布 =exp,12exp,12假設第三階段只用均勻采樣11=1exp1,11exp1,1在第一個子空間選中聚類1221=1,2exp 2,221,exp 2,21在第二個子空間選中聚類23 1,2=11,21在聚類1和2的交集1,2選中1,2推薦算法之采樣基于量化的近似采樣24 隨機初始化模型的量化采樣和靜態采樣一致 量化采樣采出物品的頻率分布和softmax分布最接近 隨著模型訓練，采樣分布從靜態分布到近似softmax分布演

13、化結論推薦算法之采樣基于量化的近似采樣25深藍：橙色：灰色：黃色：綠色：淺藍：靜態采樣不采樣量化采樣核近似采樣 量化采樣方法的采樣效果遠勝于靜態采樣 量化采樣方法的采樣效果接近于不采樣結果結論推薦算法之采樣基于量化的近似采樣26 量化采樣和靜態采樣在訓練效率上沒有數量級差異 量化采樣比不采樣方法能提升2-8倍加速 物品數越多，加速越多結論推薦線上服務27候選生成排序第一階段第二階段數百數十模型召回模型精排模型所有物品數百萬線上服務之召回模型（精確結果）281D數據庫,1Top-K計算偏好user 1user item 1item item user 時間復雜度Top-K:,D查詢向量,=,：最

14、大內積搜索,=;：最大函數搜索,=：最近鄰搜索線上服務之召回模型（近似結果）291D查詢向量數據庫user 1user item 1item item user 時間復雜度次線性,=,：最大內積搜索,=;：最大函數搜索,=：最近鄰搜索DHNSWPQTree線上服務之召回模型（可學習索引）30用戶1用戶物品1物品物品用戶提出方法：端到端構建法傳統方法物品 1物品 物品 1212內積：=11+221.學習用戶和物品向量表征2.針對物品向量表征構建索引從原始數據中學習索引同時學習向量表示和構建索引向量表征和索引構建獨立 索引度量和偏好函數不一致技術問題兩階段法研究挑戰 索引構建可能不可微 大離散空間

15、的組合優化線上服務之召回模型（可學習哈希）31用戶-物品交互矩陣-1-11-11111111-11-1-1-111-1-1-1-1-1-1-1-111-1-1-1-1-111-11-1-1-1物品1物品 用戶1用戶用戶 物品1物品 物品 用戶1用戶用戶 二值向量表示坐標塊=2,=,+,2s.t.1,1基于二值二次規劃，提出了塊坐標下降法，以概率搜索漢明距離為k 內的參數，解決了傳統離散坐標下降法只搜索漢明距離為1 內的參數的問題主要貢獻物品 Defu Lian,Xing Xie,Enhong Chen.Discrete Matrix Factorization and Extension fo

16、r Fast Item Recommendation.IEEE Transaction on Knowledge and Data Engineering(TKDE),2019二值矩陣分解線上服務之召回模型（可學習哈希）坐標下降法與塊坐標下降的聯系32Defu Lian,Xing Xie,Enhong Chen.Discrete Matrix Factorization and Extension for Fast Item Recommendation.IEEE Transaction on Knowledge and Data Engineering(TKDE),2019 當塊大小為1時，

17、塊坐標下降和離散坐標下降等價 當塊大小大于1時，離散坐標下降 劣于 塊坐標下降 塊數增加不一定意味召回率提升，因為優化目標和召回率并不一致結論線上服務之召回模型（可學習量化）33隱向量優化目標=,2+,2=Defu Lian,Xing Xie,Enhong Chen and Hui Xiong.Product Quantized Collaborative Filtering.IEEE Transaction on Knowledge and Data Engineering(TKDE),2020建立查找表量化矩陣分解線上服務之召回模型（可學習量化）34Defu Lian,Xing Xie,E

18、nhong Chen and Hui Xiong.Product Quantized Collaborative Filtering.IEEE Transaction on Knowledge and Data Engineering(TKDE),2020 同樣加速比上可學習量化方法優于可學習哈希 可學習量化比工業搜索庫ANNOY的召回精度更高結論線上服務之召回模型（可學習量化）35物品向量 被近似為:=1 保證前向onehot,后向可微 STE：=+stop_gradient()=exp ,/exp ,/Defu Lian,Haoyu Wang,Zheng Liu,Jianxun Lian,

19、Enhong Chen and Xing Xie.LightRec:a Memory and Search-Efficient Recommender System.WWW 2020端到端深度量化線上服務之召回模型（可學習量化）36 新算法能更準確地召回用戶可能感興趣的物品；端到端的索引構建優于兩階段法；循環碼書學習機制可以顯著提升碼書的質量結論Defu Lian,Haoyu Wang,Zheng Liu,Jianxun Lian,Enhong Chen and Xing Xie.LightRec:a Memory and Search-Efficient Recommender System

20、.WWW 2020線上服務之精排模型壓縮37方法組成模塊內存估算（MB）FM一階權重，表示向量1986Wide&Deep表示向量，MLP網絡1995DSSM表示向量，MLP網絡1974DeepFM一階權重，表示向量，MLP網絡2011以Avazu數據集為例：CTR預估任務，包含21類特征，共2M個特征，每個特征用128向量表示，參數類型取float64實際CTR預估場景中，特征數可能過億，精排模型的大小約為100GB。電商場景10億特征情形，模型大小接近1TB。特征Embedding占據其中絕多數對特征Embedding的壓縮尤為重要線上服務之精排模型壓縮（xLightFM）38 FM 模型

21、=0+=1+=1=+1,量化FM模型 =0+=1+=1=+1,線上服務之精排模型壓縮（xLightFM）量化FM模型 =0+=1+=1=+1,研究問題 對特征的量化需要構建多組碼本來分別建模 例子：年齡(1-100)和男女(0,1)需要的聚類中心數不同39搜索空間搜索策略采用AutoML解決線上服務之精排模型壓縮（xLightFM）40 新算法能更準確地建模用戶特征間的交互；算法能夠節省20X的內存開銷；結論線上服務之精排模型壓縮（LISA）自注意力 簡單案例(和使用長度為的代替)41is(2)平方量級的計算和存儲開銷Yongji Wu,Defu Lian*,Neil Gong,Lu Yin,

22、Mingyang Yin,Jingren Zhou and Hongxia Yang.Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation.WWW 2021Attention,=softmax=1exp=1exp 線上服務之精排模型壓縮（LISA）自注意力 簡單案例(和使用長度為的代替)42is(2)平方量級的計算和存儲開銷Yongji Wu,Defu Lian*,Neil Gong,Lu Yin,Mingyang Yin,Jingren Zhou and Hongxia Yang.Lin

23、ear-Time Self Attention with Codeword Histogram for Efficient Recommendation.WWW 2021Attention,=softmax=1exp=1exp 對 量化=exp exp =1exp=1exp 僅需要計算與存儲 與每個碼字的乘積線上服務之精排模型壓縮（LISA）擴展到多碼本43計算和存儲效率：022010330113212310301200sequence (codew ord i ndi ces)codew ord hi stogram s=1exp=1=1=1exp=1近似為=1=1exp=1exp=1=1e

24、xp=1exp 可以視為 multi-head attention僅需要計算與存儲codeword出現的頻次，存儲消耗僅為(2)碼本1碼本2碼本3碼本4022010330113212310301200sequence (codew ord i ndi ces)codew ord hi stogram s序列序列第二位物品在第二個碼本中的碼字編號為2碼本2碼本4碼本3直方圖線上服務之精排模型壓縮（LISA）44 新算法能更準確地召回用戶可能感興趣的物品；算法能夠有效的對Self-Attention計算和內存開銷進行節??；結論存儲開銷推薦算法庫RecStudio45第一個高度模塊化的推薦算法庫，可以通過搭積木的方式實現舊算法、搭建新模型將所有推薦算法分為 排序模型 召回模型兩類模型從推薦算法分離出 打分 損失 采樣 搜索共性模塊根據推薦任務將數據集分為：MF、AE、Seq、ALS等數據集https:/ YOU!安徽大數據應用協同創新中心首旅生活方式智慧服務實驗室中國科大智慧城市研究院（蕪湖）智慧醫療大數據研究中心大數據分析與應用安徽省重點實驗室（Anhui Province Key Laboratory of Big Data Analysis and Application）http:/