2008-Collaborative Filtering for Implicit Feedback Datasets

论文原文 -> 链接

文章简介

推荐系统的一个常见任务是基于先前的隐式反馈，通过个性化推荐来改善客户体验。这些系统被动地跟踪用户的各种行为，如购买历史、观看习惯和浏览活动，以建立用户偏好模型。与研究更为广泛的显式反馈不同，我们没有用户关于其偏好的任何直接输入。特别是，我们缺乏关于消费者不喜欢哪些产品的实质性证据。
在这篇论文中，我们识别了隐式反馈数据集的独特属性。提出将数据视为与不同置信水平相关的正负偏好指示。这导致了一个特别为隐式反馈推荐系统定制的因子模型。我们还提出了一种可扩展的优化程序，该程序与数据规模呈线性关系。
广义上讲，推荐系统基于两种不同的策略（或其组合）。
- 基于内容的策略为每个用户或产品创建一个画像以表征其本质。例如，电影画像可能包括其类型、参与的演员、票房受欢迎程度等属性。用户画像可能包括人口统计信息或对适当问卷的回答。生成的画像允许程序将用户与匹配的产品关联起来。然而，基于内容的策略需要收集可能不可用或难以收集的外部信息。
- 另一种策略，也是本文的重点，仅依赖于过去的用户行为，而不需要创建显式画像。这种方法被称为协同过滤（CF），CF分析用户之间的关系和产品之间的相互依赖性，以识别新的用户-项目关联。例如，一些CF系统识别倾向于被相似评分的项目对或具有相似评分或购买历史的志同道合的用户，以推断用户和项目之间的未知关系。唯一需要的信息是用户过去的行为，这可能是他们之前的交易或他们对产品的评分方式。CF的主要吸引力在于它是领域无关的，但它可以处理通常难以捉摸且使用基于内容的技巧非常难以建模的数据方面。尽管通常比基于内容的技巧更准确，但CF存在冷启动问题，因为它无法处理系统中的新产品，而基于内容的策略在这种情况下是合适的。
推荐系统依赖于不同类型的输入。最方便的是高质量的显式反馈，其中包括用户关于他们对产品兴趣的明确输入。
- 例如，Netflix收集电影的星级评分，TiVo用户通过按下拇指向上/向下按钮来表示他们对电视节目的偏好。然而，显式反馈并不总是可用的。
- 因此，推荐系统需要从更丰富的隐式反馈中推断用户偏好，这些反馈通过观察用户行为间接反映意见。隐式反馈的类型包括购买历史、浏览历史、搜索模式，甚至鼠标移动。例如，一个用户购买了许多同一作者的书籍，可能喜欢该作者。

本文探索了特别适合处理隐式反馈的相关算法。本文的前提是，我们不会主动从用户那里收集显式反馈，因此系统完全基于隐式反馈——分析匿名用户的观看习惯，识别隐式反馈的独特特征至关重要。以下列出了主要特征：

没有负面反馈。通过观察用户的行为，我们可以推断出他们可能喜欢哪些项目并因此选择消费。然而，很难可靠地推断出用户不喜欢哪些项目。
- 例如，一个用户没有观看某个节目可能是因为她不喜欢该节目，或者只是因为她不知道该节目或没有时间观看。这种基本的不对称性在显式反馈中不存在，因为用户会告诉我们他们喜欢什么和不喜欢什么。
  - 它有几个影响：例如，显式推荐系统倾向于关注收集到的信息——那些我们知道其评分的用户-项目矩阵。因此，剩余的用户-项目关系，通常构成数据的大部分，被视为“缺失数据”并从分析中省略。这在隐式反馈中是不可能的，因为仅关注收集到的反馈将使我们只剩下正面反馈，大大歪曲了完整的用户画像。因此，处理缺失数据至关重要，因为大多数负面反馈预计会在其中找到。
