您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

化繁为简:推荐算法三视角

时间:2019-12-10 10:16:33  来源:  作者:

关于推荐系统,如果在忘掉所有的公式和代码,忘记所有的语言描述,脑海里就剩下几张图景,会是什么?一张二维表格,一个拓扑图,一条时间线。这三幅图景,是我看待推荐算法的三种视角。

视角一:矩阵视角

在脑中想象一个二维的表格,每一行代表一个用户,每一列代表一个物品,表格里的每一个点代表用户对物品的操作,这个操作可以是评分,点击,点赞。其中,有些格子记录了行为,有些格子是空的。到这里,我们就建立了基本的矩阵视角,推荐问题转化成了如何补上那些空格子。

化繁为简:推荐算法三视角

 

用户对物品的评分等于相似用户对该物品评分的加权平均值,这就是user-base的协同过滤了。换一个方向,用户对物品的评分等于该用户对其他物品的评分按物品相似加权平均值,这就是item-base的协同过滤。度量用户之间的相似度,把矩阵的一行——对物品的评分向量作为该用户的表示向量,那么用户之间可以计算向量的距离,可以选择任何距离公式,如余弦距离,皮尔森距离。对于物品之间的相似度,换一个方向即可。

对于任何两个物品,可以计算它们的评分差值。具体来说,两个物品有一批共同的历史评分用户,也就是矩阵里两列有交集的行,每一行可以计算一个差值,将差值平均起来,作为两个物品的距离。和上面的距离不同的,这个差值可以想象成物理中的位移,带着符号的。推荐时,某用户对于某个物品的评分,等于某用户对其他物品评分加上这个位移,再进行平均得到的平均评分。和上面的item-base一样的,都是列向量计算相似度,只不过相似度由距离变成了位移。这就是著名的Slope-One算法。

化繁为简:推荐算法三视角

 

物品直接的相似度,除了上面的启发式算法,能不能通过数据本身学习所得?这就诞生了SLIM(Sparse Linear Methods)方法。矩阵A是n*m评分矩阵,要学习一个n*m维的物品相似的矩阵W。

A的每一行是用户的历史评分,w的每一列是每一个物品和该列对应物品的相似度,计算内积即为该用户对该列物品的评分,通过梯度下降训练来拟合真实评分。其中,w非负体现了相似度的物理意义;对角线限制为0避免对角线全都学习到1完美过拟合;添加L1正则产生稀疏的w,使得结果在大规模物品集上可用;w的每一列的学习都可以看作一个线性回归模型,训练时可以彼此相互独立,因而可以分布式学习。

化繁为简:推荐算法三视角

 

在矩阵视角下,很自然可以进行矩阵分解。SVD矩阵分解将n个用户m个物品的大矩阵分解成三个矩阵相乘,中间的矩阵越靠近左上角的特征值越大,代表矩阵分解的主要成分,也就是说保留左上角的

k*k维矩阵D,其余的都置为零,将原来的等于变为约等于。将蓝色和红色的矩阵合并,得到一个

m*k维的矩阵,每一个行代表一个k维的用户向量,对于黄色矩阵保留其前k行(后面的不影响计算了),每一列代表一个物品向量,用户和物品向量的内积也就是矩阵相乘后对应矩阵的值,也就是空缺处的评分,将向量索引起来就可以推荐了。

化繁为简:推荐算法三视角

 

要使用SVD分解,待分解矩阵要是稠密的,稀疏的评分矩阵要按照统计学方法填充,如填充均值。另外,SVD过拟合现象严重,泛化误差太大。在2006年Netflix Prize的百万推荐大奖赛上, Simon Funk 在博客公开FunkSVD算法。直接将评分矩阵分解成两个矩阵相乘,n*k维度的用户矩阵,每一行是用户的隐式向量表示,k*m维的物品矩阵,每一列是物品的隐式向量表示,用户和物品向量的内积即为预估的评分。那如何进行分解呢?随机初始化矩阵,使用均方误差作为loss,梯度下降进行学习。这个过程中还可以加入正则项,降低泛化误差。由FunkSVD开始,基于Matrix factor(MF)的方法大放异彩。

化繁为简:推荐算法三视角

 


化繁为简:推荐算法三视角

 

在MF的基础上,考虑推荐中的side information,如用户的年龄性别,物品的类目价格。用户和物品自身或属性称作一个field,field之间可以两两进行矩阵分解,这个被称作二阶项,类似BiasSVD考虑每一个field都有一个bias,这个被称作一阶项,再加上一个全局的bias项。这就是著名的Factorization machines(FM)。

化繁为简:推荐算法三视角

 

如果把上面介绍的SLIM和MF解结合起来,将物品的相似度矩阵

W分解成P*Q两个低维矩阵,用户对某物品的评分,等于他过去评分过的物品在P中对应的向量和

Q中该物品向量内积的和,这就是FISM算法。相比SLIM的稀疏处理,变为分解降维。最后再附上一张图,说明MF,SLIM和FISM之间的关系。

化繁为简:推荐算法三视角

 

 

视角二:图视角

