0°

详析兴趣feed:从理论到技术要点

内容预览:
  • Feed 通常都是默认按照内容产生的时间先后顺序排列,这就是 timeline(...~
  • 具体到兴趣feed系统中,每当一个用户发布一条动态,我们就产生一个celer...~
  • 工程上,特征工程比算法要重要很多,方法有一些,但是领域差别大,具体...~

作者:陈开江@刑无刀

来源:ResysChina


本文分为四大部分,包括:


  1. 为什么应该关注兴趣Feed?

  2. 关于 Facebook NewsFeed,看这一篇就够了!

  3. Pinterest 的 Smart Feed 架构与算法

  4. 通用兴趣Feed的技术要点


一、为什么应该关注兴趣Feed?


一方面,Twitter 和 Instagram 都宣布要转向兴趣feed了,可见大势所趋。另外,推荐算法工程师对传统的推荐系统关注很多,对兴趣feed这种形式关注较少,按照KK的说法,它更代表一种互联网的必然。


我们经常谈论的推荐系统,从形式上看是比较“静态”的推荐:它通常安安静静站在一个角落(右边、左边、底边),通常只是我们主要浏览信息的一个陪衬。


电商网站的“X了又X”是最常见的推荐形式,“看了又看”、“买了又买”,还有略高级点的,“X了又O”,比如“看了最终买了”。


详析兴趣feed:从理论到技术要点


在协同过滤鼻祖 Amazon 的引领下,这种推荐系统四处开花,成为了电商届的标配,纵使一些中小型垂直网站,也能在百分点这样的第三方推荐引擎帮助下,加入这种推荐系统。在 Netflix 的百万美元诱惑下,其相关的推荐算法发展又前进了一大步。


但这种推荐系统大多数场景下没能独立撑起一款产品,永远安安静静站在某个角落,眼巴巴渴望用户能瞧上一眼。而今天我们要介绍的“兴趣feed”是另一个类型的推荐系统,它已经成为很多互联网产品的现金牛、大当家。


Feed,就是我们常常看到的“动态”、“新鲜事”,是一种信息流。当用户与一些内容源建立了硬链接后,这些内容源产生的动态,就会源源不断地流向用户,多个内容源产生的动态会被聚合后呈现在用户面前。


详析兴趣feed:从理论到技术要点


想象一下,当你加入一个社交网络,就成为了这个网络中的节点之一,其他的节点的风吹草动你就想有所了解,同时别的节点也想知道你的风吹草动。网络中任何一个节点“动一下”,都会以feed的形式在整个网络中荡漾。


Feed 通常都是默认按照内容产生的时间先后顺序排列,这就是 timeline(时间线),Twitter、微博、Instagram 一开始都是这种时间线。


详析兴趣feed:从理论到技术要点

详析兴趣feed:从理论到技术要点


但是最近这些老牌时间线feed都扬言要切换成兴趣feed了,现有微博2012年就尝试过智能排序,Twitter 在去年上线了一个功能叫做“当你不在时发生了什么”[1]。


详析兴趣feed:从理论到技术要点


今年初 Twitter 又宣布在时间线中引入算法,帮用户筛选更感兴趣的内容[2]。今年三月,Instagram 也说他们的用户平均错过了70%的内容,宣布用算法解决这个问题[3]。


为虾米?一方面,智能手机的普及和移动网络的提速,都使得 UGC 越来越容易,浏览和发布动态越来越碎片化,数量陡增。以前用户消费无压力的时间线feed,开始出现信息过载或者错过一些更感兴趣的内容了。另一方面,时间线feed 的确不利于商业化的开展,试想一下微博只要在时间线中插入广告,就有用户不满,但同时那些企业微博,段子号又赚得盆满钵满。


兴趣feed,也有很多高大上的叫法:NewsFeed(Facebook)、SmartFeed(Pinterest)、智能feed(微博曾尝试过),也有叫作 Aggregated Feed 的。它本质上是对传统的时间序feed按照与用户兴趣的相关程度重排序展示。


简言之:时间线看不完了,信息过载了,就按兴趣给你挑选。凡是搞过推荐系统的,或者被推荐系统搞过的人,看到“信息过载”四个字,可能都会自然滴分泌多巴胺,因为那意味着你有用武之地了。




[1] https://blog.twitter.com/2015/while-you-were-away-0

[2] https://blog.twitter.com/2016/never-miss-important-tweets-from-people-you-follow

[3] http://blog.instagram.com/post/141107034797/160315-news


二、关于 Facebook NewsFeed,看这一篇就够了!


NewsFeed 怎么来的


2004年,Facebook 问世,两年后的9月份,NewsFeed 问世,同时问世的还有MiniFeed(个人动态)。今年是 NewsFeed 上线十周年了,这10年里,Facebook 是怎么一步一步把 NewsFeed 打造成了日收入几千万美金的现金牛的?不管你对这充满铜臭的问题感不感兴趣,反正我很感兴趣。


今天我们都已经习惯了把照片、文字等内容主动分享给好友,但是当时 Facebook 上线了这个功能时,引起了广泛的争议,焦点就是“隐私”问题,用户认为我发的动态怎么能让别人看见呢[1]?用户一直不停质疑和抗议,又忍不住继续使用,Facebook 就这样在争议声中增加了最初的隐私控制,比如隐藏自己的动态,而 NewsFeed 就这样坚持了下来。看来,小扎真是一个撩妹高手,看穿了用户们“嘴上说不要,身体却诚实”的内在。


随着用户们渐渐地爱上了浏览好友的分(xuan)享(yao)了,2009年,Facebook 加上了赞(like)功能(FriendFeed 在2007年发明了赞按钮,FriendFeed 后来于2009年被 Facebook 收购,并将赞这个功能整合进来),开始按照热门程度对 Feed 重排序,不出意外,这又引起了用户们的反抗,因为大家已经习惯按照时间顺序阅读。


伴随这么多争议,为什么 Facebook 一直坚持做兴趣feed?从数据上看,平均每个用户每天待看的新鲜事有1500条之多,但平均每个用户每天只能阅读300条;从商业角度,将 Feed 排序交给上帝的做法,非常不利于商业化且有损用户体验,公共主页可以使用很多伎俩吸引用户关注,然后肆无忌惮发广告。


10年来,NewsFeed 有数不清的改进,甚至每天线上会同时部署很多算法版本进行AB测试。但 EdgeRank 是这条优化迭代之路上的一个标志性建筑。我们可以将 NewsFeed 排序策略按照 EdgeRank 分为 PreEdgeRank 时代、InEdgeRank 时代、PostEdgeRank 时代。


EdgeRank 算法


EdgeRank,顾名思义,就是对边(Edge)进行排序(Rank)[2]。


每一个朋友的每一个操作(Action)都可能以新鲜事(News)的方式呈现在用户面前,比如朋友发布了一条新鲜事,朋友赞了朋友的朋友一条新鲜事,朋友评论了朋友的朋友一条新鲜事,朋友给自己的照片加了一个标签,等等。稍微用脚后跟想一想就知道,按照这样罗列的话,每个用户得看多少新鲜事?于是 FB 就想在一条动态呈现给一个用户之前,先预估一下这个用户对这条新鲜事感兴趣程度。在 FB 的定义下,一个 Action 就是一个 Edge,所以这套量化兴趣的算法就叫做 EdgeRank。


别看今天 Facebook 各种高大上,又是深度学习又是人工智能,要知道,在 EdgeRank 提出之前,FB 也是有过刀耕火种时代的,FB 的首席产品官 Chris Cox 谈及早期 NewsFeed 是这样说的[3]:


“In the beginning, News Feed ranking was turning knobs. Turn up photos a little bit, turn down platform stories a little bit.”(最初,NewsFeed 排序就是在主观拍脑袋,给照片加点权重,给平台动态消息降点权重)


“a photo might be worth 5 points, while joining a group was worth 1 point” (把照片权重定为5,把加群权重定为1)


详析兴趣feed:从理论到技术要点


国内算法工程师们听到这些,想必都要会心地笑了:原来 FB 也是从这个时代走过来的。但 Facebook 不同的是,这只是暂时的情形,他们已经走到更高级的阶段了。


Serkan Piantino 在2010年左右领导并开发了第一版 EdgeRank 算法[4]。下面说说大名鼎鼎的 EdgeRank 是怎么回事。


详析兴趣feed:从理论到技术要点

EdgeRank 主要有三个因素在起作用:


  • 亲密度(Affinity Score)

  • 边的权重(Edge Weight)

  • 新鲜程度(Time Decay)


想象一条内容诞生后,途经什么路径流动到你的面前?


  1. 首先经你的一个朋友(或者你的关注源)的之手产生了一条新鲜事(他发布、赞、加标签这些产生了新鲜事);

  2. 然后经过你这个朋友(或者你的关注源)的介绍,到了你家门口,你一开门(登录)就可能看见它;

  3. 内容不多时,开门一个一个寒暄可能还行,它们也等得起,也无所谓先来后到,内容太多时,就得考虑个先来后到了。


这三个步骤,就大致刻画了 EdgeRank 的思想了,其实还是很简单直接的。


亲密度对应了第二个步骤背后的思想,那么多人介绍过来,我们当然要优先照顾更“喜欢”的人了,亲密度的量化要考虑平常里你和这个朋友“走动”是否频繁,连接是否紧密。主要考虑下面几点:


  1. 你们连接的强度,点赞之交,还是评论之交,或是私信之交,连接方式不同,强度就不同;

  2. 你们连接的频繁程度,一日百赞,还是百日一赞,差别也很大;

  3. 你们有多久没有建立连接了,一年没有了,关系自然就更淡了;

  4. 亲密度是单向的,也就是说你对朋友的亲密度,和朋友对你的亲密度可能不一样哦。


你看,看似神秘的 EdgeRank 算法,其实跟大家不太待见的鸡汤居然意思是一样的,是不是觉得它竟然如此平易近人?


边的权重也很直接,其实它反映了产生一条新鲜事的成本,成本越高的,权重越大。点赞、评论、发一条文字、发一张照片、发一个链接,背后用户付出的成本不一样,反应在边的权重上也就不一样。显然,你点个赞的成本,和你发布一条新鲜事的成本差别很多。


最后,新鲜程度,也是一个符合直觉的自然假设:NewsFeed 总是青睐 New 一些的 Feed,新的新鲜事总体上更可能得到用户的临幸。FB 用了一个类似指数衰减的函数来量化动态的新旧程度。


三个分数,最终用相乘的方式共同作用于每一条新鲜事的分数,用于排序和筛选。


这个排序方法的确是很简单,基本上只考虑了社交方面的因素,而没有考虑太多内容本身对用户吸引力。


从公开的资料看 EdgeRank,并不是什么高深的算法,它只是量化了三个主要因素,然后主观地相乘,而没有任何目标优化思想在背后,根据 Facebook 披露的消息看,早期的 EdgeRank 的确没有引入机器学习,所以根本称不上是智能的算法。


为什么 EdgeRank 这么有名?因为它是在F8开发者大会上公开介绍过的,经过一知半解的媒体渲染,变成了一个神秘高深的存在。


后 EdgeRank 时代


2011年之后,Facebook 内部就不再提 EdgeRank 算法了,因为用户数和广告主的飞增,导致 NewsFeed 的排序算法必须要更上一层楼。如今月活跃超过10亿用户,约2000万的公共主页,移动设备贡献了大多数流量,复杂的上下文因素,必须引入机器学习才能 Hold 住整个场面。


在原来 EdgeRank 的基础上,更加细致地定义了不同层级的亲密度。用深度神经网络理解图片内容和文字内容[5],从而可以知道相片中的物体是不是用户感兴趣的,可以知道新鲜事的讨论话题。随着产品迭代,也加入了更多产品特征,诸如阅读时间长短、视频内容、链接内容等,取关、隐藏一个源。前前后后一共考虑了10万+的变量(模型的特征空间应该会更高),如果还按照原来的方式去调节权重,显然既不科学又很低效。


从 Facebook 的机器学习应用博客页面可以看到,2010年之后就开始逐渐有机器学习方面的文章出现了[5]。


相关资料显示[6],2011年之后的 NewsFeed 排序算法,全面转向了机器学习,用优化理论来决定每个因素的权重,将人从繁杂的策略量化中解放出来。在被机器学习接管后的 NewsFeed,很多地方都更加细致。


用机器学习预估新鲜事的质量[7]。通过构造了一份问卷调查,访问了若干用户来收集数据,用收集的数据构建了一个机器学习模型,用于 NewsFeed 排序时预测一条动态的质量,将预测的质量分数作为最终排序的一个特征。用树模型构造离散特征,结合最常见的LR模型预估广告点击率[8]。


除了全面转向机器学习之外,NewsFeed 团队也在重新思考人和算法的关系。他们要关心的是到底“如何把用户真正最关心的找出来”,而不仅仅是“提高点击率”。Facebook 一直是数据驱动的,也是他们能够在争议中把 NewsFeed 坚持下来的信念来源,而是不是唯数据马首是瞻,团队内部有很多思考,也有很多变化。


仅举几例:


  • 团队发现有85%的隐藏新鲜事操作来自5%的人,经过与这些用户沟通才发现,原来这5%的人把“隐藏”当作邮件里的“标记已读”了,对喜不喜欢的新鲜事只要看过就会点击隐藏。

  • 对于悲伤的事情,用户可能关心但不会点赞的。

  • 对于有些点赞,用户可能并不是真的感兴趣,只是“点赞狂魔”发狂而已。

  • 用户阅读一篇长帖子,读到一半不读了,也并不能说明他对这篇帖子不感兴趣。


这些 case,都让他们开始关注到机器学习和数据的局限[9]。


于是,在算法团队之外,Facebook 搭建了一个遍布全球的人肉评测小组。人肉评测小组不是简单地对算法筛选结果进行喜欢/不喜欢的标注,而是会非常深入地阐述为什么喜欢/不喜欢算法筛选结果,而且会与工程师详细交流评测结果,因为这种人肉评测方式可以有效地拆穿数据说谎,让产品远离一味追求提高数据指标的怪圈。


除此之外,产品上还加强了过滤器功能(Filter):你可以选择你的动态给谁看,你可以选择不看谁的动态(Hide),你也可以选择优先看到谁的动态(See first),当然你可以取消关注一些人或者公共主页,将这些控制权交给用户,一方面安抚了用户被算法接管的不安,另一方面也是一项重要的数据来源。事实上,如今的过滤器已经复杂到大多数用户都不会使用这些控制权。


“如何衡量用户真的感兴趣”这个问题也许远远没有最终答案,为什么?因为人的非理性占据了绝大多数时候,而“不一致性”又是非理性的最重要表现,根据心情不同,用户有不同的感兴趣的标准,而且这些标准也许还是相互矛盾的。


NewsFeed 的配套设施


NewsFeed 存在的前提是要依赖用户建立大量的社交联系,这样才会出现信息过载,因此 NewsFeed 的一个重要的配套设施就是“你可能感兴趣的人”(People you may like)推荐系统。


这是一个我们在产品形式上比较熟悉的推荐系统,它是一套大规模矩阵分解算法[10],利用已有的协同矩阵为你推荐你可能想建立联系的新Item,包括用户、app、公共主页等。


NewsFeed 还有另一个配套设施,也是它为什么每天能吸金几千万刀的原因:广告系统。Facebook 的广告形态多样[11]:


  • Suggested Page (你可能喜欢的公众页)

  • Page Post (公众号帖子推广)

  • Suggested App (你可能喜欢的应用)

  • Video Ads (视频广告)


现在,每一次 NewsFeed 调整算法都会引来广告主们的抗议,他们都是在 FB 上拥有公共主页的商业机构。


在以前,FB 鼓励这些商业机构花钱投广告增加粉丝,彼时的 NewsFeed 算法允许随意发广告(以原生的新鲜事形式)。而现在,FB 严格限制商业广告和普通用户的触达。商业机构感觉自己被耍了,花钱买粉之后却不能发原生广告,无独有偶,根据微博 CEO(@来去之间)在微博上的披露,现在微博企业号也是被限制博文达到粉丝 feed 次数的[12]。


据国外某专门做 NewsFeed 推广的公司追踪,1000个公共主页的50000条内容以原生方式触达用户的比例,从2012年16%降低到了2014年的6.51%,降了一倍还多,这当然也可能因为用户平均关注的公共主页增多了[13]。


详析兴趣feed:从理论到技术要点

世界上最遥远的距离,就是:手握大把粉丝,却不能随心所欲地曝光自己的产品。


当然,所有的公共主页们,不要灰心,并不是没有办法,NewsFeed 的广告系统大门永远向你们敞开。


对 NewsFeed 的展望


具体 NewsFeed 会怎么发展,无法预测,但是可以肯定的有三点:


  1. NewsFeed 的算法会一直进化下去。

  2. NewsFeed 团队把人和算法的关系处理得更好,从数据驱动(Data-Driven)到数据启示(Data-Informed)。

  3. 越来越多的 Feed 型产品会效仿 NewsFeed,加入到兴趣feed的潮流中去。




[1] https://en.wikipedia.org/wiki/Criticism_of_Facebook#News_Feed_and_Mini-Feed

[2] http://edgerank.net/

[3] http://marketingland.com/edgerank-is-dead-facebooks-news-feed-algorithm-now-has-close-to-100k-weight-factors-55908

[4] https://research.facebook.com/serkan-piantino

[5] https://research.facebook.com/publications/machinelearning

[6] http://www.dailydot.com/technology/facebook-news-feed-algorithm-edgerank/

[7] https://www.facebook.com/business/news/News-Feed-FYI-Showing-More-High-Quality-Content

[8] https://pdfs.semanticscholar.org/daf9/ed5dc6c6bad5367d7fd8561527da30e9b8dd.pdf

[9] http://www.slate.com/articles/technology/cover_story/2016/01/how_facebook_s_news_feed_algorithm_works.html

[10] https://code.facebook.com/posts/861999383875667/recommending-items-to-more-than-a-billion-people/

[11] http://zhihu.com/question/20553088/answer/78721851

[12] http://weibo.com/1111681197/D0qNcDlcc

[13] http://techcrunch.com/2014/04/03/the-filtered-feed-problem/


三、Pinterest 的 Smart Feed 架构与算法


详析兴趣feed:从理论到技术要点


Pinterest 的本意是协同收集创意内容的工具,看到感兴趣的内容就把它钉(Pin)在板上(Board)。虽然 Pinterest 自己不认为自己是社交网络,但是它允许人关注人,关注兴趣,本质上就是社交网络了。


Pinterest 把 feed 改成兴趣feed是2014年的事情,也引起了不少争议,甚至你在 Google 搜索 Pinterest Smart Feed 能看到以下场景:


详析兴趣feed:从理论到技术要点


这都按下不表,世间互联网产品改版的遭遇大抵如此,只不过有的坚持下来,有的赶紧下线。


相对于 Facebook 的讳莫如深, Pinterest 在其官方技术博客上相对详细披露了其架构和算法的一些技术细节[1],本篇综合 Pinterest 的官方技术博客进行解读,窥探一个现有的兴趣feed是怎么实现的。


Pinterest 产品特点


Pinterest产品有几个关键元素:


  • Pin:采集或者采集的内容(既有名词含义,又有动词含义)。

  • Piner:采集内容的人。

  • Board:看板,内容集合。

  • Interest:兴趣,标签或分类。


用户在 Pinterest 上可以关注一个人,关注一个分类,看到感兴趣的内容可以 Pin 一下到已有的 Board 来。


所以,Pinterest 的首页 Feed 就包括三种:


  1. 来自你关注的人收集的 Pin。

  2. 跟你已采集的内容相似或相关的内容。

  3. 来自你关注的分类的内容。


Pinterest 架构概览


Pinterest 的首页 feed 有这么几个要求:


  1. Pin 的不同发表源要按照一定比例混合后展示。

  2. 有选择地(按照权重)不展示或者推迟展示某些 Pin。

  3. Pin 一定要按照“好坏”来排序,而不是按照“新旧”排序。


第三点很显然,“好坏”其实就是对用户的价值来说,否则就不是 Smart Feed 了,你也一定会认为我该吃药了。


整个首页 feed 后端主要模块逻辑如下:


详析兴趣feed:从理论到技术要点


非常清晰,整个结构逻辑上由三部分构成:

  • Worker

  • Content Generator

  • Service


Worker


Worker可以认为是后台作业模块,最苦最累的活都在这里,其任务有两个:


  1. 接收数据源产生的新 Pin,决定这个 Pin 该推送给哪些用户,并针对每一个它该推送的用户,给出这个 Pin 对这个用户的吸引程度,俗称“打分”。

  2. 存储这些经过打分的 Pin,备用。


什么?你问用什么算法给 Pins 评分的?你们这些搞算法的就是猴急,上来就问G点在哪,后面会专门讲到,不要急,也不要快进,我们继续看看 Worker 是怎么回事。


详析兴趣feed:从理论到技术要点


前面说到,Pins 一共来自三个地方,每一个 Pin 都会结合用户来打分,这决定了它会不会出现在这个用户的 Feed 里。


打了分的 Pin 就会根据其不同来源分开存储(Pool)。存储结构是一个优先队列,按照打分排序,新的 Pin 进来和原来(但用户还未看)的 Pins 一起排序。


这个存储的 Pool 可以直接用 KV 数据库顶上,HBase,Redis 都可以,每次送入数据库的数据是一个三元组:(user, pin, score)。


具体到 Pinterest,他们选用的是 HBase[3][5]。一共有两个 HBase 集群,一个存还没看过的 Pin,一个存已经看过的 Pin。


详析兴趣feed:从理论到技术要点


解释一下这个图。


  1. Zen(中文名字叫禅,有意境)是个专门封装向 HBase 存储图模型(社交网络的基本模型[4])数据的,抽象了很多 HBase的 基本操作。

    当数据源产生了新的 Pin 之后,需要由一个叫 PinLater 的模块经过 Zen 推送给粉丝。这里推送是异步的,有几秒到几分钟的延迟[2]。每一个新的 Pin 产生,都是异步地进行,并不会影响后面的 Content Generator 和 Service。

    PinLater 是一个自己研发的分布式任务队列,开源替代品有 Celery,非常好用,下一篇会介绍。

  2. materialized content 就是“旧”内容,它是和新内容分开存的。


另外,Pinterest 还在不同机房有一个热备 HBase 集群,对主集群的任何操作都会同步到这个热备集群上,一旦主集群挂了,热备集群就顶上去。


Content Genreator


详析兴趣feed:从理论到技术要点


如图,Conent genreator 就是在用户登录后或者手动刷新时会触及的关键服务了。


当用户登陆上来后,会向 Content generator 请求“新的” Pins。这个模块最主要的责任就在这里:给出新的 Pins。这里所说的“新” Pins 就是用户没看过的。


具体它要做的就是:


  1. 决定返回多少个 Pins,数量不是固定的,会根据用户访问频繁程度,以及上次看到的新内容多少决定。

  2. 分配来源的比例构成,这块没有透露怎么分配比例,我们可以猜一下,也许是固定比例,也许是有一些启发式算法。

  3. 将 Pins 排成一定的顺序,按照分数排序就好了。

  4. 待推送内容要从 Pool 中删除,以保证每次请求的都是没看过的。


每一次产生的待推送内容合在一起叫做一个“块”(chunk)。


Feed Service


详析兴趣feed:从理论到技术要点


Feed service 就是提供前端的服务了。为了提供高可用服务,service 的任务有二个:


  1. 接收从 generator 返回的“新”内容。

  2. 新内容合并上一次的“旧”内容。


Service 不对内容顺序做任何修改,只是把新旧内容合并在一起,同时还要保证服务的高可用。


  1. 如果 generator 当掉了,service 就会优雅降级:返回上一次推送的内容。这时候从用户端看到的效果就是还没有产生新内容。

  2. 如果上一次发生了优雅降级,那么用户本次访问时获得的新内容会比正常要多。


总体架构逻辑上很清晰,每个模块的分工很明确。据 Pinterest 说,整个应用的流量1/3都来自首页,可想而知,首页架构必须要高可用。而且,Pinterest 内部对服务的要求是99.99%情况下不出错。


总结一下,这个架构关键有几点保证了服务的高可用:


  1. 内容产生后给粉丝采用异步的推模式(PinLater)。

  2. HBase 集群采用冗余备份,并且新旧内容分开存储。

  3. Service 和 Generator 分离,当事故发生时优雅降级。


Pinterest排序算法


好了,我知道大家都很关心 SmartFeed 的算法。


答案揭晓:名字叫做 Pinnability[6]。


我们可以翻译成“可Pin度”,可Pin度是一组机器学习模型,用于衡量一个用户对一条 Pin 产生互动的可能性。


详析兴趣feed:从理论到技术要点


在 Pinnability 诞生之前,Pinterest 的 Feed 一点也不 Smart,就是最简单的时间排序。但和 Facebook 不同的是,Pinterest 改成兴趣feed之后直接就上了机器学习,而没有走 EdgeRank 这样的中间状态。


详析兴趣feed:从理论到技术要点


时间序很简单直接。


Pinnability 模型用到的机器学习算法都是比较常用的模型:


  1. Logistic Regression(逻辑回归)。

  2. Support Vector Machines(支持向量机SVM)。

  3. Gradient Boosted Decision Trees(GBDT,梯度提升树)。

  4. Convolutional Neural Networks (CNN,深度学习之卷积神经网络)。


整个 Pinnability 的模型流程是:


详析兴趣feed:从理论到技术要点


pipeline 分为三个阶段:


  1. 准备训练数据

  2. 训练模型

  3. 上线使用


准备训练数据的时候主要就是对样本采样和特征生成,因为曝光样本远多于正样本,严重不平衡的类别分布,需要对负样本采样(展示给用户但没产生互动的)。


模型用到特征目前有几千个,相比 Facebook 的 NewsFeed 少了一些。 这里有文本特征,还有图像特征(CNN也用于这里)。


特征有三类:


  1. Pin 本身的特征,包含内容特征,一些统计特征如历史热度之类, 新鲜程度,是垃圾的可能性。

  2. 产生这个 Pin 的用户特征,比如活跃度,性别,看板状态等。

  3. 互动特征,待推送的这个用户之前和类似的 Pin 互动程度。


每条训练样本包含三部分:目标值(正负样本)、特征、元数据(一些ID类,时间戳等,用于在MapReduce阶段分割样本,用于交叉测试)。


模型训练时尝试了上面列的所有算法,用 AUC 做为模型的主要评价指标,发现同样的特征集合,基本上都是 LR 和 GBDT 表现最好。


确定算法之后,特征选择也是必须的,做了很多特征筛选工作,保留了最具区分性的特征。每次模型更新训练之后,先用历史数据做离线测试,然后上线AB测试,最后再全局铺开。根据 Pinterest 的博客显示,他们目前还是离线批量学习,在线使用,还没有做到实时更新参数,毕竟据说只有不到20人的公司。


模型上线之后就是以一个服务形式存在,当 PinLater 把新的 Pin 和要推送的用户发送过来后,就逐一去预测每个用户可能会对该 Pin 产生互动的概率,将概率做为分数返回,通过 Zen 存储进 HBase 集群中。


Smart Feed 给我们的启示


太shi公曰:Smart Feed 的架构平易近人,算法司空见惯,都是类似“多喝热水、重启一下”的常规方法,奈何其产品竟然如何成功。国内也有仿 Pinterest 的,先有花瓣网,后有微博倾全公司之力做了微刊,均没有 Pinterest 这么成功,介是为嘛呢?


现在关灯,我们一起闭眼思考思考。




[1] https://engineering.pinterest.com/blog/building-smarter-home-feed

[2] https://engineering.pinterest.com/blog/pinlater-asynchronous-job-execution-system

[3] https://engineering.pinterest.com/blog/building-scalable-and-available-home-feed

[4] https://engineering.pinterest.com/blog/building-follower-model-scratch

[5] http://www.slideshare.net/cloudera/case-studies-session-3a

[6] https://engineering.pinterest.com/blog/pinnability-machine-learning-home-feed


四、通用兴趣Feed的技术要点


一句废话:兴趣feed,就是按照兴趣相关重排序的feed。


温馨提示:要搜索 feed 相关技术文章,你应该用 Activity Stream 作为关键词去搜,而不应该只用"feed"搜索。Activity Stream 之于 Feed,就好比多潘立酮之于吗丁啉。


详析兴趣feed:从理论到技术要点

整体逻辑


要实现一个兴趣feed,整体逻辑上是比较清楚的。可以划分为两个子问题:


  1. 如何实现一个 feed 系统?

  2. 如何给 feed 内容重排序?


我们先给出整体的逻辑框架,然后再分别详谈。

详析兴趣feed:从理论到技术要点
数据模型


Feed 的基本数据有三个:用户(User)、内容(Activity)和关系(Connection)。 用户不用说,就是区别不同用户的身份。重点说一说 feed 的数据模型。


内容即 activity。表达 activity 的元素有相应的规范,叫做 Atom[1],可以参考它,并结合产品需求,定义出自己的feed数据模型来。


根据 Atom 的定义,一条 Activity 包含以下元素:


  1. Time: activity 发生的时间。

  2. Actor: activity 由谁发出的?通常 actor 就是用户ID,但是我们也可以扩展到其它拟人化物体上,如关注的一个“店铺”,收藏的一部“电影”

  3. Verb: 动词,这个 activity 是哪一个动作?比如“follow”,“like”等

  4. Object: 动作作用到最主要的对象,只能有一个

  5. Target: 动作的最终目标,与 verb 有关,可以没有。它对应英语中介词to后接的事物,比如"John saved a movie to his wishlist"(John保存了一部电影到清单里),这里电影就是 Object,而清单就是 Target。

  6. Title: 这个 activity 的标题,自然语言描述

  7. Summary: 通常是一小段 HTML 代码,是对这个 activity 的描述,还可能包含类似缩略图这样的可视化元素,可以理解为 activity 的 view,不是必须的。


举个例子: 2016年5月6日23:51:01(Time) @刑无刀(Actor) 分享了(Verb) 一条微博(Object) 给 @ResysChina (Target)。Title 就是前面这句话去掉括号后的内容,Summary 暂略。


除了上面的字段外,还有一个ID,用于唯一标识一个 activity。社交电商 Etsy 在介绍他们的feed系统时,还创造性地给 activity 增加了 Owner 属性,同一个 activity 可以属于不同的用户[2]。


关系即连接。互联网产品里处处皆连接,有强有弱,好友关系,关注关系等社交是较强的连接,还有点赞,收藏,评论甚至浏览,这些动作都可以认为用户和另一个对象之间建立了连接。有了连接,就有 feed 的传递和发布。


定义一个连接的元素有:


  1. from: 连接的发起方

  2. to: 被连接方

  3. type/name: 连接的类型/名字,关注,加好友,点赞,浏览,评论,等等

  4. affinity: 连接的强弱


如果把建立一个连接视为一个 Activity 模型的话,from 就对应 Activity 中的 actor,to 就对应 Activity 中的 object。


将整个社交网络视为一个图。可以按照 from节点的邻接表来分解其中林林总总的连接关系。


连接的发起从 from 到 to,内容的流动从 to 到 from。Connection 和 Activity 是相互加强的,蛋和鸡的关系:有了 Activity,就会产生 Connection,有了 Connection,就可以喂(feed)给你更多的 Activity。


已有的轮子

  • Activity 存储: mysql/redis/cassandra

  • Connection 存储: mysql

  • User 存储: mysql


Feed 发布


用户登录/刷新后,feed 是怎么产生的?内容出现在受众的 feed 中,这个过程称为 Fan-out。


我们的直觉上是这样实现的:

  1. 获取用户所有连接的终点(如好友或者关注对象)

  2. 获取这些连接终点(关注对象)产生的新内容(Activity)

  3. 排序后输出


上面这个步骤别看简单,在一个小型的社交网络上,通常还是有效,而且twitter的早期也是这么做的[3]。


详析兴趣feed:从理论到技术要点


这就是行话说的“拉”模式(Fan-out-on-load),feed 是在用户登录/刷新后实时产生的。


详析兴趣feed:从理论到技术要点
“拉”模式的好处有目共睹:


  1. 实现简单直接:一行sql就搞定了

  2. 实时:内容产生了,受众只要刷新就看得见


但是不足也是大写的:


  1. 随着连接数的增加,这个操作的复杂度是指数级增加的,显然不可取。

  2. 内存中腰保留每个人的产生的内容

  3. 服务很难做到高可用


与之对应,还有一个“推”模式(Fan-out-on-write)。

详析兴趣feed:从理论到技术要点
当一个 Actor 产生了一条 Activity 后,不管受众在不在线,刷没刷新,立即将这条内容推送给相应的用户(和这个 actor 建立了连接的人),系统为每一个用户单独开辟一个 feed 存储区域,用于接收推送的内容。如此一来,当用户登录后,系统只需要读取他自己的 feed 即可。


推模式的好处显而易见:在用户访问自己的feed时,几乎没有任何复杂的查询操作,所以服务可用性较高。


推模式的不足:


  1. 大量的写操作:每一个粉丝都要写一次

  2. 大量的冗余存储:每一条内容都要存储N份(受众数量)

  3. 非实时:一条内容产生后,有一定的延迟才会到达受众feed中


既然两者各有优劣,那么实际上就应该将两者结合起来。


一种简单的结合方案是全局的:


  1. 对于活跃度高的用户,使用推模式,每次他们刷新时不用等待太久,而且内容页相对多一些

  2. 对于活跃度没有那么高的用户,使用拉模式,当他们登录时才拉取最新的内容

  3. 对于热门的内容生产者,缓存其最新的N条内容,用于不同场景下拉取


还有一种结合方案是分用户的,这是 Etsy 的设计方案[2]:


  1. 如果受众用户与内容产生用户之间的亲密度高,则优先推送,因为更可能被这个受众所感兴趣

  2. 如果受众用户与内容产生用户之间的亲密度低,则推迟推送或者不推送

  3. 也不是完全遵循亲密度顺序,而是采用与之相关的概率


在中小型的社交网络上,采用纯 push 模式就够用了,结合的方案可以等业务发展到一定规模后再考虑。


已有的轮子


  • 用户feed的存储: redis, uid为key

  • feed推送的任务队列: celery


celery是一个开源的分布式异步任务队列,python语言,它与常用的消息队列(redis, RabbitMQ等)结合使用,很容易做到水平扩展。


用户只需要定义任务处理方法即可,其余的celery都帮你处理了。还可以将多个处理方法串成一个异步的chain,从而构建自己的pipeline。


celery还能做定时任务,周期任务。


具体到兴趣feed系统中,每当一个用户发布一条动态,我们就产生一个celery的任务,这个任务就是做兴趣预测和动态推送,它是准实时的异步任务,不会阻塞feed的读取和写入。


排序算法


兴趣feed的排序,要避免陷入两个误区:

  1. 没有目标

  2. 人工量化


第一个误区意思就是:设计排序算法之前,一定要先弄清楚为什么要对时间序重排?希望达到什么目标?我们这里假设兴趣排序要提高互动率:即希望用户对feed里面的内容互动比例越高越好。所以这里的目标就是:提高互动率。只有先确定目标,才能检验和优化算法。


第二个误区是人工量化。也就是我们通常见到的产品同学或者运营同学要求对某个因素加权、降权。这样做很不明智,因为人的知识利于做启发,不利于做量化。我们很多算法理论上可以得到最优参数,但是所需时间可能是无法承受的,这时候如果有丰富领域知识的人给一些有用的信息,就能大大缩小算法参数的搜索空间,从而在可接受的时间内搜索到效果可以接受的参数。


人可以告诉算法很多可能有用的排序因素,缩短效果提升的路径,但是人直接指定参数的权重,对效果提升来说基本上有百害而无一利。


基于上述经验,我们从机器学习思路来简单设计一个优化互动率的兴趣feed。


首先,定义好互动行为包括哪些,比如点赞,转发,评论,查看详情等。 其次,区分好正向互动和负向互动,比如隐藏某条内容,点击不感兴趣等是负向的互动。


基本上到这里就可以设计成一个典型的二分类监督学习问题了,对一条feed的内容,在展示给用户之前,预测其获得用户正向互动的概率,概率就可以作为兴趣排序分数输出。


能产生概率输出的二分类算法都可以用在这里:贝叶斯,最大熵,逻辑回归等。互联网常用的是 Logistic Regression,谁用谁知道,反正用过的都说好:

  1. 线性模型,足够简单

  2. 产生0-1之间的输出,互相可以比较

  3. 开源实现多,初始技术成本小

  4. 工业界已经反复验证过


分类器需要特征输入,一条feed内容推送给一个用户,特征可以分三类:

  1. 用户特征,包括用户人口统计学属性,用户兴趣标签,活跃程度等。

  2. 内容特征,一条内容本身可以根据其属性提取文本、图像、音频等特征,并且可以利用 Topic Model 提取更抽象的特征。

  3. 其他特征,比如刷新时间,所处页面等。


在算法选定后,人工可以花很多力气在寻找新特征上,这就是传说中的“特征工程”,特征工程还包括对已有的特征进行选择,选择的目的是:

  1. 控制模型的维度,降低复杂度

  2. 去掉信号小的特征,提高效果


工程上常用的特征选择有很多,可以参考我的朋友严林在知乎上的答案[5]。 关于特征工程,还可以参考[6]。工程上,特征工程比算法要重要很多,方法有一些,但是领域差别大,具体不再赘述。


在线使用排序算法时,可以做成 RPC 服务,以供发布feed时调用。


已有的轮子


  • RPC 框架:thrift,FB开源,支持多语言,包括C、C++、Java、Python、PHP等

  • 模型训练:vowpal wabbit,分布式机器学习框架,可以和Hadoop轻松结合

  • 特征工程:python (ipython notebook) 或者 R (RStudio Server).


数据和效果追踪


既要通过历史数据来寻找算法的最优参数,又要通过新的数据验证排序效果。 所以搭建一个数据流通的 pipeline 也是兴趣feed系统必须的。


相关数据:

  1. 目标有关的互动行为数据(记录每一个用户在feed上的操作行为)

  2. 曝光给用户的内容(一条曝光要有唯一的ID,曝光的内容仅记录ID即可)

  3. 互动行为与曝光的映射关系(每条互动数据要对应到一条曝光数据)

  4. 用户profile(提供用户特征,来自离线挖掘和数据同步)

  5. feed内容分析数据(提供内容特征)


对于一个初级的兴趣feed,没必要做到在线实时更新排序算法的参数,所以数据的 pipeline 可以借鉴 Pinterest 的 pipeline,具体见第三部分。


详析兴趣feed:从理论到技术要点

如果选用 LR 预测互动行为排序feed的话,在离线时关注模型的 AUC[7] 是否有提升。AB测试时关注具体的产品目标是否有提升,比如互动率等,同时还要根据产品具体形态关注一些辅助指标。


另外,互动数据相比全部曝光数据,数量会小得多,所以在生成训练数据时需要对负样本(展示了却没有产生互动的样本)进行采样,采样比例也是一个可以优化的参数,固定算法和特征后,在0.1-0.9之间遍历对比实验,选择最佳的正负比例即可,经验比例在2:3左右,即负样本略大于正样本,你可以用这个比例做启发式搜索。


已有的轮子

  • 日志存储:HDFS

  • 训练样本生成:Hive

  • 效果追踪:Hive


其他


还需要有:

  1. 一个提供 feed API 的服务

  2. 系统指标收集及监控

  3. 服务监控及管理


已有的轮子

  • feed API: tornado

  • 监控指标收集:StatsD,Nodejs 服务

  • 监控指标可视化:Graphite,Django 服务

  • python进程管理:supervisor

  • API 反向代理:nginx


最后的最后


本文逐一梳理了实现一个通用兴趣feed的关键模块,及其已有的轮子,从而能最大限度的降低开发成本。


这些对于一个中小型的社交网络来说已经足够,当你面临更大的社交网络,会有更多复杂的情况出现,尤其是系统上的。所以,壮士,请好自为之,时刻观察系统的监控,日志的规模。


最后再补充三点:


  1. 准备上兴趣feed之前先想清楚,是否真的需要这样做。

  2. 以上整个系统框架已有开源实现,作者本人也是把剧本演到最后才发现:如不自宫,也可成功[8]。


[1] http://activitystrea.ms/specs/atom/1.0/

[2] http://www.slideshare.net/danmckinley/etsy-activity-feeds-architecture

[3] http://www.slideshare.net/nkallen/q-con-3770885

[4] http://www.slideshare.net/cevin/timyang

[5] https://www.zhihu.com/question/28641663/answer/41653367

[6] http://machinelearningmastery.com/an-introduction-to-feature-selection/

[7] https://en.wikipedia.org/wiki/Area_under_the_curve_(pharmacokinetics)

[8] https://github.com/tschellenbach/Stream-Framework


作者简介:陈开江@刑无刀

  1. 2013年之前在新浪微博搜索部和商业产品部任资深算法工程师,先后负责过微博反垃圾、基础数据挖掘、智能客服平台、个性化推荐等产品的后端算法。

  2. 2012-2013领导翻译了《机器学习:实用案例解析》一书。

  3. 2013年末加入传统媒体公司车语传媒,任算法主管,负责从零打造公司转型产品考拉FM的个性化推荐系统,如今个性化推荐已成为考拉FM与其他FM之间最大差异化特性。

  4. 2015年初,离职创业,公司拿到IDG和晨兴资本的天使投资,产品几经调整,如今专注在用视频分享购物经验,App名称:边逛边聊。


版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。


-END- 详析兴趣feed:从理论到技术要点

架构文摘

ArchDigest

架构知识丨大型网站丨大数据丨机器学习

详析兴趣feed:从理论到技术要点

更多精彩文章,请点击下方:阅读原文

原文始发于微信公众号(架构文摘):详析兴趣feed:从理论到技术要点

以上就是:详析兴趣feed:从理论到技术要点 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论