隐式反馈本质上是有噪声的。当我们被动地跟踪用户行为时，我们只能猜测他们的偏好和真实动机。
- 例如，我们可能会查看个人的购买行为，但这并不一定表明对产品的正面看法。该物品可能是作为礼物购买的，或者用户可能对产品感到失望。
- 我们可能会看到电视在特定时间播放特定频道，但观众可能正在睡觉。
显式反馈的数值表示偏好，而隐式反馈的数值表示置信度。基于显式反馈的系统让用户表达他们的偏好程度，例如1到5星的评分（“完全不喜欢”到“非常喜欢”）。另一方面，隐式反馈的数值描述了行为的频率，例如用户观看某个节目的时长、用户购买某个项目的频率等。
- 较大的数值并不表示更高的偏好。例如，用户最爱的节目可能是一部电影，用户只会观看一次，而有一部系列剧用户相当喜欢，因此每周都在观看。
- 然而，反馈的数值肯定是有用的，因为它告诉我们对某个观察的置信度。一次性事件可能由与用户偏好无关的各种原因引起。然而，重复事件更可能反映用户的意见。
隐式反馈推荐系统的评估需要适当的度量手段。在传统的设置中，用户指定一个数值评分，有明确的指标如均方误差来衡量预测的成功。然而，在隐式模型中，我们必须考虑项目的可用性、与其他项目的竞争以及重复反馈。
- 例如，如果我们收集电视观看数据，不清楚如何评估一个被多次观看的节目，或如何比较两个同时播放的节目，因此用户无法同时观看。

我们为区分用户和项目保留了特殊的索引字母：对于用户 $u, v$ ，以及项目 $i, j$ 。输入数据通过 $r_{ui}$ 值将用户和项目关联起来，我们将其称为观测值。

对于显式反馈数据集，这些值将是评分，表示用户 $u$ 对项目 $i$ 的偏好，其中高值意味着更强的偏好。
对于隐式反馈数据集，这些值将表示用户行为的观测结果。例如， $r_{ui}$ $r_{u i}$ 可以表示用户 $u$ $u$ 购买项目 $i$ $i$ 的次数或用户 $u$ $u$ 在网页 $i$ $i$ 上花费的时间。
- 在电视推荐案例中， $r_{ui}$ 表示用户 $u$ 完整观看节目 $i$ 的次数。例如， $r_{ui} = 0.7$ 表示用户 $u$ 观看了节目 $i$ 的 70%，而对于一个观看了节目两次的用户，我们将设置 $r_{ui} = 2$ 。

显式评分对于绝大多数用户-项目对来说通常是未知的，因此适用的算法处理相对较少的已知评分，同时忽略缺失的评分。然而，对于隐式反馈，自然会为所有 $r_{ui}$ 变量赋值。如果没有观测到任何行为， $r_{ui}$ 被设置为零，因此在我们的例子中意味着零观看时间，或零购买记录。

文献综述

邻域模型

CF 最常见的方法是基于邻域模型。其原始形式，几乎所有早期的 CF 系统都采用了这种方法，是面向User的；参见以获得良好的分析。这种面向用户的方法基于志同道合用户的记录评分来估计未知的评分。后来，一种类似的面向Item的方法变得流行起来。在这些方法中，评分是使用同一用户对相似Item的已知评分来估计的。更好的可扩展性和改进的准确性使得面向Item的方法在许多情况下更受欢迎。此外，面向Item的方法更容易解释预测背后的推理。这是因为用户熟悉他们之前偏好的Item，但通常不认识那些所谓的志同道合的用户。

大多数面向Item的方法的核心是Item之间的相似性度量，其中 $s_{ij}$ 表示Item $i$ 和 $j$ 之间的相似性。通常，它是基于皮尔逊相关系数。我们的目标是预测 $r_{ui}$ ，用户 $u$ 对Item $i$ 的未观测值。使用相似性度量，我们识别出 $u$ 评分的与 $i$ 最相似的 $k$ 个Item。这组 $k$ 个邻居用 $S_k(i; u)$ 表示。 $r_{ui}$ 的预测值被视为相邻Item评分的加权平均值：

