type
Post
status
Published
date
Nov 6, 2022
slug
2022.11.06 读论文: PDN > I2I + U2I
summary
2022.11.06 读论文: PDN > I2I + U2I
tags
推荐
召回
算法
category
算天算地系列
icon
password
Path-based Deep Network for Candidate Item Matching in Recommenders, 2021
背景
工业界召回算法大致分为两类:倒排召回和向量召回(EBR, Embedding-Based Retrieval)
倒排召回
- 典型算法:Item-based CF、Swing 等
- 优势在效率和多样性
- 在线服务的效率比较高,也可以捕捉实时兴趣;
- 用户的兴趣多样性能被较好的满足。
- 不足在个性化
- 大多基于 Item 的共现性计算,因此难以处理数据稀疏问题(长尾、冷启等);
- 无法利用 User 和 Item 的 side information。
向量召回
- 典型算法:双塔模型
- 优势
- 可以利用 User 和 Item 的 side information
- 不足
- 难以显式学习 Item 之间的共现性;
- User 侧只有一个向量,无法充分表达用户的兴趣多样性。
当前工业界解决上述不足问题的方式比较粗暴,就是同时跑多路召回,比如多个不同角度的倒排召回,多个不同模型和目标的向量召回。这些不同路的召回结果 merge 起来形成最终的召回结果,由于不同召回路的分数不可比,因此 merge 过程就需要一定的人工干预,而人工干预就大概率不是全局最优的。
一个有趣的点
这篇文章有趣的一个点在 Section 3 PRELIMINARIES,它抽象出了一个召回问题,并指出当前的倒排召回和向量召回都只是其特例,没有考虑到全链路信息,因此推出 PDN。写文章还是佩服阿里的同学。
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F200d396b-e3d7-4b46-bd2f-f22b024a1b6c%2FUntitled.png%3Ftable%3Dblock%26id%3D0184b0ef-0679-4ce3-b474-831f28f2f8c3%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3D5yBsODyr4gTlSRMZHEw-zDihb1Z9tds-y36Ku-H22Xc?table=block&id=0184b0ef-0679-4ce3-b474-831f28f2f8c3&cache=v2)
上图是一个召回的示意图,左边 是用户信息,右边 是目标 Item 的信息,中间的一溜 是用户历史有过交互的 Item, 是用户与这些 Item 的交互信息 (比如停留时长,是否加购,购买次数等等), 是 Item-i 和 Item-j 之间的关联性信息 (比如共现情况等等)。下方的虚线是反应的是用户 对目标 Item 的 intuitive 兴趣。这种兴趣也可以通过上方用户交互过的 Item 来做一个连接,因此召回过程可以被形式化地表示为:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F53f2e6e3-e2ea-49eb-b956-3f5da213a6fc%2FUntitled.png%3Ftable%3Dblock%26id%3D030f5982-2eaa-4af0-8246-258159195ebc%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DG1QPAhPydQnaYQkxvWHRC-i_AgOD65K7TKaiZArsl1c?table=block&id=030f5982-2eaa-4af0-8246-258159195ebc&cache=v2)
其中,N(u) 是用户交互过的 Item 集合。
Item-based CF:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F06e3d147-31ab-417d-87c9-9d9fda29bb10%2FUntitled.png%3Ftable%3Dblock%26id%3Da437596d-e96e-4c90-9169-9f4cdd1107c9%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DdEZ_tXY11h7VZSJUwZ4d88y_qvEYTF4cl4osP3RajRg?table=block&id=a437596d-e96e-4c90-9169-9f4cdd1107c9&cache=v2)
双塔 MBR:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F7aaf1464-ac97-4d85-9119-e9d03432f103%2FUntitled.png%3Ftable%3Dblock%26id%3Dcee7bc7c-9d7e-4ab1-b2bb-92f91178a6f8%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DZahfqp2zgPfOKaTVOlXCNacw0yLdB7YhM_vvdITmskE?table=block&id=cee7bc7c-9d7e-4ab1-b2bb-92f91178a6f8&cache=v2)
PDN 的训练
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F34bc5958-c51a-4683-9cea-7685341cc70a%2FUntitled.png%3Ftable%3Dblock%26id%3D5ad9adfb-1638-4ca6-a274-0431edbad118%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3D0C8yczsFrvWYs-Am-_7mNwGmyvG-7z1xgl4LST0Xonk?table=block&id=5ad9adfb-1638-4ca6-a274-0431edbad118&cache=v2)
就是直接路径下通过双塔模型算的用户 和 Item 的打分, 就是通过 Item j 作为桥算的打分,最后通过 AGG 函数进行计算得到一个最终打分, 比如把这个 n+1 个打分相加):
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2Fac8d4032-0e7f-4974-9358-c6c14b1357b1%2FUntitled.png%3Ftable%3Dblock%26id%3D017e55e2-fa71-457c-8799-8fc51a195fa6%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DEBDZlaxtrzXqt7x3azUcO7H-JM5fmn_Dx1F3NeNH8PQ?table=block&id=017e55e2-fa71-457c-8799-8fc51a195fa6&cache=v2)
MEG 函数是用来 merge Trigger Net 和 Similarity Net 两部分分数的,如果 Trigger Net 和 Similarity Net 的输出都是向量,MEG 函数可以选择内积,如果输出都是标量,则 MEG 函数可以选择加法或者乘法,也可以用其他更奇怪的方式,比如(文章 disscuss 部分里说这种始终为正值的处理,相对于允许有负数的情况,可以有更好的收敛效果):
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F89d446a5-e60b-4fbf-9b96-03b8f899b369%2FUntitled.png%3Ftable%3Dblock%26id%3D5b9af5db-d7d3-4f7d-8ee0-812d76dad55f%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DLGA70NulZDX3CEgnAzh_xVtDOcTYTEsYpwOY2gnfU1w?table=block&id=5b9af5db-d7d3-4f7d-8ee0-812d76dad55f&cache=v2)
整个 PDN 结构如下图所示:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2Fc19225ee-8990-4013-819f-8a2740744506%2FUntitled.png%3Ftable%3Dblock%26id%3Daf561496-e30d-4597-ac62-ec27863cf0a7%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DUbuuCUKFEVmHpLMVeXhrt2Olj3EkUCoweOnLnxyLAMk?table=block&id=af561496-e30d-4597-ac62-ec27863cf0a7&cache=v2)
结合上图,最上面两层的计算如下:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2Ffce91221-e9bc-4cf3-b208-a376708608de%2FUntitled.png%3Ftable%3Dblock%26id%3D9ce55d5f-8561-4a14-8921-f9b02c335c19%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3Dj2_POpCWzUk0NKzzFRIRbz9GiB_a7WEqsYvTe7PJ-Zg?table=block&id=9ce55d5f-8561-4a14-8921-f9b02c335c19&cache=v2)
这里用 softplus 也是为了保证输出是正值,softplus 激活函数是 ReLU 函数的近似表示,两者差异如下:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F9bc7f17a-9faf-4959-8660-e0c59cf9f749%2FUntitled.png%3Ftable%3Dblock%26id%3D0de09cbb-2d16-4e94-bbfd-a3384f1e49fd%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DIOx4j896hPgfIFOyd7iraDSYz6OQxBkv5T_IGNiLhwc?table=block&id=0de09cbb-2d16-4e94-bbfd-a3384f1e49fd&cache=v2)
如果 label 是是否点击 item xi,那么 就是预估的点击率,loss function 可以选择 cross entropy。
PDN 的线上部署
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F73faaa91-cdd6-49a3-8f7f-053472439e28%2FUntitled.png%3Ftable%3Dblock%26id%3D115c88de-ecf9-446d-b680-133874825459%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3DMw1wFf8Jolucj58PNyPnZYO7K0WFs-dwprqjwWNaLSQ?table=block&id=115c88de-ecf9-446d-b680-133874825459&cache=v2)
- Index generation (Step 1):基于 SimNet,将每个商品的 个最相似商品及相似分数 离线算好,并建立索引;
- Trigger extraction (Step 2):当用户登录淘宝后,用 TrigNet 对用户历史交互过的所有 Item 进行打分,并截取 Top-m 结果及打分;
- Top-K retrieval (Step 3):用 step2 得到的 Top-m 作为 trigger,通过 step1 建好的索引,去检索得到 个候选商品,然后利用下式进行排序后取 top 输出。
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2Fffee562f-5ea5-4d44-9437-1b577bbc0d79%2FUntitled.png%3Ftable%3Dblock%26id%3Df55afb65-b938-43c3-8a0d-0f6242a7b6e3%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725789600000%26signature%3D6OVthG9W0_1L2FGZ3rJwi2Qc9fABqHr-O-1n60A6SXY?table=block&id=f55afb65-b938-43c3-8a0d-0f6242a7b6e3&cache=v2)
PDN 的评估
评估指标 Hit Ratio (HR) 和 Normalized Discounted Cumulative Gain (NDCG)
HR@10,NDCG@10
类似的推广
PDN 这种做法其实就是一种端到端的建模思路,把 I2I 和 U2I 显式地考虑到了一个模型中。在这种思路指导下,还可以做一些类似 PDN 的方法,比如简单的把历史互动的 item list (比如随机挑 3 个) 和目标 item 的 embedding 做内积后,再 avgpooling 或者 maxout,最后输出一个 loss,与 U2I 那一路的 loss 相加得到最终的 loss,这种做法,可以让相似的 item embedding 更加靠近,提升了模型的泛化能力,对于一些冷启动问题会有帮助。
线上 serving 的时候,可以只用 U2I 的那一路结果,也可以先用 U2I 得到 trigger,再用 I2I 这一路做召回,或者反过来都是可以的。