课外天地 李树青学习天地推荐系统原理课件 → [转帖]深度学习与推荐系统


  共有12007人关注过本帖树形打印复制链接

主题:[转帖]深度学习与推荐系统

帅哥哟,离线,有人找我吗?
admin
  1楼 博客 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信 管理员
等级:管理员 帖子:1938 积分:26572 威望:0 精华:34 注册:2003/12/30 16:34:32
[转帖]深度学习与推荐系统  发帖心情 Post By:2016/5/17 16:23:43 [只看该作者]

今天说说深度学习在推荐领域的应用情况。

也许是最早的,算是与 Deep Learning 沾点儿边的推荐算法,是在 Netflix Prize 竞赛后半程异军突起的 Restricted Boltzmann Machine 算法。当时以 SVD++ 为核心的模型几乎已经陷入了僵局,大家基本进入到了比拼trick与融合模型数量的体力活阶段了。RBM 的出现推动整个竞赛上了一个新台阶,相关的论文「Restricted Boltzmann Machines for Collaborative Filtering」在此[1]。但 RBM 本身大家并不认为和 Deep Learning 有太大关系,因为它太“浅”了,官方论文里面最后也提到了 RBM 一个重要的扩展方向就是「Learning Deep Generative Models」。Netflix 在2014年发表了一篇结合使用 GPU 和 AWS 搞分布式神经网络的博客「Distributed Neural Networks with GPUs in the AWS Cloud」[2],昭告了一下除 Google 之外他们在 deep learning 领域也不容小觑,然而并没有透露太多的应用细节。再多说几句 Netflix Prize,有关 Netflix Prize 对 Netflix Recommendation 带来的改变,可以看看 Netflix 自己的官方博客[3][4],这几乎也可以看做是推荐系统领域最佳的入门资料。关于 RBM,对工业界同学们更具参考价值的是 Edwin Chen 的这篇「Introduction to Restricted Boltzmann Machines」[5],更浅显易懂,还有开源代码实现。然后就是最近,有人号称使用 deep learning 取得了比 Netflix Prize 大奖方案更好的结果[6]。 其他一些值得看看的内容: 音乐是 deep learning 适合发挥优势的领域之一,与 Spotify 相关的 deep learning 应用有两篇报导,一篇是「Recommending music on Spotify with deep learning」[7] 很详尽,另外一篇是把 deep learning 与经典的 collaboritive filtering 结合的尝试,「Recurrent Neural Networks for Collaborative Filtering」[8]。 Google 也发表了一篇音乐相关的 deep learning 论文,「Temporal Pooling and Multiscale Learning for Automatic Annotation and Ranking of Music Audio」[9]。 Netflix 的一位算法研究员作为作者之一的「Session-based Recommendations with Recurrent Neural Networks」[10]。 基于 deeplearning4j 的一个推荐引擎「The WellDressed Recommendation Engine」[11],据说,使用了这个玩意儿的电商网站把 ad coverage 提升了200%。 微软同学在 WWW2015 上的一篇文章,「A Multi-View Deep Learning Approach for Cross Domain User Modeling in Recommendation Systems」[12],讲在新闻和应用推荐领域使用 deep learning 的一些心得。 最后重磅推荐,Netflix 前推荐引擎总监 Xavier Amatriain 在 KDD2014 上的压轴分享,「The Recommender Problem Revisited」[13],得认真啃一啃。 今年的 RecSys 会议,将会第一次专门针对 Deep Learning 与 Recommender Systems 设立一个专门的 workshop,将于今年9月15日在 Boston 举办,[14]这里是一些方向性的题目,有启发。欢迎参加的同学能够带回来相关报道,或者哪个直播平台愿意赞助我去直播一下也是极好的。 抛砖引玉,希望大家多多切磋。 [1] http://www.cs.utoronto.ca/~hinton/absps/netflixICML.pdf [2] http://techblog.netflix.com/2014/02/distributed-neural-networks-with-gpus.html [3] http://techblog.netflix.com/2012/04/netflix-recommendations-beyond-5-stars.html [4] http://techblog.netflix.com/2012/06/netflix-recommendations-beyond-5-stars.html [5] http://blog.echen.me/2011/07/18/introduction-to-restricted-boltzmann-machines/ [6] https://karthkk.wordpress.com/2016/03/22/deep-learning-solution-for-netflix-prize/ [7] http://benanne.github.io/2014/08/05/spotify-cnns.html [8] http://erikbern.com/wordpress.php?p=589 [9] http://ismir2011.ismir.net/papers/PS6-13.pdf [10] http://arxiv.org/abs/1511.06939 [11] http://deeplearning4j.org/welldressed-recommendation-engine.html [12] http://msr-waypoint.com/pubs/238334/frp1159-songA.pdf [13] http://www.kdd.org/kdd2014/tutorials/KDD - The Recommender Problem Revisited.pdf [14] http://dlrs-workshop.org/dlrs-2016/cfp/ 微信公众号【ResysChina】,中国最专业的个性化推荐技术社区。

