令人着迷的时间动态CF算法

作者：一元，炼丹笔记四品炼丹师

Collaborative Filtering with Temporal Dynamics(2010)

背景

Yehuda Koren

本文是一篇较老的文章,是Yahoo的研究员关于协同过滤中时间动态建模的最为细致的讨论。

顾客对产品的偏好随着时间的推移而变化。随着新选择的出现，产品的认知和受欢迎程度也在不断变化。同样地，顾客的偏好也在不断演变，导致他们不断地重新定义自己的品味。因此，在设计推荐系统或一般客户偏好模型时，时间动态建模是一个关键。然而，这会有独特的挑战。在跨多个产品和客户的生态系统中，许多不同的特征同时发生变化，而其中许多特征又相互影响，这些变化往往是微妙的，并与一些数据实例相关联。这将问题与概念漂移(concept drift)探索区分开来。传统的时间窗或实例衰减方法可能无法奏效，因为它们在丢弃数据实例时会丢失太多信号。需要一种更敏感的方法，以便更好地区分瞬态效应和长期模式。我们提供的范例是创建一个模型来跟踪数据生命周期中随时间变化的行为。这允许我们利用所有数据实例的相关组件，同时丢弃那些被建模为不相关的组件。

跟踪不断变化的客户偏好

消费者的喜好会伴随着时间而变化, 客户喜好漂移的这一方面突出了文献中一个共同的范式，即全球漂移概念影响整个数据。在推荐系统中,我们面临一种更为复杂的概念漂移(concept drift)，即许多用户的相互关联的偏好在不同的时间点以不同的方式漂移。

这需要学习算法来跟踪多种变化的概念。此外，与单个消费者相关联的典型的低量的数据实例需要更简洁有效的学习方法，从而最大限度地利用数据中的信号。

instance selection: (1).丢弃和系统当前状态低相关的；一个常见的变体是时间窗口方法，只考虑最近的实例。这个简单模型的一个可能的缺点是，它对所考虑的时间窗口内的所有实例都赋予相同的意义，而完全丢弃所有其他实例。当时间偏移突然时，这可能是合理的，但当时间偏移是渐进的时，则不太合理。(2).一个精化是实例权重是基于实例的估计相关性进行加权的。使用时间衰减函数，当实例发生在更深的过去时，我们会对其进行加权。(3).第三种方法是基于集成学习，它保持了一系列预测因素，这些因素共同产生最终结果。这些预测因素根据其与当前时间点的感知相关性进行加权，例如，在最近的实例中更成功的预测者获得更高的权重。

所以我们尝试对变化的用户喜好进行建模：

寻求能够解释整个时间段内用户行为的模型，而不仅仅是当前行为（同时受到性能限制）。这是能够从每个时间点提取信号而忽略噪声的关键;
应该捕捉到多个不断变化的概念。有些依赖于用户，有些依赖于商品。同样，有些是渐进的，有些是突然的;
虽然我们需要为每个用户和/或商品分别建模独立的漂移“概念”或喜好，但必须在单个框架内组合所有这些概念。这允许跨用户和商品建模交互，从而识别更高级别的模式;
一般来说，我们不会试图推断未来的时间动态，例如，估计用户偏好的未来变化。这可能非常有用，但太难了，尤其是在已知数据量有限的情况下。相反，我们的目标是捕获过去的时间模式，以便将持续信号从瞬态噪声中分离出来。这确实有助于预测未来的行为.

时间感知的分解模型

因子模型剖析

我们假设每个用户对应一个向量,每个商品对应一个向量, 那么我们可以这么进行打分:

为了学习向量和向量,我们通过最小化下面的平方损失进行：

min_{q_*,p_*} sum_{(u,i,t) in mathcal{K}} (r_{ui} - q_i^Tp_u)^2 lambda (||q_i||^2 ||p_u||^2)

其中,由交叉验证获得。

