Question

1. 基于评分的协同过滤RatingBased CF 方法是从其它用户的评分中预估目标用户如何对目标商品进行评分的过程。一个理想的 RatingBased CF 需要满足以下条件：

   • 易于实现和维度：算法的可解释性强，并且易于实现和维护。
   • 即时更新：添加新的评分之后，模型能够立即更新预测。
   • 高性能：在线推荐速度应该非常快速，这可能需要以内存为代价。
   • 数据需求低：能够为评分数量较少的目标用户提供高质量的推荐。
   • 合理的推荐准确性：和效果最好的推荐相比具有可比的推荐质量，其中推荐质量的小幅提升并不值得牺牲简单性 simplicity 和可扩展性 scalability 。

   为此，论文 《Slope One Predictors for Online Rating-Based Collaborative Filtering》 提出的 Slope One 算法满足上述五个目标。论文的目标并不是比较各种 CF 算法的准确性，而是证明 Slop One 算法可以同时满足这五个目标。相比之下，其它的一些 CF 方法追求其中的一部分目标而牺牲了另外一些目标。

   Slope One 算法的基本思想是：不同item 之间的流行度差异 popularity differential 。我们以 pair 对的方式来决定item $ j $ 比item $ i $ 要好多少，从而计算流行度差异。一种简单的计算方式是：用item $ j $ 的评分减去item $ i $ 的评分。反之，如果已知item $ i $ 的评分，以及 $ j $ 和 $ i $ 的流行度差异，那么item $ j $ 的评分就可以计算到。

   考虑下图中的两个用户 $ A $ 和 $ B $ 以及item $ I $ 和 $ J $ 。用户 $ A $ 给item $ I $ 评分 1 分、用户 $ B $ 给item $ I $ 评分 2分、用户 $ A $ 给item $ J $ 评分 1.5 分。我们观察到item $ J $ 比item $ I $ 的评分更高，差异在 1.5 - 1 = 0.5 分，因此我们预计用户 $ B $ 将给item $ J $ 的评分为 2 + 0.5 = 2.5 分。我们称 $ B $ 为目标用户，item $ J $ 为目标商品。

   

   对于每个未知的评分，在训练集中存在大量的这种差异，则我们可以取这些差异的均值。Slop One 算法提供了三种方式来选择差异，并最终得到单个预测结果。Slope One CF 的预测形式为 $ f(x) = x + b $ ，其中 $ b $ 为平均的流行度差异。

   论文的主要贡献是提出了一个 Slope One CF 算法，并证明它和 memory-based 算法相比具有几乎相同的准确性，同时更适合 CF 任务。

2. 相关工作：

   • MemoryBased CF 使用 u-2-u 相似性来执行预测，其中相似函数的选择决定了推荐的质量。其缺点包括：

     • 可扩展性scalability ：MemoryBased CF 依赖于的 u-2-u 相似性计算复杂度太高，而这些计算无法通过离线预计算。
     • 数据稀疏的敏感性 sensitivity ：为满足推荐的高质量，MemoryBased CF 要求最低数量的用户（如至少 100 个用户)、最低数量的评分（如至少 20 个评分）。

     本文中我们将 Slope One CF 和众所周知的 MemoryBased CF 算法 Pearson 进行对比。

   • 也有一些 ModelBased CF，如基于线性代数的方法（如SVD、PCA）、基于机器学习的方法（如贝叶斯方法）、基于神经网络的方法、基于聚类的方法。与MemoryBased CF 相比，ModelBased CF 在线计算的性能很高，但是它们具有昂贵的离线学习阶段或者离线更新阶段。当在线速度至关重要时，ModelBased CF 算法相比 MemoryBased CF 更可取。

   • 我们的 Slope One CF 的形式为： $ f(x) = x + b $ ，其中 $ b $ 为常数、 $ x $ 表示评分变量，因此该方法叫做 slope one 。对于任何 item pair 对，我们试图找到从一个 item 评分中预测另一个 item 评分的最佳函数 $ f $ ，不同 item pair 的函数 $ f $ 可能不同。

     • 在 《Item-based collaborative filtering recommender algorithms》 中，作者考虑了 item pair 之间的相关性，然后将用户评分的加权均值作为评分变量，其中权重为相关系数。

       在该论文的简单版本中，预估形式为 $ f(x) = x $ ；在该论文的回归版本中，预估形式为 $ f(x) = ax+b $ 。

     • 在论文 《A regression-based approach for scaling-up personalized recommender systems in e-commerce》 中，作者也使用了 $ f(x) = ax+b $ 形式的预估。

     这两篇论文工作的一个自然扩展是考虑 $ f(x) = ax^2 + b x+c $ 形式的预估。相反，本文中我们使用形式为 $ f(x) = x + b $ 的预估。在 《A regression-based approach for scaling-up personalized recommender systems in e-commerce》 中观察到，即使他们使用基于回归的 $ f(x) = ax+b $ 算法也没有导致相对 MemoryBased CF 算法的较大改进。因此，证明 $ f(x) = x +b $ 形式的预估可以与 MemoryBased CF 算法竞争，这是本文的一个重要结果。