\hat{r}_{ui} = \frac{\sum_{j \in S_k(i; u)} s_{ij} r_{uj}}{\sum_{j \in S_k(i; u)} s_{ij}}

这种方案的一些增强方法在显式反馈中得到了很好的实践，例如纠正由不同用户和Item的平均评分变化引起的偏差。

这些修改对于隐式反馈数据集的相关性较低，因为我们使用的不是所有评分都在同一尺度上的评分，而是同一用户消费Item的频率。不同用户的频率可能根据应用程序的不同而有非常不同的尺度，并且如何计算相似性不太清楚。

所有面向Item的模型在隐式反馈方面都有一个缺点——它们没有提供区分用户偏好和我们可能对这些偏好的信心。

潜在因子模型

潜在因子模型是协同过滤的另一种方法，其更全面的目标是揭示解释观测评分的潜在特征；例如，包括 pLSA、神经网络和潜在狄利克雷分配。我们将重点关注通过用户-Item观测矩阵的奇异值分解（SVD）诱导的模型。最近，SVD 模型因其吸引人的准确性和可扩展性而变得流行；参见例如。一个典型的模型将每个用户 $u$ 与一个用户因子向量 $x_u \in \mathbb{R}^f$ 关联，并将每个Item $i$ 与一个Item因子向量 $y_i \in \mathbb{R}^f$ 关联。预测是通过内积完成的，即 $\hat{r}_{ui} = x_u^T y_i$ 。

更复杂的部分是参数估计。许多最近的工作，应用于显式反馈数据集，建议仅对观测到的评分进行建模，并通过适当的正则化模型避免过拟合，例如：

\min_{x_*, y_*} \sum_{r_{u,i} \text{ is known}} (r_{ui} - x_u^T y_i)^2 + \lambda (\| x_u \|^2 + \| y_i \|^2)

这里， $\lambda$ 用于正则化模型。参数通常通过随机梯度下降来学习。在最大的可用数据集——Netflix 数据集上，结果往往一致优于邻域模型所取得的结果。在这项工作中，我们借鉴这种方法应用于隐式反馈数据集，这需要在模型公式和优化技术上进行修改。

核心

首先，需要形式化置信度的概念，这是 $r_{ui}$ 变量所测量的。为此，让我们引入一组二进制变量 $p_{ui}$ ，它表示用户 $u$ 对 $i$ 的偏好。 $p_{ui}$ 值是通过对 $r_{ui}$ 值进行二值化得到的：

p_{ui} = \begin{cases} 1 & \text{如果 } r_{ui} > 0 \\ 0 & \text{如果 } r_{ui} = 0 \end{cases}

换句话说，如果用户 $u$ 消费了 $i$ （ $r_{ui} > 0$ ），那么我们有 $u$ 喜欢 $i$ （ $p_{ui} = 1$ ）的指示。另一方面，如果 $u$ 从未消费过 $i$ ，我们认为没有偏好（ $p_{ui} = 0$ ）。然而，我们的置信度与极大不同的置信水平相关联「However, our beliefs are associated with greatly varying confidence levels」。

首先，根据数据性质， $p_{ui}$ 的零值与低置信度相关联，因为对不采取任何正向行动可能源于许多其他原因，而不仅仅是不喜欢它。
- 例如，用户可能不知道存在，或者由于价格或有限可用性而无法消费。
此外，消费也可能是由于偏好以外的因素。
- 例如，用户可能因为停留在之前观看的节目频道而观看电视节目。或者消费者可能购买一个作为礼物送给别人，尽管他自己不喜欢这个。
因此，我们对于用户表示偏好的也会有不同的置信水平。一般来说，随着 $r_{ui}$ 的增长，我们有更强的指示表明用户确实喜欢该Item。因此，我们引入一组变量 $c_{ui}$ ，它测量我们对观测 $p_{ui}$ 的置信度。一个合理的选择是：

c_{ui} = 1 + \alpha r_{ui}

