d0evi1 Reading time ~3 minutes

介绍

共享账号的推荐，很早就有人发paper，我们看下先人的一些探索《Top-N Recommendation for Shared Accounts》：

介绍

一般的推荐系统假设：每个用户账号(user account)表示单个用户(user)。然而，多个用户(user)经常共享单个账号(account)。一个示例是：一个家庭中的所有人会共享同一个在线视频账号、同一个在线音乐流账号、同一个在线电商账号、同一个商店的购物卡。

当多个用户共享账号时会引出三个问题。

首先，dominance problem。当所有推荐项（recommendations）只与共享账号的部分用户有关，至少一个用户不会获得任何相关推荐项，此时会引起“主导问题（dominance problem）”。我们会说：只有少量用户的兴趣会主宰该账号的推荐。另外，考虑一个经常购物的家庭。他们通常会在购买家庭用品时偶尔也会为孩子购买玩具。现在，很有可能所有推荐项会基于更多的家庭用品来生成，该推荐系统对孩子来说是基本没啥用。

第二，generality problem。当推荐项不仅与共享账号下所有用户兴趣都有些相关，并且又不仅仅与任一个用户相关时，会引发“generality problem”。当多个用户的不同品味兴趣被合到同一个账户上时，推荐系统更可能会推荐被大多数人喜欢的通用items（general items），忽略掉私人的品味。

第三，如果推荐系统可以为共享账号上的每个用户生成相关的推荐项，每个用户如何知道哪个推荐项是为你推荐的呢？我们称这为“presentation problem”。

如果有提供上下文信息（比如：time、location、购买意图、item内容、session logs等），context-aware推荐系统是SOTA的解决方案，它可以将accounts划分成多个用户，并检测在推荐时活跃用户的身份。

然而，通常对于划分账号来说通常没有提供这么多上下文信息：

  • 第一种情况是：许多公司不会保存过往的上下文信息日志，同时也不保存timestamps
  • 第二个情况是：家庭会在一个超市里进行一起购买，他们只有一个信用卡账户，当访问商店时会将购物进行放在一起。在这种情况下，context信息对于每个家庭成员来说是相同的，不能用来将家庭账号划分成各自成员。

因此，我们会介绍：在缺失上下文信息下的共享账号的top-N推荐，上面的关于共享账号的三个问题会在不使用任意上下文信息的情况下得到解决。

正式的，我们先考虑使用二元（binary）、positive-only的偏好反馈的CF的setting。我们将可提供数据表示成一个偏好矩阵，其中：行表示用户，列表示items。偏好矩阵中的每个值是1或0，其中1表示一个已知偏好，0表示未知。[12]称这种setting为one-class CF（OCCF），但它也被称为基于binary、postive-only偏好数据的top-N推荐。这种数据通常与implicit feedback有关。然而，它也是explicit feedback的结果。这不同于社交网站的例子（explicit）。其它相关的应用有：照片标签、文档的words、一个顾客购买的物品。

尽管在缺失上下文信息下共享账号的top-N推荐很重要，我们没有先前研究解决过该挑战。我们通过提出一个解决方案来解决所有item-based topN CF推荐系统的该case，基于binary、postive-only feedback来生成推荐。在这种情况下，我们覆盖了大多数应用，因为ICF很流行。大多数作者将ICF的流行性归结为：多个特性的组合（简洁、稳定、高效、准确），可以直觉性解释它们的推荐，并且能立即解释新进来的feedback。

我们展示了新的item-based top-N CF推荐系统，它允许我们在O(nlogn)下计算推荐分（非指数时间内）。

主要贡献如下：

  • 正式介绍缺失上下文信息下的共享账号top-N推荐
  • 提出解决方案
  • 一个必要特性
  • 实验表明：多个数据集上，可以检测共享账号下独立用户的偏好

2.问题定义

假设：U是用户集合，A是账号集合，I是items集合。更进一下，假设：

  • \(U(a) \subseteq U\)是具有共享账号a的用户的集合（例如：账号a的用户集合）
  • \(a(u) \in A\)是用户u属于的账号

注意：在该问题设定中，每个用户会属于一个账号。

首先，考虑用户评分矩阵（user-rating-matrix）\(T \in \lbrace 0, 1 \rbrace^{\mid U \mid \times \mid I \mid}\)。其中：

  • \(T_{ui}=1\)表示存在用户\(u \in U\)对于item \(i \in I\)的偏好
  • \(T_{ui}=0\)表示没有这样的偏好

我们给定：一个相关的推荐系统\(R_{ref}\)会产生在给定T下的期望推荐。因此，我们会说：通过相关推荐系统\(R_{ref}(T)\)在用户评分矩阵（user-rating-matrix）T上计算，如果i在u的top-N推荐中，则一个item i与一个user u相关。

不幸的是，在我们的问题设定中，T是未知的。因此，我们会给出账号评分评阵（account-rating-matrix） \(R \in \lbrace 0, 1 \rbrace^{\|A\| \times \|I\|}\)。其中：

  • \(R_{ai}=1\)表示账号\(a \in A\)对于\(i \in I\)是存在一个已知偏好的
  • \(R_{ai}=0\)表示不存在这样的信息

现在，缺失上下文信息的共享账号的top-N推荐，会设计一个共享账号推荐系统\(R_{sa}(R)\)，它基于账号评分评阵（account-rating-matrix）R，计算每个账号a的top \(N_a\)的推荐，如下：

  • top \(N_a\)包含了在账号a的用户集合下每个用户的top-N items，有：\(N = \frac{N_a}{\mid U(a) \mid}\)。实际上，这里目标是：通过最大化在topN中具有至少一个item的用户的数目（用户多，兴趣也多），来避免dominance问题和generality问题。
  • 账户a的用户集合中的某一用户，在top-Na中的哪个items是对他有意义的，这是很清楚的，presentation problem会得到解决

注意：在上面的定义中，共享账号的推荐系统不会获得共享每个账号的用户数目作为输入。更进一步，关于共享一个账号的用户的共享兴趣，不会做出任何假设。他们可以具有完全不同的兴趣，或者部分重叠的兴趣，或者完全重合的兴趣。

最后，注意该问题定义与一个典型的group推荐问题【10】正交。

  • 首先，在group推荐中，在共享账号下的用户的个体profiles通常都是已知的。而在这里，他们是未知的。
  • 第二：在group推荐中，通常会假设，推荐内容会被在共享账号中的所有用户所消费；而在这里，共享账号的每个用户可以区别对它有意义的推荐，并单独消费这些推荐。

3.相关推荐系统

通常，对于一个用户u的top-N推荐，推荐系统会先为每个候选推荐项i计算推荐得分 s(u,i)，接着从中选择按最高分排序的top-N推荐项。

对于binary、postive-only feedback，大多数流行的推荐系统的其中之一是，item-based CF推荐系统【2】。这些item-based推荐系统根源于这样的意图：好的推荐会与target user偏好的目标items相似，其中在两个items间的相似性会通过使用在用户喜欢的items的各自集合间的任意相似度measure进行衡量。因此，对于一个target user u，这种推荐系统：

  • 首先会发现KNN(j)：这是对j的k个最相似items，其中：每个喜欢的item j（\(T_{uj}=1\)）通过使用一个相似measure \(sim(j,i)\)进行衡量。
  • 接着，用户u对候选推荐项i的item-based推荐得分给定如下：
\[S_{IB}(u, i) = s_{IB}(I(u), i) = \sum_{j \in I(u)} sim(j, i) \cdot | KNN(j) \cap \lbrace i \rbrace |\]

…(1)

其中：

  • \(I(u) = \lbrace j \in I \mid T_{uj} = 1 \rbrace\)，这是u喜欢的items集合。

sim(j,i)的一个常见选择是cosine相似度。更进一步，归一化相似度得分可以提升表现【2】。sim(j,i)的定义如下：

\[sim(j,i) = \frac{cos(j,i)}{ \sum\limits_{l \in KNN(j)} cos(j, l)}\]

我们可以使用这种推荐系统作为相关推荐系统\(R_{ref}\)。

4.相关推荐系统的共享账号问题

简单将相关推荐系统（reference recommender system）应用到account-rating-matrix R上会导致次优结果，因为RRS会有三个共享账号问题。我们使用两个示例进行说明。在两个示例中，我们考虑：

  • 两个用户\(u_a\)和\(u_b\)会共享账号s
  • 用户\(u_a\)对于items \(a_1\)和\(a_2\)具有一个已知偏好（相当于推荐里面的trigger item list）
  • 用户\(u_b\)对于items \(b_1\), \(b_2\), \(b_3\)具有一个已知偏好（相当于推荐里面的trigger item list）
  • 存在5个候候选推荐：\(r_a^1, r_a^2, r_b^1, r_b^2, r_g\)

其中：

  • \(r_a^1\)和\(r_a^2\)是对于\(u_a\)来说的好推荐；
  • \(r_b^1\)和\(r_b^2\)是对于\(u_b\)来说的好推荐。
  • \(r_g\)是一个完全通用的推荐，对两个用户都是中性

图片名称

表1、2

表1和2给出了前两个示例一些立即计算。两表左侧都是每个候选推荐项（行）与共享账号s（列）的已知偏好间的相似度。两表的右侧都是每个候选推荐项（行）的三个推荐得分（列）。这些得分使用等式（1）计算而来，分别根据左侧的相似度值得到。前两个得分分别对应于\(u_a\)和\(u_b\)，如果他们没有共享一个账号。第三个得分是对于s（两者共享）的得分。

  • 第一个示例中（对应于表1）中的IB RRS会有genreality问题。对于表1，我们可以学到：如果\(u_a\)与\(u_b\)不共享账号，item-based RRS会为\(u_a\)正确安排最好的得分给\(r_a^1\)和\(r_a^2\)，为\(u_b\)安排\(r_b^1\)和\(r_b^2\)。然而，如果\(u_a\)和\(u_b\)会共享账号s，那么完全通用的item \(r_g\)会得到最高得分。在本例中，item-based RRS会具有genreality问题，因为它不会区别推荐得分（少量大值的求和，而是许多小值的总和）。

  • 第二个示例（对应于表2）展示了item-based RRS会有dominance问题。从表2看到，我们学到，如果\(u_a\)不会与\(u_b\)共享一个账号，item-based RRS会为\(u_a\)正确安排最高分\(r_a^1\)和\(r_a^2\)，为\(u_b\)分配\(r_b^1\)和\(b_b^2\)。然而，即使\(u_a\)和\(u_b\)会共享账号s，\(u_b\)的所有推荐项会接收到一个比\(u_a\)的任意推荐项更高的得分。因而，\(u_b\)的推荐项会主宰账号。在这种情况下，item-based RRS会具有dominance问题，因为它不会解释：\(u_b\)具有比\(u_a\)更多的偏好。

  • 两个示例都适合说明RRS存在的presentation问题。例如，考虑表1的第一行。推荐得分\(s(s, r_a^1) = 11\)是以下三项\(sim(a_1, r_a^1)=5, sim(a_2, r_a^1) = 5, s(b_1, r_a^1) = 1\)的总和。因此，它可以通过\(a_1, a_2, b_1\)来进行解释。然而这是一个坏的解释，因为由于\(b_1\)的存在，\(u_a\)会难于区分解释，会错误下结论成该推荐项对\(u_b\)来说也是有意义的。

5.解决genreality问题

前面章节表明，由于item-based RRS不会区分：一个得分是少量大相似得分的求和，还是许多小相似分得分的求程。因此会出现generality问题。因而，我们的第一步是采用item-based的推荐得分（等式1）到length-adjusted item-based（LIB）推荐得分上：

\[S_{LIB}(u, i) = S_{LIB}(I(u), i) = \frac{1}{|I(u)|^p} \cdot S_{IB}(I(u), i)\]

…(2)

其中，超参数\(p \in [0,1]\)。尽管这种adjustment不会立即解决genreality问题，它会提供一种方式，来区分是：在少量大相似得分的求和，还是许多小得分求和的问题。通过选择p > 0，我们可以创建一个bias，它偏向于少量大相似得分的求程。p值越大，该bias就越大。

由于因子\(\frac{1}{\mid I(u) \mid^P}\)对于所有候选推荐i来说是相同的，对于用户u根据\(S_{LIB}\)和\(S_{IB}\)的top N items是相同的。然而，当我们计算两个不同用户间的得分时，\(S_{LIB}\)也会解释用户喜欢的items总量。

为了避免generality问题，我们理想地希望：为共享账号a中的某个用户推荐与他高度相关的推荐项i。因此，我们会计算item i与每个个体用户\(u \in U(a)\)的推荐得分。正式的，我们希望根据它的推荐得分对所有item i进行排序：

\[\underset{u \in U(a)}{max} S_{LIB} (I(u), i)\]

不幸的是，我们不能计算理想的推荐得分，因为\(U(a)\)和I(u)是未知的。相似的，我们只知道账号a的偏好：\(I(a) = \lbrace j \in I \mid R_{aj} = 1 \rbrace\), 它表示账号a喜欢的items集合。

然而，我们可以使用它的上界对理想的推荐得分进行近似：

\[\underset{S \in 2^{I(a)}}{max} S_{LIB} (S, i) \geq \underset{u \in U(a)}{max} S_{LIB}(I(u), i)\]

其中，\(2^{I(a)}\)是\(I(a)\)的幂（power）（该集合包含了所在I(a)的可能子集）。提出的近似是一个理想得分的上界，因为I(u)的每个集合对于\(u \in U(a)\)来说是\(2^{I(a)}\)的一个元素。该近似是基于假设：所有I(a)的子集，它们对应于用户更可能生成最高的推荐得分，而非将它们随机地放在一起。

相应的，我们提出使用disambiguating item-based(DAMIB)推荐系统，关于账号a对于item i的推荐得分如下：

\[s_{DAMIB}(a, i) = \underset{S \in 2^{I(a)}}{max} S_{LIB}(S, i)\]

…(3)

每个得分\(s_{DAMIB}(a, i)\)对应于一个最优的子集\(S_i^* \subseteq I(a)\)：

\[S_i^* = \underset{S \in 2^{I(a)}}{argmax} S_{LIB}(S, i)\]

…(4)

因而，\(s_{DAMIB}(a, i) = s_{LIB}(S_i^*, i)\)。这样，DAMIB推荐系统不仅会计算推荐得分，也会发现账号a对于i的最大化length-adjuested item-based推荐得分的最优子集\(S_i^*\)。

换句话说，DAMIB推荐系统会基于直觉和task-specific准则，隐式地（implicitly）将共享账号a划分成子集\(S_i^*\)，每个\(S_i^*\)会对于候选推荐项i之一来最大化\(S_{LIB}\)。

  • 当\(S_{LIB}(S_i^*, i)\)很高时，我们希望，\(S_i^*\)能很好地对应一个个体用户。
  • 当\(S_{LIB}(S_i^*, i)\)很低时，在共享账号上没有用户对于i是一个强推荐，我们希望\(S_i^*\)是一个随机子集。

这样，我们会避免容易出错的（error prone）任务：估计在共享账号上的用户数目、并基于一个通用的聚类准则，显式地将账号a划分成它的个体用户。

更进一步，由于子集可以是潜在重合，DAMIB推荐系统不会关注在共享账号上的用户的已知偏好是否强重合、微重合、或者根本不重合。

最终，注意，对于p=0来说，它总是有：\(s_{DAMIB} = s_{LIB} = s_{IB}\)。因此，item-based推荐系统是DAMIB推荐系统的一个特例。

6.高效计算

可以发现，在等式(3)中的最大化，需要以指数时间复杂度来直接计算\(S_{LIB}\)，称为\(2^{\mid I(a) \mid}\)。相应的，直接计算\(s_{DAMIB}\)是很难的。

幸运的是，我们表明：\(S_{LIB}\)会允许我们来以O(nlogn)来计算\(s_{DAMIB}\)，其中：\(n = \mid I(a) \mid\)。该特性由定理6.1给出。

定理6.1 ： 假设a是一个账号，它喜欢items I(a)的集合。i是一个候选推荐。如果我们将所有items \(j,l \in I(a)\)进行排序，\(rank(j) < rank(l) \Leftrightarrow sim(j,i) > sim(l,i)\)，这样，子集\(S_i^* \subseteq I(a)\)会在所有\(S \in 2^{I(a)}\)上最大化\(S_{LIB}(S, i)\)，它是ranking的一个prefix。

证明：给定任意的\(S \subseteq I(a)\)。初始化P=S。当P不是一个prefix时，从P中移除最差的ranked item r，并添加最好的ranked item a到P中（它不在P中）。只要P还不是一个prefix，它会持有: \(sim(a, i) \geq sim(r, i)\)。因此，每个这样的item安排会增加\(s_{LIB}(P, i)\)（或至少等于），因为因子\(\frac{1}{\mid I(a) \mid^P}\)不会变化，在求和项\(\sum_{j \in I(a)} sim(j,i) \cdot \mid KNN(j) \cap \lbrace i \rbrace \mid\)中的一个较小项会被更一个更大的项所替代。因而，对于每个\(S \subseteq I(a)\)，它不是ranking的一个prefix，我们也可以总是找到一个prefix \(P \subseteq I(a)\)，满足：\(s_{LIB}(P,i) \geq s_{LIB}(S, i)\)。因此，子集\(S_i^*\)会最大化在所有\(S \in 2^{I(a)}\)上的\(s_{LIB}(S, i)\)，必须总是ranking的一个prefix。

由于最优的subset是一个prefix，我们可以发现，它在ranked items I(a)上的一次遍历是线性时间的。时间复杂度上的log因子会来自于对\(\mid I(a) \mid\)上进行排序。

该理论是我们方法的核心，因为它允许我们在O(nlogn)上计算\(s_{DAMIB}\)。

7.解决Dominance问题

DAMIB推荐系统允许我们检测：什么时候(when)发生domainance问题。这是因为：由DAMIB提供的每个推荐项i会伴随着一个清晰的解释，形式为：最优子集\(S_i^* \subseteq I(a)\)。因此，如果union \(U_{i \in top-N_a} S_i^*\)只是I(a)的一个小子集时，我们知道：这个小子集会在账号a的top \(N_a\)推荐中占统治地位。

可以通过选择在算法1中的ALG=DAMIB（我们称为COVER）来解决dominance问题。例如，我们为共享账号推荐的最终算法是DAMIB-COVER，其中：DAMIB-COVER(a) = COVER(a, DAMIB)。

图片名称

算法1

该DAMIB-COVAER算法会使用DAMIB得分来找出\(N_a\)的最高得分候选推荐，如果它的解释(explanation)\(S_c^*\)与更高排序的候选的解释不容易区分，我们就从top \(N_a\)中移除该候选推荐项c。\(D(S_c^*, C(a)) \geq \theta_D\)的解释区分性条件，会衡量一个候选(\(S_c^*\))以及更高排序候选（ranked candidates）C(a)的explanations的union是否足够不同。

关于explanation-diffference条件的可能的启发定义是：$$S_c^* \backslash C(a) \geq 0.5 \cdot S_c^* \(，并且\)\mid S_c^* \backslash C(a) \mid = \mid S_c^* \mid\(。然而，我们的实验表明：\)\mid S_c^* \backslash C(a) \mid \geq 1$$会比其它两种都好。因此，使用后一种启发法。

8.求解presentation问题

对于一个共享账号a，使用DAMIB-COVEAR生成top-Na推荐项是不够的，因为共享账号的用户不知道哪个推荐项属于哪个用户。这被称为presentation问题。

我们的解决方案是，将每个推荐项 \(i \in top-N_a\)、与它的解释(explanation)\(S_i^*\)表示在一起。我们期望：对于在top-Na中的items i的绝大多数，explanation \(S_i^*\)是u（共享账号a的某一用户）的偏好I(u)的一个子集。我们会在第9节进行验证该假设。

因此，我们将该推荐表示为item r推荐给喜欢s1, s2, s3的用户。接着，一个会用户认为s1, s2, s3是他的偏好，并知道r是推荐给他的。

9.实验评估

所有数所集都是公开提供的。另外，我们的源代码和数据集链接在：https://bitbucket.org/BlindReview/rsa 上有提供。该网站包含了脚本来自动化运营每个实验。另外，所有结果可以复现。

9.1 数据集

我们使用一个包含了真实的共享账号信息的数据集。CAMRa 2011数据集，它包含了家庭成员信息，关于用户对电影评分的一个子集。这样，我们可以使用该数据集构建真实共享账号。不幸的是，owner不希望分发该数据集，我们没有其它包含共享信息的数据集。然而，从CAMRa 2011数据集上，我们可以学到，大多数家庭账号包含了两个用户（290个家庭有272个），一些包含了三个（14/290），四个（4/290）。因此，我们会根据Zhang[15]的方法，来创建“人工伪造（synthetic）”的共享账号，随机将用户分成2个、3个、4个的组。尽管该方法并不完美，[15]表明‘synthetic’的共享账号会与CAMRa 2011数据集的真实共享账号特性相似。

我们在4个数据集中对解决方案进行评估：Yahoo!Music[13]、Movielens1M[4]，Book-Crossing[16]以及Wiki10+[17]数据集上。

YahooMusic: 14382个用户在1000首歌上进行评分：1-5分。由于我们会考虑binary、postive-only数据的问题设定。我们将4-5的评分转成1，忽略其它评分。平均的，一个用户具有8.7个偏好。

Movielens1M：包含了6038个用户在3533电影上，评分：1-5分。另外，我们会将4-5的评分转化为1. 平均一个用户具有95.3个偏好。

Book-Crossing：包含了两种信息。首先，用户在books上的评分：1-10分。与前2个数据集类似，我们会将评分8, 9, 10分转成偏好并忽略所有的其它评分。第二，也存在二元偏好，我们会添加到偏好列表中。总之，存在87835个用户，300695本书，每个user具有平均11个偏好。

wiki10+：包含了99162个tags，分配给20751个wikipedia文章。在本case中，我们考虑文章的标签推荐，文章看成是“users”的角色，tags看成是”items”的角色。如果一个文章a被打上至少一次的tag t标签，我们认为文章a具有tag t 的一个”perference”。在该context下，一个共享账号是一个大文章，它具有广泛主题，包含了多个更小在子主题下的“articles”。平均，每个article具有22.1个tags。

由于空间限制，我们只展示了在Yahoo!Music dataset上的数值结果。然而，对于其它三个数据集，可以在https://bitbucket.org/BlindReview/rsa上下结论，并导致相同的结论。

