一、Implicit Feedback CF [2008]

《Collaborative Filtering for Implicit Feedback Datasets》

1. 随着电商越来越受欢迎，一个重要的挑战是帮助用户对提供的各种产品（product）进行分类，从而轻松地找到用户喜欢的产品。解决这一挑战的工具之一是推荐系统。最近推荐系统吸引了很多关注。推荐系统为用户提供个性化的产品或服务推荐，希望满足用户独特的品味和需求。这些系统背后的技术基于分析（profiling）用户和产品，并找到如何将用户和产品进行关联。从广义上讲，推荐系统基于两种不同的策略（或者这两种策略的组合）：

   • content-based 方法：content-based 方法为每个用户或每个产品创建一个画像来刻画其特性 （nature）。例如，电影画像可以包含电影类型、演员、票房排行等属性；用户画像可以包含人口统计信息等。

     我们可以通过用户画像和item 画像进行匹配从而执行基于内容的推荐。然而，基于内容的策略需要收集一些外部信息（这些外部信息用于构建画像），这些外部信息可能难以获取或者根本无法获取。

   • CF-based 方法：协同过滤（ Collaborative Filtering: CF ）方法仅依赖于用户历史行为，而无需创建显式的画像。协同过滤这一术语是由第一个推荐系统 Tapestry 创造的。

     协同过滤分析用户之间的关系和产品之间的相互依赖性，从而识别新的 user-item 关联。例如，一些 CF 系统识别倾向于评分相似的 item pair 、或者具有相似评分/相似购买历史的志趣相投的用户，从而推断 user-item 之间的未知关系。唯一需要的信息是用户历史行为，这可能是用户历史的交易、或者历史评分。

     CF-based 方法的一个主要吸引力在于它是无领域（domain free）的，但是可以解决数据中通常难以捕获、且很难分析的数据面（data aspect）。虽然CF-based 方法通常比 content-based 方法更准确，但是它会遇到冷启动问题（ cold start problem），因为 CF-based 方法无法解决系统中的新产品（而 content-based 方法可以处理新产品）。

   推荐系统依赖于不同类型的输入。

   • 最方便的是高质量的显式反馈（explicit feedback），其中包括用户对产品兴趣的显式输入。例如，Netflix 收集电影的星级评分，TiVo 用户通过点击 thumbs-up/down 按钮来表明用户对电视节目的偏好。然而，显式反馈并不总是可用的。

   • 数量最多的是隐式反馈（implicit feedback ）数据，这些隐式反馈数据包括：用户的购买历史、浏览历史、搜索历史、甚至鼠标移动历史等等。推荐器（recommender）可以从丰富的隐式反馈中推断用户偏好，通过观察用户行为间接地反映用户的意见（opinion）。例如，购买了同一作者的多本书的用户可能喜欢该作者。

   推荐领域的绝大多数文献都专注于处理显式反馈，可能是因为使用这种纯净信息（pure information）的便利性。然而，在许多实际情况下，推荐系统更多的需要处理隐式反馈数据，因为可能用户不愿意显式给出评分、或者系统的局限性导致无法收集显式的反馈。在隐式模型中，一旦用户同意系统收集并使用隐式数据，用户就不需要额外的显式反馈（如评分）。

   论文 《Collaborative Filtering for Implicit Feedback Datasets》 对处理隐式反馈的算法进行了探索。这些探索反映了作者构建电视节目推荐引擎时取得的一些主要经验教训和发展。该推荐场景的setup 阻止作者主动收集用户的显式反馈，因此该系统完全基于隐式反馈 -- 分析匿名用户的观看习惯。

   识别隐式反馈的 unique 特性至关重要，因为这些特性阻止了直接应用显式反馈算法。下面给出了隐式反馈数据的主要特点：

   • 没有负反馈：通过观察用户的行为我们可以推断出用户可能会喜欢的 item，但是难以推断出用户不喜欢的 item 。例如：没有观看某个节目的用户之所以未观看该节目，可能是因为用户不喜欢这个节目、也可能是用户不知道有这个节目的存在、或者在同一时刻存在用户更喜欢的节目导致用户无法同时观看两个节目。在显式反馈中用户可以直接告诉我们：他们喜欢和不喜欢的 item 。因此，这种基本的不对称性（即只知喜欢、不知不喜欢）在显式反馈中不存在。

     这有一些含义。例如，显式推荐器倾向于关注收集到的信息（观察到的已评分的那些 user-item pair），这些信息提供了用户偏好的平衡图（balanced picture）。因此，剩余的 user-item pair 关系（这些剩余的pair 占比很高）被视为缺失数据（missing data），并从分析中省略。这对于隐式反馈是不可能的，因为只关注收集到的隐式反馈会给我们留下正反馈 （positive feedback），极大地扭曲了完整的用户偏好。因此，在隐式反馈中解决缺失数据也很重要，这是预期会发现大多数负反馈的地方。

   • 包含大量噪音：当跟踪用户行为时，我们只能猜测他们的偏好和真实的动机。例如，我们可能会观察用户的购买行为，但这并不一定代表用户对item 的 postive 评价。该item 可能作为礼物来购买，而不是自己使用，因此购买不等于自己喜欢（而是接受礼物的人喜欢）；也可能购买的时候用户并不了解产品，使用一段时间后对产品很失望。例如，我们可能会发现用户一直在观看某个节目，但是事实上用户可能在睡觉，只是电视机一直开着而已。这意味着隐式反馈数据中，不仅没有 negative 数据， postive 数据也是不可靠的。

   • 显式反馈的数值代表偏好（preference），隐式反馈的数值表示置信度（confidence）：基于显式反馈的系统可以让用户表达自己的喜好程度，如：评分从 1 （完全不喜欢）到 5（非常喜欢）。而基于隐式反馈的数值描述了行为的频次，如：用户观看某个节目的时长、用户购买某个 item 的次数。较大的值并不表示较高的偏好。如，用户最喜欢的电影可能就看过一次，但是有些用户喜欢程度一般的电影可能就看了几次（陪朋友一起看）。

     但是隐式反馈的数值绝对有价值，因为它告诉我们有关某种观察结果的置信度。单次事件的发生可能是由于和用户偏好无关的偶然因素引起，但是重复事件的发生一定可以反应用户的某种意图。

   • 隐式反馈推荐的评估需要采取合适的指标：传统的显式反馈推荐中，我们为每个 user-item 预测一个评分，然后通过明确的指标（如均方误差 MSE）来衡量预测的准确性。但是在隐式反馈推荐中，我们必须考虑到 item 是否可用、item 之间的竞争、重复反馈等。例如，在电视节目推荐的过程中，如何评估那些看过多次的节目？ 如何评估播放时段重叠的两个节目？（因为用户无法在同一时刻观看两个节目）。