把用户和物品看作顶点,用户的评分在用户和物品之间建立起边,就得到了一个二部图;在二部图的基础上添加更多的顶点和边,形成一个更为复杂的图,辅助二部图的计算。在图的视角下,推荐问题转化成了在图上寻找高效的链接模式。

化繁为简:推荐算法三视角

 

 

我们认为在同一个用户的历史行为中,那么两个物品之间有一条边,现在要计算两个物品之间的相似度,最朴素的思想就是数一数他们之间有多少条边。考虑每一条边权重不一样,边是通过用户建立的,用户的点击的物品越多,对应边的权重就越小。这就是Adamic/Adar算法的思想。

阿里著名的协同过滤推荐算法swing,寻找图中更加稳固的形状,共同评分过两个物品的用户集合中,每两个用户和这个两个物品形成了一个四边形(下图红边为一个swing结构),统计有多少个这样的结构,每一个结构的权重是不同的,这个结构里两个用户共同评分过的物品的数量越多权重就越小。

化繁为简:推荐算法三视角

 

从用户和物品的二部图出发进行构图,再结合隐因子模型(Latent Factor Model),就进入了Graph-Embedding的领域。DeepWalk算法在图上随机游走深度优先遍历得到序列,然后和word2vec类似地使用Skip-Gram(A和B序列中相邻,用A的embedding作为特征最大化B的选中概率)进行训练。Node2Vec算法在DeepWalk的基础上,考虑随机游走的方式,引入深度优先和广度优先的权衡,能够得到更好的更灵活的顶点隐式表示。LINE算法考虑顶点的二阶相似,两个顶点有边为一阶相似,两个顶点有共同的邻居顶点为二阶相似,它虽不做随机游走,但可以看作是广度优先的采样。Graph-Embedding取得了顶点的embedding,计算相似度可以得到用户物品距离,物品物品距离,用于推荐。

化繁为简:推荐算法三视角

 

GCN(图卷积)接收拓扑图作为网络输入,可以计算每一个顶点更好的表示,相比graph-embedding可以有监督地为推荐目标而训练。但GCN在运算时,每一层都要输入整个图,在推荐系统里,物品和用户都可以是百万级别以上,实际中无法使用。GraphSAGE通过RandomWalk采样,解决了这个问题,用在推荐领域就是PinSage算法。从某顶点出发,深度优先走k步,得到多个子图,组成一个batch进行训练,。然后按照采样的反方向做前向传播,这就是一个k层的图网络,下图是一个k为2的例子。

化繁为简:推荐算法三视角

 

在用户和物品的二部图基础上,用户和用户根据社会关系建立起边来,这就是社会化推荐。

化繁为简:推荐算法三视角

 

在用户和物品的二部图基础上,增加物品的属性作为顶点,建立新的边,就得到了一个异质信息网络。比如一个电影推荐系统,除了用户和电影外,还有导演,演员,电影类型,导演拍摄电影,电影属于某种类型,演员出演电影,导演与演员合作,诸如此类就能建立很多边。其中一类推荐算法叫做meta-path,通过专家经验人工挑选出一些图中路径,如用户->演员->电影,用户->导演->电影,这样的路径称之为meta-path,计算每一条meta-path的权重,将用户和物品间的所有meta-path联合计算评分。

化繁为简:推荐算法三视角

 

视角三:时间线

把用户对物品的行为想象成一条时间线,我们已知当前时刻前用户的物品行为序列,推荐问题被转化成了预测下一个时刻用户发生行为的物品。

化繁为简:推荐算法三视角

 

假设序列中下一个物品只与上一个物品有关,可以使用马尔科夫模型MC(Markov Chains),序列中相邻的物品间进行矩阵分解。结合上文提到的用户和物品间矩阵分解MF,用户,当前行为物品和下一个物品三者之间两两进行矩阵分解,将三个值加起来拟合评分,就得到了FPMC(Factorizing Personalized Markov Chains)算法。

Translation-based推荐在序列建模中引入Metric Learning(把行为关系和高维空间距离映射起来),用户u,当前行为物品i,下一个物品j三者向量化表示,训练使得它们满足u+i≈j,推荐时只需拿到用户历史行为的物品向量加上用户向量得到下一个物品向量,然后在推荐集合中KNN寻找即可完成推荐。

化繁为简:推荐算法三视角

 

以前模型的输入形式有限,人们通过特征处理将数据组织成模型可以接受的形式;随着深度学习的发展,数据越来越倾向于保存其原有的形式,人们通过模型设计来学习有效的模式。在时间线的视角下,直接用深度模型结构建模序列,预测下一物品,形成了一个可以发挥想象力和燃烧算力的领域——Sequential/Session-base推荐。在2016年的时候,RNN是处理序列问题的标配,它从NLP领域走来,诞生了GRU4Rec算法。受到NLP领域Char-CNN启发,CNN的结构也逐渐用于建模序列结构,Attention机制大火之后,RNN+Attention,CNN+Attention,RNN+CNN+Attention被枚举了一遍。随着google老师的BERT取得NLP领域巨大成就,Self-Attention以及多层的Transformer结构开始成为序列建模的常规配置。最近的文章里,图神经网络(GNN),Memory networks,变分自编码器(VAE)也成为了序列推荐领域的深度乐高积木。