[此贴子已经被作者于2016-05-17 16:25:07编辑过]

 回到顶部
帅哥哟,离线,有人找我吗?
admin
  2楼 博客 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信 管理员
等级:管理员 帖子:1938 积分:26572 威望:0 精华:34 注册:2003/12/30 16:34:32
AlphaGo 与深度学习  发帖心情 Post By:2016/5/17 16:24:44 [只看该作者]

AlphaGo 对工业界和学术界的影响是深远的,至少对于我来说,他让我直接就把研究方向从其他方面转向了深度学习。从今年2月开始,就一直在研究 AlphaGo 的算法,并尝试自己写围棋程序,一直忙到4月份。最近已经把精力从围棋转向更实际的领域了,所以写一篇文章总结一下。

个人觉得,整个 AplphaGo 对于机器学习来说,最核心的算法就是深度学习(Deep Learning)和增强学习(Reinforcement Learning)。蒙特卡洛树搜索 MCTS 是一个搜索框架,将这些机器学习的技术融合在了一起。今天这篇文章的重点在深度学习,增强学习以后再说。

蒙特卡洛树搜索

每个博弈类的人工智能算法的基础都是一个搜索算法。比如我们上学时学习的 A-star 算法,alpha-beta 剪枝,极大极小搜索(min-max search)。蒙特卡洛树搜索也是其中一个。所有搜索算法大概的步骤都如下:
基于当前的状态,给出N种自己可以做出的选择
对于每种选择,评估一下这种选择对自己的好处
选择对自己好处最大的选择

但是这里有一个难点,就是如何评估每种选择对自己的好处,也就是如何设计出评价函数。比如说,如果我们设计出一个评价函数,结果发现在N种选择中,有M个选择得分一样,而且都是最高分,那这个时候我们怎么办?这里本质的原因是,如果基于当前的状态只看一步,其实很多时候看不出好坏。所以就要多看几步。比如
基于当前的状态,给出N种自己可以做出的选择
对于每种自己可以做出的选择,做出对手可能做出的N种选择
这个时候,我们最多可以面临 N^2 种局面,对每种局面进行评估
反推出自己应该做出什么选择

举个例子,比如给定一个评价函数Q,在当前局面下,自己有A,B两个选择,且评分一样 Q(A) = Q(B)。

但是,如果我做出A选择,对手可以做出A1选择,在这种选择下我就死了,对手就赢了。那么我肯定不能选A。这个时候,如果发现我选择B,对手的选择中,没有一种选择能让我立即就死了,那么至少B还是比A好的。这其实就是极大极小搜索的基本原理。而 Alpha-beta 剪枝是对极大极小搜索的一种优化。
当然,在上面的例子里我们只向前看了2步。但是也许看2步还是看不出局势的好坏。这个时候就要不断的扩展深度,直到能看出局势的好坏,然后再反推自己第一步怎么走。Alpha-beta 剪枝在国际象棋领域取得了很大的成功,深蓝就是基于这个算法的。但当人们把这个算法应用到围棋时就发现了一个问题:因为围棋每种状态下的选择远远大于象棋,造成在相同的算力下,围棋很难向前看太多步,但同时又很难设计出一个评价函数在搜索深度不大时,就能看清局势。

