GBRank:一种基于回归的学习排序算法

GBRank 是一种 pairwise 的学习排序算法,他是基于回归来解决 pair 对的先后排序问题。在 GBRank 中,使用的回归算法是 GBT(Gradient Boosting Tree) ,可以参考这个, pairwise 相关的可以参考这个

算法原理

一般来说在搜索引擎里面,相关性越高的越应该排在前面。现在 query-doc 的特征使用向量$x$或者$y$表示,假设现在有一个文档对$\left \langle x_i,y_i \right \rangle$,当$x_i$排在$y_i$前面时,我们使用$x_i \succ y_i$来表示。

我们含顺序的 pair 对用如下集合表示(也就是真的$x_i$真的排在$y_i$前面):$$S=\{ \left \langle x_i,y_i \right \rangle | x_i \succ y_i,i = 1…N \}$$

现假设学习的排序函数为$h$,我们希望当$h(x_i)>h(y_i)$时,满足$x_i \succ y_i$的数量越多越好.
现在将$h$的风险函数用如下式子表示:$$R(h) = \frac{1}{2} \sum_{i=1}^N \left( max\{0,h(y_i)-h(x_i)\} \right)^2$$

从$R(h)$可以知道知道每个 pair 对$\left \langle x_i,y_i \right \rangle$的cost为:

可以发现当:

  1. $h(x_i) \geq h(y_i)$,cost代价为0,也就是并不会对最终的风险函数的值产生影响
  2. $h(x_i) < h(y_i)$,cost代价为其差值的平方

上述风险函数直接优化比较困难,这里一个巧妙的解决方案时使用回归的方法,也就是$x_i$或者$y_i$去拟合他们另个预测值目标。为了避免优化函数$h$是一个常量,风险函数一般情况下会加上一个平滑项$\tau$($0 < \tau \leq 1$):$$R(h,\tau ) = \frac{1}{2} \sum_{i=1}^N \left( max\{0,h(y_i)-h(x_i)+\tau \} \right)^2 -\lambda \tau^2 $$

因为当$h$为常量函数时,先前的$R(h)=0$就没有再优化的空间了
其实加了平滑项就变相的转为:如果希望$x_i \succ y_i$,就得有$h(x_i) > h(y_i)+\tau$,也就是更为严格了,多了一个 gap

对于$R(h)$计算$h(x_i)$和$h(y_i)$的负梯度为:$$max\{0,h(y_i)-h(x_i)\} \quad,\quad -max\{0,h(y_i)-h(x_i)\}$$
可以发现当 pair 对符合$\left \langle x_i,y_i \right \rangle$的顺序时,上述的梯度均为0,对于这类 case 就没有必要在去优化了(以为已经满足目标了),但是对于另一类,如果$h$不满足 pair $\left \langle x_i,y_i \right \rangle$,他们对应的梯度为:$$h(y_i)-h(x_i) \quad,\quad h(x_i)-h(y_i)$$

因为此时$h(y_i)>h(x_i)$还有对于上面两个梯度的后面那个式子存在的意义不是很理解-_-

到了这儿,我们知道所谓的训练样本就是对于$x_i \succ y_i$但是$h(y_i) > h(x_i)$,并且使用的是回归方法, GBRank 为其巧妙的找了训练的目标:$x_i$的目标为$h(y_i)+ \tau$以及$y_i$的目标为$h(x_i)- \tau$,也就是在每次迭代是将会构建以下训练集:$$\{(x_i,h(y_i)+\tau),(y_i,h(x_i)-\tau)\}$$

算法步骤

GBRank 使用 GBT 为回归函数,所以整个 GBRank 的算法过程为:
Input :

  • 训练数据集,真实的排序pair对$S=\{(x_1,y_1),(x_2,y_2)…(x_N,y_N)\}$
  • 迭代的次数:$K$

Output:

  • 最终模型$h(x)$

Procedure:

  1. 随机初始化为一个函数$h_o$
  2. 循环$k \in \{1….K\}$
    1. 使用$h_{k-1}$作为近似的$h$函数,我们将对样本的计算结果分到两个不相交的集合:$$S^+=\{\left \langle x_i,y_i \right \rangle \in S | h_{k-1}(x_i) \geq h_{k-1}(y_i)+\tau \}$$和$$S^-=\{\left \langle x_i,y_i \right \rangle \in S | h_{k-1}(x_i) < h_{k-1}(y_i)+\tau \}$$
    2. 使用 GBT 对下面的数据集拟合一个回归函数$g(x)$:$$\{(x_i,h_{k-1}(y_i)+\tau),(y_i,h_{k-1}(x_i)-\tau) | (x_i,y_i) \in S^- \}$$
    3. 进行模型的更新:$$h_k(x) = \frac{kh_{k-1}(x)+\eta g_k(x)}{k+1}$$其中$\eta$为收缩因子
  3. 输出最终的模型$h_k(x)$

注意了,其实这里的回归函数还可以使用其他的回归函数来代替,比如$Linear Regression$之类的

总结

$h(x)$为最终的排序函数, GBRank 在训练时每次迭代中将$h_k(x)$的排序结果与真实结果不一样的样本(就是分错的样本)单独拿出来做训练样本,并且其训练目标为 pair 的另一个预测值作为回归目标,非常巧妙。
此时重新看这个 GBRank 模型与 AdaBoostGBT 其实很大同小异,都是将上一次训练中分错的样本再拿来训练,也是一个提升的模型

在其paper中的实验结果也是要略好于$RankSvm$,但是其比较疼的时其训练还是比较复杂的,或者说比较耗时,其预测也会比较麻烦一点,所以使用时得慎重~

参考

[1]. 2007-GBRank-A Regression Framework for Learning Ranking Functions Using Relative Relevance Judgments

本作品采用 [知识共享署名-非商业性使用-相同方式共享 2.5] 中国大陆许可协议进行许可,我的博客欢迎复制共享,但在同时,希望保留我的署名权kubiCode,并且,不得用于商业用途。如您有任何疑问或者授权方面的协商,请给我留言。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章