数据挖掘系列篇：Facebook内容排序算法研究

摘要：最近研究了下Facebook内容排序问题，这个在新浪微博、知乎内容排序这些场景下都应用到。主要是关于edgerank的算法讨论以及Facebook的AB test机制。

EdgeRank 是Facebook 在 F8 开发者大会上提出的对 fb 新鲜事 (Feeds) 排序的新算法, 用于区别默认的按时间逆序的 timeline。

要解决的问题就像@宋一松介绍到的：

Edgerank 是几年前外界对Facebook Newsfeed上的新鲜事排序算法的称呼。

至于是怎么算的，这其实可以出成一道面试题，不妨以知乎为例。题目就是，你觉得应如何对知乎的新鲜事排序

具体问题描述：

知乎用户刘看山，他关注了100个人，30个专栏，10个话题。在他打开知乎的一瞬间，将有100个最新动态等着他，你要怎么给这100个新鲜事排序

当然，作为知乎官方，你掌握着几乎所有知乎用户的信息，包括刘看山的。他经常给谁点赞，经常关注哪个话题下面的问题，这些你都知道。

哦，对了，你只有50毫秒时间。超过50毫秒刘看山就会不耐烦了。

你该怎么办

0. 这些新鲜事对用户而言质量各有高低

如果你让刘看山自己看一遍这100个新鲜事，他大概能说出自己更喜欢哪个，更不喜欢哪个。比如，他更喜欢张佳玮的答案，张公子的回答他基本都会点开看。他不太喜欢抖机灵的回答，即使赞同数很高他也只是扫一眼就过去。

我们要做的，就是用模型化的语言描述这件事。

1. 确定一个变量作为优化目标

这个变量，要能反映新鲜事的质量。一组常用的变量就是互动数：点开，赞同，感谢。好的新鲜事应该能吸引到更多的互动，这样的新鲜事也更应该排在前面。

当然另一方面，用什么变量来定义成功其实不是一个简单的问题。Twitter的创始人之一 Evan Williams 就曾发文警告用单一变量定义成功的危险性。我们在这里也可以考虑其他信号，比如说，被很多用户点选“没有帮助”的新鲜事很可能质量不高，又或者用户花了很长时间在上面的新鲜事很可能质量不错。于是，“没有帮助”数和阅读时长也可以成为我们的优化目标之一。

2. 预测用户在哪个新鲜事上更可能触发我们的目标变量

或者说，在哪个新鲜事上刘看山更可能点开/赞同/收藏/分享/长时间阅读，在哪个新鲜事上更可能选不再显示/没有帮助，前者要排高点，后者排低点。

这就是机器学习(Machine Learning)派上用场的时候了。具体用什么算法是个开放性问题。可以是Logistic Regression，可以是SVM，还可以是别的，各有各的特点。(真要是做ML的面试题，这里会和选手展开讨论一下)

算法不重要，那什么重要Feature。这就是知乎数据库里的那些数据的作用了。刘看山之前赞过张公子几次，这个回答被总共看了几次并赞了几次，这些都是feature。从历史看未来。Feature是强大的模型的关键。

3. 故事还没有结束

学术上，这个模型已经差不多成型了。然而在实际应用中，很多问题还应付不了。比如说：

刘看山看到张公子赞了别人的一个回答，大概读了下，没意思，就过去了。后来刘看山所关注的张小北也赞了这个回答。这时候这个新鲜事要怎么排序

刘看山出远门一周没上知乎，回来一上知乎1000个新鲜事可以排序。好不容易排完了，刘看山看了10个就关浏览器了。一个小时之后刘看山再上知乎的时候，之前剩下的990个新鲜事你要怎么办

你会发现，这个问题，与其说是算法，不如说是涉及产品本身的决策。所以说，好的ranking engineer都是半个PM (还有半个Data Scientist和半个Growth Hacker)。

而Facebook内部工程师Lars Backstrom也介绍道：

During a phone call this week, Lars Backstrom, Engineering Manager for News Feed Ranking at Facebook, estimated that there are as many as “100,000 individual weights in the model that produces News Feed.” The three original EdgeRank elements — Affinity, Weight and Time Decay — are still factors in News Feed ranking, but “other things are equally important,” he says.

Facebook已经应用了10万个以上的feature来去排序用户的内容。而这三个最基础的权重因素就是亲密度、权重、时间衰减。

EdgeRank 用于当某个用户查看他的新鲜事时, 决定这些新鲜事先后顺序的一个排序算法. 算法核心是每个事件对这个用户而言的权重 E, 其计算公式是 E = u*w*d, 其中

u, 事件生产者和观察者之间的亲密度

亲密度主要指的是互动情况, 互动越频繁亲密度越高
互动可以是单向的, 比如 A 经常关注 B, 而 B 不怎么关注 A, 那 u(a,b) 和 u(b, a) 的权重不一样

w, 边权重 (主要是事件的类型)

边权重主要受事件类型影响, edgerankchecker 给的关于点击跟其他事件的关系可以大概说明
- i. Avg Clicks Per Like: 3.103
- ii. Avg Clicks Per Comment: 14.678
- iii. Avg Clicks Per Impression: 0.005

d, 时间衰减因子

比较少见到讨论时间衰减因子怎么做的, 猜测是类 log 变化
如果将 EdgeRank 公式只保留 d, 则 EdgeRank 退化到经典 timeline 模式

而就像spooy说的：

Timeline 模式对大多数人来说其实已经够用, 而 EdgeRank 排序后的 Feeds, 并不能有一个很好的效果评判标准. 看用户在 Feeds 模式下是否有比 Timeline 模式更好的体验怎么看用 item 的先后顺序和点击序列做比较很难, 而且因为面对的是有感情的人难保今天我心情好愿意什么都看看, 明天心情不好就只看所谓的感兴趣内容, 那怎么判断某天的效果好坏难不成 fb 还能预测我心情

从大部分广告相关的资料来看, 受 EdgeRank 影响最大的应该是那些企业用户. 以前企业用户可以花比较低的价格建立一个公共主页 (Page), 然后以比常规广告便宜得多的方式获得大量粉丝 (Fans/Follower), 对于这些成为粉丝用户, 企业的新广告就可以以几乎免费的价格推送到这些人的 timeline 中. 显然这样的结果不是 Facebook 乐于见到的, 你们都可以不花钱做广告了, 那我们喝西北风么而且, Facebook 也想通过 EdgeRank 让企业知道, 他的多少粉丝是僵尸粉, 都是没意义的.

回到 EdgeRank 的定义, 相比较 timeline 模式的, 区别就在多出来那两个参数 u 和 w, w 没什么好说的, 可以认为就是简单加权, 或者考虑事件对用户的重要度, u 才是 EdgeRank 的核心所在. 如果 a 跟 b 互动少, 那么 u(a,b) 值变低, 则导致 b 发布的东西在 a 那的排名就会很低, 如果把 a 看成一个粉丝, 而 b 是某企业的主页, 则这个主页发布的消息在这个粉丝这可能就完全看不见了。

所以, 为了保持现有粉丝的有效性, 企业必须经常发布一些互动活动来保持现有粉丝的活跃度, 否则千辛万苦弄来的粉丝都没意义了。而同时为了把那些已经僵尸掉的粉丝挽救回来, 以及扩展新粉丝, 企业还是需要投放大量广告, 这样 Facebook 的广告业务就不会因为公共主页粉丝数变多而衰落, 整个公司也就能一直维持很好的盈利状况了。

参考资料

本文为专栏文章，来自：数据分析侠，内容观点不代表本站立场，如若转载请联系专栏作者，本文链接：https://www.afenxi.com/12765.html 。