Recommendation

Twitter去年开源推荐系统代码到现在一年多了，一直没时间去看一看，今天想起来瞄了会，本文简单记录下。 开源： 系统代码：https://github.com/twitter/the-algorithm 算法代码：https://github.com/twitter/the-algorithm-ml 博客：https://blog.twitter.com/engineering/en_us/topics/open-source/2023/twitter-recommendation-algorithm 我先读的博客，基本了解其推荐系统的概况，总体来说，算法相比国内阿里电商首猜/小红书feed流的推荐是更初级很多。 整个系统基本就是召回 + 精排，可以理解没有粗排，在In-Network召回时也就是RealGraph那里会有一个LR模型类似粗排的功能。 数据： 因为Twitter是社交app，所以： 主要是用户交互数据，包括用户-用户Follow的社交图，Tweet engagement通常指用户和内容的的交互，比如点赞、分享、关注等等； 用户的profiles数据：语言、地理位置等 召回 召回是本次开源里面的重头部分。Twitter召回包括In-Network的召回和Out-of-Network的召回。In-Network指从用户的Follow用户的内容中召回，Out-of-Network指从未Follow的其他用户中召回，两者占比大概各50%。召回最终返回1500个候选集给到精排（Twitter叫Heavy Rank）打分排序。 In-Network召回，占比50% 从Follow的用户中召回所有的内容，然后通过一个LR模型对这些内容进行排序。这部分叫Real Graph，看了下这个是2014的工作了，博客中也提到要对LR模型重构。 RealGraph核心逻辑就是构建User间的有向图，然后通过LR学习Edges的权重，权重高的用户的内容多推荐一些。 Out-of-Network召回，占比50% 包括直接从U2U2I召回、Sparse Embedding召回、Dense Embedding召回。 U2U2I召回：即从关注的用户喜欢的内容中召回，占比15%。有个问题，这里如果U2U2I内容数量超过15%怎么截断呢？ Sparse Embedding召回：也是U2U2I，只不过是通过Sparse Embedding找相似用户。首先通过SimClusters社区发现算法，找到用户的社区representation embedding，然后通过ANN找到相似用户。 Sparse Embedding可解释性强，虽然Sparse Embedding从技术上来说是相比下面的Dense Embedding简单，但是基本所有的公司都还是会保留该路召回的。 Dense Embedding召回：相比用社区向量表征用户，Dense Embedding采用了TwHIN模型学习用户的向量表征，得到的向量结果可用于其他模型作为特征。 TwHIN思路和其他的U2U/U2I召回算法类似： 正样本：和目标用户有engagement的用户作为正样本 负样本：batch内采样负样本 优化：通过binary_cross_entropy_with_logits loss函数train一个Model。模型离线Train完之后，离线存储user vector，然后线上通过ANN索引查找最相似的用户。 采用的Graph数据：提到了大致是类似于"User follows User" “User favorites Tweet” “User clicks Advertisement”，但是由于隐私原因没法公开数据，由于存在不同的关系类型，所以TwHIN应该是训练的异构图，数据格式是：左节点id, 关系类型，右节点id。 工程上，TwHIN采用了pytorch开源的torchrec来实现该算法，torchrec适合高维稀疏特征的场景，也被用在Meta自己的DLRM的模型训练中。 召回里面的算法其实都比较中规中矩，没有很fancy的模型，对于图模型训练感兴趣的可以研究下TwHIN的详细代码。除了算法上，召回会有很多工作在推荐工程上，比如设计GraphJet去维护user-tweet-entity-graph (UTEG)即用户的交互图，比如follow-recommendation-service (FRS)推荐服务的工程实现等等。有兴趣的可以深入研究下twitter的工程实现，比如: 相似性检索，user/item embedding的存储，ANN的实现 图数据的存储 训练的规模和配置等等。 精排 召回的1500个候选送到大概48M参数的MaskNet中打分。国内的推荐系统，通过各种工程优化，中等公司一般也能做到差不多3000左右了，所以twitter进到精排的量并不算太大。 MaskNet是微博21年发表的一篇paper，其主要是为了解决输入特征（尤其是特征交叉）学习不充分的问题，作者也说过，MaskNet是微博摸索过的几个模型里面（FiBiNet,GateNet,MaskNet,ContextNet）综合效果最好的一个。MaskNet由多个MaskBlock构成，多个MaskBlock可以组成Serial Model或者Parallel Model的形式。Parallel其实就是输入Embedding经过多个不同的特征权重计算后concat起来，最终输入DNN的Embedding维度会变成N倍。 对于每个MaskBlock，它的输入都是全量的Embedding，计算方式大概如下， LN-EMB：计算Embedding的Layer Norm，$LN_{EMB}(Vemb)=concat(LN(e_1),LN(e_2),..,LN(e_f))$, 对于Parallel Model，其中Vemb都是原输入Embeddings=$[e_1,e_2,…,e_f]$，而对于Serial Model，第二个MaskBlock之后就是上一个MaskBlock特征加权后的输出； Instance-Guided Mask: Mask计算：2层全连接层，$𝑉𝑚𝑎𝑠𝑘 =𝑊_2(ReLU(𝑊_1*𝑉𝑒𝑚𝑏 + b_1)) + b_2$，注意Vmask的输出维度是F X K，F是特征Fields数量，K是每个Field的Embedding数量。所以输入Embedding的每个元素的mask weight都不同，而不只是每个Field不同。 Mask输出：$Voutput=ReLU(LN(W_i(Vmask⊙𝐿𝑁_{𝐸𝑀𝐵}(V𝑒𝑚𝑏))))$，Vmask点乘LN-EMB，再经过一个线性层+LN+ReLU输出。几个点，一个为什么这里Vmask没有像Attention一样softmax归一化？第二个，输出这里的线性层只有一个weight没有bias项？ 重排和混排 重排就是一些基于业务的规则和策略，主要就是过滤和打散操作：...

