Learning Groupwise Multivariate Scoring Functions Using Deep Neural Networks
来自ICTIR2019，https://doi.org/10.1145/3341981.3344218
Motivation
不同于分类或回归，排序的主要目标不是为每个文档分配标签或值，而是给定一系列文档，产生一个有序的列表，使得整个列表的效用最大化。换言之，在排序中，我们更关注文档相关性的相对顺序（对于某些相关性而言），而不是其绝对大小。
在排序学习的背景下，人们对排序中的相对性建模进行了广泛的研究。排序学习旨在学习一种评分函数，它在有监督的设置下将特征向量映射为实值分数，由此得到的分数可以得到对文档的排序。现有的大多数排序学习算法都通过优化 pairwise 或 listwise 的损失函数来学习参数化的评分函数。
尽管有效，但大多数现有的排序学习的框架都受限于单变量评分函数的范式——待排序列表中每个文档的相似度评分的计算独立于列表中其他的文档。这样会导致排序结果是次优的，主要有两方面原因：（1）单变量的评分函数在建模跨文档相关性时能力有限。（2）通过文档对之间的比较可以比绝对评分更快、更一致地获得偏好判断。
基于以上的理由，作者假设文档的相关性评分应该通过与列表中的其他文档进行比较来计算。因此作者提出了排序学习下的多变量评分函数 $f: \mathcal{X}^{n} \rightarrow \mathbb{R}^{n}$，其中 $\mathcal{X}$ 是所有文档的集合。该函数以 $n$ 个文档的向量作为输入，输出 $n$ 维的实值向量，输出向量中的每个元素都代表了该位置的文档对于别的文档的相对相关性。在此基础上，作者提出了一种分组的评分函数，它由DNN网络参数化得到。GSF学习对固定大小组的文档进行评分，它可以扩展到为任意长度的列表中的文档进行评分，并通过蒙特卡罗采样策略进行加速。
Formulation
令 $\psi=(\boldsymbol{x}, \boldsymbol{y}) \in \mathcal{X}^{n} \times \mathbb{R}^{n}$ 是一个训练样本，其中 $\boldsymbol{x}$ 是 $n$ 个文档 $x_i, 1 \leq i \leq n$ 的向量，$\boldsymbol{y}$ 是 $n$ 个相关性分数 $y_i$ 的分数，$\Psi$ 是训练数据的集合，排序学习的目标是学习到如下的映射函数 $f:\mathcal{X}^{n} \rightarrow \mathbb{R}^{n}$，然后最小化如下的损失函数：
\[\mathcal{L}(f)=\frac{1}{|\Psi|} \sum_{(\boldsymbol{x}, \boldsymbol{y}) \in \Psi} \ell(\boldsymbol{y}, f(\boldsymbol{x}))\]$\ell(\cdot)$ 是局部损失函数。
正如前文所提到的，不同的排序学习算法之间的主要差异在于如何定义评分函数 $f(\cdot)$ 和损失函数 $\ell(\cdot)$。多数的排序学习算法都假设了单变量的评分函数 $u: \mathcal{X} \rightarrow \mathbb{R}$，它独立于其他文档为每个文档单独计算了分数：
\[f(x)\mid _{i}=u\left(x_{i}\right), 1 \leq i \leq n\]其中 $f(x)\mid_{i}$ 代表了 $f$ 的第 $i$ 个维度。$u(\cdot)$ 计算得到的分数只取决于自身，换言之，如果固定 $x_i$ 而改变别的文档，不影响 $u(x_i)$ 的输出。
在本文中，作者提出探索排序学习中的多变量评分函数 $f:\mathcal{X}^{n} \rightarrow \mathbb{R}^{n}$。按照之前的讨论，这个评分函数理论上可以捕获文档间的关系，然后产生相对的评分。也就是说，替换 $x_i$ 会导致列表中每个文档的评分都会改变。
然而，实际上，学习多变量评分函数并非易事。 上面的讨论有一个简化的假设，即列表中的文档数 $n$ 在所有训练样本中都是恒定的。 但是，通常并不是如此。实际上文档长度是任意的，并且在训练或验证集中有所不同。 接下来，我们将介绍作者提出的多变量评分函数，该函数适用于排序学习的任务，并且经过有效的训练和评估。
GSF Model
这一部分我们将详细地介绍作者提出的多变量评分函数——Groupwise Scoring Functions (GSF)。GSF有如下的形式：$g(\cdot;\theta): \mathcal{X}^{m} \rightarrow \mathbb{R}^{m}$，它由一个DNN网络构成，将一组里的 $m$ 个文档映射到相同大小的向量中。
使用DNN参数化
先定义输入层。文档 $x$ 可以表示为两部分特征的拼接——稀疏文本特征 $x^{embed}$ 和稠密特征 $x^{dense}$。因此输入层由所有 $m$ 个文档的拼接得到：
\[\boldsymbol{h}_{0}=\operatorname{concat}\left(x_{1}^{\mathrm{embed}}, x_{1}^{\mathrm{dense}}, \cdots, x_{m}^{\mathrm{embed}}, x_{m}^{\mathrm{dense}}\right)\]给定如上的输入层，作者构建了具有3层隐藏层的前馈神经网络：
\[\boldsymbol{h}_{k}=\sigma\left(\boldsymbol{w}_{k}^{T} \boldsymbol{h}_{k-1}+\boldsymbol{b}_{k}\right), k=1,2,3\]其中激活函数 $\sigma(t)=\max(t,0)$。最终的GSF函数定义为：
\[g(\boldsymbol{x})=\boldsymbol{w}_{o}^{T} \boldsymbol{h}_{3}+\boldsymbol{b}_{\boldsymbol{o}}\]输出层的网络包含了 $m$ 个单元，每个为 $m$ 个文档的每个产生一个分数。
扩展到任意长度的列表
上文所述的评分函数 $g(\cdot)$ 的定义域 $\mathcal{X}^{m}$ 的维度是固定的，而在排序学习的场景下，不同查询得到的文档数量是变化的，因此需要将 $g(\cdot)$ 扩展到应用于不同长度的文档排序。
给定任意长度 $n$ 的文档列表 $\boldsymbol{x}$ 和 GSF函数 $g: \mathcal{X}^{m} \rightarrow \mathbb{R}^{m}$ ，作者提出计算 $\boldsymbol{x}$ 中大小为 $m$ 的排列，并在这个过程中累积分数。令 $\Pi_m(\boldsymbol{x})$ 代表 $n$ 个文档集合中大小为 $m$ 的所有的 $\frac{n!}{(n-m)!}$ 个排列的集合。一个排列 $\pi_k$ 可以认为是一组 $m$ 个文档。因此 $g(\pi_k)$ 包含了该组里每个文档 $x_i \in \pi_k$ 相对于其他文档的评分，该组的评分 $g$ 后续用于全部 $n$ 个文档的分数：
\[h(\pi, x)=\left\{\begin{array}{ll} \left.g(\pi)\right|_{\pi^{-1}(x)}, & \text { if } x \in \pi \\ 0, & \text { otherwise } \end{array}\right.\]其中 $\pi^{-1}(x)$ 表示 $x$ 在 $\pi$ 中的位置。最终的分数 $f(\cdot)$ 由如下的式子计算得到：
\[\left.f(\boldsymbol{x})\right|_{i}=\sum_{\pi_{k} \in \Pi_{m}(\boldsymbol{x})} h\left(\pi_{k}, x_{i}\right), 1 \leq i \leq n\]加速训练和推断
上述GSF的一个问题是枚举空间的阶乘式增长，对于很大的 $n$，集合 $\Pi_m(\boldsymbol{x})$ 增长迅速，因此计算 $g(\cdot)$ 成为一个困难的问题。假设 $g(\cdot)$ 的计算复杂度是 $O$，那么评分函数的计算复杂度为
\[O\left(m \frac{n !}{(n-m) !}\right)\]为了减少GSF的复杂度，作者提出将 $f(\boldsymbol{x})\mid_{i}$ 中的求和替换为期望：
\[\left.f(\boldsymbol{x})\right|_{i}=\mathbb{E}_{\pi \ni x_{i}}\left[\left.g\left(\pi, x_{i}\right)\right|_{\pi^{-1}\left(x_{i}\right)}\right], 1 \leq i \leq n\]上式的期望可以使用蒙特卡罗方法近似计算。对于每个训练样本，从随机打乱后的文档列表里中采样子序列构建一组文档。这样的降采样方法可以减少时间复杂度到 $O(mn)$，每个文档 $x_i \in \boldsymbol{x}$ 都会出现在 $m$ 个组中，因此每篇文档都会与列表中的其他文档进行比较，每组内文档的位置是均匀分布的。给定足够的训练数据，使用该采样策略训练的GSF会渐近地接近使用所有排列训练的GSF，并且对于输入列表中的文档顺序也将具有不变性。
损失函数
在实际使用中，作者发现交叉熵损失更为有效。因此，定义损失函数如下：
\[\ell(\boldsymbol{y}, f(\boldsymbol{x}))=-\sum_{i=1}^{n} \frac{y_{i}}{Y} \cdot \log p_{i}\]其中 $Y=\sum_{y \in \boldsymbol{y}} y$ 是标准项，$p_i$ 是经过softmax之后的分数 $f(\boldsymbol{x})$：
\[\left.\operatorname{Softmax}(t)\right|_{i}=\frac{e^{t_{i}}}{\sum_{j=1}^{n} e^{t_{j}}}, 1 \leq i \leq n\]