排序学习(Learning To Rank)

排序学习思维导图和系统框架

排序学习系统通用学习框架(摘自参考文献)

排序学习和其他机器学习任务一样，分为训练环节和预测环节，唯一的不同点就是输入数据格式和普通数据不同。排序学习思维导图如下。

问题定义

问题类型

Pointwise算法
是指给定$$对，如果最终预测目标是一个实数值，就是一个回归问题。如果目标是概率预测，这就是一个分类问题，例如CTR预估.
Pairwise
是指给定$$，即给定两个文档的排序。Pairwise算法的目标是减少逆序的数量，所以是个二分类问题
Listwise
是指给定一个排序列表$$,目标往往是直接优化nDCG、ERR等评价指标.

学习方法

评价指标

MAP(Mean Aaverage Precision)平均准确率均值，体现的是取不同个数排序结果下的平均准确率，所谓准确率是指前面$k$个中，相关文档的占比.MAP计算公式如下：
$AP@K=\frac{\sum_{i=1}^{K}P(i)rel(i)}{K} \\ P(i) = \frac{前i个文档中相关文档个数}{i} \\ rel(i) = 1(第i个文档是相关文档) or 0 (第i个文档不相关)$
以上公式计算了一个query时，针对$TopK$的准确率，$K$表示在结果中选取多少个文档。
针对于整个数据集的$MAP$,即平均准确率
$AMP@Q=\frac{\sum_{q=1}^Q AP_q@K}{Q}$
MAP指标只考虑文档相关与否0和1，不考虑具体相关程度。
CG(Cumulative Gain)累积增益
可用于评价基于打分或者评分的排序系统，计算公式如下 $CG = \sum_{i=1}^K rel(i)$ 其中，$K$表示排序内容的个数，$rel(i)$表示第$i$个物品的相关性或者评分。举例来说，给一个用户推荐了五个商品，$I_1, I_2, I_3, I_4, I_5$, 对应的得分分别为$5, 3, 2, 1, 0.5$,累积增益为： $CG=5+3+2+1+0.5 = 11.5$ 累积增益并没有考虑每个物品具体的位置，只考虑了得分大小
DCG(Discount Cumulative Gain) 折扣累积增益
计算公式如下
$DCG_K=\sum_{i=1}^K\frac{2^{rel(i)}-1}{log_2{(i+1)}}$
其中，$K$表示列表中元素个数，分子表示相关性的大小，分母表示当前物品位置的惩罚。举例来说，给一个用户推荐了五个商品，$I_1, I_2, I_3, I_4, I_5$, 对应的得分分别为$5, 3, 2, 1, 2$,则折扣累积增益为(列表位置索引从1开始)，
$DCG_5=\frac{2^5-1}{log_22} + \frac{2^3-1}{log_23} +\frac{2^2-1}{log_24} + \frac{2^1-1}{log_25} + \frac{2^2-1}{log_26} = 38.5$
NDCG(Normalized Discount Cumulative Gain)归一化折扣累积增益
因为DCG并没有考虑列表中和查询query真正有效的个数，其计算公式如下，给一个用户推荐了五个商品，$I_1, I_2, I_3, I_4, I_5$, 对应的得分分别为$5, 3, 2, 1, 2$(但是这里有疑惑点，推荐列表为什么不是按照实际的得分排序呢?)
$NDCG_k = \frac{DCG_K}{IDCG_k}$
$IDCG$是指列表按照真实分数排序状况下的$DCG$，依然用上面的例子，则五个商品的按分数排序是$5, 3, 2, 2, 1$,则对应的$IDCG$为
$IDCG_5=\frac{2^5-1}{log_22} + \frac{2^3-1}{log_23} +\frac{2^2-1}{log_24} + \frac{2^2-1}{log_25} + \frac{2^1-1}{log_26} = 38.5$
对应的$NDCG$如下
$NDCG_5=\frac{DCG_5}{IDCG_5}$
$NDCG$是0-1的数，越接近于1说明推荐越准确.

总结

对于排序问题，主要弄情况$pointwise, pairwise, listwize$和相应的评价指标既可，对于算法的选择可根据业务论文进行对比。