一、SGD的一个例子说明
下图是我目前得到的一个评分文件,3列的含义分别是UID:User ID,IID:Item ID,score:用户评分.可以看到一共有3个用户,4个物品.
他们可以构成一个3 * 4的评分矩阵矩阵.我现在取k=2,要把它们分解成为一个32的P矩阵和一个24的Q矩阵.
首先初始化P和Q矩阵,一般都用符合正态分布的随机数X~N(0,1)来填充矩阵.
现在我计算u=1时的∂L/∂Pu,取λ的值为1 首先计算u=1,i=1这个评分记录带来的梯度分量,即u=1,i=1时的
然后计算u=1,i=2这个评分带来的梯度分量:
所以,u=1时的梯度为
刚才提到的迭代公式: p_u=p_u-η ∂L/∂Pu,其中η表示学习率,就是平时我们说的梯度下降时的步长,取η=0.05 于是有
可见,通过这一次对于p_1的梯度下降, p_1对应的向量从随机产生的
我们来验证一下这个变化是否是的预估的值更加准确了 原来对于R_11的估计误差为
新的对于R_11的估计误差为
确实比原来有提升.按照上述步骤分别更新所有P矩阵中的p_i,然后用更新好的P矩阵,用公式(4)中的方法更新Q,再用更新好的Q第二次更新P.这种迭代方法最终可以使得|R-PQ|的值缩小,当|R-PQ|在下一轮迭代的过程中不再变小时,我们就认为在当前的学习率η下,P,Q已经得到了局部最优解.
二、加速梯度下降
通过逐步减小参与计算的数据量加速（类似SPFA对贝尔曼算法的优化）
在上面的介绍中我们可以看到整个的迭代都是矩阵Q和矩阵P不断变化,使得P*Q的结果接近R的过程。对于某些用户和物品节点而言,这些点的K维向量很快就收敛到了我们的目标值,即对于这些用户节点而言,
对于某些点,误差值在迭代开始没几轮的时候就达到了目标范围,这个某些点提前结束迭代的功能对于物品节点也成立.这些点可以不用参加之后的迭代。
通过图计算可以实现，比如spark就带有这些功能。