9.2 对比算法

我们比较了新算法：DAMIB-COVER，以及另两种算法。第一个对比算法是IB，是item-based RRS在account-rating-matrix上的应用，它忽略了shared account问题的存在。这是我们的baseline。第二个对比算法是IB-COVER，它被定义成IB-COVER(a) = COVER(a, IB). IB-COVER是与【14】的算法相似。

9.3 效果

首先，考虑到共享一个账号a（它具有\(| U(a) |\)个其它用户）的其中一个用户的recall。对于它的shared account来说，这是个体的top-5推荐项也出现在top-Na推荐项中的百分比，具有$$N_a = 5 \cdot U(a) $$。正式的，我们会定义user u的recall如下：
\[rec(u) = \frac{|top\-5(u) \cap top\-N_a(a)}{5}\]

理想的，在共享账号中所有用户的recall是1，这意味着，对于共享账号的top-Na是个体top-5的union，共有\(\|U(a)\|\)个用户共享账号。

现在，为了研究有多少用户会有共享账号的问题，我们会衡量用户没有获得任何相关推荐的比例，例如：不会发现单个的top-5个体推荐项在共享账号的top-Na推荐项。我们将该数目表示成\(rec_0^u\)，召回为0的用户占比。正式的，我们定义如下：

\[rec_0^\mathcal{U} = \frac{u \in \mathcal{U} | rec(u) = 0 }{| \mathcal{U} |}\]

一个具有共享账号问题的用户的示例如表3所示。该表展示了两个来自Movielens1M数据集的两个真实用户，它们各自已知的偏好I(u)，以及item-based个体top-5推荐。它们item-based个体top-5推荐项看起来合理给出它们的已知偏好，这两个用户是同一家庭的一部分并且共享账号看起来是不现实的。相应的，表3也展示了对于’synthetic’账号的推荐项，它们会在两个cases中（ \(R_{sa} = IB\)以及\(R_{sa} = DAMIB-COVER\)）被两个用户共享。在case \(R_{sa} = IB, rec(562) = 0\)中，例如：user 56

1

2不会获得单个推荐，它会存在共享一个账号的问题。
在case \(R_{sa} = DAMIB-COVER\)中，\(rec(562) = 0.6\)，例如：user 562会获得3个好的推荐，不存在严重的问题。很明显，只有一个示例，我们需要查询数据集中的所有用户来对比不同算法。

图1展示了Yahoo!Music数据集的\(rec_0^u\)。最近邻的数目k，是一个item-based RRS的参数。存在多种方式来选择k。在这些方法中，样本是以一个offline实验的accuracy，推荐的主观质量调整；在线A/B的accuracy，计算效率，等。因此，我们会呈现关于RRS的变化带来的结果，例如：ICF RS会与其它k种选择不同。相应的，图1的每个plot会展示一个不同k的结果。

对于每种k的选择，以及单独的top-5推荐，对应于4个实验：一个账号被1、2、3、4个用户共享。注意，一个账号如果由一个用户共享，这种实际并不是共享。每个水平轴表示共享该账号的用户数目，每个垂直轴表示产生的\(rec_0^u\)。4种不同的标记表明，4种不同的共享账号推荐系统\(R_{sa}\)：

  • baseline 算法IB
  • IB-COVER
  • 提出的DAMIB-COVER算法的两个变种

这两个变种会根据参数选择的不同有所区别：p=0.5和p=0.75。由于我们会随机重复每个实验5次，每个plot包含了5x4=20个相似的标记。然而，由于低传播、大多数标记会在相互的top上被绘制，形成dense的maker云。更进一步，由于95%的置信区间，意味着5个数据集的maker-clounds会更窄，我们没有进行绘制。相应的，两个maker-clouds会进行单独可视化，也会在5%的显著级别上具有显著不同。

我们从图1中做出4个观察：

  • 首先，我们观察到，baseline的效果并不好。当他们相互共享账号时，接近19%的用户获得不相关推荐。这表明，共享账号会对于推荐系统引起极大问题
  • 第二，我们提出的解法，DAMIB-COVER算法，可以提大提升\(rec_0^u\)。在一些情况下，提交是剧烈的。一个示例是$$| U(a) = 2\(，个体top-5会使用k=200进行生成。在本case中，当使用baseline IR算法时，12%的用户不会获得相关推荐。通过使用DAMIB-COVER(p=0.75)，该数目会减小到因子4（\)rec_0^U = 0.03$$）。
  • 第三，一些IB-COVER已经在IB上进行了提升。存在多个cases，其中DAMIB-COVER会进一步在IB-COVER上提升。另外，DAMIB-COVER会胜过IB-COVER会变得在评估presentation问题时更清晰。
  • 最后，当\(\| U(a) \| = 1\)，例如，当账号并不共享时，\(rec_0^u=0\)，是为baseline算法IB进行定义。然而，我们观察到，对于IB-COVER以及DAMIB算法的变种，\(rec_0^u\)可以足够低。因而，当账号不共享时，提出的DAMIB算法不会失败。

9.4 有限的trade-off

为了强调这一点：当没有账号共享时，DAMIB-COVER算法仍在传统设定下表现良好，我们也讨论了DAMIB-COVER的结果会在一个【2】使用的更确定的实验设定下。为了避免所有的困惑：该实验设定不会做关于共享账号的任何事。在该实验设定下，每个用户的一个偏好会被随机选中作为该用户的测试偏好\(h_u\)。如果一个用户只有一个偏好，不会有测试偏好被选中。剩余偏好会被在training matrix R中表示成1（由于没有账号会被共享，它在该case中是完全相同的）。R的所有其它条目都为0。我们将\(U_t\)定义成具有一个测试偏好的用户集合。对于每个user \(u \in U_t\)，每个算法会基于R对items \(\lbrace i \in I \| R_{ui} = 0 \rbrace\)进行排序。根据[2]，我们会使用hitrate@5来评估每个ranking。hitrate@5的给定如下：

\[HR@5 = \frac{1}{U_t} \sum_{u \in U_t} | \lbrace h_u \rbrace \cap top5(u) |\]

其中，top5(u)是用户u的5个最高的ranked items。因而，HR@5给出了测试偏好在top5 推荐中的测试用户百分比。Yahoo!Music数据集的实验结果如图2所示。除了早前讨论的算法外，图2也包含了baseline算法POP的结果，非个性化算法会根据它们的流行度对所有items进行排序；例如：用户在training set中的用户会偏向于该item的数目。在该case中，我们会重复实验5次，使用一个不同的随机分。另外，由于低传播性，5个数据点通常会绘制在互相的顶部。图2展示了DAMIB-COVER和IB在HR@5上非常相似。因此，以HR@5作为全局accuracy几乎没有trade-off。

9.5 Presentation

在第8节中，我们提出解通过将每个推荐项与它的explanation放在一起进行presenting，来解决presentation问题。如果这样，共享账号中的一个用户可以将一个explanation看成是他的偏好的一个子集，该用户会区分该推荐项，因此可以知道推荐项对它是有意义的。对于这种解决方案，很重要的是推荐项是可辨别的，例如：它的explanation是共享账号中某一用户的偏好子集。对于一个共享账号a，我们可以使用explanation \(S_i^*\)来测量一个推荐项i的可辨识性：

\[ldent(S_i^*) = max_{u \in U(a)} \frac{| S_i^* \cap I(u)}{ |S_i^*| }\]

理想的，ident(S_i^*) = 1，例如，explanation中的每个item是某个用户一个偏好。在最坏的情况下，\(ident(S_i^*) = 1/ \| U(a) \|\)，例如：explanation包含了一个在共享账号中所有用户的一个等量偏好，因此没有用户可以使用推荐进行区分。

图3展示了对于多个共享账号推荐系统\(R_{sa}\)，在Yahoo!Music数据集上 \(\| U(a) \| = 2\)的top10推荐的identifiability的直方图。从图3a所示，我们可以学到，如果某个用户简单地将item-based reference算法应用到Yahoo的共享账号数据集上，会发生presentation问题：很少的推荐项可以被在共享账号中的某一用户所区分出，例如：\(ident(S_i^*) = 1\)只有10%的explanations。图3b展示了使用IB-COVER来替代IB，不会对情况带来改善。然而，图3c展示了使用DAMIB-COVER可以弹性增加推荐项的区分性，例如：\(ident(S_i^*) = 1\)有近似60%的explanations。因而，DAMIB的explanations会优于iitem-based explanations。

参考

d0evi1 Reading time ~1 minute

介绍

facebook在2019在《Deep Learning Recommendation Model for Personalization and Recommendation Systems》。

摘要

facebook开发了一种SOTA的深度学习推荐模型（DLRM）并提供了Pytorch和Caffe2的实现。另外，还设计了一种专门的并行化scheme利用在embedding tables上的模型并行机制来缓和内存限制，利用数据并行机制来从fully-connected layers中扩展（scale-out）计算。我们比较了DLRM与已存在推荐模型.

1.介绍

在大型互联网公司中的许多任务上，部署了个性化和推荐系统，包括：CTR预估和rankings。尽管这些方法具有很长的历史，这些方法最近才拥抱神经网络。对于个性化和推荐，朝着深度学习模型架构设计方向贡献了两个主要视角。

第一个视角来自于推荐系统。这些系统最初部署了content filtering，其中：运营人员会将products按categories分类，而用户选择它们喜欢的categories，因而可以基于它们的偏好进行match[22]。该领域接着演化成使用collaborative filtering，基于用户过往行为（比如：用户对商品的评分）进行推荐。最近邻方法[21]通过将users和products进行分组（grouping）在一起来提供推荐，latent factor方法通过MF技术以及特定隐式factors将users和products进行特征化，并成功部署。

第二个视角来自预测分析(predictive analytics)，它依赖于统计模型根据给定数据来对events进行分类（classify）或预测（predict）。预测模型从简单模型（比如：linear或logistic regression）转向到深度网络上来建模。为了处理类别型数据，这些模型采用了embeddings，它会将one-hot和multi-hot vectors转化成在一个抽象空间中的dense表示。该抽象空间可以被解释成由推荐系统发现的latent factors空间。

在本paper中，我们引入了一个个性化模型，它可以通过将上述两个视角进行联合来表示。模型会：

  • 1.使用embeddings来处理稀疏特征（sparse features）（它可以表示categorical data）
  • 2.使用一个multilayer perceptron（MLP）来处理dense features

接着使用[24]中的统计技术将这些features进行显式交叉。最终，它会使用另一个MLP来post-processing交叉来寻找event probability。我们将该模型称为：DLRM（深度学习推荐模型）。见图1。该模型的PyTorch和Caffe2实现已公开。

2.模型设计与架构

在本节中，我们会描述DLRM的设计。我们会从网络的high-level组件开始，并解释how和why它们以一种特别的方式组合在一起，对未来模型设计有启发，接着描述组成模型的low-level operators和primitives，用于未来的硬件和系统设计。

2.1 DLRM组件

通过回顾以往模型，DLRM的high-level组件可以很容易理解。我们会避免完整回顾，把精力集中在早期模型的4个技术上，它可以在DLRM中的高级组件中被解释。

2.1.1 Embeddings

为了处理类型化数据，embeddings可以将每个category映射到一个在抽象空间中的dense表示上。特别的，每个embedding lookup可以被解释成使用一个one-hot vector \(e_i\)来获得embedding table \(W \in R^{m \times d}\)相应的row vector：

