以下文章来源于推荐道 ,作者石塔西
本文算是《日久见人心:论建模用户长期兴趣的几种姿势》一文的后续。主要是近期读了美团2022年的新论文《Sampling Is All You Need on Modeling Long-Term User Behaviors for CTR Prediction》有感而发。结合阿里之前ETA的工作,我感到在用户长行为序列建模这一领域,SimHash有望取代Attention,成为新的主力建模工具。本文通过梳理长行为序列建模的发展脉络,对比阿里ETA与美团的SDIM在利用SimHash时的异同,帮助读者快速了解这个建模用户长期序列的新范式。
众所周知,用户行为序列是最能反映用户兴趣的信息来源。以前对用户行为序列,只是简单Pooling。阿里的Deep Interest Network开创性地通过target item对user historical sequence做attention,实现了用户兴趣的“千物千面”,也拉开了研究“如何从用户行为序列中更有效提取用户兴趣”的序幕。
DIN的成功,自然而然地让人联想到,能不能扩大喂入Attention的行为序列的长度,包含更远的用户历史行为?这个想法是非常具有吸引力的:
但是简单将DIN套用到长期行为序列上,有一个无法回避的难题,就是计算量太大。对于一个Batch Size=B的user request,用户的行为序列长度为L,其中每个item embedding的大小是d,target attention的时间复杂度是O(BLd)。如果L达到了千或万这个数量级,这个时间开销是在线实时预测所不能容忍的。
为了解决target attention耗时太长的问题,阿里又提出了SIM。想法也非常直觉:
SIM是分“两步走”策略:
至于GSU中要用到的离线索引是如何建立的?
map<category, itemset>
的索引虽然离线索引加快了Search速度,但是也带来了两个“不一致”的问题:
因为离线索引的以上缺点,最新的发展趋势是取消离线索引,让target item在线直接从user behaivor sequence中找到与自己相似的historical items
但是重新走target attention的老路,让target item与每个historical item逐一点积,前面已经说有了,性能上吃不消,那是死路一条。我们只能另辟蹊径,这时SimHash给我们指明了一条新路。
SimHash是Locality-Sensitive Hashing(LSH)的一种实现,做起来很简单:
的矩阵,每一行代表一个hash function
h(x,R)=sign(Rx)
,也就是将x映射成m维长的整数向量。因为结果向量的每位只能是0或1,从而h(x,R)
可以表示成一个m-bit的整数。h(x,R)
可以称为hash signature,或hash fingerprint。SimHash的优点在于其locality-preserving属性:两个向量
和
,SimHash后得到
,
。
和
在向量空间中越接近,
和
中相互重合的位数就越多。
这一重要性质,也是SimHash能够被用于Search User Interest的基础保障。
阿里2021年发表的《End-to-End User Behavior Retrieval in Click-Through Rate Prediction Model》提出End-to-End Target Attention(ETA),正是利用了SimHash的locality-preserving属性,将其应用于GSU阶段:
,每个都是m-bit的整数
与每个
计算hamming distance,也就是两个m-bit序列中不相同bit的个数,比如hamming(11011001, 10011101) = 2
的hamming distance最小的Top-K个historical items作为SBS,交到ESU做target attention。
分析一下ETA的时间复杂度,在线预测时:
O(BL)
。O(BKd)
。O(BL+BKd)
美团的Sampling-based Deep Interest Modeling(SDIM),沿着ETA的思路,更进一步:
与target item 'q'很相似,那么q的hash signature
与
的hash signature
,就有很多bits是相互重合的。这也是ETA的理论基础。
的hash signature的从i-th bits到j-th bits组成的子序列
,与target item的
相同位置上的子序列
完全重合,那么
就是target item 'q'的相似item,就要参与针对q的user interest modeling。
美团的SDIM就是沿着以上思路实现的。首先,把每个historical item embedding先SimHash成m-bit的大的hash signature(比如下图中m=4),再把大的hash signature每隔
个位置分隔成小的hash signature(比如下图中每隔2bits组成黄色和绿色的小方块)。
再把相同hash signature的historical item embedding聚合成一个向量。如下图中的
所示,聚合方法就是先按位相加,再做L2-normalization。这样,就把user behavior sequence存储成若干buckets。
而针对一个target item做target attention时,将target item也先SimHash再拆解成
个hash signature,每个hash signature去上一步得到的buckets提取聚合好的向量。把每个hash signature提取出来的向量再简单pooling一下,就得到了针对这个target item的user interest embedding。
以上作法是不是超级简单?但是背后有理论依据吗?美团的大佬们认证指出(我还没有详细看证明过程):由于simhash有一定的随机性,那么target item 'q'与某个historical item '
'的两个hash signature发生碰撞也是一个概率。其中有
个位置重合(i.e., hash collision)的概率,在很大时,趋近于如下公式。
那么historical item
对构建针对target item q的用户兴趣的贡献,如下所示。从形式上看,是不是与target item非常相似,比如都和
点积相关。
所以美团认为他们的作法就相当于在原始、完整的长期用户行为序列上做target attention,被称为Hash Sampling-based Attention。
DSIM的实时性能肯定是迄今为止最好的。DSIM线上预测时的部署要拆分成两部分:
个hash signature,再把具有相同hash signature的historical item embedding聚合一起,组成buckets。这部分工作单独部署成Behavior Sequence Encoding (BSE) Server。
个hash signature,再去接收到的buckets提取向量。所有
个hash signature提取完毕后,将提取出来的向量pooling一下,就得到了针对当前candidate item的long-term user interest embedding,再和其他特征一起喂入上边的DNN。
先看BSE Server这边的性能:
O(md)
。有近似解法,可以在O(mlog(d))
内完成。O(Lmlog(d))
。而且只需要做一次,也candidate items的多少无关。个hash signature也就固定了。可以缓存起来,无需重复计算。
再看CTR Server这边的性能:
个hash signature。由于同样可以被缓存,这部分的开销也不大。
注意与ETA的区别,
O(BKd)
的时间- END -