AlS学习与应用

Posted on Edited on In


参考网址:
交换最小二乘

Tips:

矩阵中的最大的不相关的向量的个数，就叫秩
一个mn的矩阵，如果秩很低（秩r远小于m,n），则它可以拆成一个mr矩阵和一个rn矩阵之积（类似于SVD分解）。后面这两个矩阵所占用的存储空间比原来的mn矩阵小得多。

什么是ALS

  ALS是交替最小二乘（alternating least squares）的简称。在机器学习中，ALS特指使用交替最小二乘求解的一个协同推荐算法。它通过观察到的所有用户给商品的打分，来推断每个用户的喜好并向用户推荐适合的商品。这就是一个有m个的U(用户),与n个V(商品)的矩阵.

  ALS的核心就是这样一个假设：打分矩阵是近似低秩的。换句话说，就是一个m*n的打分矩阵可以由分解的两个小矩阵U（m*k）和V（k*n）的乘积来近似，即$A=U{V}^{T},k <= m,n$。这就是ALS的矩阵分解方法。这样我们把系统的自由度从O(mn)降到了O((m+n)k)。

  我们把某个人的喜好映射到了低维向量ui上，同时将某个影片的特征映射到了维度相同的向量vj上，那么这个人和这个影片的相似度就可以表述成这两个向量之间的内积$$u_{i}^{T}v_{j}$ 。我们把打分理解成相似度，那么打分矩阵A就可以由用户喜好矩阵和产品特征矩阵的乘积$ U{V}^{T} $来近似了。

  低维空间的选取是一个问题。这个低维空间要能够很好的区分事物，那么就需要一个明确的可量化目标，这就是重构误差。在ALS中我们使用F范数来量化重构误差，就是每个元素重构误差的平方和。这里存在一个问题，我们只观察到部分打分，A中的大量未知元是我们想推断的，所以这个重构误差是包含未知数的。
解决方案很简单：只计算已知打分的重构误差:

$$ \sum_{i,j\in R}(a_ij - u_iv_j^T)^2 $$

Spark中ALS的实现原理

  Spark利用交换最小二乘解决矩阵分解问题分两种情况：数据集是显式反馈和数据集是隐式反馈。由于隐式反馈算法的原理是在显示反馈算法原理的基础上作的修改，所以我们在此只会具体讲解数据集为隐式反馈的算法。

介绍

  从广义上讲，推荐系统基于两种不同的策略：基于内容的方法和基于协同过滤的方法。Spark中使用协同过滤的方式。协同过滤分析用户以及用户相关的产品的相关性，用以识别新的用户-产品相关性。协同过滤系统需要的唯一信息是用户过去的行为信息，比如对产品的评价信息。协同过滤是领域无关的，所以它可以方便解决基于内容方法难以解决的许多问题。

  推荐系统依赖不同类型的输入数据，最方便的是高质量的显式反馈数据，它们包含用户对感兴趣商品明确的评价。例如，Netflix收集的用户对电影评价的星星等级数据。但是显式反馈数据不一定总是找得到，因此推荐系统可以从更丰富的隐式反馈信息中推测用户的偏好。

