sgr-interview-300

第 46 题：ETA的End-to-End长序列，长序列兴趣提取的线性复杂度方案？

题目

ETA的End-to-End长序列，长序列兴趣提取的线性复杂度方案？

---

完整讲解

一、长序列与复杂度瓶颈

用户行为序列可达数千甚至更长，若用标准 self-attention（每位置 attend 到所有位置），复杂度为 $O(L^2)$，显存与计算难以承受。ETA (End-to-End Target Attention) 等工作的目标是在端到端不丢长序列信息的前提下，把兴趣提取的复杂度压到 $O(L)$ 或近线性。

二、ETA 的线性复杂度思路

ETA 的核心是用 Target (候选 item) 作为 query，只与行为序列做一次 target attention，而不是行为序列内部的 $L\times L$ self-attention。设候选嵌入 $\boldsymbol{q}$，行为嵌入 ${e_1,\ldots,e_L}$，则 \(a_t = \frac{\exp(\boldsymbol{q}^\top e_t / \sqrt{d})}{\sum_{j=1}^L \exp(\boldsymbol{q}^\top e_j / \sqrt{d})},\quad \boldsymbol{v}_U = \sum_{t=1}^L a_t e_t.\) 计算量：对每个 $t$ 算 $\boldsymbol{q}^\top e_t$ 为 $O(L\cdot d)$，softmax 与加权和再 $O(L)$，整体 $O(L\cdot d)$，与序列长度线性。这样既保留「与候选相关」的局部注意力语义，又避免 $O(L^2)$ 的 self-attention。

三、实现细节与扩展

可对 $\boldsymbol{q}$ 与 $e_t$ 先做线性变换再内积（即 target 为 query，行为为 key/value）；为增强表达，可堆叠多层 target attention 或混合少量 local self-attention（窗口内 $O(w\cdot L)$）。ETA 类方法适合超长序列的线上服务：用户侧可预计算行为 embedding，请求时只对候选算一次 attention 得到 $\boldsymbol{v}_U$。

---

面试要点

• 能说明长序列下 $O(L^2)$ self-attention 的问题，以及 ETA 目标：端到端、线性复杂度。
• 能写出 ETA 的 target attention 形式：以候选为 query、行为为 key/value，$a_t \propto \exp(\boldsymbol{q}^\top e_t)$，$\boldsymbol{v}_U = \sum_t a_t e_t$；复杂度 $O(L\cdot d)$。
• 能简述工程上的预计算与多层/局部 attention 的扩展。

---

记忆要点

• ETA：以候选为 query 的 target attention，不做行为间 $L^2$ attention；复杂度 $O(L\cdot d)$。
• 公式：$a_t = \mathrm{softmax}(\boldsymbol{q}^\top e_t)$，$\boldsymbol{v}_U = \sum_t a_t e_t$；保留「候选相关」且线性。
• 工程：用户侧预计算 embedding，请求时只算一次 attention；可多层或加局部 self-attention。

返回模块

返回总览