于是 MCTS 就诞生了。其实这个算法很早之前就诞生了,只是在围棋的领域里才找到了自己的出路。这个算法有如下的本质:
他对局势的评估,是基于自我对局进行模拟的。模拟的次数越多,估计的越准。这种评估基本能做到不需要太深的搜索,就能看清局势。
每次选择评估什么局势时,都是选择对当前胜率最大的节点进行评估

举个例子,比如棋局进行到X手时,轮到黑棋下,
黑棋找到10个自己可能下的位置,每个位置有两个数,一个是W,一个是T
找出10个位置中,黑棋下了胜率最大(胜率就是W/T, 当然出于探索的需要,一般会在这里使用多臂赌博机的模型,所以选择时并不完全考虑胜率,这个以后再细说)的位置,进行模拟对局。
对局结束后,T = T + 1, 如果黑棋胜了,W = W + 1,同时这个节点的祖先节点中,所有黑棋对应的节点的W都会加1。
假设经过一段时间后,黑棋可能下的10个位置都已经评估过了。这个时候就找出胜率最高的位置,开始考虑如果黑棋下在这个位置后,白棋怎么下。假设白棋也找10个可能下的位置。
当我们在评估白棋的位置好不好时,也要进行模拟对局。如果白棋胜了,那么这个节点的W = W + 1,同时这个节点的祖先节点中,所有的白色节点的W都加1。

上面这个过程其实是一种 min-max 搜索。为什么呢?我们考虑如果我们发现一个黑色节点,在之前的评估中胜率很高。但是,如果我们扩展了这个节点后,存在一个白色子节点的胜率很高(假设100%),那么我们在评估那个白色节点时,这个黑色节点的T会增加,但W不变,此时就会拉低黑色节点的胜率,直到这个节点降低到一定的程度。计算资源就不会再评估这个节点,而是去评估别的黑色节点了。

从上面的描述时,我们知道 MCTS 需要解决两个问题:
在每个状态下, 如果找出下一步的候选位置
如何评估每个状态的最终胜率。
在传统的 MCTS 里,是通过自己和自己下棋,一直下到最后确定胜负,然后下很多局可以计算出胜率。那么自己和自己下棋,也得有一个算法去给出下一步可能走在哪里。
AlphaGo 在这里有一个创新,就是不通过自我对局,而是直接通过神经网络基于当前局面,给出最后胜率的估计。

综合上面的讨论,下面这个问题显然是 AlphaGo 需要解决的第一个问题:
如果基于当前的局面,给出下一步的可能位置

这就是 AlphaGo 的 Policy Network 做的事情。在传统的围棋程序,比如 GnuGo 中,这一步大都是通过大量的规则去确定的。这里我们不考虑这种方法,只讨论如果通过机器学习,怎么实现。

预测下一步的传统机器学习实现

假设我们有一个数据集,包含了过去几十年人类高手对局的棋谱。那么我们就有了大量关于在某个盘面下,人类是怎么走下一步的例子。在19路棋盘上,总共有361个位置,如果我们对每个盘面能建立一个特征,那么就可以转化为一个361类的分类问题。这个时候最简单的就是可以用最大熵的分类器来解决这个问题。

更进一步,出于提高效率的考虑,我们也可以把这个361类的分类问题转化为一个两类分类问题。就是对于一个盘面S和一个合法的下一步p。判断y(S, p)是1, 还是0。是1表示人会下在p这个位置,是0表示人不会下。对于两类分类问题,我们的任务就是对于盘面S和位置p,抽取相关的特征。此时,我们的围棋知识就可以派上用场了:
如果我下在p,是不是就能吃掉对方几个子?
如果我下在p,是不是能救活我方的几个子?
如果我下在p,是不是能让对方的几个子处于危险之中?
如果我下在p,是不是能让我方几个子脱离危险?
如果我下在p,是不是能断开对方的大龙?
如果我下在p,是不是能让我方的大龙连回家?
如果我下在p,能否破对方的眼?
如果我下在p,是否能做我方的眼?
如果我下在p,是否征子有利?
如果我下在p,能否让一块棋活了?
……

基于围棋知识,我们可以设计出很多特征。

同时,在传统的机器学习中,也可以用模版法。直接抽去p这个位置的N邻域,hash出一个数做为特征。这个特征最终的权重代表在历史的对局中,当遇到这个局部时,人类会在p落子的可能性。

很不幸的是,当我们运用大量的围棋知识去设计各种特征,并加上各种邻域的模版特征之后,下一步预测的准确率只能达到30%~40%之间。这也是目前发表的paper中具有的水平。

预测下一步的 DCNN 实现

由于传统方法在这个问题上表现的很挫,因此 AlphaGo 用 DCNN(deep cnn)来解决这个问题。DCNN 之前在图片分类的问题中取得了很大的成功,给定一幅图,DCNN 可以知道这个图里是一棵树,还是一只猫,还是一艘船,还是一栋楼。由于围棋的棋盘其实可以看成一个19*19的图片,每个像素就是对应的位置的状态(是黑棋,还是白棋,还是没放棋)。因此我们可以把每个盘面表示成一个三通道的图片,对于位置p,
通道0 = 1 表示p放的我方的子 (这里我方代表在这个盘面下,下一步走棋的子的颜色,对方反之)
通道1 = 1 表示p放的对方的子
通道2 = 1 表示p没放子

然后这个图片的类别就是下一步可能的位置,一共有361种可能性,因此就是一个361类的分类问题。然后用 DCNN 训练一下,结果发现预测下一步的准确率可以达到44%。这是很令人惊奇的,因为整个过程中我们没有利用到任何围棋知识,也没有提前任何特征。DCNN 就自动学习出44%的精度了。

当得到这个惊人的结果时,群众们觉得,还是加点围棋知识吧,于是有人把3通道扩展到了更多的通道,比如:
通道0 = 1 表示p放的是我方的棋子
通道1 = 1 表示p放的是对方的棋子
通道2 = 1 表示没有放子
通道3 = 1 表示p放的是我方的棋,且于p相连的棋串只有1口气
通道4 = 1 表示p放的是我方的棋,且于p相连的棋串有2口气
通道5 = 1 表示p放的是我方的棋,且于p相连的棋串有3口气
通道6 = 1 表示p放的是我方的棋,且于p相连的棋串大于3口气
通道7 = 1 表示p放的是对方的棋,且于p相连的棋串只有1口气
通道8 = 1 表示p放的是对方的棋,且于p相连的棋串有2口气
通道9 = 1 表示p放的是对方的棋,且于p相连的棋串有3口气
通道10 = 1 表示p放的是对方的棋,且于p相连的棋串大于3口气
通道11 = 1 表示p是上一步刚刚落的子

可以看到,这里只利用到了2个围棋知识,一个是棋串,一个是气。另外还利用到了上一步的信息。然后用 DCNN 训练一下,会发现下一步的预测准确率能达到53%左右了。在 AlphaGo 里,还利用到了更多的围棋知识,它们一共使用了48个通道(也就是每个点提取了48个特征),然后就可以达到57%的准确率了。

当我看到这个结果时,确实觉得 DCNN 的效果已经超出我之前的认识了,因此促使我开始全面的研究深度学习。

目前开源的围棋程序 Pachi (https://github.com/pasky/pachi) 已经支持了 DCNN 用来预测下一步,有兴趣的可以关注一下。按照我在网上的实测,配合不太多的模拟之后,棋力在业余2段到3段之间。关于这里用的网络的详细信息可以参考 http://computer-go.org/pipermail/computer-go/2015-December/008324.html


 回到顶部