2009年4月3日星期五

Technical Details in RBM for CF

Technical Details in RBM for CF
受限玻尔兹曼机的技术细节

参考
[1]http://www.netflixprize.com/community/viewtopic.php?id=1007
[2]http://todwang.blogspot.com/2009/03/understanding-rbm-for-cf.html
[3]http://www.iro.umontreal.ca/~lisa/twiki/bin/view.cgi/Public/DBNPseudoCode
[4]http://imonad.com/blog/2008/10/restricted-boltzmann-machine/
[5]http://www.ics.uci.edu/~welling/teaching/ICS273AFall06/NeuralNets273AFall06.ppt

Gibbs一步采样

在[2]中,我提到训练中要计算<vikhf>data和<vikhf>T,而按照[1]中的讨论,T通常取1,因为实践中发现T取大了也得不到更精确的解。因此,我们下面的讨论都是Gibbs一步采样。
这一步如何采,也有两种方式。[3]中<vikhf>1项中的hf使用了它的期望而不是采样值,而标准的Gibbs采样步骤这步也应该采样。[1]中的讨论中说,[3]的做法精度更好。而我实验发现,这两种方法效果差不多。[3]的具体做法在下一节中一起详细说明。

在线训练

Hinton那篇开创RBM for CF的文章中,用了Batch update weights的方法,也就是我[2]中解释的那样。而[1]讨论中发现,per-case-update(在线训练)也取得很好的效果。具体来说:
1、设trainning case v是一个M×K的0-1阵,表示一个用户的所有评分行为,vik=1表示该用户给电影i评分为k。
2、按照[2]中假设2采样得到隐层的F维0-1向量h,表示用户的特征。
3、按照[2]中假设1采样得到显层的M×K的0-1阵,记作v2,表示重构后的用户评分行为。
4、再按照[2]中假设2计算h的期望Eh,也是F维的向量,元素值取于区间[0,1]。
5、针对这一个trainning case v就可以更新W了:
W[i][k][f]+=LRATE * (v[i][k]*h[f]-v2[i][k]*Eh[f]),foreach i,k,f

利用稀疏性

在我的程序中,v使用了一种相对紧凑的数据结构,注意到v的列和总为1(如果此列不缺失的话)。
ur是一个二元组(mid, rate)的列表,长度和v的非缺失列个数sz相同,rate取值于K,它和v等价:v[ur[j].mid][ur[j].rate]=1恒成立,且v[i][k]=1当且仅当存在j<sz使得ur[j].mid=i,ur[j].rate=k。对应v2为结构ur2。
用这个结构改善上述第5步:
for j in sz
  note u as ur[j], u2 as ur2[j]
  foreach f
    W[u.mid][u.rate][f] += LRATE * h[f];
    W[u2.mid][u2.rate][f]-= LRATE * Eh[f];
这样一来,这一步的复杂度从MKF降到sz×F<<M×F了。

Bias设置与训练

[1]中讨论说hidden unit bias都设为零,也就是[2]中df设为0,visibel unit bias固定为先验概率分布的对数:bik=log(给电影i评k分的用户个数/给电影i有评分的用户数)。bik也可以一起在线训练:
bik+=<vik>data-<vik>T
利用稀疏性表示为:
for j in sz
  note u as ur[j], u2 as ur2[j]
  b[u.mid][u.rate]+=LRATE
  b[u2.mid][u2.rate]-=LRATE
我实践发现,visibel unit bias固定或训练效果差不多。

Weight Decay和Momentum

这是常见的梯度下降技巧,[5]中有详细的解释。
Weight Decay可以理解为一个弹簧,把每个weight拉回0点,防止权变太大:

其中lambda是充分小的正数。
W[u.mid][u.rate][f] += LRATE * (h[f]-WEIGHTDECAY*W[u.mid][u.rate][f]);
Momentum是动量项,用于加速梯度下降,有点自适应步长的意思。

其中γ为小于1的正数。
相当于这一步计算的权变化量不仅对这一步迭代有贡献,而且对以后都有贡献,不过贡献随着迭代的次数指数衰减罢了。
注意到,这两个技巧主要是针对Batch update weights的,用到在线训练中的效果不好估计。

退火

这也可以用在所有迭代学习算法中,主要随着收敛步长减小的格式。[1]中给出了一个反比例函数的降温格式。
lrate = LRATE/(1 + iter / (3 * U));
其中LRATE是初始步长,iter是用过的trainning case的个数。可见,迭代30轮(pass),步长就已经下降一个数量级了。

连续受限玻尔兹曼机

参考[4],注意到评分1,...,5原本是全序的,而不是K个无序的label,而发明RBM的初衷是用于模式分类,最后输出是一个离散label。因此引入连续受限玻尔兹曼机,是自然的。也就是显层向量v不是0-1的,而是连续取值的。这就要求更新[2]中的假设了,需要模型建立者重新假设条件概率分布,也就是重新定义整个贝叶斯网络。[4]引用的那篇Continuous RBM很有意思,用扩散网络建模,求解时用了随机微分方程。以后可以考虑做做这个方向。

结果

可能由于是随机算法,发现rmse随着迭代进行的下降过程有抖动,而不是严格单调的。
目前做到了probe rmse 0.9438 :迭代46步,其算法参数:
100个hidden unit,在线训练、固定bias、没有退火,lrate=0.001,WEIGHTDECAY=0.0001,没有用动量项。

没有评论: