criteo也开放了它们的dpp方法:《Tensorized Determinantal Point Processes for Recommendation》, 我们来看下:

摘要

DPP在机器学习中的关注度越来越高,因为它可以在组合集合上提供一种优雅的参数化模型。特别的,在DPP中的所需的参数数目只与ground truth(例如:item catalog)的size成平方关系,而items的数目增长是指数式的。最近一些研究表明,DPPs对于商品推荐和(basket completion)任务 来说是很高效的模型,因为他们可以同时在一个集合中解释diversity和quality。我们提出了一种增强的DPP模型:tensorized DPP,它特别适合于basket completion任务。我们利用来自张量分解(tensor factorization)的思想,以便将模型进行定制用在next-item basket completion任务上,其中next item会在该模型的一个额外维度中被捕获。我们在多个真实数据集上评估了该模型,并找出:tensorized DPP在许多settings中,比许多SOTA模型提供了更好的predictive quality。

1.介绍

在averge shooping basket中items数的增加,对于在线零售商来说是一个主要关注点。该问题存在许多处理策略。而本工作主要关注于:算法会生成一个items集合,它们能适合补全用户的当前shopping basket。

Basket analysis和completion是机器学习中非常老的任务。许多年来,关联规则挖掘(association rule mining)是SOTA的。尽管该算法具有不同变种,主要的准则是涉及到:通过统计在过往observations中的共现,来计算购买一个额外商品的条件概率。由于计算开销和健壮性,现代方法更喜欢i2i CF,或者使用LR基于二分类购买得分来预测一个用户是否会构买一个item。

标准CF方法必须被扩展到能正确捕获商品间的diversity。在basket completion中,需要插入一定形式的diversity,因为推荐过于相似的items给用户并不好。实践者经常通过添加constraints到items推荐集合中来缓和该问题。例如,当使用类目信息时,在裤子被添加到basket时可以强制推荐相匹配的鞋子,而如果按天然的共同出售(co-sale) patterns会导致其它裤子的推荐。在这种情况中,diversity推荐的出现不会通过学习算法直接驱动,但可以通过side information和专家知识。Ref【28】提出了一种有效的Bayesian方法来学习类目的权重,当类目已知时。

然而,不依赖额外信息直接学习合适的diversity更令人关注。不使用side information,直接从数据中的diversity的naive learning,会得到一个高的计算开销,因为可能集合的数目会随类目中items数目而指数增长。该issue是no-trivial的,即使当我们只想往已存在集合中添加一个item时,而当我们想添加超过一个item来达到最终推荐set的diversity时会更难。

【9, 10】使用基于DPPs的模型来解决该组合问题。DPPs是一个来自量子物理学的优雅的关于排斥(repulsion)的概率模型,在机器学习上被广泛使用[17]。它允许抽样一个diverse的点集,相似度(similarity)和流行度(popularity)会使用一个称为“kernel”半正定矩阵进行编码。关于marginalization和conditioning DPPs有很多高效算法提供。从实用角度,学习DPP kernel是个挑战,因为相关的likelihood是non-convex的,从items的observed sets中学到它是NP-hard的。

对于basket completion问题,天然地会考虑:那些转化成售买的baskets的sets。在该setting中,DPP通过一个size为\(p \times p\)的kernel matrix进行参数化,其中p是catalog(item目录表)的size。因而,参数的数目会随着p的二次方进行增长,计算复杂度、预测、抽样会随着p的三次方增长。由于学习一个full-rank的DPP是很难的,[10]提出了通过对kernel限制到low rank来对DPP正则化(regularization)。该regularization会在不伤害预测效果下提升generalization,并可以提供更diversity的推荐。在许多settings中,预测质量也会被提升,使得DPP对于建模baskets问题是一个理想的工具。再者,对比起full-rank DPP,low-rank假设也提供了更好的runtime效果

另外,由于DPP的定义,正如在Model部分所描述的,low-rank假设对于kernel来说,意味着任意可能的baskets会比那些概率为0的选中rank要具有更好的items。该方法对于大的baskets来说不可能,一些其它DPP kernel的正则化可能更合适。另外,由于DPP kernel的对称性,可以建模有序(ordered corrections)。然而,这些被添加到shooping basket中的items的order会在basket completion任务中扮演重要角色。

主要贡献:

  • 在kernel上修改了constraints来支持大的baskets;也就是说,对于大于kernel rank的sets来说,我们会阻止返回概率0
  • 我们通过在DPP kernel的行列式上添加一个logistic function,来修改在所有baskets上的概率。我们将训练过程适配成处理这种非线性,并在许多real-world basket数据集上评估了我们的模型
  • 通过使用tensor factorization,我们提出了一种新方式来对在目录中的集合间的kernel进行正则化。该方法也会导致增强预测质量
  • 我们展示了这种新模型,称之为”tensorfized DPP”,允许我们可以捕获ordered basket completion。也就是说,我们可以利用该信息,忽略掉items被添加到basket的顺序,来提升预测质量

另外,我们展示了这些思想的组合来提升预测质量,tensorized DPP建模的效果要好于SOTA模型一大截。

2.相关工作

3.模型

DPPs最初用来建模具有排斥效应(replusive effect)的粒子间的分布。最近,在利用这种排斥行为上的兴趣,已经导致DPP在机器学习界受到大量关注。数学上,离散DPPs是在离散点集上的分布,在我们的case中,点就是items,模型会为观察到的给定items集合分配一个概率。假设I表示一个items集合,L是与DPP相关的kernel matrix(它的entries会在items间对polularity和similarity进行编码)。观察到的set I的概率与主子矩阵(principal submatrix)L的行列式成正比:\(I: P(I) \propto del L_I\)。因而,如果p表示在item catalog中的items数目,DPP是在\(2^p\)上的概率measure(),而它只包含了\(p^2\)的参数。kernel L会对items间的polularities和similarities进行编码,而对角条目\(L_{ii}\)表示item i的流行度,off-diagonal entry \(L_{ij} = L_{ji}\)表示item i和item j间的相似度。行列式从几何角度可以被看成是体积(volume),因此更diverse的sets趋向于具有更大的行列式。例如,选择items i和j的概率可以通过以下计算:

\[P[\lbrace i,j \rbrace] \propto \begin{vmatrix} L_{ii} & L_{ij} \\ L_{ji} & L_{jj} \\ \end{vmatrix} = L_{ii} L_{jj} - L_{ij}^2\]

…(1)

等式(1)中我们可以看到:如果i和j更相似,他们被抽样在一起的可能性越低。entries \(L_{ij}\)因此会决定kernel的排斥行为。例如,如果使用图片描述符来决定相似度,那么DPP会选择那些有区别的图片。另一方面,如果entries \(L_{ij}\)使用之前观察到的sets学到,比如:电商购物篮[10],那么,“similarity” \(L_{ij}\)会低些。由于共同购买的items可能具有某些diversity,DPPs对于建模包含购买items的baskets是一种天然选择。在搜索引擎场景、或者文档归纳应用中,kernel可以使用特征描述述 \(\phi_i \in R^D\)(例如:文本中的tf-idf)、以及一个关于每个item i的相关得分\(q_i \in R^+\),比如:\(L_{ij} = q_i \phi_i^T q_j\)(它会喜欢相关items (\(q_i\)值大),阻止相似items组成的lists)。

3.1 Logistic DPP

我们的目标是,寻找一个最可能一起购买的items集合。我们将该问题看成是一个分类问题,目标是预测:一个items的特定集合会生成一个转化(conversion),即:所有items都将被一起购买,这可以表示成\(Y \in \lbrace 0, 1 \rbrace\)。我们将class label Y建模成一个Bernoulli随机变量,它具有参数\(\phi(I)\),其中\(I\)是items集合,\(\phi\)是如下定义的函数:

\[p(y | I) = \phi(I)^y (1- \phi(I))^{1-y}\]

…(2)

我们使用一个DPP来建模函数\(\phi\)。

我们假设:存在一个隐空间,在该空间内diverse items很可能会被一起购买。与[10]相似,我们假设:在kernel matrix \(L \in R^{p \times p}\)上存在一个low-rank constraint,我们进行如下分解:

\[L = VV^T + D^2\]

…(3)

其中,\(V \in R^{p \times r}\)是一个隐矩阵,其中每个row vector i会编会item i的r个latent factors。D是一个对角阵(diagonal matrix),\(\|V_i \|\),表示每个item的intrinsic quality或popularity。在D上的平方指数确保了,我们总是具有一个合理的半正定kernel。我们接着定义:

\[\phi(I) \propto det(V_{I_{,:}} V_{I_{,:}}^T + D^2) \geq 0\]

注意,没有对角项,r的选择会限制observable set的cardinality,由于\(\mid I \mid > r\)暗示着当\(D \equiv 0\)时\(\phi(I)=0\)。使用该term会确保,任意set的后续概率都是正的,但对于基数(cardinality)高于r的sets,它的cross-effects会更低。我们也看到,具有相似latent vectors的items,对比起具有不同latent vectors的items,被抽到的可能性会更小,由于相似vectors会生成一个具有更小体积(volume)的超平行体(parallelotope)。为了对概率归一化,并鼓励vectors间的分离,我们会在\(\phi\)上使用一个logistic function:

\(\phi(I) = P(y = 1 | I) & \doteq 1 - exp(-w det L_I) \\ & \doteq \delta(w del L_I)\) …(5)

通常,logistic function的形式是:\(1/(1 + exp(-w det L_I))\)。然而,在我们的case中,行列式总是正的,因为L是半正定的,这会导致\(P(y=1 \mid I)\)总是大于0.5 。通过构建,我们的公式允许我们获得一个介于0和1之间的概率。最终,\(w \in R\)是一个scaling参数,可以通过cross-validation被选中,这确保了指数不会爆炸,因于对角参数会近似为1.

Learning。为了学习matrix V,我们确保了历史数据 \(\lbrace I_m, y_m \rbrace_{1 \leq m \leq M}\),其中,\(I_m\)是items集合,\(y_m\)是label set,如果该set购买则为1, 否则为0。该训练数据允许我们通过最大化数据的log似然来学习矩阵V和D。为了这样做,我们首先对所有y写出点击概率:

\[P(y | I) = \sigma(w det L_I)^y (1-\sigma(w det L_I))^{1-y}\]

…(6)

\(f(V,D)\)的log似然接着被写成:

\[f(V,D) = log \prod\limits_{m=1}^m P(y_m | I_m) - \frac{a_0}{2} \sum\limits_{i=1}^{p} a_i ( \| V_i \|^2 + \| D_i \|^2) \\ = \sum\limits_{m=1}^M log P(y_m | I_m) - \frac{a_0}{2} \sum\limits_{i=1}^{p} a_i ( \| V_i \|^2 + \| D_i \|^2)\]

根据[10],\(a_i\)是一个item正则权重,它与item流行度成反比。矩阵V和D可以使用SGA来最大化log似然进行学习。GA的一个step需要计算一个对称矩阵(\(L_i\),其中I是gradient step的相应item set)的行列式,它可以使用 optimized CW-like algorithm算法来达到,复杂度为:\(O(f^3)\)或\(O(f^{2.373})\),其中,f对应于在I中的items数目。用于学习所使用的最优化算法如算法1所示。

图片名称

算法1

3.3 Tensorized DPP

我们现在提出了对之前模型的一个修改版本,它更适合basket completion任务。为了这样做,对于basket completion场景,我们加强logistic DPP,其中我们对概率建模:用户将基于已经出现在shooping basket中的items来购买一个指定额外的item。我们使用一个tensor来表示它,目标是预测用户是否会基于basket来购买一个给定的candidate target item。该tensor的每个slice对应于一个candidate target item。在该setting中,对于在catalog p中的item (减去basket中已经存在的items),会存在越来越多的问题待解决。为每个待推荐的item学习一个kernel,每个item会与其它所有items相独立,在实际上是不可能的,会存在稀疏性问题。每个item只在baskets中的一小部分出现,因而每个kernel只会接受一小部分数据来学习。然而,所有items间并不完全相互独立。为了解决稀疏性问题,受RESCAL分解的启发,我们使用一个low-rank tensor。我们使用一个cubic tensor \(K \in R^{p \times p \times p }\),其中K的每个slice \(\tau\)(标为:\(K_{\tau}\))是candidate item (low-rank) kernel。通过假设:tensor K是low-rank的,我们可以实现在每个item间学到参数的共享,以如下等式所示:

\[K_{\tau} = V R_{\tau}^2 V^T + D^2\]

…(7)

其中,\(V \in R^{p \times r}\)是item latent factors,它对所有candidates items是共用的,\(R_{\tau} \in R^{r \times r}\)是一个candidate item指定的matrix,会建模每个candidate item间的latent components的交叉。为了对candidate items与已经在basket中的items间的自由度进行balance,我们进一步假设:\(R_{\tau}\)是一个对角矩阵。因此,\(R_{\tau}\)的对角向量会建模每个candidate item的latent factors,item的latent factors可以被看成是在每个latent factor上的产品的相关度。正如在matrix D的case,在\(R_{\tau}\)上的平方指数(squared exponent)可以确保我们总是有一个合理的kernel。

