sgr-interview-300

第 47 题：SDIM的哈希注意力，局部敏感哈希(LSH)的碰撞概率控制？

题目

SDIM的哈希注意力，局部敏感哈希(LSH)的碰撞概率控制？

---

完整讲解

一、哈希注意力与 LSH 动机

SDIM 用局部敏感哈希 (LSH) 把「候选与历史行为」的精确 attention 近似成「只与同一哈希桶内行为」做 attention，从而把复杂度从 $O(L)$ 降到与桶大小相关、近似 $O(L^{1/c})$ 或常数级（取决于 LSH 族）。核心是：相似的行为与候选会以高概率落入同一桶，只需在桶内算注意力。

二、LSH 与碰撞概率

设 $h(\cdot)$ 为 LSH 函数，满足 locality-sensitive：相似向量碰撞概率高，不相似低。对于夹角相似度（如 attention 用的内积/余弦），常用 random projection LSH：随机向量 $\boldsymbol{r}$，$h(\boldsymbol{x}) = \mathrm{sign}(\boldsymbol{x}^\top \boldsymbol{r})$。两向量 $\boldsymbol{u},\boldsymbol{v}$ 夹角为 $\theta$ 时，同号（同桶）概率为 \(P(h(\boldsymbol{u})=h(\boldsymbol{v})) = 1 - \frac{\theta}{\pi}.\) 即 $\theta$ 越小（越相似），碰撞概率越大。用 $K$ 个独立哈希函数构成复合桶（如 AND 或 OR 构造），可控制 precision-recall：更多 hash 联合（AND）桶更小、更准、召回低；少 hash（OR）桶更大、召回高、噪声多。

三、碰撞概率控制与工程

控制方式：（1）调节 hash 个数 $K$ 与 AND/OR 结构；（2）多组独立哈希（多轮 bucket），取并集或投票，提高召回；（3）桶内再做精确 attention 或二次排序。SDIM 通过 LSH 把「全序列 attention」变为「若干桶内 attention」，在可控碰撞概率下近似长序列兴趣，兼顾效果与复杂度。

---

面试要点

• 能说明 SDIM 用 LSH 做哈希注意力的动机：相似项同桶、只算桶内 attention，降复杂度。
• 能写出 random projection LSH 的碰撞概率与夹角关系：$P(h(\boldsymbol{u})=h(\boldsymbol{v})) = 1 - \theta/\pi$；夹角小则碰撞概率高。
• 能说清如何控制：$K$、AND/OR、多组哈希；桶内精确 attention 做精排。

---

记忆要点

• SDIM：LSH 将行为/候选分桶，只在桶内做 attention；复杂度由桶大小控制。
• LSH 碰撞概率：夹角 $\theta$ 小 → 碰撞概率高（如 $1-\theta/\pi$）；$K$ 与 AND/OR 控制桶大小与召回。
• 工程：多组 hash 提高召回，桶内精确 attention 保证质量。

返回模块

返回总览