5.1 模型

1. 给定用户 $ u $ ，定义他/她的评分 array 记作：

   $ \mathbf{\vec r}_u = (r_{u,1},r_{u,2},\cdots,r_{u,n})^T $

   其中第 $ i $ 个元素 $ r_{u,i} $ 对应于item $ i $ 的评分。由于存在大量的未评分item ，因此这个向量是不全的 incomplete 。

   定义用户 $ u $ 评分的所有item 为 $ \mathbb I_u $ ，用户 $ u $ 的平均打分为 $ \bar r_u $ ：

   $ \mathbb I_u = \{i\mid r_{u,i} \gt 0\}, \quad \bar r_u = \frac{1}{|\mathbb I_u|}\sum_{i\in \mathbb I_u}r_{u,i} $

   定义训练集的所有评分 array 为 $ \mathbb X $ ： $ \mathbb X = \{\mathbf{\vec r}_u\mid u\in \mathbb U\} $ ，其中 $ \mathbb U $ 为所有用户。

   定义 $ \mathbb U_i $ 为包含item $ i $ 的用户集合 ： $ \mathbb U_{i} = \{u\mid u\in \mathbb U \;\text{and}\; r_{u,i} \gt 0\} $ 。定义同时包含item $ i,j $ 的用户集合为： $ \mathbb U_{i,j} = \{u\mid u\in \mathbb U \;\text{and}\; r_{u,i} \gt 0\;\text{and} \; r_{u,j}\gt 0\} $ 。定义用户 $ u,v $ 共同评分的item 集合为： $ \mathbb I_{ u,v}=\{i\mid i\in \mathbb I\;\text{and}\; r_{u,i}\gt 0\;\text{and} \; r_{v,i}\gt 0\} $ 。

   定义预测 $ \mathbf{\vec p}_u = (p_{u,1},\cdots,p_{u,n})^T $ ，其中每个元素代表一个预测结果。

2. RatingBased CF 在线预测时， 首先提供一个评分 array （称作 query array）， 它包含用户的所有评分item ；模型返回一个预测array（称作 response array），其中包含用户尚未评分的item 及其预估的评分。

5.1.1 baseline

1. 最简单的 baseline 为 PER USER AVERAGE：

   $ p_{u,i} = \bar r_u,\quad i\notin \mathbb I_u $

   即：预测用户的所有未评分item 的评分为该用户的评分均值。

2. 针对PER USER AVERAGE 的一种改进方式为 BIAS FROM MEAN（也被称作 NON PERSONNALIZED），其预测结果为：

   $ p_{u,i} = \bar r_u + \frac{1}{|\mathbb U_i|}\sum_{v \in \mathbb U_i}(r_{v,i} - \bar r_v),\quad i\notin \mathbb I_u $

   它考虑了用户 $ u $ 的评分均值，以及所有其它用户在该item 上的评分差异（其它用户在该 item 上的评分减去用户平均均值）。

