算法改变未来：NetFlix百万美金数据建模大奖的故事（下）

叶子颜

也许你会问：改进一个算法怎么会需要漫长的三年时间？

        当时参赛的多数选手也是这么问的。当 NETFLIX 最初宣布了竞赛规则之后，许多人认为这个问题并不难，答案就像是挂在一棵矮树上的果子，似乎伸手可得。开赛后的几个月里，就有参赛者把原有的 Cinematch 算法准确性提高了 5%。比赛进行一年多时，最好的答案已经非常接近 9%。可是事实证明，那最后的 1% 才是真正的攻坚战。

        获奖团队的名字叫 BPC （BellKor's Pragmatic Chaos），它由原本是竞争对手的三个团队重新组团而成，其中的七个成员分别来自奥地利、加拿大、以色列和美国，他们的职业身份分别是电脑工程师、统计学家和人工智能专家。这七个人原来分属的三个参赛团队都是曾经保持最好成绩的顶尖团队，他们的重新组合使得 BPC的实力大增，如虎添翼。但是，直到最后参加颁奖仪式时，这七个成员在领奖台上才是第一次真正面对面握手相见。原来他们是通过互联网来进行合作的，这里又一 次显示了互联网的好处；这种跨学科、跨组织的异地合作标志着今后高效科研的方向，互联网成为科研突破的重要工具；组建国际团队、实行虚拟合作也成为科学工 作者的必备能力。

        获奖团队 BPC 中有两位来自于 AT&T 实验室，名叫 Chris Volinsky 和 Robert Bell。 Chris 是分管 AT&T 研发的执行总管，他们参加这项为期三年的 NETFLIX 百万大奖赛利用了他们的工作时间，因此他们所获的奖金归 AT&T 所有，这就是所谓的 “Work for hire” 的成果。最后，AT&T 把这笔奖金捐给了当地的教育慈善机构和中小学，以鼓励青少年从事科学、技术、工程、数学（STEM）方面的学习和工作。

        有趣的是，BPC团队最终险胜了另一个参赛团队叫The Ensemble，这个团队也是由几个名列前茅的前参赛团队重新组合而成的新团队。根据比赛规则，各个团队的得分精确到小数点后第四位，我们来看看这两个参赛小组的最后得分：

        The Ensemble 的 RMSE 测试分数： 0.856714，对 Cinematch 算法的改进： 10.06%

        Bellkor's Pragmatic Chaos 的 RMSE 测试分数： 0.856704，对 Cinematch 算法的改进： 10.06%

        我们在后面再讨论什么是 RMSE 测试分数，仅就最终结果看，两个小组都达到并超过了 NETFLIX 的比赛目标，对原有算法的改进都超过了 10%。遗憾的是，The Ensemble 小组在提交最后结果时比 BPC 小组晚了二十分钟。“时间就是金钱”在这里有了绝妙的注解，尽管这两个团队的算法效率非常接近，因为 The Ensemble 小组晚了二十分钟，他们就与奖金无缘，只能望洋兴叹。

        在总结这次赛事时，NETFLIX 的首席执行官哈庭斯说：“我们经历了一次非常激烈的比赛，参赛团队开始时候独立作战，后来协同作战，终于将影片推荐效率提高到了 10％ 以上。在接近比赛截止日期时，还有新的参赛作品不断快速地提交上来，让整个比赛过程变得非常曲折和惊心动魄。”要知道，把这个算法的预测效率提高10％以 上可不是一件轻而易举的事，这个效率目标是 NETFLIX 的科学家们在过去的十年里面都没有办法逾越的瓶颈。

        随着一百万美金大奖的颁发，NETFLIX 很快宣布了第二个百万美金大奖。

        第一个百万大奖成功地解决了一个巨大的挑战，为已有评级的观众准确地预测了他们的口味和对新影片的喜好。第二个百万大奖的目标是，为那些不经常做影片评级或者根本不做评级的顾客推荐影片，这就要求使用一些隐藏着观众口味的地理数据和行为数据来进行预测。如果能解决这个问题，NETFLIX 就能够很快向新客户推荐影片，而不需要等待客户提供大量的评级数据后才能做出推荐。新的比赛用数据集有一亿条数据，包括评级数据，顾客年龄，性别，居住地 区邮编，和以前观看过的影片等信息。

        尽管所有的数据都是匿名的，没有办法把这些数据直接关联到 NETFLIX 的任何一位顾客，但是把顾客的年龄、性别、居住地邮编等信息公开让许多人感到不安。美国联邦政府交易委员会开始关注这项大赛对顾客隐私的损害，有一家律师事务所也代表客户递交了对NETFLIX的诉状。为了防止官司缠身，NETFLIX 在 2010 年 3 月宣布取消了第二个百万美金大奖赛。

        获胜的团队的名字叫 Bellkor's Pragmatic Chaos，这个名字其实是由三个领先团队组合起来的：第一个是来自 AT&T 统计研究部的 BellKor，第二个是来自加拿大蒙特利尔的 Pragmatic Theory，第三个是来自于奥地利的 BigChaos。这种最优合并的方法也出现在其它参赛的团队里，比如这次竞赛的第二名 The Ensemle 团队就有三十几名成员，他们都是在前期比赛阶段获得较好成绩的选手，后来自愿重新组合，最终在竞赛中脱颖而出。

        每一位参赛者都有自己的强项和弱项，团队重组可以使参赛者之间取长补短，优化合作。这种优势互补的方法也适用于不同算法之间的合并，事实上，探讨优秀算法之间的强强结合已经成为一个很活跃的研究方向。

        NETFLIX 在这次大赛中使用两组数据：第一组数据是用户对电影的评的历史数据，它有 100480507 条，这是由 480189 名用户从 1999 年到 2005 年这六年间对 17770 部电影的评级数据，这组数据是用来让参赛者进行数据挖掘和数据分析的，如下图中的绿色左段所示。这组数据是公开数据，参赛者根据对这种数据的分析、挖掘研 究而建立自己的模型和算法，并用这组数据对该算法进行训练和修正。

        第二组数据被用来测试算法的可靠性和精确性，这组数据不对参赛者公开，只被裁判用来测试参赛者的算法效果。裁判们用来评判算法优劣的标准是均方根误差 RMSE （root mean squared error），它是误差平均数的平方根，用来表明实际观测值和预测值之间的平均误差水平，其计算公式如下：

        RMSE = .sqrt{.frac{.sum_{i=1}^{n}{( y_i-.tilde{y_i} )^{2}} }{n} }

        获胜团队 BPC 的算法的高明之处在于考察了用户评级数据中的时间和“频率”，用户在为影片打分时往往带有情绪影响，而情绪是与时间有关的。另外，用户的口味也许随着时间 的变化而变化；对比一位用户五年之前的打分和他最近的打分，肯定他最近的打分更为准确地反映了他当前的好恶标准，在决定他明天可能喜好哪些电影时所起的作 用更大。于是 BPC 团队就研究用户评分的结果与他们打分的时间以及频率之间的关系，建立了相关性模型。比如用户在周一和周五在打分时所用的标准有差异，有些用户在周日的情绪 最好，这时所打的分数比平时偏高。通过这样的分析，他们能更精确地发现用户对电影的喜好口味，进而对他们打分的规律预测得更为准确。

        实际的算法带有几个控制常数，需要在运行过程中精细调整，以便得出最佳的RMSE 结果。要详细解释这个算法需要许多数学准备知识，这里就不赘述了。NETFLIX 的产品总监杭特博士解释了这个算法的重要性，他说,“成功地预测客户分别喜欢哪些影片是我们服务中一个非常关键的环节。个性化推荐的极端的例子是你进入了一间有 10 万部影片的商店，那些你最感兴趣的影片马上就能在你的面前排成了一排，让你尽快地发现自己要看的影片。我们用预测模型来为顾客推荐影片，相信我们的顾客一 定会非常享受这项服务”。

        互联网络正从一个“搜索知识”的 时代进入一个“发现知识”的时代，推荐引擎无所不在。它能为你推荐看什么电影，读什么文章，听什么音乐，买什么商品等等。搜索引擎需要一个庞大的数据库和 快速搜索算法，推荐引擎需要有一个精确的用户模型和预测决策算法；搜索引擎注重于数据，推荐引擎侧重于知识；两者相比，开发推荐引擎的难度更高。

        随着算法的不断改进，推荐技术越来越普遍地应用，计算机会不会越来越多地介入我们的日常生活，甚至于控制人类？在现实生活中，有时候我们并不十分清楚自己是 否肯定需要某个东西，或者不完全清楚自己的具体需求，在这样的时候，计算机就像一位善解人意的私人秘书一样帮助你做些推荐，这是很不错的进步。当然像推荐 引擎这样的技术应用如果过于泛滥，无孔不入，当人们过于依赖于机器的时候，它对人类生活的副作用也不容忽视。