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


2009年3月19日星期四

Netflix数据集的一些统计特征(2)

很多网站的流量在一周之内变化的趋势类似,那就是工作日流量多,周末流量少。Netflix数据集也如此。无论是训练集还是测试集,评分日期的一周分布中,周六周日两天加起来不到20%,而周一周二尤其多,加起来超过了35%,说明人们上班的时候很闲可以上网,或者晚上喜欢放松看看电影,而周末则外出休闲去鸟。

另一个发现,是训练集和测试集的某些边缘分布很不同(测试集包括probe set和quiz set,分布相同)。
1、训练集的用户分布不均匀,少数用户非常活跃,10%最活跃的用户评分点占了所有测试集评分点的43.6%,而测试集的用户分布是均匀的,几乎所有用户被测试的概率相同,除了极少数最不活跃的用户。说明Netflix对所有用户一视同仁,不活跃的用户被认为与活跃的用户有相同的消费的能力。
2、测试集比训练集的时间更集中于离现在较近的时刻,测试集中最后一周的评分点占了20.4%,而训练集中最后一周的评分点仅占了1.5%。说明要求模型有一定预测的能力,尤其是预测当下用户偏好,而不是猜测用户过去偏好的能力,因为前者是有价值的。

2009年3月4日星期三

run mysql with ruby in ubuntu 8.04

  1. 用新立得安装ruby,mysql,mysql server的最新版
  2. 下载mysql-ruby-2.8.1,http://www.tmtm.org/en/mysql/ruby/
  3. 按照上面网址的说明,配置、编译、安装
中途遇到几个小麻烦,mkmf包在ubuntu 8.04默认的ruby 1.8中没有,mysql客户端的版本也有些问题。总之全都使用最新版就OK了。