这样，我们对每个用户-Item 对都有一些最小的置信度，但随着我们观察到更多正面偏好的证据，我们对 $p_{ui} = 1$ 的置信度相应增加。增加率由常数 $\alpha$ 控制。在我们的实验中，设置 $\alpha = 40$ 被发现能产生良好的结果。

我们的目标是找到每个用户 $u$ 的向量 $x_u \in \mathbb{R}^f$ ，以及每个 $i$ 的向量 $y_i \in \mathbb{R}^f$ ，这些向量将用户偏好分解。换句话说，偏好被假设为内积： $p_{ui} = x_u^T y_i$ 。这些向量分别被称为用户因子和因子。本质上，这些向量努力将用户和映射到一个共同的潜在因子空间，在那里它们可以直接比较。这与显式反馈数据流行的矩阵分解技术类似，有两个重要的区别：

（1）我们需要考虑不同的置信水平，

（2）优化应考虑所有可能的 $u, i$ 对，而不仅仅是那些对应于观测数据的。因此，因子通过最小化以下成本函数来计算：

\min_{x_*, y_*} \sum_{u,i} c_{ui} (p_{ui} - x_u^T y_i)^2 + \lambda \left( \sum_u \| x_u \|^2 + \sum_i \| y_i \|^2 \right)

$\lambda \left( \sum_u \| x_u \|^2 + \sum_i \| y_i \|^2 \right)$ 项对于正则化模型是必要的，以防止其过拟合训练数据。参数 $\lambda$ 的确切值取决于数据，并通过交叉验证确定。

注意，成本函数包含 $m \cdot n$ 项，其中 $m$ 是用户数量， $n$ 是数量。对于典型的数据集， $m \cdot n$ 很容易达到数十亿。这个庞大的项数阻止了大多数直接优化技术，如随机梯度下降，这些技术广泛用于显式反馈数据集。因此，我们建议一种替代的高效优化过程，如下所示。

观察到当用户因子或因子固定时，成本函数变为二次型，因此其全局最小值可以很容易地计算出来。这导致了一个交替最小二乘优化过程，我们在重新计算用户因子和因子之间交替进行，并且每一步都保证降低成本函数的值。交替最小二乘法用于显式反馈数据集，其中未知值被视为缺失，导致稀疏目标函数。隐式反馈设置需要不同的策略来克服密集成本函数并整合置信水平。我们通过利用变量的结构来解决这些问题，使得这个过程可以实现高度可扩展。

第一步是重新计算所有用户因子。假设所有因子都收集在一个 $n \times f$ 矩阵 $Y$ 中。在遍历所有用户之前，我们在时间 $O(f^2n)$ 内计算 $f \times f$ 矩阵 $Y^T Y$ 。对于每个用户 $u$ ，我们定义对角 $n \times n$ 矩阵 $C_u$ ，其中 $C_u^{ii} = c_{ui}$ ，以及包含 $u$ 所有偏好的向量 $p^{(u)} \in \mathbb{R}^n$ （ $p_{ui}$ 值）。通过微分，我们找到最小化成本函数的 $x_u$ 的解析表达式：

x_u = (Y^T C_u Y + \lambda I)^{-1} Y^T C_u p^{(u)}

这里的计算瓶颈是计算 $Y^T C_u Y$ ，其朴素计算将需要时间 $O(f^2n)$ （对于每个 $m$ 个用户）。通过使用 $Y^T C_u Y = Y^T Y + Y^T (C_u - I) Y$ 的事实，可以显著加速。现在， $Y^T Y$ 独立于 $u$ 并且已经预先计算。至于 $Y^T (C_u - I) Y$ ，注意到 $C_u - I$ 只有 $n_u$ 个非零元素，其中 $n_u$ 是 $r_{ui} > 0$ 的的数量，通常 $n_u \ll n$ 。类似地， $C_u p^{(u)}$ 只包含 $n_u$ 个非零元素。因此，重新计算 $x_u$ 的时间为 $O(f^2 n_u + f^3)$ 。这里，我们假设矩阵求逆 $(Y^T C_u Y + \lambda I)^{-1}$ 的时间为 $O(f^3)$ ，尽管存在更高效的算法，但对于通常较小的 $f$ 值可能不太相关。这一步在每个 $m$ 个用户上执行，因此总运行时间为 $O(f^2 N + f^3 m)$ ，其中 $N$ 是非零观测的总数，即 $N = \sum_u n_u$ 。重要的是，运行时间与输入大小成线性关系。典型的 $f$ 值在 20 到 200 之间。

