GB-Rank -- 一种排序算法

排序问题是计算机领域的常用问题。一方面,我们研究各种排序算法。另一方面,我们希望知道以怎么样的标准来对一组对象,例如网页搜索的结果等,进行排序。在这一过程中,我们要考虑的因素可能有网页与关键词的关系,网页本身的质量,网页更新的时间等许多复杂的因素。

一个很自然的想法是为每一个结果进行打分,即找到一个函数 $f$ 满足$Score = f(Page)$。然后根据评分进行排序就可以。

那么,怎么来寻找这样的一个函数呢?

以机器学习的视角来看,我们需要有一些标记好的数据 $(X, y)$, 其中 $X$ 是每一个网页要考虑的特征向量,而 $y$ 是人工标记的分数。

现在我们得到了这样一个问题:

找到一个函数 $f$ ,满足 对任意一对网页 $i, j$, $ y_i \le y_j$,都有 $f(X_i) \le f(X_j) $

于是,对于每一组$x_i, x_j$ 满足 $y_i > y_j$,可以定义损失函数 $l$ 为

其中引入了$\tau$ 满足 $0 < \tau < 1$,以避免函数收敛到一个常数。也可以认为我们希望 $f(x_i) > f(x_j) + \tau$ 以获得更好的效果。

而在全部样本上的损失函数为

然而,直接对这个函数进行优化是困难的, GBRank 采用了这样的策略:

1. 随机初始化一个函数 $f(x)$ 2. 进行若干次循环。假设在第 $n-1$次获得了函数 $f_{n-1}$, 那么使用它可以将每一组$x_i, x_j(y_i > y_j)$ 划分到下面两个集合之中:

对于集合A中的元素,以及达到了我们的要求,不需要进行处理。而对于集合B中的元素,需要我们来进行模型的改进。

3. 将B集合转化为这样一个集合C: $\lbrace (x_i, f_{n-1}(x_j) + \tau) | (x_i,x_j)\in B)\rbrace \bigcup \lbrace (x_j, f_{n-1}(x_i) - \tau)|(x_i,x_j) \in B \rbrace$

4. 用 GBT 对集合C进行拟合。得到函数 $g(x)$ 5. 获得新的函数,$f_n(x) = \frac{nf_{n-1}(x) + \beta g(x)}{n+1}$

可以发现,其训练的思想是仍旧是 Boosting。每次选择效果不好的数据重新进行训练,最终达到一个满意的效果。

*****
Written by Functor on 26 November 2016
Tags: [ GBDT  ranking  search  decision-tree  boosting  algorithm  ]