Learning a Deep Listwise Context Model for Ranking Refinement
论文来自SIGIR18，https://arxiv.org/abs/1804.05936
代码已开源：https://github.com/QingyaoAi/Deep-Listwise-Context-Model-for-Ranking-Refinement
Motivation
排序学习是信息检索中受到广泛重视和研究的一个任务。然而在常规的排序学习算法中，模型从标注的数据中学习到全局的排序函数，它在整体的平均上取得了不错的表现。但在个别的查询而言却是次优的，因为它忽视了不同文档的相关文档在特征空间的分布是不同的。
例如，考虑词的匹配程度和检索结果的新鲜度两个特征，显然，对于查询“生活大爆炸第一季在线观看”，词的匹配程度要比检索结果的新鲜度更重要。但是对于查询”政治新闻“，检索结果的新鲜度则更重要。无论如何设计表示查询和文档的特征向量，都很难解决这样的全局排序函数的问题。
在这篇文章中，作者提出可以动态地为每个查询学习一个局部模型，并使用它来优化排名结果。大概的做法是通过使用GRU模型来学习排序靠前的文档形成的局部排序上下文信息，然后用于重排序。
Formulation
给定一个特别的查询 $q$，向量 $\boldsymbol{x}_{(q, d)}$ 代表文档 $d$ 的特征表示。传统的Learning to rank算法假设存在一个最优的全局排序函数 $f$，它的输入是 $\boldsymbol{x}_{(q,d)}$ ，输出是该文档的排序分数。通过优化如下的损失函数求解最优的 $f$：
\[\mathcal{L}=\sum_{q \in Q} \ell\left(\left\{y_{(q, d)}, f\left(\boldsymbol{x}_{(q, d)}\right) \mid d \in D\right\}\right)\]$Q$ 是所有可能查询的集合，$D$ 是候选文档的集合，$\ell$ 是局部损失，它由预测的文档分数和对应的相关性准则$y_{(q, d)}$ 计算得到。
假设可以利用局部上下文模型 $I(R_q,X_q)$ 捕获查询 $q$ 的局部排序上下文，其中 $R_{q}=\{d$ sorted by $f(x_{(q, d)})\}$，$X_{q}=\{\boldsymbol{x}_{(q, d)} \mid d \in R_{q}\}$。此时排序学习的损失函数是：
\[\mathcal{L}=\sum_{q \in Q} \ell\left(\left\{y_{(q, d)}, \phi\left(\boldsymbol{x}_{(q, d)}, I\left(R_{q}, X_{q}\right)\right) \mid d \in D\right\}\right)\]其中 $\phi$ 是一个评分函数，它基于文档的特征和局部上下文模型 $I(R_q,X_q)$ 给文档进行打分。目标是寻找最优的 $I$ 和 $\phi$ 使得损失函数最小化。
为了有效地利用局部排序上下文，$I$ 的设计应该满足两点要求：
- 它应该能够直接处理标量特征。 多数排序学习的模型将排序信号（离散或连续）转换为标量向量。 如果列表式上下文模型 $I$ 不能直接处理这些标量，则需要从文档中提取原始数据，并手动使用启发式方法来对局部排序上下文进行建模，这既困难又效率低下。
- 它应考虑检索到的排序靠前的文档的位置作用。 排名靠前的结果中的文档的价值并不相同，其按全局排序函数排序的位置也很重要。 如果没有明确地建模位置作用，我们将失去全局排序信息并损害整个系统的泛化能力。
DLCM模型
在本文中，作者提出了DLCM模型。模型的总体思路是使用RNN对每个查询的排名靠前的检索的文档进行编码，并根据编码后的局部上下文模型优化排序列表。
使用DLCM进行文档排序的流程包括三个步骤。 第一步是使用标准的排序学习算法进行初始的检索。在这一步里，每个查询文档对 $(q,d)$ 被转换为特征向量 $\boldsymbol{x}_{(q,d)}$，然后基于全局的排序函数生成长度为 $n$ 的排序列表 $R_q^n$。第二步是编码的过程，使用RNN编码检索结果靠前的文档的特征向量$X_q^n$，RNN从最低位置到最高位置逐个编码文档，并生成一个潜在向量 $s_n$ 来表示编码后的局部上下文模型 $I(R_q,X_q)$。第三步是重排过程，使用基于 $s_n$ 和RNN隐层输出 $\boldsymbol{o}$ 的局部排序函数 $\phi$ 对排序结果靠前的文档进行重排序。
输入文档的表示
作者使用了一个双层的前馈神经网络来学习原始特征的抽象：
\[\begin{array}{l} z_{i}^{(0)}=\boldsymbol{x}_{\left(q, d_{i}\right)} \\ z_{i}^{(l)}=e l u\left(W_{z}^{(l-1)} \cdot z_{i}^{(l-1)}+b_{z}^{(l-1)}\right), l=1,2 \end{array}\]其中，$W_{z}^{(l)}$ 和 $b_{z}^{(l)}$ 分别是第 $l$ 层权重矩阵和偏置。$elu$ 是非线性的激活函数。作者然后将 $z_{i}^{(2)}$ 与原始的特征向量 $\boldsymbol{x}_{(q, d_{i})}$ 拼接起来得到新的输入向量 $\boldsymbol{x}_{(q, d_{i})}^{\prime}$，令 $\alpha$ 和 $\beta$ 分别是 $z_{i}^{(2)}$ 和 $\boldsymbol{x}_{(q, d_{i})}$ 的维度。
编码局部上下文
排序函数得到的前 $n$ 个检索结果和对应的特征向量 $X_{q}^{n}=\{\boldsymbol{x}_{(q, d_{i})} \mid d_{i} \in R_{q}^{n}\}$，将其作为输入，输入到GRU网络中，GRU的计算过程如下：
\[\begin{aligned} \boldsymbol{o}_{t} &=\left(1-\boldsymbol{u}_{t}\right) \odot \boldsymbol{o}_{t-1}+\boldsymbol{u}_{t} \odot \boldsymbol{s}_{t} \\ \boldsymbol{u}_{t} &=\sigma\left(\boldsymbol{W}_{u}^{x} \cdot \boldsymbol{x}_{t}+\boldsymbol{W}_{u}^{s} \cdot \boldsymbol{o}_{t-1}\right) \\ \boldsymbol{s}_{t} &=\tanh \left(\boldsymbol{W}^{x} \cdot \boldsymbol{x}_{t}+\boldsymbol{W}^{s} \cdot\left(\boldsymbol{r}_{t} \odot \boldsymbol{o}_{t-1}\right)\right) \\ \boldsymbol{r}_{t} &=\sigma\left(\boldsymbol{W}_{r}^{\boldsymbol{x}} \cdot \boldsymbol{x}_{t}+\boldsymbol{W}_{r}^{s} \cdot \boldsymbol{o}_{t-1}\right) \end{aligned}\]网络最后的状态 $s_n$ 就是编码后的局部上下文模型 $I(R_q^n, X_q^n)$。之所以选用RNN完成编码，一来是因为RNN天然地可以将当前状态和之前的状态结合起来，同时又可以捕获位置信息。作者将检索后的文档从低位置到高位置依次输入GRU网络，因此高位置的文档对于最终的网络状态有更重要的影响。
使用局部上下文进行重排
作者使用了类似于机器翻译中的注意力函数作为评分函数，它考虑了RNN的隐层状态和局部排序上下文在编码后的潜在表示。令 $\boldsymbol{o}_{n+1-i}$ 是文档 $d_i \in R_q^n$ 的输出表示，那么局部排序函数 $\phi$ 为：
\[\phi\left(\boldsymbol{o}_{n+1-i}, \boldsymbol{s}_{n}\right)=\boldsymbol{V}_{\phi} \cdot\left(\boldsymbol{o}_{n+1-i} \cdot \tanh \left(\boldsymbol{W}_{\phi} \cdot \boldsymbol{s}_{n}+\boldsymbol{b}_{\phi}\right)\right)\]损失函数
作者实验了三种不同的损失函数，分别是ListMLE，SoftRank和Attention Rank。
-
ListMLE 是一个列表式的损失函数，它将排序学习问题形式化为最小化概率损失的问题。它将排序视作序列化选择的问题，它定义从文档集合 $\pi_m^n=\{d_j \mid j \in [m,n]\}$ 中选择文档 $d_i$ 的概率为：
\[P\left(d_{i} \mid \pi_{m}^{n}\right)=\frac{e^{S_{i}}}{\sum_{j=m}^{n} e^{S_{j}}}\]其中，$S_i$ 和 $S_j$ 分别是文档 $d_i$ 和 $d_j$ 的排序分数。如果我们从排序列表的顶部开始选择，然后在每一步骤之后从候选集中删除所选文档，因此给定排序分数 $S$ 下的排序列表的概率为：
\[P\left(R_{q}^{n} \mid S\right)=\prod_{i=1}^{n} P\left(d_{i} \mid \pi_{i}^{n}\right)=\prod_{i=1}^{n} \frac{e^{S_{i}}}{\sum_{j=i}^{n} e^{S_{j}}}\]令 $\mathcal{R}_{q}^{*}$ 是最优的排序列表，那么ListMLE的损失被定义为 $\mathcal{R}_{q}^{*}$ 的负对数似然。
-
SoftRank 直接优化了信息检索中的排序准则，如NDCG等。令$S_i$ 和 $S_j$ 分别是文档 $d_i$ 和 $d_j$ 对于查询 $q$ 的排序分数，SoftRank 函数假设文档 $d_i$ 的真实排序分数 $S_i^{\prime}$ 是从高斯分布 $\mathcal{N}(S_i,\sigma_s^2)$ 中采样得到，因此 $d_i$ 的排序高于 $d_j$ 的概率为：
\[\pi_{i j} \equiv \operatorname{Pr}\left(S_{i}^{\prime}-S_{j}^{\prime}>0\right)=\int_{0}^{\infty} \mathcal{N}\left(S \mid S_{i}-S_{j}, 2 \sigma_{s}^{2}\right) d S\]令 $p_{j}^{(1)}(r)$ 是 $d_j$ 初始的排序分布，$d_j$ 是排序列表中唯一的文档。那么当新增第 $i$ 个文档时，有
\[p_{j}^{(i)}(r)=p_{j}^{(i-1)}(r-1) \pi_{i j}+p_{j}^{(i-1)}(r)\left(1-\pi_{i j}\right)\] -
Attention Rank 是作者提出的新的损失函数。令相关性标签 $y_{(q,d_i)}$ 代表在查询 $q$ 下选择文档 $d_i$ 的信息增益，因此排序列表 $R_{q}^{n}$ 的最优的注意力分配策略是：
\[a_{i}^{y}=\frac{\psi\left(y_{\left(q, d_{i}\right)}\right)}{\sum_{d_{k} \in R_{q}^{n} \psi\left(y_{\left(q, d_{k}\right)}\right)}}\]其中，$\psi(x)$ 是校正指数函数。利用上面的注意力策略和最优的注意力策略的交叉熵定义损失函数：
\[\ell\left(R_{q}^{n}\right)=-\sum_{d_{i} \in R_{q}^{n}}\left(a_{i}^{y} \log \left(a_{i}^{S}\right)+\left(1-a_{i}^{y}\right) \log \left(1-a_{i}^{S}\right)\right)\]
Conclusion
在本文中，作者提出了一个DLCM模型，以改进局部排序上下文的排序学习算法。 该模型使用RNN对全局排序算法中检索到的最热门文档进行编码，并使用局部上下文模型优化排序列表。 这个模型可以通过基于注意力的列表式排序损失进行训练，并且可以直接应用到现有的排序学习模型上，而无需进行额外的特征提取或检索处理。
