上一篇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$是一个常量，在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