SIM和ETA的问题 SIM通过类目从长序列中检索相关的items（hard-search）或者通过embedding inner product计算从长序列中检索最相似的topK个item；SIM的问题在 ETA 中讲过，主要是离线索引可能带来的在线target item embedding和离线的item embeddings不一致的问题； ETA在SIM基础上，通过对Long Behavior Sequence的item embeddings进行SimHash（LSH）之后，然后就可以将inner product的耗时计算转化为Hamming distance计算。从而大大降低了计算量，可以把检索topK的过程放到线上模型中，解决了SIM在离线不一致的问题；但是ETA依然需要通过一个Multi Head Target Attention得到最终的Long Behavior Sequence Embedding表达； 不管是SIM还是ETA，都是基于检索的方法从长序列（>1000）的候选items中选出最相关的topK，美团的这篇文章Sampling Is All You Need on Modeling Long-Term User Behaviors for CTR Prediction 则是吸收了ETA中Hash函数的特点，但不使用检索的方法，不通过Multi Head Target Attention，直接得到用户Long Behavior Sequence的embedding表达——SDIM（Sampling-based Deep Interest Modeling）。 Hash-Based Sampling的用户行为建模 SimHash有Local Sentitive特性，也就是说空间距离相近的两个vector在Hash之后距离也 大概率 相近。SDIM就是利用这个原理： 将序列的所有Item Embeddings和Target Embedding通过m个Hash函数进行Hash（比如下图m=4） Item Embedding每次Hash之后和Target Embedding落在同一个桶（Hash的LSH特性），则记为一次贡献； 进行m次Hash之后，统计每个item embedding的贡献，最后用L2 normalization进行归一化得到每个item embedding的权重 weights（按理L1也可以，但是作者说L2效果更好） 最后只需要将长序列的item embeddings通过weighted sum pooling求和就得到了Long Behavior Sequence的Embedding表达，完美避开了Multi Head Target Attention的操作； 当然，为了降低Hash冲突的风险，实际中需要将hash function数量m和Hash width设置得大一些。...