重新计算用户因子后，我们以并行方式重新计算所有因子。我们将所有用户因子排列在一个 $m \times f$ 矩阵 $X$ 中。首先在时间 $O(f^2 m)$ 内计算 $f \times f$ 矩阵 $X^T X$ 。对于每个 $i$ ，我们定义对角 $m \times m$ 矩阵 $C_i$ ，其中 $C_i^{uu} = c_{ui}$ ，以及包含 $i$ 所有偏好的向量 $p^{(i)} \in \mathbb{R}^m$ 。然后我们求解：

y_i = (X^T C_i X + \lambda I)^{-1} X^T C_i p^{(i)}

使用与用户因子相同的技术，这一步的运行时间为 $O(f^2 N + f^3 n)$ 。我们执行几次用户因子和因子的配对重新计算，直到它们稳定。比如，扫描次数为 10 次。

整个过程与数据的大小成线性比例。在计算了用户因子和项目因子之后，我们向用户 $u$ 推荐 $K$ 个可用项目中具有最大值 $\hat{p}_{ui} = x_u^T y_i$ 的项目，其中 $\hat{p}_{ui}$ 表示用户 $u$ 对项目 $i$ 的预测偏好。

现在，我们的技术基本描述已经完成，我们希望进一步讨论它，因为我们的某些决策可以修改。例如，可以从 $r_{ui}$ 以不同方式导出 $p_{ui}$ ，通过在 $r_{ui}$ 上设置最小阈值，使得相应的 $p_{ui}$ 不为零。类似地，有许多方法可以将 $r_{ui}$ 转换为置信水平 $c_{ui}$ 。我们发现也有效的一种替代方法是设置：

c_{ui} = 1 + \alpha \log(1 + r_{ui}/\epsilon)

无论方案的具体变体如何，重要的是要认识到其主要属性，这些属性解决了隐式反馈的独特特征：

将原始观测值（ $r_{ui}$ ）转换为两个具有不同解释的独立量：偏好（ $p_{ui}$ ）和置信水平（ $c_{ui}$ ）。这更好地反映了数据的性质，并且对于提高预测准确性至关重要，如实验研究（第 6 节）所示。
通过利用变量的代数结构，以线性运行时间处理所有可能的（ $n \cdot m$ ）用户-Item组合的算法。

如何解释该算法？

基于邻域（或“基于记忆”）技术的解释是直接的，因为推荐是直接从过去用户的行为中推断出来的。然而，对于潜在因子模型，解释变得更具挑战性，因为所有过去用户的行为都通过用户因子抽象化，从而阻断了过去用户行为与输出推荐之间的直接关系。
有趣的是，我们的交替最小二乘模型提供了一种计算解释的新方法。替换用户因子： $x_u = (Y^T C_u Y + \lambda I)^{-1} Y^T C_u p(u)$ 。因此，用户 $u$ 对项目 $i$ 的预测偏好 $\hat{p}_{ui} = y_i^T x_u$ 变为： $y_i^T (Y^T C_u Y + \lambda I)^{-1} Y^T C_u p(u)$ 。通过引入一些新符号，可以简化这个表达式。让我们将 $f \times f$ 矩阵 $(Y^T C_u Y + \lambda I)^{-1}$ 表示为 $W_u$ ，这应该被视为与用户 $u$ 相关的权重矩阵。因此，从 $u$ 的角度来看，项目 $i$ 和 $j$ 之间的加权相似性表示为 $s_{ij}^u = y_i^T W_u y_j$ 。使用这种新符号，用户 $u$ 对项目 $i$ 的预测偏好可以重写为：

