2009年5月11日星期一

Principle of Shrink Method in collaborative filtering

Scalable Collaborative Filtering with Jointly Derived Neighborhood InterpolationWeights等很多篇流行的协同过滤算法的文献中,都提到了Shrink技巧。

 

Shrink技巧的理论基础是高斯假设下的贝叶斯参数估计,这部分内容是经典的,可以在贝叶斯方法、模式分类等的领域相关教科书中找到。我们将假设和推导过程整理、重述如下:

假设我们要估计参数,视为随机变量,关于的先验知识是它服从正态分布,即其概率密度函数为:

的一组观测值视为独立同分布的样本,其总体为随机变量,满足条件正态分布。我们关心的是,有了一组观测后,我们应该如何用的信息修正先验知识。为此,计算后验概率密度函数:




其中c为归一化系数,倒数第二步将其整理为
的二次型,是为了将其凑成正态密度函数的形式。上式告诉我们服从正态分布,记为,则

将上面两个式子中
二项式对应项系数相等,得到下面两个方程:


从中很容易反解出我们关心的


从中可以得到两点结论:

1、后验期望总可以表示成样本均值和先验期望的凸组合;

2、当观测足够多,即n充分大时,趋向于0,即我们确信
非常接近其期望。而收敛到样本均值



中取



即得到文献中的Shrink技巧的实用形式:

2009年5月3日星期日

Implement RBM for netflix CF

RBM的实现

RBM预测器(隐层节点数F

参数

权值矩阵W,维数M×K×F(K=5)

Bias矩阵b,维数M×K

原始显层节点向量v0,元素取值于K,维数不超过M,与当前用户的评分个数相同,重构后的显层节点向量v1,与v0维数相同,mv0下标集到M的映射,即v0j表示电影mj的实际评分

隐层节点0-1向量第一次采样h0,第二次采样h1,维数F

每个用户对应的隐层节点向量的期望Eh,维数U×F

训练算法

1)初始化W~N(0, 0.001),bik=电影ik分的评分次数占电影i评分次数的比例

迭代2)3)直到收敛

2)对于每个用户u

2.a)根据u的实际评分生成v0

2.b)h0采样

,生成随机数p来自U[0,1],若

h0f=1,否则h0f =0

2.c)轮盘赌法重构v1


生成随机数p来自U[0,)

 其中k使得

2.d) h1采样

生成随机数p来自U[0,1],若

h1f=1,否则h1f =0

2.e)更新W

  h0f=1

  h1f=1

3)计算Eh



预测函数





实验结果

F=16,lrate=0.002
[1]1.0528 0.0508 1
[2]0.9617 -0.0018 135 0.0911
[3]0.9516 0.0024 273 0.0101
[4]0.9476 0.0007 411 0.0041
[5]0.9454 0.0008 550 0.0022
[6]0.9440 0.0011 689 0.0014
[7]0.9434 -0.0007 828 0.0006
...
[20]0.9404 -0.0003 2636 0.0002
...
[30]0.9400 -0.0024 4029 0.0001
...

各列含义:[迭代步数]RMSE(on ProbeSet) 平均偏差(on ProbeSet) 逝去时间(秒) RMSE改进量
发现前几步RMSE下降非常快。
注:使用Weight Decay可以略微改进结果
将2.e)改成

 

 

实验结果
F=16,lrate=0.002,decay=0.0001
...
[20]0.9393 -0.0011 2719 0.0005
...