2009年3月26日星期四

Understanding RBM for CF

Understanding RBM for CF

理解协同过滤中的受限玻尔兹曼机

引论

协同过滤(Collaborative Filtering,简称CF)推荐系统中,古典的模型有近邻模型、隐性因子模型等。从2007年开始,受限玻尔兹曼机模型在协同过滤中开始流行起来。
参考文献
[1]Restricted Boltzmann Machines for Collaborative Filtering
[2]On Contrastive Divergence Learning
[3]Markov Chain Monte Carlo and Gibbs Sampling
受限玻尔兹曼机(Restricted Boltzmann Machines,简称RBM)是一种借鉴了模拟退火思想的人工神经网络模型,它在计算过程中又借鉴了蒙特卡洛马尔科夫链(MCMC)的思想。这篇Blog是[1]的阅读笔记,为了理解训练的算法,延伸阅读了[2]和[3]。

问题描述

在线系统中,有很多用户(User)给电影(Movie)评分的数据,协同过滤推荐系统利用这些数据,估计给定User对给定Movie的评分。评分值域为{1,...,K},用户集合记作U={0,...,U-1},电影集合记作M={0,...,M-1},已知评分用有缺失值的矩阵R表示,,推荐系统使用某种协同过滤算法评分器估计(u,i)点处的评分记作,我们希望在给定测试集Q上均方根误差尽量小。

模型框架

存在这样一个对称网络可以表示用户给电影评分的机制,它包括显层和隐层两层节点。
显层共M×K个节点,对应M个电影和K个可能评分的卡氏积。每个u∈U的实际评分对应一组显层状态(Visible),一组显层状态用M×K的、允许缺失行的、0-1矩阵V表示,它刻画了u的实际行为。V=(vik),若V的第i行数据缺失,则表示u没有给i评分,否则V的第i行总恰有一个非零元,vik=1表示u给i评分为k。
隐层共F个节点,对应F个隐藏的因素(Factor)。隐层表示为F维0-1向量h,非零元代表u具备的因素,它描述了u行为的原因。
任一显层节点(i,k)和任一隐层节点f之间用无向弧相连,弧的权值记作,表示两个节点联系的程度。权值矩阵W为M行K列F层的三维矩阵。不同的u,对应不同的V和h,但是他们共用一个W。根据显层状态分布假设P(V|h),用隐层状态h和权值W决定显层状态的过程,是预测的过程。利用显层状态V反推权值W和隐层状态的过程,是训练的过程。作为Hopfiled网络,学习过程是以下两个步骤的交替:
1、激活:固定W,根据隐层状态分布假设P(h|V),计算h的分布
2、反向传播误差修正W:固定h,极大化似然函数P(V),计算它关于W各分量的偏导数,沿负梯度方向改变一充分小步长来修正W。

模型假设

固定一个u,
1、显层状态的条件概率分布:

其中

这里aik表示u给电影i的评k分的激发程度,它关于h和Wik的向量内积成指数增加,也就是说,i具备u评k分的因素越多,被u评k分的可能性越大,而且这种正相关的影响呈指数增加。bik为电影i的得k分的内在因素,与u无关。
2、隐层状态的条件概率分布:

其中Wf为W的第f层,

df为因素f被观测数据影响的因子,它只与因素f自身有关,与u和i无关,
sigmoid(x)=1/(1+e-x)
注意到,hf=1的条件概率,数值上就是hf的条件期望。
3、似然函数

其中c为归一化因子,E(V,h)为能量函数

疑问:
这个假设如何从前两个假设推出来?

训练

计算似然函数偏导数

其中
为训练过程遍历所有u∈U时,vikhf非零的频率,具体来说,其中h(u)根据假设2采样得到;
是vikhf非零的频数的数学期望,它的值由模型假定的分布决定,但计算复杂度太高,按照[2]介绍的Contrastive Divergence方法用近似;
通过Gibbs采样[3]迭代T次得到,T初始为1,随着训练T的值不断增加,[1]中说T太大也没必要。Gibbs采样是一种蒙特卡洛方法,意思有点像“左右互搏”,在这个问题中,就是先固定V0=V,根据假设2采样得到h1,然后根据假设1采样得到V1,这叫迭代了一步,迭代T步求平均,就可以近似它的期望了。具体来说
有了似然函数个方向偏导数,就可以“爬山”啦~

lrate为学习率,或者叫步长。

预测

训练好了权值矩阵后,就可以用它来预测(u,i)∈U×M了。给定u,先根据假设2算出h的条件期望,然后用它来代替假设1中的h,算出vi1,...,viK的分布,然后计算rui期望作为预测值。具体来说:
step1

step2

step3


没有评论: