Question

1. 现代消费者被各种选择所淹没。电商和内容提供商提供种类繁多的产品，有前所未有的机会来满足用户各种特殊的需求和口味。为消费者匹配最合适的产品并非易事，但却是提高用户满意度和忠诚度的关键。这强调了推荐系统的重要性，它提供个性化的产品推荐来满足用户口味。Amazon、谷歌、Netflix、TiVo、雅虎等互联网领头羊越来越多地采用此类推荐系统。

   推荐系统通常基于协同过滤Collaborating Filtering:CF ，它仅依赖于用户过去的行为（如，用户历史交易记录或评分记录）而无需创建显式的用户画像或item 画像。值得注意的是：一方面，协同过滤不依赖于任何领域知识domain knowledge ，也不需要大量的画像数据；另一方面，协同过滤可以发现复杂的或者意料之外的行为模式，这些模型很难基于用户画像或item 画像来刻画。 因此，协同过滤在过去十年中引起了广泛的关注，取得了重大进展，并被一些成功的商业系统（如 Amazon、TiVo、Netflix ）采用。

   CF 系统需要比较本质上不同的两种对象：user 和 item 。主要有两类方法可以执行这种比较，这两种方法构成了CF 的两个主要流派discipline：

   • 邻域方法 neighborhood approach：邻域方法的核心是计算 item 之间的相似性或者 user 之间的相似性。

     ItemBased CF 利用同一个用户的、和 item $ j $ 相似的 item 的评分来评估该用户对 item $ j $ 的评分。从某种意义上讲，该方法将user 视为一组已评分item 的集合，从而将 user 映射到 item 空间。这样我们不需要将 user 和 item 进行比较，而是直接将 item 和 item 进行比较。

   • 潜在因子模型latent factor model：诸如奇异值分解SVD 之类的潜在因子模型通过将 user 和 item 分别映射到同一个潜在因子空间，从而使得它们可以直接进行比较。

     潜在因子模型试图根据用户反馈来自动推断出用户因子user factor、 item 因子 item factor， 从而解释评分。例如，当 item 是电影时，因子可能是某些显著的维度（如：电影流派、是否适合儿童等等），也可能是不显著的维度（如：演员的气质），甚至也可能是完全无法解释的维度。

   自 2006 年 10 月 Netflix Prize 竞赛开始以来，CF 领域一直备受关注。Netflix 发布了一个包含 1 亿个电影评分的数据集，并要求学术界开发能够超越其推荐系统 Cinematch 准确性的算法。论文 《Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model》 的作者从这次比赛中学到的一个教训是：邻域方法和潜在因子方法解决了数据中不同层次level 的结构，因此它们都不是最优的。

   • 邻域模型在检测局部关系最为有效，它依赖于少数几个重要的邻域关系，从而忽略了用户的其它绝大多数评分。因此该方法无法捕获用户所有评分中包含的全部弱信号。
   • 潜在因子模型通常有效地估计与所有 item 有关的整体结构。但是它在检测少数紧密相关的item 之间的局部强相关性表现不佳，而这恰恰是邻域模型做得最好的地方。

   在论文 《Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model》 中，作者提出了一个组合模型，该模型同时利用邻域方法和潜在因子方法的优势来提高预测准确性。据作者所知，这是第一次将这两种方法集成到单个模型中。事实上，过去的一些工作认识到结合这些方法的效用。然而，他们建议对因子分解结果进行后处理，而不是同时地考虑邻域信息和因子信息的统一模型。

   作者从 Netflix Prize 竞赛中吸取的另一个教训是：将不同形式的用户输入集成到模型中的重要性。推荐系统依赖于不同类型的输入。

   • 最方便的、最高质量的是用户显式反馈，其中包括用户对item 的显式输入。例如，Netflix 收集电影的星级评分，TiVo 用户通过点击 thumbs-up/down 按钮来表明他们对电视节目的偏好。
   • 但是显式反馈并非始终可以获取，因此推荐系统可以从更丰富的隐式反馈中推断用户的偏好。这些隐式反馈通过观察用户行为来间接反应偏好，反馈类型包括：历史购买记录、历史浏览记录、历史搜索记录甚至历史鼠标移动记录。例如，购买了同一作者的多本书的用户可能喜欢该作者。

   论文主要关注提供显式反馈的情况，但是也认识到隐式反馈的重要性：可以解释没有提供足够显式反馈的用户。因此，论文的模型同时集成了显式反馈和隐式反馈。

   最终，论文的方法同时利用邻域方法和潜在因子方法、同时利用了用户的显式反馈和隐式反馈。

2. 我们根据 Netflix 数据对匿名用户的超过 1 亿个评分评估了算法。为了保持和其他人发布的结果可比，我们采用 Netflix 设置的一些标准：采用测试集 RMSE 来评估模型效果。Netflix 提供的测试集包含了 140 万个近期的评分，另外 Netflix 还提供了另外的 140 万个近期评分作为验证集（也称作 Probe Set）。

   注意：Netflix 给出的测试集和验证集包含了很多低频用户，这些用户的评分数量很少。这使得任务难度非常大。在某种程度上，这也代表了 CF 系统的真实需求：对老用户预测最新的评分，并且公平地对待所有用户，而不仅仅是只考虑高频用户。

   Netflix 数据集是正在进行的 Netflix Prize 竞赛的一部分，其中 benchmark 是 Netflix 专属系统 Cinematch，它在测试集上的 RMSE 为 0.9514。大奖将颁发给测试集 RMSE 低于 0.8563（改进 10%）的团队。在本文中我们将测试集 RMSE 降低到 0.887 左右的水平，这比之前在该数据集上发布的结果要好。

9.1 模型

1. 令 $ r_{u,i} $ 表示用户 $ u $ 在 item $ i $ 上的评分，评分越高表示用户 $ u $ 越喜欢 item $ i $ ；令 $ \hat r_{u,i} $ 表示模型预估的用户 $ u $ 对 item $ i $ 的评分。

   定义 $ \mathcal K = \{(u,i)\mid r_{u,i}\; \text{is known}\} $ 为评分已知的 user-item pair 对；定义 $ \mathbb U $ 为所有用户集合， $ \mathbb I $ 为所有 item 集合；定义 $ \mathbb U_i $ 为对 item $ i $ 评分的用户集合， $ \mathbb I_u $ 为用户 $ u $ 评分的item 集合：

   $ \mathbb U_i = \{u\mid (u,i) \in \mathcal K\},\quad \mathbb I_u=\{i\mid (u,i)\in \mathcal K\} $

2. 通常绝大多数评分是未知的，即 $ \frac{\mathcal K}{|\mathbb U|\times |\mathbb I|} $ 占比非常低，其中如， Netflix 数据有 99% 的评分缺失。为了避免模型对稀疏数据的过拟合，我们通常采用正则化技术。正则化系数由常数 $ \lambda_1,\lambda_2,\cdots $ 等等来控制，正则化系数越大则正则化越强。

9.1.1 前置知识

a. Baseline Model

1. 最简单的预估模型为： $ \hat r_{u,i} = \mu $ ，其中 $ \mu $ 为所有 user-item 的均值：

   $ \mu = \frac{\sum_{(u,i)\in \mathcal K} r_{u,i}}{|\mathcal K|} $

   但是考虑到用户效应或者 item 效应：某些用户相对于其它用户始终会给一个较高的评分、某些item 相对于其它item 始终会收到一个较高的评分，那么我们的 Baseline 模型为：

   $ b_{u,i} = \mu + b_u + b_i $

   其中： $ b_u $ 为用户 $ u $ 对均值的偏差、 $ b_i $ 为item $ i $ 对均值的偏差，它们都是模型的参数。

   例如：假设所有用户的电影评分为 $ \mu = 3.7 $ 。假设用户 A 的评分比较苛刻，他的评分比平均水平低 $ 0.3 $ 分；假设电影 I 比较热门，它收到的评分比平均水平高 0.5 。则用户 A 对电影 I 的评分预测为： $ 3.7-0.3+0.5 = 3.9 $ 分。

2. Baseline 模型的损失函数为带正则化的平方误差：

   $ \min_{\mathbf{ b}} \sum_{(u,i)\in \mathcal K}(r_{u,i} -\mu - b_u-b_i)^2+ \lambda_1\left(\sum_{u\in \mathbb U}b_u^2 + \sum_{i\in \mathbb I}b_i^2\right) $

   其中 $ \mathbf{ b} = \{b_u,b_i\mid u\in \mathbb U, i\in \mathbb I\} $ 为所有参数。

   第一项为模型预估的平方误差，第二项为正则化项。该最优化问题为简单的凸优化，可以通过最小二乘法求解。

b. 邻域模型

1. 协同过滤方法最常用的模型是邻域模型 neighborhood model 。

   • 几乎所有早期的协同过滤系统都是UserBased CF ，这种面向用户的方法基于兴趣相同的用户的评分来预估。

   • 后来基于ItemBased CF 更为流行，它使用同一个用户在相似item 上的评分来预估。

     ItemBased CF 具有更好的可扩展性、准确性，另外它的可解释性也更好：因为用户熟悉他们以前喜欢过的 item， 但是用户不认识那些 ”兴趣相投“ 的其它用户。

     我们这里重点介绍 ItemBased CF，但是也可以通过切换user 和 item 的角色来开发一个 UserBased CF 版本。

2. 大多数ItemBased CF 方法的核心是计算 item 之间的相似性。通常采用基于 Pearson 相关系数 $ \rho_{i,j} $ 作为相似性的度量，它衡量了所有用户在 item $ i $ 和 item $ j $ 上评分的相似性。

   考虑到评分是稀疏的，因此很多 item 之间仅共享非常少的几个评分用户，而相关系数的计算仅仅在这些很少的、共同的评分用户上进行。因此，当共享的评分用户越少，计算到的相关系数越不可靠。即：共同评分用户的规模越大，则相关系数越可靠。因此我们调整相关系数为：

   $ s_{i,j} = \frac{n_{i,j}}{n_{i,j}+\lambda_2} \rho_{i,j} $

   其中 $ n_{i,j} $ 为 item $ i $ 和 item $ j $ 之间共同评分的用户数量， $ \lambda_2 $ 为平滑系数，典型的值为 100 。

3. 给定 item $ i $ 和用户 $ u $ ，我们定义用户 $ u $ 已经评分过的、和 item $ i $ 最相似的 top k 个 item 为 $ \mathcal S^k(i;u) $ 。

   用户 $ u $ 对 item $ i $ 的预估评分看作是这些相似 item 的评分的加权均值，同时考虑了 user 效应和 item 效应：

   $ \hat r_{u,i} = b_{u,i} + \sum_{j\in \mathcal S^k(i;u)}w_{i,j}^u (r_{u,j} - b_{u,j})\\ w_{i,j}^u = \frac{s_{i,j}}{\sum_{j^\prime\in \mathcal S^k(i;u)}s_{i,j^\prime}},\quad b_{u,i} = \mu + b_u + b_i $

   这里 $ w_{i,j}^u $ 表示 item 权重不仅和 item $ i $ 、 $ j $ 的相似度有关，还和用户 $ u $ 有关。

4. 因为这种形式的邻域模型直观且易于实现，因此该方法非常流行。但是我们有一些不同的看法：

   • 首先，该方法并没有正式的数学模型来证明其有效性。
   • 其次，在计算item $ i $ 和 $ j $ 的相似性时，仅仅考虑这两个item 的评分，而完全忽略了所有其它的 item 。这种方式计算得到的相似性是否合适，该问题还无法证明。
   • 最后，上式中的权重 $ w_{i,j} $ 满足 $ \sum_{j\in \mathcal S^k(i;u)} w_{i,j} = 1 $ 。实际上当用户 $ u $ 的行为非常稀疏时，即使 $ i $ 和 $ j $ 相似度很低时，其权重 $ w_{i,j} $ 仍然可能较大。

   因此我们提出了一个更准确的邻域模型：给定邻域集合 $ \mathcal S^k(i;u) $ ，我们计算插值权重 interpolation weight $ \{\theta_{i,j}^u\mid j\in \mathcal S^k(i;u)\} $ ，从而实现预测：

   $ \hat r_{u,i} = b_{u,i} + \sum_{j\in \mathcal S^k(i;u)} \theta_{i,j}^u(r_{u,j} - b_{u,j}) $

   完整的说明参考论文《Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights》 。

   这种插值权重存在一个严重的问题：模型容量空间太大，很容易过拟合。插值权重相当于自动学习 item 权重 $ w_{i,j}^u $ ，参数规模 $ O(|\mathbb I|^2 \times |\mathbb U|) $ ，而数据量仅有 $ O(|\mathbb I|\times |\mathbb U|) $ 。

c. 潜在因子模型

1. 潜在因子模型是协同过滤的另一种方法，其目标是找出揭示观测评分的潜在因子，典型的模型为 pLSA、神经网络、LDA 。我们将集中讨论 user-item 评分矩阵上的 SVD 分解相关的模型。

   近年来，由于 SVD 模型具有准确性、可扩展性等优点，因此广受欢迎。对于每个用户 $ u $ ， SVD 模型关联一个用户因子 $ \mathbf{\vec p}_u\in \mathbb R^f $ ； 对于每个item $ i $ ，SVD 模型关联一个 item 因子 $ \mathbf{\vec q}_i\in \mathbb R^f $ 。我们通过因子之间的内积来执行预测： $ \hat r_{u,i} = b_{u,i} + \mathbf{\vec p}_u^\top \mathbf{\vec q}_i $ 。

   在信息检索领域已经可以很好地利用 SVD 来识别潜在的语义因子，但是在协同过滤领域由于大量的评分缺失，这会给SVD 的应用带来困难：

   • 首先，当矩阵不全时，传统的 SVD 是未定义的。
   • 其次，如果仅针对稀疏的、已经评分的部分进行拟合，则模型容易陷入过拟合。

   可以对已评分部分进行拟合，同时采用正则化技术来缓解过拟合：

   $ \min_{\mathbf P,\mathbf Q,\mathbf{ b}} \sum_{(u,i)\in \mathcal K}\left(r_{u,i} - \mu - b_u - b_i - \mathbf{\vec p}_u^\top \mathbf{\vec q}_i\right)+\lambda_3\left(\sum_{u\in \mathbb U}||\mathbf{\vec p}_u||^2 + \sum_{i\in \mathbb I}||\mathbf{\vec q}_i||^2 + \sum_{u\in \mathbb U}b_u^2 + \sum_{i\in \mathbb I}b_i^2\right) $

   其中：

   • 其中 $ \mathbf P = \{\mathbf{\vec p}_u\mid u\in \mathbb U\},\mathbf Q = \{\mathbf{\vec q}_i\mid i\in \mathbb I\},\mathbf{ b} = \{b_u,b_i\mid u\in \mathbb U, i\in \mathbb I\} $ 为所有参数。
   • 第一项为模型预估的平方误差，第二项为正则化项。

   然后基于梯度下降来求解该问题。

2. 《Improving Regularized Singular Value Decomposition for Collaborative Filtering》 提出了NSVD 模型，该模型避免显式地参数化每个用户的参数，而是根据他们已经评分的item 来对用户进行建模。因此，每个 item 关联两个因子向量 $ \mathbf{\vec q}_i $ 和 $ \mathbf{\vec x}_i $ 。用户 $ u $ 的 representation 为：

   $ \mathbf{\vec p}_u=\frac{1}{\sqrt{|\mathbb I_u|}} \sum_{j\in \mathbb I_u}\mathbf{\vec x}_j $

   因此有：

   $ \hat r_{u,i} = b_{u,i} + \left(\frac{1}{\sqrt{|\mathbb I_u|}} \sum_{j\in \mathbb I_u}\mathbf{\vec x}_j\right)^\top \mathbf{\vec q}_i $

   在本文中，我们将扩展该方法。

d. 隐式反馈

1. 如前所述，我们的模型融合了显式反馈和隐式反馈。对于诸如 Netflix 之类的数据，最自然的隐式反馈是电影租借的历史记录。这些数据可以间接反馈用户的偏好，但是这类数据我们无法取到。

   另一种不太明显的隐式数据为：用户是否对电影进行评分。即，可以通过用户是否评分来侧面反应了他们的偏好。这使得评分矩阵退化为 0-1 二元矩阵，其中 1 代表已经评分、0 代表尚未评分。这种二元隐式反馈数据并不像其它类型的隐式反馈数据那样独立和数据量大，但是我们发现它确实可以显著提高预测准确性。一个原因是：它可以从测试数据集中获得隐式反馈。

   我们的模型不限于具体的隐式数据类型。为了保持通用性，每个用户 $ u $ 和两组 item 关联：一组item 用 $ \mathbb I_u $ 表示，它表示显式反馈的 item 集合；另一组 item 用 $ \mathbb N_u $ 表示，它表示隐式反馈的 item 集合。

9.1.2 新的邻域模型

2. 前面介绍的邻域模型使用了特定于具体用户的权重 $ w_{i,j}^u $ 或者插值权重 $ \theta_{i,j}^u $ 。为了进行全局优化，我们希望抛弃此类 user-specific 权重，转而使用全局权重。

   定义 item $ j $ 相对于 item $ i $ 的权重为 $ w_{i,j} $ ，模型的初始版本为：

   $ \hat r_{u,i} = b_{u,i} + \sum_{j\in \mathbb I_u} (r_{u,j} - b_{u,j})w_{i,j} $

   其中 $ w_{i,j} $ 为模型参数，它从训练数据中学习得到。

   与 $ \hat r_{u,i} = b_{u,i} + \sum_{j\in \mathcal S^k(i;u)} \theta_{i,j}^u(r_{u,j} - b_{u,j}) $ 相比，我们这里有两个区别：

   • 权重 $ w_{i,j} $ 和用户 $ u $ 无关。
   • 考虑的item 集合为 $ \mathbb I_u $ ，而不是 $ \mathcal S^k(i;u) $ 。

3. 通常邻域模型中的权重代表了未知评分与已知评分相关的插值系数，但是这里我们采用不同的观点：权重 $ w_{i,j} $ 代表了和 baseline 的偏移量，残差 $ (r_{u,j} - b_{u,j}) $ 代表了这些偏移量施加的系数。即我们在 $ u $ 对 $ i $ 的评分 baseline 上增加了 $ (r_{u,j} - b_{u,j})w_{i,j} $ ：对于两个相关的 item $ i,j $ ，我们预计 $ w_{i,j} $ 会很高；进一步地，如果 $ u $ 在 $ j $ 上的评分超过预期，即 $ (r_{u,j} - b_{u,j}) $ 很大，则我们预计 $ u $ 对 $ i $ 的评分会更高。

   这一观点带来几个改进：

   • 首先我们可以使用隐式反馈，它提供了另一种方式来了解用户偏好。因此我们修改模型为：

     $ \hat r_{u,i} = b_{u,i} + \sum_{j\in \mathbb I_u} (r_{u,j} - b_{u,j})w_{i,j} +\sum_{j\in \mathbb N_u} c_{i,j} $

     类似于 $ w_{i,j} $ ，参数 $ c_{i,j} $ 也被视作添加到 baseline 预估上的偏移量。

     对于两个item $ i,j $ ，用于 $ u $ 在 item $ j $ 上的隐式偏好使得我们可以通过 $ c_{i,j} $ 来影响 $ r_{u,i} $ 。

   • 将权重视为全局偏移量，而不是user-specific 的插值系数，可以降低评分缺失的影响，即：用户的偏好不仅取决于他已评分的item，还取决于他未评分的 item 。

     可以理解为 $ w_{i,j} $ 是跨用户全局共享的，它是 item 之间的固有属性，和具体用户无关（即使用户对 item $ j $ 未评分）。

   • 在邻域模型中，因为 $ \hat r_{u,i} $ 是通过对 $ \{(r_{u,j} - b_{u,j})\mid j\in S^k(i;u)\} $ 进行插值得到，所以 $ b_{u,i} $ 和 $ b_{u,j} $ 都是兼容的，即它们都采用： $ b_{u,i} = \mu + b_u +b_i $ 来计算得到。

     我们这里不再使用插值的解释，因此可以解耦 $ b_{u,i} $ 和 $ b_{u,j} $ 的定义。一个更通用的做法是：

     $ \hat r_{u,i} = \tilde b_{u,i} + \sum_{j\in \mathbb I_u} (r_{u,j} - b_{u,j}) w_{i,j} + \sum_{j\in \mathbb N_u} c_{i,j} $

     其中 $ \tilde b_{u,i} $ 为其它方法，如潜在因子模型预估的结果。这里我们仍然选择 $ \tilde b_{u,i} = b_{u,i} = \mu + b_u +b_i $ ，但是我们选择 $ b_{u,j} $ 为常数：它直接根据均值 $ \mu $ 、用户 $ u $ 在已知评分上的偏移量、item $ i $ 在已知评分上的偏移量直接计算得到。即：

     $ \hat r_{u,i} = \mu + b_u +b_i + \sum_{j\in \mathbb I_u} (r_{u,j} - b_{u,j}) w_{i,j} + \sum_{j\in \mathbb N_u} c_{i,j} $

     其中 $ b_u,b_i,w_{i,j},c_{i,j} $ 为参数， $ \mu,r_{u,j},b_{i,j} $ 为常数。