化繁为简:推荐算法三视角

 

在CTR预估领域,越来越多的模型直接将用户历史行为序列按照时间顺序排列,使用深度模型结构直接建模。

总结

其实如果要细数,还有一个视角叫做高维空间视角。用户和物品都是一个高维度空间里的点,空间里点之间的距离越近,代表着物品和物品越相关,用户对物品越偏好,推荐问题转化成了如何将用户和物品嵌入到高维空间里。典型的主题如Metric Learning。不过这个视角的正交性不好,深度学习席卷推荐系统后,embedding是个太常见的思路,前面很多的方法也都是最终把问题转化成了高维空间嵌入,如graph-embedding,Transition-base推荐。为了避免归类上的纠结;再加上任何一个深度网络作为Encoder把用户和物品embedding,都可以归在这个视角,没有那么多令人印象深刻的典型方法,就不做单独梳理了。

To My Best Knowledge,我把自己认为推荐系统里经典且令人印象深刻的方法归在三种视角中——矩阵,图,时间线。本来想谈谈认识的,写着写着写多了,变成了一篇梳理文章。如果对你从偏算法的角度理解推荐系统有所助益,我就很开心了。后面有所学习所得,也会持续更到这篇文章,感兴趣的收藏关注一下吧!



Tags:推荐算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
导读:本文的主题为阿里飞猪推荐算法探索实践,首先会介绍电商背景下主流推荐技术的发展,例如基于全空间的CVR预估技术的发展历程等 ( ESMM / ESM^2 / HM^3 );接着会重点结合旅行...【详细内容】
2021-10-21  Tags: 推荐算法  点击:(56)  评论:(0)  加入收藏
商品详情页是手淘内流量最大的模块之一,它加载了数十亿级商品的详细信息,是用户整个决策过程必不可少的一环。这个区块不仅要承接用户对当前商品充分感知的诉求,同时也要能肩负起其他来源导流流量的留存,最终尽可能地激活...【详细内容】
2021-08-04  Tags: 推荐算法  点击:(89)  评论:(0)  加入收藏
架构头条 作者 | theinsaneapp.com译者 | 张健欣策划 | 万佳今天,我们会讨论一些不同的东西,例如 Spotify、YouTube、Signal Messenger、Amazon 等科技巨头的推荐算法,以及像 U...【详细内容】
2021-07-15  Tags: 推荐算法  点击:(121)  评论:(0)  加入收藏
导读:近年来,电商呈现内容化的趋势,以直播和短视频为首,内容化提升了用户体验,增加了平台收益。作为电商的重要流量入口,推荐算法除了应用于商品,现在也被应用于直播场景。我们将以阿里的B类电商网站1688为例,分享直播推荐相...【详细内容】
2021-04-21  Tags: 推荐算法  点击:(287)  评论:(0)  加入收藏
【写在前面】淘宝搜索引擎至今已经迭代了多轮,搜索排序也已经从最开始的统计模型升级到机器学习模型;2010年前是没有标签概念的就是基础标签这些都没有,随着算力的增强,2010年后...【详细内容】
2020-12-29  Tags: 推荐算法  点击:(222)  评论:(0)  加入收藏
指尖在抖音上划过,满屏幕的颜值少女,满屏幕的乡村野趣,满屏幕的都市传奇,满屏幕的生活乐趣。在碎片化的时间里,我们拿着手机,看着屏上的视频,充满了视觉的欢乐与笑语。手指迅速地划...【详细内容】
2020-09-28  Tags: 推荐算法  点击:(200)  评论:(0)  加入收藏
本次分享的主要内容包括以下三个方面:首先是介绍推荐业务背景,包括推荐产品形态及算法优化目标;然后是算法的演进路线;最后重点介绍在线学习是如何在饿了么推荐领域实践的。...【详细内容】
2020-09-21  Tags: 推荐算法  点击:(88)  评论:(0)  加入收藏
读者读完本文后,你会知道每类范式常用的算法有哪些、实现的思路是什么、以及常用的应用场景。本文也可以作为读者落地推荐算法到真实推荐场景的参考指南。一、推荐算法与产品...【详细内容】
2020-08-31  Tags: 推荐算法  点击:(147)  评论:(0)  加入收藏
近些年,随着深度学习理论,GPU 和 CPU 等计算机硬件,TensorFlow、Caffe、PyTorch 等算法平台的发展,深度学习算法在个性化推荐、计算机视觉、自然语言处理、语音识别等领域大放光...【详细内容】
2020-08-04  Tags: 推荐算法  点击:(53)  评论:(0)  加入收藏
今天,算法分发已经是信息平台、搜索引擎、浏览器、社交软件等几乎所有软件的标配,但同时,算法也开始面临质疑、挑战和误解。今日头条的推荐算法,从2012年9月第一版开发运行至今,...【详细内容】
2020-06-22  Tags: 推荐算法  点击:(66)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条