Netflix_Prize_中的协同过滤算法

吴金龙导师：鄂维南、李铁军2010-05-28吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法2PartI：背景介绍推荐系统NetflixPrize协同过滤（CollaborativeFiltering）问题PartII：协同过滤（CollaborativeFiltering）模型评分预测模型模型组合方法PartIII：三维协同过滤：立方填补应用背景评分预测模型PartIV：总结与展望吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法3推荐系统NetflixPrize协同过滤（CollaborativeFiltering）问题吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法4PartI：背景介绍——推荐系统依据信息检索的方式，互联网的发展可分为三个阶段门户网站阶段，典型代表为Yahoo为互联网上的重要信息提供导航搜索引擎阶段，典型代表为Google依据用户输入的关键词，返回给用户与关键词相关的网页个性化推荐阶段依据用户的特点和需求，为用户提供个性化的服务推荐系统作用利用历史，预测现在与未来常用领域传统的零售行业互联网行业搜索引擎：Google电子商务：Amazon社会化网络服务（SNS）：Facebook吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法5PartI：背景介绍——推荐系统基于内容的过滤（content-basedfiltering，简记为CBF）根据事先抽取出的产品或用户特征产生推荐主要缺点需要预处理产品以得到代表它们的特征无法发现用户并不熟悉但具有潜在兴趣的产品种类协同过滤（collaborativefiltering，简记为CF）收集用户过去的行为以获得其对产品的显式或隐式信息优点不需要预处理产品或用户的特征，故而不依赖于特定的应用领域主要缺点冷启动：对于新用户或新产品，无法产生可靠推荐可扩展性：算法往往需要较大的时间和空间复杂度两者的组合（hybrid）组合上面两种方法，以克服它们各自的缺点，并融合它们特有的优点吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法6PartI：背景介绍——NetflixPrizeNetflix：美国一家提供在线电影租赁服务的公司2006年10月，Netflix建立了NetflixPrize竞赛，并对外发布了一个电影评分（评分为1,…,5的整数）数据集NetflixPrize竞赛最终的目标是在Cinematch推荐系统的基础上获得10%的改进，其预测精度由均方根误差（RMSE）来衡量：GrandPrize，奖金为一百万美元第一个达到10%改进的参赛团队ProgressPrize，奖金为五万美元每年排名第一的参赛团队吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法7PartI：背景介绍——NetflixPrize给出了整体训练数据集（WTS）中的评分值及对应的评分时间参赛团队提交整个QualifyingSet上的预测评分值CompleteNetflixPrizeDataset480,189个用户17,770部电影FirstPartofTrainingSet(FPTS)99,072,112个评分HeldOutSet(HOS)4,225,526个评分WholeTrainingSet(WTS)100,480,507个评分ProbeSetQuizSetTestSet吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法8PartI：背景介绍——NetflixPrize2009年6月26日团队BellKor’sPragmaticChaos(BPC)的提交在QuizSet上获得0.8558的预测误差，改进首次超过10%，竞赛进入最后三十天角逐2009年9月10日NetflixPrize官方正式宣布BPC为竞赛的最终胜利者，获得GrandPrize，整个竞赛正式结束已颁发的奖项及获奖团队奖项获奖团队TestRMSEProgressPrize2007KorBell0.8723ProgressPrize2008BellKorinBigChaos0.8627GrandPrizeBellKor’sPragmaticChaos0.8567吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法9PartI：背景介绍——NetflixPrize极度稀疏性WTS中包括了480,189个用户对17,770部电影的评分，而评分值只有100,480,507个，也即近99%的评分值未知长尾性大部分用户只对极少的电影进行了评分四分之一的用户只对少于36部电影进行了评分大部分电影只收到极少的用户评分四分之一的电影只收到少于190个用户的评分时间性数据集中评分的特点随着时间的变化在不断变化吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法10PartI：背景介绍——推荐系统矩阵填补问题给定矩阵的少部分元素，预测其它未知元素的值E.Candèsetal.(Found.ofComput.Math.,2008;SIAMJ.onOptimization,2008;Proc.ofIEEE,2009;…)探讨了矩阵填补的理论和算法但他们的算法目前还无法应用于实际数据集产品1产品2产品3……产品M用户113??用户22?24用户3??4?用户45?53…………………………用户U?3?2吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法11常用模型邻居（kNN）模型受限玻尔兹曼机（RBM）模型因子模型矩阵分解（MF）模型二项矩阵分解（BMF）模型修正模糊聚类（MFCM）模型模型组合方法吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法12PartII：CF模型——常用模型邻居（kNN）模型（R.Belletal.,ICDM,2007;G.Takácsetal.,SIGKDD,2007;…）根据相似用户对此电影的评分（或此用户对相似电影的评分）获得推荐特点易于编程实现好的可解释性空间复杂度很高受限玻尔兹曼机（RBM）模型（R.Salakhutdinovetal.,ICML,2007）一层隐藏单元（hiddenunits）H代表用户特征一层可视化单元（visibleunits）R代表评分特点好的预测精度时间复杂度很高吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法13PartII：CF模型——Factor因子模型假设（R.Bell&Y.Koren,ICDM,2007;A.Paterek,1stNetflix-KDDWorkshop,2007;…）每个用户和电影都可由少数若干个因子来刻画当一个用户和某部电影的因子向量相匹配时，此用户会对该部电影给予高的评分原始因子模型（通常称为矩阵分解模型）的表达式为其中和分别为用户和电影的潜在因子矩阵上述表达式是奇异值分解的一种简化形式吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法14PartII：CF模型——Factor因子模型vs.邻居模型因子模型可以获得更高的预测精度因子模型vs.受限玻尔兹曼机模型因子模型需要更少的训练时间吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法15PartII：CF模型——Factor——MF矩阵分解模型（MatrixFactorization，简记为MF）可以看成是一种有向图模型（D.Lin&L.Mackey,2007;R.Salakhutdinov&A.Mnih,NIPS,2008;ICML,2008）吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法16PartII：CF模型——Factor——MF用户和电影的因子向量各自满足正态分布且相互独立用户u对电影m的评分随机变量满足均值为，方差为的正态分布以上的正态分布对于不同的u或m是相互独立的吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法17PartII：CF模型——Factor——MFMF假设在给定因子向量时，用户u对电影m的评分变量满足正态分布此假设对于离散协同过滤（CF）问题并不合理例如，对于NetflixPrize问题，真实的评分只在{1,2,3,4,5}内使用多项分布表示评分（Marlin,NIPS,2003;master’sthesis,2004）但多项分布的各个取值之间是无序的，它可能是多峰的（multimodal）的我们建议使用二项分布表示评分（J.Wu,ICDM,2009）吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法18PartII：CF模型——Factor——BMF使用二项分布表示评分的直观意义对于NetflixPrize问题，用户可以给予一部电影1至5颗用户以某个固定的喜好程度把每颗星星放入两篮（“喜爱”与“不喜爱”）中的其中一个其中的喜好程度与相应的用户和电影有关最终获得的评分即满足二项分布，如上图中评分为3吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法19PartII：CF模型——Factor——BMF用户和电影的因子向量各自满足正态分布且相互独立用户u对电影m的评分随机变量满足二项分布其中的S为界定允许评分范围的定值（对于NetflixPrize问题，S=5），而偏好参数吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法20PartII：CF模型——Factor——BMFBMF中因子P和Q的对数后验分布为使用两种方法最大化此后验分布或数据似然梯度上升法（GradientAscent）BMF算法变分EM法（VariationalEM）PBMF算法算法的具体过程见博士论文P56-60或J.Wu(ICDM,2009)吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法21PartII：CF模型——Factor——实验结果当固定因子数K=40，惩罚系数λ分别为0.025和0.0015时，算法MF和BMF获得的预测误差见下表对于两个算法，更小的学习率都可以产生更低的预测误差，但同时算法的收敛速度也变得更慢逐渐降低学习率经过77次迭代后算法BMF的ProbeRMSE降至0.9098具体过程见博士论文P70-71或J.Wu(ICDM,2009)学习率η算法MF算法BMF迭代步数ProbeRMSE迭代步数ProbeRMSE0.004470.923738270.9181980.002910.916908560.9133620.0011820.9136631150.9107210.00053610.9119192310.909483吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法22PartII：CF模型——Factor——实验结果当因子数K取不同值时，算法PMF和PBMF获得的ProbeRMSE随着迭代步数的变化图吴金龙@SMS.pku.edu.cn(2010-05-28)NetflixPrize中的协同过滤算法23PartII：CF模型——Factor优势程序容易实现较低的时间和空间复杂度（使用梯度上升法求解）可以获得很好的预测精度劣势推荐结