上一篇Ranking Relevance in Yahoo Search一文中提到的logistRank方法吃不太透,没展开。这两天刚好中秋,整理出来。
介绍思路如下:

  1. gbrank:gbdt怎么用在排序,如何进行pair-wise训练
  2. logistRank:logistRank和gbrank的区别,和关于scale因子的思考

本篇博文分两篇将从应用出发,往算法细节深入了解的顺序进行介绍。上篇:第1部分,介绍基础的gbrank,可以知道gbdt用在learning to rank领域的应用法子。第2部分,介绍logistRank,希望进一步理解前一篇笔记中作者提出改进。下篇:主要按提出者Jerome H. Friedman论文思路介绍gbdt

相关拓展:纵向可以往前看adboost及在learning to rank(ltr)应用[2], 或者往后看xgboost、FastBDT、LightGBM。横向可以看看bagging的一些算法,包括随机森林。
ltr中常用的还有rankSVM(应用svm分类器)[3,4,5]、rankNet(应用神经网络)[6]、LambdaMART[9]

gbrank:如何进行pair-wise训练

learning to rank需要解决的问题是给定一个query,如何选择最相关的document。gbrank核心为将排序问题转化为一组回归问题,对于回归问题可以用gbdt进行求解,也可以用其他的回归函数[7]。
先介绍一组记号,对于所有的query-document pair,我们从pair抽取出一系列特征对其进行表示。例如query1-document1记为$x$,query1-document2记为$y$。记$x \succ y$表示,用户发起查询query1时,$x$比$y$更适合,更加满足query1的需求。记训练集合为$$S = \left\{ {\left\langle {{x_i},{y_i}} \right\rangle |{x_i} \succ {y_i},i = 1,...,N} \right\}$$
给定排序函数空间 $H$,我们希望得到一个排序函数$h$($h \in H$),当$x_i \succ y_i$时,我们有$h\left( {{x_i}} \right) \ge h\left( {{y_i}} \right)$。损失函数定义为如下形式:$$ R\left( h \right) = {1 \over 2}{\sum\limits_{i = 1}^N {\left( {\max \left\{ {0,h\left( {{y_i}} \right) - h\left( {{x_i}} \right)} \right\} } \right)}^2}$$
这个函数可以解读为,对于训练数据中的一个 $\left\langle {{x_i},{y_i}} \right\rangle $,如果$h$学到了这种偏序关系,那么有$h(x_i)>h(y_i)$,$h$对于损失函数的贡献为0,否则为${\left( {h\left( {{y_i}} \right) - h\left( {{x_i}} \right)} \right)^2}$。直接优化loss比较困难,可以通过改变$h(x_i)$或者$h(y_i)$达到减少loss的目的,例如用回归的方式来拟合$h(x_i)$、$h(y_i)$。
h(yi)-h(xi)

为了避免优化函数$h$是一个常量,在loss fuction上增加一个平滑项$\tau $, $0 < \tau \le 1$。在实际应用中$\tau$为固定常数。$$R\left( {h,\tau } \right) = {1 \over 2}{\sum\limits_{i = 1}^N {\left( {\max \left\{ {0,h\left( {{y_i}} \right) - h\left( {{x_i}} \right) + \tau } \right\}} \right)} ^2} - \lambda {\tau ^2}$$

因为当$h$为常量函数时,原$R(h)=0$就没有再优化的空间了。
其实加了平衡项,就变相转为:如果希望${{x_i} \succ {y_i}}$,就得有$h\left( {{x_i}} \right) \ge h\left( {{y_i}} \right)+\tau$,更加严格。多了一个gap[8]

