目录
概
一种动态选取负样本的策略.
符号说明
- \(I\), items;
- \(I_u\), positive items for user \(u\);
- \(\hat{r}_{ui}\), \((u, i)\) 的 ranking score;
- \(C(\langle i, j \rangle_u) = z_u \delta(\hat{r}_{ui} - \hat{r}_{uj})\), cost, 其中 \(\delta\) 通常为:\[\delta (\hat{r}_{ui} - \hat{r}_{uj}) = \frac{1}{1 + e^{\hat{r}_{ui} - \hat{r}_{uj}}}; \]
Motivation
-
通常我们会用一个模型来建模 ranking score, 比如
\[\hat{r}_{ui} = h(u, i; \theta), \]然后通过最小化 cost \(C(\langle i, j \rangle_u)\) 来最大化 \(\hat{r}_{ui} - \hat{r}_{uj}\).
-
这一步通常需要计算梯度:
\[\frac{\partial C}{\partial \theta} = \frac{\partial C}{\partial (\hat{r}_{ui} - \hat{r}_{uj})} \frac{\partial (\hat{r}_{ui} - \hat{r}_{uj})}{\partial w} =: \lambda_{ij}(\frac{\partial \hat{r}_{ui}}{\partial w} - \frac{\partial \hat{r}_{uj}}{\partial w}). \] -
\(\lambda_{ij}\) 可以看成是 \((i, j)\) 这一对应的权重, 当然了我们也可以将这一部分复杂化, 人为给定权重:
\[\frac{\partial C}{\partial \theta} = f(\lambda_{ij}, \zeta_u) (\frac{\partial \hat{r}_{ui}}{\partial w} - \frac{\partial \hat{r}_{uj}}{\partial w}), \]其中 \(\zeta_u\) 是 \(u\) 的 item list.
-
比如, NDCG 是推荐中一个评价排序质量的一个重要指标, 我们可以令 \(\Delta NDCG_{ij}\) 表示排序的 list 中 (i, j) 交换次序后的 NDCG 的变化的绝对值, 则
\[f(\lambda_{ij}, \zeta_u) = \lambda_{ij} \Delta NDCG_{ij} \]会对于那些变化很大的 pair 赋予更多的权重, 如下图所示:
-
此时会分配更多权重给 (6, 1) 这一 pair. 不过, 这图看似合理, 也有一点问题, 比如 6 本身排得很靠前, 而 1 拍得很靠后, 此时 (6, 1) 的权重依旧是非常大的 (因为衡量的是绝对值), 所以我感觉这可能就不是太合理了.
-
然后这种做法还有一个计算量上的问题, 每次都排序是对于计算量的需求过于庞大了.
Dynamic Negative Sampling
-
作者退而求其次, 只是希望采样一个和相对排序 \(x_j = \text{Pr}(s(j) \le s(i)) \in [0, 1]\) 的采样方式, 即满足:
\[p_j \propto f(\lambda_{ij}, \zeta_u) / \lambda_{ij} = g(x_j), \]注: 严格来说, \(p_j\) 应该为 \(p_{uj}\).
-
这个可以通过如下算法实现:
-
可以发现, 每一次, 我们只需要均匀采样连个 unobserved items, 并再进行一次拒绝采样即可 (方便很多), 可以发现这种情况下
\[p_j = \frac{1}{1 + \beta} \text{Pr}(s(j) > s(l)) + \frac{\beta}{1 + \beta} \text{Pr}(s(j) \le s(l)) \propto (1 - x_j) + \beta x_j =: g(x_j). \] -
更一般地, 作者提出更复杂一点的算法:
- 此时,\[p_j \propto 1C_n^0 (1 - x_j)^n + \sum_{k=1}^n \beta_k C_n^k x_j^k (1 - x_j)^{n-k}. \]