Facebook如何向十亿人推荐东西

作者 张天雷 为了保证用户体验和使用效果，推荐系统中的机器学习算法一般都是针对完整的数据集进行的。然而，随着推荐系统输入数据量的飞速增长，传统的集中式机器学习算法越来越难以满足应用需求。因此，分布式机器学习算法被提出用来大规模数据集的分析。作为全球排名第一的社交网站，Facebook就需要利用分布式推荐系统来帮助用户找到他们可能感兴趣的页面、组、事件或者游戏等。近日，[Facebook就在其官网公布了其推荐系统的原理、性能及使用情况](https://code.facebook.com/posts/861999383875667/recommending-items-to-more-than-a-billion-people/)。 目前，Facebook中推荐系统所要面对的数据集包含了约1000亿个评分、超过10亿的用户以及数百万的物品。相比于著名的[Netflix Prize](http://www.netflixprize.com/) ，Facebook的数据规模已经超过了它两个数据级。如何在在大数据规模情况下仍然保持良好性能已经成为世界级的难题。为此， Facebook设计了一个全新的推荐系统。幸运的是，Facebook团队之前已经在使用一个分布式迭代和图像处理平台——[Apache Giraph](http://giraph.apache.org/)。因其能够很好的支持大规模数据，Giraph就成为了Facebook推荐系统的基础平台。 在工作原理方面，Facebook推荐系统采用的是流行的协同过滤（Collaborative filtering，CF）技术。CF技术的基本思路就是根据相同人群所关注事物的评分来预测某个人对该事物的评分或喜爱程度。从数学角度而言，该问题就是根据用户-物品的评分矩阵中已知的值来预测未知的值。其求解过程通常采用矩阵分解（[Matrix Factorization](http://en.wikipedia.org/wiki/Matrix_decomposition), MF）方法。MF方法把用户评分矩阵表达为用户矩阵和物品的乘积，用这些矩阵相乘的结果R’来拟合原来的评分矩阵R，使得二者尽量接近。如果把R和R’之间的距离作为优化目标,那么矩阵分解就变成了求最小值问题。 对大规模数据而言，求解过程将会十分耗时。为了降低时间和空间复杂度，一些从随机特征向量开始的迭代式算法被提出。这些迭代式算法渐渐收敛，可以在合理的时间内找到一个最优解。随机梯度下降（[Stochastic Gradient Descent](http://en.wikipedia.org/wiki/Stochastic_gradient_descent), SGD）算法就是其中之一，其已经成功的用于多个问题的求解。SGD基本思路是以随机方式遍历训练集中的数据，并给出每个已知评分的预测评分值。用户和物品特征向量的调整就沿着评分误差越来越小的方向迭代进行，直到误差到达设计要求。因此，SGD方法可以不需要遍历所有的样本即可完成特征向量的求解。交替最小二乘法（[Alternating Least Square](http://bugra.github.io/work/notes/2014-04-19/alternating-least-squares-method-for-collaborative-filtering/), ALS）是另外一个迭代算法。其基本思路为交替固定用户特征向量和物品特征向量的值，不断的寻找局部最优解直到满足求解条件。 为了利用上述算法解决Facebook推荐系统的问题，原本Giraph中的标准方法就需要进行改变。之前，Giraph的标准方法是把用户和物品都当作为图中的顶点、已知的评分当作边。那么，SGD或ALS的迭代过程就是遍历图中所有的边，发送用户和物品的特征向量并进行局部更新。该方法存在若干重大问题。首先，迭代过程会带来巨大的网络通信负载。由于迭代过程需要遍历所有的边，一次迭代所发送的数据量就为边与特征向量个数的乘积。假设评分数为1000亿、特征向量为100对，每次迭代的通信数据量就为80TB。其次，物品流行程度的不同会导致图中节点度的分布不均匀。该问题可能会导致内存不够或者引起处理瓶颈。假设一个物品有1000亿个评分、特征向量同样为100对，该物品对应的一个点在一次迭代中就需要接收80GB的数据。最后，Giraph中并没有完全按照公式中的要求实现SGD算法。真正实现中，每个点都是利用迭代开始时实际收到的特征向量进行工作，而并非全局最新的特征向量。 综合以上可以看出，Giraph中最大的问题就在于每次迭代中都需要把更新信息发送到每一个顶点。为了解决这个问题，Facebook发明了一种利用work-to-work信息传递的高效、便捷方法。该方法把原有的图划分为了由若干work构成的一个圆。每个worker都包含了一个物品集合和若干用户。在每一步，相邻的worker沿顺时针方法把包含物品更新的信息发送到下游的worker。这样，每一步都只处理了各个worker内部的评分，而经过与worker个数相同的步骤后，所有的评分也全部都被处理。该方法实现了通信量与评分数无关，可以明显减少图中数据的通信量。而且，标准方法中节点度分布不均匀的问题也因为物品不再用顶点来表示而不复存在。为了进一步提高算法性能，Facebook把SGD和ALS两个算法进行了揉合，提出了旋转混合式求解方法。 接下来，Facebook在运行实际的A/B测试之间对推荐系统的性能进行了测量。首先，通过输入一直的训练集，推荐系统对算法的参数进行微调来提高预测精度。然后，系统针对测试集给出评分并与已知的结果进行比较。Facebook团队从物品平均评分、前1/10/100物品的评分精度、所有测试物品的平均精度等来评估推荐系统。此外，均方根误差（Root Mean Squared Error, RMSE）也被用来记录单个误差所带来的影响。 此外，即使是采用了分布式计算方法，Facebook仍然不可能检查每一个用户/物品对的评分。团队需要寻找更快的方法来获得每个用户排名前K的推荐物品，然后再利用推荐系统计算用户对其的评分。其中一种可能的解决方案是采用[ball tree](http://en.wikipedia.org/wiki/Ball_tree)数据结构来存储物品向量。all tree结构可以实现搜索过程10-100倍的加速，使得物品推荐工作能够在合理时间内完成。另外一个能够近似解决问题的方法是根据物品特征向量对物品进行分类。这样，寻找推荐评分就划分为寻找最推荐的物品群和在物品群中再提取评分最高的物品两个过程。该方法在一定程度上会降低推荐系统的可信度，却能够加速计算过程。 最后，Facebook给出了一些实验的结果。在2014年7月，[Databricks公布了在Spark上实现ALS的性能结果](https://databricks.com/blog/2014/07/23/scalable-collaborative-filtering-with-spark-mllib.html)。Facebook[针对Amazon的数据集](https://snap.stanford.edu/data/web-Amazon.html)，基于[Spark MLlib](https://spark.apache.org/mllib/)进行标准实验，与自己的旋转混合式方法的结果进行了比较。实验结果表明，Facebook的系统比标准系统要快10倍左右。而且，前者可以轻松处理超过1000亿个评分。 目前，该方法已经用了Facebook的多个应用中，包括页面或者组的推荐等。为了能够减小系统负担，Facebook只是把度超过100的页面和组考虑为候选对象。而且，在初始迭代中，Facebook推荐系统把用户喜欢的页面/加入的组以及用户不喜欢或者拒绝加入的组都作为输入。此外，Facebook还利用基于ALS的算法，从用户获得间接的反馈。未来，Facebook会继续对推荐系统进行改进，包括利用社交图和用户连接改善推荐集合、自动化参数调整以及尝试比较好的划分机器等。