1、推荐系统算法报告人：连德富 教授邮箱：时间：2022年5月26日1中国科学技术大学 大数据分析与应用安徽省重点实验室（Anhui Province Key Laboratory of Big Data Analysis and Application,USTC）研究背景及意义2根据学生考试历史，分析知识掌握状况，针对性地推荐试题，可以提升学习效率超过10亿条商品超过2千万试题库 学生考试情况试题推荐海量题库海量商品库用户购买历史根据用户购物历史，分析用户兴趣偏好，个性化地推荐商品，可以满足用户需求商品推荐教育场景消费场景信息爆炸时代，信息过载日趋严重。个性化推荐是一种解决信息过载的主动信息过滤

2、技术，广泛应用于教育、医疗、消费、交通、旅游等场景中。研究背景及意义3个性化推荐是智能教育、智能商务等国家迫切需求的重要支撑2017年国务院关于印发新一代人工智能发展规划的通知指出：“（二）培育高端高效的智能经济。（二）培育高端高效的智能经济。个性化需求与定制成为消费新潮流个性化需求与定制成为消费新潮流”“智能智能商务商务 围绕个人需求提供定制化商务智能决策服务围绕个人需求提供定制化商务智能决策服务。”“（三）建设安全便捷的智能社会。围绕教育等迫切民生需求（三）建设安全便捷的智能社会。围绕教育等迫切民生需求，为公众提供个性化为公众提供个性化、多元化多元化、高品质服务高品质服务。”“智能教育智能

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计算和存储效率：0220310301200sequence (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码本40220310301200sequence (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:/