\hat{p}_{ui} = \sum_{j: r_{uj} > 0} s_{ij}^u c_{uj}

这使得我们的潜在因子模型简化为一个线性模型，该模型将偏好预测为过去行为（ $r_{uj} > 0$ ）的线性函数，由Item-Item相似性加权。每个过去的行为在形成预测的 $\hat{p}_{ui}$ 时都有一个单独的项，因此我们可以隔离其独特的贡献。与最高贡献相关的行为被识别为推荐背后的主要解释。此外，我们可以进一步将每个过去行为的贡献分解为两个独立的来源：与用户 $u$ 的关系的重要性 $c_{uj}$ ，以及与目标项目 $i$ 的相似性 $s_{ij}^u$ 。

这很大程度上类似于面向Item的邻域模型，从而实现了解释计算预测的期望能力。如果我们进一步采用这种观点，我们可以将我们的模型视为基于邻域方法的强大预处理器，其中项目相似性通过有原则的优化过程学习。此外，项目之间的相似性变得依赖于特定的用户，反映了不同用户不完全同意哪些项目相似的事实。

代码

看Github，说这算是「交替最小二乘法」，Github地址：https://github.com/benfred/implicit

没有找到论文中的数据源，所以依然使用MovieLen代替

数据

"""
2008-Collaborative Filtering for Implicit Feedback Datasets
Code Reproduction
"""

import os
import sys

sys.path.append(os.path.join(os.path.dirname(__file__), ".."))

import copy
import numpy as np
import pandas as pd
from tqdm import tqdm
from util import sprint

data_path = "../DATASETS/MovieLens100K/u.data"
raw = pd.read_csv(
    data_path,
    sep="\t",
    header=None,
    names=["user_id", "item_id", "rating", "timestamp"],
)
sprint(raw.head(), raw.shape)

# Create a user-item matrix
n_users = raw.user_id.unique().shape[0]
n_items = raw.item_id.unique().shape[0]
sprint("Number of users =", n_users, "; Number of items =", n_items)

data = copy.deepcopy(raw)
data = data.sort_values(by=["user_id", "item_id"])

ratings = np.zeros((n_users, n_items))
for row in raw.itertuples():
    ratings[row[1] - 1, row[2] - 1] = row[3]
sprint(ratings, ratings.shape)

latent_factors = 5
# random init user and item matrix
X = np.random.rand(n_users, latent_factors)
Y = np.random.rand(n_items, latent_factors)

aplha = 40
c_ui = 1 + aplha * ratings
lambda_reg = 0.1

max_iterations = 20

for iteration in range(max_iterations):
    # optimize X
    for u in range(n_users):
        A = np.dot((c_ui[u, :].reshape(-1, 1) * Y).T, Y) + lambda_reg * np.eye(latent_factors)
        b = np.dot((c_ui[u, :] * ratings[u, :]).reshape(1, -1), Y).flatten()
        X[u, :] = np.linalg.solve(A, b)
        
    # optimize Y
    for i in range(n_items):
        A = np.dot((c_ui[:, i].reshape(-1, 1) * X).T, X) + lambda_reg * np.eye(latent_factors)
        b = np.dot((c_ui[:, i] * ratings[:, i]).reshape(1, -1), X).flatten()
        Y[i, :] = np.linalg.solve(A, b)
    
    # calculate current loss
    predictions = np.dot(X, Y.T)
    weighted_squared_error = np.sum(c_ui * (ratings - predictions) ** 2)
    regularization = lambda_reg * (np.sum(X ** 2) + np.sum(Y ** 2))
    loss = weighted_squared_error + regularization
    print(f"Iteration {iteration+1}, Loss: {loss}")

# select user 0 and item 30
print(f"Actual p_{0,3}: {ratings[0, 30]}")
print(f"Predicted p_{0,3}: {np.dot(X[0, :], Y[30, :])}")

2008 - Collaborative Filtering for Implicit Feedback Datasets