Press "Enter" to skip to content

用ADMM优雅地做推荐系统(WSDM2020)

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

最近看到一篇WSDM 2020的文章ADMM SLIM [0], 用得是优化的方法却比sota的deep learning方法表现还好 ,觉得很有趣,想分享一下。先讨论一下如何把推荐建模成优化问题和如何用ADMM解这个优化问题;最后就个人理解讨论一下这套方法与深度学习方法之间的关系,感兴趣的同学可以往下看。

 

然后说一下本文各部分出处,emmm这篇文章也是拼出来的,ADMM介绍内容来自香港科技大学张潼老师的课件,ADMM SLIM来自[0]。对于这些内容我也是一知半解(特别是推荐系统部分),所以如果有哪里错了请一定指出来!

 

本文分成一下几个部分:

 

Part I: 推荐系统建模

 

Part II: 用ADMM解推荐问题

 

Part III: ADMM-SLIM为何比深度学习效果好?

 

Appendix A: ADMM详细介绍

 

Appendix A.A: 增广拉格朗日与Proximal Point Method

 

Appendix A.B: ADMM, Preconditioned ADMM, Accelerated Linearized ADMM

 

Part I: 推荐系统建模

 

首先我们有一个评分矩阵,它大概长下面这个样子。我们希望从已经打分的数据当中推测出用户没有打分的那些电影(空白部分)的分数,把推测出的高分的数据推荐给用户。

推荐系统一个比较常用的假设呢,就是用户对不同电影打分是有关联的。比如上表当中M2和M3都是偶像剧,喜欢M2的用户也喜欢M3,反之亦然。

 

表示第i个用户对第j个电影的 已经打了的分数 , 表示我们 估计 的第p个用户对第q个电影的打分。我们希望从第i个用户已经打分的电影 当中推测出用户i对某个没有打分的 的分数。在着名的slim [1]文章当中假设这个关系式是线性的

 

 

其中 是我们要从训练数据当中学习的系数矩阵。

 

推荐分为训练和测试两个阶段。在推荐阶段,我们知道groundtruth的打分矩阵,所以可以解下面这个优化问题来得到

 

 

下面这个constraint是用来避免 这个trival solution的。为了防止过拟合,我们常常会加一些l1和l2的正则化,比如下面这样 [0]

 

 

在测试阶段,我们已经有了系数矩阵 和一个用户i部分打分数据 。我们可以根据已有打分 来估计剩下的分数

 

 

然后推荐分数最高的几个给用户。

 

Part II: ADMM-SLIM

 

有了问题的建模(1),下面就是解这个问题了,在文章当中采用了ADMM算法。ADMM一般用来解长下面这个样子的问题

 

 

它的算法长这个样子

我们只要把(1)写成(2)的样子就可以用ADMM解决这个问题了,具体的,我们把(1)进行一些变形

 

 

其中

 

i) 我们先看Algorithm 2当中的第一步(line2)更新 ,更新方法是

 

 

其中 是矩阵。(3)式子要求最值所以我们令argmin里面求导等于0

 

 

上面的式子可以转化为element-wise的形式,即

 

 

其中 ,所以最优解分类讨论一下

 

 

这个 就是大名鼎鼎的soft shrinkage operator啦!

 

综上,第一步更新是

 

 

ii) 再看Algorithm 2的第二步(line3)更新 ,更新方法是

 

 

其中 是一个矩阵,(a) 部分对应 , ,

 

(4)当中剩下一个要求的拉格朗日乘子 ,需要从约束条件 当中求出,我们有

 

 

所以在(4)当中 ,这样我们就完成了第二步更新也就是(4)。

 

iii) Algorithm 2第三步(line4)可以原封不动地抄下来。

 

到这里,我们就完全推导出了这个推荐方法的所有步骤啦!效果嘛比深度学习的方法高到不知道哪里去了(下图前三大行)。

Part III: ADMM-SLIM为何比深度学习效果好?

 

原文当中光说了效果好,并没有太多的解释以及与深度学习方法的比较,我这里斗胆揣测一下原因,因为之前不了解推荐方面的知识,说错了请大家一定要指出来。

 