\[w_i^T = e_i^T W\]

…(1)

在更复杂的情况下，一个embedding也可以表示成多个items的加权组合**，它具有一个关于weights的multi-hot vector：

\[a^T = [0, \cdots, a_{i_1}, \cdots, a_{i_k}, \cdots, 0]\]

其中，

  • 对于\(i=i_1, \cdots, i_k\)，元素\(a_i \neq 0\)，否则为0 ，其中\(i=i_1, \cdots, i_k\)是相应的items。

注意，t embedding lookups的一个mini-batch可以写成：

\[S = A^T W\]

…(2)

其中，sparse matrix为：\(A = [a_1, \cdots, a_t]\)。

DLRMs会使用embedding tables来将categorical features映射成dense representations。然而，在这些embeddings被设计后，如何利用它们来生成更精准的预测呢？我们先来回顾下latent factor。

2.1.2 Matrix Factorization

推荐问题的常用形式，我们给定一个集合S：用户会对一些商品进行评分。我们通过两个vector：

  • \(w_i \in R^d, i=1,\cdots, n\)来表示第i个商品，
  • \(v_j \in R^d, j=1, \cdots, m\)来表示第j个user

以便寻找所有的ratings，其中n和m各表示products和users的总数。更严格的，当第i个商品已经被第j个user评分时，集合S包含了(i,j) tuples。

MF方法通过最小化下面的等式来求解该问题：

\[min \sum\limits_{(i,j) \in S} r_{ij} - w_i^T v_j\]

…(3)

其中：

  • \(r_{ij} \in R\)是第j个user对第i个product的rating，\(i=1, \cdots, m; j = 1, \cdots, n\)。

接着，假设：\(W^T = [w_1, \cdots, w_m]\)和\(V^T = [v_1, \cdots, v_n]\)，我们希望将full matrix的ratings \(R=[r_{ij}]\)近似为矩阵乘法 \(R \approx W V^T\)。注意，W和V可以被解释成两个embedding tables，其中每一行表示在latent factor space中的一个user/product。这些embedding vectors的dot product会生成后续rating的一个有意义的预测，这对于FM和DLRM的设计来说是一个key observation。

2.1.3 Factorization Machine

在经典问题中，我们希望定义一个预测函数：\(\phi: R^n \rightarrow T\)，从一个输入数据点\(x \in R^n\)到一个target label \(y \in T\)上的预测。作为示例，我们可以通过定义 \(T = \lbrace +1, -1 \rbrace\)预测CTR，其中：+1表示点击，-1表示未点击。

FM使用categorical data，通过定义以下形式的模型，来将二阶交叉并入到一个线性模型中：

\[\hat{y} = b + w^T x + x^T upper(VV^T) x\]

…(4)

其中：

  • 1.\(V \in R^{n \times d}\)
  • 2.\(w \in R^n\)
  • 3.\(b \in R\)
  • 4.\(d << n\)的参数
  • 5.upper会严格选择该矩阵的上三角部分【24】。

FM与SVM和polynomial kernels有明显区别，因为它们将二阶交叉矩阵分解成latent factors（或embedding vectors）（和MF很像），它能更有效地处理稀疏数据。通过只捕获不同embedding vectors pairs间的交叉，这可以极大减小二阶交叉的复杂度，生成线性的计算复杂度。

2.1.4 MLP(Multilayer Perceptrons)

同时，在机器学习上的最近许多成功都归因于deep learning。DL最基础的模型是：MLP。预测函数由一串交替的FC layers和activation function \(\sigma: R \rightarrow R\)组成：

\[\hat{y} = W_k \sigma(W_{k-1} \sigma(W_1 x + b_1) \cdots) + b_{k-1}) + b_k)\]

…(5)

其中：

  • \(W_l \in R^{n_l \times n_{l-1}}\)是weight matrix
  • \(b_l \in R^{n_l}\)：表示对于\(layer \ l=1,\cdots,k\)的bias

该方法被用于捕获更复杂的交叉。例如，给定足够参数，MLP会具有够深和够宽，可以拟合任意想预测的数据。这些方法的变种被广告用于CV和NLP中。例如：NCF被用于MLPerf benchmark的一部分，它使用MLP，而非dot product来计算MF中embeddings间的交叉。

2.2 DLRM架构

我们已经描述了在RS中不同的模型。我们将这些想法进行组合来构建SOTA的个性化模型。

假设用户和商品通过许多连续型特征（continuous features）和类别型特征（categorical features）进行描述。

  • 为了处理categorical features，每个categorical feature可以通过一个相同维度的embedding vector表示，即MF中latent factors。
  • 为了处理continous features，会通过一个MLP来进行转换，它会生成和embedding vectors相同长度的dense representation。

我们将根据FMs提供的处理sparse data的方式，将它们传给MLPs，显式地(explicitly)计算不同特征间的二阶交叉（second-order interaction）。这可以通过使用所有embedding vectors的pairs和dense features间的dot product来做到。用这些dot products可以使另一个MLP(top 或 output MLP)将original-processed dense features和post-processed一起concatenated，接着被feed到一个sigmoid function来提供一个概率。

我们将产生的模型称为：DLRM。如图1所示，并在表1中展示了PyTorch和Caffe2的DLRM所用到的一些operators。

表1

2.3 与之前的模型比较

许多deep learning-based的推荐模型，使用相似的底层思想来生成高阶项来处理sparse features。Wide&Deep, Deep&Cross, DeepFM, xDeepFM网络，例如，设计专有网络来有系统的构建高阶交叉。这些网络接着将来自这些专有模型和MLP的结果进行求和（sum），将它传给一个linear layer及sigmoid activation来生成一个最终概率。DLRM以一种结构化的方式与embeddings交互，通过只考虑由final MLP中embeddings pairs间的dot-product生成的cross-terms，模拟了FM对模型进行极大地降维。对于在其它网络的二阶交叉外的更高阶交叉，使用额外的计算/内存开销并不值。

DLRM和其它网络之间的一个关键不同点是：这些网络是如何对待embedded feature vectors和它们的cross-terms的。DLRM(以及XDeepFM)会将每个feature vector看成单个unit来表示单个category，其它像DCN(Deep&Cross)网络会将feature vector中的每个element看成是一个新的unit，这会生成不同的cross-terms。因此，Deep&Cross网络不仅会生成不同feature vectors的elements间的cross-terms（这和DLRM通过dot product方式一样），也会生成在相同feature vector的elements间的cross-terms，从而生成更高的维度。

3.并行化（Parallelism）

模型个性化和推荐系统，需要大且复杂的模型来估计大量数据上的价值。DLRMs特别包含了许多数目的参数，多阶的幅度要超过其它常见的deep learning模型（比如：CNN），transformer、RNN、GAN。这会导致训练时间上常达数周或更久。因此，对这些模型进行高效并行化，以便解决在实际规模中的问题。

如前面章节所示，DLRMs会以成对（coupled）的方式，同时处理categorical features（使用embeddings）以及continuous features（使用bottom MLP）。Embeddings会占据参数的大部分，一些tables每个都需要超过多个GBs的内存，使得DLRM对内存容量和带宽很敏感。embeddings的size使得它禁止使用数据并行化（data parallelism），因为它需要在每个设备上复制很大的embeddings。在许多cases中，这种内存限制需要模型分布跨多个设备，以便能满足内存容量需求。

在另一方面，MLP参数在内存上是更小的，但需要大量计算。因此，data-parallelism对MLPs更好，因为它可以让不同devices上的samples并发处理，只需要在当累积更新（accumulating updates）时需要通信。我们的并行化DLRM会使用一个embeddings的模型并行化(model parallelism)以及MLPs的数据并行化(data parallelism)的组合，来减缓由embeddings生成的内存瓶颈，而MLPs上的forward和backward propagations并行化。通过将model和data parallelism进行组合，是DLRM的唯一需求，因为它的架构和大模型size所导致；这样的组合并行化在Caffe2或PyTroch中并不支持（以及其它流行的DL框架），因此，我们设计了一种定制实现。我们计划在将来提供它的详细效果研究。

在我们的setup中，top MLP和interaction operator需要访问部分来自bottom MLP的mini-batch以及和所有embeddings。由于模型并行化已经被用于跨devices分布embeddings，这需要一个个性化的all-to-all通信。在embedding lookup的尾部，对于在mini-batch中的所有samples（必须根据mini-batch维度进行分割、以及与相应devieces进行通信）、对于在这些devices上的embedding tables，每个device都具有一个vector，如图2所示。Pytorch或Caffe2都不会提供model parallelism的原生支持；因此，我们通过显式将embedding operators（PyTorch的nn.EmbeddingBag, Caffe2的SparseLengthSum）映射到不同devices上来实现它。个性化的all-to-allcwpwy使用butterfly shuffle operator来实现，它可以将生成的embedding vectors进行切片（slices），并将它们转移到目标设备（target devices）上。在当前版本，这些transfers是显式的copies，但我们希望后续使用提供的通信原语（比如：all-gather以及send-recv）进一步optimize。

我们注意到，对于数据并行化MLPs，在backward pass中的参数更新会使用一个allreduce进行累积（accumulated），并以一种同步方式将它用在每个device的参数复制上，确保在每个device上的参数更新在每轮迭代上是一致的。在Pytorch中，data parallelism可以通过nn.DistributedDataParallel和nn.DataParallel模块来开启，将在每个device上的model复制，使用必要的依赖插入allreduce。在Caffe2中，我们会在梯度更新前手工插入allreduce。

4.数据

为了measure模型的acuracy，并测试它的整体效果，并将单独operators特征化，我们需要为我们的实现创建或获得一个dataset。我们模型的当前实现支持三种类型的datasets：random、synthetic、public datasets。

前两个dataset对于从系统角度实验我们的模型很有用。特别的，它允许我们通过生成即时数据，并移除数据存储依赖，来测试不同的硬件属性及瓶颈。后一个dataset允许我们执行真实数据的实验，并measure模型的accuracy。

4.1 Random

回顾DLRM，它接收continuous和categorical features作为inputs。前者可以通过生成一个随机数目的vector，通过使用一个uniform/normal(Gaussian)分布（numpy.random rand/randm缺省参数）。接着通过生成一个matrix来获得mini-batch inputs，其中每行对应在mini-batch中的一个element。

为了生成categorical features，我们需要决定在一个给定multi-hot vector中具有多少非零元素。benchmark允许该数字可以是fixed或在一个[1,k]的范围内random。接着，我们生成整型indices的相应数字，范围在[1,m]中，其中，m是在embedding W中的rows数目(2)。最后，为了创建一个mini-batch的lookups，我们将以上indices进行concatenate，并将每个单独的lookup使用lengths和offsets进行描述。

4.2 Synthetic

对应于categorical features，有许多理由支持定制索引的生成。例如，如果我们的应用使用一个特定dataset，但我们不希望出于私人目的共享它，那么我们可以选择通过distributions来表示categorical features。这可以潜在作为一种隐私保护技术的可选方法（用于联邦学习(federated learning)）。同时，如果我们希望练习系统组件（比如：学习内存行为）。。。

4.3 Public

参考

d0evi1 Reading time ~4 minutes

