【推荐系统】logQ矫正

推荐系统中训练双塔模型的标准做法是使用sampled softmax，可以说就是一个加了logQ矫正的infoNCE Loss，这里介绍它的原理和不同实现。

问题

用随机变量 $u$ 表示用户，用 $v$ 表示item，那么可以用 $p(v|u)$ 表示用户对item的点击概率，我们的目的是建模这个概率分布。为此，我们可以获取用户和item的交互数据 $\{(u_i, v_i)\}_{i=1}^m$，然后用最大似然估计去近似：

\[\mathcal L = -\frac1m\sum_{i=1}^m\ln p_{\theta}(v_i|u_i)\]

这里的 $p_{\theta}(v_i|u_i)$ 使用深度学习的建模思路是把 $u_i$ 的特征和所有item的特征求相似度，并使用softmax归一化，取出其中 $v_i$ 对应的概率。这本应该是一个简单的分类问题，但是由于item数量会非常巨大（亿级别），无法全部计算相似度并计算softmax，导致我们不好求 $p_{\theta}(v_i|u_i)$ 进而计算loss。为了解决这个问题，一些近似softmax的算法被提出，包括分层softmax，以及只采样一部分类别计算的方法，如NCE、NEG、infoNCE、Sampled Softmax等，这里只介绍sampled softmax。

Sampled Softmax

Sampled Softmax（这里缩写为SSM）思路非常简单，就是从全量的item集合 $\mathcal D$ 中根据采样分布 $Q$ 采样一个子集 $\mathcal S$ 来计算softmax，这是重要性采样的做法。具体来说，假设完整的类别集合是，完整的softmax公式是：

\[p(v_i|u_i) = \frac{e^{s_i}}{Z} = \frac{e^{s_i}}{\sum_{j \in \mathcal D} e^{s_j}}\]

其中 $s_i=\frac1T\frac{u_i^Tv_i}{|u_i||v_i|}$ 表示用户特征 $u_i$ 和 物品 $v_i$ 的余弦相似度，$T$ 是温度系数。 问题在于 $\mathcal D$ 太大了，是亿级别的，导致 $Z$ 很难计算。Sampled Softmax从选择从 $\mathcal D$ 中采样一些item组成更小的 $\mathcal S$ 近似计算 $Z$（一般采样几千个），具体怎么采样可以人为设计采样策略，例如均匀采样。但无论是什么策略，都可以用一个采样分布 $Q$ 表示。接下来的问题是基于 $Q$ 进行采样应该怎么推导出softmax的近似计算公式，也就是 $Z$ 的近似公式是什么。考虑到 $Z=\sum_{j \in \mathcal D} e^{s_j}=|\mathcal D|\cdot E[e^{s_j}]$ 其实是在求期望，而且是均匀分布 $U(j)=\frac{1}{|\mathcal D|}$ 的期望，而重要性采样就是用来近似期望的，所以可以用重要性采样的思路进行推导：

\[\begin{aligned} Z =\sum_{j \in \mathcal D} e^{s_j} &=|\mathcal D|\cdot E_{j\sim U}[e^{s_j}]\\ &=|\mathcal D|\cdot E_{j\sim Q}[\frac{e^{s_j}}{Q(j)}U(j)]\\ &=|\mathcal D|\cdot E_{j\sim Q}[\frac{e^{s_j}}{Q(j)}\frac{1}{|\mathcal D|}]\\ &=E_{j\sim Q}[\frac{e^{s_j}}{Q(j)}]\\ &=E_{j\sim Q}[e^{s_j - \ln Q(j)}] \end{aligned}\]

最后的推导结果变成了 $Q$ 分布上的一个简单期望，所以只需要随机采样一些item计算相似度 $s_j$，再计算 $e^{s_j-\ln Q(j)}$ 取平均就能近似 $Z$ 了，采样越多近似越准。有了 $Z$ 的这个近似公式我们就可以得到sampled softmax loss：