按一般套路,用梯度下降的方法去最小化loss function。假设有未知函数$h(x_i)$,$h(y_i)$,$i=1,...,N$,loss $R(h)$对$h(x_i)$,$h(y_i)$的负梯度分别为$$\max \left\{ {0,h\left( {{y_i}} \right) - h\left( {{x_i}} \right)} \right\},-\max \left\{ {0,h\left( {{y_i}} \right) - h\left( {{x_i}} \right)} \right\}$$。当$h$满足$< {x_i},{y_i} >$偏序关系,$h\left( {{y_i}} \right) - h\left( {{x_i}} \right) < 0$,上面两个梯度都会为0。当$h$不满足$< {x_i},{y_i} >$偏序关系时,梯度为$$h\left( {{y_i}} \right) - h\left( {{x_i}} \right),h\left( {{x_i}} \right) - h\left( {{y_i}} \right)$$
接下来,还需要知道如何将梯度作用到$h$的更新上,通过设定$x_i$的目标值为$h\left( {{y_i}} \right) + \tau $。$y_i$的目标值为$h\left( {{x_i}} \right) - \tau $。因此在每轮迭代中,当$h$不满足$< {x_i},{y_i} >$会产生一组数据:$$\left\{ {\left( {{x_i},h\left( {{y_i}} \right) + \tau } \right),\left( {{y_i},h\left( {{x_i}} \right) - \tau } \right)} \right\}$$ ,我们需要拟合本轮产生的所有负例。下面介绍详细算法
gbRank算法

  1. 估计一个初始函数$h_0$(任意选择一个都可以)。
  2. 根据上一轮的$h_{k-1}$,将数据分为两个不相交的子集(正例和负例两个集合): $${S^ + } = \{ \left\langle {{x_i},{y_i}} \right\rangle \in S|{h_{k - 1}}({x_i}) \ge {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 \}$$。其中$S^-$作为我们下一步的训练集。
  3. 使用GBDT拟合负例集合中的数据$$\{(x_i,h_{k-1}(y_i)+\tau),(y_i,h_{k-1}(x_i)-\tau) | (x_i,y_i) \in S^- \}$$得到$g_k(x)$。(作者设置$\tau=0.1$,其他值也可以尝试。)
  4. 进行模型的更新:$$h_k(x) = \frac{kh_{k-1}(x)+\eta g_k(x)}{k+1}$$ 其中,$\eta$为伸缩因子。

可以看到step3里面每轮都拟合误判的结果,在迭代中这个集合会越来越小。还有一种做法是将曾经误判的集合维持在训练集中,那么训练集就会始终增长。在这个步骤中使用GBDT模型进行回归预测,当然其他的回归方法也可以使用。

logistRank:logistRank和gbrank的区别,和关于scale因子的思考

logistRank复用了gbdt框架,文中介绍篇幅比较短,反复看了看和gbrank的主要区别在point-wise与pair-wise两种不同的方式。通常,Logistic loss函数我们用在描述二分类问题(这部分感兴趣可以看引文[11,12])。$$L\left( {y,F} \right) = \log \left( {1 + \exp \left( { - yF} \right)} \right),y \in \left\{ {1, - 1} \right\}$$
作者认为,它能将positive/negative往positive/negative两个方向拉开,如果一个url的相关性是perfect,对应的打分会距离决策平面远一些。接下来结合gbdt框架介绍其具体做法(符号统一为freidman文章用法,gbdt将会在下一篇中说详细些)。
在训练阶段第$m$轮的学习目标pseudo-response,即梯度为:$$ - {h_m}\left( {{x_i}} \right) = - {\left[ {{{\partial L\left( {{y_i},F\left( {{x_i}} \right)} \right)} \over {\partial F\left( {{x_i}} \right)}}} \right]_{F\left( x \right) = {F_{m - 1}}\left( x \right)}} = {{y_i} \over {1 + \exp \left( {{y_i}{F_{m - 1}}\left( {{x_i}} \right)} \right)}}$$
为了刻画{perfec, excellent,good}三种不同的相关性label,引入梯度scale因子,对于不同的label给予不同的梯度scale因子{例如:perfect:3, excellent:2, good:1}。经过调整以后,第$m$轮的学习目标pseudo-response为:
$$pseudo - response \left( x \right) = - {g_m}\left( {{x_i}} \right) \times scale\left( {label} \right)$$
其中:scale(perfect)=3,scale(excellent)=2,scale(good | fair | bad )= 1.这种方法等价于给不同的label样本的loss进行加权,在每一轮树的生长过程中,产生影响。
树的节点通过$\gamma$系数进行组合:
$${\gamma _{jm}} = \arg \mathop {\min }\limits_\gamma \sum\limits_{{x_i} \in {R_{jm}}} {\log \left( {1 + \exp \left( { - {y_i}\left( {{F_{m - 1}}\left( {{x_i}} \right) + \gamma } \right)} \right)} \right)} $$
这个公式无解析解。通过下述牛顿-拉夫森公式进行逼近:
$${\gamma _{jm}} = \sum\limits_{{x_i} \in {R_{jm}}} {{{{{\tilde y}_i}} \over {\sum\limits_{{x_i} \in {R_{jm}}} {\left| {{{\tilde y}_i}\left( {2 - \left| {{{\tilde y}_i}} \right|} \right)} \right|} }}} , j=1,...,J$$
logistRank算法
初始化${F_0}\left( x \right) = \bar y$
对于$m = 1...N$次迭代中:

  1. $pseudo-response: {{\tilde y}_i} = {{{y_i}} \over {1 + \exp \left( {{y_i}{F_{m - 1}}\left( {{x_i}} \right)} \right)}}\times scale\left( {label} \right)$
  2. $\left\{ {{R_{jm}}} \right\}_1^J = J 个叶结点的回归树tree\left\{ {{{\tilde y}_i},{x_i}} \right\}_1^N$
  3. ${\gamma _{jm}} = \sum\limits_{{x_i} \in {R_{jm}}} {{{{{\tilde y}_i}} \over {\sum\limits_{{x_i} \in {R_{jm}}} {\left| {{{\tilde y}_i}\left( {2 - \left| {{{\tilde y}_i}} \right|} \right)} \right|} }}} , j=1,...,J$
  4. ${F_m}\left( x \right) = {F_{m - 1}}\left( x \right) + \sum\limits_{j = 1}^J {{\gamma _{jm}}1\left( {x \in {R_{jm}}} \right)} $

得到$F_m(x)$作为模型打分。
关于scale对不同label的加权,我们可以看到,对于perfect或者excellent这类样本,回归的值会更大,不同等级的正例之间相关性的区别度相对明显。下图为作者实验结果展示:
实验结果
雅虎线上结果显示,LogistRank减少了40%的bad document,在DCG5指标上提高了5%。

有点困惑,point-wise目前不是很流行的rank方法。有两个缺点:1.高频query对应候选的文档很多,相关度高的文档在训练集里面的label可能被低估,而对于低频长尾query,可满足的documet相关度较高,因此人工标准里面的label可能被高估。这样带来训练数据的不一致性。此外,同一档的文档(例如perfect里面的两篇文章)不能相互区分。
当然pair-wise也有它的问题。1. 只有pair之间的顺序,并不考虑在全局的顺序,实际上排第1位置和排在第5位置的发生错误应该进行不同程度的惩罚,需要引入位置因素。2. 对于不同的查询相关文档集的数量差异很大,转换为文档对后,会带来训练集有偏。有的查询可能只有十几个文档对,而有的查询可能会有数百个对应的文档对,这对学习系统的效果评价带来了偏置。假设查询1对应500个文档对,查询2对应10个文档对,假设机器学习系统对应查询1能够判断正确480个文档对,对应查询2能够判断正确2个。对于总的文档对该系统准确率是(480+2)/(500+10)=95%,但从查询的角度,两个查询对应的准确率分别为:96%和20%,平均为58%,与总的文档对判断准确率相差巨大,这将使得模型偏向于相关文档集大的查询[10]。
请教l2r的同事,实验里面没有对gbrank做同样的正例加权(scale),这样的比较可能不太公允,因为很难确定提升部分是来自scale还是说loss function的改变。

附录:牛顿-拉夫森迭代(百科地址
牛顿-拉夫森百科

[1]J. Friedman. Greedy function approximation: a gradient boosting machine. Ann. Statist., 2001
[2]Y. Freund, R. Iyer, R. Schapire and Y. Singer. An ecient boosting algorithm for combining preferences. Journal of Machine 2Learning Research, 2003.
[3]T. Joachims. Optimizing search engines using clickthrough data. Proceedings of the ACM Conference on Knowledge Discovery and Data Mining, 2002.
[4]T. Joachims. Evaluating retrieval performance using clickthrough data. Proceedings of the SIGIR Workshop on Mathematical/Formal Methods in Information Retrieval, 2002.
[5] T. Joachims, L. Granka, B. Pang, H. Hembrooke, and G. Gay. Accurately Interpreting Clickthrough Data as Implicit Feedback. Proceedings of the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2005.
[6]C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to rank using gradient descent. Proceedings of international conference on Machine learning, 89{96, 2005.
[7]Zheng Z, Zha H, Chen K, et al. Regression Framework for Learning Ranking Functions using Relative Preferences[J]. 2008.对应专利:百度云盘链接
[8] GBRank:一种基于回归的学习排序算法, 2016
[9] C. J. C. Burges. From RankNet to LambdaRank to LambdaMART: An overview. Technical report, Microsoft Research, 2010.
[10] 学习排序 Learning to Rank 小结
[11] gradient boosting decision tree[上篇]
[12] gradient boosting decision tree[下篇]

ShawnXiao@baidu