deepmind在19年发了篇关于feedback loops的paper：《Degenerate Feedback Loops in Recommender Systems》，我们可以来看下它的paper介绍：

摘要

在生产环境中的推荐系统大量使用机器学习。这些系统的决策会影响user beliefs和preferences，从而影响学习系统接受到的feedback——这会创建一个feedback loop。这个现象被称为“echo chambers”或“filter bubbles”。本paper提供了一个新的理论分析，来检查user dynamics的角色、以及推荐系统的行为，从而从filter bubble效应中解脱出来。另外，我们提供了实际解决方案来减小系统的退化（degeneracy）。

介绍

推荐系统广泛被用于提供个性化商品和信息流。这些系统会采用user的个人特征以及过往行为来生成一个符合用户个人偏好的items list。虽然商业上很成功，但这样的系统会产生一个关于窄曝光（narrowing exposure）的自我增强的模式，从而影响用户兴趣，这样的问题称为“echo chamber”和“filte bubble”。大量研究都致力于对曝光给用户的items set上使用favor diversity来解决。然而，echo chamber和filter bubble效应的当前理解很有限，实验分析表明会有冲突结果。

在本paper中，我们将echo chamber定义为这样的效应：通过重复曝光一个特定item或item类目，一个用户的兴趣被正向地（positively reinforced）、或负向地（negatively）增强。这是Sunstein(2009)的定义概括，其中，该术语通常指的是：对相似政治意见的over-exposure和limited-exposure，会增强个人的已存在信念（beliefs）。Pariser(2011)引入了filter bubble的定义，来描述推荐系统会选择有限内容来服务用户。我们提供了一个理论方法来允许我们单独考虑echo chamber和filter bubble效应。我们将用户兴趣看成是一个动态系统（dynamical system），并将兴趣看成是系统的退化点（degeneracy points）。我们考虑不同模型的动态性，并确定系统随时间degenerate的充分条件集合。我们接着使用该分析来理解推荐系统所扮演的角色。最终我们展示了：在一个使用模拟数据和多个经典bandit算法的仿真学习中，在user dynamics和推荐系统actions间的相互作用。结果表明，推荐系统设计的许多缺陷（pitfalls）和缓和策略。

相关工作

。。。

3.模型

我们考虑一个推荐系统，它会与用户随时间一直交互。在每个timestep t上，recommender系统会从一个有限的item set M中提供l个items给一个user。总之，该系统的目标是：将可能感兴趣的items呈现（present）给用户。我们假设：

  • 在timestep t上，user在一个item $a \in M$上的兴趣，可以通过函数\(\mu_t: M \rightarrow R\)来描述。
  • 如果用户对该item很感兴趣，那么\(\mu_t(a)\)很大（positive）；反之为很小（negative）

给定一个推荐(recommendation) \(a_t = (a_t^1, \cdots, a_t^l) \in M^l\)，用户基于它当前的兴趣 \(\mu_t(a_t^1), \cdots, \mu_t(a_t^l)\)提供一些feedback \(c_t\)。该交互具有多个effects：在推荐系统传统文献中，feedback \(c_t\)被用于更新用于获取推荐\(a_t\)推荐系统的internal model \(\theta_t\)，接着新模型\(\theta_{t+1}\)会依赖\(\theta_t, a_t, c_t\)。实际上，\(\theta_t\)通常会预测user feedback的分布来决定哪个items \(a_t\)应被呈现给该用户。在本paper中，我们关注另一个效应（effect），并显式考虑用户与推荐系统的交互可能会在下一次交互时以不同的items来变更他的兴趣，这样，该兴趣\(\mu_{t+1}\)会依赖于\(\mu_t, a_t, c_t\)。交互的完整模型如图1所示。

图片名称

图1

我们对用户兴趣的演化研究很感兴趣。这样的一个演化示例是，兴趣会通过用户与所推荐items的交互进行增强，也就是说：

  • 如果用户在timestep t上对一个item a进行点击，那么\(\mu_{t+1}(a) > \mu_t(a)\)；
  • 如果a被展示但未被点击，则\(\mu_{t+1}(a) < \mu_t(a)\). （这里, \(c_t \in \lbrace 0, 1 \rbrace^l\)可以被定义成所对应items的关于点击的indicator vector）

为了分析echo chamber或filter bubble效应，我们对于用户兴趣在什么时候发生非常剧烈变化非常感兴趣。在我们的模型中，这会转成\(\mu_t(a)\)采用任意不同于初始兴趣\(\mu_0(a)\)的值：大的positive values表示用户会对item a变得非常感兴趣，而大的negative values表示用户不喜欢a。正式的，对于一个有限item set M，我们会问到：L2-norm \(\| \mu_t - \mu_0 \|_2 = (\sum_{a \in M} (\mu_t(a) - \mu_0(a))^2)^{1/2}\)是否可以变得任意大？如果满足下面条件，几乎必然用户的兴趣序列\(\mu_t\)被称为“弱退化（weakly degenerate）”(证明见附录)：

\[\underset{t \rightarrow \infty} {lim} sup || \mu_t - \mu_0 ||_2 = \infty,\]

…(1)

关于degenracy的”stronger”概念，需要满足：一旦\(\mu_t\)远离\(\mu_0\)，它就是个stronger degeneracy。序列\(\mu_t\)是一个较强的degenrate，（ almost surely）需满足：

\[\underset{t \rightarrow \infty} {lim} || \mu_t - \mu_0 ||_2 = \infty\]

…(2)

下一节中，我们将展示，在\(\mu_t\)的动态演进上的充分条件较缓和时，degeracy发生的强弱。

对于一个无限item set M的情况，存在多种方式来扩展上述定义。出于简化，我们只考虑使用\(\| \mu_t - \mu_0 \|_2\)来替代等式(1)和等式(2)中的\(sup_{a \in M} \mid \mu_t(a) - \mu_0(a) \mid\)，当M是有限时，它等于原始定义。

3. 用户兴趣动态性——Echo Chamber

由于items通常以多样的类目(t diverse categorie)的方式呈现，我们简化猜想：它们间是相互独立的。通过对于所有t (例如：\(M = \lbrace a \rbrace\))，设置\(l=1\)和\(a_t^1 = a\)，我们可以移除推荐系统的影响，并单独考虑用户的动态性( Dynamics)。这使得我们分析echo chamber effect：如果item a被无限次推到，兴趣 \(\mu_t(a)\)会发生什么？

由于a是固定的，为了简化概念，我们将\(\mu_t(a)\)替换成\(\mu_t\)。给定\(a_t\)，根据图1，\(\mu_{t+1}\)是一个关于\(\mu_t\)的函数（可能随机，由于\(\mu_{t+1}\)依赖于\(c_t\)和\(\mu_t\)，\(c_t\)依赖于\(\mu_t\)）。我们考虑当漂移量（drift） \(\mu_{t+1} - \mu_t\)是一个非线性随机函数时的通用case；对于drift的deterministic模型在附录B中。

非线性随机模型（Nonlinear Stochastic Model）

\[\mu_{t+1} = \mu_t + f(\mu_t, \xi_t)\]

其中：

  • 我们假设\(\mu_0 \in R\)是固定的
  • \((\xi_t)_{t=1}^{\infty}\)是一个关于独立均匀分布的随机变量的无限序列，它引入噪声到系统中（例如：\(\mu_{t+1}\)是一个\(\mu_t\)的随机函数）
  • 函数 \(f: R \times [0, 1]\)是假设是可测的，但其它任意。通过\(U([0, 1])\)来定义[0,1]上的均匀分布，假设：
\[\bar{f}(\mu) = E_{\xi \sim U([0,1])} [f(\mu, \xi)]\]

是当\(\mu_t = \mu\)的期望增量\(\mu_{t+1} - \mu_t\)。我们也定义了：

\[F(\mu, x) = P_{\xi \sim U([0,1])} (f(\mu, \xi) \leq x)\]

是increment的累积分布。\(\mu_t\)的渐近行为依赖于f，但在mild假设下，系统会微弱（定理1）／较强（定理2）退化。

定理1（弱退化weak degeneracy）。假设F对于所有\(\mu \in R\)在\((\mu, 0)\)上是连续的，存在一个\(\mu_o \in R\)，使得：

  • 1) 对于所有\(\mu \geq \mu_o\)，有\(F(\mu, 0) < 1\)
  • 2) 对于所有\(\mu \geq \mu_o\)，有\(F(\mu, 0) > 0\)

那么序列\(\mu_t\)是weakly degenerate，比如：\(\underset{t \rightarrow \infty}{lim} sup \mid \mu_t \mid = \infty\)

该假设保证了在任意闭区间内，存在一个常数概率，当分别从\(\mu_o\)的左侧/右侧开始时，该random walk会逃离区间左侧/右侧。在stronger condition下，可以保证random walk的分散性（divergence）。

定理2 (强退化: strong degeneracy)

假设定理1恒定，另外存在\(c \in R\)使得 \(\| \mu_{t+1} - \mu_t \| \leq c\)，存在一个\(\epsilon > 0\)，使得对于所有足够大的\(\mu\)，有\(f(\mu) > \epsilon\)，对于所有足够小的\(\mu\)有\(f(\mu) \leq - \epsilon\)。接着，\(limit_{t \rightarrow \infty} \mu_t = \infty\)或者\(limit_{t \rightarrow \infty} \mu_t = -\infty\)。

直觉上，如果用户兴趣具有一些关于drift的非零概率，weak degeneracy在一个随机环境中发生。而strong degeneracy会持有额外的\(\mu_{t+1} - \mu_t\)被限制，对于\(\mu_t\)足够大/小，而增量\(\mu_{t+1} - \mu_t\)具有positive/negative drift，它大于一个constant。

定理1和2表明，用户兴趣会在非常温和的条件下退化（degenerate），特别的是在我们的模似实验中。在这样的cases中，如果一个item（或一个item category）是被展示有限多次时，degeneracy可以被避免，否则你只能寄希望于控制\(\mu_t\)退化的有多快了（例如：趋向于\(\infty\)）。

4.系统设计角色——filter bubble

在之前的部分讨论了对于不同user interest dynamics的degeneracy的条件。在本节中，会检查另一面：推荐系统动作对于创建filter bubbles上的影响。我们通常不知道现实世界用户兴趣的动态性。然而，我们考虑echo chamber/filter bubble的相关场景：其中在一些items上的用户兴趣具有退化动态性(degenerative dynamics)，并检查了如何设计一个推荐系统来减缓degeneracy过程。我们会考虑三个维度：model accuracy，曝光量（exploration amount），growing candidate pool。

4.1 Model accuracy

推荐系统设计者的一个常见目标是，增加internal model \(\theta_t\)的预测accuracy。然而，模型accuracy如何与greedy optimal \(a_t\)组合一起来影响degeneration的速度？对于exact predictions的极端示例，例如：\(\theta_t = \mu_t\)，我们会将这样的预测模型为“oracle model”。我们会在前提假设法（surfacing assumption）下讨论，oracle模型与greedily optimal action selection组合来生成快速的degeneracy。

为了具体分析该问题，对于\(\mu_t(a)\)的\(a \in M\)，我们会关注degenerate线性动态模型，例如：\(\mu_{t+1}(a) = (1+k) \mu_t(a) + b\)。接着，我们可以为\(\mu_t(a)\)求解，对于\(\mid 1+k(a) \mid > 1\)来获得：