3. 基于MemoryBased CF 的一个经典实现是 PEARSON 方案：

   $ p_{u,i} = \bar r_u + \frac{\sum_{v \in\mathbb U_i} \gamma(u,v)(r_{v,i} - \bar r_v)}{\sum_{v \in\mathbb U_i} |\gamma(u,v)|},\quad i\notin \mathbb I_u $

   它在 BIAS FROM MEAN 的基础上考虑了用户 $ u,v $ 之间的相似性。其中 $ \gamma $ 为Pearson 相关系数，它刻画了用户之间的相似性：

   $ \text{corr}(u,v) = \frac{\sum_{i\in\mathbb I_{u,v}}(r_{u,i}- \bar r_u)(r_{v,i}- \bar r_v)}{\sqrt{\sum_{i\in \mathbb I_ {u,v}}(r_{u,i}- \bar r_u)^2\sum_{i\in\mathbb I_{u,v}}(r_{v,i} - \bar r_v)^2}}\\ \gamma(u,v) = \text{corr}(u,v)|\text{corr}(u,v)|^{\rho-1} $

   其中 $ \rho=2.5 $ 为 Case Amplification 系数，它降低了数据中的噪音。

   • 如果相关系数很高，如 corr = 0.9，则经过 Case Amplification 之后它仍然很高： $ 0.9^{2.5} \simeq 0.8 $ 。
   • 如果相关系数很低，如 corr = 0.1，则经过 Case Amplification 之后它可以忽略不计： $ 0.1^{2.5}\simeq 0.003 $ 。

   尽管存在更准确的方法，但是 PEARSON 相关系数以及 Case Amplification 一起已经能够提供相当好的推荐质量。

4. 采用 adjusted cosine 相似度的 ItemBased CF ：给定item $ i $ 和 $ j $ ，定义相似度为：

   $ \text{sim}(i,j) = \frac{\sum_{u\in \mathbb U_{i,j}}(r_{u,i}-\bar r_u)(r_{u,j}-\bar r_u)}{\sum_{u\in \mathbb U_{i,j}}(r_{u,i}-\bar r_u)^2\sum_{u\in \mathbb U_{i,j}}(r_{u,j}-\bar r_u)^2} $

   使用基于回归Regression 的预测为：

   $ p_{u,i} = \sum_{j\in \mathbb I_u} w_{i,j} (\alpha_{i,j}r_{u,j} + \beta_{i,j}),\quad i\notin \mathbb I_u\\ w_{i,j} = \frac{|\text{sim}(i,j)|}{\sum_{j^\prime\in \mathbb I_u} |\text{sim}(i,j^\prime)|} $

   其中 $ \alpha_{i,j},\beta_{i,j} $ 为回归系数，它根据最小化目标来求得：

   $ \arg\min_{\alpha_{i,j},\beta_{i,j}} \sum_{u\in \mathbb U_{i,j}} (\alpha_{i,j} r_{u,j} +\beta_{i,j} - r_{u,i})^2 $

5.1.2 Slope One

1. slope one 方法同时考虑了来自相同 item 的其它用户的评分（就像ItemBased CF ）、来自相同用户的其它 item 的评分（就像 MemoryBased CF），除此之外slope one 方法还依赖于既不是相同 item 、也不是相同用户的那些评分。因为这些评分数据都有助于我们进行预测。

   slope one 方法的大部分优势都来自于 ItemBased CF、MemoryBased CF 未考虑的数据。

2. 给定用户 $ u,v $ ，我们寻找最佳的预测器 predictor 来从 $ u $ 的评分中预测 $ v $ 的评分。

   slope one 方法选择的 predictor 为斜率为1 的线性函数 $ f(x) = x + b $ ，这就是名字 slope one 的由来。 具体而言，我们需要拟合方程：

   $ r_{v,i}^\prime = r_{u,i} + b ,\quad i\in \mathbb I_{u,v} $

   我们通过最小化残差：

   $ \arg\min_b \sum_{i\in \mathbb I_{u,v}}(r_{v,i} - r^\prime_{v,i})^2 $

   通过残差的偏导数为0，我们得到：

   $ b = \frac{\sum_{i\in \mathbb I_{u,v}}(r_{v,i} - r_{u,i})}{|\mathbb I_{u,v}|} $

   因此 $ b $ 是用户 $ u $ 和 $ v $ 的评分差异的均值。

