-
2018-03-30 23:07:56
一. 背景
负责信息流推荐系统后台算法的工作也有一段时间,从零开始构建推荐系统的过程中,在总结了业界一些成功的经验的同时,也摸索了一些有效的实践方法。愿在此沉淀,通过交流扩展眼界。推荐系统重在算法,这也是各大公司算法团队不断追新与实践的过程。无奈个人能力有限,团队人力有限,只能一步一步从基础做起。本文将主要介绍信息流视频推荐算法的应用和探索。
二. 算法架构
- 召回算法:包含了多个渠道的召回模型,比如协同过滤,主题模型,内容召回和热点召回等渠道,能够从视频库中选出多样性的偏好内容。
- 排序算法:对多个召回渠道的内容进行统一打分排序,选出最优的少量结果。
三. 技术细节
1. 召回算法(match)
基于用户行为的match
以下召回算法,包括尝试算法,和最终线上用的算法。这里为了扩展思路,都列举了出来
离线cf(ALS)召回
(1) 根据用户行为日志,利用基于ItemBased的协同过滤生成离线的item2item相似度矩阵和用户的离线推荐结果,其中优化过程包括基于艾宾浩斯遗忘曲线按照时间进行降权、弱化热点影片的权重以及矩阵分解;
(2) 线上服务端基于用户的playlog接口实时获取用户的短时间内的观看历史,通过item相似度矩阵进行CF扩散,提取出与用户短时间内观看历史相似的topN个item用于召回;
(2) 用户的CF离线推荐结果直接作为线上服务的召回渠道之一。w2v召回
(1) 根据用户行为,将全部影片作为语料库,每个用户的观看历史按时序排序视为文档,利用w2v算法原理计算所有item的词向量;
(2) 根据词向量距离计算item2item的相似度矩阵,用于线上playlog召回数据;lda召回
(1) 基于概率主题模型:文档 – 潜在主题 – 词 的三级关系,映射到用户行为数据上,即用户 – 潜在兴趣 – 资源;
(2) 通过用户历史行为记录,提取LDA的中间产物,及用户的潜在兴趣向量,以及资源的潜在主提分布向量;
(3) 基于item的主题向量,进行item2item的相似度计算,用于线上playlog召回数据;SimRank召回
将user与deal的关系视作一个二部图,基于graph-based算法相似关系可以在图上传播的思想,使用simrank计算Item相似队列
基于内容的match
基于title简介召回
(1) 基于影片的文本简介部分使用doc2vector,计算出每个资源的表示向量;
(2) 基于资源的向量,进行item2item的相似度计算。基于style(风格)召回
基于tag(标签)召回
EE问题 & 冷启问题
冷启用户召回
(1) 根据imbd算法,计算资源得分,根据不同时间周期进行得分融合并线上进行ab对比,选取最优的时间周期组合;
(2) 按照imdb得分进行倒排,生成热点召回数据冷启资源召回
基于资源库,统计各个资源的点击和播放率,按一定比例召回点击/播放率低的item
EE问题(Exploration and Exploitation tradeoff)
目前暂没有引入线上强化学习,只采用调整不同召回渠道的配比方式来保证一定的多样性。
2. 排序算法(rank)
基础模型
线上baseline模型是lr逻辑回归。该模型的优势在于简单,解释性强,并行化程度高,线上做实时预测,基本的性能问题可以得到保证;但是,从模型效果上来讲,需要做大量的人工的特征组合,特征两两作Interaction 的情况下,模型预测复杂度高,三个以上的特征进行Interaction 几乎是不可行的。
特征工程
特征分类
按特征的基本来源分类
- Item特征:资源风格、地域、类型、标签、以及相应的统计特征等
- User特征:性别、年龄、婚姻状况、收入预测等
- Context特征:网络状态、时间段、城市等
- 交叉特征:基于User基本特征和Item\Context的交叉特征
按特征的更新频率以及获取方式分类
- 离线特征:一段时间变化幅度小的特征,如user/item的基本特征和统计特征
- 近在线特征:分钟级/小时级需要更新的特征,如item近4个小时的ctr等
- 在线特征:需要在每次请求到达时,实时获取的特征,如网络状态、当前请求时间等
特征处理
特征扩充
(1) 用户兴趣向量:lda的中间产物之一用户潜在兴趣向量,以及基于w2v的词向量和用户行为历史统计出的用户兴趣向量,可丰富用户维度上的兴趣特征。
(2) 资源embedding向量:基于用户行为数据进行的embedding的w2v/lda的词向量,以及基于资源本身title的doc2vector都可丰富最近模型使用的特征维度。且word2vecor和lda由于原理上的区别,可拓展出不同意义上的特征向量。
(3) 资源封面AutoEncode向量:基于资源封面图像,离线采用AutoEncode训练,提取隐层向量,作为资源本身特征。统计特征细化
(1) 特征工程时间窗口细化: 将资源的统计特征,按不同的时间窗口,如1,3,5,7,15天进行特征细化,可在丰富资源特征的同时,融入时间衰减的因素。
(2) 在线特征交叉:对于一些资源统计特征,在与用户特征以及上下文特征进行交叉之后效果会更加明显,根本原因在于增加了样本特征的区分度;具体交叉方法的落地,建议由服务端是执行,这里比如一个男性用户发来请求,服务端可实时获取用户的性别特征(男)以及召回队列中每个资源的在不同性别上统计特征(如历史CTR),基于特征编码表,新增加交叉特征(sex_cross_ctr),并将每个资源在男性上的ctr上作为新增交叉特征的特征值,记录成log,后面回流给模型样本。其实所有的在线特征都和交叉特征一样,最后都由服务端的日志回流给模型训练过程。连续特征离散化 & 统一独热编码
(1) 这里先引出美团连续特征归一化的方法
当然,它归一化和这里离散化的方法的考虑点几乎一致。即由于不同维度特征的取值分布、相同维度下特征值的差异都很大。如很多特征的数据服从长尾分布。直接基于该特征进行常规的归一化方法(例如 min-max, z-score)都只是对数据的分布进行平移和拉伸,最后特征的分布仍然是长尾分布,这就导致大部分样本的特征值都集中在非常小的取值范围内,使得样本特征的区分度减小;与此同时,少量的大值特征可能造成训练时的波动,减缓收敛速度。此外也可以对特征值做对数转化,但由于不同维度间特征的分布不同,这种特征值处理的方式并不一定适用于其他维度的特征。
(2) 考虑到LR模型的特性,这里的方法是先对连续特征先进行等频离散化,即基于特征值的频率等频分成N个桶,并做0/1标识,最后和离散型特征,统一进行One-hot编码,喂给LR模型。这样做的具体优势知乎有一定交流,实践过程中也确实如此。
采样策略
负样本采样策略调整
基于曝光时间showtime和曝光顺序order,过滤负样本。
不平衡样本策略调整
离线进行A/B测试不同正负样本比例,进行择优调整(如1:5)
四. 模型探索
1. 召回算法探索
- 可以利用RNN来“捕捉”用户在点击序列中的模式,即利用用户点击行为发生先后顺序进行推荐的展示排序。
- Graph embedding算法,具体实践经验可见阿里
2. 排序算法探索
非线性模型
(1) GBDT+LR:
GBDT是基于Boosting 思想的ensemble模型,由多颗决策树组成,具有以下优点:
- 对输入特征的分布没有要求;
- 根据熵增益自动进行特征转换、特征组合、特征选择和离散化,得到高维的组合特征,省去了人工转换的过程,并且支持了多个特征的Interaction;
- 预测复杂度与特征个数无关。
GBDT与LR的进行stacking可以一定程度防止GBDT过拟合。且升级为GBDT+LR可因为省去了对新特征进行人工转换的步骤,增加特征的迭代测试也相对容易。但是需要注意对于所有LR模型所有特征都进行离散化,出来的特征值全部非0即1。但是GBDT本来就是树模型,能很好的处理非线性特征,使用离散化后的特征效果可能不佳。而且对于这种只有0、1值的情况,GBDT可能出现了不收敛的现象。所以喂给GBDT的特征不建议进行没有必要的离散化。
(2) GBDT+FM:
- GBDT+LR排序模型中输入特征维度为几百维,都是稠密的通用特征;
- 这种特征的泛化能力良好,但是记忆能力比较差,所以需要增加高维的(百万维以上)内容特征来增强推荐的记忆能力,包括视频ID,标签,主题等特征。
- GBDT是不支持高维稀疏特征的,如果将高维特征加到LR中,一方面需要人工组合高维特征,另一方面模型维度和计算复杂度会是O(N^2)级别的增长。可采用Factorization Machines模型替换LR。FM能够自动对特征进行交叉组合、增加隐向量使得模型训练和预测的计算复杂度降为O(N)、支持稀疏特征这几个优点,FM使用GBDT(稠密特征)的叶子结点和稀疏特征(内容特征)作为输入。
- 如果优化算法可以选择的话,建议FTRL,它较SGD有以下优势:带有L1正则使得学习的特征更加稀疏、使用累计的梯度加速收敛、根据特征在样本的出现频率确定该特征学习率,保证每个特征有充分的学习。FM模型中的特征出现的频次相差很大,FTRL能够保证每个特征都能得到充分的学习,更适合稀疏特征。
(3) DNN+GBDT+FM:
GBDT+FM模型,对embedding等具有结构信息的深度特征利用不充分,而深度学习(Deep Neural Network)能够对嵌入式(embedding)特征和普通稠密特征进行学习,抽取出深层信息,提高模型的准确性。- DNN+GBDT+FM的ensemble模型FM层作为模型的最后一层,即融合层,其输入由三部分组成:DNN的最后一层隐藏层、GBDT的输出叶子节点、高维稀疏特征。
- DNN模型:(a)使用全连接网络,设置N个隐藏层。(b)预训练好的用户和视频的Embedding向量,包含基于用户行为以及基于语义内容等的多种Embedding,防止隐层不够,训练不足。(c)DNN能从具有良好数学分布的特征中抽取深层信息,比如embedding特征,归一化后统计特征等等。
- GBDT模型: (a)单独进行训练,输入包含归一化和未归一化的稠密特征(b)能处理未归一化的连续和离散特征。(c)能根据熵增益自动对输入特征进行离散和组合。
- FM融合层:(a)FM模型与DNN模型作为同一个网络同时训练。(b)将DNN特征,GBDT输出和稀疏特征进行融合并交叉
组合不同的目标函数
考虑融合点击和播放时长不同性质的目标函数,进行模型训练:(a)可独立成不同的模型进行训练。(b) 亦可不同的模型共享一定的深度隐层,最后在全连接层进行独立分割。最后在线上预测时对不同性质的模型,进行线性加权。
3. EE&冷启问题探索
- 常用Bandit算法(累积遗憾->评估效果)
- Thompson sampling算法
- UCB算法
- Epsilon-Greedy算法
- 朴素Bandit算法
- LinUCB(UCB算法加入特征信息)
- COFIBA算法(Bandit和协同过滤结合)
五. 总结展望
按照目前主流的算法架构 match + rank,不难发现match召回算法最终决定了推荐效果的上界,而rank层的排序是更加保证了推荐结果的精准。所以从模型优化的角度来讲,只有保证match 和 rank 双管齐下,才能发挥推荐系统的终极效果。match趋近个性化、召回度和新颖度的完美结合,rank层趋近排序结果的精准化,无疑对于算法工程师来说,都是极大的挑战。最后引出阿里在match层最新的探索,以及美团在rank层的最近进展。
更多相关内容 -
数据挖掘算法原理与实现(第2版).王振武(带详细书签).pdf
2018-05-12 23:49:523.2关联规则挖掘算法——Apriori算法原理 36 3.3Apriori算法实例分析 38 3.4Apriori算法源程序分析 41 3.5Apriori算法的特点及应用 50 3.5.1Apriori算法特点 50 3.5.2Apriori 算法应用 51 3.6小结 52 思考题 52 第4... -
推荐算法原理
2019-03-26 13:40:57资讯推荐系统本子上要解决用户,环境和咨询的匹配: y = F(x1c, x2e, x3u) / 是否合适 模型之后再看一下典型的推荐特征,主要有四类特征会对推荐起到比较重要的作用。 第一类是相关性特征,就是评估内容的...资讯推荐系统本子上要解决用户,环境和咨询的匹配:
y = F(x1c, x2e, x3u) / 是否合适模型之后再看一下典型的推荐特征,主要有四类特征会对推荐起到比较重要的作用。
第一类是相关性特征,就是评估内容的属性和与用户是否匹配。显性的匹配包括关键词匹配、分类匹配、来源匹配、主题匹配等。像FM模型中也有一些隐性匹配,从用户向量与内容向量的距离可以得出。
第二类是环境特征,包括地理位置、时间。这些既是bias特征,也能以此构建一些匹配特征。
第三类是热度特征。包括全局热度、分类热度,主题热度,以及关键词热度等。内容热度信息在大的推荐系统特别在用户冷启动的时候非常有效。
第四类是协同特征,它可以在部分程度上帮助解决所谓算法越推越窄的问题。协同特征并非考虑用户已有历史。而是通过用户行为分析不同用户间相似性,比如点击相似、兴趣分类相似、主题相似、兴趣词相似,甚至向量相似,从而扩展模型的探索能力。
曹欢欢关于《今日头条算法原理》的分享内容:
本次分享将主要介绍今日头条推荐系统概览以及内容分析、用户标签、评估分析,内容安全等原理。
一、系统概览
推荐系统,如果用形式化的方式去描述实际上是拟合一个用户对内容满意度的函数,这个函数需要输入三个维度的变量。
第一个维度是内容。头条现在已经是一个综合内容平台,图文、视频、UGC小视频、问答、微头条,每种内容有很多自己的特征,需要考虑怎样提取不同内容类型的特征做好推荐。第二个维度是用户特征。包括各种兴趣标签,职业、年龄、性别等,还有很多模型刻划出的隐式用户兴趣等。第三个维度是环境特征。这是移动互联网时代推荐的特点,用户随时随地移动,在工作场合、通勤、旅游等不同的场景,信息偏好有所偏移。
结合三方面的维度,模型会给出一个预估,即推测推荐内容在这一场景下对这一用户是否合适。
这里还有一个问题,如何引入无法直接衡量的目标?
推荐模型中,点击率、阅读时间、点赞、评论、转发包括点赞都是可以量化的目标,能够用模型直接拟合做预估,看线上提升情况可以知道做的好不好。但一个大体量的推荐系统,服务用户众多,不能完全由指标评估,引入数据指标以外的要素也很重要。
比如广告和特型内容频控。像问答卡片就是比较特殊的内容形式,其推荐的目标不完全是让用户浏览,还要考虑吸引用户回答为社区贡献内容。这些内容和普通内容如何混排,怎样控制频控都需要考虑。
此外,平台出于内容生态和社会责任的考量,像低俗内容的打压,标题党、低质内容的打压,重要新闻的置顶、加权、强插,低级别账号内容降权都是算法本身无法完成,需要进一步对内容进行干预。
下面我将简单介绍在上述算法目标的基础上如何对其实现。
前面提到的公式y = F(Xi ,Xu ,Xc),是一个很经典的监督学习问题。可实现的方法有很多,比如传统的协同过滤模型,监督学习算法Logistic Regression模型,基于深度学习的模型,Factorization Machine和GBDT等。
一个优秀的工业级推荐系统需要非常灵活的算法实验平台,可以支持多种算法组合,包括模型结构调整。因为很难有一套通用的模型架构适用于所有的推荐场景。现在很流行将LR和DNN结合,前几年Facebook也将LR和GBDT算法做结合。今日头条旗下几款产品都在沿用同一套强大的算法推荐系统,但根据业务场景不同,模型架构会有所调整。
模型之后再看一下典型的推荐特征,主要有四类特征会对推荐起到比较重要的作用。
第一类是相关性特征,就是评估内容的属性和与用户是否匹配。显性的匹配包括关键词匹配、分类匹配、来源匹配、主题匹配等。像FM模型中也有一些隐性匹配,从用户向量与内容向量的距离可以得出。
第二类是环境特征,包括地理位置、时间。这些既是bias特征,也能以此构建一些匹配特征。
第三类是热度特征。包括全局热度、分类热度,主题热度,以及关键词热度等。内容热度信息在大的推荐系统特别在用户冷启动的时候非常有效。
第四类是协同特征,它可以在部分程度上帮助解决所谓算法越推越窄的问题。协同特征并非考虑用户已有历史。而是通过用户行为分析不同用户间相似性,比如点击相似、兴趣分类相似、主题相似、兴趣词相似,甚至向量相似,从而扩展模型的探索能力。
模型的训练上,头条系大部分推荐产品采用实时训练。实时训练省资源并且反馈快,这对信息流产品非常重要。用户需要行为信息可以被模型快速捕捉并反馈至下一刷的推荐效果。我们线上目前基于storm集群实时处理样本数据,包括点击、展现、收藏、分享等动作类型。模型参数服务器是内部开发的一套高性能的系统,因为头条数据规模增长太快,类似的开源系统稳定性和性能无法满足,而我们自研的系统底层做了很多针对性的优化,提供了完善运维工具,更适配现有的业务场景。
目前,头条的推荐算法模型在世界范围内也是比较大的,包含几百亿原始特征和数十亿向量特征。整体的训练过程是线上服务器记录实时特征,导入到Kafka文件队列中,然后进一步导入Storm集群消费Kafka数据,客户端回传推荐的label构造训练样本,随后根据最新样本进行在线训练更新模型参数,最终线上模型得到更新。这个过程中主要的延迟在用户的动作反馈延时,因为文章推荐后用户不一定马上看,不考虑这部分时间,整个系统是几乎实时的。
但因为头条目前的内容量非常大,加上小视频内容有千万级别,推荐系统不可能所有内容全部由模型预估。所以需要设计一些召回策略,每次推荐时从海量内容中筛选出千级别的内容库。召回策略最重要的要求是性能要极致,一般超时不能超过50毫秒。
召回策略种类有很多,我们主要用的是倒排的思路。离线维护一个倒排,这个倒排的key可以是分类,topic,实体,来源等,排序考虑热度、新鲜度、动作等。线上召回可以迅速从倒排中根据用户兴趣标签对内容做截断,高效的从很大的内容库中筛选比较靠谱的一小部分内容。
二、内容分析
内容分析包括文本分析,图片分析和视频分析。头条一开始主要做资讯,今天我们主要讲一下文本分析。文本分析在推荐系统中一个很重要的作用是用户兴趣建模。没有内容及文本标签,无法得到用户兴趣标签。举个例子,只有知道文章标签是互联网,用户看了互联网标签的文章,才能知道用户有互联网标签,其他关键词也一样。
另一方面,文本内容的标签可以直接帮助推荐特征,比如魅族的内容可以推荐给关注魅族的用户,这是用户标签的匹配。如果某段时间推荐主频道效果不理想,出现推荐窄化,用户会发现到具体的频道推荐(如科技、体育、娱乐、军事等)中阅读后,再回主feed,推荐效果会更好。因为整个模型是打通的,子频道探索空间较小,更容易满足用户需求。只通过单一信道反馈提高推荐准确率难度会比较大,子频道做的好很重要。而这也需要好的内容分析。
上图是今日头条的一个实际文本case。可以看到,这篇文章有分类、关键词、topic、实体词等文本特征。当然不是没有文本特征,推荐系统就不能工作,推荐系统最早期应用在Amazon,甚至沃尔玛时代就有,包括Netfilx做视频推荐也没有文本特征直接协同过滤推荐。但对资讯类产品而言,大部分是消费当天内容,没有文本特征新内容冷启动非常困难,协同类特征无法解决文章冷启动问题。
今日头条推荐系统主要抽取的文本特征包括以下几类。首先是语义标签类特征,显式为文章打上语义标签。这部分标签是由人定义的特征,每个标签有明确的意义,标签体系是预定义的。此外还有隐式语义特征,主要是topic特征和关键词特征,其中topic特征是对于词概率分布的描述,无明确意义;而关键词特征会基于一些统一特征描述,无明确集合。
另外文本相似度特征也非常重要。在头条,曾经用户反馈最大的问题之一就是为什么总推荐重复的内容。这个问题的难点在于,每个人对重复的定义不一样。举个例子,有人觉得这篇讲皇马和巴萨的文章,昨天已经看过类似内容,今天还说这两个队那就是重复。但对于一个重度球迷而言,尤其是巴萨的球迷,恨不得所有报道都看一遍。解决这一问题需要根据判断相似文章的主题、行文、主体等内容,根据这些特征做线上策略。
同样,还有时空特征,分析内容的发生地点以及时效性。比如武汉限行的事情推给北京用户可能就没有意义。最后还要考虑质量相关特征,判断内容是否低俗,色情,是否是软文,鸡汤?
上图是头条语义标签的特征和使用场景。他们之间层级不同,要求不同。
分类的目标是覆盖全面,希望每篇内容每段视频都有分类;而实体体系要求精准,相同名字或内容要能明确区分究竟指代哪一个人或物,但不用覆盖很全。概念体系则负责解决比较精确又属于抽象概念的语义。这是我们最初的分类,实践中发现分类和概念在技术上能互用,后来统一用了一套技术架构。
目前,隐式语义特征已经可以很好的帮助推荐,而语义标签需要持续标注,新名词新概念不断出现,标注也要不断迭代。其做好的难度和资源投入要远大于隐式语义特征,那为什么还需要语义标签?有一些产品上的需要,比如频道需要有明确定义的分类内容和容易理解的文本标签体系。语义标签的效果是检查一个公司NLP技术水平的试金石。
今日头条推荐系统的线上分类采用典型的层次化文本分类算法。最上面Root,下面第一层的分类是像科技、体育、财经、娱乐,体育这样的大类,再下面细分足球、篮球、乒乓球、网球、田径、游泳...,足球再细分国际足球、中国足球,中国足球又细分中甲、中超、国家队...,相比单独的分类器,利用层次化文本分类算法能更好地解决数据倾斜的问题。有一些例外是,如果要提高召回,可以看到我们连接了一些飞线。这套架构通用,但根据不同的问题难度,每个元分类器可以异构,像有些分类SVM效果很好,有些要结合CNN,有些要结合RNN再处理一下。
上图是一个实体词识别算法的case。基于分词结果和词性标注选取候选,期间可能需要根据知识库做一些拼接,有些实体是几个词的组合,要确定哪几个词结合在一起能映射实体的描述。如果结果映射多个实体还要通过词向量、topic分布甚至词频本身等去歧,最后计算一个相关性模型。
三、用户标签
内容分析和用户标签是推荐系统的两大基石。内容分析涉及到机器学习的内容多一些,相比而言,用户标签工程挑战更大。
今日头条常用的用户标签包括用户感兴趣的类别和主题、关键词、来源、基于兴趣的用户聚类以及各种垂直兴趣特征(车型,体育球队,股票等)。还有性别、年龄、地点等信息。性别信息通过用户第三方社交账号登录得到。年龄信息通常由模型预测,通过机型、阅读时间分布等预估。常驻地点来自用户授权访问位置信息,在位置信息的基础上通过传统聚类的方法拿到常驻点。常驻点结合其他信息,可以推测用户的工作地点、出差地点、旅游地点。这些用户标签非常有助于推荐。
当然最简单的用户标签是浏览过的内容标签。但这里涉及到一些数据处理策略。主要包括:一、过滤噪声。通过停留时间短的点击,过滤标题党。二、热点惩罚。对用户在一些热门文章(如前段时间PG One的新闻)上的动作做降权处理。理论上,传播范围较大的内容,置信度会下降。三、时间衰减。用户兴趣会发生偏移,因此策略更偏向新的用户行为。因此,随着用户动作的增加,老的特征权重会随时间衰减,新动作贡献的特征权重会更大。四、惩罚展现。如果一篇推荐给用户的文章没有被点击,相关特征(类别,关键词,来源)权重会被惩罚。当然同时,也要考虑全局背景,是不是相关内容推送比较多,以及相关的关闭和dislike信号等。
用户标签挖掘总体比较简单,主要还是刚刚提到的工程挑战。头条用户标签第一版是批量计算框架,流程比较简单,每天抽取昨天的日活用户过去两个月的动作数据,在Hadoop集群上批量计算结果。
但问题在于,随着用户高速增长,兴趣模型种类和其他批量处理任务都在增加,涉及到的计算量太大。2014年,批量处理任务几百万用户标签更新的Hadoop任务,当天完成已经开始勉强。集群计算资源紧张很容易影响其它工作,集中写入分布式存储系统的压力也开始增大,并且用户兴趣标签更新延迟越来越高。
面对这些挑战。2014年底今日头条上线了用户标签Storm集群流式计算系统。改成流式之后,只要有用户动作更新就更新标签,CPU代价比较小,可以节省80%的CPU时间,大大降低了计算资源开销。同时,只需几十台机器就可以支撑每天数千万用户的兴趣模型更新,并且特征更新速度非常快,基本可以做到准实时。这套系统从上线一直使用至今。
当然,我们也发现并非所有用户标签都需要流式系统。像用户的性别、年龄、常驻地点这些信息,不需要实时重复计算,就仍然保留daily更新。
四、评估分析
上面介绍了推荐系统的整体架构,那么如何评估推荐效果好不好?
有一句我认为非常有智慧的话,“一个事情没法评估就没法优化”。对推荐系统也是一样。
事实上,很多因素都会影响推荐效果。比如侯选集合变化,召回模块的改进或增加,推荐特征的增加,模型架构的改进在,算法参数的优化等等,不一一举例。评估的意义就在于,很多优化最终可能是负向效果,并不是优化上线后效果就会改进。
全面的评估推荐系统,需要完备的评估体系、强大的实验平台以及易用的经验分析工具。所谓完备的体系就是并非单一指标衡量,不能只看点击率或者停留时长等,需要综合评估。过去几年我们一直在尝试,能不能综合尽可能多的指标合成唯一的评估指标,但仍在探索中。目前,我们上线还是要由各业务比较资深的同学组成评审委员会深入讨论后决定。
很多公司算法做的不好,并非是工程师能力不够,而是需要一个强大的实验平台,还有便捷的实验分析工具,可以智能分析数据指标的置信度。
一个良好的评估体系建立需要遵循几个原则,首先是兼顾短期指标与长期指标。我在之前公司负责电商方向的时候观察到,很多策略调整短期内用户觉得新鲜,但是长期看其实没有任何助益。
其次,要兼顾用户指标和生态指标。今日头条作为内容分创作平台,既要为内容创作者提供价值,让他更有尊严的创作,也有义务满足用户,这两者要平衡。还有广告主利益也要考虑,这是多方博弈和平衡的过程。
另外,要注意协同效应的影响。实验中严格的流量隔离很难做到,要注意外部效应。
强大的实验平台非常直接的优点是,当同时在线的实验比较多时,可以由平台自动分配流量,无需人工沟通,并且实验结束流量立即回收,提高管理效率。这能帮助公司降低分析成本,加快算法迭代效应,使整个系统的算法优化工作能够快速往前推进。
这是头条A/B Test实验系统的基本原理。首先我们会做在离线状态下做好用户分桶,然后线上分配实验流量,将桶里用户打上标签,分给实验组。举个例子,开一个10%流量的实验,两个实验组各5%,一个5%是基线,策略和线上大盘一样,另外一个是新的策略。
实验过程中用户动作会被搜集,基本上是准实时,每小时都可以看到。但因为小时数据有波动,通常是以天为时间节点来看。动作搜集后会有日志处理、分布式统计、写入数据库,非常便捷。
在这个系统下工程师只需要设置流量需求、实验时间、定义特殊过滤条件,自定义实验组ID。系统可以自动生成:实验数据对比、实验数据置信度、实验结论总结以及实验优化建议。
当然,只有实验平台是远远不够的。线上实验平台只能通过数据指标变化推测用户体验的变化,但数据指标和用户体验存在差异,很多指标不能完全量化。很多改进仍然要通过人工分析,重大改进需要人工评估二次确认。
五、内容安全
最后要介绍今日头条在内容安全上的一些举措。头条现在已经是国内最大的内容创作与分发凭条,必须越来越重视社会责任和行业领导者的责任。如果1%的推荐内容出现问题,就会产生较大的影响。
因此头条从创立伊始就把内容安全放在公司最高优先级队列。成立之初,已经专门设有审核团队负责内容安全。当时研发所有客户端、后端、算法的同学一共才不到40人,头条非常重视内容审核。
现在,今日头条的内容主要来源于两部分,一是具有成熟内容生产能力的PGC平台
一是UGC用户内容,如问答、用户评论、微头条。这两部分内容需要通过统一的审核机制。如果是数量相对少的PGC内容,会直接进行风险审核,没有问题会大范围推荐。UGC内容需要经过一个风险模型的过滤,有问题的会进入二次风险审核。审核通过后,内容会被真正进行推荐。这时如果收到一定量以上的评论或者举报负向反馈,还会再回到复审环节,有问题直接下架。整个机制相对而言比较健全,作为行业领先者,在内容安全上,今日头条一直用最高的标准要求自己。
分享内容识别技术主要鉴黄模型,谩骂模型以及低俗模型。今日头条的低俗模型通过深度学习算法训练,样本库非常大,图片、文本同时分析。这部分模型更注重召回率,准确率甚至可以牺牲一些。谩骂模型的样本库同样超过百万,召回率高达95%+,准确率80%+。如果用户经常出言不讳或者不当的评论,我们有一些惩罚机制。
泛低质识别涉及的情况非常多,像假新闻、黑稿、题文不符、标题党、内容质量低等等,这部分内容由机器理解是非常难的,需要大量反馈信息,包括其他样本信息比对。目前低质模型的准确率和召回率都不是特别高,还需要结合人工复审,将阈值提高。目前最终的召回已达到95%,这部分其实还有非常多的工作可以做。头条人工智能实验室李航老师目前也在和密歇根大学共建科研项目,设立谣言识别平台。
以上是头条推荐系统的原理分享,希望未来得到更多的建议,帮助我们更好改进工作。
https://www.jianshu.com/p/7286e8bd7793
-
今日头条推荐算法原理 - 梳理
2018-06-11 12:29:12PS:腾讯新闻和今日头条,我每天都会对比着用,喜欢腾讯新闻的细致和头条的粗暴。 算法分发已经是信息平台...今日头条资深算法架构师曹欢欢博士,公开今日头条的算法原理,以推动整个行业问诊算法、建言算法;通过...PS:腾讯新闻和今日头条,我每天都会对比着用,喜欢腾讯新闻的细致和头条的粗暴。
算法分发已经是信息平台、搜索引擎、浏览器、社交软件等几乎所有软件的标配,但同时,算法也开始面临质疑、挑战和误解。
今日头条的推荐算法,从 2012 年 9 月第一版开发运行至今,已经经过四次大的调整和修改。
今日头条资深算法架构师曹欢欢博士,公开今日头条的算法原理,以推动整个行业问诊算法、建言算法;通过让算法透明,来消除各界对算法的误解,并逐步推动整个行业让算法更好的造福社会。
本次分享主要围绕五个方面介绍今日头条的推荐原理:
- 系统概览
- 内容分析
- 用户标签
- 评估分析
- 内容安全
系统概览
推荐系统,如果用形式化的方式去描述实际上是拟合一个用户对内容满意度的函数。
这个函数需要输入三个维度的变量:
- 内容。头条现在已经是一个综合内容平台,图文、视频、UGC 小视频、问答、微头条,每种内容有很多自己的特征,需要考虑怎样提取不同内容类型的特征做好推荐。
- 用户特征。包括各种兴趣标签,职业、年龄、性别等,还有很多模型刻划出的隐式用户兴趣等。
- 环境特征。这是移动互联网时代推荐的特点,用户随时随地移动,在工作场合、通勤、旅游等不同的场景,信息偏好有所偏移。
结合三方面的维度,模型会给出一个预估,即推测推荐内容在这一场景下对这一用户是否合适。
这里还有一个问题,如何引入无法直接衡量的目标?
推荐模型中,点击率、阅读时间、点赞、评论、转发包括点赞都是可以量化的目标,能够用模型直接拟合做预估,看线上提升情况可以知道做的好不好。
但一个大体量的推荐系统,服务用户众多,不能完全由指标评估,引入数据指标以外的要素也很重要。
比如广告和特型内容频控,像问答卡片就是比较特殊的内容形式,其推荐的目标不完全是让用户浏览,还要考虑吸引用户回答为社区贡献内容。这些内容和普通内容如何混排,怎样控制频控都需要考虑。
此外,平台出于内容生态和社会责任的考量,像低俗内容的打压,标题党、低质内容的打压,重要新闻的置顶、加权、强插,低级别账号内容降权都是算法本身无法完成,需要进一步对内容进行干预。
下面我将简单介绍在上述算法目标的基础上如何对其实现。
前面提到的公式 y = F(Xi ,Xu ,Xc),是一个很经典的监督学习问题。可实现的方法有很多。
比如传统的协同过滤模型,监督学习算法 Logistic Regression 模型,基于深度学习的模型,Factorization Machine 和 GBDT 等。
一个优秀的工业级推荐系统需要非常灵活的算法实验平台,可以支持多种算法组合,包括模型结构调整,因为很难有一套通用的模型架构适用于所有的推荐场景。
现在很流行将 LR 和 DNN 结合,前几年 Facebook 也将 LR 和 GBDT 算法做了结合。
今日头条旗下几款产品都在沿用同一套强大的算法推荐系统,但根据业务场景不同,模型架构会有所调整。
模型之后再看一下典型的推荐特征,主要有四类特征会对推荐起到比较重要的作用。
- 相关性特征,就是评估内容的属性和用户是否匹配。显性的匹配包括关键词匹配、分类匹配、来源匹配、主题匹配等。像 FM 模型中也有一些隐性匹配,从用户向量与内容向量的距离可以得出。
- 环境特征,包括地理位置、时间。这些既是 bias 特征,也能以此构建一些匹配特征。
- 热度特征。包括全局热度、分类热度,主题热度,以及关键词热度等。内容热度信息在大的推荐系统特别在用户冷启动的时候非常有效。
- 协同特征,它可以在部分程度上帮助解决所谓算法越推越窄的问题。协同特征并非考虑用户已有历史。 而是通过用户行为分析不同用户间相似性,比如点击相似、兴趣分类相似、主题相似、兴趣词相似,甚至向量相似,从而扩展模型的探索能力。
模型的训练上,头条系大部分推荐产品采用实时训练。实时训练省资源并且反馈快,这对信息流产品非常重要。
用户需要行为信息可以被模型快速捕捉并反馈至下一刷的推荐效果。我们线上目前基于 Storm 集群实时处理样本数据,包括点击、展现、收藏、分享等动作类型。
模型参数服务器是内部开发的一套高性能的系统,因为头条数据规模增长太快,类似的开源系统稳定性和性能无法满足,而我们自研的系统底层做了很多针对性的优化,提供了完善运维工具,更适配现有的业务场景。
目前,头条的推荐算法模型在世界范围内也是比较大的,包含几百亿原始特征和数十亿向量特征。
整体的训练过程是线上服务器记录实时特征,导入到 Kafka 文件队列中,然后进一步导入 Storm 集群消费 Kafka 数据,客户端回传推荐的 Label 构造训练样本,随后根据最新样本进行在线训练更新模型参数,最终线上模型得到更新。
这个过程中主要的延迟在用户的动作反馈延时,因为文章推荐后用户不一定马上看,不考虑这部分时间,整个系统是几乎实时的。
但因为头条目前的内容量非常大,加上小视频内容有千万级别,推荐系统不可能所有内容全部由模型预估。
所以需要设计一些召回策略,每次推荐时从海量内容中筛选出千级别的内容库。召回策略最重要的要求是性能要极致,一般超时不能超过 50 毫秒。
召回策略种类有很多,我们主要用的是倒排的思路。离线维护一个倒排,这个倒排的 key 可以是分类,topic,实体,来源等,排序考虑热度、新鲜度、动作等。
线上召回可以迅速从倒排中根据用户兴趣标签对内容做截断,高效的从很大的内容库中筛选比较靠谱的一小部分内容。
内容分析
内容分析包括文本分析,图片分析和视频分析。头条一开始主要做资讯,今天我们主要讲一下文本分析。
文本分析在推荐系统中一个很重要的作用是用户兴趣建模。没有内容及文本标签,无法得到用户兴趣标签。
举个例子,只有知道文章标签是互联网,用户看了互联网标签的文章,才能知道用户有互联网标签,其他关键词也一样。
另一方面,文本内容的标签可以直接帮助推荐特征,比如魅族的内容可以推荐给关注魅族的用户,这是用户标签的匹配。
如果某段时间推荐主频道效果不理想,出现推荐窄化,用户会发现到具体的频道推荐(如科技、体育、娱乐、军事等)中阅读后,再回主 Feed,推荐效果会更好。
因为整个模型是打通的,子频道探索空间较小,更容易满足用户需求。只通过单一信道反馈提高推荐准确率难度会比较大,子频道做的好很重要。而这也需要好的内容分析。
上图是今日头条的一个实际文本 case。从图中可以看到,这篇文章有分类、关键词、topic、实体词等文本特征。
当然不是没有文本特征,推荐系统就不能工作,推荐系统最早期应用在 Amazon,甚至沃尔玛时代就有,包括 Netfilx 做视频推荐也没有文本特征直接协同过滤推荐。
但对资讯类产品而言,大部分是消费当天内容,没有文本特征新内容冷启动非常困难,协同类特征无法解决文章冷启动问题。
今日头条推荐系统主要抽取的文本特征包括以下几类。首先是语义标签类特征,显式为文章打上语义标签。这部分标签是由人定义的特征,每个标签有明确的意义,标签体系是预定义的。
此外还有隐式语义特征,主要是 topic 特征和关键词特征,其中 topic 特征是对于词概率分布的描述,无明确意义;而关键词特征会基于一些统一特征描述,无明确集合。
另外文本相似度特征也非常重要。在头条,曾经用户反馈最大的问题之一就是为什么总推荐重复的内容。这个问题的难点在于,每个人对重复的定义不一样。
举个例子,有人觉得这篇讲皇马和巴萨的文章,昨天已经看过类似内容,今天还说这两个队那就是重复。
但对于一个重度球迷而言,尤其是巴萨的球迷,恨不得所有报道都看一遍。解决这一问题需要根据判断相似文章的主题、行文、主体等内容,根据这些特征做线上策略。
同样,还有时空特征,分析内容的发生地点以及时效性。比如武汉限行的事情推给北京用户可能就没有意义。
最后还要考虑质量相关特征,判断内容是否低俗,色情,是否是软文,鸡汤?
上图是头条语义标签的特征和使用场景。他们之间层级不同,要求不同。
分类的目标是覆盖全面,希望每篇内容每段视频都有分类;而实体体系要求精准,相同名字或内容要能明确区分究竟指代哪一个人或物,但不用覆盖很全。
概念体系则负责解决比较精确又属于抽象概念的语义。这是我们最初的分类,实践中发现分类和概念在技术上能互用,后来统一用了一套技术架构。
目前,隐式语义特征已经可以很好的帮助推荐,而语义标签需要持续标注,新名词新概念不断出现,标注也要不断迭代。
其做好的难度和资源投入要远大于隐式语义特征,那为什么还需要语义标签?
有一些产品上的需要,比如频道需要有明确定义的分类内容和容易理解的文本标签体系。语义标签的效果是检查一个公司 NLP 技术水平的试金石。
今日头条推荐系统的线上分类采用典型的层次化文本分类算法。
最上面是 Root,下面第一层的分类是像科技、体育、财经、娱乐,体育这样的大类。
再下面细分足球、篮球、乒乓球、网球、田径、游泳等,足球再细分国际足球、中国足球,中国足球又细分中甲、中超、国家队等。
相比单独的分类器,利用层次化文本分类算法能更好地解决数据倾斜的问题。有一些例外是,如果要提高召回,可以看到我们连接了一些飞线。
这套架构通用,但根据不同的问题难度,每个元分类器可以异构,像有些分类 SVM 效果很好,有些要结合 CNN,有些要结合 RNN 再处理一下。
上图是一个实体词识别算法的 case。基于分词结果和词性标注选取候选,期间可能需要根据知识库做一些拼接,有些实体是几个词的组合,要确定哪几个词结合在一起能映射实体的描述。
如果结果映射多个实体还要通过词向量、topic 分布甚至词频本身等去歧,最后计算一个相关性模型。
用户标签
内容分析和用户标签是推荐系统的两大基石。内容分析涉及到机器学习的内容多一些,相比而言,用户标签工程挑战更大。
今日头条常用的用户标签包括用户感兴趣的类别和主题、关键词、来源、基于兴趣的用户聚类以及各种垂直兴趣特征(车型,体育球队,股票等)。还有性别、年龄、地点等信息。
性别信息通过用户第三方社交账号登录得到。年龄信息通常由模型预测,通过机型、阅读时间分布等预估。
常驻地点来自用户授权访问位置信息,在位置信息的基础上通过传统聚类的方法拿到常驻点。
常驻点结合其他信息,可以推测用户的工作地点、出差地点、旅游地点。这些用户标签非常有助于推荐。
当然最简单的用户标签是浏览过的内容标签。但这里涉及到一些数据处理策略,主要包括:
- 过滤噪声。通过停留时间短的点击,过滤标题党。
- 惩罚热点。对用户在一些热门文章(如前段时间 PG One 的新闻)上的动作做降权处理。理论上,传播范围较大的内容,置信度会下降。
- 时间衰减。用户兴趣会发生偏移,因此策略更偏向新的用户行为。因此,随着用户动作的增加,老的特征权重会随时间衰减,新动作贡献的特征权重会更大。
- 当然同时,也要考虑全局背景,是不是相关内容推送比较多,以及相关的关闭和 dislike 信号等。
用户标签挖掘总体比较简单,主要还是刚刚提到的工程挑战。头条用户标签第一版是批量计算框架,流程比较简单,每天抽取昨天的日活用户过去两个月的动作数据,在 Hadoop 集群上批量计算结果。
但问题在于,随着用户高速增长,兴趣模型种类和其他批量处理任务都在增加,涉及到的计算量太大。
2014 年,批量处理几百万用户标签更新的 Hadoop 任务,当天完成已经开始勉强。
集群计算资源紧张很容易影响其他工作,集中写入分布式存储系统的压力也开始增大,并且用户兴趣标签更新延迟越来越高。
面对这些挑战,2014 年底今日头条上线了用户标签 Storm 集群流式计算系统。
改成流式之后,只要有用户动作更新就更新标签,CPU 代价比较小,可以节省 80% 的 CPU 时间,大大降低了计算资源开销。
同时,只需几十台机器就可以支撑每天数千万用户的兴趣模型更新,并且特征更新速度非常快,基本可以做到准实时。这套系统从上线一直使用至今。
当然,我们也发现并非所有用户标签都需要流式系统。像用户的性别、年龄、常驻地点这些信息,不需要实时重复计算,就仍然保留 daily 更新。
评估分析
上面介绍了推荐系统的整体架构,那么如何评估推荐效果好不好?有一句我认为非常有智慧的话,“一个事情没法评估就没法优化”。对推荐系统也是一样。
事实上,很多因素都会影响推荐效果。比如侯选集合变化,召回模块的改进或增加,推荐特征的增加,模型架构的改进,算法参数的优化等等。
评估的意义就在于,很多优化最终可能是负向效果,并不是优化上线后效果就会改进。
全面的评估推荐系统,需要完备的评估体系、强大的实验平台以及易用的经验分析工具。
所谓完备的体系就是并非单一指标衡量,不能只看点击率或者停留时长等,需要综合评估。
过去几年我们一直在尝试,能不能综合尽可能多的指标合成唯一的评估指标,但仍在探索中。目前,我们上线还是要由各业务比较资深的同学组成评审委员会深入讨论后决定。
很多公司算法做的不好,并非是工程师能力不够,而是需要一个强大的实验平台,还有便捷的实验分析工具,可以智能分析数据指标的置信度。
一个良好的评估体系建立需要遵循几个原则,首先是兼顾短期指标与长期指标。
我在之前公司负责电商方向的时候观察到,很多策略调整短期内用户觉得新鲜,但是长期看其实没有任何助益。
其次,要兼顾用户指标和生态指标。今日头条作为内容分发创作平台,既要为内容创作者提供价值,让他更有尊严的创作,也有义务满足用户,这两者要平衡。还有广告主利益也要考虑,这是多方博弈和平衡的过程。
另外,要注意协同效应的影响。实验中严格的流量隔离很难做到,要注意外部效应。
强大的实验平台非常直接的优点是,当同时在线的实验比较多时,可以由平台自动分配流量,无需人工沟通,并且实验结束流量立即回收,提高管理效率。
这能帮助公司降低分析成本,加快算法迭代效应,使整个系统的算法优化工作能够快速往前推进。
这是头条 A/B Test 实验系统的基本原理。首先我们会在离线状态下做好用户分桶,然后线上分配实验流量,将桶里用户打上标签,分给实验组。
举个例子,开一个 10% 流量的实验,两个实验组各 5%,一个 5% 是基线,策略和线上大盘一样,另外一个是新的策略。
实验过程中用户动作会被搜集,基本上是准实时,每小时都可以看到。但因为小时数据有波动,通常是以天为时间节点来看。动作搜集后会有日志处理、分布式统计、写入数据库,非常便捷。
在这个系统下工程师只需要设置流量需求、实验时间、定义特殊过滤条件,自定义实验组 ID。
系统可以自动生成:实验数据对比、实验数据置信度、实验结论总结以及实验优化建议。
当然,只有实验平台是远远不够的。线上实验平台只能通过数据指标变化推测用户体验的变化,但数据指标和用户体验存在差异,很多指标不能完全量化。很多改进仍然要通过人工分析,重大改进需要人工评估二次确认。
内容安全
最后要介绍今日头条在内容安全上的一些举措。头条现在已经是国内最大的内容创作与分发平台,必须越来越重视社会责任和行业领导者的责任。如果 1% 的推荐内容出现问题,就会产生较大的影响。
因此头条从创立伊始就把内容安全放在公司最高优先级队列。成立之初,它已经专门设有审核团队负责内容安全。
当时研发所有客户端、后端、算法的同学一共才不到 40 人,可见头条非常重视内容审核。
现在,今日头条的内容主要来源于两部分:
- 具有成熟内容生产能力的 PGC 平台。
- UGC 用户内容,如问答、用户评论、微头条。
这两部分内容需要通过统一的审核机制。如果是数量相对少的 PGC 内容,会直接进行风险审核,没有问题会大范围推荐。
UGC 内容需要经过一个风险模型的过滤,有问题的会进入二次风险审核。审核通过后,内容会被真正进行推荐。
这时如果收到一定量以上的评论或者举报负向反馈,还会再回到复审环节,有问题直接下架。
整个机制相对而言比较健全,作为行业领先者,在内容安全上,今日头条一直用最高的标准要求自己。
分享内容识别技术主要有鉴黄模型,俗模型以及谩骂模型。今日头条的低俗模型通过深度学习算法训练,样本库非常大,图片、文本同时分析。
这部分模型更注重召回率,准确率甚至可以牺牲一些。谩骂模型的样本库同样超过百万,召回率高达 95%+,准确率 80%+。如果用户经常出言不讳或者不当的评论,我们有一些惩罚机制。
泛低质识别涉及的情况非常多,像假新闻、黑稿、题文不符、标题党、内容质量低等等,这部分内容由机器理解是非常难的,需要大量反馈信息,包括其他样本信息比对。
目前低质模型的准确率和召回率都不是特别高,还需要结合人工复审,将阈值提高。目前最终的召回已达到 95%,这部分其实还有非常多的工作可以做。
头条人工智能实验室李航老师目前也在和密歇根大学共建科研项目,设立谣言识别平台。
以上是头条推荐系统的原理分享,希望未来得到更多的建议,帮助我们更好改进工作。
作者:曹欢欢
编辑:陶家龙、孙淑娟
来源:https://www.sohu.com/a/217497781_463994
-
【应用算法】信息流-推荐系统的去重策略
2018-09-23 01:09:53聊两个问题,它们看似和推荐系统没有必然关系,但实际上, ...先说说内容源的去重,这部分以前几年的图文信息流推荐为典型的例子。 如果一个平台自己不生产内容,只是做内容搬运和聚合分发,那么...聊两个问题,它们看似和推荐系统没有必然关系,但实际上,
在你构建自己的推荐系统的时候,不可避免地会遇到这两个问题。
去重是刚需
在推荐系统中,有一个刚需就是去重,那么说在哪些地方有去重的需求呢?
主要是在两个地方:一个是内容源去重,另一个是不重复给用户推荐。
先说说内容源的去重,这部分以前几年的图文信息流推荐为典型的例子。
如果一个平台自己不生产内容,只是做内容搬运和聚合分发,那么从大量第三方的内容生产处抓取内容,就难免遇到相似甚至重复的内容。这就需要对内容做一个重复检测了。
对内容做重复检测,直观的思路是分词,然后提取关键词,再两两计算词向量之间的距离,距离小于一定阈值后就判定为重复。然而,这对于海量内容,比如几千万以上的内容来说简直就是灾难。
其实,内容源去重并不是仅在推荐系统中才首次出现,这早在搜索引擎时代就是一个刚需了,搜索引擎把整个互联网的网页都下载到自己的服务器上,这时,重复冗余的内容就需要被检测出来。
另一个需求是在内容阅读类推荐场景下,给用户推荐的内容不要重复,推荐过的内容就不再出现在推荐候选集中。
在你刷一个信息流产品时,不断看到重复的内容,想必不是使用感很好的一件事。因为以抓取作为主要内容来源的信息流产品,不同于社交网站上用户自发产生内容,除非遇到用户恶意发送,否则后者是不容易重复的。
以上两个场景,需要在你打造自己的推荐系统时予以考虑和应对。
今天就介绍两种最常见的去重算法,两者有相通之处也有不同的之处。
Simhash
内容重复检测,是搜索引擎公司最先遇到的,所以 Google 在 07 年公开了他们内部的内容重复检测算法,这个算法简单有效,甚至造福了今天的信息流推荐产品。
对于很长的内容,如果只是检测绝对重复,也就是说完全一模一样的那种情况,那么使用 MD5 这样的信息指纹方法非常高效,无需再去分词、提取关键词和计算关键词向量之间的距离。
我们直接将原始的内容映射为一个短字符串,这个短字符串就是原始内容的指纹,虽然不是绝对保证和原始内容一一映射,但是不同内容能得到相同指纹的概率非常小。
只是这种信息指纹的方法有个非常明显的坏处就是,哪怕原始内容改一个字,得到的信息指纹就会截然不同。
这就没法愉快地玩耍了,你一定希望的是只要主要内容不变,就算一些不太重要的词句不同,也仍然可以得到相近甚至相同的指纹。这才能更加灵活地进行内容重复检测。是否有这样的算法?有,就是 Simhash。
Simhash 核心思想也是为每个内容生成一个整数表示的指纹,然后用这个指纹去做重复或者相似的检测。下面这个示意图说明了 Simhash 如何把一个原始内容表示成一个整数指纹。
好,现在详细说明一下这个过程。
1. 首先,对原始内容分词,并且计算每个词的权重;
2. 对每个词哈希成一个整数,并且把这个整数对应的二进制序列中的 0 变成 -1,1 还是 1,得到一个 1 和 -1 组成的向量;
3. 把每个词哈希后的向量乘以词的权重,得到一个新的加权向量;
4. 把每个词的加权向量相加,得到一个最终向量,这个向量中每个元素有正有负;
5. 把最终这个向量中元素为正的替换成 1,为负的替换成 0,这个向量变成一个二进制位序列,也就是最终变成了一个整数。
最终这个整数就代表了原始的内容。这个 Simhash 奇妙在哪呢?
看这个示意图中,故意加了一个不太重要的词“了”,它的权重是 1,对应的加权向量元素不是 1 就是 -1,在上述的第四步中,如果这个词对应的向量缺少了,其实根本不影响最终得到那个整数,因为它很难改变最终向量元素的正负。这就是为什么那些不太重要的词不影响内容之间的重复检测。
Simhash 为每一个内容生成一个整数指纹,其中的关键是把每个词哈希成一个整数,这一步常常采用 Jenkins 算法。这里简单示意的整数只有 8 个二进制位,实际上可能需要 64 个二进制位的整数,甚至范围更大。
得到每个内容的 Simhash 指纹后,可以两两计算汉明距离,比较二进制位不同个数,其实就是计算两个指纹的异或,异或结果中如果包含 3 个以下的 1,则认为两条内容重复。
为了高效,也可以直接认为指纹相同才重复,视情况而定。
Bloomfilter
除了内容重复检测,还有一个需求是防止已经推荐的内容被重复推荐。这个刚需和上述内容重复相比,最大的不同就是过滤对象不同,上述 Simhash 过滤对象是内容本身,而这里则一般是内容的 ID。
内容的 ID 一般是用一个 UUID 表示,是一个不太长的字符串或者整数。
对于这类形如模式串的去重,显然可以用单独专门的数据库来保存,为了高效,甚至可以为它建上索引。
但对于用户量巨大的情况下,这个做法对存储的消耗则不可小看。实际上,解决这类看一个字符串在不在一个集合中的问题,有一个有点老但很好用的做法,就是 Bloomfilter,有时候也被称为布隆过滤器。
布隆过滤器的原理也要用到哈希函数。它包含两部分:一个很长的二进制位向量,和一系列哈希函数。Bloomfilter 是一个很巧妙的设计,它先把原始要查询的集合映射到一个长度为 m 的二进制位向量上去,它映射的方法是:
1. 设计 n 个互相独立的哈希函数,准备一个长度为 m 的二进制向量,最开始全是 0;
2. 每个哈希函数把集合内的元素映射为一个不超过 m 的正整数 k,m 就是二进制向量的长度;
3. 把这个二进制向量中的第 k 个位置设置为 1;也就是一个元素会在二进制向量中对应 n 个位置为 1。
看示意图。
这个示意图中,原始的模式串经过三个互相独立的哈希函数,映射到 8 位二进制向量中的三个位置了。
原始的模式串集合经过这样的处理后,就得到一个很大的二进制向量。在应用阶段时,假如来了一个模式串 s,需要查询是否在这个集合中,也需要经过同样的上述步骤。
每个哈希函数对这个模式串 s 哈希后都得到一个整数,看看这个整数在二进制向量中所指示的位置是不是 1,如果每个哈希函数所指示的位置都是 1,就说明模式串 s 已经在集合中了。
需要说明的是,Bloomfilter 也并不是百分之百保证的,有很小的概率把原本不存在集合中的模式串判断为存在。这样就会造成那些明明还没有推荐给用户的内容 ID 就再也不会推荐给用户了,当然,这个小概率是可以承受的。
总结
介绍了两种去重算法。在推荐系统中,虽然我们十分关心推荐匹配的效果,但是别忘了,对原始内容的挖掘和清洗往往更加重要。这其中就包括对重复内容的检测。
两种去重策略都是牺牲一点误伤的概率换得大幅度的效率提升,具体的做法都是要借助哈希函数。只是哈希函数的结果在两个算法中有不同的处理手段,Simhash 是加权,Bloomfilter 则是用来做寻址。
有一个思考题,请你想一想,如果要从 Bloomfilter 中去掉一个元素,该怎么做?有兴趣,可以一起探讨一下。
------------------------------------------------------
------------------------------------------------------
关于我(个人域名)
期望和大家一起学习,共同进步,共勉,O(∩_∩)O谢谢
欢迎交流问题,可加个人QQ 469580884,
或者,加我的群号 751925591,一起探讨交流问题
不讲虚的,只做实干家
Talk is cheap,show me the code
如果觉得内容赞,您可以请我喝杯咖啡:
-
基于内容推荐算法实现原理
2020-04-30 22:00:36本文会从什么是基于内容的推荐算法、算法基本原理、应用场景、基于内容的推荐算法的优缺点、算法落地需要关注的点等5个方面来讲解。 1、什么是基于内容的推荐算法 所谓基于内容的推荐算法(Content-Based ... -
今日头条推荐算法原理解析
2018-10-29 15:37:03转自:https://blog.csdn.net/ScarlettYellow/article/details/80458075?utm_source=blogxgwz2 ,谢谢原作者这么...1.头条推荐算法原理1.1 系统概览1.资讯推荐系统”你关心的,才是头条“本质要解决的问题:用户、环... -
常用的基于内容的推荐算法实现原理
2019-10-05 11:03:26本文会从什么是基于内容的推荐算法、算法基本原理、应用场景、基于内容的推荐算法的优缺点、算法落地需要关注的点等5个方面来讲解。 希望读者读完可以掌握常用的基于内容的推荐算法的实现原理,并且可以基于本文的... -
今日头条、抖音推荐算法原理全文详解!
2020-03-12 00:00:00实时训练省资源并且反馈快,这对信息流产品非常重要。用户需要行为信息可以被模型快速捕捉并反馈至下一刷的推荐效果。 我们线上目前基于storm集群实时处理样本数据,包括点击、展现、收藏、分享等动作类型。 模型... -
今日头条的新闻推荐算法原理
2018-05-23 09:54:03为让产业各方更好的了解算法分发的相关技术和原理,我们特整理了当下最具影响力的平台的相关干货,和各方分享。本期微信,我们将推荐影视类的Netflix和新闻类的今日头条的算法技术。 今天,算法分发已经... -
揭秘今日头条、抖音的推荐算法原理!
2020-09-22 00:00:00实时训练省资源并且反馈快,这对信息流产品非常重要。用户需要行为信息可以被模型快速捕捉并反馈至下一刷的推荐效果。我们线上目前基于storm集群实时处理样本数据,包括点击、展现、收藏、分享等动作类型。模型参数... -
【密码学原理】流密码和RC4算法
2020-10-03 12:01:55流密码 -
典型推荐算法总结
2018-11-23 21:05:42推荐算法种类很多,但是目前应用最广泛的应该是协同过滤类别的推荐算法,本文就对协同过滤类别的推荐算法做一个概括总结,后续也会对一些典型的协同过滤推荐算法做原理总结。 1. 推荐算法概述 推荐算法是非常... -
限流算法-常见的4种限流算法
2022-03-17 17:39:12首先我们先来看看什么是限流? 限流是指在系统面临高并发、大流量请求的情况下,限制新的流量对系统的访问,从而保证系统服务的安全性。 另一种解释:在计算机网络中,限流就是控制网络接口发送或接收请求的速率,它... -
ZUC算法原理及实现过程.doc
2020-12-21 14:54:22ZUC算法原理及实现过程1.1 算法设计背景ZUC算法,即祖冲之算法,是3GPP机密性算法EEA3和完整性算法EIA3的核心,为中国自主设计的流密码算法。2009年5月ZUC算法获得3GPP安全算法组SA立项,正式申请参加3GPPLTE第三套... -
RSA算法原理——(1)目前常见加密算法简介
2018-06-18 21:50:53今天为大家带来RSA算法的讲解文章,主要包括RSA算法的加解密过程和公式论证。文章可能会稍微有点长,但是内容绝对是目前全网最详细的,最通俗易懂的,跟着昌昌来一起揭开RSA非对称加密算法的面纱,保你看完本篇文章... -
今日头条算法原理(全)
2020-03-31 18:00:00▲3分钟了解今日头条推荐算法原理今天,算法分发已经是信息平台、搜索引擎、浏览器、社交软件等几乎所有软件的标配,但同时,算法也开始面临质疑、挑战和误解。今日头条的推荐算法,从2012年9... -
AMCL算法原理讲解
2020-04-13 16:48:13ROS进阶教程(二)AMCL算法原理讲解AMCL算法理解蒙特卡洛定位算法蒙特卡洛定位算法自适应变种里程计运动模型测距仪模型波束模型似然域模型 AMCL算法理解 AMCL(adaptive Monte Carlo Localization)自适应蒙特卡洛定位... -
Java 常用限流算法解析
2021-08-19 19:38:03限流无处不在,既然限流的作用如此强大,那么其底层的实现原理如何呢,说到底,限流的核心是由一系列不同的算法完成,本篇将通过实例来说明下常用的几种限流算法的用法和原理 1、计数器算法 计数器算法限流是采用... -
CRC算法原理详解
2019-09-18 00:20:33CRC基础算法解析生成多项式CRC运算CRC算法解析(零填充)CRC算法解析(无需零填充)总结 生成多项式 以比特流 11001001为例,其生成多项式为: G(x) = x^7 + x^6 + x^3 + 1 至于为何使用指数的形式,是因为生成... -
个性化推荐算法总结
2019-04-11 23:24:58读书笔记 |《推荐系统实践》- 个性化推荐系统总结 对于推荐系统,本文总结内容,如下图所示: 一、什么是推荐系统 1. 为什么需要推荐系统 为了解决互联网时代下的信息超载问题。 2. 搜索引擎与推荐系统 ... -
算法高级(7)-限流(Rate limit)算法详解
2019-09-02 00:31:41今天和大家谈谈限流算法的几种实现方式,本文所说的限流并非是Nginx层面的限流,而是业务代码中的逻辑限流。 那么为什么需要限流呢? 按照服务的调用方,可以分为以下几种类型服务 1、与用户打交道的服务 比如... -
微博推荐算法简述
2019-11-26 17:38:36在介绍微博推荐算法之前,我们先聊一聊推荐系统和推荐算法。有这样一些问题:推荐系统适用哪些场景?用来解决什么问题、具有怎样的价值?效果如何衡量? 推荐系统诞生很早,但真正被大家所重视,缘起于以”facebook... -
字节跳动:今日头条算法原理(全)
2020-12-16 22:30:00今天,算法分发已经是信息平台、搜索引擎、浏览器、社交软件等几乎所有软件的标配,但同时,算法也开始面临质疑、挑战和误解。今日头条的推荐算法,从2012年9月第一版开发运行至今,已经经过四次... -
带你走进微博背后的大数据原理:微博推荐算法
2019-03-25 17:18:06在介绍微博推荐算法之前,我们先聊一聊推荐系统和推荐算法。有这样一些问题:推荐系统适用哪些场景?用来解决什么问题、具有怎样的价值?效果如何衡量? 推荐系统诞生很早,但真正被大家所重视,缘起于以”facebook”... -
从原理到落地,七大维度详解矩阵分解推荐算法
2019-08-23 20:19:07作者 |gongyouliu编辑丨Zandy来源 |大数据与人工智能 ( ID: ai-big-data)导语:作者在《协同过滤推荐算法》这篇文章中介绍了 user... -
【人工智能】推荐系统算法
2021-12-07 19:33:04推荐系统算法详解 一、常用推荐算法分类 1. 基于人口统计学的推荐算法 基于人口统计学的推荐机制(Demographic-based Recommendation)是一种最易于实现的推荐方法,它只是简单的根据系统用户的基本信息发现用户的... -
3分钟了解今日头条推荐算法原理(附视频+PPT)
2018-01-17 00:00:00来源:大数据文摘概要:2018年1月,今日头条资深算法架构师曹欢欢博士,终于首次公开今日头条的算法原理,以期推动整个行业问诊算法、建言算法,希望消除各界对算法的误解。今日头条的内容分发算法一直颇神秘低调。... -
WMD算法原理
2019-10-25 10:54:33WMD(Word Mover’s Distance)算法原理 文章主要是自己在学习过程中摘录做的笔记。 参考连接:WMD算法详解 1. WMD的直观理解 两段文字D1D1D1,D2D2D2,每段文字中的字都使用word2vec算法映射到embedding空间中。并且... -
RSA算法原理简介
2019-01-13 17:24:44我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rives...