Heterogeneous Feeds predict优化介绍

Reading time ~2 minutes

ali在2018年前提的一个《An End-to-end Model of Predicting Diverse Ranking On Heterogeneous Feeds》,我们来看下它的实现。

介绍

图片名称

图1 Item Search Engine和Content Search Engine间的关系

2.基本概念

2.1 商业背景

alibaba自己拥有CSE(Content Search Engine)和ISE(Item Search engine),它会相互交互来为用户创建在线购物环境。在ISE中的所有items与CSE中的一群feed相关。用户可以自由地travel和search在两个搜索引擎。

阿里巴巴ISE和CSE的混合使用,对用户在线购物有收益。总之,用户会在阿里巴巴上日志化,他们与搜索引擎的交互总是有意图的。然而,当面对大量items时,如果他们只搜索在ISE中的items,他们可能会迷茫。例如,阿里的官网,像服装这样的热门品类可能包含上万的items。每个items会使用数十个keywords进行打标记(比如:风格、slim cut、韩版等)。如果没有任意指导,用户们从一个item候选的大集合中区分合适的items是面临挑战的。

因此,为了帮助用户避免疑惑,并提供它们可靠的购物建议,CSE会成为用户的购物指导。给定来自用户的queries,CSE会组织一个合适的feed ranking list作为一个返回结果,替代item ranking list。feeds可以被表示成post(article)、list(item list)以及video的形式。他们由电商领域(clothing、travelling、化妆品)专家的”淘宝达人(Daren)”生产。在它们的feeds流量,“达人”会介绍特定items的优点和缺点,并对特定subjects基于它们的领域知识提出个人建议。

  • 一个post feed是一篇文章,它会介绍特定items的属性;
  • 一个list feed是一个推荐items的集合;
  • 一个video feed是一个用来演示建议items的short video。

通过达人的建议,用户可以做出更好的购物选择。

每天在生产环境中的数据会经验性地展示在两个搜索引擎间的user travel rate是否频繁。在用户跳到CSE中前,他们通常已经在ISE中搜索过记录。这表明用户实际上希望购买来自“达人”的建议。提供更好的CSE搜索结果可以帮助用户更方便的定向到合适的items,从而做出之后的购买,这是电商的主要目标。然而,仍然有挑战。首先,feed types是异构的,不同类型的feeds的匹配度(fitness)与一个给定的query是不可比的。例如,一个list feed是否比一个post feed更好依赖于用户体验。第二,大量用户进入阿里CSE会携带着来自ISE的用户行为。如何处理跨域信息并构建user profiles来形成一个在CSE上的个性化feed ranking需要进一步探索。

2.2 数据准备

在我们的方法中,我们的目标是:给定一个user u发起的一个query q,返回一个异构feed ranking list \(R_1(feed) \mid u, q\)

在Top K个ranked feed中的每个item都会被安置(locate),并在CSE中从上到下分别在一个”slot”中展示。为了学习independent Multi-armed Bandit(iMAB)模型以及personalized Markov DNN(pMDNN)模型,需要获取slot相关的统计数据(全局信息)以及用户点击流数据(个性化信息)这两者。

2.2.1 slot相关的统计数据

用户偏好的一个假设是:在每个slot中的feed type相互独立

对于每个slot,三个候选feed types的概率(post、list、video)会遵循它们自己的Beta分布。因此,给定在一个slot s上的候选类型T,为了估计一个feed type \(\theta\)的先验分布\(p(\theta \mid \alpha, \beta, T, s)\),必须知道每个slot的所有slot相关统计信息,以便估计\(\alpha\)和\(\beta\)。slot相关的统计数据包含了两部分:在线实时数据和离线历史数据。在线实时数据指的是流数据:每天由用户生成的对于一个特定slot type的点击数(click)、曝光数(display)。离线历史数据指的是:过去n天page view(pv)、以及item page view(ipv)的总数。在线天数据是streaming data,只能在实时中观察到。而离线历史数据可以被追踪、并能从仓库中获取。我们会在表1中计算和展示top 5 slots的统计数据。

图片名称

表1 在CSE的top 5 slots上的feed历史数据

从表1中看到,在每个相关slots的pv和ipv的总数会有不同,video feeds在CSE中的top 5 slots很难出现。这表示:从全局上看,用户在不同feed types会偏向不同的feed types。

2.2.2 用户点击流数据

来自ISE和CSE的用户行为序列数据对于训练一个个性化feed ranking结果来说是有用的。为了构建user profile,我们会设置一个window size w,它只考虑用户在ISE上的最新w个行为。该行为可以表示为两种类型的triplet:<user, issue, query>和<user, click, item>。

  • 用户在items上的点击次数表明users和items间的关系,
  • 而用户(users)发起(issue)相同query的次数表明:users和queries间的关系强度。

