矩阵分解算法的求解 随机梯度下降SGD和交替最小二乘ALS

优化时为何选择偏导数的负方向？

首先假设目标函数为$min f(x)$minf(x)
那么我们的关注点就是如何找到当前状态$x^k$xk后的下一个状态点$x^{k+1}$xk+1
$x^{k+1}=x^k+t_k\cdot p_k$xk+1=xk+tk​⋅pk​
其中，$t_k$tk​表示步长，$p_k$pk​表示方向
依据泰勒展开式
$f(x)=f(a)+\frac{f^{'}(a)}{1!}(x-a)+\frac{f^{''}(a)}{2!}(x-a)^2+\cdots+\frac{f^{(n)}(a)}{n!}(x-a)^n+R_n(x)$f(x)=f(a)+1!f′(a)​(x−a)+2!f′′(a)​(x−a)2+⋯+n!f(n)(a)​(x−a)n+Rn​(x)
因此
$f(x^k+t_kp_k)=f(x^k)+t^k\cdot \nabla f(x^k)^T\cdot p^k+o(\Vert t^k \cdot p^k \Vert)$f(xk+tk​pk​)=f(xk)+tk⋅∇f(xk)T⋅pk+o(∥tk⋅pk∥)
于是
$f(x^k)-f(x^k+t_kp_k)=-t^k\cdot \nabla f(x^k)^T\cdot p^k+o(\Vert t^k \cdot p^k \Vert)$f(xk)−f(xk+tk​pk​)=−tk⋅∇f(xk)T⋅pk+o(∥tk⋅pk∥)
由于$o(\Vert t^k \cdot p^k \Vert)$o(∥tk⋅pk∥)是高阶无穷小量，可以不考虑
若要使$f(x^k)-f(x^k+t_kp_k)$f(xk)−f(xk+tk​pk​)最大，即下降的最多，又因为$t^k$tk是不变的参数，因此就要使
$p^k=-\nabla f(x^k)^T$pk=−∇f(xk)T
即方向向量等于（偏）导数的负方向

随机梯度下降算法(Stochastic Gradient Descent, SGD)

SGD的思路就是让训练集中的每一条数据依次进入模型，不断优化变量。
要注意的是，因为是一条条进入模型，因此数据的顺序会对实验结果产生影响，
对于考虑时间因素的数据集，应按照时间顺序依次进入模型

以最基本的矩阵分解模型$r_{ui}=q_i^Tp_u$rui​=qiT​pu​为例
损失函数可以定义为$J(p_u,q_i) =\frac{1}{2}\left( \sum (r_{ui}-q_i^Tp_u)^2 + \lambda(\Vert q_i \Vert^2 + \Vert p_u \Vert^2 ) \right)$J(pu​,qi​)=21​(∑(rui​−qiT​pu​)2+λ(∥qi​∥2+∥pu​∥2))
其中$\lambda$λ是正则化系数，这里把对$p_u$pu​和$q_i$qi​的正则化系数设置为相同值，也可以为不同值，不使用括号即可
下面求损失函数对$p_u$pu​的偏导
$\frac{\partial J(p_u)}{\partial p_u} = (r_{ui}-q_i^Tp_u)(-q_i^T) + \lambda p_u$∂pu​∂J(pu​)​=(rui​−qiT​pu​)(−qiT​)+λpu​
常令
$e_{ui} = r_{ui}-q_i^Tp_u$eui​=rui​−qiT​pu​
因此
$p_u = p_u - \eta \cdot \frac{\partial J(p_u)}{\partial p_u}= p_u+\eta(e_{ui}\cdot q_i - \lambda \cdot p_u)$pu​=pu​−η⋅∂pu​∂J(pu​)​=pu​+η(eui​⋅qi​−λ⋅pu​)
其中，$\eta$η表示学习速率
同理
$q_i = q_i - \eta \cdot \frac{\partial J(q_i)}{\partial q_i}= q_i+\eta(e_{ui}\cdot p_u - \lambda \cdot q_i)$qi​=qi​−η⋅∂qi​∂J(qi​)​=qi​+η(eui​⋅pu​−λ⋅qi​)

交替最小二乘算法(Alternating Least Squares, ALS)

因为p和q两个变量未知，因此损失函数不是凸函数，无法使用凸优化求解。
但是，如果固定p，那么损失函数是只关于q的二次函数，用解二次函数方法。
因此，可固定p，求q；再固定q，求p，这样迭代下去，此即为交替一词出处。

$\frac{\partial J(p_u)}{\partial p_u} = (r_{ui}-q_i^Tp_u)(-q_i^T) + \lambda p_u=(q_i^T q_i + \lambda)p_u - r_{ui}q_i^T$∂pu​∂J(pu​)​=(rui​−qiT​pu​)(−qiT​)+λpu​=(qiT​qi​+λ)pu​−rui​qiT​
下面令$\frac{\partial J(p_u)}{\partial p_u}=0$∂pu​∂J(pu​)​=0
写成矩阵形式
$(QQ^T+\lambda E)P=R_jQ^T$(QQT+λE)P=Rj​QT
$P=(QQ^T+\lambda E)^{-1}R_j$P=(QQT+λE)−1Rj​
同理
$Q=(PP^T+\lambda E)^{-1}R_i$Q=(PPT+λE)−1Ri​