\[\mu_t(a) = (\mu_0(a) + \frac{b(a)}{k(a)} (1 + k(a))^t - \frac{b(a)}{k(a)}\]

Sufacing Assuption:

假设\([m] = \lbrace 1,2, \cdots, m \rbrace\)是size=m的candidate set。如果一个items子集 \(S \subset [m]\)会产生positive degenerate （例如，对于所有\(a \in S\), \(\mu_t(a) \rightarrow +\infty\)），那么我们假设：存在一个时间\(\tau > 0\)，对于所有\(t \geq \tau\)，S会占据根据\(\mu_t\)值生成的top \(\mid S \mid\)的items。该\(\mu_t\)由指数函数 \(\mid 1 + k(a) \mid\)的base value进行排序。

如果给定足够的曝光（exposure）时间，surfacing assumption可以确保很快地将items surface退化到top list上。它可以被泛化到关于\(\mu_t\)的非线性随机动态性上，从而提供：来自S的items具有一个稳定的随时间退化速度\(\mid \mu_t(a) - \mu_0(a) \mid /t\)的排序。

在通用的surfacing assumption下，在时间\(\tau\)之后，退化（degeneration）的最快方式是：根据\(\mu_t\)或oracle model的\(\theta_t\)来服务top l items。即使该assuption有一定程度的冲突，oracle model仍会产生非常高效的退化（degeneracy），通过根据\(\mu_t\)来选择top l items，由于较高的\(\mu_t\)，他不会接受到positive feedback，从而增加\(\mu_{t+1}\)、并增强过往选择。

实际上，推荐系统模型是不准确的（inaccurate）。我们可以将inaccurate models看成是具有不同级别的noises(添加到\(\theta_t\))的oracle model。

4.2 探索量（Amount of Exploration）

考虑一种\(\epsilon\)-random exploration，其中\(a_t\)总是从一个有限candidate pool [m]中（它在\(\theta_t\)上具有一个uniform \(\epsilon\) noise），根据\(\theta_t^{'} = \theta_t + U([-\epsilon, \epsilon])\)，选择出top l items。

给定相同的模型序列\(\theta_t\)，\(\epsilon\)越大，系统退化（degenerate）越慢。然而，实际上，\(\theta_t\)从observations上学到，在一个oracle model上添加的random expoloration可能会加速退化（degeneration）：random exploration可以随时间展示最正向的degenerating items，使得suracing assumption更可能为true（在图5中，我们在仿真实验中展示了该现象）。另外，如果user interests具有degenerative dynamics，随机均匀推荐items会导致degeration，虽然相当慢。

接着我们如何确保推荐系统不会使得user interests退化（degenerate）？一种方法是，限制一个item服务给user的次数（times）， 越多次会使得用户兴趣动态性退化。实际上，很难检测哪个items与dynamics退化相关，然而，如果所有items都只服务一个有限次数，这通常会阻止degeneration，这也暗示着需要一个不断增长的candidate items池子。

4.3 Growing Candidate Pool M

有了一个不断增长的（growing） candidate pool，在每个timestep时，会有一个关于new items的额外集合可提供给该user。从而，function \(\mu_t\)的domain会随时间t的增加而扩展（expands）。线性增加新items通常是一个避免退化的必要条件，因为在一个有限/任意次线性（sublinearly）增长的candidate pool上，通过鸽巢原理(pigeon hole principle)，必须存在至少一个item，在最坏情况下它会退化（degenerate）（在定理2描述的通用条件下）。然而，有了一个至少线性增长的candidate pool M，系统会潜在利用任意item的最大服务次数来阻止degeneration。

5.模拟实验

本节考虑一个\(\mu_t\)简单的degenerative dynamics，并检查在5个不同的推荐系统模型中的degeneration速度。我们进一步演示了，增加new items到candidate pool中会有一个对抗system degeneracy的有效解法。

我们为图1中一个推荐系统和一个用户间的交互创建了一个simulation。初始size=\(m_0\)，在timestep t上的size=\(m_t\)。在timestep t时，一个推荐系统会从\(m_t\)个items中，根据内部模型\(\theta_t\)来选择top l 个items \(a_t = (a_t^1, \cdots, a_t^l)\)服务给一个user。

该user会独立考虑l items的每一个，并选择点击一个子集（也可能不点击，为空），从而生成一个size=l的binary vector \(c_t\)，其中\(c_t(a_t^i)\)会给出在item \(a_t^i\)上的user feedback，根据\(c_t(a_t^i) \sim Bernoulli(\phi(\mu_t(a_t^i)))\)，其中\(\phi\)是sigmoid function \(\phi(x) = 1/(1 + e^{-x})\)。

接着该系统会基于过往行为（past actions）、feedbacks和当前模型参数\(\theta_t\)来更新模型\(\theta_{t+1}\)。我们假设，用户兴趣通过\(\theta(a')\)增加/减少，如果item \(a'\)会收到/未收到一个点击，例如：

\[\mu_{t+1}(a_t^i) - \mu_t(a_t^i) = \begin{cases} \delta(a_t^i) & \text{if $ c_t(a_t^i) = 1 $ } \\ -\delta(a_t^i) & \text{otherwise} \end{cases}\]

…(3)

其中，function \(\delta\)会从candidate set映射到R上。从定理2中，我们知道对于所有item，有\(\mu_t \rightarrow \pm \infty\)。在该实验中，我们设置l=5,并从一个均匀随机分布\(U([-0.01, 0.01])\)中抽样drift \(\delta\)。对于所有items，用户的初始兴趣\(\mu_0\)是独立的，它们从一个均匀随机分布U([-1,1])中抽样得到。

内部推荐系统模型根据以下5个算法更新：

  • Random model
  • Oracle：
  • UCB Multi-armed bandit
  • Thompson Multi-armed bandit

6.1 Echo Chamber & Filter Bubble effect

我们通过在一个fixed size \(m_t = m = 100\)、time horizon T=5000的candidate pool上运行仿真，来检查echo chamber和filter bubble效应。

在图2中，我们展示了user interest \(\mu_t\)（左列）的degenreation、以及每个item的serving rate（右列），因为每个推荐模型会随时间演化。一个item的serving rate展示了在report interval内服务的频次。为了清楚地观察该分布，我们根据report time上的z-values对items进行排序。尽管所有模型会造成user interest degeneration，degeneration的speeds相当不同（Optimal Oracle > Oracle, TS, UCB > Random Model）。Oracle, TS 和 UCB是基于\(\mu_t\)优化的，因此我们可以看到对于\(\mu_t\)有一个positive的degenerative dynamics。Optimal Oracle会直接在degeneration speed上进行优化，而不会在\(\mu_t\)上，因此我们可以看到在\(\mu_t\)上同时有一个positive和negative degeneration。Random Model也会在两个方向上对\(\mu_t\)进行drifts，但以一个更慢的rate。然而，除了Random Model外，在所服务的top items上和top user interests会非常快速地收窄降到\(l=5\)的最positive的reinfofced items上。

图片名称

图2

Degenracy Speed

接着，我们在fixed和growing的两种candidate sets上，为5个推荐系统模型比较了degeneracy speed。由于测量系统degeneracy的L2矩离对于所有五种模型来说是线性对称的，我们可以在有限candidate pools上，对于不同的实验设定比较\(\mid \mu_t - \mu_0 \mid_2 /t\)。

图片名称

图3 5000个time steps上的系统演进，其中在report interval为500。结果是在30次运行上的平均，共享区域表示标准差。在degeneracy speed上，Optimal Oracle > Oracle > TS > UCB > Random

图3展示了5种模型的degeneracy speed，。。。。我们可以看到，Optimal Oracle会产生最快的degnereation，接着是：Oracle, TS，UCB。Random Model最慢。

Candidate Pool Size

在图4a中，我们比较了Optimal Oracle、UCB、TS的degenreacy speed \(\|\| \mu_t - \mu_0 \|\|_2 /t\)，直到5000 time steps，candidate pool sizes \(m=10, 10^2, 10^3, 10^4\)。除了random model，在给定一个大的candidate pool下，我们可以看到UCB会减慢degeneracy最多，因为它会首先强制探索任意unserved item。对于bandit算法，一个越大的candidate pool对于exploration需要一个更长时间。在给定time horizon下，由于candidate pool size增长到10000 UCB的dengeracy speed，从未达到峰值，但事实上会在给定一个更长时间上增长。TS具有越高的degereracy speed，因为在new items上具有更弱的exploration。Optimal Oracle 在给定一个更大pool上加速degeneration，因为比起一个更小的pool，它会潜在选择具有更快degenerative的items。

图片名称

图4

另外，在图4b中，我们画出了所有5个模型的degeneracy speed，对于T=20000, 对比candidate pool sizes的相同变化。Optimal Oracle 和Oracle的degeneracy speed会随着candidate set的size增长。实际上，具有一个大的candidate pool可以是一个临时解法(temporary solution)来降低系统degeneration。

Noise Level的效应

接着我们展示了internal model inaccuracy在degeneracy speed上的影响。我们对比使用不同均匀随机噪声量的Oracle model，例如：系统根据noisy internal model \(\theta_t^{'} = \theta_t + U([-\epsilon, \epsilon])\)来对外服务top l items。candidate pool具有fixed size \(m=100\)。在图5中，我们从0到10来区分\(\epsilon\)。与直觉相反的是（ Counter-intuitively），添加噪声到Oracle中会加速degeneration，因为对比起由\(\mu_0\)排序的top l items的fixed set，添加噪声会使得具有更快degenerative的items会被偶然选中，更可能满足Surfacing Assumption。给定\(\epsilon > 0\)，我们可以看到，随着noise level的增长，在degeneracy speed上具有一个单调递增的阻尼效应（damping effect）。

图片名称

图5 在Oracle model上具有不同noise levels \(\epsilon \in [0, 10]\)的degeneracy speed，直到T=20000. 在Oracle中添加noise会加速degeneration，但随着noise level的增长，degneracy会缓下来

Growing Candidate Pool

我们通过计算\(sup_{a \in M} \mid \mu_t(a) - \mu_0(a)\mid /t\)，将degeneracy speed的定义扩展到一个有限的candidate pool上。由于degeneracy speed对于所有5种模型不是渐近线性的（asymptotically linear），我们会在10000个time steps上直接检查sup distance \(sup_{a \in M} \mid \mu_t(a) - \mu_0(a) \mid\)。为了构建在不同growth speed上的growing candidate pools，我们定义了一个增长函数\(m_t = \lfloor m_0 + l t^{\eta}\rfloor\)，通过不同增长参数\(\eta = 0, 0.5, 1, m_0 = 100\)定义。在图6中，我们在10个独立运行上对结果进行平均。对于所有growth rates，Oracle和Optimal Oracle都是degenerate的。Random Model会在sublinear growth \(\eta=0.5\)上停止degeneration，UCB也如此，这归因于之前unserved items上进行强制exploration，尽管它的trajectory具有一个小的上翘（upward tilt）。TS模型会在sublinear growth上degenerates，但在linear growth \(\eta=1\)上停止degernation。对于所有模型，growth rate \(\eta\)越高，他们degerate会越慢，如果他们完全这样做的话。当全部可用时，线性growing candidate set和continuous random exploration看起来是一个不错的方法，来对抗\(\mu_t\)的dynamics来阻止degeneracy。

图片名称

图6 5个模型的比较，它们使用growing candidate pools，具有不同的rates \(\eta = 0, 0.5, 1.0\)，degeneracy直到T=10000, 在10个运行结果上平均得到。对于所有growth rates，Oracle和Optimal Oracle都是degenerate的。Random Model和UCB会在sublinear growth上停止generation，而TS model需要linear growth才会停止degeneration。

参考

d0evi1 Reading time ~1 minute

在《The Impact of Popularity Bias on Fairness and Calibration in Recommendation》paper中，提出了polularity bias与miscalibration之间具有一定的关联：

摘要

最近，在fairness-aware的推荐系统上收获了许多关注，包括：在不同users或groups上提供一致performance的fairness。如果推荐不能公平地表示某一个确定user group的品味，而其它user groups则与他们的偏好一致时，则一个推荐系统可以被认为是unfair的。另外，我们使用一个被称为“miscalibration”的指标来measure一个推荐算法响应用户的真实偏好程度，我们会考虑多个算法在miscalibration上的不同程度。在推荐上一个知名类型的bias是polularity bias，在推荐中有少量流行items被过度呈现（over-represented），而其它items的majority不会获得大量曝光。我们推测，popularity bias是导致在推荐中的miscalibration的一个重要因素。我们的实验结果使用两个真实数据集，展示了不同user groups间algorithmic polularity bias和他们在popular items上的兴趣程度的强相关性。另外，我们展示了，一个group受algorithmic polularity bias的影响越多，他们的推荐是miscalibrated也越多。最后，我们展示了具有更大popularity bias趋势的算法会具有更大的miscalibration。

1.介绍

在推荐生成中近期关注的一个热点是：fairness。推荐的fairness在推荐的不同domain、不同users或user groups的特性（比如：protected vs. unprotected）、以及系统设计者的目标下具有不同的含义。例如，[12]中将fairness定义成不同user groups间accuracy一致性。在他们的实验中，观察到，特定groups（比如：女性）会比男性获得更低的accuracy结果。

用来衡量推荐质量的一个metrics是：calibration，它可以衡量推荐分发与用户评分过的items的一致性。例如，如果一个用户对70%的action movies以及30%的romance movies评过分，那么，该用户在推荐中也期望看到相似的pattern[27]。如果该ratio与用户profile不同，我们则称推荐是miscalibrated。Miscalibration自身不能被当成unfair，因为它只能简单意味着推荐不够个性化。然而，如果不同的users或user groups在它们的推荐中都具有不同程度的miscalibration，这可能意味着一个user group的unfair treatment。例如，[28]中定义了一些fairness metrics，它关注于不同user groups间estimation error的一致性效果。

协同推荐系统的一个显著限制是popularity bias：popular items会被高频推荐，在一些cases中，推荐甚至超过它们的popularity，而大多数其它items不能获得合适比例的关注。我们将algorithmic popularity bias定义成：一个算法扩大了在不同items上已存在的popularity差异。我们通过popularity lift指标来measure该增强效应（amplification），它表示在input和output间平均item polularity的差异。比如，关于popularity bias可能会有疑惑，可能有以下原因：long-tail items（non-popular）对于生成一个用户偏好的完整理解来说很重要。另外，long-tail推荐也可以被理解成是一个社会福利（social good）；存在popularity bias的market会缺乏机会来发现更多obscure的产品，从而被大量大品牌和知名artists占据。这样的market会越来越同质化（homogeneous），为创新提供更少的机会。

在本paper中，我们推荐：popularity bias是导致推荐列表miscalibration的一个重要因素。

。。。

2.相关工作

3.Popularity bias和miscalibration

3.1 Miscalibration

miscalibration用来measure用户真实偏好与推荐算法间差异程度。前面提到，如果在所有用户上都存在miscalibration，可能意味着个性化算法的failure。当不同user groups具有不同程度的miscalibration时，意味着对特特定user groups存在unfair treatment。

。。。

为了measure 推荐的miscalibration，我们使用[27]中的metric。假设u是一个user，i是一个item。对于每个item i，存在一个features集合C来描述它。例如，一首歌可能是pop、jazz，或一个电影的genres可以是action、romance、comedy等。我们使用c来表示这些独立categories之一。我们假设每个user会对一或多个items进行评分，这意味着会对属于这些items的features c感兴趣。对于每个user u的两个分布：一个是u评分过的所有items间的categories c的分布，另一个是u的所有推荐items间categories c的分布：

  • \(p_u(c \| u)\)：在过去用户u评分过的items集合\(\Gamma\)上的feature c的分布为：
\[p_u(c | u) = \frac{\sum\limits_{i \in \Gamma w_{u,i} p(c|i)}}{\sum\limits_{i \in \Gamma} w_{u,i}}\]

…(1)

其中\(w_{u,i}\)是item i的权重，表示user u评分的频率。本paper中可以将w设置为1. 更关注不同分布上的差异，而非user profile的时序方面.

  • \(q_u(c \| u)\)：推荐给user u的items list的feature c上的分布：
\[q_u(c|u) = \frac{\sum\limits_{i \in \wedge} w_r(i) p(c|i)}{ \sum\limits_{i \in \wedge} w_r(i)}\]

…(2)

\(\wedge\)表示推荐items集合。item i的weight则表示推荐中的rank r(i)。比如：MRR或nDCG。此外我们将\(w_r\)设置为1, 确保\(q_u\)和\(p_u\)可比。

在两个分布间的dissimilarity程度用来计算推荐中的miscalibration。常见的比方法有：统计假设检验。本文则使用KL散度来作为miscalibration metric。在我们的数据中，许多profiles没有ratings，这会导致在\(p_u\)上出现零值，同样具有推荐列表只关注特定features，对于一些users也在\(q_u\)上也会出现零值。对于没有observations的情况KL散度是undefined。作为替代，我们使用Hellinger distance H，它适用于存在许多0的情况。miscalibration的定义如下：

\[MC_u(p_u, q_u) = H(p_u, q_u) = \frac{|| \sqrt{p_u} - \sqrt{q_u}||_2}{\sqrt{2}}\]

…(3)

通过定义发现，H distance满足三角不等式。\(\sqrt{2}\)可以确保\(H(p_u, q_u) \leq 1\)。

对于每个group G的整体的miscalibration metric \(MC_G\)可以通过在group G中所有users u的\(MC_u(p,q)\)的平均来获得。例如：

\[MC_G(p, q) = \frac{\sum_{u \in G} MC_u(p_u, q_u)}{|G|}\]

….(4)

fairness

和[27]相似，本文将unfair定义为：对于不同user groups具有不同程度miscalibration时，则存在unfair。存在许多方式来定义一个user group，可以基于以下features：gender、age、occupation（职业）、education等。相似的，我们也可以基于它们的兴趣相似程度来定义user group。例如：对某些category上的兴趣度。

3.2 rating data中的Popularity Bias

推荐算法受popularity bias影响。也就是说，少量items会被推荐给多个users，而大多数其它items不会获得大量曝光。该bias可能是因为rating data的天然特性会倾向于popular items，因为该bias会存在algorithmic amplification。图1-b展示了两个user A和B的rated items的百分比。我们可以看到，user A的推荐被popularity bias高度影响，而user B在它们推荐中则不存在popularity bias的增强效应。

在许多领域，rating data会倾向于popular items——许多流行items会获得大量ratings，而其余items则具有更少的ratings。图2展示了item popularity的长尾分布。在其它datasets中也有相似的分布。流行的items之所以流行是有原因的，algorithmic popularity bias通常会将该bias放大到一个更大的程度。

并非每个用户都在流行items上具有不同程度的兴趣[4,22]。也会存在用户只能非流行、利基（niche）的items感兴趣。推荐算法也需解决这些用户的需求。图3展示了在不同user profiles上rated items的average popularity。用户首先会基于items的average popularity进行sort，接着绘出data。在movielens上，在图的最右侧和右侧，表示存在少量user，它们具有大量average item popularity，中间部分大量用户的分布具有0.1到0.15之间的average item popularity。在Yahoo Movies中，具有少量users具有low-popularity profiles，否则，distribution是相似的。这些图表明，用户在popular items上具有不同程度的偏向。

由于原始rating data上的imbalance，通常在许多情况下，算法会增强该bias，从而过度推出popular items，使得它们具有更大的机会被更多users进行评分。这样的推荐循环会导致rich-get-richer、poor-get-poorer的恶性循环。然而，并非每个推荐算法对popularity bias具有相同的放大能力（ampli€cation power）。下一部分描述了，测量推荐算法所传播的popularity bias的程度。经验上，会根据popularity bias增强来评估不同算法的performance。

4.方法

略.

参考

d0evi1 Reading time ~2 minutes

介绍

alibaba在《Personalized Re-ranking for Recommendation》介绍了一种reranking模型。

摘要

ranking是推荐系统的核心问题，通常，一个ranking函数会从labeled dataset中学到，并会为每个单独item产生一个ranking score。然而，它可能是次优的(sub-optimal)，因为scoring function被应用在每个独立item上，没有显式考虑item间的相互影响，以及用户偏好／意图间的不同。因此，这里提出了一种个性化的re-ranking模型。通过直接使用一个已经存在的ranking feature vectors，提出的re-ranking模型可以很轻易地部署成在任意ranking算法之后跟着的一个follow-up模块。它会通过采用一个transformer结构来对在推荐列表中的所有items信息进行有效编码，来直接优化整个推荐列表。特别的，transformer使用一种self-attention机制，它直接建模在整个list中任意items pair间的关系。我们证实，通过引入pre-trained embedding来为不同用户学习个性化编码函数。在offline和online的实验结果上均有较大提升。

1.介绍

通常，在推荐系统中的ranking不会考虑在list列表中其它items（特别是挨着的items）的影响。尽管pairwise和listwise l2r方法尝试解决该问题，但它们只关注充分利用labels（比如：click-through data）来优化loss function，并没有显式建模在feature space中items间的相互影响。

一些工作[1,34,37]尝试显式建模items间的相互影响，重新定义由之前ranking算法给出的intial list，这被称为“re-ranking”。构建该scoring function的主要思路是：将intra-item patterns编码成feature space。state-of-the-arts的方法有：RNN-based（比如：GlobalRerank[37]和DLCM[1]）。它们会将初始列表（intial list）按顺序feed给RNN-based结构，并在每个timestep上输出编码后的vector。然而，RNN-based方法对建模在list中items间的交叉的能力有限。之前编码的item的feature信息会沿着编码距离退化（degrade）。同时，由于并行化，transformer的编码过程比RNN-based方法更高效。

除了items间的交叉外，交叉的个性化编码函数可以被考虑用于re-ranking。对推荐系统进行re-ranking是user-specific的，决取于用户的偏好。对于一个对价格敏感的用户，在re-ranking模型中，对“price”特征间进行交叉更重要。常见的global encoding function可能不是最优的，因为它会忽略每个用户在特征分布间的不同。例如，当用户关注价格对比时，具有不同价格的相似items趋向于在list中更聚集。当用户没有明显的购买意图时，推荐列表中的items趋向于更分散。因此，我们在transformer结构中引入一种个性化模块来表示关于item interactions用户偏好和意图。在我们的个性化re-ranking模型中，可以同时捕获：在推荐列表中的items、以及用户间的交叉。

2.相关工作

我们的工作主要是，重新定义由base ranker给出的initial ranking list。在这些base rankers间，l2r是一种广泛使用的方法。l2r方法可以根据loss function分为三类：point-wise、pairwise、listwise。所有这些方法可以学习一个global scoring function，对于一个特定feature的权重会被全局学到。然而，这些features的weights应可以意识到：不仅items间的交叉、以及user和items间的交叉。

【1-3,37】的工作主要是re-ranking方法。它们使用整个intial list作为input，并以不同方式建模在items间的复杂依赖。[1]使用unidirectional GRU来将整个list的信息编码到每个item的表示。[37]使用LSTM、[3]使用pointer network，不仅编码整个list信息，也会由decoder生成ranked list。对于这些使用GRU or LSTM的方法来编码items间的依赖，encoder的能力通过encoding distance进行限制。在我们的paper中，我们使用transfomer-like encoder，它基于self-attention机制以O(1) distance来建模任意两个items间的交叉。另外，对于那些使用decoder来顺序生成ordered list的方法，它们不适合online ranking系统，因为需要有严格的延迟。由于sequential decoder使用在time t-1上选中的item作为input来在time t上选择item，它不能并列行，需要n倍的inferences，其中n是output list的长度。[2]提出了一种groupwise scoring function，它可以对scoring进行并列化，但它的计算开销很高，因为它会枚举在list中所有可能的item组合。

3.re-ranking模型

在本节中，我们首先给出了一些关于l2r以及re-ranking的先验知识。接着对问题公式化来求解。概念如表1所示。

表1:

l2r方法在ranking中被广泛使用，为推荐和信息检索生成一个ordered list。l2r方法会基于items的feature vector学习一个global scoring function。有了该global function，l2r方法会通过在candidate set中的每个item。该global function通常通过对以下loss L最小化得到：

\[L = \sum\limits_{r \in R} l( \lbrace y_i, P(y_i | x_i;\theta) | i \in I_r \rbrace )\]

…(1)

其中：

  • R是对于推荐所有用户请求的集合。
  • \(I_r\)是对于请求\(r \in R\)的items的candidate set
  • \(x_i\)表示的是item i的feature space
  • \(y_i\)是在item i上的label (例如：click or not)
  • \(P(y_i \mid x_i; \theta)\)是由ranking model给出的对于参数\(\theta\)的预测点击概率
  • l是通过\(y_i\)和\(P(y_i \mid x_i; \theta)\)计算得到的loss

然而，对于学习一个好的scoring function来说，\(x_i\)是不足够的。我们发现推荐系统的ranking应考虑以下额外信息：

  • (a)item-pairs间的相互影响 [8,35]
  • (b)users和items间的交叉(interactions)

在item-pairs间的相互影响，可以通过使用已经存在的LTR模型为请求r从inital list \(S_r=[i_1, i_2, \cdots, i_n]\)直接学到。[1][37][2][3]提出了方法来更好利用item-pairs间的相互信息。然而，很少研究去关注users和items间的interactions。item-pairs的相互影响，对于不同用户来说是不同的。在本paper中，我们引入了一种个性化矩阵(personlized matrix) PV来学习user-specific encoding function，它可以建模item-pairs间的个性化相互影响。模型的loss function可以被公式化成等式(2)。

\[L = \sum\limits_{r \in R} l( \lbrace y_i, P(y_i \mid X, PV; \hat{\theta}) | i \in S_r \rbrace )\]

…(2)

其中：

  • \(S_r\)是由之前ranking model给出的inital list
  • \(\hat{\theta}\)是我们的re-ranking model的参数
  • X是在list中所有items的feature matrix

4.个性化re-ranking模型

在本节中，我们首先给出了关于PRM(Personalized Re-ranking Model)的总览。接着详细介绍每一部分。

4.1 模型架构

PRM的结构如图1所示。模型包含三个部分：

  • input layer
  • encoding layer
  • output layer

它会将由之前的ranking模型生成的关于items的intial list作为input，并输出一个re-ranked list。详细结构分挨个介绍。

图片名称

4.2 Input Layer

input layer的目的是，为在initial list中的所有items准备representations，并将它feed给encoding layer。首先，我们具有一个固定长度的intial sequential list \(S=[i_1, i_2, \cdots, i_n]\)，它由之前的ranking方法给出。与之前ranking方法相同，我们具有一个raw feature matrix \(X \in R^{n \times d_{feature}}\)，在X中的每一行表示每个\(i \in S\)的item对应的raw feature vector \(x_i\)。

Personalized Vector(PV)

对两个items的feature vectors进行encoding，可以建模它们之间的相互影响，但这些影响进行扩展将会影响那些未知用户。因而需要学习user-specific encoding function。尽管整个intial list的representation可以部分影响用户的偏好，但对于一个强大的personlized encoding function来说它是不够的。如图1(b)所示，我们将raw feature matrix \(X \in R^{n \times d_{feature}}$与一个个性化矩阵\)PV \in R^{n \times d_{pv}}\(进行concat来获取中间（intermediate）的embedding matrix\)E’ \in R^{n \times (d_{feature} + d_{pv})}$$，如等式(3)。PV通过一个pre-trained model生成，它会在下一节中介绍。PV的performance增益可以由evaluation部分被介绍。

\[E' = \left[ \begin{array} x_{i_1}; pv_{i_1} \\ x_{i_2}; pv_{i_2} \\ \cdots \\ x_{i_n}; pv_{i_n} \end{array} \right]\]

…(3)

position embedding(PE)

为了利用在intial list中的顺序信息，我们将一个position embedding \(PE \in R^{n \times (d_{feature}+d_{pv})}\)注入到input embedding中。接着，该embedding矩阵可以用等式(4)计算。本paper中会使用一个可学习的PE，它的效果要比[28]中固定的position embedding要略微好些。

\[E'' = \left[ \begin{array} x_{i_1}; pv_{i_1} \\ x_{i_2}; pv_{i_2} \\ \cdots \\ x_{i_n}; pv_{i_n} \end{array} \right] + \left[ \begin{array} pe_{i_1} \\ pe_{i_2} \\ \cdots \\ pe_{i_n} \end{array} \right]\]

…(4)

最后，我们使用一个简单的feed-forward网络来将feature matrix \(E'' \in R^{n \times (d_{feature} + d_{pv}}\)转成\(E \in R^{n \times d}\)，其中：d是encoding layer中每个input vector中潜在维度(latent dimensionality)。E可以通过等式(5)公式化：

\[E = EW^E + b^E\]

…(5)

其中，\(W^E \in R^{(d_{feature} + d_{pv}) \times d}\)是投影矩阵，\(b^E\)是d维向量。

4.3 Encoding Layer

如图1(a)所示，encoding layer的目标是，将item-pairs间的相互影响、以及其它额外信息进行集成，这些额外信息包含：用户偏好、intial list S的ranking顺序。为了达到该目标，我们采用Transfomer-like encoder，因于Transformer已经在许多NLP任务中被证明是有效的，特别是在机器翻译中。Transformer中的self-attention机制特别适合我们的re-ranking任务，因为它可以直接建模任意两个items间的相互影响，忽略掉两者间的距离。没有了距离衰减(distance decay)，Transfomer可以捕获更多在intial list中离得较远的items间的交叉。如图1(b)所示，我们的encoding模块包含了\(N_x\)个关于Transformer encoder的块（blocks）。每个块（block）（如图1(a)所示）包含了一个attention layer和一个Feed-Forward Network(FFN) layer。

Attention Layer

attention函数如等式(6)所示：

\[Attention(Q,K,V) = softmax(\frac{QK^T}{\sqrt{d}})V\]

…(6)

其中矩阵Q, K, V各自表示queries、keys和values。d是matrix K的维度，为了避免内积的大值。softmax被用于将内积值转化成为value vector V添加权重。在我们的paper中，我们使用self-attention，其中：Q, K和V从相同的矩阵进行投影。

为了建模更复杂的相互影响，我们使用multi-head attention，如等式(7)所示：

\[S' = MH(E) = Concat(head_1, \cdots, head_h) W^O \\ head_i = Attention(EW^Q, EW^K, EW^V)\]

…(7)

其中，\(W^Q, W^K, W^V \in R^{d \times d}\)。\(W^O \in R^{hd \times d_{model}}\)是投影矩阵。h是headers的数目。h的不同值间的影响会在下一节被研究。

FFN(Feed-forward Network)

该position-wise FFN的函数主要是为了使用在input vectors不同维度间的非线性（non-linearity）和交叉（interacitons）来增强模型。

对Encoding Layer进行Stacking

这里，我们使用attention模块，后面跟着position-wise FFN作为一块(block)Transformer encoder。通过对多个blocks进行stacking，我们可以得到更复杂和高阶的相互信息（mutual information）。

4.4 Output Layer

output layer的函数主要为每个item \(i = i_1, \cdots, i_n\)生成一个score。（如图1(b)所示Score(i)）我们在softmax layer之后使用一个linear layer。softmax layer的output是每个item的点击概率，被标记为：\(P(y_i \mid X, PV; \hat{\theta})\)。我们使用\(P(y_i \mid X, PV, \hat{\theta})\)作为\(Score(i)\)来在one-step中对items进行re-rank。Score(i)的公式为：

\[Score(i) = P(y_i \mid X, PV; \hat{\theta}) = softmax(F^{(N_x)}W^F + b^F), i \in S_r\]

…(8)

其中：

  • \(F^{(N_x)}\)是Transformer encoder的\(N_x\)个blocks的output
  • \(W^F\)是可学习的投影矩阵
  • \(b^F\)是bias term
  • n是在intial list中的items数目

在训练过程中，我们使用click-through data作为label并最小化等式(9)的loss function：

\[L = - \sum\limits_{r \in R} \sum\limits_{i \in S_r} y_i log(P(y_i | X, PV; \hat{\theta})\]

…(9)

4.5 个性化模块

在本节中，我们会引入该方法来计算个性化矩阵PV，它表示user和items间的interactions。使用PRM来学习PV的最简单办法是，通过re-ranking loss以end-to-end的方式进行学习。在re-ranking任务中学到的task-specific representation缺少用户的一般偏好。因此，我们可以利用一个pre-trained NN来产生用户个性化embeddings PV，它接着被用做PRM模型的额外features。pre-trained NN可以从平台的所有click-through logs上学到。图1(c)展示了pre-trained模型的结构。sigmoid layer会输出：在给定所有行为历史\((H_u)\)和用户的side information时，关于item i、user u的点击概率\((P(y_i \mid H_u, u; \theta')\)。用户的side information包括：gender、age和purchasing level等。模型的loss通过一个point-wise cross-entropy函数来计算，如等式(10)所示：

\[L = \sum\limits_{i \in D} (y_i log( P(y_i | H_u, u; \theta')) + (1-y_i) log(1-P(y_i | H_u,u;\theta')\]

…(10)

其中：

  • D是user u在平台上展示的items set。
  • \(\theta'\)是pre-trained model的参数矩阵
  • \(y_i\)是item i的label

受[13]的启发，我们在sigmoid layer之前采用hidden vector作为personlized vector \(pv_i\)(如图1c所示)，feed到我们的PRM模型中。

图1c展示了pre-trained模型的可能架构，其它模型如：FM, FFM, DeepFM, DCN, FNN和PNN也可以做为生成PV的替代方法。

5.实验

参考