\[\mathcal L_{SSM'} = -\ln \frac{e^{s_i}} {\frac{1}{|\mathcal S|}\sum\limits_{j\in \mathcal S} e^{s_j - \ln Q(j)}}\]

考虑到loss取了对数，所以分子分布里面的乘以的系数对于loss来说都是常数，我们可以把分母的 $\frac{1}{|\mathcal S|}$ 去掉：

\[\mathcal L_{SSM} = -\ln \frac{e^{s_i}} {\sum\limits_{j\in \mathcal S} e^{s_j - \ln Q(j)}}\]

这就得到了sampled softmax loss。注意有些地方会把分子写成 $e^{s_i-\ln Q(i)}$，实际上也是等价的，对loss来说是常数项。

均匀负采样

在推荐系统中，计算sampled softmax loss其实就是均匀地随机采样一些item计算分母项，这个时候 $Q(j)=\frac{1}{|\mathcal D|}$，是一个常数，放在loss里就可以把它去掉：

\[\mathcal L_{SSM} = -\ln \frac{e^{s_i}} {\sum\limits_{j\in \mathcal S} e^{s_j}}\]

这种均匀负采样的做法有一个细节问题，理论上我们应该完全随机的采样得到 $\mathcal S$，但实际上更好的做法是采样的时候排除掉正样本 $v_i$，并把 $e^{s_i-\ln q_i}$ 专门放到分母里，也就是采用公式：

\[\mathcal L_{SSM} = -\ln \frac{e^{s_i}} {e^{s_i} + \sum\limits_{j\in \mathcal S} e^{s_j}}\]

其中采样的时候保证 $i\notin\mathcal S$。这样突出了正样本的作用，是大多数人采取的做法，也更契合其它对比学习的方法。但是这样强行保证采样到正样本，其实违背了均匀采样的分布。但召回使用这个loss的目的不是为了严格拟合训练集的数据分布，而是为了得到更好的特征从而改进检索效果，让正样本总是在分母中直觉上能得到更好的对比效果进而改进特征质量，在MovieLens数据集上简单测试了一下两种做法差不多。

最近也有一篇论文认为这样采样违背了前面的理论，对这一点做了修正，得到了improved logQ：

\[\mathcal L_{improved\ SSM}=-\text{sg}(1-p_i)\ln\frac{e^{s_i - \ln q_i}}{\sum_{j\in D} e^{s_j - \ln q_j}}\]

这里 $\text{sg}$ 表示stop gradient，$p_i=p(v_i|u_i)$ 需要用重要性采样去近似，具体可以参考原文。从论文里提供的工业界场景实验结果来看，这样做会导致Recall@10显著下降，Recall@100略微提升，Recall@1000显著提升，在召回场景来说算是有提升的。

In-Batch负采样与logQ矫正

均匀负采样的做法有2个缺点：

• 一是对采样的每个item都要过一遍模型计算特征 $v_j$，然后再计算loss，计算量很大。
• 二是热门样本作为正样本的机会太多，很少作为负样本，而冷门样本几乎总是作为负样本，对冷门样本太不公平。

谷歌的论文Sampling Bias Corrected Neural Modeling使用batch内的其他样本作为负样本，batch内的样本本身就是要forward进行计算的，所以把这些计算好的特征拿来做负样本就不需要任何额外的计算。并且热门样本也有更多的机会作为负样本了，因为推荐系统的样本是用户交互过的样本（曝光、点击等），那些热门的样本在batch里出现的概率比较高，而冷门样本几乎不出现。

但是这样做的问题是 $Q(j)$ 不是均匀分布了，而是数据集的分布，它的分布正比于曝光次数或点击次数之类的。这篇谷歌的论文给出了一个简单的、在分布式系统中流式地估计 $Q(j)$ 的算法，具体怎么估计的可以参考原文。记 $Q(j)$ 的估计值是 $q_j$，这个时候loss可以写成：

\[\mathcal L_{SSM} = -\ln \frac{e^{s_i}} {\sum\limits_{j\in \mathcal B} e^{s_j-\ln q_j}} = -\ln \frac{e^{s_i}} {e^{s_i-\ln q_i} + \sum\limits_{j\in \mathcal B-\{i\}} e^{s_j-\ln q_j}}\]

其中 $\mathcal B$ 表示Batch内的所有item，包含自身作为正样本，并把其它样本的item都作为负样本。这个loss直观理解是，更热门的item天然会导致 $s_i$ 比较高，通过在训练的时候减去 $\ln q_j$这样一个更大的值排除它的影响即可，相当于做了一个矫正，所以这种做法叫 logQ矫正。

混合负采样

前面介绍了使用Batch内负样本的logQ矫正方法，它的优点是没有额外的计算量，也没有对冷门物品不公平的问题，但是存在Sample Selection Bias问题：模型训练见到的更多是样本分布有明显热度差异，但推理时是面向所有item的均匀分布。或者说，只用batch内的样本作为负样本会导致热门样本占据了太多训练机会，冷门样本的训练机会太少。相比之下，均匀采样的负样本没有SSB问题，但是计算量大。为此，谷歌提出了混合Batch内负采样和均匀采样的方法Mixed Negative Sampling(MNS, 2020)，得到了一个折中的方案，能有比较大的提升。这里的问题是负样本有了不同来源，应该如何进行logQ矫正？有几种不同的方案：

1. 把两个采样方式合并成一个，这时采样函数为 $Q(i) = \frac{|\mathcal B|q_j + \mathcal |S|\frac1n}{|\mathcal B| + |\mathcal S|}$，这是google官方的做法。

2. 两种采样方式都是对 $Z$ 的估计，直接加权求和缩小方差得到方差更小的估计值：

   $$ Z = \alpha E_{j\sim Q}[e^{s_j-\ln Q(j)}] + (1-\alpha) E_{j\sim U}[e^{s_j-\ln \frac{1}{n}}] $$ 令 $\alpha=\frac{\|\mathcal B\|}{\|\mathcal B\| + \|\mathcal S\|}$，使样本数量更多的权重更高，可以得到一个优雅的方案： $$ Z \approx \frac{1}{|\mathcal B| + |\mathcal S|} ( \sum_{j\in \mathcal B} e^{s_j-\ln q_j} + \sum_{j\in \mathcal S} e^{s_j-\ln \frac1n} ) $$ 这样loss就是： $$ -\ln\frac {e^{s_i - \ln q_i}} { \sum_{j\in \mathcal B} e^{s_j - \ln q_j} + \sum_{j\in \mathcal S} e^{s_j - \ln \frac1n}} $$ 只需要简单的把2个来源的负样本拼起来即可。

3. 计算两个loss加起来，这是itemSAGE采用的做法，论文里的结果显示这样比上面的第二种做法好。

4. 还有一种错误但是很多人用的方式是全部统一用 $-\ln q_i$ 纠偏。

我在MovieLens-1M数据集上测试了SASRec模型使用不同loss的结果，一直训练到连续10个epoch Recall@10没有提升就停止，结果如下表所示。从表中可以看出不同方法差距其实不大，第二种做法要好一些，错误的做法要差一些。考虑到MovieLens数据集只有6k个user和3k个item，数量很小而且稠密，这个实验结果可信度不高，在具体业务上可能都需要尝试才能得到一个更明确和solid的结果。