推荐系统ALS算法浅述

概览

从协同过滤的分类来说，ALS（Alternating Least Squares，交替最小二乘）算法属于User-Item CF，也叫做混合CF。它同时考虑了User和Item两个方面。

用户和商品的关系，可以抽象为如下的三元组：<User,Item,Rating>。其中，Rating是用户对商品的评分，表征用户对该商品的喜好程度。

ALS算法是基于模型的推荐算法。其基本思想是对稀疏矩阵进行模型分解，评估出缺失项的值，以此来得到一个基本的训练模型。然后依照此模型可以针对新的用户和物品数据进行评估。ALS是采用交替的最小二乘法来算出缺失项的。交替的最小二乘法是在最小二乘法的基础上发展而来的。

首先，我们对问题进行建模：

假设有 m m m 个item 和 n n n 个user，其行为数据构成 rating 矩阵 R ∈ { 0 , 1 } n × m R\in \{0,1\}^{n\times m} R∈{0,1}n×m。

一般情况下， m , n m,n m,n 的值都会十分大，且每个user评分的item数量一般较item总数很少，所以矩阵 R R R 通常是一个稀疏矩阵。矩阵中缺失的数据即是我们想要计算的数据。

虽然评分矩阵一般rating并非是0，1二值的，但是一般在处理过程中为了简化问题我们都将其二值化。

为了计算缺失的数据，一种矩阵分解（Matrix Factorization，MF）的方法便被提出了。其基本思想是将 R R R 矩阵分解成 U ∈ R n × k , V ∈ R m × k U\in \R^{n\times k},V\in \R^{m\times k} U∈Rn×k,V∈Rm×k 两个矩阵，使得 R R R 中的有值的项尽量满足：

R n , m ≈ U n V m T R_{n,m} \approx U_nV_m^T Rn,m​≈Un​VmT​

这里，k的取值一般设定为超参数，也就是将每个user和item都提取出相应的特征表示（也可以视为隐变量）。

那么需要优化的问题就变成如下所示：

min ⁡ x , y ∑ u , i   i s   k n o w n ( r u i − x u y i T ) 2 \min_{x,y}\sum_{u,i \, is \,known}(r_{ui}-x_uy_i^T)^2 x,ymin​u,iisknown∑​(rui​−xu​yiT​)2

然后对该式加上正则化项后变成：

min ⁡ x , y ∑ u , i   i s   k n o w n ( r u i − x u y i T ) 2 + λ ( ∣ x u ∣ 2 + ∣ y i ∣ 2 ) \min_{x,y}\sum_{u,i \, is \,known}(r_{ui}-x_uy_i^T)^2+\lambda(|x_u|^2+|y_i|^2) x,ymin​u,iisknown∑​(rui​−xu​yiT​)2+λ(∣xu​∣2+∣yi​∣2)

优化过程

由于上式中需要优化的量有 X , Y X,Y X,Y 两个，计算二元导数很难计算，所以每次固定住一个变量对另一个变量求导，采用最小二乘法。两个变量交替进行，故称为交替最小二乘。

对 x x x 求导：

∂ L ∂ x u = − 2 ∑ i ( r u i − x u T y i ) y i + 2 λ x u = − 2 ∑ i ( r u i − y i T x u ) y i + 2 λ x u = − 2 Y T r u + 2 Y T Y x u + 2 λ x u \begin{aligned} \frac{\partial L}{\partial x_{u}} &=-2 \sum_{i}\left(r_{u i}-x_{u}^{T} y_{i}\right) y_{i}+2 \lambda x_{u} \\ &=-2 \sum_{i}\left(r_{u i}-y_{i}^{T} x_{u}\right) y_{i}+2 \lambda x_{u} \\ &=-2 Y^{T} r_{u}+2 Y^{T} Y x_{u}+2 \lambda x_{u} \end{aligned} ∂xu​∂L​​=−2i∑​(rui​−xuT​yi​)yi​+2λxu​=−2i∑​(rui​−yiT​xu​)yi​+2λxu​=−2YTru​+2YTYxu​+2λxu​​

根据最小二乘法，令导数为0，有：

2 Y T Y x u + 2 λ I x u = 2 Y T r u    ⟹    x u = ( Y T Y + 2 λ I ) − 1 Y T r u 2 Y^{T} Y x_{u}+2 \lambda I x_{u}=2 Y^{T} r_{u} \implies x_u = (Y^TY+2\lambda I)^{-1}Y^Tr_u 2YTYxu​+2λIxu​=2YTru​⟹xu​=(YTY+2λI)−1YTru​

同理，对称可求得：

y i = ( X T X + 2 λ I ) − 1 X T r i y_i = (X^TX+2\lambda I)^{-1}X^Tr_i yi​=(XTX+2λI)−1XTri​

因此，整个优化过程为：

1. 随机生成 $X,Y$，即迭代的开始
2. 循环直至收敛：
3. 		固定X，更新Y
4. 		固定Y，更新X
           

一般使用 RMSE(Root Mean Square Error) 指标来评价是否收敛，在此任务中如下表示：

R M S E = ∑ ( R − X T Y ) 2 N RMSE = \sqrt{\frac{\sum(R-X^TY)^2}{N}} RMSE=N∑(R−XTY)2​

​

其中，N 为 ⟨ u , i , r a t i n g ⟩ \langle u,i,rating\rangle ⟨u,i,rating⟩ 三元组的数量

复杂度：

• 求 X X X， O ( k 2 m + k 3 n ) O(k^2m+k^3n) O(k2m+k3n)
• 求 Y Y Y， O ( k 2 n + k 3 m ) O(k^2n+k^3m) O(k2n+k3m)