这里考虑下面这个简化的建模,有着和文章当中方法相当的结果(效果是上图第二大行的第一小行)

 

 

和auto-encoder深度学习方法的关系: 这篇文章对比的深度学习的方法就是基于auto-encoder的方法(DAE和VAE),这里目标函数当中的 也可以看成是一个autoencoder 的loss。注意到如果采用denoising autoencoder输入有噪声的 ,label是没有噪音的 ,如果我们做无穷多次data-augmentation,有

 

 

所以这个方法也是一个DAE。值得注意的是,这个模型的参数大大高于之前的深度学习的方法,比如对于表现最好的MSD数据集 admm-slim方法有 1.6Billion个参数 ,个人感觉参数量的增大也起到了效果。

 

和GNN深度学习方法的关系: 考虑一个线性的GNN,初始的item feature是 ,经过一次item to user message passing是 ,再经过一次user to item message passing 是 ,考虑多层线性GNN加上jumping knowledge最后的feature是

 

 

在(5)的解当中有

 

 

所以它其实是一个无穷多层的线性的JKGNN的特例。感觉如果用设计一个JKGNN的话效果应该会比admm slim还好!

 

和着名的SLIM [1] 的关系: 这篇文章和slim的区别是去掉了 的约束条件,效果大大好于SLIM。个人在看SLIM的时候感觉 这个约束条件不是很合理,电影之间有正相关性也有负相关性,而且去掉这个条件模型的表达能力提升了。

 

Appendix A: ADMM详细介绍

 

在写这篇知乎之前,我去看了一下香港科技大学张潼老师优化课的课件,搞懂了一些之前没搞懂的ADMM的问题,在这里记录一下算是一个小笔记吧。

 

ADMM考虑这样一个问题

 

 

Appendix A.A: 增广拉格朗日与Proximal Point Method

 

在优化当中,为了提高收敛性,我们常常在目标函数上面加一个二次项让目标函数是 -strongly convex

 

 

拉格朗日函数长下面这个样子

 

 

直接优化这个问题就是Method of Multipliers算法

这里有一件比较神奇的事情是method of multipliers等价于对偶变量的proximal point ,我们下面来证明这件事情。对偶变量的proximal point算法长这个样子

 

 

其中 是问题(6)的对偶问题

 

i) 对于增广拉格朗日,我们把Algorithm 1 line2的first order optimality写出来

 

 

其中的等号是代入Algorithm 1的line3。解得

 

 

利用对偶的性质[2],(8)可以转化为

 

 

ii)对于proximal point (7),我们先整理一下

 

 

把(10)代入令(7)求导等于0

 

 

把(9)代入(11)得到

 

 

综上,(9)就是Algorithm 1的line2,(12)就是Algorithm 1的line3,所以对偶变量的proximal point算法就是原始变量的增广拉格朗日。

 

Appendix A.B: ADMM, Preconditioned ADMM, Accelerated Linearized ADMM

 

ADMM: Algorithm 1的line2当中x和z couple在一起,很难求,所以ADMM把求解x和z的步骤分成两步,每步求解一个变量。

Preconditioned ADMM: 对于general的线性约束 , 在ADMM当中需要解这幺一个问题

 

 

这个问题不经常有close-form的解,如果能变成proximal operator的话就经常有close-form的解了,所以考虑在算法这一步里面加上一项消掉前面的B,这个就是preconditioned ADMM

其中 用来消掉前面的B。

 

Accelerated Linearized ADMM: 上面说的是关于g(z)的那一步不好求,在有一些机器学习的问题当中关于f(x)那一步不好求,要怎幺办呢?那就把f展开成二次的就行啦!

 

 

这样我们就有了(accelerated) linearized admm

算法在SVM上表现大概这样子

参考文献

 

[0] ADMM SLIM: Sparse Recommendations for Many Users

 

[1] SLIM: Sparse Linear Methods for Top-N Recommender Systems

 

[2] 原始对偶角度下的几类优化方法

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注