这种纯因子模型很好地捕捉了用户和项目之间的交互作用。然而，大部分观察到的评分值都是由于与用户或者商品相关联的影响，而与它们的交互作用无关。一个主要的例子是，典型的CF数据显示出很大的用户和项目偏差，即一些用户给出的评分高于其他用户，而某些项目的评分高于其它商品。

我们将把这些不涉及用户商品交互的影响封装在基线预测值中。这些基线预测器倾向于捕捉大部分观察到的信号，特别是数据中的大部分时间动态。因此，对它们进行精确的建模是至关重要的，这样可以更好地识别真正代表用户-商品交互的信号部分，并且应该进行因式分解。

为了解决这种问题,我们构建一个静态的baseline预测,我们用表示平均得分, 和表示用户和商品的影响。

b_{ui} = mu b_u b_i

其中,和表示用户和商品观测到的偏差。于是我们得到新的估计：

bar{r}_{ui} = mu b_u b_i q_i^Tp_u

和上面的算法略有不同,此处我们使用SVD , 添加了第二组商品的因子，将商品与因子向量相关联, 这些新的商品因子用于根据用户评分的项目集来描述用户。于是我们有：

bar{r}_{ui} = mu b_u b_i q_i^T(p_u |R(u)|^{-frac{1}{2}} sum_{j in R(u)} y_j)

其中包含量用户打分的商品.

时变基线预测因子

通过两个主要的时间效应，大部分时间变异性包含在基线预测因子中。

第一个问题是解决：一个商品的受欢迎程度随着时间的推移而变化。例如，电影可能会因为外部事件（如演员在新电影中的出现）而进入或退出流行状态。这一点在我们的模型中得到了体现，即项目偏差不是一个常数，而是一个随时间变化的函数。
第二个主要的时间效应与用户偏见有关-用户随着时间的推移改变了他们的基准评分。例如，一个倾向于给一部普通电影评“4星”的用户，现在可能会给这样一部电影评“3星”，这是因为前面解释过的各种原因。因此，在我们的模型中，我们希望将参数bu作为时间的函数。

基于上述的问题,我们对之前我们的假设进行修改：

b_{ui}(t) = mu b_u(t) b_i(t)

表示用户在天对于商品的预估，一个主要区别是跨越长时间的时间效应和更多的瞬时效应。在电影分级的情况下，我们并不期望电影的受欢迎程度每天都在波动，而是会在更长的时间内发生变化。另一方面，我们观察到用户的影响每天都会发生变化，反映出消费者行为的不一致性。在建模用户偏差时，这需要更精细的时间分辨率，而不是足够捕捉项目相关时间效果的较低分辨率。

让我们从我们选择的时间变化的项目偏差，这是更容易捕捉，因为我们不需要最好的分辨率。因此，一个适当的决定是将商品偏差分为基于时间的。在每个对应于一个箱子的时间段内，我们使用不同的商品偏差。

决定如何将时间线划分为多个箱子时，应在实现更高分辨率（因此，更小的箱子）和每个箱子有足够评级（因此，更大箱子）的需求之间取得平衡。对于电影分级数据，有各种各样的垃圾箱大小，它们的准确度大致相同。在我们的实现中，每个bin对应于大约连续10周的数据，因此在数据集中，总共有30个bin跨越所有的时间。一天与一个整数相关联（在我们的数据中是一个介于1和30之间的数字），因此电影偏差被分成固定部分和时间变化部分：

b_i(t) = b_i b_{i,Bin(t)}

虽然binning参数在项目上工作得很好，但对用户来说这是一大的挑战。一方面，我们想要一个更好的分辨率，以便用户检测非常短暂的时间效应。另一方面，我们不期望每个用户有足够的打分，以产生可靠的估计孤立的bins。不同的函数形式可以用来参数化用户时间行为，但也伴有不同的复杂性和准确性。

第一个建模的选择:是非常简洁,使用一个线性函数来捕捉可能的渐进的用户偏差的迁移;对于每个用户,我们使用表示平均打分的时间。现在,如果用户在第天对电影进行来打分,那么这个评分相关的时间偏离可以被定义为:

dev_{u}(t) = sign(t - t_u) cdot |t - t_u|^{beta}

其中, 表示时间日期与的距离,其中是通过交叉验证得到,最终我们得到关于用户偏差时间相关的定义：

b_u^{(1)}(t) = b_u alpha_u cdot dev_u(t)

这么做的话,我们只需要学习两个参数, 和

第二种更为方便的参数化方式, 我们令成为一个带有个打分的用户;我们设计个时间点, , 在的打分日期上均匀分布，作为控制以下函数的核函数：

b_u^{(1)}(t) = b_u alpha_u cdot dev_u(t) rightarrow b_u^{(2)}(t) = b_u frac{sum_{l=1}^{k_u} e^{- gamma |t - t_l^u|} b_{t_l}^u}{sum_{l=1}^{k_u} e^{- gamma |t - t_l^u|}}

其中与控制点相关并且是从数据中自动化学习得到。以这种方式,我们将用户的偏差建模为参数的时间加权组合。此处的表示曲线的平滑情况,通过交叉验证得到, 是平衡灵活性和计算效率.

上面的函数已经非常好了，但在许多应用程序中，会出现与一天或一个会话相关的突然漂移。例如，在电影分级数据集中，我们发现一个用户在一天内给出的多个评分往往集中在一个值上。这种影响不会超过一天。这可能反映了用户当天的情绪，一天内给出的评分对彼此的影响，或多人帐户中实际评分者的变化。为了解决这种短暂的影响，我们为每个用户和每一天分配一个参数，吸收特定日期的变化。这个参数用表示。注意，在某些应用程序中，要使用的基本原始时间单位可以短于或长于一天。

所以我们得到线性函数：

b_u^{(1)}(t) = b_u alpha_u dev_u(t) b_{u,t}

基于曲线的模型变为：

b_u^{(2)}(t) = b_u frac{sum_{l=1}^{k_u} e^{- gamma |t - t_l^u|} b_{t_l}^u}{sum_{l=1}^{k_u} e^{- gamma |t - t_l^u|}} b_{u,t}

将上面所说的综合起来，我们使用线性函数加入突变的情况来建模得到：

b_{ui}(t) = mu b_u alpha_u dev_u(t) b_{u,t} b_i b_{i,Bin(t)}

于是我们最终就需要优化下面的式子:

min sum_{(u,i,t) in mathcal{K}} (r_{ui}(t) - mu - b_u - alpha_u cdot dev_u(t) b_{u,t} b_i b_{i, Bin(t)})^2 lambda (b_u^2 alpha_u^2 b_{u,t}^2 b_i^2 b_{i, Bin(t)}^2)

实验对比

static: 不带有时间影响:
mov: 表示与电影相关的时间影响:
linear: 线性建模用户偏差:
spline: 线性建模用户偏差:
linear 对用户的偏差和单天的影响linear建模 : 线性建模用户偏差:
spline 对用户的偏差和单天的影spline建模 : 线性建模用户偏差:

上面的时间没有考虑时间的周期性影响，我们也可以将其加入进来(但在我们但数据集中并没有发现明显但周期性,所以暂时就没有使用),

如果我们假设周期是基于天的, 那么,

在另一个基本的时间范围内，用户评分的变化与预测因素的变化有关。虽然是在时间时第个商品的一个独立于用户的度量但是用户对这种度量的响应往往不同。例如，不同的用户使用不同的评分尺度，单个用户可以随着时间的推移改变其评分尺度。因此，电影偏差的原始价值并不完全独立于用户。为了解决这个问题，我们在基线预测值中添加了一个时间依赖的缩放特性，我们用表示。

b_{ui}(t) = mu b_u alpha_u cdot dev_u(t) b_{u,t} (b_i b_{i,Bin(t)}) cdot c_u(t)

此处,我们令, 其中表示稳定的部分, 表示baseline的预测算子。通过该方式,我们可以将RMSE降低为0.9555。

时变因子模型

