McRank是学习排序(Learning to Rank)的单文档排序分支(Pointwise)中较为经典的一种，本文是读原Paper[1]之后自己的一个理解.

基本介绍

McRank的全称是Multiple Classification Rank,可以理解为将学习排序转为机器学习中的一个多分类问题.
McRank对DCG指标进行优化，并且可以证明DCG的误差可以被分类误差给bounded住.

折损累积增益

DCG(Discounted Cumulative Gain)是在信息检索领域评估一个rank好坏的常用指标。(在实际使用中一般会进行归一化，称为NDCG，可以看这里).

假设在指定的query下通过某个排序算法对$n$个文档进行排序，则可以得到
$$DCG=\sum_{i=1}^{n}c_{[\pi_i]}(2^{y_i}-1)$$

其中:

1. $i$表示原文档的索引顺序
2. $c_{[\pi_i]}=log(i+1)$
3. $y_i$表示对应文档与query相关性的程度，一般用档位$\{0,1,2,3,4\}$来表示

最终的DCG值越大，表示排序效果越好,假如直接根据档位降序得到的排序结果中DCG是最大的，实际使用中一般根据当前可能的最大DCG进行归一化

排序思想

现在已经知道了文档与query之间一般用档位衡量，而假如按档位降序的DCG值最高,所以排序问题可以转为指定query对文档相关性类别的预测，即多分类问题。

DNCG误差计算

现在可以这么理解，我们希望的是DCG越大越好，也即是DCG误差越小越好，但如果是分类问题将直接优化的是分类误差，那如果DCG误差能够被分类误差给bouded住，就可以通过优化分类误差来间接的优化DCG误差了.

对于一个排序的置换映射函数$\pi$,DCG误差为$DCG_g-DCG_{\pi}$，其中$DCG_g$表示最优排序,就是根据实际的query-doc相关性分档降序的排序，所以肯定有$DCG_g \geq DCG_{\pi}$

现给定$n$个URLS的顺序为$\{1,2,3…n\}$，假设分类器分配的相关结果为$\hat{y}_i \in \{0,1,2,3,4\}$，置换映射函数$\pi$直接根据相关性进行排序，高档位的排在前面，相同档位可以随意排序，则可以有以下证明:

先看变量^_^
$y_i$表示query-doc的实际相关性
$\hat{y}_i$表示query-doc的分类器预测相关性
$c_{[g_i]}$表示根据实际相关性得到的排序
$c_{[\pi_i]}$表示根据预测相关性得到的排序

$$\begin{equation}\begin{split}DCG_{\pi}&=\sum_{i=1}^{n}c_{[\pi_i]}(2^{y_i}-1) \\
&=\sum_{i=1}^{n}c_{[\pi_i]}(2^{\hat{y}_i}-1)+\sum_{i=1}^{n}c_{[\pi_i]}(2^{y_i}-2^{\hat{y}_i}) \\
&\geq \sum_{i=1}^{n}c_{[g_i]}(2^{\hat{y}_i}-1)+\sum_{i=1}^{n}c_{[\pi_i]}(2^{y_i}-2^{\hat{y}_i}) \\
&=\sum_{i=1}^{n}c_{[g_i]}(2^{y_i}-1)-\sum_{i=1}^{n}c_{[g_i]}(2^{y_i}-2^{\hat{y}_i})+\sum_{i=1}^{n}c_{[\pi_i]}(2^{y_i}-2^{\hat{y}_i}) \\
&=DCG_g+\sum_{i=1}^{n}(c_{[\pi_i]}-c_{[g_i]})(2^{y_i}-2^{\hat{y}_i})
\end{split}\end{equation}$$

解释下不等式$\sum_{i=1}^{n}c_{[\pi_i]}(2^{\hat{y}_i}-1) \geq \sum_{i=1}^{n}c_{[g_i]}(2^{\hat{y}_i}-1)$成立的原因:$c_{[\pi_i]}$是根据相关性$\hat{y}_i$排序得到的，也就是上面提到的最优排序，得到的$DCG$值是最大的(当然这个是分类器的预测值，不是真实值，就是假象的意思-_-)，所以换一种顺序$c_{[g_i]}$其$DCG$的值必定会小于等于最大值.