图片名称

图1

图1展示了factorization的一个图示。candidate item \(\tau\)的概率与已经在basket中的items set I是相关的:

\[P(y_{\tau} = 1 | I) = \sigma (w det K_{\tau, I} = 1 - exp(-w det K_{\tau,I})\]

…(8)

因此,\(g(V,D,R) \doteq g\)的log似然为:

\[g = \sum\limits_{m=1}^M log P(y_{\tau} | I_m) - \frac{a_0}{2} a_i (\| V_i \|^2 + \| D_i \|^2 + \| R^i \|^2)\]

其中,每个observation m与一个candidate item有关,\(I_m\)是与一个observation相关的basket items的set。由于之前的描述,矩阵V, D,以及\((R_{\tau})_{\tau \in \lbrace 1, \cdots, p\rbrace}\)通过使用SGA最大化log似然学到。正如logistic DPP模型,gradient ascent的一个step需要计算对称矩阵 \(L_I\)的逆和行列式,会产生\(O(f^{2.373})\)的复杂度(I中items数目为f)。算法2描述了该算法。关于最优化算法的细节详见附录。

图片名称

算法2

泛化到高阶交叉。在basket completion应用中,尝试同时推荐多个items挺有意思的。这可以使用一个贪婪方法来完成。也就是说,我们首先使用一个初始产品(initial product)来补充basket,并将augmented basket看成是一个新的basket,接着补充它。一种更直接的方法是,更适合捕获items间的高阶交叉,这可以泛化等式(7)。我们提出了一种高阶版本的模型,将来会对该模型进行效果评估。假设:d是要推荐的items数目,\(\tau = [\tau_1, \cdots, \tau_d] \in [p]^d\)。我们接着可以将kernel \(K_{\tau}\)定义为:

\[K_{\tau} = V \prod\limits_{k=1}^d R_{(d), \tau_d}^2 V^T + D^2\]

…(9)

其中,每个\(R_{(d), \tau_d} \in R^{r \times r}\)是一个对角矩阵。

3.3 预测

如前所述,从一个DPP中抽样可能是一个很难的问题,提出了许多解法[6,12]。尽管,在所有可能sets间抽样最好的set是个NP-hard问题,我们的目标是,寻找最好的item来补全basket。在这样的应用中,可以有效使用greedy方法,特别是我们的模型具有low-rank结构。另外,[10]提出了一种有效的方法来进行basket completion,涉及到对DPP进行conditioning,这在我们的logistic DPP模型有使用。

4.实验

5.实验结果

参考

阿里在paper《Behavior Sequence Transformer for E-commerce Recommendation in Alibaba》中提出了BST模型,我们可以借鉴一下:

1.介绍

2.架构

在rank stage中,我们会将推荐任务建模成CTR预测问题,它的定义如下:给定一个user点击的行为序列 \(S(u) = \lbrace v_1, v_2, \cdots, v_n \rbrace\),我们需要学习一个函数F,来预测u点击target item \(v_t\)的概率(例如:candidate item)。其它Features包括user profile、context、item、以及cross features。

我们会在WDL之上构建BST,总体架构如图1所示。从图1中知,我们可以看到,它遵循流行的embedding & MLP范式,其中,在feed到MLP之前,过去点击的items和相关features会首先嵌入到低维vectors中。BST和WDL的关键区别是:会添加transformer layer,通过捕获底层的序列信号(underlying sequential signals)来为用户点击items学习更好的表示。在以下部分,我们会引入一个bottom-up方式的BST核心组件:embeddding layer、transformer layer、MLP。

图片名称

图1 BST的架构总览。BST会使用用户的行为序列作为输入,包括:target item,以及”Other features”。它首先会将这些input features嵌入成低维vectors。为了更好地捕获在行为序行中的items间关系,会使用transformer layer来为该序列中的每个item学习更深的表示。接着通过将Other features的embeddings和transformer layer的output进行concatenate,使用3-layer MLP来学习hidden features间的交叉,最后使用sigmoid function来生成最终的output。注意,”Positional Features”会被包含在”Sequence Item Features”中。

2.1 Embedding Layer

第一个组件是embedding layer,它会将所有input features嵌入到一个fixed-size的低维vectors中。在我们的场景中,存在许多features,像:user profile features、item features、context features、以及不同features的组合(例如:cross features)。由于本工作聚焦于建模带transformer的行为序列,出于简洁性,我们会将所有这些features表示为“Other features”,并给出表1的一些示例。如图1所示,我们将图1左侧的“Other features”进行concatenate,并将它们嵌入到低维vectors中。对于这些features,我们会创建一个embedding matrix \(W_o \in R^{\mid D \mid \times d_0}\),其中:\(d_0\)是维度size。

图片名称

表1 图1左侧的”Other Features”。我们实际使用更多features,出于简洁,只列了许多有效的特征

另外,我们也会获得在行为序列中每个item的embedding。如图1所示,我们使用两种features类型来表示一个item:“Sequence Item Features”(红色)和“Positional Features”(暗蓝色),其中:“Sequence Item Features”包括:item_id和category_id。其中,一个item通常具有成百上千个features,在一个行为序列中选择所有features来表示该item代价太高。过往工作[15]介绍的,item_id和category_id对于表现来说足够好,在嵌入用户行为序列时,我们选择这两个特征作为sparse features来表示的每个item。”Positional Features”对应于以下的“positinal embedding”。接着,对于每个item,我们会将Sequence Item Features和Positional Features进行concatenate在一起,并创建一个embedding matrix:

\[W_V \in R^{\mid V \mid \times d_V}\]

其中:

  • \(d_V\)是embedding的dimension size
  • \(\mid V \mid\)是items数目

我们使用\(e_i \in R^{d_v}\)来表示在一个给定behavior sequence中的第i个item的embedding。

Positional embedding

在[13]中,作者提出了一个positional embedding来捕获句子中的order信息。同样的,在用户的行为序列中存在order。因而,在它们被投影成一个低维向量前,我们会添加“position”作为在bottom layer中每个item的一个input feature。注意,item \(v_i\)的position value会被计算成:

\[pos(v_i) = t(v_t) - t(v_i)\]

其中:

  • \(t(v_t)\)表示推荐时间(ecommending time)
  • \(t(v_i)\)是当用户点击item \(v_i\)的timestamp

我们会采用该方法,因为在我们的场景中它的效果要好于在[13]中的sin和cos函数

2.2 Transformer layer

在这部分,我们会引入Transformer layer,它会通过捕获在行为序行中其它items的关系,来为每个item学习一个deeper表示。

Self-attention layer

scaled dot-product attention[13]的定义如下:

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

…(1)

其中:

  • Q表示queries
  • K是keys
  • V是values

在我们的场景中,self-attention操作会将items的embeddings作为input,并通过线性投影将它们转成三个matrices,接着将它们feed到一个attention layer中。根据[13],我们使用multi-head attention:

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

…(2)(3)

其中,投影矩阵\(W^Q, W^K, W^V \in R^{d \times d}\),E是所有items的embedding matrics,h是heads的数目.

Point-wise Feed-Forward Network

根据[13],我们会将point-wise Feed-Forward Networks(FFN)来进一步增强模型的非线性(non-linearity),定义如下:

\[F = FFN(S)\]

…(6)

为了避免overfitting,并能层次化学习有意义的features,我们在self-attention和FFN中同时使用dropout和LeakyReLU,接着,self-attention和FFN layers的overall output如下:

\[S' = LayerNom(S + Dropout(MH(S)) \\ F = LayerNomr(S' + Dropout(LeakyReLU(S'W^{(1)} + b^{(1)}) W^{(2)} + b^{(2)}))\]

…(5)(6)

其中,\(W^{(1)}, b^{(1)}, W^{(2)}, b^{(2)}\)是可学习的参数,LayerNomr是标准的normalization layer。

Stacking the self-attention block

在经过第一个self-attention block之后,它会将所有之前的items的embeddings进行聚合,为了进一步建模在item sequences下的复杂关系,我们将self-building blocks和第b个block进行stack,定义如下:

\[s^b = SA(F^{(b-1)}) \\ F^b = FFN(S^b), \forall i \in 1, 2, \cdots, n\]

…(7) (8)

实际上,我们观察到,对比起b=2, 3(见表4),在我们的实验中b=1可以获取更好的效果。出于效率的目的,我们不再尝试更大的b。

2.3 MLP layers和loss function

通过将Other features的embeddings和应用在target item上的transfomer layer的output进行concatenate,我们接着使用三个fully connected layers来进一步学习在dense features间的交叉,它在工作界RS中是标准实现。

为了预测一个用户是否在target item \(v_t\)上有点击,我们会将它建模成一个二分类问题,接着我们使用sigmoid函数作为output unit。为了训练该模型,我们使用cross-entropy loss:

\[L = - \frac{1}{N} \sum\limits_{(x,y) \in D} (y log p(x) + (1-y) log(1-p(x)))\]

…(9)

其中,D表示所有的样本,\(y \in \lbrace 0, 1\rbrace\)表示用户是否点击了某个item,p(x)是在sigmoid unit之后的network的output,表示sample x被点击的预测概率。

3.实验

在本节中,我们会展示实验结果。

3.1 Settings

Dataset

数据集从taobao APP中构造得到。我们会构建一个8天内的基于用户行为的离线数据集。我们使用前7天作为训练数据,后一天作为test data。dataset的统计如表2所示。我们可以看到,dataset相当大与稀疏。

图片名称

表2

Baseline

为了展示BST的效果,我们会使用两个模型进行对比:WDL[2]和DIN[17]。另外,我们创建了一个baseline方法,它会将sequential信息包含到WDL中,表示成WDL(+Seq),它会以平均的方式将过去点击的items的embeddings进行聚合。我们的framework会在WDL之上进行构建,使用Transfomer添加序列建模,而DIN只会使用attention机制捕获在target item与过去点击items间的相似度。

评估指标

对于offline结果,我们使用AUC进行online A/B test,我们会使用CTR和平均RT来评估所有模型。TR是响应时间(response time)的简称,它表示给定一个query生成推荐结果的时间开销,例如:一个用户对taobao的一次请求。我们使用平均RT作为指标来评估在在线生产环境中的不同效率。

Settings

我们的模型使用python2.7+tensorflow 1.4实现,使用”adagrad”作为optimizer。另外,我们会使用表3的模型参数。

图片名称

表3

3.2 结果分析

结果如表4所示。我们可以看到BST对比baseline的优势。特别的,离线实验的AUC提升从0.7734(WDL)和0.7866(DIN)到了0.7894(BST)。当对比WDL和WDL(+Seq)时,我们可以看到将sequential信息以简单平均方式包括其中的效果。这意味着有了self-attention的帮助,BST可以提供强大的能力来捕获在用户行为序列下的sequential signal。注意,从我们的实际经验看,offline AUC的小增益可以导致在online CTR上的大收益。相似的现象也在google的WDL[2]中有报告。

图片名称

表4

另外,除了efficiency,BST的平均RT与WDL和DIN接近,这可以确保在实际大规模RS中部署像Transformer这样的复杂模型的可行性

最后,我们也展示了在2.2节中对self-attention进行stacking的影响。从表4中,我们可以看到b=1可以获得最好的offline AUC。这可能会归因于这样的事实:在用户行为序列中存在顺序依赖(sequential dependency)不像在机器翻译任务中的句子那样复杂,更小数目的blocks就足够获得好的效果。在[7]中有类似的观察。因此,我们选择b=1来在生产环境中部署BST,表4只上报了b=1的online CTR gain。

4.相关工作

在本节,我们简单回顾了在deep learning CTR方法的相关工作。由于WDL的提出【2】,提出了一系列工作来使用deep learning-based方法来提升CTR,比如:DeepFM、XDeepFM、Deep&Cross networks【16】等。然而,所有这些之前的工作主要关注于特征组合(feature combinations)或者neural network的不同结构,忽略了在真实推荐场景中用户行为序列的顺序特性。最近,DIN提出attention机制来处理用户行为序列。我们的模型与DIN的不同之处是,使用Transformer来处理在用户行为序列中每个item的一个更深表示,而DIN只会捕获与之前点击的items与target item间的不同相似性。换句话说,使用transformer的模型更合适捕获序列信号(sequential signals)。在[7,12]中,transformer模型提出以seq-to-seq的方式来解决sequential推荐问题,它们的架构与我们的CTR预测不同。

5.结论

本paper中,我们呈现了使用transfomer到taobao推荐中的技术细节。通过使用捕获sequential关系的强大能力,我们通过大量实验展示了在建模用户行为序列中transfomer的优越性。另外,我们也呈现了taobao在生产环境上的部署细节。

参考

介绍

从历史行为中建模用户的动态偏好,对于推荐系统来说是个挑战。之前的方法采用序列神经网络以从左到右的方式将用户历史交互编码成隐表示,来生成推荐。尽管它们是有效的,这种从左到右的单向模型是次优的,我们对此仍有争论,因为有以下的限制:

  • a) 单向结构限制了在用户行为序列中的隐表示的能力(power)
  • b) 通常这样的一个严格排序的序列,并不总是实际可行的

为了解决这样的限制,我们提出了一个序列推荐模型,称为:BERT4Rec,它采用deep bidirectional self-attention机制来建模用户行为序列。为了避免信息泄漏,以及对双向模型的有效训练,我们采用了Cloze objective到序列推荐中,通过联合条件(从左到右的context)预测在序列中随机的masked items。这种方式下,通过允许在用户历史行为中的每个item以及融合从左到右的信息,我们学习了一个bidirectional表示模型来做出推荐。我们在4个benchmark数据集上进行了大量实验,表明我们的模型要胜过state-of-art的序列模型。

1.介绍

用户兴趣的准确表征是一个推荐系统的核心。在许多真实应用中,用户当前兴趣是天然动态和演化的,受他们历史行为的影响。例如,一个用户可能在购买一个任天堂(Nintendo) Switch后,购买配件(比如:Joy-Con controller);但是在正常情况下他不会单买配件。

为了建模这样的序列动态性,提出了许多方法[15,22,40]基于用户历史交互来做出序列化推荐(sequential recommendations)。他们的目标是:在给定一个用户的过往历史交互后,预测他可能会交互的后继item(s)。最近,大量工作采用序列化神经网络(比如:RNN)来建模[14,15,56,58]。这些工作的基本模式是:将用户历史行为编码成一个vector(例如:用户偏好的表示),并使用一个从左到右的序列模型基于隐表示来做出推荐

图1 序列推荐模型架构的不同。BERT4Rec可以通过Cloze task来学习一个双向模型,而SASRec和RNN-based模型是从左到右的单向模型,只能顺序预测next item

尽管这些方法很流行并且是有效的,我们仍有争论:这种从左到右的单向模型不足够学到关于用户行为序列的最优表示。主要限制(如图1c和1d所示),这样的单向模型限制了历史行为序列中的items的隐表示的能力,其中每个item只能从之前的items的信息中进行编码(encode)。另一个限制是,之前提出的单向模型最初引入是为了使用原始顺序的序列数据,比如:文本(text)和时序数据。他们通常假设在数据上有一个严格有序的序列,但对于真实应用中的用户行为来说并不总是正确的。实际上,由于存在许多不可观察的外部因素,在一个用户历史交互行为中的items选择,可能不会遵循一个严格的顺序假设。在这种情况下,在用户行为序列建模中在两个方向上包含上下文(context)很重要。

为了解决上述限制,我们使用一个双向模型来学习用户历史行为序列的表示。特别的,受BERT的成功启发,我们提出使用深度双向self-attention模型到序列推荐中,如图1b所示。对于表征能力(representation power),在文本序列建模的深度双向模型的良好结果,表明对于序列表示学习的两个方向包含context很有意义。对于更严格的顺序假设,比起在建模用户行为序列上使用单向模型,我们的模型更适合,因为在双向模型中所有items都可以利用两侧的context。

然而,对于序列化推荐(sequential recommendation)来说训练双向模型并不简单和直接。常见的序列推荐模型通常以从左到右方式训练,并在输入序列中为每个位置预测下一个item。如图1所示,在一个深度双向模型中同时在左向到右向上联合上context,可能会造成信息泄露,例如:允许每个item间接地“看到target item”。这会使得预测future项变得不重要,该网络可能不能学到任何有用的东西

为了解决该问题,我们引入了Cloze task[6,50]来取代在单向模型(例如:序列化预测next item)中的目标函数。特别的,我们在输入序列中随机将一些items进行遮掩(mask)(例如:使用一个特别token[mask]进行替代),接着基于围绕他们的context来预测这些masked items的ids。这种方式下,我们可以避免信息泄露,并通过允许在输入序列中的每个item的表示融合(fuse)左和右的context,学到一个双向表示模型。除了训练一个双向模型外,Cloze objective的另一个优点是,它可以生成更多样本(samples)在多个epochs上训练一个更强大的模型。然而,Cloze task的缺点是,对于最终任务(例如:sequential recommendation)不一致。为了解决该问题,在测试期间,我们会在输入序列的末尾添加特殊token “[mask]”来表示我们需要预测的item,接着基于它的最终hidden vector来作出推荐。实验表明,我们的模型要更好。

主要贡献有:

  • 提出了使用双向self-attention网络,通过Cloze task来建模用户行为序列。据我们所知,这是首个在推荐系统中引入双向序列建模和Cloze objective的研究
  • 比较了该模型与state-of-the-art方法
  • 分析了在提出模型中的关键构成

2.相关工作

回顾下相关工作。

2.1 通用推荐

推荐系统的早期工作通常会使用CF,并基于它们的历史交互来建模用户偏好。在众多CF方法中,MF是最流行的方法,它会将users和items投影到一个共享的向量空间中,并通过两个向量间的内积来估计一个用户对该item的偏好。item-based的最邻近方法有[20,25,31,43]。他们会通过使用一个预计算好的i2i相似矩阵,结合它们历史交互上的items间的相似度,来估计一个用户在一个item上的偏好。

最近,深度学习已经重构了推荐系统。早期的工作是两层的RBM CF。

基于深度学习的另一条线是,通过集成辅助信息(比如:文本[23,53]、图片[21,55]、音频特征[51])到CF模型中来学习item的表示来提升推荐效果。另一条线是,替代常用的MF。例如,NCF会通过MLP替代内积来估计用户偏好,而AutoRec和CDAE则使用auto-encoder框架来预测用户评分。

2.2 序列化推荐

不幸的是,上述方法中没有一个是用于序列化推荐(sequential recommendation)的,因为他们会忽略用户行为中的顺序。

在序列化推荐中的早期工作,通常会使用MC(markovchains)来捕获用户历史交互。例如,Shani[45]将推荐生成公式化为一个序列优化问题,并采用MDP(Markov Decision Process)来求解它。之后,Rendle结合MC和MF通过FPMC来建模序列化行为和兴趣。除了一阶MC外,更高阶的MC也可以适用于更多之前的items。

最近,RNN和它的变种,Gated Recurrent Unit(GRU)[4]和LSTM(LSTM)在建模用户行为序列上变得越来越流行。这些方法的基本思想是,使用多种recurrent架构和loss function,将用户之前的记录编码成一个vector(例如:用户偏好的表示,可用于预测),包含:GRU4Rec、DREAM、user-based GRU、attention-based GRU(NARM))、improved GRU4Rec(BPR-max/Top1-max),以及一个有提升的抽样策略[14]。

与RNN不同,许多深度模型也被引入进序列化推荐中。例如,Tang[49]提出了一个卷积序列网络(Caser)来学习序列模式,它同时使用水平和垂直卷积filters。Chen[3]和Huang[19]采用Memory Network来提升序列化推荐。STAMP使用一个带attention的MLP来捕获用户的通用兴趣和当前兴趣。

2.3 Attention机制

Attention机制在建模序列化数据(例如:机器翻译、文本分类)中展示了令人满意的潜能。最近,一些工作尝试采用attention机制来提升推荐效果和可解释性[28,33]。例如,Li[28]将attention机制引入到GRU中来捕获用户序列行为以及在session-based推荐中的主要目的。

上述提到的工作基本上将attention机制看成是对于原始模型的一种额外的组件。作为对比,Transformer[52]和BERT[6]在multi-head self-attention上单独构建,并在文本序列建模中达到了state-of-the-art的效果。最近,对于在建模序列化数据中使用纯attention-based网络有上升的趋势。对于序列化推荐来说,Kang[22]引入了一个二层的Transformer decoder(例如:Transformer语言模型)称为SASRec来捕获用户的序列化行为,并在公开数据集上达到了state-of-the-art的效果。SASRec与我们的工作紧密相关。然而,它仍是一个单向模型,并使用了一个非正式的(casual) attention mask。而我们使用Cloze task以及一个双向模型来编码用户的行为序列。

3.BERT4Rec

我们首先引下研究问题、基本概念。

3.1 问题声明

在序列化推荐中,假设:

  • \(U=\lbrace u_1, u_2, \cdots, u_{\mid U \mid}\rbrace\) :表示一个用户集合
  • \(V=\lbrace v_1, v_2, \cdots, v_{\mid V \mid}\rbrace\)表示一个items集合
  • \(S_u=[v_1^{(u)}, \cdots, v_5^{(u)}, \cdots, v_{n_u}^{(u)}]\):表示对于用户\(u \in U\)按时间顺序的交互序列,其中\(v_t^{(u)} \in V\)是用户u在timestep t上交互的item,\(n_u\)是用户u交互序列的长度。

给定交互历史\(S_u\),序列化推荐的目标是预测:用户u在timestep \(n_u + 1\)的交互的item。它可以公式化为,为用户u在timestep \(n_u + 1\)上建模所有可能items的概率:

\[p(v_{n_u + 1}^{(u)} = v | S_u)\]

3.2 模型结构

这里,我们引入了一个新的序列化推荐模型,称为BERT4Rec,它采用Transformer中的双向编码表示到一个新任务(sequential Recommendation)中。它在流行的self-attention layer上构建,称为“Transformer layer”。

如图1b所示,BERT4Rec通过L个双向Transformer layers进行stack组成。每个layer上,它会通过使用Transformer layer并行地跨之前层的所有positions交换信息,来迭代式地修正每个position的表示。通过如图1d的方式,以step-by-step的RNN-based的方式来前向传播相关信息进行学习,self-attention机制会赋予BERT4Rec直接捕获任意距离间的依赖。该机制会产生一个全局的receptive field,而CNN-based方法(比如:Caser)通常有一个受限的receptive field。另外,对比RNN-based方法,self-attention更容易并行化。

对比图1b, 1c, 1d,大多数显著的不同之处是,SASRec和RNN-based方法都是从左到右的单向结构,而BERT4Rec使用双向self-attention来建模用户的行为序列。这种方式下,我们提出的模型可以获取关于用户行为序列的更强大表示,来提升推荐效果。

3.3 Transformer Layer

如图1b所示,给定一个长度为t的输入序列,我们在每一层l的每个position i上同时使用transformer layer来迭代式地计算隐表示\(h_i^l\)。这里,我们将\(h_i^l \in R^d\)进行stack在一起来形成一个矩阵(matrix) \(H^l \in R^{t \times d}\),因为我们会在实际上同时计算所有positions的attention function。如图1a所示,Transformer layer Trm包含了两个sub-layers:一个Multi-head self-attention sub-layer以及一个position-wise feed-forward network。

Multi-Head self-Attention. Attention机制在许多任务中变为序列建模的一部分,它可以捕获在representation pairs间的依赖,无需关注序列中的距离。之前的工作表明,在不同positions上的不同表征子空间上的信息进于jointly attend是有用的[6,29,52]。因而,我们可以采用multi-head self-attention来替代执行单一的attention函数。特别的,multi-head attention会首先使用不同的、可学习的线性投影,将\(H^l\)线性投影到h个子空间(subspaces)上,接着以并行的方式使用h个attention functions来生成output表示,它们可以进行拼接,然后进行再次投影

\[MH(H^l) = [head_1; head_2; \cdots; head_h] W^O \\ head_i = Attention(H^l W_i^Q, H^l W_i^K, H^l W_i^V)\]

…(1)

其中,每个head的投影矩阵是可学习的参数。

  • \[W_i^Q \in R^{d \times d / h}\]
  • \[W_i^K \in R^{d \times d /h}\]
  • \[W_i^V \in R^{d \times d /h}\]
  • \[W_i^O \in R^{d \times d}\]

这里,出于简洁性,我们忽略掉layer上标l。实际上,这些投影参数并不是跨网络共享的。这里,Attention函数是scaled dot-product attention:

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

…(2)

这里,query Q, key K 和value V使用等式(1)中不同学到的投影矩阵从相同的矩阵\(H^l\)进行投影。 temperature \(\sqrt{d/h}\)被引入用来生成一个softer attention分布,以避免极小的梯度。

Position-wise feed-forward网络

如上所述,self-attention sub-layer主要基于线性投影。为了使该模型具有非线性以及不同维度间的交叉,我们在self-attention sub-layer的outputs上使用一个Position-wise Feed-forward network,每个position独立且相同。它包含了两个仿射变换(affine transformations),两者间具有一个GELU activation(Gaussian Error Linear Unit):

\[PFFN(H^l) = [FFN(h_1^l)^T; \cdots; FFN(h_t^l)^T]^T \\ FFN(x) = GELU(xW^{(1)} + b^{(1)}) W^{(2)} + b^{(2)} \\ GELU(x) = x \phi(x)\]

…(3)

其中:

  • \(\phi(x)\)是标准gaussian分布的累积分布函数,
  • \(W^{(1)} \in R^{d\times 4d}, W^{(2)} \in R^{4d\times d}, b^{(1)} \in R^{4d}, b^{(2)} \in R^d\)是可学习参数,并且跨所有positions共享

出于便利我们忽略layer上标l。事实上,这些参数在layer与layer间是不同的。在本工作中,根据OpenAI GPT和BERT,我们使用一个更平滑的GELU activation而非标准的ReLU activation。

Stacking Transformer layer

如上所述,我们可以使用self-attention机制,来很轻易地捕获跨整个行为序列的item-item交叉。然而,通过将self-attention layers进行stacking来学习更复杂的item transition patterns是有利的。然而,该网络会随着更深而变得更难训练。因此,我们两个sublayers的每一个周围都采用一个residual连接,如图1a所示,并使用layer normalization。另外,在它们被normalized后,我们会在每个sub-layer的output上采用dropout[47]。也就是说,每个sub-layer的output是:\(LN(x + Dropout(sublayer(x)))\),其中:\(sublayer(\cdot)\)是通过sublayer自身实现的函数,LN是由[1]定义的layer normalization function。我们会使用LN来在相同layer上的所有hidden units上归一化inputs,以便加速网络训练。

总之,BERT4Rec以如下形式重新定义了每个layer的hidden表示:

\[H^l = Trm(H^{l-1}), \forall i \in [1, \cdots, L] \\ Trm(H^{l-1}) = LN(A^{l-1} + Dropout(PFFN(A^{l-1})) \\ A^{l-1} = LN(H^{l-1} + Dropout(MH(H^{l-1})))\]

3.4 Embedding Layer

所上所述,由于不使用任何recurrence或convolution模块,Transformer layer Trm不会意识到输入序列的顺序。为了利用输入的顺序信息,我们在Transformer layer stacks的底部,将position embeddings引入到input item embeddings中。对于一个给定的item \(v_i\),它的输入表示\(h_i^0\)通过对相应的item embedding和positinal embedding进行求和来构成:

\[h_i^0 = v_i + p_i\]

其中,\(v_i \in E\)对于item \(v_i\)是第d维的embedding,\(p_i \in P\)是position index=i上的d维positional embedding。在本模型中,我们使用可学习的positional embeddings来替代确定的sinusoid embedding以提升更高的效果。positional embedding matrix \(P \in R^{N \times d}\)允许我们的模型来标识要处理哪一部分的input。然而,它也在最大句长N上做了限制。因而,我们需要将输入序列\([v_1, \cdots, v_t]\)截断取最近的N个items \([v_{t-N+1}^u, \cdots, v_t]\) (如果t>N)。

3.5 Output layer

在L layers后,会跨之前层上的所有positions来层次化交换信息,对于input序列的所有items,我们会获得最终的output \(H^L\)。假设我们将item \(v_t\)在timestep t上进行mask,我们接着基于图1b的\(h_t^L\)来预测masked items \(v_t\)。特别的,我们会应用一个两层的feed-forward网络,并使用GELU activation来生成一个在target items上的output分布:

\[P(v) = softmax(GELU(h_t^L W^P + b^P) E^T + b^O)\]

…(7)

其中:

  • \(W^P\)是可学习的投影矩阵
  • \(b^P\)和\(b^O\)是bias项
  • \(E \in R^{\mid V \mid \times d}\)是对于item set V的embedding矩阵

我们在input layer和output layer上使用共享的item embedding matrix来减缓overfitting并减小模型size。

3.6 模型学习

训练

常见的单向序列推荐模型通常通过为输入序列中的每个position预测next item的方式来进行训练(如图1c和1d)。特别的,input序列\([v_1, \cdots, v_t]\)的target是一个shfited版本 \([v_2, \cdots, v_{t+1}]\)。然而,如图1b所示,在双向模型中的left context和right context进行联合,可能会造成:每个item的最终output表示会包含target item的信息。这会使得预测将来项变得更平凡,网络不会学到任何有用的东西。对于该问题一种简单的解法是,从长度为t的原始行为序列中创建t-1个样本(带有next items的子序列,形如:\(([v_1],v_2)\)、\(([v_1,v_2],v_3)\)),接着使用双向模型将每个历史子序列进行encode,以预测target item。然而,该方法非常耗时、耗资源,因为我们必须为在序列中的每个position创建一个新样本并进行单独预测。

为了高效地训练我们的模型,我们使用了一个新的objective:\(Cloze ask\) [50](在[6]中被称为“Masked Language Model”)来序列推荐中。它是一种测试(test),由将某些词移除后的语言的一部分组成,其中参与者(participant)会被要求填充缺失的词(missing words)。在我们的case中,对于每个training step,我们对输入序列中的所有items的一部分\(\rho\)进行随机遮掩(randomly mask)(通过使用特殊token “[mask]”进行替代),接着只是基于它的left context和right context来预测masked items的原始ids。例如:

Input: \([v_1, v_2, v_3, v_4, v_5]\) —-> \([v_1, [mask]_1, v_3, [mask]_2, v_5]\)

labels: \([mask]_1 = v_2, [mask]_2 = v_4\)

对应于”[mask]”的最终的hidden vectors,会被feed给一个在item set上的output softmax,这与常规的序列推荐相同。事实上,我们会为每个masked input \(S_u'\)定义loss来作为关于该masked targets的负log似然:

\[L = \frac{1}{ |S_u^m|} \sum\limits_{v_m \in S_u^m} -log P(v_m = v_m^* | S_u')\]

…(8)

其中,\(S_u'\)是用户行为历史\(S_u\)的masked版本,\(S_u^m\)是在它上的random masked items,\(v_m^*\)是masked item \(v_m\)的true item,概率\(P(\cdot)\)如等式(7)定义。

Cloze task的一个额外优点是,它可以生成更多样性来训练模型。假设一个长度为n的序列,如图1c和图1d所示的常规序列预测可以为训练生成n个唯一的样本,而BERT4Rec在多个epochs上可以获得\((_k^n)\)的样本(如果我们随机mask k个items)。它允许我们训练一个更强大的单向表示模型。

Test

如上所述,我们会在训练和最终序列推荐任务间不匹配(mismatch),因为Cloze objective是为了预测当前maskted items,而序列推荐的目标是预测the future。为了解决该问题,我们会在用户行为序列的结尾添加特殊token “[mask]”,接着,基于该token的最终hidden表示预测next item。为了更好匹配(match)序列推荐任务(例如:预测last item),我们也可以在训练期间生成只在输入序列中mask最后一个item的抽样。它与序列推荐的fine-tuning相似,可以进一步提升推荐效果。

3.7 讨论

这里,我们会讨论我们的模型与之前的工作的关系。

SASRec

很明显,SARRec是从左到右的单向版本的Bert4Rec,它使用单个head attention以及causal attention mask。不同的结构导至不同的训练方法。SASRec会为序列中的每个position预测next item,而Bert4Rec会使用Cloze objective预测序列中的masked items。

CBOW & SG

另一个非常相似的工作是CBOW(Continuous Bag-of-Words)和(SG)Skip-Gram。CBOW会使用在context(包含左和右)中的所有word vectors的平均来预测一个target word。它可以看成是一个简版的BERT4Rec:如果我们在BERT4Rec中使用一个self-attention layer,并在items上具有均匀的attention weights,不共享的item embeddings,移除positional embedding,并将中心项mask住。与CBOW相似,SG也可以看成是BERT4Rec的简版(mask所有items,除了它自身)。从该角度看,Cloze可以看成是CBOW和SG的objective的一个通用格式。另外,CBOW使用一个简单的aggregator来建模word序列,因为它的目标是学习好的word representations,而非sentence representations。作为对比,我们会寻找一个更强大的行为序列表示模型(deep self-attention network)来作出推荐。

BERT

尽管我们的BERT4Rec受NLP中BERT,它与BERT仍有许多不同之处:

  • a) 大多数主要区别是,BERT4Rec是一个用于序列推荐的end-to-end模型,而BERT是一个用于句子表示的pre-training模型。BERT会利用大规模task-independent语料来为许多文本序列任务pre-train句子表示模型,因为这些任务会共享关于该语言的相同背景知识。然而,在推荐任务中不受该假设约束。这样,我们可以为不同的序列化推荐datasets训练BERT4Rec end-to-end。
  • b) 不同于BERT,我们会移除next sentence loss和segment embeddings,因为BERT4Rec会建模一个用户的历史行为,只有在序列推荐中有一个序列

4.实验

评估了三个数据集:

  • Amazon Beauty:Amazon.com收集的产品review数据集。
  • Steam:从在线视频游戏发生商Steam中收集得到,
  • MovieLens:MovieLens电影数据集

4.5 hidden维度d的影响

4.6 Mask比较\(\rho\)的影响

4.7 最大序列长度N的影响

4.8 消融(Ablation)研究

参考

Alex Beutel等人在KDD 2019《Fairness in Recommendation Ranking through Pairwise Comparisons》中提出pairwise比较来看fairness。具体方法如下:

介绍

我们希望什么样的推荐系统?推荐器对于将用户连接到网络上的相关内容、items或者信息来说很重要,用户、内容提供商、零售商、信息提供商都依赖这些系统,我们需要明白谁应该是否被支持很重要。在本paper中,我们主要关注一个推荐系统在关于items的under-ranking groups上的风险。例如,一个under-ranked的社交网络通过一个给定的demographic group发表,会限定在该group范围内可见。

对于分类(classification)的公平性度量(fairness metrics)有许多研究,每种metric都是恰当的,但对于推荐系统来说,这方面考虑的较少。在推荐系统中,公平性的研究是很有挑战性的,它们很复杂。通常包含了多个模型,必须平衡多个目标,由于存在很大、倾斜的稀疏性以及许多动态性(dynamics)很难评估。所有这些要点在推荐系统社区中很难解决,在提升推荐公平性上提出了额外的挑战。

一个挑战性的划分是介于:将推荐看成是一个pointwise prediction问题、将这些预测应用于排序列表的构建。pointwise recommenders会为每个item做出一个关于用户兴趣的预测,接着基于这些预测决定一个推荐排序(ranking)。该setup在实际中很常见,但大多数研究都是深入去缩小pointwise predictions和ranking construction间的构建。公平性会陷入进退两难的境地。最近围绕pointwise accuracy为中心的关于fairness metrics的研究[8,49],并不能表明产生的ranking是用户实际想看的。做为对比,[52,44,45,11]探索了什么是一个fair ranking,但都关注于非个性化排序(unpersonalized rankings),它们会考虑上items的相关度、并且大多数情况下需要使用上item group关系的一个后处理算法(post-processing algorithm),这在实际中通常是不可行的[10]。

另外,推荐系统的评估是很难的,因为系统的动态变化性。一个用户昨天感兴趣的东西,在明天可能会不感兴趣,我们只能通过一个用户的偏好来推荐一个item给他们。因而,metrics通常是对之前的推荐系统(previous)[3]是有偏的(biased:在统计上),大量研究会做无偏离线评估[43,42],由于存在很大的item space、以及极其稀疏的feedback、users和items的不断演化,很难进行评估。当尝试衡量推荐系统的公平性时,这些issues只能变得更显著;而当你尝试评估complete rankings时更甚

我们通过一个pairwise recommendation fairness metric来解决所有的这些挑战。通过使用易运行、随机化的实验,我们可以得到关于用户偏好的无偏估计(unbiased estimates)。基于这些观察到的(observed) pairwise偏好,我们甚至都可以对一个pointwise的推荐系统的公平性进行measure,我们展示了这些metrics与排序效果直接相关。另外,我们提供了一种新的正则项(regularization term),结果表明它可以提升一个pointwise recommender的最终ranking fairness,如图1所示。我们在生产环境中的一个大规模推荐系统上进行测试,结果表明实际是有益的,并且理论上和经验上是可同时trade-offs的。我们的贡献有:

  • Pairwise Fairness:
  • Pairwise Regularization:
  • 真实实验:

2.相关工作

推荐系统:。。。

机器学习公平性(Machine Learning Fairness.):机器学习公平性主要关注分类问题的公平性,提出了许多定义。基于这些定义的group fairness,一个模型将两组样本进行比较,成为了最常见的结构,但研究者们展示了不同定义间的调节器。我们主要根据Hardt[23]的机会等式(equality of opportunity intuition),其中我们会关注不同groups上在accuracy上的差异。我们的metric更接近于构建在一个AUC-based 分类和回归问题上的fairness metrics,它由Dixon[18]提出,并在[12]中展开可以作为不同的Mann-Whitney U-tests。

Recommender System Fairness。在ranking和recommendation上的fairness上,已经有一些研究,但这些研究都从不同的视角出发。Zehlike[52]从排序公平性的目标出发,但没有考虑推荐系统(它的数据是很稀疏的)。相似的,Singh[44]采用一个full-ranking的公平性视角,可以通过一个后处理算法(post-processing) 对模型预测应用于推荐系统;接着[45]将它移到模型训练中。所有这些工作[52,44,45,11]关注于一个非个性化的信息检索系统,其中主要关注每个item的相关labels;我们关于的个性化推荐场景存在:数据稀疏性和biases。[8,49]则关注于CF pointwise accuracy跨不同groups的差异,但没有将这些metrics连接到最终的rankings上。

更多研究在统计等价(statistical parity),其中在一些应用上还有争议:items应跨不同groups以相同的rate被展示。Diversity、filter bubbles、feedback loops,以及机器学习的fairness,在本paper不是关注重点。

Fairness Optimization. 许多方法的提出是为了解决公平性问题。Post-processing可以提供优雅解法【23,44】,但通常需要已经对于所有样本的group memberships,这对于demographic数据来说几乎是未知的。然而,许多方法在分类训练期间来优化fairness metrics,比如:constriaint-based optimization、adversarial learning、以及通过模型预测的regularzation。我们构建了这些regularization方法来提升我们推荐系统的fairness属性。

3.推荐的pairwise fairness

我们考虑一个生产环境推荐系统,它会推荐一个关于K个items的个性化列表给用户。我们考虑一个cascading recommender,它会使用检索系统(retrieval systems)集合,后跟着一个排序系统(ranking system)。我们假设:retrival systems会从一个包含M个items的语料J中,返回一个关于\(M'\)的相关items的集合R,其中\(M \gg M' \geq K\)。排序模型(ranking model)接着必须进行打分,并对\(M'\)个items进行排序来得到最终的K items排序列表。这里,我们主要关注ranker的角色。

当做出一个推荐时,系统会为user i观察用户特征\(u_i\),和一个上下文特征集合c(比如时序(timing)、或设备信息);我们将它称为query:\(q=(u,c)\)。另外,对于每个item \(j \in J\),我们观察到特征向量 \(v_j\);这里,我们会包含对于item的稀疏表示或学到的embeddings,以及与该item相关的其它属性。ranker会基于user feedback(包含:clickes, ratings, 文上的停留时间,items的后续购买等)的估计执行ranking。对于我们的系统,我们会估计用户是否会在该item上的点击\(y \in {0, 1}\),以及在点击该item上的用户参与度(user engagement)\(z \in R\),比如:停留时间、购买、raitings。这样,我们的数据集包含了历史样本 \(D = \lbrace (q,v,y,z) \rbrace\)。(注意,由于z是在一个点击之后的user engagement,如果没有点击发生,z=0)。D只包含了之前被推荐的样本。

ranker是一个模型\(f_{\theta}\),参数为\(\theta\);该模型被训练来预测用户参与度\(f_{\theta}(q,v) = (\hat{y},\hat{z}) \approx (y,z)\)。最终,一个items的ranking会通过打分函数\(g(\hat{y}, \hat{z})\)来生成,用户会从由g排序的相关items R中选取topK个items。

3.2 Fairness concerns的动机

在之前的讨论中,有许多公平性关注点在文献中有强调。在本paper中,我们主要关注items分组成为under-recommended的风险。例如,如果一个under-ranked的社交网络,通过一个给定的demographics group进行发表,它会限制分组在该服务上的可见性和参与度。如果一个网络的评估部分是个性化的,那么一个demographic group的用户评论也是under-ranked,接着该demographic会在该网络上有更少的话语权(voice)。在一个更抽象的层次上,我们假设,每个item j具有敏感属性\(s_j \in \lbrace 0, 1 \rbrace\)。我们会measure:来自一个group上的items是否在系统上是under-ranked。

尽管并非是我们的主要关注点,这些issues可以user group concerns并列,如果一个items的group是否被一个特定的user group更偏好。该框架会显式扩展到包含user groups。如果每个user具有一个敏感属性,我们可以通过每个user group来计算所有以下的metrics,并计算跨groups的性能比较。例如,如果我们关注的是,一个社交网络是under-ranking,特定主题的items只限定于特定的demographic人群,我们可以比较:跨demographic groups的主题内容的under-ranking的degree。

3.3 Pairwise Fairness Metric

上述fairness目标看起来很重要,对于一个”under-ranked”的item来说,我们必须准确搞清它的含义。这里我们吸收了[23]的思想:一个classifier的fairness通过比较它的false postive rate and/or false negative rate进行量化。不同的是,给定一个item的label是postive的,classifier预测它为positive的probability。在分类中,由于模型预测可以通过一个预测定阀值进行比较,这可以有效工作。

在推荐系统中,一个positive prediction是不明确的,即使人们将分析限制在clicks(y)和ignore engagement(z)中。例如,如果一个item被点击,y=1,那么被预测的点击概率为\(\hat{y}=0.6\),这是一个positive prediction吗?它可以被看成是一个0.4的under-prediction,如果其它items都具有一个预测的\(\hat{y}<0.6\)它仍是top-ranked item。因而,理解在pointwise predictions中的errors需要对比对于相同query的items预测。

我们开始定义了一个pairwise accuracy:一个clicked item的概率被排在另一个相关uncliked item之上,对于一个相同的query有:

\[PairwiseAccuarcy \triangleq P(g(f_{\theta} (q, v_j)) > g(f_{\theta}(q, v_j')) | y_{q,j'}, j, j' \in R_q)\]

…(1)

有了该定义,我们可以知道ranking系统会对cliked item进行rank的频次。出于简洁,我们使用\(c_q(j, j') \triangleq 1 [g(f_{\theta}(q,v_j)) > g(f_{\theta}(q,v_{j'}))]\)来表示:对于query q,item j和\(j'\)间的预测比较;我们会隐掉\(j, j' \in R_q\)项,但我们只考虑对于所有以下定义相关items间的比较。

对于余下的fairness研究,我们会关注groups间的相对performance,而非绝对performance。因而,我们可以比较:

\[P(c_q(j, j') | y_{q,j} > y_{q,j'}, s_j = 0) = P(c_q(j,j') | y_{q,j} > y_{q,j'}, s_j =1)\]

也就是说,来自一个group \(S=0\)的items的PairwiseAccuarcy,要比来自另一个group \(S=1\)的PairwiseAccuarcy或高或低些。

这是一个直觉上的metric,这里还有疑问:它会忽略整个user engagement z,因而可能会有促进ckickbait的风险。

定义1(Pairwise Fairness)。一个具有ranking公式g的模型\(f_{\theta}\),如果一个clicked item的likelihood被排到另一个相关的uncliked item之上(跨相同的groups),被认为是服从pairwise fairness,则被认为是服从pairwise fairness:

\[P(c_q(j,j') | y_{q,j} > y_{q,j'}, s_j = 0, z_{q,j} = \bar{z}) = P(c_q(j, j') | y_{q,j} > y_{q,j'}, s_j=1, z_{q,j}=\bar{z}), \forall \bar{z}\]

对于来自每个group的items,该定义给出了一个关于ranker accuracy的聚合概念。

由于它是valuable的,它不会区别来自mis-orderings types。对于来自一个group的under-exposing items可能是有问题的。为了说明,考虑以下两个示例:在两种情况下,每个group \(\lbrace A_j \rbrace_{j=1}^3 \cup \lbrace B_j \rbrace_{j=1}^3\)存在三个items,在第一个case中,系统给出了一个 ranking \([ A_2, A_3, B_1, A_1, B_2, B_3 ]\),在第二个case中,系统给出了\([A_1, A_2, A_3, B_1, B_2, B_3]\),我们可以看到,overall pairwise accuracy在两个cases中相同,\(\frac{2}{5}\),但在第二个case中,当group B中的一个item有兴趣(clicked),所有group B items会排在group A items之下。两者在ranking中都有问题(排在clicked item之下),但第二个case有系统上更有问题,偏向于某个group,这独立于用户偏好。

为了解决该问题,我们可以将上述pairwise fairness定义分割成两个独立的criteria:在相同group中items间的pairwise accuracy,不同groups的items间的pairwise accuracy;我们将这些metrics称为:”intra-group pairwise accuracy”和”inter-group pairwise accuracy”:

\[Intra-Group \ Acc. \triangleq P(c_q(j, j') | y_{q,j} > y_{q,j'}, s_j = s_{j'}, z_{q,j} = \bar{z}) Inter-Group \ Acc. \triangleq P(c_q(j, j') | y_{q,j} > y_{q,j'}, s_j \neq s_{j'}, z_{q,j} = \bar{z})\]

…(3) …(4)

定义2

定义3

3.4 Measurement

在推荐系统中,users和items是高度动态的,我们通常只在之前的recommended items上观察user feedback,这会使得metrics容易偏偏于previous recommender system。

然而,对于上述给出的三个fairness定义,我们希望在item pairs间用户偏好的无偏估计。为了这样做,我们在小量queries上运行随机实验。

参考

Minmin Chen、Alex Beutel等在《Top-K Off-Policy Correction for a REINFORCE Recommender System》中提出使用强化学习来提升youtube推荐。主要是从bias/variance的角度出发,具体方法如下:

摘要

工业界推荐系统会处理非常大的动作空间(action spaces)——数百万items来进行推荐。同时,他们需要服务数十亿的用户,这些用户在任意时间点都是唯一的,使得用户状态空间(user state space)很复杂。幸运的是,存在海量的隐式反馈日志(比如:用户点击,停留时间等)可用于学习。从日志反馈中学习是有偏的(biases),这是因为只有在推荐系统上观察到的反馈是由之前版本的推荐系统(previous versions)选中的。在本文中,我们提出了一种通用的方法,在youtube生产环境上的top-k推荐系统中,使用一个基于策略梯度的算法(policy-gradient-based algorithm,比如:REINFORCE),来解决这样的偏差。该paper的主要贡献有:

  • 1.将REINFORCE扩展到生产环境推荐系统上,动作空间有数百万;
  • 2.使用off-policy correction来解决在从多种行为策略中收集的日志反馈的数据偏差(data biases)
  • 3.提出了一种新的top-K off-policy correction来解释我们一次推荐多个items的策略推荐
  • 4.展示了探索(exploration)的价值

我们通过一系列仿真(simulations)和youtube的多个真实环境,来展示我们的方法的效果。

1.介绍

在工业界,通过推荐系统来帮助用户从海量内容中挑选和发现用户感兴趣的少部分内容。该问题十分具有挑战性,因为要推荐海量的items数目。另一方面,将合适的item在合适的时间上曝光给正确的用户,需要推荐系统能基于历史交互,不断地适应用户的兴趣漂移。不幸的是,对于一个大的状态空间(state space)和动作空间(action space),我们只观察到相对少量的数据,大多数用户只被曝光了少量items,而显式反馈的数据占比更少。也就是说,推荐系统在训练时只能接受相当稀疏的数据,例如:Netflix Prize Dataset只有0.1%的数据是dense的。因此,推荐系统的大量研究会探索不同的机制来处理相当稀疏的情况。从隐式用户反馈(比如:点击、停留时间)中学习,对未观察到的交互进行填充,对于提升推荐是很重要的一步。

大多数独立的研究线上,增强学习(RL)已经在游戏、机器人领域取得了相当大的进步。RL通常聚焦于构建agents,在一个环境(environment)中采取哪些动作(action)来最大化一些长期收益(long term reward)。这里,我们探索了将推荐解析成:构建RL agents来最大化每个用户使用该系统的长期满意度。在推荐问题上,这提供给我们一个新的视角和机会来基于在RL最新进展之上进行构建。然而,将这些新东西应用于实际还是有许多挑战。

如上所述,推荐系统需要处理大的状态空间(state spaces)和动作空间(action spaces),在工业界尤其显著。推荐可提供的items集合是不确定的(non-stationary),新items会不断被引入到系统中,从而产生一个日益增长的带新items的动作空间(action space),这会产生更稀疏的反馈。另外,在这些items上的用户偏好是会随时间一直漂移的(shifting),从而产生连续演化的用户状态(user states)。在这样一个复杂的环境(environment)中,通过这些大量actions进行reason,在应用已有RL算法时提出了独特的挑战。这里,我们分享了我们的实践:在非常大的动作空间和状态空间中,在一个神经网络候选生成器(neural candidate generator)上(一个top-k推荐系统)应用REINFORCE算法[48]。

除了大量动作和状态空间外,推荐系统中的RL仍是有区别的:只有有限提供的数据。经典的RL应用通过self-play和仿真(simulation)生成的大量训练数据,已经克服了数据无效性(data inefficiencies)。相比较而言,推荐系统的复杂动态性,使得对于仿真生成真实推荐数据是不可能的。因此,我们不能轻易寻找(probe for)关于之前的state和action space的未探索领域上的回报(reward),因为观测到的回报(observing reward)需要为一个真实用户给出一个真实推荐。作为替代,该模型几乎依赖于之前推荐模型们(models即policies)所提供的数据,大多数模型我们是不能控制的或不再可以控制。对于从其它policies中大多数日志反馈,我们采用一个off-policy learning方法,在该方法中我们会同时学习之前policies的一个模型,当训练我们的新policy时,在纠正数据偏差时包含它。我们也通过实验演示了在探索数据(exploratory data)上的价值(value)。

最终,在RL方法中大多数研究主要关注于:产生一个可以选择单个item的policy。而真实世界的推荐系统,通常会一次提供用户多个推荐[44]。因此,我们为我们的top-K推荐系统定义了一个新的top-K off-policy correction。我们发现,在模拟和真实环境中,标准off-policy correction会产生一个对于top-1推荐来说最优的policy,而我们的top-K off-policy correction会生成更好的top-K推荐。我们提供了以下的贡献:

  • 1.REINFORCE推荐系统:我们在一个非常大的action space中,扩展了一个REINFORCE policy-gradient-based方法来学习一个神经网络推荐policy。
  • 2.Off-Policy候选生成:我们使用off-policy correction来从日志反馈中学习,这些日志从之前的model policies的一个ensemble中收集而来。我们会结合一个已经学到的关于行为策略(behavior policies)的神经网络模型来纠正数据偏差。
  • 3.Top-K Off-policy Correction:我们提供了一个新的top-K off-policy correction来说明:我们的推荐一次输出多个items。
  • 4.真实环境的提升:我们展示了在真实环境中(在RL文献中很少有这种情况),这些方法对于提升用户长期满意度的价值。

我们发现,这些方法的组合对于增加用户满意度是很有用的,并相信对于在推荐中进一步使用RL仍有许多实际挑战。

2.相关工作

增强学习:Value-based方法(比如:Q-learning),policy-based方法(比如:policy gradients constitue经典方法)来解决RL问题。[29]中罗列了现代RL方法的常见比较,主要关注于异步学习(asynchronous learning),它的关键点是扩展到更大问题上。尽管value-based方法有许多优点(比如:seamless off-policy learning),他们被证明是在函数逼近(function approximation)上是不稳定的[41]。通常,对于这些方法来说,需要进行大量的超参数调参(hyperparameter tuning)才能达到稳定行为。尽管许多value-based方法(比如:Q-learning)取得了实际成功,这些算法的策略收敛(policy convergence)没有被充分研究。另外,对于函数逼近来说,Policy-based方法只要给定一个足够小的learning rate,仍然相当稳定。因此,我们选择一个policy-gradient-based方法(尤其是REINFORCE[48]),将这种on-policy方法适配到在当训练off-policy时提供可靠的policy gradient估计。

神经网络推荐系统:与我们的方法紧密相关的另一条线是,在推荐系统中应用深度神经网络[11,16,37],特别是使用RNN结合时序信息和历史事件用于推荐[6,17,20,45,49]。我们使用相似的网络结构,通过与推荐系统的交互来建模用户状态(user states)的演进。由于神经网络架构设计不是本文重点,有兴趣可以自己了解。

推荐系统中的Bandit问题:在线学习方法很流行,由于新的用户反馈是可提供的,可以快速被适配到推荐系统中。Bandit算法比如(UCB)[3],会以一种解析可跟踪的方式(它在regret上提供了很强的保证)来权衡exploration和exploitation。不同的算法,比如:Thomson sampling【9】,已经被成功应用于新闻推荐和展示广告。Contextual bandits提供了一种关于基础在线学习方法的context-aware refinement,并会将推荐系统朝着用户兴趣的方向裁减[27]。Agarwal【2】使得contextual bandits可跟踪,并且很容易实现。MF和bandits的混合方法被开发出来用于解决cold-start问题[28]。

推荐系统中的倾向得分(Propensity Scoring)和增强学习(Reinforcement learning):学习off-policy的问题在RL中是很普遍的,通常会影响policy gradient。由于一个policy会演进,因此在对应梯度期望下的分布需要重新计算。在机器人领域的标准方法[1,36],会通过限制policy更新的方式来绕过,以便在某一更新policy下新数据被收集之前,不能从实质上变更policy,作为回报,它会提供关于RL目标函数的单调提升保证。这样的近似(proximal)算法很不幸不能应用于item目录和用户行为快速变化的推荐情景中,因此大量的policy会发生变更。同时,对于大的状态空间和动作空间规模来说,收集日志反馈很慢。事实上,在推荐系统环境中,对于一个给定policy的离线评估已经是个挑战。多个off-policy estimators会利用逆倾向得分(inverse-propensity scores)、上限逆倾向得分(capped inverse-propensity scores)、以及许多变量控制的measures已经被开发出[13,42,43,47]。Off-policy评估会将一个相似的数据框架纠正为off-policy RL,相似的方法会被应用于两个问题上。逆倾向指数已经被大规模的用于提升一个serving policy【39】。Joachims[21]为一个无偏排序模型学习了一个日志反馈的模型;我们采用一个相似的方式,但使用一个DNN来建模日志行为策略(logged behavior policy),它对于off-policy learning来说是必需的。更常见的是,off-policy方法已经被适配到更复杂的问题上(比如:[44]为石板推荐)。

3.增强推荐

为便于理解,这里插入了张图(from 李宏毅课程)。

我们开始描述我们的推荐系统,及我们的RL-based算法。

对于每个用户,我们考虑一个关于用户历史交互行为的序列,它会记录下由推荐系统的动作(actions,比如:视频推荐)、用户反馈(比如:点击和观看时长)。给定这样一个序列,我们会预测下一个发生的动作(action:比如:视频推荐),以便提升用户满意度指标(比如:点击、观看时长)。

我们将该过程翻译成一个马尔可夫决策过程(Markov Decision Process: MDP)\((S, A, P, R, \rho_0, \gamma)\),其中:

  • S:用于描述用户状态(user states)的一个连续状态空间(state space)
  • A:一个离散的动作空间(action space),它包含了推荐可提供的items
  • \(P: S \times A \times S \rightarrow R\):是一个状态转移概率
  • \(R: S \times A \rightarrow R\):回报函数(reward function),其中\(r(s,a)\)是立即回报(immediate reward),它通过在用户状态(user state)s上执行动作a得到
  • \(\rho_0\):初始state分布
  • \(\gamma\):对于future rewards的discount factor

我们的目标是:寻找一个policy \(\pi(a \mid s)\)(它会将一个在item上的分布转化成:基于用户状态\(s \in S\)的条件来推荐\(a \in A\)),以便最大化由推荐系统获得的期望累积回报(expected cumulative reward)

\[max_{\pi} E_{\tau \sim \pi} [R(\tau)], where \ R(\tau) = \sum\limits_{t=0}^{|\tau|} r(s_t, a_t)\]

这里,在轨迹(trajectories) \(\tau = (s_0, a_0, s_1, \cdots)\)上采用的期望,它通过根据policy: \(s_0 \sim \rho_0, a_t \sim \pi(\cdot \mid s_t), s_{t+1} \sim P(\cdot \mid s_t, a_t)\)来获得。

提供了不同族的方法来解决这样的RL问题:Q-learning[38], Policy Gradient[26,36,48]以及黑盒优化(black box potimization)[15]。这里我们主要关注policy-gradient-based方法,比如:REINFORCE[48]。

我们假设:policy的一个函数形式为\(\pi_\theta\),参数为\(\theta \in R^d\)。根据各policy参数的期望累积回报(expected cumulative reward)的梯度,可以通过”log-trick”的方式进行解析法求导,生成以下的REINFORCE梯度:

\[E_{\tau \sim \pi_\theta} [R(\tau) \nabla_\theta log \pi_{\theta} (\tau)]\]

…(1)

在online RL中,policy gradient由正在更新的policy生成的轨迹(trajectories)上计算得到,policy gradient的估计是无偏的,可以分解成:

\[\sum_{\tau \sim \pi_{\theta}} R(\tau) \nabla_{\theta} log \pi_{\theta}(\tau) \approx \sum_{\tau \sim \pi_{\theta}} [ \sum_{t=0}^{|\tau|} R_t \nabla_{\theta} log \pi_{\theta} (a_t | s_t)]\]

…(2)

对于一个在时间t上的动作(action),通过使用一个discouted future reward \(R_t = \sum\limits_{t'=t}^{\mid \tau \mid} \gamma^{t'-t} r(s_{t'}, a_{t'})\)将替换\(R(\tau)\)得到的该近似结果,可以减小在梯度估计时的方差(variance)。

4.off-policy collrection

由于学习和基础设施的限制,我们的学习器(learner)没有与推荐系统的实时交互控制,这不同于经典的增强学习。换句话说,我们不能执行对policy的在线更新,以及立即根据updated policy来生成轨迹(trajectories)。作为替代,我们会接收的的关于actions的日志反馈由一个历史policy(或者一个policies组合)选中,它们在action space上会具有一个与正在更新的policy不同的分布。

我们主要关注解决:当在该环境中应用policy gradient方法时所带来的数据偏差。特别的,在生产环境中在部署一个新版本的policy前,我们会收集包含多个小时的一个周期性数据,并计算许多policy参数更新,这意味着我们用来估计policy gradient的轨迹集合是由一个不同的policy生成的。再者,我们会从其它推荐(它们采用弹性的不同policies)收集到的成批的反馈数据中学习。一个navie policy gradient estimator不再是无偏的,因为在等式(2)中的gradient需要从updated policy \(\pi_\theta\)中抽取轨迹(trajectories),而我们收集的轨迹会从一个历史policies \(\beta\)的一个组合中抽取

我们会使用importance weighting[31,33,34]的方法来解决该分布不匹配问题(distribution)。考虑到一个轨迹 \(\tau=(s_0,a_0,s_1,...)\),它根据一个行为策略\(\beta\)抽样得到,那么off-policy-corrected gradient estimator为:

\[\sum_{\tau \sim \beta} \frac{\pi_{\theta}(\tau)}{\beta(\tau)} [\sum_{t=0}^{|\tau|} R_t \nabla_{\theta} log(\pi_{\theta} (a_t | s_t))]\]

其中:

\[\frac{\pi_{\theta}(\tau)}{\beta(\tau)} = \frac{\rho(s_0) \prod_{t=0}^{|\tau|} P(s_{t+1}|s_t, a_t) \pi(a_t|s_t)}{\rho(s_0) \prod_{t=0}^{|\tau|} P(s_{t+1}|s_t, a_t) \beta(a_t | s_t)} = \prod_{t=0}^{|\tau|} \frac{\pi(a_t | s_t)}{\beta(a_t | s_t)}\]

是importance weight。该correction会生成一个无偏估计器(unbiased estimator),其中:轨迹(trajectories)会使用根据\(\beta\)抽样到的actions进行收集得到。然而,由于链式乘积(chained products),该estimator的方差是很大的,这会快速导致非常低或非常高的importance weights值

为了减少在时间t时该轨迹上的每个gradient项的方差,我们会首先忽略在该链式乘法中时间t后的项,并在将来时间采用一个一阶近似来对importance weights进行近似:

\[\prod_{t'=0}^{|\tau|} \frac{\pi(a_{t'} | s_{t'})}{\beta(a_{t'} | s_{t'})} \approx \prod_{t'=0}^{t} \frac{\pi(a_{t'} | s_{t'})}{\beta(a_{t'}|s_{t'})} = \frac{P_{\pi_{\theta}}(s_t)}{P_{\beta}(s_t)} \frac{\pi(a_t | s_t)}{\beta(a_t|s_t)} \approx \frac{\pi(a_t|s_t)}{\beta(a_t | s_t)}\]

这会产生一个具有更低方差的关于policy gradient的有偏估计器(biased estimator):

\[\sum_{\tau \sim \beta} [\sum_{t=0}^{|\tau|} \frac{\pi_{\theta} (a_t |s_t)}{\beta(a_t | s_t)} R_t \nabla_{\theta} log \pi_{\theta} (a_t | s_t)]\]

…(3)

Achiam[1]证明了:该一阶近似对于学到的policy上的总回报的影响,会通过\(O(E_{s \sim d^{\beta}} [D_{TV}(\pi \mid \beta)[s]])\)来限定幅值,其中\(D_{TV}\)是在\(\pi(\cdot \mid s)\)和\(\beta(\cdot \mid s)\)间的总方差,\(d^{\beta}\)是在\(\beta\)下的discounted future state分布。该estimator会权衡精确的off-policy correction的方差,并仍能为一个non-corrected policy gradient收集大的偏差,这更适合on-policy learning。

4.1 对policy \(\pi_{\theta}\)进行参数化

这里有:

  • user state (\(s_t \in R^n\)): 我们对每个时间t上的user state建模,这可以同时捕获用户兴趣的演进,它使用n维向量\(s_t \in R^n\)来表示。
  • action (\(u_{a_t} \in R^m\)): 沿着该轨迹(trajectory)每个时间t上的action会使用一个m维向量\(u_{a_t} \in R^m\)进行嵌入。

我们会使用一个RNN [6, 49]来建模状态转移\(P: S \times A \times S\):

\[s_{t+1} = f(s_t, u_{a_t})\]

我们使用了许多流行的RNN cells(比如:LSTM, GRU)进行实验,最终使用一个简单的cell,称为:Chaos Free RNN (CFN)[24],因为它的稳定性和计算高效性。该state会被递归更新:

\[s_{t+1} = z_t \odot tanh(s_t) + i_t \odot tanh(W_a u_{a_t}) \\ z_t = \sigma(U_z s_t + W_z u_{a_t} + b_z) \\ i_t = \sigma(U_i s_t + W_i u_{a_t} + b_i)\]

…(4)

其中:

  • \(z_t \in R^n\)是update gate
  • \(i_t \in R^n\)是input gate

考虑到一个user state s, policy \(\pi_{\theta}( a \mid s)\)接着使用一个简单的softmax进行建模:

\[\pi_{\theta}(a | s) = \frac{exp(s^{\top} v_a / T)}{\sum\limits_{a' \in A} exp(s^{\top} v_{a'} / T)}\]

…(5)

其中:

  • \(v_a \in R^n\)是每个action a在action space A中的另一个embedding(注:前面的\(u_{a_t} \in R^m\)是m维,而\(v_a\)是与\(s_t\)相同维度)
  • T是时序(通常设置为1)。T值越大会在action space上产生一个更平滑的policy。

在softmax中的归一化项需要检查所有可能的动作,在我们的环境中有数百万量级。为了加速计算,我们会在训练中使用sampled softmax。在serving时,我们使用一个高效的最近邻查寻算法来检索top actions,并使用这些actions来近似softmax概率,如第5节所述。

总之,policy \(\pi_{\theta}\)的参数\(\theta\)包含了:

  • 两个action embeddings:\(U \in R^{m \times \mid A \mid}\)和\(V \in R^{n \times \mid A \mid}\),
  • 在RNN cell中的权重矩阵:\(U_z, U_i \in R^{n \times n}, W_u, W_i, W_a \in R^{n \times m}\)
  • biases:\(b_u, b_i \in R^n\)

图1展示了一个描述main policy \(\pi_{\theta}\)的神经网络架构。给定一个观察到的轨迹 \(\tau = (s_0, a_0, s_1, ...)\),它从一个行为策略(behavior policy)\(\beta\)中抽样得到,该新策略(new policy)首先会生成一个关于user state \(s_{t+1}\)的模型,它使用一个initial state \(s_0 \sim \rho_0\)并通过等式(4)的recurrent cell迭代得到。给定user state \(s_{t+1}\),policy head会通过等式(5)的softmax来转化在action space分布。有了\(\pi_{\theta}(a_{t+1} \mid s_{t+1})\),我们接着使用等式(3)生成一个policy gradient来更新该policy。

图1 该图展示了policy \(\pi_{\theta}\)的参数变量(parametrisation)以及behavior policy \(\beta_{\theta'}\)

4.2 估计behavior policy \(\beta\)

伴随等式(3)的off-policy corrected estimator出现的一个难题是:得到behavior policy \(\beta\)。理想状态下,对于一个选中action的日志反馈(logged feedback),我们希望也能记录(log)下选中该action的behavior policy概率。直接记录该behavior policy在我们的情况下是不可行的,因为:

  • (1) 在我们的系统中有许多agents,许多是不可控的
  • (2) 一些agents具有一个deterministic policy,将\(\beta\)设置成0或1并不是使用这些日志反馈(logged feedback)的最有效方式

作为替代,我们采用[39]中首先引入的方法,并估计行为策略\(\beta\),在我们的情况中\(\beta\)是在系统中一个多种agents的policies的混合(它们使用logged actions)。给定一个logged feedback集合 \(D = \lbrace (s_i, a_i), i=1, \cdots, N \rbrace\),Strehlet[39]会以不依赖user state的方式,通过对整个语料的action频率进行聚合来估计\(\hat{\beta}(a)\)。作为对比,我们会采用一个依赖上下文(context-dependent)的neural estimator。对于收集到的每个state-action pair(s, a),我们会估计概率\(\hat{\beta}_{\theta'}(a \mid s)\),它指的是该behavior policies的混合体来选中该action的概率,使用另一个softmax来计算,参数为\(\theta'\)。如图1所示,我们会复用该user state s(它由main policy的RNN model生成),接着使用另一个softmax layer来建模该mixed behavior policy。为了阻止该behavior head干扰到该main policy的该user state,我们会阻止该gradient反向传播回该RNN。我们也进行了将\(\pi_{\theta}\)和\(\beta_{\theta'}\)的estimators分离开的实验,由于会计算另一个state representation,这会增加计算开销,但在离线和在线实验中不会产生任何指标提升。

尽管在两个policy head \(\pi_{\theta}\)和\(\beta_{\theta'}\)间存在大量参数共享,但两者间还是有两个明显的不同之处

  • (1) main policy \(\pi_{\theta}\)会使用一个weighted softmax来考虑长期回报(long term reward)进行有效训练;而behavior policy head \(\beta_{\theta'}\)只会使用state-action pairs进行训练(言下之意,不考虑reward?)
  • (2) main policy head \(\pi_\theta\)只使用在该trajectory上具有非零回报(non-zero reward)的items进行训练(注3);而behavior policy \(\beta_{\theta'}\)使用在该轨迹上的所有items进行训练,从而避免引入在\(\beta\)估计时的bias

注3:1.具有零回报(zero-reward)的Actions不会对\(\pi_{\theta}\)中的梯度更新有贡献;2.我们会在user state update中忽略它们,因为用户不可能会注意到它们,因此,我们假设user state不会被这些actions所影响 3.它会节约计算开销

在[39]中是有争议的:一个behavior policy(在给定state s,在time \(t_1\)上的它会确定式选中(deterministically choosing)一个action a;在time \(t_2\)上选中action b),可以看成是:在日志的时间间隔上,在action a和action b间的随机化(randomizing)。这里,我们在同一点上是有争议的,这也解释了:给定一个deterministic policy,为什么behavior policy可以是0或1。另外,由于我们有多个policies同时进行acting,在给定user state s的情况下,如果一个policy会确定式选中(determinstically choosing)action a,另一个policy会确定式选中action b,那么,以这样的方式估计\(\hat{\beta}_{\theta'}\)可以近似成:在给定user state s下通过这些混合的behavior policies,action a被选中的期望频率(expected frequency)。

4.3 Top-K off-policy Correction

在我们的setting中存在的另一个挑战是:我们的系统一次会推荐一个包含k个items的页面给用户。由于用户会浏览我们的推荐(整个集合或部分集合),并与一个以上的item存在潜在交互,我们需要选择一个相关items集合(而非单个item)。换句话说,我们会寻找一个policy \(\prod\limits_{\theta} (A \mid s)\),这样每个action A会选择一个关于k个items的集合,来最大化期望累积回报(expected cumulative reward):

\[max_{\theta} E_{\tau \sim \prod_{\theta}} [ \sum\limits_t r(s_t, A_t)]\]

轨迹(trajectory) \(\tau = (s_0, A_0, s_1, \cdots)\)会通过根据 \(s_0 \sim \rho_0, A_t \sim \prod(\mid s_t), s_{t+1} \sim P(\cdot \mid s_t, A_t)\) 进行acting来获得。不幸的是,动作空间(action space)在该集合推荐公式下是指数级增长,在给定items数时这会过大(从阶数为百万级的语料中选择items)。

为了让该问题可跟踪,我们假设:一个无重复(non-repetitive) items的集合的期望回报(expected reward)等于在集合中每个item的expected reward的和(该假设仍会认为:用户会独立地检查每个item)。更进一步,我们通过对每个item a根据softmax policy \(\pi_\theta\)进行独立抽样,接着进行去重来限制生成action A集合。也就是:

\[\prod_{\theta}(A' | s) = \prod\limits_{a \in A'} \pi_{\theta} (a | s)\]

注意:集合\(A'\)会包含重复的items,可以移除重复项来形成一个无重复的集合A。

在这些假设下,我们可以对该集合推荐setting采用REINFORCE算法,将在等式(2)的梯度更新修改为:

\[\sum_{\tau \sim \pi_\theta} [ \sum_{t=0}^{|\tau|} R_t \nabla_{\theta} log \alpha_{\theta} (a_t | s_t)]\]

其中:

  • \(\alpha_{\theta} (a \mid s) = 1 - (1- \pi_{\theta}(a \mid s))^K\):表示的是一个item a出现在最终的无重复集合A中的概率。这里,\(K = \mid A'\mid >\mid A\mid = k\)。(注:作为有放回(replacement)和去重(de-duplicate)抽样的结果,最终集合A的size是可变的)

我们接着更新等式(3)中的off-policy corrected gradient,通过使用\(\alpha_{\theta}\)替代\(\pi_{\theta}\),生成top-K off-policy correction factor:

\[\sum_{\tau \sim \beta} [ \sum_{t=0}^{|\tau|} \frac{\alpha_{\theta} (a_t |s_t)}{\beta(a_t|s_t)} R_t \nabla_{\theta} log \alpha_{\theta} (a_t | s_t)] \\ = \sum_{\tau \sim \beta} [\sum_{t=0}^{|\tau|} \frac{\pi_{\theta}(a_t|s_t)}{\beta(a_t|s_t)} \frac{\partial \alpha(a_t|s_t)}{\partial \pi(a_t|s_t)} R_t \nabla_{\theta} log \pi_{\theta} (a_t | s_t)]\]

…(6)

对比等式(6)和等式(3),top-K policy会增加一个额外的乘子\(\lambda_K(s_t, a_t)\)到original off-policy correction factor的\(\frac{\pi(a \mid s)}{\beta(a \mid s)}\)中:

\[\lambda_K(s_t, a_t) = \frac{\partial \alpha(a_t | s_t)}{\partial \pi(a_t | s_t)} = K(1-\pi_{\theta} (a_t | s_t))^{K-1}\]

…(7)

现在,我们回顾下该额外乘子:

  • 随着\(\pi_{\theta}(a\mid s) \rightarrow 0, \lambda_K(s,a) \rightarrow K\)。对比起标准的off-policy correction,top-K off-policy correction会通过一个K因子来增加policy update;
  • 随着\(\pi_{\theta}(a \mid s) \rightarrow 1, \lambda_K(s,a) \rightarrow 0\)。该乘子会使policy update归0
  • 随着K的增加,以及\(\pi_{\theta}(a \mid s)\)会达到一个合理的范围, 该乘子会更快地将graident减小于0

总之,当期望的item在softmax policy \(\pi_{\theta}(\cdot \mid s)\)具有一个很小的量,比起标准的correction,top-K correction会更可能推高它的likelihood。一旦softmax policy \(\pi_{\theta}(\cdot \mid s)\)在期望的item上转化成一个合理的量(以确认它可能出现在top-K中),correction接着会将梯度归0, 不再尝试推高它的似然。作为回报,它允许其它感兴趣的items在softmax policy中占据一定的量。我们会在仿真和真实环境中进一步演示,而标准的off-policy correction会收敛到一个当选择单个item时最优的policy,top-K correction会产生更好的top-K推荐。

4.4 Variance Reduction技术

在本节开始,我们会采用一个一阶近似来减小在梯度估计时的方差(Variance)。尽管如此,梯度仍会有较大的方差,因为等式(3)中展示的\(\omega(s,a) = \frac{\pi(a \mid s)}{\beta(a \mid s)}\)具有很大的importance weight,这与top-K off-policy correction相类似。具有较大值的importance weight是因为由(1)中来自behavior policy的new policy \(\pi(\cdot \mid s)\)的导数具有较大值所产生,特别的,new policy会探索那些被behavior policy很少探索过的区域。也就是说,\(\pi(a \mid s) \gg \beta(a \mid s)\)和(2)在\(\beta\)估计中有大的方差

我们测试了在counterfactual learning和RL文献中提出的许多技术来控制在梯度估计时的方差。大多数这些技术会减小方差,但在梯度估计时会引入一些bias。

Weight Capping。

我们测试的第一种方法会简单的将weight设置上限

\[\omega_c(s,a) = min(\frac{\pi(a|s)}{\beta(a|s)}, c)\]

…(8)

c的值越小,会减小在梯度估计时的方差,但会引入更大的bias。

NIS(归一化重要性抽样:Normalized Importance Sampling)

我们使用的第二种技术是引入一个ratio来控制变量,其中我们使用经典的权重归一化,如下:

\[\bar{\omega}(s, a) = \frac{w(s,a)}{\sum\limits_{(s',a') \sim \beta} w(s', a')}\]

由于\(E_{\beta}[w(s,a)] = 1\),归一化常数等于n,batch size在预期之中。随着n的增大,NIS的效果等价于调低learning rate。

TRPO(Trusted Region Policy Optimization). TRPO会阻止new policy \(\pi\)背离behavior policy,它通过增加一个正则项来惩罚这两个policies的KL散度。它会达到与weight capping相似的效果。

5.探索(EXPLORATION)

有一点很明确:训练数据的分布对于学习一个好的policy来说很重要。现有的推荐系统很少采用会询问actions的探索策略(exploration policies),这已经被广泛研究过。实际上,暴力探索(brute-force exploration),比如:\(\epsilon-greedy\),对于像Youtube这样的生产系统来说并不是可行的,这很可能产生不合适的推荐和一个较差的用户体验。例如,Schnabel【35】研究了探索(exploration)的代价。

作为替代,我们使用Boltzmann exploration[12]来获取探索数据(exploratory data)的收益,不会给用户体验带来负面影响。我们会考虑使用一个随机policy,其中推荐会从\(\pi_{\theta}\)中抽样,而非采用最高概率的K个items。由于计算低效性(我们需要计算full softmax),这对于考虑我们的action space来说开销过于高昂。另外,我们会利用高效的ANN-based系统来查询在softmax中的top M个items。我们接着会feed这些M个items的logits到一个更小的softmax中来归一化该概率,接着从该分布中抽样。通过设置\(M \gg K\),我们仍可以检索大多数概率块,限制了生成坏的推荐的风险,并允许计算高效的抽样。实际上,我们会通过返回top \(K'\)个最大概率的items,以及从剩余的\(M-K'\)个items中抽取\(K-K'\)个items,来进一步平衡exploration和exploitation

6.实验结果

我们展示了:在一个工业界规模的推荐系统中,在一系列仿真实验和真实实验中,这些用于解决数据偏差(data biases)的方法的效果。

6.1 仿真

我们设计了仿真实验来阐明:在更多受控环境下off-policy correction的思想。为了简化我们的仿真,我们假设:该问题是无状态的(stateless),换句话说,reward R与user states是相互独立的,action不会改变user states。作为结果,在一个trajectory上的每个action可以被独立选中。

6.1.1 off-policy correction

在第一个仿真中,我们假设存在10个items:\(A=\lbrace a_i, i=1, \cdots, 10 \rbrace\)。每个action的reward等于它的index,也就是说:\(r(a_i)=i\)(可以理解成按reward大小排好序)。当我们选中单个item时,在该setting下最优的policy总是会选中第10个item(因为它的reward最大),也就是说:

\[\pi^* (a_i) = I(i=10)\]

我们使用一个无状态的softmax来对\(\pi_{\theta}\)参数化:

\[\pi(a_i) = \frac{e^{\theta_i}}{\sum_j e^{\theta_j}}\]

如果observations是从behavior policy \(\beta\)中抽样得到的,那么等式(1)中不对数据偏差负责的naively使用policy gradient的方式,会收敛到以下的一个policy:

\[\pi(a_i) = \frac{r(a_i)\beta(a_i)}{\sum_j r(a_j) \beta(a_j)}\]

这具有一个明显的缺点(downside):behavior policy越选择一个次优(sub-optimal)的item,new policy越会朝着选择相同的item偏移

图2: 当behavior policy \(\beta\)倾向于喜欢最小reward的actions时,(比如:\(\beta(a_i)=\frac{11-i}{55}, \forall i = 1, \cdots, 10\)),所学到的policy \(\pi_{\theta}\),(左):没有使用off-policy correction; (右): 使用off-policy correction

这里我附上了我的理解代码(本节的目的,主要是为说明:当存在behavior policy倾向喜欢选择较小reward actions时,不使用off-policy correction效果会差):

1
2
3
4
5
6
7
8
actions = [1,2,3,4,5,6,7,8,9,10]
b = lambda x: (11-x)/55.0
beta = [b(i) for i in actions]
rxb = [(i+1)*j for i, j in enumerate(beta)]
total = sum(rxb)
pi = [i/total for i in rxb]

图2比较了:当behavior policy \(\beta\)倾向于最少回报的items,分别使用/不使用 off-policy correction及SGD所学到的policies \(\pi_{\theta}\)。如图2(左)所示,没有对数据偏差负责naivly使用behavior policy的方式,会导致一个sub-optimal policy。在最坏的case下,如果behavior policy总是选择具有最低回报的action,我们将以一个任意差(poor)的policy结束,并模仿该behavior policy(例如:收敛到选择最少回报的item)。另外一方面,使用off-policy correction则允许我们收敛到最优policy \(\pi^*\),无需关注数据是如何收集的,如图2(右)。

6.1.2 Top-K-policy correction

为了理解标准off-policy correction和top-K off-policy correction间的不同,我们设计了另一个仿真实验,它可以推荐多个items。我们假设有10个items,其中\(r(a_1)=10, r(a_2)=9\),具有更低reward的其余items为:\(r(a_i)=1, \forall i=3,\cdots,10\)。这里,我们关注推荐两个items的问题,即K=2。 behavior policy \(\beta\)会符合一个均匀分布(uniform distribution),例如:以平等的机率选择每个item。

给定从\(\beta\)中抽样到的一个observation \((a_i, r_i)\),标准的off-policy correction具有一个SGD,以如下形式进行更新:

\[\theta_j = \theta_j + \eta \frac{\pi_{\theta}(a_j)}{\beta(a_j)} r(a_i) [ I(j=i) - \pi_{\theta}(a_j)] , \forall j = 1, \cdots, 10\]

其中,\(\eta\)是learning rate。SGD会根据在\(\pi_\theta\)下的expected reward的比例继续增加item \(a_i\)的似然(likelihood),直到\(\pi_{\theta}(a_i)=1\),此时的梯度为0。换句话说,top-K off-policy correction以如下形式进行更新:

\[\theta_j = \theta_j + \eta \lambda_K(a_i) \frac{\pi_\theta(a_j)}{\beta(a_j)} r(a_i) [I(j=i) - \pi_{\theta}(a_j)], \forall j=1, \cdots, 10\]

其中,\(\lambda_K(a_i)\)是在第4.3节定义的乘子。当\(\pi_{\theta}(a_i)\)很小时,\(\lambda_K(a_i) \approx K\),SGD会更强烈地增加item \(a_i\)的似然。由于\(\pi_\theta(a_i)\)会达到一个足够大的值,\(\lambda_K(a_i)\)会趋向于0. 作为结果,SGD不再强制增加该item的likelihood,即使当\(\pi_\theta(a_i)\)仍小于1时。作为回报(in return),这会允许第二好(second-best)的item在所学到的policy上占据一些位置。

图3 学到的policy \(\pi_{\theta}\). (左): 标准的off-policy correction; (右): 对于top-2推荐,使用top-k correction.

图3展示了使用标准(left) off-policy correction和top-k off policy correction)(右)学到的policies \(\pi_{\theta}\)。我们可以看到,使用标准的off-policy correction,尽管学到的policy会校准(calibrated),从某种意义上说,它仍会维持items关于expected reward的顺序,它会收敛到一个policy:它能在top-1 item上将整个mass转换(cast),也就是:\(\pi(a_1) \approx 1.0\)。作为结果,学到的policy会与在次优item(本例中的\(a_2\))和其余items间的差异失去联系。换句话说,该top-K correction会收敛到一个在第二优item上具有较大mass的policy,而维持在items间optimality的次序。作为结果,我们可以推荐给用户两个高回报(high-reward) items,并在整体上聚合更多reward。

6.2 真实环境

具有仿真实验对于理解新方法有价值,任何推荐系统的目标最终都是提升真实用户体验。我们因此在真实系统中运行A/B test实验。

我们在Youtube中所使用的生产环境上的 RNN candidate genreation model上评估这了些方法,相似的描述见[6,11]。该模型是生产环境推荐系统的众多候选生成器(candidate generators)之一,它们会进行打分(scored)然后通过一个独立的ranking模型进行排序(ranked),之后再在Youtube主页或视频观看页的侧边栏上展示给用户视频。如上所述,该模型的训练会采用REINFORCE算法。该立即回报(immediate reward) r被设计来体现不同的用户活动(user activities);被推荐的视频如果没有点击会收到零回报(zero reward)。长期回报(long-term reward)r会在4-10小时的时间范围内进行聚合。在每个实验中,控制模型(control model)和测试模型(test model)会使用相同的reward function。实验会运行许多天,在这期间模型会每隔24小时使用新事件作为训练数据进行持续训练。我们可以查看推荐系统的多种在线指标,我们主要关注用户观看视频时长,被称为:ViewTime。

这里的实验描述了在生产系统中的多个顺序提升。不幸的是,在这样的setting中,最新(latest)的推荐系统会为下一次实验提供训练数据,结果是,一旦生产系统包含了一个新方法,后续的实验就不能与之前的系统相进行比较。因此,后续的每个实验都应该看成是为每个(compoenent)单独分析,我需要在每一部分声明:在从新方法接收数据起,之前的推荐系统是什么。

6.2.1 Exploration

我们开始理解探索数据(exploratory data)在提升模型质量上的价值。特别的,我们会measure是否服务(serving)一个随机策略(stochastic policy),在该policy下我们使用在第5节中描述的softmax模型进行抽样,可以比serving一个确定策略(deterministic policy)(这种模型总是推荐根据softmax使用最高概率的K个items)来产生成好的推荐。

我们开展了一系列实验来理解:serving一个随机策略(stochastic policy) vs. serving一个确定策略(deterministic policy)的影响,并保持训练过程不变。在该实验中,控制流量(control polulation)使用一个deterministic policy进行serving,测试流量(test traffic)的一小部分使用第5节描述的stochastic policy进行serving。两种policies都基于等式(2)相同softmax model进行训练。为了控制在serving时stochastic policy的随机量,我们使用等式(5)的不同时间(temperature) T来区分。T值越低,会将stochastic policy降为一个deterministic policy,而一个更高的T会产生一个random policy,它以相等的机会推荐任意item。T设置为1, 我们可以观察到,在实验期间ViewTime在统计上没有较大变化,这意味着从sampling引入的随机量不会直接伤害用户体验。

然而,该实验的setup不会说明,在训练期间提供探索数据的好处。从日志数据中学习的一个主要偏差之一是,该模型不会观察未被之前推荐policy所选中actions的反馈(feedback),对数据进行探索会缓和该问题。我们展开了以下实验,其中,我们将探索数据引入到训练中。为了这样做,我们将平台上的用户分成三个buckets:90%,5%,5%。前两个buckets使用一个deterministic policy并基于一个deterministic model进行serving,最后一个bucket的用户使用一个基于一个使用exploratory data训练的模型得到的stochastic policy进行serving。deterministic model只使用由前两个分桶的数据进行训练,而stochastic model则使用第一和第三个buckets的数据进行训练。这两个模型会接收相同量的训练数据,结果表明,由于存在exploration,stochastic model更可能观察到一些更罕见state、action pairs的结果。

根据该实验过程,我们观察到在test流量中,在ViewTime上一个很大的增长。尽管提升并不大,它由一个相当小量的探索数据(只有5%的用户体验了该stochastic policy)所带来。我们期待stochastic policy被全量后所能带来的更高增益。

6.2.2 Off-policy Correction

在使用一个stochastic policy之后,我们会在训练期间对合并进的(incorporating)off-policy correction进行测试。这里,我们遵循一个更传统的A/B testing setup【注6】,我们会训练两个模型,它们均会使用所有流量。控制模型(control model)会根据等式(2)进行训练,通过reward对样本进行加权。测试模型(test model)会遵循图1的结构,其中该模型会同时学习一个serving policy \(\pi_\theta\)以及behavior policy \(\beta_{\theta}'\)。serving policy会使用等式(3)描述的off-policy correction进行训练,其中每个样本会同时使用reward以及importance weight \(\frac{\pi_\theta}{\beta_{\theta}'}\)进行加权来解决数据偏差。

【注6】:实际中,我们使用一个相当小比例的用户做为test polulation;作为结果,我们记录的feedback则几乎通过control model获取

在实验期间,我们观察到,学到的policy(test)会开始偏离behavior policy(control)(它被用于获取流量)。图4画出了:根据在控制流量中视频的排序(rank),对应在control/experiment流量中nominator所选中的视频(videos)的CDF(累积分布函数)(rank 1是由控制模型最可能指定的视频,最右表示最小可能指定)。我们看到,test model并不会模仿收集数据所用的模型(如蓝色所示),test model(绿色所示)会更喜欢那些被control model更少曝光的视频。我们观察到:来自top ranks之外视频的nominations的比例,在experiment流量中以几倍的因子递增。这与我们在图2仿真中观察到的现象一致。当忽略在数据收集过程中的偏差时,会创建一个“rich get richer”现象,其中,在学到的policy所指定(nominated)的一个视频,会只因为它在behavior policy上很难指定,采用off-policy correction可以减小该效应。

图4: 根据在control population中视频的排序(rank),在control 和test population中nominated的视频的CDF。标准的off-policy correction会解决”rich get richer”现象

有意思的是,在真实环境中,我们不会观察到control和test 流量(polulation)间在ViewTime上有一个大的改变。然而,我们看到,在视频观看(vv)数上有0.53%的提升,这在统计上是很大的,表明用户确实获得了更大的enjoyment。

6.2.3 top-k off-policy

理解超参数

最后,我们直接比较了超参数的不同选择对top-k off-policy correction的影响,以及在用户体验上的不同。我们会在top-k off-policy correction成为生产模型之后执行这些测试。

actions数目

我们首先探索了在top-K off-policy correction中K的选择。我们训练了三个结构相同的模型,分别使用:\(K \in \lbrace 1,2,16,32 \rbrace\)。控制(生产)模型(control(production) model)是top-K off-policy model,它使用K=16. 我们在图5中绘制了在5天实验中的结果。如第4.3节所示,K=1时,top-K off-policy correction会变成标准的off-policy correction。当K=1时,会失去0.66%的ViewTime(对比baseline K=16)。这进一步证明,该收益是由top-K off-policy correction带来的。设置K=2时,效果比生产模型还差,但gap降到了0.35%。K=32时效果与baseline相当。K=8时,有+0.15%的提升。

Capping

这里,我们在所学推荐器的最终质量上考虑了variance reduction技术。如4.4节所述,weight capping可以在初始实验中带来最大的online收益。我们不会观察到从归一化importance sampling或TRPO中进一步的metric提升。我们使用一个回归测试来学习weight capping的影响。我们比较了一个模型,它使用等式(8)中cap \(c=e^3\),以及\(c=e^5\)进行训练。正如我们在importance weight上提出的限制,学到的policy \(\pi_\theta\)可以潜在overfit到一个更少记录的actions,它们可能接收高的reward。在真实实验中,我们观察到使用importance weight在ViewTime中有0.52的损失。

参考