3. 类似地，我们可以通过利用item $ i $ 的评分来预测item $ j $ 的评分。同样的推导过程，我们有：

   $ b = \frac{\sum_{u\in \mathbb U_{i,j}}(r_{u,j} - r_{u,i})}{|\mathbb U_{i,j}|} $

   给定训练集 $ \mathbb X $ ，以及任意两个item $ i,j $ ，我们定义item $ i $ 到item $ j $ 的平均偏移为：

   $ \text{dev}_{j,i} =\frac{1}{|\mathbb U_{i,j}|} \sum_{u\in \mathbb U_{i,j}} (r_{u,j} - r_{u,i}) $

   因此在给定 $ r_{u,i} $ 的条件下， $ r_{u,j} $ 的预测值为：

   $ r_{u,j}^\prime = \text{dev}_{j,i} + r_{u,i} $

   考虑所有这样的 $ r_{u,i} $ ，因此用户 $ u $ 在 item $ j $ 上的 predictor 定义为：

   $ p_{u,j} = \frac{1}{|\mathbb S_{u,j}|} \sum_{i\in \mathbb S_{u,j} } (\text{dev}_{j,i} + r_{u,i}) $

   其中 $ \mathbb S_{u,j}=\{i\mid i\in \mathbb I_u\;\text{and}\;i\ne j\;\text{and}\; \mathbb U_{i,j} \ne \Phi\} $ ，即：用户 $ u $ 同时评分的、且与 $ j $ 有共同评分用户的item 的集合。

   当数据足够稠密，即几乎所有item pair 对之间都有评分时，有： $ \mathbb S_{u,j} = \mathbb I_u $ 。考虑到：

   $ \frac{1}{|\mathbb S_{u,j}|}\sum_{i\in \mathbb S_{u,j}}r_{u,i}\simeq \frac{1}{|\mathbb I_{u}|}\sum_{i\in \mathbb I_{u}}r_{u,i} = \bar r_u $

   因此有：

   $ p_{u,j} = \bar r_u + \frac {1}{|\mathbb I_u|}\sum_{i\in \mathbb I_u}\text{dev}_{j,i} $

   可以看到：slope one 方法不依赖于用户对具体item 的评分，而依赖于用户的平均评分，以及用户对哪些item 进行评分。

4. slop one 方法的关键数据是item 之间的偏移矩阵：

   $ \mathbf E = \begin{bmatrix} 0&\text{dev}_{1,2}& \text{dev}_{1,3}& \cdots & \text{dev}_{1,n}\\ \text{dev}_{2,1}&0& \text{dev}_{2,3}& \cdots & \text{dev}_{2,n}\\ \vdots&\vdots&\vdots& \ddots & \vdots\\ \text{dev}_{n,1}&\text{dev}_{n,2}& \text{dev}_{n,3}& \cdots & 0 \end{bmatrix} $

   其中 $ E_{i,j} = - E_{j,i} $ 。

   偏移矩阵 $ \mathbf E $ 可以预计算，并且当有新数据进来时实时更新。

5. ItemBased CF 中，我们需要根据相似商品的评分来给出结果。

   • 朴素版本的 predictor 可以视作 $ f(x) = x $ 的加权聚合结果：

     $ p_{u,i} = \sum_{j\in \mathbb I_{u,i}}w_{i,j} \times r_{u,j}\\ w_{i,j} = \frac{s_{i,j}}{\sum_{j^\prime\in \mathbb I_{u,i}}s_{i,j^\prime}} $

   • 基于回归的predictor 可以视为 $ f(x) = \alpha x +\beta $ 的加权聚合结果：

     $ p_{u,i} = \sum_{j\in \mathbb I_{u,i}}w_{i,j} \times (\alpha_{i,j}\times r_{u,j}+\beta_{i,j}) \\ w_{i,j} = \frac{s_{i,j}}{\sum_{j^\prime\in \mathbb I_{u,i}}s_{i,j^\prime}} $

   slope one 方法采用 $ f(x) = x +b $ 的聚合结果，但是没有使用相似性进行加权：

   $ p_{u,i} = \bar r_u + \frac {1}{|\mathbb I_u|}\sum_{j\in \mathbb I_u}\text{dev}_{i,j} $

   事实上可以进一步的扩展到 $ f(x) = ax^2 + b x +c $ 的形式。