根据上面的推导就可以直接得到$DCG$的误差了:
$$\begin{equation}\begin{split}DCG_g-DCG_{\pi} &\leq \sum_{i=1}^{n}(c_{[g_i]}-c_{[\pi_i]})(2^{y_i}-2^{\hat{y}_i}) \\
& \leq \left(\sum_{i=1}^{n}(c_{[g_i]}-c_{[\pi_i]})^2\right)^{\frac{1}{2}}\left(\sum_{i=1}^{n}(2^{y_i}-2^{\hat{y}_i})^2\right)^{\frac{1}{2}} \\
&\leq \left(2\sum_{i+1}^{n}c_{[i]}^2-2n\prod_{i=1}^nc_{[i]}^{\frac{2}{n}}\right)^{\frac{1}{2}} 15 \left(\sum_{i=1}^{n}1_{y_i \neq \hat{y}_i}\right)^{\frac{1}{2}} \\
&= 15\sqrt{2} \left(\sum_{i+1}^{n}c_{[i]}^2-n\prod_{i=1}^nc_{[i]}^{\frac{2}{n}}\right)^{\frac{1}{2}}\left(\sum_{i=1}^{n}1_{y_i \neq \hat{y}_i}\right)^{\frac{1}{2}}
\end{split}\end{equation}$$

上面公式1~2是不等式是根据柯西不等式得到的，第2~3行平方展开的不等式成立是因为:

1. $\sum_{i=1}^{n}c_{[\pi_i]}^2=\sum_{i=1}^{n}c_{[g_i]}^2=\sum_{i=1}^{n}c_{[i]}^2$,$\prod_{i=1}^{n}c_{[\pi_i]}^2=\prod_{i=1}^{n}c_{[g_i]}^2=\prod_{i=1}^{n}c_{[i]}^2$，他们虽然是顺序不一样，但是他们集合的内容是一样的，所以求和和连乘的等式是成立的。
2. 两种相关性$y_i$和$\hat{y}_i$的值在0~4范围内,因此有$(2^{y_i}-2^{\hat{y}_i})^2\leq 15$，因为$2^4-2^0=15$

因此当需要最小化DCG误差时只需要最小化分类误差$\sum_{i=1}^{n}1_{y_i \neq \hat{y}_i}$即可，但是该误差非凸也非平滑，实际使用中使用代理损失函数进行优化:
$$\sum_{i=1}^{N}\sum_{k=0}^{K-1}-log(p_{i,k})1_{y_i=k}$$
其中$p_{i,k}$表示doc输入每个档位的概率，$K$是总的档位数。

我感觉:上面不等式里面的排序顺序时间使用$c_{[i]}$代替了，虽然表面上和分档结果无关，因此只需要优化分档即可，但是。。。实际上$c_{[\pi_i]}$的顺序是和分档预测有关的啊….

分类排序

上面提到过有了分档结果之后可以按档位顺序降序排序，得到的DCG就是最优的，但是这里存在一个问题，那就是相同档位之间是可以随便排的，就是导致排序的不稳定性，为了得到一种良好的排序机制，McRank在实际排序中会将分类结果转为一个连续的分数，按这个分数进行排序.

假设训练是$\{y_i,x_i\}_i^N$，$y_i$表示多分类的分档,则最终将会学习到的是每个类别的概率$p_{i,k}=Pr(y_i=k)$，则最后的排序分数为:
$$S_i=\sum_{k=0}^{K-1}p_i^kT(k)$$
其中$T(k)$表示随档位单调递增的函数，比如$T(k)=k$或者$T(k)=2^k$（McRank用的是前者）

不同的单调递增函数不会对排序进行影响，同时如果对函数进行线性变换也会改变排序结果

最终McRank是使用Boosting Tree进行多分类预测..

有序分类

好吧，其实上面McRank已经讲完了，但是Paper里面提到有序分类(Ordinal Classfifcation，貌似就是Pointwise里面的第三个分支)可以提升排序结果。

这里在进行多分类时，可以发现每个类别(档位)并不是平等的，比如4档就是要比0档相关性更好，为了考虑这种的偏移，有序分类就是干这个的，多类别有序分类是学习一段区间内的累积概率$Pr(y_i<k)$

首先将训练数据点分类两种$\{y_i \geq 4 \}$和$\{y_i \leq 3\}$，那这样称为了一个二分类问题，这里一样使用boosting Tree进行分类，同样关于$\{y_i \leq 3\}$也可以分为$\{y_i \geq 3 \}$和$\{y_i \leq 2\}$，如果迭代就可以进行变相多分类.

这种方式就是考虑目标类目的不均等性，带来的问题就是会增加训练开销(因为有重复计算，并且可能会带来较大的样本不均衡性。。。。)

还有一个坏消息。。。McRank的Paper实验里面这种方式并没有比普通多分类提升多少效果-_-

总结

McRank是非常经典的一种Pointwise学习排序，将排序转为机器学习的多分类预测，并且对其排序指标DCG误差可以被分类误差给bounded住，最终将分类结果的概率转为一个连续分数进行最终的排序，在实验里面显示该方法比基于回归的subRank以及pairwise的LambdaRank效果更好。

McRank速度快，效果也还行，最大的问题就是训练样本的构建比较麻烦..

参考

1. Li P, Burges C J C, Wu Q. McRank: Learning to Rank Using Multiple Classification and Gradient Boosting[J]. Advances in Neural Information Processing Systems, 2007:897-904.

---

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