2. 给定用户 $u$$u$ 和 item $i$$i$ ，我们称 $r_{u,i}$$r_{u,i}$ 为观测值 observation 。

   • 对于显式反馈数据，$r_{u,i}$$r_{u,i}$ 代表用户 $u$$u$ 对 item $i$$i$ 的偏好评分，其中：评分越高代表越喜欢、评分越低代表越不喜欢。

   • 对于隐式反馈数据，$r_{u,i}$$r_{u,i}$ 代表用户的行为频次。例如 $r_{u,i}$$r_{u,i}$ 可以表示用户 $u$$u$ 购买产品 $i$$i$ 的次数、或者用户 $u$$u$ 在网页 $i$$i$ 上花费的时长。在电视推荐案例中，$r_{u,i}$$r_{u,i}$ 表示用户 $u$$u$ 完整观看节目 $i$$i$ 的次数。例如，$r_{u,i}=0.7$$r_{u,i} = 0.7$ 表示用户观看了 70% 的节目，而对于观看了两遍节目的用户则设置 $r_{u,i}=2$$r_{u,i} = 2$ 。

   对于绝大多数 user-item ，显式评分都是未知的，因此基于显式反馈数据的推荐算法使用相对较少的已知评分数据，忽略 missing data 。但是在隐式反馈数据中，所有的 user-item 的行为次数都是已知的：要么发生了行为，即 $r_{u,i}>0$$r_{u,i} \gt 0$ ；要么未发生行为，即 $r_{u,i}=0$$r_{u,i} = 0$ ，这表示零购买记录或者零观看时长。

