交替最小二乘法(Alternating Least Square

作者: Lutouch | 来源:发表于2019-02-22 13:36 被阅读0次

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

背景知识

显式数据与隐式数据(Explicit data and implicit data)

显式数据(Explicit Data) 是指那些有评价得分的数据，比如对电影的评分。此类数据明确指出用户对物品的喜好程度，但往往很难获取到。
隐式数据(Implicit Data) 是指从用户行为中收集到的数据，缺少评分或评分所必须的特定行为。这可能是一个用户购买了某个物品、重复播放了多少次歌曲、观看某部电影多长时间以及阅读某篇文章的时长等等。此类数据优点是数据量大，缺点是噪音较多并且往往含义不明显。
举个例子，通过给商品打星的数量，我们知道 1 表示用户不喜欢该商品，5 表示用户非常喜爱。用户播放了某歌曲，我们推测用户可能喜欢该歌曲或者讨厌该歌曲，也可能介于两者之间。如果用户没有播放某歌曲，有可能是因为用户不喜欢它，也可能只是不知道这首歌曲的存在。

邻域模型(Neighborhood models)

UserBased CF - 基于用户的协同过滤
ItemBase CF - 基于物品的协同过滤

所有以物品为中心的模型在处理隐式数据时有个共同的劣势 -- 他们都不提供区分用户偏好与偏好的置信度的能力。

潜在因素模型(Latent factor models)

Netflix Prize开始后，Simon Funk在其个人博客中公布了一个基于 SVD 的改进算法(Funk-SVD)，一下子引爆了推荐系统研究者对于矩阵分解的关注。这种改进算法称为隐语义模型或潜在因素模型。

概念

潜在因素模型，又称隐语义模型，是协同过滤系统中的另一种实现方案，其整体目标是发掘已有评分数据中的隐藏因子。通过对 user-item 评分矩阵进行 奇异值分解(Singular Value Decomposition, SVD) 推断出模型。

原理

隐语义模型也是基于矩阵分解的，但是和 SVD 不同，它是把原始矩阵分解成两个矩阵相乘而不是三个。
$R = XY^T$
现在的问题就变成了确定 $X$ 和 $Y$ ，我们把 $X$ 叫做用户因子矩阵， $Y$ 叫做物品因子矩阵。通常上式不能达到精确相等的程度，我们要做的就是要最小化它们之间的差距，从而又变成了一个最优化问题。

通常一个隐语义模型为每个用户 $u$ 定义一个用户因子向量 $x_u \in R^f$ , 为每一个物品 $i$ 定义物品因子向量 $y_i \in R^f$ 。通过计算两个向量的内积得到预测结果，如 $\hat{r}_{ui} = x_u^{T} y_i$ 。

优化目标是最小化代价函数，即:
$\min_{x_*, y_*}\sum_{r_{ui}\,is\,known}{(r_{ui} - x_u^Ty_i)^2 + \lambda(||x_u||^2 + ||y_i||^2)}$
其中 $\lambda$ 用作模型正则化。

两种求解算法

梯度下降法

Simon Funk所采用的方法，为了减少计算量，采用随机梯度下降SDG(Stochastic Gradient Descent)

交替最小二乘法

通常 SGD 比 ALS(Alternating Least Squares) 简单而且快速，但是 ALS 的并行性能比较好，而且可以较好地处理稀疏数据。

基本原理

概念定义

偏好(Preference)

布尔型变量，表示用户 $u$ 对物品 $i$ 的感情偏好。定义如下:
$p_{ui} = \begin{cases} 1& {r_{ui}>0}\\ 0& {r_{ui}=0} \end{cases}$

由定义可知，偏好值仅仅表示用户和物品之间有没有交互，而不表示评分高低或者喜好程度。

如果用户 $u$ 消费过某物品 $i$ ，即 $r_{ui} > 0$ ，这暗示用户 $u$ 喜爱物品 $i$ ；另一方面，如果用户 $u$ 从未消费过物品 $i$ ，我们认为用户 $u$ 对该物品 $i$ 没有偏好。

置信度(Confidence)

置信度用于衡量对偏好值 $p_{ui}$ 的信心。定义如下:
$c_{ui} = 1 + \alpha r_{ui}$
我们的目标是发现每一个用户 $u$ 的向量 $x_u \in R^f$ 和每一个物品 $i$ 的向量 $y_i \in R^f$ 。分别称为用户因子 user-factor 和物品因子 item-factor。