6. Weighted Slope One：slope one 方法的一个缺点是未考虑已经评分的数量。

   假设给定用户 A 对item J, K 的评分，我们需要预测用户 A 对item L 的评分。如果有 2000 个用户同时对item J,L 评分、有 20 个用户对item K,L 评分，则商品 J 相比商品 K 更适合作为商品 L 的 predictor。因为 $ \text{dev}_{L,J} $ 比 $ \text{dev}_{L,K} $ 更为置信。

   因此定义 Weighted Slope One 预测为：

   $ p_{u,j} = \frac{\sum_{i\in \mathbb S_{u,j} }(\text{dev}_{j,i} + r_{u,i})\times |\mathbb U_{i,j}|}{\sum_{i\in \mathbb S_{u,j} } |\mathbb U_{i,j}|} $

   .

5.1.3 Bi-Polar Slope One

1. 给定一个0 到 10 的评分等级表，我们认为评分超过 5 分表示用户喜欢的item ，评分低于 5 分表示用户不喜欢的item 。如果用户的评分是均匀分布的，则阈值设置为 5 分没有问题。但是通常用户的评分不是均匀分布的，如 EachMovie 数据集中超过 70% 的评分都超过 5 分。

   考虑到用户评分的分布多种多样，如均匀分布、倾向于乐观的分布(均值超过5 分)、倾向于悲观的分布(均值低于 5 分)、双峰分布（同时偏向于两个极端）。为了自适应这些分布，我们不再设置固定的阈值，而是使用自适应的阈值：将喜欢/不喜欢阈值设定为用户评分的均值。对于一个用户而言：

   • 评分低于该用户所有评分均值的item 被视为用户不喜欢的item 。
   • 评分高于该用户所有评分均值的item 被视为用户喜欢的item 。

   这种方式可以确保我们能够为每个用户提供合理数量的喜欢/不喜欢item 。

2. Weighted Slope One 倾向于更加高频的评分模式，Bi-Polar Slope One 倾向于某种偏好的评分模式。

   Bi-Polar Slope One 方法将预测拆分为两个部分：

   • 从用户喜欢的item中使用 Weighted Slope One 得出一个预测。
   • 从用户不喜欢的item中使用 Weighted Slope One 得出另一个预测。

   然后合并这两部分的预测，即可得到 Bi-Polar Slope One 的预测。