4. 当且方案的一个特点是：对于显式评分很多（即 $ |\mathbb I_u| $ 很大）、或者隐式反馈很多 （即 $ |\mathbb N_u| $ 很大）的用户，预估评分更大。通常这也是推荐系统预期的：

   • 对于更活跃的用户(显式反馈更多或隐式反馈更多)，我们掌握的信息更多，则我们的推荐更激进，我们预估的评分比 baseline 有一个很大的偏差。

   • 对于不活跃的用户（显式反馈更多或隐式反馈更少），我们掌握的信息非常少，则我们的推荐更保守，这种情况下我们希望保持接近 baseline 的安全估计。

     但是我们的经验表明，模型在某种程度上过分强调了活跃用户和不活跃用户。因此我们通过调整预测模型，从而缓解这个现象：

     $ \hat r_{u,i} = b_{u,i} +\frac{\sum_{j\in \mathbb I_u}(r_{u,j} - b_{u,j})w_{i,j}}{\sqrt{|\mathbb I_u|}} +\frac{\sum_{j\in \mathbb N_u}c_{i,j}}{\sqrt{ |\mathbb N_u|}} $

     进一步的，我们可以通过移除不太相似的 item 从而减少参数来降低模型复杂度。定义 $ \mathcal S^k(i) $ 为和 item $ i $ 最相似的 $ k $ 个 item （通过相似度 $ s_{i,j} $ 来选取） ，定义 $ \mathbb I_u^k(i) = \mathbb I_u\cap \mathcal S^k(i),\mathbb N_u^k(i) = \mathbb N_u\cap \mathcal S^k(i) $ 。我们认为：最具影响力的权重与 item $ i $ 最相关的 item 关联，则有：

     $ \hat r_{u,i} = \mu +b_u+b_i +\frac{\sum_{j\in \mathbb I^k_u(i)}(r_{u,j} - b_{u,j})w_{i,j}}{\sqrt{|\mathbb I^k_u(i)|}} + \frac{\sum_{j\in \mathbb N^k_u(i)}c_{i,j}}{\sqrt{|\mathbb N^k_u(i)|}} $

     当 $ k=\infty $ 时，模型退化到上一个版本。对于一个较小的 $ k $ 值，它可以显著降低参数数量。

5. 新的邻域模型的一个主要设计目标是促进有效的全局优化过程，这是旧模型所欠缺的。我们最小化损失函数：

   $ \min_{\mathbf b,\mathbf w,\mathbf c} \sum_{(u,i)\in \mathcal K}\left(r_{u,i} - \hat r_{u,i}\right)^2 + \lambda_4\left(\sum_{u\in \mathbb U}b_u^2 +\sum_{i\in \mathbb I} b_i^2 + \sum_{i ,j\in \mathbb I}w_{i,j}^2 + \sum_{i ,j\in \mathbb I}c_{i,j}^2\right) $

   该问题是一个凸优化问题，可以通过最小二乘求解器来求解。但是，我们发现基于梯度下降的方法来求解时，求解速度更快。

   令 $ e_{u,i} $ 为预估的误差 $ e_{u,i} = r_{u,i} - \hat r_{u,i} $ ，对于 $ \mathcal K $ 中的每个评分 $ r_{u,i} $ ，我们更新参数为：

   $ b_u\leftarrow b_u + \gamma(e_{u,i} - \lambda_4b_u)\\ b_i\leftarrow b_i + \gamma(e_{u,i} - \lambda_4b_i)\\ \forall j\in \mathbb I^k_u(i): w_{i,j}\leftarrow w_{i,j} + \gamma\left(|\mathbb I^k_u(i)|^{-1/2}e_{u,i}(r_{u,j} - b_{u,j}) - \lambda_4 w_{i,j}\right)\\ \forall j\in \mathbb N^k_u(i): c_{i,j}\leftarrow c_{i,j} + \gamma\left(|\mathbb N^k_u(i)|^{-1/2}e_{u,i} - \lambda_4 c_{i,j}\right) $

   其中：

   • 超参数 $ \gamma $ 为学习率、 $ \lambda_4 $ 为正则化系数，他们都是通过交叉验证得到的超参数。在 Netflix 数据集中我们使用 $ \gamma = 0.005, \lambda_4 = 0.002 $ 。
   • 超参数 $ k $ 控制邻域大小。经验表明：增加 $ k $ 总是有助于提高测试集结果的准确性。因此， $ k $ 的选择反应了模型准确性和计算成本之间的折衷。

6. 我们在 Netflix 数据集上对新的邻域模型进行评估，评估结果如下图所示。我们将它和前面提到的两个邻域模型进行对比：

   • 首先是最基础、应用最广泛的邻域模型： $ \hat r_{u,i} = b_{u,i} + \sum_{j\in \mathcal S^k(i;u)}w_{i,j}^u (r_{u,j} - b_{u,j}) $ ，我们称之为 CorNgbr 。在图中用绿色直线表示。
   • 然后是基于插值权重的邻域模型： $ \hat r_{u,i} = b_{u,i} + \sum_{j\in \mathcal S^k(i;u)} \theta_{i,j}^u(r_{u,j} - b_{u,j}) $ ，我们称之为 WgtNgbr。在图中用青色直线表示。

   对这两个模型我们尝试选择最佳的参数和邻域大小，对于 CorNgbr 最佳邻域大小为 20，对于 WgtNgbr 最佳邻域大小为 50 ，注意：CorNgbr 、WgtNgbr 的邻域和这里的 $ k $ 值无关，因为它们是不同的邻域概念，因此二者的曲线都是直线。

   我们新邻域模型用粉色曲线表示，它给出了不同 $ k $ 值下的效果。黄色曲线为新邻域模型但是不使用隐式反馈数据的情况。结论：

   • 随着 $ k $ 的增加，模型准确性会单调增加。注意：Netflix 仅包含 17770 部电影，因此 $ k=\infty $ 等价于 $ k=17770 $ 。
   • 当没有隐式反馈数据时，模型的准确性会显著下降，并且这种降幅随着 $ k $ 的增加而增加。这证明了隐式反馈数据的价值。

   

   新模型的预处理时间如下所示，可以看到预处理时间随着 $ k $ 的增加而增加。

   注意：预处理需要计算常数 $ \mu $ 、 $ b_{u,j} $ ，以及每个 item 的邻域 $ \mathcal S^k(i) $ 。

   

9.1.3 新的潜在因子模型

a. Asymmetric-SVD

