字节跳动端到端深度学习召回算法
数据派THU
共 4008字,需浏览 9分钟
·
2021-12-05 08:44
来源:DataFunTalk
本文约2600字,建议阅读5分钟
本文为你介绍字节跳动AML Team在大规模推荐中构建的可学习的索引结构。
[ 导读 ] 传统的召回算法一般基于双塔结构并加以approximately nearest neighbor search (ANN) 或者maximum inner productive search (MIPS),比如fast ball tree (FBT),hierarchical navigable small world (HNSW) 等。这些传统的算法embedding的训练目标和ANN的目标不一致,导致ANN的损失无法学习。目前比较著名的解决思路是构建一个tree-based model如TDM等。
我们今天将介绍字节跳动AML Team在大规模推荐中构建的可学习的索引结构,使得embedding的训练目标和索引结构的训练目标可以一致学习,达到良好的召回效果,它不仅局限于广告业务,在推荐和搜索业务中也有应用。
本文将从以下几方面展开:
- Deep retrieval的核心模型
- 如何训练structure model
- 思考与讨论
- 精选问答
01、Deep retrieval的核心
![beffef4853ce750c5ea651120af63e3e.webp](https://filescdn.proginn.com/dd2fe8d6126771a50f3d7158013e475a/beffef4853ce750c5ea651120af63e3e.webp)
如图所示我们可以根据DR的structure的KxD的矩阵构造出path。我们可以把这种path看成层级的聚类,每个path里面有很多的item,每个item也可以属于多个path,这样我们可以保留item的多元化信息。比如“同仁堂”可能是中药企业,也可以是一个相声,所以我们在搜索“同仁堂”对应的文章时,它既有可能在中医药的path出现,又有可能在相声中出现,达到了我们multi-path的效果。
1. 训练阶段的structure loss
![653bf18bfbef4dfec645b7eca6e35f4c.webp](https://filescdn.proginn.com/03423f51d5cf218ebe916db328af5bbe/653bf18bfbef4dfec645b7eca6e35f4c.webp)
从上图的图例我们可以看到网络的结构,在第一层得到用户的embedding x 对应c_1的概率,之后path中的每一段都将用户embedding与之前的path embedding串联,最终得到path中当前code的条件概率。根据联合概率公式最终的概率为:
p(c|x)=p(c_1,c_2,c_3|x)=p(c_1|x)p(c_2|c_1,x)p(c_3|c_2,c_1,x)
在训练中已知正例用户embedding x和item id y, 如果我们知道y所在的path为π(y),则:
maxlogp(π(y)|x)=logp(π(y)1|x)+logp(π(y)2|π(y)1,x)+logp(π(y)3|π(y)1, π(y)2,x)
2. serving阶段的beam search
在serving阶段我们采用的是beam search的算法,具体如图所示:
![6b06e65203ed79d01630acf29160be8e.webp](https://filescdn.proginn.com/90004352dc1de2aeca69bedfd3f137a2/6b06e65203ed79d01630acf29160be8e.webp)
通过图中示意的方法,我们在每一层选概率最大的B个node向下传递,B是指beam size,通常选10个左右。最后我们选出B个path并merge其中的item。
02、如何训练structure model
1. EM算法
在DR中我们需要同时训练structure model的参数(记为θ),以及所有item到path的mapping(记为π),则训练目标为:
![58c715df8a7a9540fa6b11fad1ea3ba9.webp](https://filescdn.proginn.com/1c39ea2a27939de294d11bbb93b9fe9b/58c715df8a7a9540fa6b11fad1ea3ba9.webp)
其中J是指J条path。我们想交替训练π和θ,于是采用EM算法来共同训练参数和mapping。最开始我们随机初始化θ和π并轮流进行E-step和M-step。
在E-step中,我们进行以下操作:一是可用任何基于梯度的优化算法优化θ,因为p_θ是可微的。二是对于每一个path c和item v计算它们的likelihood,记为s[v,c],也称为hidden score。
![28423731f216182f8b64b3c086700bed.webp](https://filescdn.proginn.com/373c3ed41e2676d5f6ac806e24ec3d77/28423731f216182f8b64b3c086700bed.webp)
其中假设对于任何一个item v出现了n次,对应n个用户xi,我们计算平均p(c|x, θ)的likelihood。由于可能的path有K^D个而我们不可能全部计算,所以我们将只选取beam search分数较高的path并记录其hidden score。
在M-step中,我们需要从hidden path和hidden score中更新π(v)。最直接的方法是对于每一个item我们选取hidden path中分数最高的path作为新的π,这样在EM算法的objective function显然会达到很高的分数,但是这样做有一个缺点,即导致很多item学到一个path,使得path过于集中,即有的path中有大量的item,有的path里面没有item,这样的结果送到下游任务时,下游的压力就无法控制。为此我们引入patch-size penalty,我们令f(x)=x^4,α是可调参数,有:
![825d40c3307a4a666f9deb8b5122a14e.webp](https://filescdn.proginn.com/49343f75d7b0e8ad201df3cd5ebb490f/825d40c3307a4a666f9deb8b5122a14e.webp)
即减去所有path,每个path里面的item个数的四次方,如果当前path的item已经很多时,可以有效抑制item继续增加。
2. 在线EM算法
对于流式训练,我们设计了在线EM算法。在E-step中,我们将使用一个滑动的平均hidden score并且动态跟踪一个固定大小的hidden path set。在M-step中我们采取定时任务的方式,从Parameter Server里面读取每个item的hidden path和hidden score,然后运行上段所说的penalty 算法计算出新的true path并写入到PS。
3. 多任务学习
![7d2fe3d7544ec8485e77e63e312dd09b.webp](https://filescdn.proginn.com/d70f49a89d4424ba6acb2151ce73c8b0/7d2fe3d7544ec8485e77e63e312dd09b.webp)
现在的DR采用multi-task learning的机制,我们使用structure loss来训练structure model以及item-path mapping,同时我们也保留了点乘模型比如FFM,NN模型来训练user或者item embedding用作reranker。在serving过程中,我们通过beam search找出hidden path以及他们的item,先经过reranker经过初步筛选出固定条数的candidates,再精排。这样可以减缓了粗排和精排的压力,另一方面也可以控制出口条数。
03、思考与讨论
与传统的ANN相比,DR的聚类更注重用户侧行为而不是item本身,比如足球视频和汽车视频在ANN召回中可能不在同一类但是在DR中会在同一类。DR其实不是利用item embeddeing本身,而是利用user和item之间的信息,利用hidden score进行聚类,即虽然两个item本身并不相近,但是他们可能会被同一种user消费。所以DR中path里面item的diversity会比ANN高很多。
因此DR更偏向于偏重用户行为的应用场景,比如广告或者推荐,在搜索中DR通常会降低相关性。
DR的structure model目前只用了正例没有负例,负例只在rerank model中使用。而且structure model只使用了item ID embedding,没有使用item侧特征,item侧特征只在rerank model中使用。除此之外,DR的学习目标之来源于user,item pair没有体现相关性,如果能将相关性loss引入DR loss来端到端学习用户行为和相关性也许可以解决搜索遇到的问题。
04、精选问答
Q:同一个item是否属于同一个D?
A:首先,同一个item是可以属于多个path, 比如“同仁堂”既可以属于相声的path又可以属于中医药的path, 在不同层的code中,item也可以属于多个,比如属于1,2,3 code,1,2,4 code。着代表两个path在类方向是一致的。
Q:retrieval算法学到的聚类结构与U2U的算法的聚类结构有什么关系?
A:有可能有一定关系,聚类的结果更容易把相同用户消费的物品聚到一起。
Q:什么在检索的过程中要用beam search而不是全部检索完?
A:因为一般线上K是100到1000,D是3,如果全部检索则需要检索至少百万级别的path,是不符合实际的。所以我们需要一个方法选择比如top20的path,这个方法选择的top20和实际的top20非常相近,beam search这个方法满足了我们的需求。
Q:EM算法的收敛性是否有保证,在实际应用中是否会出现不收敛的情况?
A:在理论上是有一些paper论证过EM算法在哪些条件下可以收敛,这些理论上的假设理论性比较强。在实际情况下我们回去检验一些这些条件,有时候也可以直接看结果。在非流式训练的情况下,我们的算法经过3到5个M-step以后会收敛到稳定的值。在流式训练中,我们通过定时M-Step的方法,实际在5到10次M-step可以达到收敛,这些都是一些比较实践的方法。
Q:这个方法是召回用户的多兴趣那么也没有和其他的一些用transformer的方法做对比?
A:我们在做多兴趣召回,目前和transformer的关系还不是特别紧密,我们大概的做法也是生成不同的user embedding, 对不同的user embedding做 beam search, 对 search的结果进行一些merge并通过一些loss控制不同的embedding学习不同的兴趣,但是transformer我们还没有尝试。
Q:不加multi-task模型会变成什么样?M-step是否只做一次?
A:不加multi-task模型学到的path非常不平衡,虽然我们有penalty进行控制但是还是不够,这是因为不加multi-task负例没有被利用,item embedding也没有被充分利用,所以这就是为什么我们现阶段使用了multi-task。M-step需要做不止一次的,实际我们需要等到模型收敛,这至少要一两天的时间。
Q:这个模型的线上效果如何?
A:这个模型已经在字节跳动不少的产品上线,覆盖广告和推荐,海内外产品都有应用,效果还是很成功的。
今天的分享就到这里,谢谢大家。
编辑:于腾凯校对:林亦霖
评论