隐式反馈类型包括购买历史、浏览历史、搜索模式甚至鼠标动作。例如，购买同一个作者许多书的用户可能喜欢这个作者。

  许多研究都集中在处理显式反馈，然而在很多应用场景下，应用程序重点关注隐式反馈数据。因为可能用户不愿意评价商品或者由于系统限制我们不能收集显式反馈数据。在隐式模型中，一旦用户允许收集可用的数据，在客户端并不需要额外的显式数据。文献中的系统避免主动地向用户收集显式反馈信息，所以系统仅仅依靠隐式信息。

  了解隐式反馈的特点非常重要，因为这些特质使我们避免了直接调用基于显式反馈的算法。最主要的特点有如下几种：

  • （1） 没有负反馈。通过观察用户行为，我们可以推测那个商品他可能喜欢，然后购买，但是我们很难推测哪个商品用户不喜欢。这在显式反馈算法中并不存在，因为用户明确告诉了我们哪些他喜欢哪些他不喜欢。

  • （2） 隐式反馈是内在的噪音。虽然我们拼命的追踪用户行为，但是我们仅仅只是猜测他们的偏好和真实动机。例如，我们可能知道一个人的购买行为，但是这并不能完全说明偏好和动机，因为这个商品可能作为礼物被购买而用户并不喜欢它。

  • （3） 显示反馈的数值值表示偏好（preference），隐式回馈的数值值表示信任（confidence）。基于显示反馈的系统用星星等级让用户表达他们的喜好程度，例如一颗星表示很不喜欢，五颗星表示非常喜欢。基于隐式反馈的数值值描述的是动作的频率，例如用户购买特定商品的次数。一个较大的值并不能表明更多的偏爱。但是这个值是有用的，它描述了在一个特定观察中的信任度。
    一个发生一次的事件可能对用户偏爱没有用，但是一个周期性事件更可能反映一个用户的选择。

  • （4） 评价隐式反馈推荐系统需要合适的手段。

隐式反馈模型

  在显式反馈的基础上，我们需要做一些改动得到我们的隐式反馈模型。首先，我们需要形式化由$r_{ij}$变量衡量的信任度的概念。我们引入了一组二元变量$p_{ij}$ ，它表示用户u对商品v的偏好。$p_{ij}$的公式如下：

$$p_{ij}=\left{
\begin{array}{ll}
1 &\mbox{$r_{ij}> 0$}\
0 &\mbox{$r_{ij}$=0}
\end{array}
\right.$$

  换句话说，如果用户购买了商品，我们认为用户喜欢该商品，否则我们认为用户不喜欢该商品。然而我们的信念（beliefs）与变化的信任（confidence）等级息息相关。首先，很自然的，$p_{ij}$的值为0和低信任有关。用户对一个商品没有得到一个正的偏好可能源于多方面的原因，并不一定是不喜欢该商品。例如，用户可能并不知道该商品的存在。
另外，用户购买一个商品也并不一定是用户喜欢它。因此我们需要一个新的信任等级来显示用户偏爱某个商品。一般情况下，$r_{ij}$越大，越能暗示用户喜欢某个商品。因此，我们引入了一组变量$c_{ij}$，它衡量了我们观察到$p_{ij}$的信任度。$c_{ij}$一个合理的选择如下所示：

$$c_{ij} = 1 + \alpha r_{ij}$$

  按照这种方式，我们存在最小限度的信任度，并且随着我们观察到的正偏向的证据越来越多，信任度也会越来越大。

  我们的目的是找到用户向量ui以及商品向量vj来表明用户偏好。这些向量分别是用户因素（特征）向量和商品因素（特征）向量。本质上，这些向量将用户和商品映射到一个公用的隐式因素空间，从而使它们可以直接比较。这和用于显式数据集的矩阵分解技术类似，但是包含两点不一样的地方：
（1）我们需要考虑不同的信任度，（2）最优化需要考虑所有可能的u，v对，而不仅仅是和观察数据相关的u，v对。显性反馈的矩阵分解优化时，对于missing data(没有评分)，是不会当做训练数据输入到模型的，优化时针对已知评分数据优化。而这里隐性反馈，是利用所有可能的u,i键值对，所以总的数据是m*n，其中m是用户数量，n是物品数量。这里没有所谓的missing data，因为假如u对i没有任何动作，我们就认为偏好值为0，只不过置信度较低而已。因此，通过最小化下面的损失函数来计算相关因素（factors）。

$$ min_{u,v}\sum {i,j}c{ij}(p_{ij}-u_{i}^{T}v_{j})^{2} + \lambda (\sum_{i}\left | u_{i} \right |^{2} + \sum_{j}\left | v_{j} \right |^{2}) $$