关注我们,一起学习~
标题:Scalar is Not Enough: Vectorization-based Unbiased Learning to Rank
链接:https://arxiv.org/pdf/2206.01702.pdf
代码:https://github.com/Keytoyze/Vectorization
会议:KDD 2022
公司:Salesforce
1. 导读
无偏的排序学习(ULTR)是从有偏的用户点击日志中训练一个无偏的排序模型。当前的大多数 ULTR 方法都是基于检验假设(examination hypothesis,EH),它假设点击概率可以分解为两个标量函数,一个与排序特征有关,另一个与偏差因素有关 。特征、偏差因子和点击之间的相互作用在实践中很复杂,通常不能以这种独立的方式分解。
本文提出了一种基于向量的EH方法,并将点击概率表示为两个向量函数的点积。在此基础上,提出 Vectorization 模型,通过将embedding投影到基向量上来自适应地学习相关embedding并对文档进行排序 。
2. 基础
在本文中,使用粗体字母表示向量(如,
\mathbf{r} ),使用细字母表示标量(如,r)。通常,LTR 的核心是学习一个排序模型f。对于查询,可以按分数降序对文档进行排序。与查询相关的观察数据
q\in Q 可以表示为
\mathcal{D}_q^{full-info}=\{(\mathbf{x}_i,r_i)\}_{i=1}^n ,其中
\mathbf{x}_i \in X 表示编码的查询、文档和用户的特征,
r_i \in \mathbb{R} 表示其真实相关性得分。目标是最小化以下损失函数来得到最优的排序函数,其中L是损失函数,真正的相关性分数
r_i 表示文档与查询的相关性
\mathcal{R}=\frac{1}{|Q|} \sum_{q \in Q} \sum_{\left(\mathbf{x}_{i}, r_{i}\right) \in \mathcal{D}_{q}^{\text {full-info }}} L\left(f\left(\mathbf{x}_{i}\right), r_{i}\right)
相关性分数通常是未知的,通常在离线点击日志中学习排序模型,但是点击日志往往是有偏的。例如,排名较高的文档更有可能被观察和点击(称为位置偏差)。与q相关的观测数据可以表示为
\mathcal{D}_q=\{(\mathbf{x}_i,\mathbf{t}_i,c_i)\}_{i=1}^n ,其中
c_i\in \{0,1\} 表示点击信号,
t_i\in \mathcal{T} 表示导致点击有偏差的偏差因素,例如文档位置、上下文信息、文档周围的其他点击或演示风格。不限制
t_i 的确切含义,能够将本文的结论推广到大多数以前的 ULTR 方法。为方便起见,令
\mathcal{D}=\left\{(\mathbf{x}, \mathbf{t}) \mid(\mathbf{x}, \mathbf{t}, c) \in \mathcal{D}_{q}, q \in Q\right\} 表示曾经出现在数据集中的所有排序特征和偏差因子对。
假设文档的点击率仅取决于其排序特征和偏差因素。
c(\mathbf{x,t})=P_r(c=1|\mathbf{x,t}) 表示点击率函数。为了从点击数据中推导出相关性,目前大多数 ULTR 方法基于检查假设 (EH) 来模拟用户的点击行为。假设如果该文档被观察到并且相关,则用户点击该文档。进一步假设相关性r取决于排名特征x并且被观察到的o取决于偏差因子 ,则可以表示为下式,这里的r和o得到的都是标量。
c(\mathbf{x}, \mathbf{t})=r(\mathbf{x}) \cdot o(\mathbf{t}), \quad \forall(\mathbf{x}, \mathbf{t}) \in \mathcal{D}
3. 方法
image.png
3.1 基于向量的EH 点击、偏差因素和特征之间的相互作用在现实世界中非常复杂。上面提到的c(x,t)分解方式在实际问题中通常不存在,因为这种形式产生的函数族不能涵盖所有可能的点击率函数。
为了捕捉相关性和观察数据之间的复杂交互,首先将基于标量的 EH 扩展到基于向量的形式。即点击函数c(x,t)可以写成两个函数的点积,一个在排名特征x上,另一个在偏差因子t上。简单来说就是原始的情况是用标量相乘,而这里是向量embedding相乘(相关性embedding和观察embedding) 。
c(\mathbf{x,t})=\mathbf{r(x)}^{\top}\mathbf{o(t)}
3.2 使用相关embedding进行排序 但是,无法直接根据相关性embedding直接进行排序(因为它是一个向量),因此不能直接应用基于向量的 EH。对于给定查询q,具有n个排序特征
\mathbf{x_1,...,x_n} ,目标是使用它们的相关embedding
\mathbf{r(x_1),...,r(x_n)} 进行排序。简单地对向量中的元素进行平均并根据平均值对所有向量进行排序是不合适的。一个方案是为查询q找到一个公共基向量
\tilde{\mathbf{o}_q} \in \mathbb{R}^d ,并将每个相关性embedding投影到
\tilde{\mathbf{o}_q} 上,如下所示,然后可以像传统的 LTR 方法一样使用标量
r(\mathbf{x}_i) 进行排序。
r\left(\mathbf{x}_{i}\right)=\mathbf{r}\left(\mathbf{x}_{i}\right)^{\top} \widetilde{\mathbf{o}_{q}}, \quad i \in[n]
3.3 找到基向量 假设已经得到函数
\mathbf{r(·)} 和
\mathbf{o(·) } ,目标是在无监督的情况下找到基向量。首先,假设对于任意两个文档,如果修正了偏差因子,它们的点击率顺序等于它们的相关性顺序,公式如下,
c\left(\mathbf{x}_{1}, \mathbf{t}\right) \geq c\left(\mathbf{x}_{2}, \mathbf{t}\right) \Longleftrightarrow \mathbf{x}_{1} \geq_{r} \mathbf{x}_{2}, \quad \forall\left(\mathbf{x}_{1}, \mathbf{t}\right),\left(\mathbf{x}_{2}, \mathbf{t}\right) \in \mathcal{D}
对于一个查询q,他对应的特征是
\{\mathbf{x}_1,...,\mathbf{x}_n\} ,假设存在公共偏差因子t与上述特征一起存在于
D 中,则可以表示为下式,
\widetilde{\mathbf{o}_{q}}=\mathbf{o}(\mathbf{t}), \quad \text { s.t. }\left(\mathbf{x}_{i}, \mathbf{t}\right) \in \mathcal{D}, \forall i \in[n] .
\mathbf{r(x_i)}^{\top}\mathbf{\tilde{o_q}}=\mathbf{r(x_i)}^{\top}\mathbf{o(t)} 表示计算的点击率。如果存在多个 t,则很难决定使用哪一个。使用最大似然估计 (MLE) 来选择最可能符合当前特征
\mathbf{x}_1,...,\mathbf{x}_n 的偏置因子
t^* 。假设 D 是从联合分布P(X,T)生成的,其中X是排名特征,T是偏差因子,公式如下,P(T|X)可以从 D 中估计出来。选择与排名特征相关的最可能的偏差因子作为q的基向量 。
\widetilde{\mathbf{o}_{q}}=\mathbf{o}\left(\mathbf{t}^{*}\right), \quad \text { where } \mathbf{t}^{*}=\arg \max _{\mathbf{t}} \prod_{i=1}^{n} P\left(T=\mathbf{t} \mid X=\mathbf{x}_{i}\right)
可能存在不重叠的问题,例如,假设 t 表示文档的位置。假设一个排名特征
\mathbf{x}_1 总是分配给第一个位置,另一个排名特征
\mathbf{x}_2 总是分配给第二个位置。无论如何选择位置t,都存在一个排序特征
\mathbf{x\in \{x_1,x_2\}} 使得P(t|x)=0。
根本原因是X和T可能不重叠。为了解决这个问题,首先将 D 转换为
\mathcal{D}_{\mathbf{o}}=\{(\mathbf{x}, \mathbf{o}(\mathbf{t})):(\mathbf{x}, \mathbf{t}) \in \mathcal{D}\} 。然后使用MLE,公式如下,其中P(O|X)可以从
\mathcal{D_o} 估计。
\mathbf{O} 比原始偏差因子更密集,这可以缓解重叠问题。
\widetilde{\mathbf{o}_{q}}=\arg \max _{\mathbf{o}} \prod_{i=1}^{n} P\left(\boldsymbol{O}=\mathbf{o} \mid \boldsymbol{X}=\mathbf{x}_{i}\right)
将P(O|X) 建模为多元高斯分布(其所有分量都是独立的),因为始终可以建立P(O|X)>0,这避免了重叠问题并使得估计更稳定。假设
P\left(\boldsymbol{O} \mid \boldsymbol{X}=\mathbf{x}_{i}\right) \sim \mathcal{N}\left(\boldsymbol{\mu}\left(\mathbf{x}_{i}\right), \boldsymbol{\sigma}\left(\mathbf{x}_{i}\right)^{2}\right) ,其中μ和σ是给定x时的均值和均方差,公式如下,
\begin{aligned}
\widetilde{\mathbf{o}_{q}} &=\arg \max _{\mathbf{o}} \prod_{i=1}^{n} P\left(\boldsymbol{O}=\mathbf{o} \mid \boldsymbol{X}=\mathbf{x}_{i}\right) \\
&=\arg \max _{\mathbf{0}} \prod_{i=1}^{n} \frac{1}{\boldsymbol{\sigma}\left(\mathbf{x}_{i}\right) \sqrt{2 \pi}} \exp \left(-\frac{\left(\mathbf{o}-\boldsymbol{\mu}\left(\mathbf{x}_{i}\right)\right)^{2}}{2 \boldsymbol{\sigma}\left(\mathbf{x}_{i}\right)^{2}}\right) \\
&=\arg \max _{\mathbf{o}} \sum_{i=1}^{n}\left(-\frac{\left(\mathbf{o}-\boldsymbol{\mu}\left(\mathbf{x}_{i}\right)\right)^{2}}{2 \boldsymbol{\sigma}\left(\mathbf{x}_{i}\right)^{2}}\right)
\end{aligned} 使得导数为0,最终的公式为
\widetilde{\mathbf{o}_{q}}=\frac{\sum_{i=1}^{n} \frac{1}{\sigma\left(\mathbf{x}_{i}\right)^{2}} \boldsymbol{\mu}\left(\mathbf{x}_{i}\right)}{\sum_{i=1}^{n} \frac{1}{\sigma\left(\mathbf{x}_{i}\right)^{2}}} 。它表明对于给定的查询,基向量可以通过与q相关的所有排序特征的加权平均值来计算。方差越大,权重越小。方差表示模型的不确定性,它可以根据不确定性综合考虑基向量,这有助于提高鲁棒性。
4. 模型实现
image.png
4.1 训练阶段 step1 :首先学习两个模型:相关模型r和观察模型o 。对于数据
\mathcal{D}_q=\{(\mathbf{x_i,t_i},c_i)\}_{i=1}^n 的查询q,使用基于 softmax 的交叉熵的 list-wise 损失函数,如下所示,
L_{q}^{\text {click }}=-\sum_{i=1}^{n} c_{i} \log \frac{\exp \left(\mathbf{r}\left(\mathbf{x}_{i} ; \theta_{r}\right)^{\top} \mathbf{o}\left(\mathbf{t}_{i} ; \theta_{o}\right)\right)}{\sum_{j=1}^{n} \exp \left(\mathbf{r}\left(\mathbf{x}_{j} ; \theta_{r}\right)^{\top} \mathbf{o}\left(\mathbf{t}_{j} ; \theta_{r}\right)\right)}
step2 :在观察模型收敛后,需要对其进行修正并学习一个估计分布P(O|X)的基模型
\mathbf{v} ,以找到推理阶段的基向量 。固定一个高斯似然来对分布进行建模,v 的输出由预测均值和预测方差组成,其中μ和σ有基模型v得到,
\left[\boldsymbol{\mu}\left(\mathbf{x}_{i}\right), \sigma^{2}\left(\mathbf{x}_{i}\right)\right]=\mathbf{v}\left(\mathbf{x}_{i} ; \theta_{v}\right)
想让由μ和σ参数化的高斯分布接近真实分布P(O|X)。可以通过最小化以下回归损失得到,在实践中,训练模型来预测对数方差,
\mathbf{s(x_i)}=\log \sigma^2(\mathbf{x_i}) ,因为它在数值上比回归方差更稳定,因为损失避免了潜在的除以零
L_{q}^{\text {base }}=\frac{1}{2} \sum_{i=1}^{n}\left(\frac{\left\|\boldsymbol{\mu}\left(\mathbf{x}_{i}\right)-\mathbf{o}\left(\mathbf{t}_{i}\right)\right\|_{2}^{2}}{\boldsymbol{\sigma}^{2}\left(\mathbf{x}_{i}\right)}+\log \sigma^{2}\left(\mathbf{x}_{i}\right)\right)+\lambda\left\|\theta_{v}\right\|_{2}^{2}
4.2 预测阶段 在推理阶段,使用相关性模型r和模型v来估计相关性标量以进行排序。对于查询q,首先计算q的基向量,然后将每个相关embedding投影到基向量上,然后计算得分。
5. 伪代码
训练:第 1 行初始化所有参数。第 2-7 行,通过基于向量的 EH 联合训练相关性模型和观察模型。第 8-12 行,训练基础模型,让分布估计接近观察embedding分布。
推理:第 1-2 行,计算观察数据的embedding分布以对特征进行排序。在第 3 行,计算基向量。第 4-5 行,将相关性embedding投影到基向量上计算排序分数。
6. 结果