基于此,可以在相同的latent space上从每个user/query中学习得到一个给定维度的embedding。另外,在每个slot中的feed type通过one-hot encoder进行编码。最后,所有users、queries、feed types可以被表示成vectors。示例如表2所示。前两列指的是每个user \(f_u\)学到的表示,以及一个issued query \(f_q\)。第三列指的是在每个slot中feed type \(f_t\)的one-hot表示。

图片名称

表2 对于每个slot的用户个性化数据的示例

3.方法

对于用户体验,我们希望观察到更好的异构feeds ranking。整个过程包含了Heterogeneous Type Sorting step以及Homogeneous Feed Ranking step。

  • 对于第一个step,对于slot independent场景,会设计一个independent Multi-Armed Bandit(iMAB)模型;
  • 对于slot denpendent场景,会设计一个改进版的personlized Markov DNN(pMDNN)模型。

第3.1节和3.2节会分别引入两个模型。对于第二个step,会使用一个DSSM模型来在每个slot上分配合适类型的feeds。第3.3节会详细介绍,pMDNN可以与DSSM一起训练来构成一个end-to-end模型。

3.1 independent Multi-Armed Bandit

在iMAB模型中,异构feed ranking的评估指标是:在ipv和pv间的ratio \(\theta\)。更高的\(\theta\)意味着:当一个用户浏览在CSE中的一个feed时,用户更可能会点击该feed。因此,\(\theta\)可以根据用户的实际需要来用于评估heterogeneous feed ranking的匹配度(fitness)。因此,对于每个independent slot,我们会为每个feed type估计一个先验ratio \(\theta\)分布,并倾向于选择能够生成最高\(\theta\)值的feed type

理论上,由于Beta分布可以天然地表示成:由两个参数\(\alpha\)和\(\beta\)控制的任意类型的分布,它会假设每个type的ratio \(\theta\)具有一个先验分布遵循:\(\theta_i \sim B(\alpha_i^0, \beta_i^0)\),

其中:

  • \(i \in \mu = \lbrace post, list, video \rbrace\)。
  • \(\alpha_i^0\)是type i的历史ipv数,
  • \(\beta_i^0\)是type i历史pv数和ipv数间的差。

由于\(B(\alpha_i^0, \beta_i^0)\)的期望是:\(\frac{\alpha_i^0}{\alpha_i^0 + \beta_i^0}\),它是ipv和pv间的历史ratio。因此,后验ratio分布可以通过在线实时流数据进行每天更新,表示成:

\[\theta_i \mid D_i \sim B(\alpha_i^0 + \lambda D^{ipv}, \beta_i^0 + \lambda (D^{pv} - D^{ipv}))\]

其中:

  • \(D_i\)指的是每天到来的feed type i
  • \(\lambda\)是时间影响因子,因为新数据会对更新ratio分布有影响。

最终,我们会使用一个two step sampling策略来选择每个slot的type。首先,对于每个feed type i,会被随机生成一个value \(\theta_i\),因为在pv和ipv间的ratio的估计遵循以下的概率分布:

\[p(\theta_i | D_i) = \frac{(\theta_i)^{\alpha_i,-1}(1-\theta_i)^{\beta_i,-1}}{B(\alpha_i, \beta_i,)}\]

…(1)

其中,给定\(\alpha_i\)和\(\beta_i,\),

  • \(B(\alpha_i, \beta_i,)\)是一个常数
  • \[\alpha_i,=\alpha_0+\lambda D_i^{ipv}\]
  • \[\beta_i,=\beta_0 + \lambda(D_i^{pv} - D_i^{ipv})\]

第二,对于每个feed type,会应用一个softmax函数到所有feed types上来生成一个归一化的selection概率:

\[p(i) = \frac{exp(\theta_i)}{\sum_{i \in \mu} exp(\theta_j)}\]

…(2)

其中:

  • i指的是三种feed types的其中之一
  • \(\theta_i\)是公式1展示了根据后验概率分布\(D(\theta)\)生成的随机值

这种方式中,在所有slots中的feed types会独立选中。整个过程的伪代码如算法1所示。

图片名称

算法1

3.2 peronalized Markov DNN

Dependent heterogneous feed type selection会由三个因素决定:user、query、以及在相同page页上之前的slot feed types。

  • 第一,不同users会在相同queries下对于items具有不同的偏好。例如,当一个用户搜索”dress”时,她可能会愿意看到关于dress描述的文章post。而对于其它user,他们可能更喜欢lists,因为他们想看到更多item选项而非单个item介绍。
  • 第二,在当前slot上的feed types的用户偏好可能会受之前feed types的潜在影响,它可以被看成是一个Markov process。例如,没有用户愿意看到在所有slots上看到相同类型,他们或多或少希望看到不同types的feeds。
  • 第三,不同queries在所有slots上应产生不同的feed type allocation。为了将用户偏好、query、以及推荐的previous feed types一起集成,对于第i个slot,我们提出了一个pMDNN模型来生成推荐的feed type \(t_i \mid (user, query, t_1, \cdots, t_{i-1})\)。整个模型可以解耦成两个子任务(sub tasks):包括一个user&query表示学习任务、以及一个personlized slot type的预测任务,如图2所示。

图片名称

图2 使用pMDNN的end-to-end模型,从cross-domain knowledge和user preference中进行学习

3.2.1 User和Query的表示

基于统计数据,在CSE中有80%的用户来自于ISE。因此,通过使用它们的用户行为序列数据,我们可以构建一个graph来描述users、queries、items间的关系。之后,node2vec会在最后使用一个skip gram模型来学习users和queries的embeddings。详细的pipeline如图2所示,目标函数如下:

\[O(\overset{\rightarrow}{f_v}) = log \sigma(\overset{\rightarrow}{f_t} \cdot \overset{\rightarrow}{f_v}) + k E_{u \in P_{noise}} [-log \sigma(\overset{\rightarrow}{f_u} \cdot \overset{\rightarrow}{f_v})]\]

…(3)

其中:

  • \(\overset{\rightarrow}{f_v}\)是当前node v的embedding。
  • t是node v的一个positive neighbour node;
  • u是v的一个negative sampled node。

这意味着:给定一个node v,我们需要学习一个node embedding表示,它可以最大化概率来生成它的positive neighbor node u,并最小化概率来生成它的negative node node sets\(P_{noise}\)。

图2的中间部分表明,如何训练node embedding表示。input layer是node的one-hot encoding。weight matrix W是所有nodes的embedding,它可以帮助将input one-hot encoding node投影到一个\(\mid D \mid\)维的latent space上。接着,最大化概率来生成node u的neighour nodes。

在最后,所有users和queries可以使用一个给定长度维度的embedding representations。并且匀们使用user & query embeddings作为输入来进行slot feed type预测。

3.2.2 Type prediction

对于给定users、queries、以及previous slot feed types信息,我们希望预测每个slot的feed types。因此,目标函数为:

\[\underset{\phi}{argmax} \prod_{i=1}^K p(\phi(X_i) = c | u_i, q_i, f_i)\]

…(4)

其中:

  • \(X_i\)是对于第i个slot的input feature vectors,它与user \(u_i\)、queries \(q_i\)以及previous slot feed types \(f_i\)相关。
  • \(\Phi\)是input feature vectors到output feed type的转换函数。
  • c是当前slot的true feed type。

我们的目标是最大化成功预测slot feed types的joint probability。

为了简化我们的pMDNN模型,并加速运行速度,只有slot feed type的一阶Markov过程会被应用到该模型上。它意味着预测第i个slot feed type,只有第(i-1)个slot feed type会对它有latent影响。而这对于一个user u的第一个slot feed type来说会带来一个问题。因为它没有previous slot feed type信息。对于一个user u,为了给第一个slot生成一个伪信息,user u喜欢的item i会在ISE中根据观看次数和停留时长被检测到。接着,我们会在ISE中将item i映射到在CSE中与它相关的feed f中,并使用f的type作为一个替代。

我们使用给定的user、query的embedding以及previous slot types来构建pMDNN模型来推荐feed type。input layer是user embedding(U)、query embedding(Q)和之前slot types(T)的concatenation。User和query embedding会通过在constructed graph上进行node2vec学到。整个input layer的构建可以看成是:

\[X = U \oplus Q \oplus T\]

…(5)

最后,会在input layer上附加三个fully connected hidden layers。每个layer会使用线性分类器和cross entropy作为loss function。在每个hidden layer中的Activation function被设置为ReLu,output layer会使用Softmax作为activation function。通过gradient descent和BP,我们会训练模型直至收敛。outpu layer是一个vector,它包含了:,在通过一个softmax activation function之后,在每个指定slot上关于三种feed types的一个概率分布。

\[L_1 = ReLu(w_0 \cdot X) \\ L_2 = ReLu(w_1 \cdot L1) \\ L_3 = ReLu(w_2 \cdot L2) \\ L = Softmax(w_3 \cdot L_3)\]

…(6)