1. 基础的 SVD 模型为：

   $ \hat r_{u,i} = b_{u,i} + \mathbf{\vec p}_u^\top \mathbf{\vec q}_i $

   我们希望通过考虑隐式信息来扩展该模型，我们认为每个 item $ i $ 关联三个因子向量： $ \mathbf{\vec q}_i,\mathbf{\vec x}_i,\mathbf{\vec y}_i\in \mathbb R^f $ ，其中用户 $ u $ 的表达通过该用户显式反馈的 item 因子向量 $ \mathbf{\vec x}_i $ 和隐式反馈的 item 因子向量 $ \mathbf{\vec y}_j $ 来表示，即：

   $ \mathbf{\vec p}_u = \left(|\mathbb I_u|^{-1/2}\sum_{j\in \mathbb I_u}(r_{u,j} - b_{u,j})\mathbf{\vec x}_j + |\mathbb N_u|^{-1/2} \sum_{j\in \mathbb N_u}\mathbf{\vec y}_j\right) $

   因此模型调整为：

   $ \hat r_{u,i} = b_{u,i} + \mathbf{\vec q}_i^\top \left(|\mathbb I_u|^{-1/2}\sum_{j\in \mathbb I_u}(r_{u,j} - b_{u,j})\mathbf{\vec x}_j + |\mathbb N_u|^{-1/2} \sum_{j\in \mathbb N_u}\mathbf{\vec y}_j\right) $

   这个新模型我们命名为非对称SVD （Asymmetric-SVD），它具有以下优点：

   • 模型参数更少：通常用户数量远大于 item 数量，因此用 item 参数代替 user 参数可以显著降低模型复杂度。

   • 新用户友好：由于非对称SVD 不存在用户因子向量，因此我们可以在新用户产生行为之后立即处理，无需重新训练模型并得到新用户的因子向量。

     同样地，我们也可以利用老用户产生的最新行为来即使更新老用户的 representation 。

     注意：我们必须学习新item 的参数。这符合我们的预期：通常系统需要向新用户提供实时的推荐，而对于新item 则允许等待一段时间来才被处理。另外，ItemBased CF 也表现出同样的、user 和 item 之间的不对称性。

   • 可解释性：用户期待推荐系统给出推荐的理由，而不是一个黑箱推荐。这不仅丰富了用户体验，还鼓励用户和系统进行交互，从而获得更多的有效反馈并提高长期预测准确性。

     诸如 SVD 之类的潜在因子模型在可解释性上面临困难，因为这些模型通过用户因子向量这个中间结果来抽象用户，该中间结果和用户历史行为分离，使得无法得到可解释性。

     非对称SVD 并没有对用户使用任何抽象，而是直接使用用户过去的行为信息，因此我们可以通过最相关的行为来解释预测结果。这一点和 ItemBased CF 相同。

   • 集成隐式反馈数据：通过集成隐式反馈数据，非对称SVD 可以进一步提高预测准确性。

     对于隐式反馈数据很多、显式反馈数据很少的用户来讲，隐式反馈数据非常重要。

2. 非对称SVD 的最小化损失函数：

   $ \min_{\mathbf Q,\mathbf X,\mathbf Y,\mathbf b} \sum_{(u,i)\in \mathcal K}\left(r_{u,i} - \hat r_{u,i} \right)^2 + \lambda_5\left(\sum_{u\in \mathbb U} b_u^2+\sum_{i\in \mathbb I}b_i^2 + \sum_{i\in \mathbb I}||\mathbf{\vec q}_i||^2 + \sum_{j\in \mathbb I}||\mathbf{\vec x}_j||^2 + \sum_{j\in \mathbb I}||\mathbf{\vec y}_j||^2\right) $

   其中超参数 $ \lambda_5 $ 为正则化系数。

   我们通过随机梯度下降来求解该最优化问题，在 Netflix 数据集上我们使用学习率 $ \gamma = 0.002 $ ，正则化系数 $ \lambda_5 = 0.04 $ 。

3. 由于我们使用 item 的因子向量来代替用户因子向量，因此会损失一些预测准确性。问题是，非对称SVD 带来的好处是否值得我们放弃一些预测准确性？ 我们在 Netflix 数据集上对此进行评估，评估指标为 RMSE 。可以看到：非对称SVD 的效果实际上略好于 SVD 。一个可能的原因是：非对称 SVD 考虑了隐式反馈。这意味着我们可以在不牺牲预测准确性的条件下享受非对称 SVD 提供的好处。

   如前所述，我们在 Netlifx 数据集上实际上并没有太多的独立的隐式反馈数据，因此我们预期在具有更多隐式反馈数据集上，非对称 SVD 模型能带来进一步的改善。

   

b. SVD++

1. 如果仅仅融合隐式反馈数据，则我们可以得到更准确的结果。我们认为每个 item $ i $ 关联两个因子向量： $ \mathbf{\vec q}_i, \mathbf{\vec y}_i\in \mathbb R^f $ ，每个用户 $ u $ 关联一个因子向量 $ \mathbf{\vec p}_u $ 。最终用户 $ u $ 通过 $ \mathbf{\vec p}_u + |\mathbb N_u|^{-1/2}\sum_{j\in \mathbb N_u}\mathbf{\vec y}_j $ 来建模。因此SVD 模型调整为：

   $ \hat r_{u,i} = b_{u,i} + \mathbf{\vec q}_i^\top \left(\mathbf{\vec p}_u + |\mathbb N_u|^{-1/2}\sum_{j\in \mathbb N_u}\mathbf{\vec y}_j\right) $

   我们称这个模型为 SVD++ ，其中参数可以通过梯度下降来最小化损失函数得到。

2. SVD++ 没有非对称SVD 涉及的诸多好处，这是因为 SVD++ 采用了用户因子向量来抽象每个用户。但是上表可以看到，就预测准确性而言 SVD++ 显然更具有优势。