3. 相关工作：

   • Neighborhood Model：CF 最常见的方法是基于邻域的模型。它的原始形式是 User-Based 的，根据志趣相投的用户的评分来预估未知评分。后来， Item-Based 的方法开始流行，它们使用同一个用户对相似 item 的评分来预估未知评分。由于 Item-Based CF 有更好的可扩展性、更高的准确性，因此在大多数情况下更受欢迎。此外，Item-Based CF 更适合解释预测背后的原因，这是因为用户熟悉他们以前喜欢的 item，但是通常不认识那些据称是志趣相投的用户。

     大多数 Item-Based CF 方法的核心是 item 之间的相似度，其中 $s_{i,j}$$s_{i,j}$ 表示 item $i$$i$ 和 $j$$j$ 的相似度。通常，相似度是基于 Pearson 相关系数。我们的目标是预测用户 $u$$u$ 对目标 item $i$$i$ 未观察到的值 $r_{u,i}$$r_{u,i}$ 。使用相似度，我们识别出 $u$$u$ 评分过的所有 item 中与 item $i$$i$ 最相似的 $k$$k$ 个 item。这组 $k$$k$ 个邻居由 ${\mathcal{S}}^k(u,i)$$\mathcal S^{k}(u,i)$ 来表示。预估的 $r_{u,i}$$r_{u,i}$ 为邻居评分的加权均值：

     $${\hat{r}}_{u,i}=\frac{\sum _{j\in {\mathcal{S}}^k(u,i)}{s}_{i,j}\times r_{u,j}}{\sum _{j\in {\mathcal{S}}^k(u,i)}{s}_{i,j}}$$

     但是基于显式反馈数据的 Item-Based CF 难以应用到隐式反馈数据中，有两个原因：

     • 在隐式反馈数据中， $r_{u,i}$$r_{u,i}$ 取值范围很广，取值相差很大（最小可为零，最大为万级甚至十万级）。相比之下显式反馈数据中的 $r_{u,i}$$r_{u,i}$ 取值在固定的几个评分 level，并且相差不大。

     • 尚不清楚如何计算隐式反馈数据的相似度。

     《Item-based top-N recommendation algorithms》 对如何使用具有隐式反馈的 Item-Based CF 方法进行了很好的讨论。

     所有 Item-Based CF 方法在隐式反馈方面都有一个缺点：它们无法灵活地区分用户偏好、以及我们对这些偏好的信心。

   • 潜在因子模型（Latent Factor Model）：潜在因子模型是协同过滤的替代方法，它的目标是揭示观测值的潜在特征。这些模型包括：pLSA、神经网络、LDA 。这里我们集中讨论观测矩阵的 SVD 分解：每个用户 $u$$u$ 对应一个用户因子向量 ${\overrightarrow{\mathbf{x}}}_u\in {\mathbb{R}}^f$$\mathbf{\vec x}_u\in \mathbb R^f$ ，每个item $i$$i$ 对应一个item 因子向量 ${\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^f$$\mathbf{\vec y}_i\in \mathbb R^f$ ， $f$$f$ 为潜在因子的数量。最终预测结果为两个向量的内积：

     $${\hat{r}}_{u,i}={\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i$$

     比较复杂的部分是参数估计。最近应用于显式反馈数据集的很多工作建议仅直接对观察到的评分进行建模，同时通过适当的正则化来避免过拟合，即：

     $$\underset{\mathbf{X},\mathbf{Y}}{min}\sum _{(u,i)\in {\mathbb{D}}^{\ast }}{(r_{u,i}-{\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i)}^2+\lambda (||{\overrightarrow{\mathbf{x}}}_u|{|}^2+||{\overrightarrow{\mathbf{y}}}_i|{|}^2)$$

     其中：

     • ${\mathbb{D}}^{\ast }$$\mathbb D^*$ 为数据集中存在观测值的部分（剔除 mising data ）。

     • $\mathbf{X}\in {\mathbb{R}}^{m\times f}$$\mathbf X \in \mathbb R^{m\times f}$ 为用户因子矩阵，每一行代表一个用户的因子向量；$\mathbf{Y}\in {\mathbb{R}}^{n\times f}$$\mathbf Y \in \mathbb R^{n\times f }$ 为item 因子矩阵，每一行代表一个item 的因子向量。

     • $\lambda$$\lambda$ 为正则化系数。

     本质上这是将用户和item 同时映射到公共的潜在因子空间（common latent factor space ）。模型参数通常通过随机梯度下降来学习。

     正如在最大的可用数据集 Netflix 数据集上报告的结果一样，上述模型往往优于 neighborhood model 。

     在这项工作中，我们将借鉴这种方法来处理隐式反馈数据集，这需要对模型公式和优化技术进行修改。

1.1 模型

1.1.1 模型

1. 定义二元变量 $p_{u,i}$$p_{u,i}$ 来指示用户 $u$$u$ 是否喜欢 item $i$$i$ ：

   $$\begin{array}{c}{p}_{u,i}=\{\begin{array}{ll}1,& r_{u,i}>0\\ 0,& r_{u,i}=0\end{array}\end{array}$$

   即：如果用户 $u$$u$ 购买了 item $i$$i$ （$r_{u,i}>0$$r_{u,i} \gt 0$ ），则认为用户 $u$$u$ 喜欢 item $i$$i$ ；如果用户 $u$$u$ 从未购买 item $i$$i$ （$r_{u,i}=0$$r_{u,i} = 0$ ），则认为用户 $u$$u$ 不喜欢 item $i$$i$ 。但是我们的结论和置信度水平（ confidence level ）有关。

   由于隐式数据的特点，$r_{u,i}=0$$r_{u,i} = 0$ 表示非常低的置信度：用户对item 没有任何行为，可能是因为除了用户不喜欢它之外的很多其它原因，如：用户可能压根不知道该item 的存在、或者由于价格太高或者已经购买过所以没有购买。

   另外，用户在 item 上的行为（$r_{u,i}>0$$r_{u,i} \gt 0$）可能是和是否喜欢无关的因素造成的。如：用户观看某个节目，可能仅仅因为他/她停留在之前喜欢看的节目的频道上；用户购买某个商品，可能仅仅作为礼物购买，尽管他/她不需要或者不喜欢这个商品。

   我们认为：随着 $r_{u,i}$$r_{u,i}$ 的增长，越能够表明用户确实喜欢该商品。因此我们引入一组变量 $c_{u,i}$$c_{u,i}$ 用于表明 $p_{u,i}$$p_{u,i}$ 的置信度水平。$c_{u,i}$$c_{u,i}$ 的一个合理选择是：

   $$c_{u.i}=1+\alpha r_{u,i}$$

   其中：

   • 超参数 $\alpha$$\alpha$ 为置信度增长率，通过实验表明 $\alpha =40$$\alpha = 40$ 可以得到一个很好的结果。

   • 常数 1 是为了对所有的 $r_{u,i}$$r_{u,i}$ 取值范围都能得到一个非零的置信度。

     因此 $c_{u,i}$$c_{u,i}$ 对所有的 $p_{u,i}$$p_{u,i}$ 都有最小的置信度 1，并且随着观察到更多的证据，则对 $p_{u,i}$$p_{u,i}$ 的置信度相应增加。

2. 假设每个用户 $u$$u$ 对应一个用户因子向量 ${\overrightarrow{\mathbf{x}}}_u\in {\mathbb{R}}^f$$\mathbf{\vec x}_u\in \mathbb R^f$ ，每个item $i$$i$ 对应一个item 因子向量 ${\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^f$$\mathbf{\vec y}_i\in \mathbb R^f$ ， $f$$f$ 为潜在因子的数量。我们建模用户偏好为两个向量的内积：

   $${\hat{p}}_{u,i}={\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i$$

   然后通过最小化代价函数来求解参数：

   $$\underset{\mathbf{X},\mathbf{Y}}{min}\left(\sum _{u,i}{c}_{u,i}{(p_{u,i}-{\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i)}^2\right)+\lambda (\sum _u||{\overrightarrow{\mathbf{x}}}_u|{|}^2+\sum _i||{\overrightarrow{\mathbf{y}}}_i|{|}^2)$$

   这类似于显式反馈数据中的矩阵分解技术，但是这里有两个重要区别：

   • 需要考虑置信度 $c_{u,i}$$c_{u,i}$ 。

   • 需要考虑所有的 user-item ，而不仅仅是观测数据对应的 user-item 。

1.1.2 优化

1. 注意到代价函数中包含 $m\times n$$m\times n$ 项，其中 $m$$m$ 为用户量、$n$$n$ 为 item 量。对于大型数据集 $m\times n$$m\times n$ 可以轻松达到数十亿。

   由于计算规模太大，因此大多数直接优化技术（如随机梯度下降）不适用。这里我们提出了一种替代的高效优化算法。

   对于显式反馈数据集，代价函数包含的项为观测值的数量，它远远小于 $m\times n$$m\times n$ 。

2. 观察到：当用户因子向量或者 item 因子向量固定时，代价函数变成二次函数，因此可以轻松计算全局最小值。这就是交替最小二乘 （alternating-least-square:ALS） 的优化过程。

   在ALS 过程中，我们需要交替重新计算用户因子向量、item 因子向量，并且保证每一步都可以降低代价函数。

   ALS 可以应用于显式反馈数据，其中计算在观测数据上进行。 但是在隐式反馈数据上，计算在所有 user-item 上进行，这导致计算规模的急剧增长。我们可以利用代数结构来解决该问题，从而得到一个 scalable 的优化方法。

3. 第一步是重新计算所有的用户因子向量。

   • 在重新计算用户因子向量之前，我们首先计算矩阵 ${\mathbf{Y}}^{\mathrm{\top }}\mathbf{Y}\in {\mathbb{R}}^{f\times f}$$\mathbf Y^\top\mathbf Y\in \mathbb R^{f\times f}$ ，其计算复杂度为 $o(f^{2}n)$$o(f^2n)$ 。

   • 对于每个用户 $u$$u$ ，定义一个对角矩阵 ${\mathbf{C}}^u=\text{diag}(c_{u,1},\cdots ,c_{u,n})\in {\mathbb{R}}^{n\times n}$$\mathbf C^{u}=\text{diag}(c_{u,1},\cdots,c_{u,n})\in \mathbb R^{n\times n}$ ，它给出了用户 $u$$u$ 在每个item 的置信度水平；定义向量 ${\overrightarrow{\mathbf{p}}}_u=(p_{u,1},\cdots ,p_{u,n}{)}^{\mathrm{\top }}\in {\mathbb{R}}^n$$\mathbf{\vec p}_u = (p_{u,1},\cdots,p_{u,n})^\top \in \mathbb R^{n}$ ，它给出了用户 $u$$u$ 在每个 item 上的偏好。

     通过对代价函数求偏导，并令偏导为零来最小化代价函数，我们得到新的 ${\overrightarrow{\mathbf{x}}}_u$$\mathbf{\vec x}_u$ 为：

     $${\overrightarrow{\mathbf{x}}}_u={({\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}+\lambda \mathbf{I})}^{-1}{\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u{\overrightarrow{\mathbf{p}}}_u$$

   • 一个计算瓶颈是 ${\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}$$\mathbf Y^\top\mathbf C^u\mathbf Y$，它的计算复杂度为 $O(f^{2}n)$$O(f^2n)$ 。考虑所有的 $m$$m$ 个用户，则计算复杂度高达 $O(f^{2}nm)$$O(f^2nm)$ 。

     考虑到 ${\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}={\mathbf{Y}}^{\mathrm{\top }}\mathbf{Y}+{\mathbf{Y}}^{\mathrm{\top }}({\mathbf{C}}^u-\mathbf{I})\mathbf{Y}$$\mathbf Y^\top\mathbf C^u\mathbf Y = \mathbf Y^\top\mathbf Y + \mathbf Y^\top(\mathbf C^u-\mathbf I) \mathbf Y$ 。

     • ${\mathbf{Y}}^{\mathrm{\top }}\mathbf{Y}$$\mathbf Y^\top\mathbf Y$ 和 $u$$u$ 无关，并且已经预计算好了。

     • 对于 ${\mathbf{Y}}^{\mathrm{\top }}({\mathbf{C}}^u-\mathbf{I})\mathbf{Y}$$\mathbf Y^\top(\mathbf C^u-\mathbf I) \mathbf Y$ ，注意到 ${\mathbf{C}}^u-\mathbf{I}$$\mathbf C^u-\mathbf I$ 仅有 $n_u$$n_u$ 个非零元素，$n_u$$n_u$ 为 $r_{u,i}>0$$r_{u,i}\gt 0$ 的元素个数，通常有 $n_u\ll n$$n_u\ll n$ 。因此其计算复杂度为 $O(f^2{n}_u)$$O(f^2n_u)$ 。

     由于 ${\overrightarrow{\mathbf{p}}}_u$$\mathbf{\vec p}_u$ 仅包含 $n_u$$n_u$ 个非零元素，因此 ${\mathbf{C}}^u{\overrightarrow{\mathbf{p}}}_u$$\mathbf C^u\mathbf{\vec p}_u$ 也仅仅包含 $n_u$$n_u$ 个非零元素。因此重新计算重新计算 ${\overrightarrow{\mathbf{x}}}_u$$\mathbf{\vec x}_u$ 的计算复杂度为 $O(f^2{n}_u+f^3)$$O(f^2n_u + f^3)$ 。其中：

     • 令 ${\mathbf{B}}_1={\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}+\lambda \mathbf{I}$$\mathbf B_1 = \mathbf Y^\top\mathbf C^u \mathbf Y + \lambda \mathbf I$ ，计算 ${\mathbf{B}}_1$$\mathbf B_1$ 的计算复杂度为 $O(f^2{n}_u)$$O(f^2n_u)$

     • 令 ${\mathbf{B}}_2={\mathbf{B}}_1^{-1}$$\mathbf B_2 = \mathbf B_1^{-1}$ ，计算 ${\mathbf{B}}_2$$\mathbf B_2$ 的计算复杂度为 $O(f^3)$$O(f^3)$ 。虽然存在更高效的矩阵求逆算法，但是对于较小的 $f$$f$ 值（在几百以内），差距可能不大。

     • 计算 ${\mathbf{B}}_2{\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u{\overrightarrow{\mathbf{p}}}_u$$\mathbf B_2 \mathbf Y^\top\mathbf C^u \mathbf{\vec p}_u$ 的计算复杂度为 $O(f^2{n}_u)$$O(f^2n_u)$ 。

     考虑所有的 $m$$m$ 个用户，则算法的计算复杂度为 $O(f^{2}N+f^{3}m)$$O(f^2 N + f^3 m)$ ，其中 $N$$N$ 为观测到的所有非零 $r_{u,i}$$r_{u,i}$ 的数量：$N=\sum _u{n}_u$$N=\sum_u n_u$ 。可以看到：计算复杂度为观测值规模 $N$$N$ 的线性函数。这里 $f$$f$ 的典型大小在 20~200 。

4. 第二步是重新计算所有的 item 因子向量。

   • 首先计算矩阵 ${\mathbf{X}}^{\mathrm{\top }}\mathbf{X}\in {\mathbb{R}}^{f\times f}$$\mathbf X^\top\mathbf X\in \mathbb R^{f\times f}$ ，其计算复杂度为 $o(f^2\times m)$$o(f^2\times m)$ 。

   • 对于每个item $i$$i$ ，定义一个对角矩阵 ${\mathbf{C}}^i=\text{diag}(c_{1,i},\cdots ,c_{m,i})\in {\mathbb{R}}^{m\times m}$$\mathbf C^{i}=\text{diag}(c_{1,i},\cdots,c_{m,i})\in \mathbb R^{m\times m}$ ，它给出了每个用户在item $i$$i$ 上的置信度水平；定义向量 ${\overrightarrow{\mathbf{p}}}_i=(p_{1,i},\cdots ,p_{m,i}{)}^{\mathrm{\top }}\in {\mathbb{R}}^m$$\mathbf{\vec p}_i = (p_{1,i},\cdots,p_{m,i})^\top\in \mathbb R^{m}$ ，它给出了每个用户在 item $i$$i$ 上的偏好。

     通过最小化代价函数，我们得到新的item 因子向量为：

     $${\overrightarrow{\mathbf{y}}}_i={({\mathbf{X}}^{\mathrm{\top }}{\mathbf{C}}^i\mathbf{X}+\lambda \mathbf{I})}^{-1}{\mathbf{X}}^{\mathrm{\top }}{\mathbf{C}}^i{\overrightarrow{\mathbf{p}}}_i$$

     采用同样的优化技巧，我们计算item 因子向量的计算复杂度为 $O(f^{2}N+f^{3}n)$$O(f^2N + f^3n)$ 。

5. 我们交替优化用户因子向量和item 因子向量，直到模型收敛，典型的交替次数为 10 次。

   • 整个优化过程的计算复杂度是输入数据规模 $N$$N$ 的线性函数。

   • 在得到用户因子向量、item 因子向量之后，对于用户 $u$$u$ 我们预估他/她对item $i$$i$ 的偏好：

     $${\hat{p}}_{u,i}={\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i,i=1,2,\cdots ,n$$

     并选择 ${\hat{p}}_{u,i}$$\hat p_{u,i}$ 最大的 $K$$K$ 个item 作为推荐结果。

1.1.3 讨论

1. 事实上我们可以修改偏好 $p_{u,i}$$p_{u,i}$ 和 $r_{u,i}$$r_{u,i}$ 的关系，如增加阈值 $\eta$$\eta$ ，使得：

   $$\begin{array}{c}{p}_{u,i}=\{\begin{array}{ll}1,& r_{u,i}>\eta \\ 0,& r_{u,i}\le \eta \end{array}\end{array}$$

   类似地，我们也可以修改置信度 $c_{u,i}$$c_{u,i}$ 和 $r_{u,i}$$r_{u,i}$ 的关系：

   $$c_{u,i}=1+\alpha \log (1+r_{u,i}/ϵ)$$

   但是不管它们如何变化，其核心都是解决隐式反馈数据独有的特点：

   • 将原始观测 $r_{u,i}$$r_{u,i}$ 转换为刻画两个不同意义的、独立的变量：偏好 $p_{u,i}$$p_{u,i}$ 、置信水平 $c_{u,i}$$c_{u,i}$ 。这可以更好的反应隐式反馈数据的性质，并对提高模型预测效果至关重要。

   • 通过利用变量的代数结构，在线性时间内解决所有可能的 $m\times n$$m\times n$ 个 user-item 组合。

2. 一个好的推荐应该有良好的可解释性，即：一段描述文字给出为什么向用户推荐该item 。这有助于提高用户对推荐系统的信任，以及提高用户对推荐结果给出良好的反馈。另外，这也是调试推荐系统、跟踪 badcase 的宝贵手段。

   Item-Based CF 推荐结果的解释很简单，因为推荐是根据用户历史行为来直接推断出来的。但是潜在因子模型的可解释性比较困难，因此模型使用用户因子向量、item 因子向量从而阻断了推荐结果和用户历史行为之间的直接关联。

   在这里，我们的 ALS 优化方法提供了一种新的方法来解释潜在因子模型。考虑到：

   $${\overrightarrow{\mathbf{x}}}_u={({\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}+\lambda \mathbf{I})}^{-1}{\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u{\overrightarrow{\mathbf{p}}}_u$$

   因此用户 $u$$u$ 对 item $i$$i$ 的偏好为：

   $${\hat{p}}_{u,i}={\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i={\overrightarrow{\mathbf{y}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_u={\overrightarrow{\mathbf{y}}}_i^{\mathrm{\top }}{({\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}+\lambda \mathbf{I})}^{-1}{\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u{\overrightarrow{\mathbf{p}}}_u$$

   定义 ${\mathbf{W}}^u={({\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}+\lambda \mathbf{I})}^{-1}\in {\mathbb{R}}^{f\times f}$$\mathbf W^u = \left(\mathbf Y^\top\mathbf C^u \mathbf Y + \lambda \mathbf I\right)^{-1}\in \mathbb R^{f\times f}$ ，它可以认为是与用户 $u$$u$ 相关的一个权重矩阵。因此以用户 $u$$u$ 的角度来看，item $i$$i$ 和 $j$$j$ 的相似性为：

   $$s_{i,j}^u={\overrightarrow{\mathbf{y}}}_i^{\mathrm{\top }}{\mathbf{W}}^u{\overrightarrow{\mathbf{y}}}_j$$

   因此用户 $u$$u$ 对于 item $i$$i$ 预估的偏好为：

   $${\hat{p}}_{u,i}=\sum _j{s}_{i,j}^u{c}_{u,j}{p}_{u,j}$$

   考虑到：

   $$\begin{array}{c}{p}_{u,i}=\{\begin{array}{ll}1,& r_{u,i}>0\\ 0,& r_{u,i}=0\end{array}\end{array}$$

   因此有：

   $${\hat{p}}_{u,i}=\sum _{j,r_{u,j}>0}{s}_{i,j}^u{c}_{u,j}$$

   因此我们的潜在因子模型简化为一个加权历史行为（$r_{u,j}>0$$r_{u,j} \gt 0$ ）的线性模型，权重为 item-item 相似性。

   在预算 ${\hat{p}}_{u,i}$$\hat p_{u,i}$ 的过程中，每个历史行为都作为一个独立的项，因此我们可以分离每一项的贡献。贡献最大的历史行为可以作为推荐的主要解释。

   此外，我们还可以进一步将每个历史行为 $j$$j$ 的贡献拆分为两个独立的部分：

   • 与用户 $u$$u$ 有关、与 $i$$i$ 无关的重要性 $c_{u,j}$$c_{u,j}$ 。

   • 与用户 $u$$u$ 有关、与 $i$$i$ 也相关的相似性 $s_{i,j}^u$$s_{i,j}^u$ 。注意：item 之间的相似性取决于具体的用户，这反映了一个事实：相同的一对item 在不同的用户看来具有不同的相似性。

   这和 Item-Based CF 模型非常相似，因此可以将我们的模型视为 Item-Based CF，其中item 相似性根据 ALS 优化过程计算得到。

3. 为了得到可解释性，我们需要求解 ${({\mathbf{Y}}^{\mathrm{\top }}{\mathbf{C}}^u\mathbf{Y}+\lambda \mathbf{I})}^{-1}{\overrightarrow{\mathbf{y}}}_j$$\left(\mathbf Y^\top\mathbf C^u \mathbf Y + \lambda \mathbf I\right)^{-1} \mathbf{\vec y}_j$ 从而方便计算 $s_{i,j}^u$$s_{i,j}^u$ 。类似上述讨论，我们预计算 ${\mathbf{Y}}^{\mathrm{\top }}\mathbf{Y}$$\mathbf Y^\top \mathbf Y$ ，最终计算复杂度为 $O(f^2{n}_u+f^3)$$O(f^2 n_u + f^3)$ 。

1.2 实验

1. 数据集：来自数字电视服务（digital tv service）采集的数据，包含大约 30 万个机顶盒上的数据。数据收集取得了用户协议并遵守隐私政策，数据都是匿名的，未包含任何个人身份信息。我们收集用户的频道切换事件，事件包含机顶盒切换到的频道以及时间戳。

   训练数据集包含四个星期的数据，其中覆盖大约 17000 个不同的电视节目。训练集中给出每个用户 $u$$u$ 和节目 $i$$i$ 的 $r_{u,i}$$r_{u,i}$ 值，它表示用户 $u$$u$ 观看节目 $i$$i$ 的次数。我们根据用户观看节目的时长除以节目的时长从而得到观看次数，因此 $r_{u,i}\in \mathbb{R}$$r_{u,i} \in \mathbb R$ 。如果用户 $u$$u$ 对节目 $i$$i$ 发生了多次观看事件，则直接将多次观看事件聚合到一个结果中。最终训练数据集包含约 3200 万非零 $r_{u,i}$$r_{u,i}$ 。

   我们将这四周的下一周数据来构造测试集，测试集的数据通过上标来区分，如 $r_{u,i}^t$$r_{u,i}^t$。然后我们使用前四周数据来训练模型，并预测接下来一周用户观看的内容。

   之所以选择四周训练是来自于一个实验研究：

   • 周期太短则训练样本不足，模型得不到充分训练从而使得模型效果很差。

   • 由于电视时间表受到季节性变化，因此周期太长会使得我们的训练集和测试集的节目分布不一致，预测没有多少意义。

     尽管我们发现我们的模型足够强大，可以避免受到季节性因素的影响。

2. 数据预处理：

   • 看电视的特点是：用户倾向于每周重复观看同样的节目。对于用户来说，推荐从未观看的节目可能更有价值。因此我们从测试数据集中删除用户曾经在训练期间观看过的节目。

   • 为了使得测试结果更为准确，我们令：

     $$\begin{array}{c}{p}_{u,i}^t=\{\begin{array}{ll}1,& r_{u,i}^t\ge 0.5\\ 0,& r_{u,i}^t<0.5\end{array}\end{array}$$

     我们认为：用户对一个节目观看时间不足 50% 并不足以表明用户喜欢该节目。

     经过这两步预处理，测试集包含大约 200 万个非零的 $p_{u,i}^t$$p_{u,i}^t$ 值。

   • 用户反复观看相同节目的趋势使得 $r_{u,i}$$r_{u,i}$ 在很大范围内变化。虽然大量的 $r_{u,i}$$r_{u,i}$ 位于 0~1 之间，但是存在部分 $r_{u,i}$$r_{u,i}$ 达到数百（如，某些用户每天用 DVD 记录同一档节目）。因此对于训练集，我们使用对数缩放置信度：

     $$c_{u,i}=1+\alpha \log (1+r_{u,i}/ϵ)$$

     其中 $ϵ={10}^{-8}$$\epsilon = 10^{-8}$ 。

   • 我们观察到一种特别的现象：用户观看同一个频道连续几个小时。事实上可能只有该频道最初的节目是用户感兴趣的，后面的节目并不感兴趣。只是由于用户做其它事情（或者睡觉），导致电视只是连续播发而已。我们称这一现象为动量效应，因动量效应而观看的节目实际上并不会反应用户的真实偏好。

     为克服动量效应的影响，我们在频道切换事件发生之后降低该频道第二个以及后续节目的权重（对原始 $r_{u,i}$$r_{u,i}$ 打折）。即，对于频道切换事件之后的第 $t$$t$ 个节目，其权重为：

     $$\frac{\exp (-(at-b))}{1+\exp (-(at-b))}$$

     通过实验发现 $a=2,b=6$$a=2,b=6$ 的效果较好，并且意义很直观：

     • 频道切换之后的第二个节目的 $r_{u,i}$$r_{u,i}$ 减半。

     • 频道切换之后的第五个节目的 $r_{u,i}$$r_{u,i}$ 降低了 99% 。

3. 评估方式：我们为每个用户生成一个有序的推荐列表，列表中的节目按照从预估最喜欢到最不喜欢来排序，然后向用户推荐。

   但是要意识到：我们并没有可靠的反馈来表明用户不喜欢那些节目。用户不看节目可能源自多种原因，而不一定是不喜欢。因此基于 precision 的指标（它需要知道正样本、负样本）不是很合适，因为它需要知道哪些节目是用户不喜欢的。另一方面，由于用户观看节目表示确实喜欢它，因此召回率（ recall ）（它只需要知道正样本）在这里更合适。

   我们用 ${\text{rank}}_{u,i}$$\text{rank}_{u,i}$ 来表示为用户 $u$$u$ 推荐的有序节目列表中，节目 $i$$i$ 的 percentile rank 。

   • ${\text{rank}}_{u,i}=0\mathrm{\%}$$\text{rank}_{u,i} = 0\%$ 意味着节目 $i$$i$ 被预测为用户 $u$$u$ 最喜欢的，因此位于列表中所有节目之前。

   • ${\text{rank}}_{u,i}=100\mathrm{\%}$$\text{rank}_{u,i}=100\%$ 意味着节目 $i$$i$ 被预测为用户 $u$$u$ 最不喜欢的节目，因此位于列表的末尾。

   考虑到每个用户的推荐列表长度不同，因此这里我们使用percentile rank 而不是绝对的排名。这使得不同用户的推荐效果之间可以进行比较。

   我们的评估指标是测试集的归一化 percentile rank：

   $$\begin{array}{c}\overline{{\text{rank}}_{u,i}}=\sum _{u,i}{w}_{u,i}^t\times {\text{rank}}_{u,i}\\ w_{u,i}^t=\frac{r_{u,i}^t}{\sum _j{r}_{u,j}^t}\end{array}$$

   该指标越低则表明实际观看的节目的 rank 更接近推荐列表的头部，因此该指标越低越好。我们对 $r_{u,i}^t$$r_{u,i}^t$ 越大的测试样本给予更大的权重。

   注意：对于随机预测 ${\text{rank}}_{u,i}$$\text{rank}_{u,i}$ 接近于 50% ，因此 $\overline{{\text{rank}}_{u,i}}\ge 50\mathrm{\%}$$\overline{\text{rank}_{u,i}} \ge 50\%$ 表明算法优于随机预测。

4. Baseline 模型：

   • 热度模型：根据节目的热度排序，然后推荐其中最热门的。这种方法的效果出人意料的好。

   • ItemBased CF 模型：使用余弦相似度，并将所有 item 作为邻居（而不是一小部分 item）的 ItemBased CF 模型。我们探索了ItemBased CF 的多个变种，并发现这种方式的效果最好。

     注意：这里使用的 ItemBased CF 配置仅适用于隐式反馈数据，对于显式反馈数据我们建议使用不同的配置。

5. 我们考察了不同数量的因子，其中 $f$$f$ 从 10 到 200， 在测试集上的结果如下图所示。

   • 仅根据热门推荐我们就可以达到 $\overline{\text{rank}}=16.46\mathrm{\%}$$\overline {\text{rank}} = 16.46\%$ ，Itembased CF 可以达到 $\overline{\text{rank}}=10.74\mathrm{\%}$$\overline {\text{rank}} = 10.74\%$ ，远低于随机预测的 $\overline{\text{rank}}=50\mathrm{\%}$$\overline {\text{rank}} = 50\%$ 。

   • 我们的模型效果最好。另外可以看到，随着 $f$$f$ 的增加模型效果不断改善，最终当 $f=200$$f=200$ 时 $\overline{\text{rank}}=8.35\mathrm{\%}$$\overline {\text{rank}} = 8.35\%$ 。因此，我们建议在资源限制内使用尽可能大的 $f$$f$ 。

   

6. 我们继续考察在测试集上的推荐质量，这里我们固定 $f=100$$f=100$ 。我们考察测试集中观看的节目在我们推荐列表中 percentile rank 的分布。对于理想的模型，这些观看的节目应该具有很低的 percentile rank 。

   可以看到：

   • 我们推荐的 top 1% 节目中，能够召回 27% 用户真正观看的节目。这远远超过了 baseline 的表现。

   • 如果我们不删除测试集中用户已经在训练期间曾经观看的节目，则结果更好，我们用黑色虚线表示。预测用户是否观看节目，要比预测用户是否首次观看节目容易得多。

     尽管向用户推荐一个他/她曾经看过的节目不是那么exciting，但是它确实有价值。这是在向用户提醒他们不要错过喜欢的节目。

     事实上仅仅通过检索用户以前观看的节目就可以轻松完成该提醒任务。

   

7. 我们研究了是否采用 $p_{u,i},c_{u,i}$$p_{u,i},c_{u,i}$ 的模型的效果。

   • 我们首先一个直接使用 $r_{u,i}$$r_{u,i }$ 的模型，因此我们最小化代价函数：

     $$\underset{\mathbf{X},\mathbf{Y}}{min}\sum _{u,i}(r_{u,i}-{\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i)+\lambda (\sum _u||{\overrightarrow{\mathbf{x}}}_u|{|}^2+\sum _i||{\overrightarrow{\mathbf{y}}}_i|{|}^2)$$

     注意：这是 SVD 算法的一个正则化版本，也是协同过滤采用的方法。

     • 如果没有正则化（ $\lambda =0$$\lambda =0$），则效果非常差，甚至比热门推荐的效果都要差。

     • 当采用正则化时效果得到改善，当 $\lambda =500$$\lambda = 500$ 时效果最好。虽然此时效果超过热门推荐，但是还是比 UserBased CF 效果更差。

       此时： $f=50$$f=50$ 时 $\overline{\text{rank}}=13.63\mathrm{\%}$$\overline{\text{rank}} = 13.63\%$ ； $f=100$$f=100$ 时 $\overline{\text{rank}}=13.40\mathrm{\%}$$\overline{\text{rank}} = 13.40\%$ 。

     这种较差的推荐质量是可以预期的，正如前面所述，直接将隐式反馈数据中的 $r_{u,i}$$r_{u,i}$ 作为偏好是不合适的。

   • 然后我们考察仅仅使用 $p_{u,i}$$p_{u,i}$ 的模型，因此我们最小化代价函数：

     $$\underset{\mathbf{X},\mathbf{Y}}{min}\sum _{u,i}(p_{u,i}-{\overrightarrow{\mathbf{x}}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i)+\lambda (\sum _u||{\overrightarrow{\mathbf{x}}}_u|{|}^2+\sum _i||{\overrightarrow{\mathbf{y}}}_i|{|}^2)$$

     其中 $\lambda =150$$\lambda = 150$ 。

     这个模型的效果要优于上一个模型： $f=50$$f=50$ 时 $\overline{\text{rank}}=10.72\mathrm{\%}$$\overline{\text{rank}} = 10.72\%$ ； $f=100$$f=100$ 时 $\overline{\text{rank}}=10.49\mathrm{\%}$$\overline{\text{rank}} = 10.49\%$ 。其效果略好于 ItemBased CF，但是比完整的模型效果差得多。

     对于完整模型：$f=50$$f=50$ 时 $\overline{\text{rank}}=8.93\mathrm{\%}$$\overline{\text{rank}} = 8.93\%$ ； $f=100$$f=100$ 时 $\overline{\text{rank}}=8.56\mathrm{\%}$$\overline{\text{rank}} = 8.56\%$ 。这表明我们在二元偏好模型中增加置信水平的重要性。

8. 现在我们考察 $f=100$$f=100$ 的完整模型在不同类型的节目和用户上的表现。

   • 训练数据中不同节目的热度（观看人次）明显不同。有的节目很受人欢迎，而另一些节目则非常冷门。

     我们基于递增的热度（从训练集中统计得到）将测试集中的postive 观测结果划分为15 个桶，其中第一个桶表示最冷门的节目，第 15 个桶表示最热门的节目。然后我们评估每个桶中节目在测试集中的性能。

     可以看到（蓝色曲线），我们的模型效果在不同的桶之间存在巨大的 gap：预测热门节目更为容易，而预测冷门节目更加困难。因此某种意义上，我们的模型倾向于安全地推荐更为热门的节目。

   • 另一方面，我们根据用户的观看时长（根据训练集统计）也将用户划分为多个桶。第一个桶表示用户几乎没有观看记录，最后一个桶表示观看时间最长的用户。然后我们评估每个桶中用户在测试集中的性能。

     可以看到（红色曲线）：除了第一个桶之外，其它所有桶的用户的预测性能都非常相似。这有些出乎我们的意料，因为在显式反馈数据集中我们的经验是：随着我们收集用户相关的信息越多，预测质量会得到显著提高。为什么用户收看的时间越多，效果反而得不到提升？一个可能的解释是：因为这些账户背后对应的不是同一个人，可能家里有多个人使用同一个账户来观看同一台电视，这导致该账号的观看时间会更长。

   

9. 最后我们分析推荐的可解释性。下表给出了我们针对同一个用户的三个推荐（粗体表示），以及每个推荐最相关的 5 个用户曾经观看过的节目。第一列都是真人秀、第二列都是漫画、第三列都是医学纪录片。这些符合常识的解释可以帮助用户理解为什么推荐某些节目。

   另外，我们还报告top 5 相似的、曾经观看过的节目（即 $s_{i,j}^u\times c_{u,j}$$s_{i,j}^u\times c_{u,j}$）对该推荐的打分 ${\hat{p}}_{u,i}$$\hat p_{u,i }$ 的贡献。可以看到贡献最大的 5 个节目占比从 35% 到 40%，这表明用户看过的很多其它节目也有较大的贡献。

   

1.3 总结

1. 在这项工作中，我们研究了隐式反馈数据集的协同过滤，这是一种非常常见的情况。我们的主要发现之一是隐式用户观察值应该转换为两个量：偏好（preference） 和置信度 （confidence） 。这种 preference-confidence 划分与广泛研究的显式反馈数据集没有相似之处，但是在隐式反馈分析中起到关键作用。

   我们提供了一种直接解决 preference-confidence 范式的潜在因子算法。与显式反馈数据集不同，我们将所有 user-item 偏好作为输入，包括那些没有任何观察值的输入。这是至关重要的，因为仅仅观察值的输入天生地就偏向于 positive preference，因此无法很好地反映用户的个人画像。然而，将所有 user-item 值作为模型的输入会引发严重的可扩展性问题。我们通过利用模型的代数结构来解决这个问题，这将导致算法与输入规模线性缩放，从而可以解决全量 user-item 输入而无需求助于任何降采样。该算法的一个有趣特性是：算法允许向用户解释推荐理由，这在潜在因子模型中很少见。这是通过该算法与著名的 ItemBased CF 产生了一个令人惊讶的、有洞察的链接来实现的。

   我们的算法作为大规模电视推荐系统被实施和测试。我们的方法力求在隐式反馈数据集的独特属性和计算可扩展性之间找到适当的平衡。我们目前正在探索以增加计算复杂度为代价来提高准确性的改进。例如，模型中我们以统一的置信度水平（confidence level） 处理所有 zero preference 的 user-item pair。由于绝大多数 pair 与 zero preference 相关，因此该决定节省了大量计算资源。但是，可以仔细地分析从而将这些 zero preference 拆分为不同的置信度水平。在我们的电视推荐案例中，用户没有观看节目这一事实可能意味着用户不知道该节目，或者还有另一个更喜欢的节目同时播放，或者用户根本不感兴趣。对于每一种原因我们可以采取不同的置信度水平。 这将导致我们对模型进行另一种可能的扩展--添加一个动态时间变量来解决用户在特定时间看电视的趋势。同样地，我们想建模某些节目类型在一天中不同时间更受欢迎。这是正在进行的研究的一部分，其中的主要挑战似乎是如何在模型中引入额外的灵活性，同时保持其良好的计算可扩展性。

   最后，推荐系统的目的是努力将用户指向他们可能没有购买或消费的 item。如果不进行深入的用户研究或调查，则很难评估该指标。在我们的案例中，我们简单的通过在测试集中删除训练集中用户已经观看的节目，从而实现该目标的评估。