上面主要都是在讨论时间对于baseline predictor的影响，同时这也会影响用户和商品的交互。此处我们使用用户的每个喜好

p_u(t)^T = (p_{u1}(t),p_{u2}(t),...,p_{uf}(t))

于是我们有：

p_{uk}(t) = p_{uk} alpha_{uk} cdot dev_u(t) p_{uk,t}, k=1,2,...,f

此处, 用来抓住因子的固定部分, 近似随时间线性变化的部分, 表死后局部的,特定天的变化性。

于是我们便可以得到,

bar{r}_{ui} = mu b_u(t) b_i(t) q_i^T(p_u(t) |R(u)|^{-frac{1}{2}} sum_{j in R(u)} y_j)\ b_u(t) = b_u alpha_u dev_u(t) b_{u,t} \ b_i(t) = b_i b_{i,Bin(t)}\ p_u(t)^T = (p_{u1}(t),p_{u2}(t),...,p_{uf}(t)), p_{uk}(t) = p_{uk} alpha_{uk} cdot dev_u(t) p_{uk,t}, k=1,2,...,f\

实验对比

所有的方法都得益于越来越多的因素维度，这使得它们能够更好地表达复杂的电影用户交互。请注意，timeSVD 相对于SVD 的改进比SVD 相对于SVD 的改进更为显著

邻域模型的时间动力学

原先的加入i2i的信息,

bar{r}_{ui} = mu b_i b_u |R(u)|^{-frac{1}{2}} sum_{j in R(u)} (r_{uj} - b_{uj}) w_{ij} c_{ij}\

此处表示item-item的权重, 表示调整。

我们加入时间影响,我们的目标是提商品-商品的权重精确值，尽管存在干扰时间效应; 我们采用指数衰减, ,其中,用来控制用户的特定衰减率,于是我们得到：

bar{r}_{ui} = mu b_i(t) b_u(t) |R(u)|^{-frac{1}{2}} sum_{(j,t_j) in R(u)} e^{- beta_u cdot |t-t_j|} ((r_{uj} - b_{uj}) w_{ij} c_{ij})\

将前面的内容加入进来,

于是我们的优化目标变为：

min sum_{(u,i,t) in mathcal{K}} (r_{ui}(t) - mu - b_u - alpha_u cdot dev_u(t) - b_{u,t} - b_i - b_{i, Bin(t)}|R(u)|^{-frac{1}{2}} sum_{(j,t_j) in R(u)} e^{- beta_u cdot |t-t_j|} ((r_{uj} - b_{uj}) w_{ij} c_{ij}))^2 lambda (b_u^2 alpha_u^2 b_{u,t}^2 b_i^2 b_{i, Bin(t)}^2 w_{ij}^2 c_{ij}^2 )

通过加入时间信息,我们可以将原先的RMSE从0.9002降低为0.8885.

小结

跟踪客户对产品偏好的时间动态带来了独特的挑战。每个用户和商品都可能在其特性上经历一系列不同的变化。此外，我们通常需要在一个模型中对所有这些变化进行建模，从而将用户（或产品）相互连接，以识别共同的行为模式。仅仅是老的实例的衰减或多个独立模型的使用会损失太多信号，从而降低预测精度。我们采用的解决方案是在整个时间段内建立时间动态模型，使我们能够智能地将时间因素和全局时间因素分离开来。我们将此方法应用于两种主要的推荐技术。在因子分解模型中，我们模拟了用户和产品特性随时间的变化方式，以便从噪声模式中提取长期趋势。在一个商品-商品邻域模型中，我们展示了如何通过学习用户评价的两个项目之间的影响如何随时间衰减来揭示项目之间更基本的关系。在因子分解和邻域模型中，时间动态的包含被证明对提高预测质量非常有用，比各种算法的增强更有效。这导致了迄今为止在广泛分析的电影分级数据集上公布的最佳结果。

参考文献

Collaborative Filtering with Temporal Dynamics：https://www.cc.gatech.edu/~zha/CSE8801/CF/kdd-fp074-koren.pdf

filtering spline

0 人点赞