9.1.4 整合模型

1. 潜在因子模型和邻域模型可以很好的互补，这里我们将邻域模型和 SVD++ 模型整合在一起，最终得到模型：

   $ \hat r_{u,i} = \mu + b_u+b_i +\mathbf{\vec q}_i^\top \left(\mathbf{\vec p}_u + |\mathbb N_u|^{-1/2}\sum_{j\in \mathbb N_u}\mathbf{\vec y}_j\right)\\ + |\mathbb I^k_u(i)|^{-1/2}\sum_{j\in \mathbb I^k_u(i)}(r_{u,j} - b_{u,j})w_{i,j}+|\mathbb N^k_u(i)|^{-1/2}\sum_{j\in \mathbb N^k_u(i)}c_{i,j} $

   从某种意义上讲，该公式提供了三层模型：

   • 第一层： $ \mu + b_u + b_i $ 描述了 item 和 user 的一般属性，未涉及任何 user-item 交互行为。

     例如：这一层可能认为电影 “《指环王三》” 是高评分的、用户 “张三” 倾向于打低分。

   • 第二层： $ \mathbf{\vec q}_i^\top \left(\mathbf{\vec p}_u + |\mathbb I_u|^{-1/2}\sum_{j\in \mathbb I_u}\mathbf{\vec y}_j\right) $ 提供了用户和 item 之间的交互。

     例如：根据 “张三” 偏好 “西幻” 主题的电影，我们可以预测 “张三” 对 “《指环王三》” 的评分会很高。

   • 第三层：邻域评分有助于进一步的精细化调整。

     例如：虽然 ”张三“ 偏好 ”西幻“ 主题的电影， 但是他对 ”《指环王一》、《指环王二》“ 的评分都很低， 那么我们预计他对 ”《指环王三》“ 的评分也会比较低。

2. 我们可以随机梯度下降来最小化损失函数来求解模型的参数。定义 $ e_{u,i} = r_{u,i} - \hat r_{u,i} $ ，对于 $ r_{u,i}\in \mathcal K $ 我们更新参数为：

   $ b_u\leftarrow b_u + \gamma_1(e_{u,i}-\lambda_6 b_u)\\ b_i\leftarrow b_i + \gamma_1(e_{u,i}-\lambda_6 b_i)\\ \mathbf{\vec q}_i\leftarrow \mathbf{\vec q}_i + \gamma_2\left(e_{u,i}\left(\mathbf{\vec p}_u+|\mathbb N_u|^{-1/2}\sum_{j\in \mathbb N_u}\mathbf{\vec y}_j\right) - \lambda_7 \mathbf{\vec q}_i\right)\\ \mathbf{\vec p}_u\leftarrow \mathbf{\vec p}_u + \gamma_2\left(e_{u,i}\mathbf{\vec q}_i-\lambda_7\mathbf{\vec p}_u\right)\\ \forall j\in N(u): \mathbf{\vec y}_j \leftarrow \mathbf{\vec y}_j + \gamma_2\left(e_{u,i}|\mathbb N_u|^{-1/2} \mathbf{\vec q}_i - \lambda_7\mathbf{\vec y}_j\right)\\ \forall j\in \mathbb I^k_u(i): w_{w,j}\leftarrow w_{i,j}+ \gamma_3\left(|\mathbb I^k_u(i)|^{-1/2}e_{u,i}(r_{u,j}-b_{u,j})-\lambda_8 w_{i,j}\right)\\ \forall j\in\mathbb N^k_u(i):c_{i,j} \leftarrow c_{i,j} + \gamma_3\left(|\mathbb N^k_u(i)|^{-1/2} e_{u,i} - \lambda_8 c_{i,j}\right) $

   其中 $ \lambda_6,\lambda_7,\lambda_8 $ 为正则化系数、 $ \gamma_1,\gamma_2,\gamma_3 $ 为学习率。我们对不同的部分采用不同的正则化系数和不同的学习率。

3. 我们在 Netflix 数据集上评估整合模型，超参数为：

   $ \gamma_1=\gamma_2=0.007,\gamma_3=0.001,\lambda_6=0.005,\lambda_7=\lambda_8 = 0.015 $

   我们使用系数为 0.9 的学习率衰减。

   我们设置邻域 $ k=300 $ 。与单纯的邻域模型不同，这里增加 $ k $ 并没有好处：虽然增加 $ k $ 可以覆盖更多的全局信息，但是这些全局信息已经被 SVD 部分充分捕获了。

   训练过程大约迭代了 30 次就收敛，下表给出了不同因子大小对应的模型性能和训练时间。可以看到：通过将邻域模型和潜在因子模型集合，并从隐式反馈中提取信息，模型效果比前面所有方法的效果都要更好。

   

4. 可以考虑将邻域模型和非对称SVD 模型结合，从而在提升单个模型的准确性的同时仍然得到可解释性等优秀性质，虽然这比邻域模型结合 SVD ++ 的准确性稍低。

9.2 实验