SIM的问题 前面介绍过阿里巴巴超长行为序列建模的方法SIM是two-stage，在预估的时候，SIM先通过target item从长行为序列中通过类目（hard-search）或item embedding相似度（soft-search）检索出top-K，再送到主模型中做target attention。由于类目索引和item embedding索引的构建是离线的，而CTR主模型很多时候需要online learning，这种情况下就造成用于检索的目标item embedding和离线构建的item embedding不在同一空间（离线的item索引存在滞后）。 End-to-End User Behavior Retrieval in Click-Through Rate Prediction Model 是阿里主搜团队 基于此出发提出了End-to-end Target Attention - ETA，GMV提升3%。我们回到长序列问题本身，为啥不能像DIN/DIEN一样直接对超长序列做target attention——因为inference time吃不消（target attention需要对长序列中的每个item emebedding做inner product）。那么有没有其它方法可以快速从长序列中检索出top-K，又不需要像SIM那样最终要用到比如faiss做快速的索引？ ETA就想到了SimHash！通过将long behavior sequence item embeddings进行SimHash后，就能通过Hamming distance替代掉inner product，从而缓解长序列中inner product所带来的计算量问题。 Embedding SimHash后能快速的进行TopK检索 SimHash算法用于将每个item embedding映射成一个二进制的串（最终可以保存成一个整数），之前主要用于长文本相似度的比较。这里应用SimHash相当于把embedding当作长文本。 本文使用的SimHash伪代码如下，代码中共进行m次Hash，Hash的width=2即每次Hash返回二值0或1的$sig_k[i]$： 只要满足下面的条件，就能保证最终的计算复杂度能够降低： 映射后的向量相似度计算函数的复杂度比inner product低（映射后的二进制向量用Hamming distance计算相似度，复杂度 < inner product）； 映射后的向量长度比原item embedding长度小（m<d）； Hash映射函数的复杂度不高；从伪代码看，Hash过程也需要计算内积，怎么感觉比inner product还高，Table 2里面的ETA的Retrieval complexity貌似也没把Hash函数的计算量考虑进去？主要原因是：在inference阶段，模型训练好之后，item embedding都是lookup table，那我们可以把lookup table里面的所有embeddings都提前计算好它的$sig_k$，然后和Embedding Table以及模型一起存储下来，最终只要根据item查表得到$sig_k$就行。所以Inference的时候，理论上Hash函数的时间可以忽略不计； 下图是采用SimHash之后，ETA对各种检索方法的时间复杂度、检索信息一致性的对比：相比直接inner product，ETA通过对item embedding做SimHash，然后用Hamming distance相似度函数进行检索。 有几个问题： SimHash把d=128维度的embedding映射到了m=4维，且通过Hamming distance代替了inner product计算，这也就是ETA为什么能降低计算复杂度的核心原因。那如何保证映射后m=4维的向量后原d=128 embedding的信息不会丢失呢？SimHash有一个特殊的性质——locality sensitive hashing，即局部敏感哈希，也就是说空间上相近的两个embedding做完Hash之后位置依然大概率接近。 如果是SimHash映射到m=4然后再计算相似度，那为什么不建embedding lookup table的时候就让d=4？核心是因为这里的复杂度降低，是将inner product计算替换成了Hamming distance计算，Hamming distance通过异或XOR运算复杂度可以控制在O(1)，所以不管怎么降低embedding dim都比较难达到Hamming distance这么低的计算复杂度。 ETA (End-to-end Target Attention) ETA结构左边就是SimHash的应用，具体的：...

为什么推荐需要超长行为序列？ 试想这么种场景，某个用户4个月前在某家店买了厕纸，2个月前又买了厕纸，然后中间又浏览了成千上万的其他东西，到现在又隔了两个月，应不应该推厕纸？ 然而，对于模型来说，因为2个月前到现在中间浏览了成千上万的其他东西，而DIN, DIEN, MIMN只能建模1000以下的行为序列，所以早就把厕纸从行为用户历史行为序列中剔除出去了。 所以： 第一，通过超长行为序列可以捕获用户长周期里面周期性或规律性的购买行为 第二，短序列只能刻画用户短时的兴趣偏好（买了几次盲盒，但无法确定是否二次元用户），但通过超长序列可以刻画用户的长期偏好（比如，除了最近几次的盲盒还买了很多手办，二次元用户） 任何事情也都有利弊，即使计算量不是问题，但直接把用户所有的历史行为序列到模型中，除了会引入有用信息，同时也引入了许多的噪音。如何从用户长历史中剔除噪声，提取有用的信息？SIM在一定程度上就是在解决这个问题。 题外话：LLM里面的RGA，不是也为了解决这种问题吗？ SIM Paper: Search-based User Interest Modeling with Lifelong Sequential Behavior Data for Click-Through Rate Prediction SIM是Two-stage Model， 包括GSU和ESU阶段。注意，主结构中依然保留了User short-time behaviors的输入，在短时序的基础上做增量，毕竟最近的行为序列才是最重要的。 General Search Unit (GSU) GSU，通过线性时间复杂度，用于从原始超长序列中检索出top-K相关的子行为。文中介绍了两种GSU的方式，soft-search和hard-search。两种搜索的差别主要在序列中的item和目标item的相似度的计算上， $$ r_i = \left\{ \begin{aligned} sign (C_i=C_a) & & hard-search \\ (W_be_i) \cdot (W_ae_a)^T & & soft-search \end{aligned} \right. $$ 其中，$C_a$是目标item的category，$C_i$是序列中behavior item的category，即只从长序列中筛选同category的items；soft-search则是直接通过behavior item embedding和目标item embedding的内积（inner product）计算相似度，SIM使用的检索算法是ALSH（这也是召回里面常用的user向量检索item向量的方法）。 关于soft-search的item embedding： 不能直接使用short behavior sequence的embedding，因为不在一个表达空间，embedding差异会比较大；所以才有了上图中左边Soft Search Training辅助任务； Soft Search在原文中是和后面的ESU一起训练，得到behavior item embedding矩阵，线上serving的时候通过类似i2i召回，内积检索得到topK的item；但是，一起训练成本太高，behavior item的长期表达在短期内变化不大，这里是否可以定期离线训练？ soft-search training的技巧：当life long sequential behavior实在太长的时候（内存放不下），可以随机采样子行为序列，对最终item embedding的分布影响不大； hard-search或soft-search的topK结果送到后续的ESU。...