L表示当前slot feed type的true label。pMDNN模型会在离线阶段被训练,我们可以管理trained model来预测实时用户请求。\(L_1, L_2, L_3\)分别表示三个hidden layers。图2的第一部分展示了这个工作流。

3.3 异构feed ranking

下一step是对homogeneous feeds进行排序,并填充相关的slots。例如,如果\(slot_i, slot_j, slot_k\)被选中具有”post” feed type,我们需要rank所有post feeds并选择在当前query下具有最高relevance score的top 3 feeds。由于所有types的feeds与文本信息相关(比如:title),会使用一个已经存在的DSSM来对所有post feeds进行rank来在三个slots上进行填充。

在DSSM中,我们不会为每个word会使用一个one-hot表示进行编码,而是使用word hashing方法来利用n-gram模型来分解每个word。这会减小word表示的维度。

最后,一个DNN模型可以使用query和feeds作为input layer,给定跨训练信的queries,并通过最大化点击文档的likelihood进行模型参数训练。相等的,该模型需要最小化以下的loss function:

\[L(\wedge) = -log \prod_{Q, D^+} p(D^ | Q)\]

…(7)

其中,\(\wedge\)表示NN的参数集。\(D^+\)表示具有true label的feed,Q是user-issued query。该模型会使用gradient-based数值优化算法进行训练。

最后,给定一个query,所有candidate feeds可以通过由该模型计算的generative probability进行排序。它可以使用pMDNN进行训练来公式化成一个end-to-end模型,如图2所示。而它仍需要从iMAB模型进行训练得到。

4.实验

我们会在ISE和CSE上进行实验,数据集划分:80%训练集,20%测试集。用户行为序列会收集N=90天的数据,来构建一个behaviors graph,它可以将users和queries表示成dimensional embeddings。

4.1 模型setup

对于iMAB模型,在online部分,我们实现了一个real-time Flink job,它会解析用户行为日志,并抽取一系列status表示:用户在不同slots上是否点击或浏览展示的feeds。接着用户行为被同步到online reward到iMAB模型中。由于阿里的用户行为日志非常大,为了确保Flink job时延低,我们分配了256个workers做parsing和joining,接着使用64个workers做aggregating。正如我们所预期的,online rewards会在3s内被传给iMAB模型,这使得它可以基于最新的用户行为来选择arm来表示一个概率分布。而在离线部分,超过1亿的ipv和pv记录会被聚合来估计Beta分布。基于经验表明,我们会在iMAB模型中设置\(\lambda=10\)来作为一个time impact factor。

另外,pMDNN模型需要一个训练过程,相应的设置如下:

  • User和Query表示:128维的graph embedding
  • Feed type表示:one-hot vector
  • Activation function:ReLu和softmax
  • Loss function:cross entropy
  • optimizer:GD opitmizer
  • learning rate: 0.0001
  • epochs: 100000

我们会训练pMDNN模型,并导出saved_model格式来在CSE中进行serving,它会接收实时在线请求,包含:user、query、以及preceding feed type,接着使用转化后的embedding vectors按顺序预测下一个slot type。在原始DSSM中的缺省设置会应用到我们的模型中。

4.2 A/B test

我们在三个分桶上部署提出的模型。每个分桶会通过一个hash partition function来等价处理用户请求。我们会选择5个major indices来对比在iMAB和pMDNN间的效果。pv表示展示items的数目,而pv click表示有多少displayed items被点击;相似的,uv是不同用户进入到CSE的总数,uv点击表示用户点击feeds的数目;至于uv CTR,它是用户点或不点的ratio。

表3展示了实验结果。对比原始的离线ranking方法,pMDNN总体上要胜过iMAB。特别是uv click和uv ctr,他们对于我们的场景是必要的,因为uv click的增加表明:更多用户超向于CSE,以便它能改进它的购物体验,同时,uv ctr的增强表明:用户进入CSE实验上在模型的ranking结果中更感兴趣。至于pv click,它也表明我们的模型工作良好,因为更多用户在发起queries后愿意点击feeds。

基于pv click和uv CTR,我们可以下结论:pMDNN要优于iMAB,它通过应用cross-domain知识并优化在whole page上的ranking results。另外,结合上用户体验信息可以增加用户点击的概率(uv click指标)。

参考

DTS介绍

youku在《Deep Time-Stream Framework for Click-Through Rate Prediction by TrackingInterest Evolution》提出了一个兴趣演进的框架。# 摘要CTR预测在像视频推荐等工业应用中是一个必要...… Continue reading

DFN介绍

Published on December 15, 2020

CSCNN介绍

Published on December 11, 2020