1. 目前为止我们按照常规做法：通过 RMSE 指标来评估模型在 Netflix 数据集上的准确性。事实上，不同模型在 Netflix 测试集上的 RMSE 集中在一个很小的区间。即使是最简单的均值预估：

   $ \hat r_{u,i} = \frac{\sum_{u^\prime\in \mathbb U_i}r_{u^\prime,i}}{|\mathbb U_i|} $

   这种方式给出的是非个性化的热门电影推荐，最终测试RMSE 为 1.053 。相比之下，Netflix Cinematch 模型可以达到 0.9514、我们的模型可以达到 0.8870 。

   一个关键问题是：如果 RMSE 降低 10% ，那么用户体验能提升多少？这对于推荐系统准确性指标的合理性至关重要。我们通过研究降低 RMSE 对推荐结果的影响来阐明该问题。

   推荐系统的一个常见场景是提供 top K 推荐，即系统需要向用户推荐排名 top K 的 item 。我们研究降低 RMSE 对top K 推荐质量的影响。

   在 Netflix 数据集中，除了测试集之外还有一个验证集。我们将验证集中的5 星评分作为用户感兴趣的电影，我们的目标是找到这些 “用户感兴趣” 电影在我们推荐列表中的排名。对于验证集中的每个用户 $ u $ 评分为5 分的电影 $ i $ ，我们额外随机挑选 1000 部电影，然后通过模型预估用户 $ u $ 对这 1001 部电影的评分。我们根据预估评分进行降序排列，然后观察电影 $ i $ 的排名情况。

   • 由于这里的 1000 部电影是随机选取的，因此可能有小部分电影也是用户 $ u $ 真正感兴趣的，但是大部分电影是用户 $ u $ 不感兴趣的。
   • 我们采用 percent rank 而不是绝对rank 来标识电影 $ i $ 的排名，这是为了使得排名和具体的队列长度无关，从而通用性更强。理想情况下电影 $ i $ 的排名为 0% （所有随机电影都在它之后），最坏情况下电影 $ i $ 的排名为 100%（所有随机电影都在它之前）。

2. Netflix 验证集包含 384573 个 $ r_{u,i} = 5 $ 的 user-item 评分，对其中每个 “用户感兴趣” 电影我们随机抽取 1000 个电影然后评估 “用户感兴趣” 电影的排名，最终我们得到了 384573 个percent rank 。然后我们评估这 384573 个排名的分布。

   我们比较了五种不同的策略：

   • 非个性化的均值预估：使用每个电影的评分均值作为预估结果，我们用 MovieAvg 表示。其测试 RMSE 为 1.053 。
   • 基于相关系数的邻域模型：即传统的 ItemBased CF 模型，我们用 CorNgbr 表示。其测试 RMSE 为 0.9406 。
   • 基于插值权重 interpolation weight 的邻域模型：即采用全局插值权重的邻域模型，我们用WgtNgbr 表示。其测试 RMSE 为 0.9107 。
   • SVD 潜在因子模型：使用因子数量为 100 的SVD 模型，我们用 SVD 表示。其测试 RMSE 为 0.9025 。
   • 我们的集成模型：使用因子数量为 100 的集成模型，我们用 integrated 表示。其测试 RMSE 为 0.8870 。

   我们给出了384573 个排名的累积分布（小于等于 rank x 的样本的比例）。可以看到：所有方法都超越了非个性化的均值预估， 并且我们的集成方法效果最好。

   

   事实上当向用户推荐电影时，我们只会推荐top K 个电影而不是所有的候选电影队列。例如，如果从 600 部电影中推荐其中的 3 部，则只有 top 0.5% 的电影才有机会呈现给用户。从某种意义上说，”用户感兴趣“ 电影排在 top 5%、top 20%、top 80% 没有任何区别，因为这些位置都没有机会呈现给用户。因此我们重点关注图中 $ x $ 轴的头部，比如 top 0% 到 top 2% ，这对应了 1000 个候选电影中的top 20 个电影。

   如下图所示，这些方法之间存在显著差异：

   • 我们的集成方法将”用户感兴趣“ 电影排在第一位（即 top 0% ）的概率为 0.067 ，这比 MovieAvg 高出三倍以上、比 CorNgbr 高出 2.8 倍以上，也是 WgtNbr 和 SVD 的 1.5 倍。
   • 我们的集成方法将”用户感兴趣“电影排在 top 0.2% 的概率为 0.157 ，相比之下其它几种方法的概率要小得多：MovieAvg 的概率为 0.050、CorNgbr 的概率为 0.065、WgtNgbr 的概率为 0.107、SVD 的概率为 0.115 。

   实验结果令人振奋和惊讶：RMSE 的微小改进可以带来 top K 推荐质量的显著提升。另外，我们也从未料到流行的基于相关性邻域模型的性能很差，它并未比非个性化的热门推荐提升很多。

   

3. 讨论：在这项工作中，我们提出了对两种最流行的、协同过滤方法的改进：

   • 首先，我们提出了一种新的、基于邻域的模型。该模型和以前的邻域方法不同，它基于跨用户全局共享的全局权重。这会在提高预测准确性的同时保持邻域方法的优点，例如：预测的可解释性、无需重新训练即可处理新用户。
   • 其次，我们引入了对基于 SVD 的潜在因子模型的扩展，通过将隐式反馈集成到模型中来提高准确性。

   此外，新的邻域模型使得我们能够首次推导出一个结合了邻域模型和潜在因子模型的集成模型。这有助于提高系统性能，因为邻域模型和潜在因子模型处理不同 level 的数据并相互补充。

   推荐系统的质量有多个维度来刻画，其中包括：准确性、多样性、惊喜度、可解释性、计算效率等。其中一些指标相对容易衡量，如准确性和计算效率，而另一些指标难以量化。我们提出了一种新的方法来衡量 top K 推荐的效果，这对于大多数推荐系统来说至关重要。值得注意的是，评估 top K 推荐显著加剧了模型之间的差异，这种差异超出了传统的准确性指标上的差异。

   这项工作一个主要见解是：推高推荐质量取决于成功解决数据的不同方面aspect 。一个主要的例子是使用隐式反馈来扩展模型质量。可以集成进来从而提高预测质量的其它数据方面是内容信息，如用户属性或 item 属性，或者评分相关的日期（这可能有助于解释用户偏好的漂移 shift）。