3. Bi-Polar Slope One 方法从两个角度进行了改进：

   • 首先在item方面，仅考虑用户的两个喜欢item之间的评分偏差，或者两个不喜欢item之间的偏差。即对 $ \mathbb S_{u,j} $ 进行限制。

     根据用户不喜欢的item去预估用户喜欢的item（或者反过来）没有意义。

   • 其次在用户方面，在计算item之间偏差时，我们仅仅考虑同时喜欢、或者同时不喜欢这两个item的用户。即对 $ \text{dev}_{i,j} $ 进行限制。

   我们拆分每个用户的评分item集合为：

   $ \mathbb I_u^{like} = \{i\mid i \in \mathbb I \;\text{and}\; r_{u,i} \gt \bar r_u\}\\ \mathbb I_u^{dislike} = \{i\mid i \in \mathbb I \;\text{and}\; r_{u,i} \lt \bar r_u\} $

   然后对于每对 `item pair 对 $ (i,j) $ ，拆分它们的共同评分用户集合为：

   $ \mathbb U_{i,j}^{like} = \{u\mid i\in \mathbb I_u^{like} \;\text{and}\; j\in \mathbb I_u^{like}\}\\ \mathbb U_{i,j}^{dislike} = \{u\mid i\in \mathbb I_u^{dislike} \;\text{and}\; j\in \mathbb I_u^{dislike}\} $

   我们计算偏差矩阵为：

   $ \text{dev}_{j,i}^{like} =\frac{1}{|\mathbb U_{i,j}^{like}|} \sum_{u\in \mathbb U_{i,j}^{like}} (r_{u,j} - r_{u,i})\\ \text{dev}_{j,i}^{dislike} =\frac{1}{|\mathbb U_{i,j}^{like}|} \sum_{u\in \mathbb U_{i,j}^{dislike}} (r_{u,j} - r_{u,i}) $

   最终我们的预测为：

   $ p_{u,j} = \frac{\sum_{i\in \mathbb S_{u,j}^{like} }(\text{dev}_{j,i}^{like} + r_{u,i})\times |\mathbb U_{i,j}^{like}|+ \sum_{i\in \mathbb S_{u,j}^{dislike} }(\text{dev}_{j,i}^{dislike} + r_{u,i})\times |\mathbb U_{i,j}^{dislike}|}{\sum_{i\in \mathbb S_{u,j}^{like} } |\mathbb U_{i,j}^{like}|+ \sum_{i\in \mathbb S_{u,j}^{dislike} } |\mathbb U_{i,j}^{dislike}|} $

   其中 ：

   • 其中 $ \mathbb S_{u,j}^{like}=\{i\mid i\in \mathbb I_u^{like}\;\text{and}\;i\ne j\;\text{and}\; \mathbb U^{like}_{i,j} \ne \Phi\} $ ，即：用户 $ u $ 同时喜欢的、且与 $ j $ 有共同喜欢用户的item的集合。
   • 其中 $ \mathbb S_{u,j}^{dislike}=\{i\mid i\in \mathbb I_u^{dislike}\;\text{and}\;i\ne j\;\text{and}\; \mathbb U_{i,j}^{dislike} \ne \Phi\} $ ，即：用户 $ u $ 同时不喜欢的、且与 $ j $ 有共同不喜欢用户的item的集合。

4. Bi-Polar Slope One 将每个用户的item区分为喜欢、不喜欢，这相当于使得用户数量增加一倍。但是由于算法在计算过程中的限制（item方面的限制和用户方面的限制），这使得预测过程的计算量总体上得到降低。

   另外，由于用户数量翻倍、评分数量不变，这加剧了数据稀疏性。在数据更加稀疏的条件下Bi-Polar Slope One 还能够改善推荐质量，这似乎是违反直觉的。但是如果在预测过程中不去剔除无关的评分，其危害更大。

   Bi-Polar Slope One 无法从 “用户 A喜欢商品 K、用户 B不喜欢商品 K” 中预测任何结果，这也是符合直觉的。

5.2 实验

2. 评估指标：测试集上的预测的均方误差 MAE 。我们采用 All But One MAE。在计算 MAE 时，我们从测试集每个用户中随机隐藏一个评分，然后预估这个评分。

3. 数据集：

   • EachMovie 数据集：Compaq Research 提供的 EachMovie 数据集，评分等级从 0.0 到 1.0， 每 0.2 一个等级。
   • MovieLens 数据集：Minnesota 大学 Grouplens Research Group 提供的 Movielens 数据集，评分等级从 1 分到 5 分，每1 分一个等级。

   我们选择 5 万个用户作为训练集 $ \mathbb X $ ，至少 10 万个用户作为测试集。当预测结果超出范围时，进行修正：EachMovie 预测结果超过 1.0 调整为 1.0 分， MovieLens 预测结果超过 5 调整为 5 分。

   由于 MovieLens 分值范围比 EachMovie 大 4 倍，因此 MovieLens 评估的 MAE 指标除以 4 从而得到可比的结果。

4. 实验结果如下表所示，可以看到：

   • Slope One 方法在所有 baseline 中表现最好，达到和 PEARSON 相匹配的准确率。这表明尽管 Slope One 具有理想的特点，它的准确率仍然可以得到保持。
   • 针对原始的 Slope One 的改进确实能够提高推荐的准确性。 Weighted Slope One 能够提高大约 1%， Bi-Polar Slope One 能够提高大约 3% 。