吴金龙吴金龙导师：鄂维南、李铁军2010-05-28吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法2Part I：背景介绍推荐系统 Netflix Prize 协同过滤（Collaborative Filtering）问题 Part II：协同过滤（Collaborative Filtering）模型评分预测模型 模型组合方法 Part III：三维协同过滤：立方填补应用背景 评分预测模型 Part IV：总结与展望吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法3推荐系统 Netflix Prize 协同过滤（Collaborative Filtering）问题吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法4Part I：背景介绍推荐系统依据信息检索的方式，互联网的发展可分为三个阶段 门户网站阶段，典型代表为 Yahoo为互联网上的重要信息提供导航 搜索引擎阶段，典型代表为 Google依据用户输入的关键词，返回给用户与关键词相关的网页 个性化推荐阶段 依据用户的特点和需求，为用户提供个性化的服务 推荐系统 作用 利用历史，预测现在与未来 常用领域 传统的零售行业 互联网行业 搜索引擎：Google 电子商务：Amazon 社会化网络服务（SNS）：Facebook吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法5Part I：背景介绍推荐系统基于内容的过滤（content-based filtering，简记为 CBF） 根据事先抽取出的产品或用户特征产生推荐 主要缺点 需要预处理产品以得到代表它们的特征 无法发现用户并不熟悉但具有潜在兴趣的产品种类 协同过滤（collaborative filtering ，简记为 CF） 收集用户过去的行为以获得其对产品的显式或隐式信息 优点 不需要预处理产品或用户的特征，故而不依赖于特定的应用领域 主要缺点 冷启动：对于新用户或新产品，无法产生可靠推荐 可扩展性：算法往往需要较大的时间和空间复杂度 两者的组合（hybrid） 组合上面两种方法，以克服它们各自的缺点，并融合它们特有的 优点吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法6Part I：背景介绍Netflix PrizeNetflix ：美国一家提供在线电影租赁服务的公司 2006年10月，Netflix建立了Netflix Prize竞赛，并对外发布了一个 电影评分（评分为1, , 5的整数）数据集 Netflix Prize竞赛最终的目标是在Cinematch推荐系统的基础上获得 10%的改进，其预测精度由均方根误差（RMSE）来衡量：Grand Prize，奖金为一百万美元 第一个达到10%改进的参赛团队 Progress Prize，奖金为五万美元每年排名第一的参赛团队吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法7Part I：背景介绍Netflix Prize给出了整体训练数据集（WTS）中的评分值及对应的评分 时间 参赛团队提交整个Qualifying Set上的预测评分值Complete Netflix Prize Dataset480,189个用户 17,770部电影First Part of Training Set (FPTS)99,072,112 个评分Held Out Set (HOS) 4,225,526 个评分Whole Training Set (WTS)100,480,507 个评分Probe SetQuiz SetTest Set吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法8Part I：背景介绍Netflix Prize2009年6月26日 团队BellKors Pragmatic Chaos (BPC)的提交在Quiz Set上获得0.8558 的预测误差，改进首次超过10%，竞赛进入最后三十天角逐 2009年9月10日 Netflix Prize官方正式宣布BPC为竞赛的最终胜利者，获得Grand Prize，整个竞赛正式结束 已颁发的奖项及获奖团队奖项获奖团队Test RMSE Progress Prize 2007KorBell0.8723 Progress Prize 2008BellKor in BigChaos0.8627 Grand PrizeBellKors Pragmatic Chaos0.8567吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法9Part I：背景介绍Netflix Prize极度稀疏性 WTS 中包括了480,189个用户对17,770部电影的评分，而评分值只 有100,480,507个，也即近99%的评分值未知 长尾性 大部分用户只对极少的电影进行了评分 四分之一的用户只对少于36部电影进行了评分 大部分电影只收到极少的用户评分 四分之一的电影只收到少于190个用户的评分 时间性 数据集中评分的特点随着时间的变化在不断变化吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法10Part I：背景介绍推荐系统矩阵填补问题 给定矩阵的少部分元素，预测其它未知元素的值E. Cands et al. (Found. of Comput. Math., 2008; SIAM J. on Optimization, 2008; Proc. of IEEE, 2009; ) 探讨了矩阵填补 的理论和算法 但他们的算法目前还无法应用于实际数据集产品1产品2产品3 产品M 用户113? 用户22?24 用户3?4? 用户45?53 用户U?3?2吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法11常用模型 邻居（kNN）模型 受限玻尔兹曼机（RBM）模型 因子模型 矩阵分解（MF）模型 二项矩阵分解（BMF）模型 修正模糊聚类（MFCM）模型 模型组合方法吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法12Part II：CF模型常用模型邻居（kNN）模型 （R. Bell et al., ICDM, 2007; G. Takcs et al., SIGKDD, 2007; ） 根据相似用户对此电影的评分（或此用户对相似电影的评分）获得 推荐 特点 易于编程实现 好的可解释性 空间复杂度很高 受限玻尔兹曼机（RBM）模型 （R. Salakhutdinov et al., ICML, 2007） 一层隐藏单元（hidden units）H 代表用户特征 一层可视化单元（visible units）R 代表评分 特点 好的预测精度 时间复杂度很高吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法13Part II：CF模型Factor因子模型假设（R. Bell A. Paterek, 1st Netflix-KDD Workshop, 2007; ）每个用户和电影都可由少数若干个因子来刻画 当一个用户和某部电影的因子向量相匹配时，此用户会对该部电影 给予高的评分 原始因子模型（通常称为矩阵分解模型）的表达式为其中 和 分别为用户和电影的潜在因子矩阵 上述表达式是奇异值分解的一种简化形式吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法14Part II：CF模型Factor因子模型 vs. 邻居模型因子模型可以获得更高的预测精度 因子模型 vs.受限玻尔兹曼机模型因子模型需要更少的训练时间吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法15Part II：CF模型Factor MF矩阵分解模型（Matrix Factorization，简记为MF）可以看成是 一种有向图模型 （D. Lin R. Salakhutdinov ICML, 2008）吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法16Part II：CF模型FactorMF用户和电影的因子向量各自满足正态分布且相互独立用户u 对电影m 的评分随机变量 满足均值为 ， 方差为 的正态分布以上的正态分布对于不同的 u 或 m 是相互独立的吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法17Part II：CF模型FactorMFMF假设在给定因子向量时，用户 u 对电影 m 的评分变量满 足正态分布此假设对于离散协同过滤（CF）问题并不合理 例如，对于Netflix Prize问题，真实的评分只在1, 2, 3, 4, 5内 使用多项分布表示评分（Marlin, NIPS, 2003; masters thesis, 2004）但多项分布的各个取值之间是无序的，它可能是多峰的（ multimodal）的 我们建议使用二项分布表示评分（ J. Wu, ICDM, 2009）吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法18Part II：CF模型FactorBMF使用二项分布表示评分的直观意义 对于Netflix Prize问题，用户可以给予一部电影1至5颗用户以某个固定的喜好程度把每颗星星放入两篮（“喜爱”与“不喜 爱”）中的其中一个其中的喜好程度与相应的用户和电影有关最终获得的评分即满足二项分布，如上图中评分为 3吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法19Part II：CF模型FactorBMF用户和电影的因子向量各自满足正态分布且相互独立用户u 对电影m 的评分随机变量 满足二项分布其中的S为界定允许评分范围的定值（对于Netflix Prize问题，S=5） ，而偏好参数吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法20Part II：CF模型FactorBMFBMF中因子P和Q的对数后验分布为使用两种方法最大化此后验分布或数据似然 梯度上升法（Gradient Ascent） BMF算法 变分EM法（Variational EM） PBMF算法 算法的具体过程见博士论文P56-60 或 J. Wu (ICDM, 2009)吴金龙 SMS.pku.edu.cn (2010-05-28)Netflix Prize 中的协同过滤算法21Part II：CF模型Factor实验结果当固定因子数K = 40，惩罚系数分别为0.025和0.0015时， 算法MF和BMF获得的预测误差见下表对于两个算法，更小的学习率都可以产生更低的预测误差 ，