learning based method（Learning to Rank小结）

Searchers Log home wiki about

Learning to Rank小结

/* -*- author: Tan Menglong; email: tanmenglong_at_gmail; twitter/weibo: @crackcell; 转载请注明出处 -*- */

Table of Contents

1 前言

2 LTR流程

3 训练数据的获取

3.1 人工标注

3.2 搜索日志

3.3 公共数据集

4 特征抽取

5 模型训练

5.1 训练方法

5.1.1 Pointwise

5.1.2 Pairwise

5.1.3 Listwise

6 效果评估

6.1 NDCG（Normalized Discounted Cumulative Gain）

6.1.1 定义

6.1.2 描述

6.2 MAP（Mean Average Precision）

6.2.1 定义

6.2.2 描述

7 参考

1 前言

在传统搜索引擎的ranking策略中 
    
    
    
  ，一般会包含若干子策略
     


     


     


     
，子策略通过若干种方式组合成更大的策略一起发挥作用    
    
    
    
。策略的组合方式以及参数一般采取人工或者半人工的方式确定  


     


     


     


  。随着策略的逐步细化 




 




 




 




，传统的方式变得越来越困难


 




 




 




 
。于是Learning to Rank（LTR）就被引入了进来   

   

   

   

。LTR的核心是想是用机器学习来解决排序的问题   

     

     

     

 。目前被广泛运用在 信息检索（IR）     
    
    
    
、 自然语言处理（NLP） 和 数据挖掘（DM） 中



  




  




  




  。 LTR是监督的学习  


  


  


  


。建好模型之后 

   

   

   

 ，需要用训练数据集的人工标注结果来训练    
     
     
     
。

2 LTR流程

./NOTE_a_short_intro_2_ltr-training_process.png [[./NOTE_a_short_intro_2_ltr-training_process.png][./NOTE_a_short_intro_2_ltr-training_process.png]]

3 训练数据的获取

有2种获取训练数据的来源:1）人工标注；2）搜索日志




   




   




   




   。

3.1 人工标注

从搜索日志中随机选取一部分Query
     

     

     

     ，让受过专业训练的数据评估员对"Query-Url对"给出相关性判断 



 



 



 


。常见的是5档的评分:差  


     


     


     


  、一般


 




 




 




 
、好   

   

   

   

、优秀   

     

     

     

 、完美                    。以此作为训练数据




    




    




    




   。 人工标注是标注者的主观判断  




  




  




  




，会受标注者背景知识等因素的影响


















。

3.2 搜索日志

使用点击日志的偏多                    。比如 


  


  


  


，结果ABC分别位于123位
     
     
     
     ，B比A位置低   




   




   




   



，但却得到了更多的点击 



 



 



 



，那么B的相关性可能好于A 



     



     



     



   。点击数据隐式反映了同Query下搜索结果之间相关性的相对好坏


















。在搜索结果中                   ，高位置的结果被点击的概率会大于低位置的结果
    




    




    




    


，这叫做"点击偏见"（Click Bias）    
    
    
    
。但采取以上的方式



















，就绕过了这个问题  


     


     


     


  。因为我们只记录发生了"点击倒置"的高低位结果                   ，使用这样的"偏好对"作为训练数据


 




 




 




 
。关于点击数据的使用
     



     



     



     

，后续再单独开帖记录



















，这里不展开   

   

   

   

。 在实际应用中 
    
    
    
  ，除了点击数据
     


     


     


     
，往往还会使用更多的数据   

     

     

     

 。比如通过session日志 




 




 




 




，挖掘诸如页面停留时间等维度



  




  




  




  。 在实际场景中 

   

   

   

 ，搜索日志往往含有很多噪音  


  


  


  


。且只有Top Query（被搜索次数较多的Query）才能产生足够数量能说明问题的搜索日志    
     
     
     
。

3.3 公共数据集

现存一批公开的数据集可以使用

LETOR, http://research.microsoft.com/en-us/um/beijing/projects/letor/

Microsoft Learning to Rank Dataset, http://research.microsoft.com/en-us/projects/mslr/

Yahoo Learning to Rank Challenge, http://webscope.sandbox.yahoo.com/

4 特征抽取

搜索引擎会使用一系列特征来决定结果的排序




   




   




   




   。一个特征称之为一个“feature 
    
    
    
  ” 



 



 



 


。按照我的理解
     

     

     

     ，feature可以分为3大类：

Doc本身的特征：Pagerank



  




  




  




  、内容丰富度  


  


  


  


、是否是spam等

Query-Doc的特征：文本相关性    
     
     
     
、Query term在文档中出现的次数等

此阶段就是要抽取出所有的特征  




  




  




  




，供后续训练使用                    。

5 模型训练

5.1 训练方法

LTR的学习方法分为Pointwise




   




   




   




   、Pairwise和Listwise三类




    




    




    




   。Pointwise和Pairwise把排序问题转换成 回归  



 



 



 


、 分类 或 有序分类 问题


















。Lisewise把Query下整个搜索结果作为一个训练的实例                    。3种方法的区别主要体现在损失函数（Loss Function）上 



     



     



     



   。

5.1.1 Pointwise

排序问题被转化成单结果的 回归                     、 分类 或 有序分类 的问题


















。

函数框架

L(F(x),y)=∑i=1nl(f(xi)−yi)

小结

./NOTE_a_short_intro_2_ltr-pointwise_flow.png

5.1.2 Pairwise

排序问题被转化成结果对的 回归 




    




    




    




   、 分类 或 有序分类 的问题    
    
    
    
。

函数框架

L(F(x),y)=∑i=1n−1∑j=i+1nl(sign(yi−yj),f(xi)−f(xj))

小结

./NOTE_a_short_intro_2_ltr-pairwise_flow.png

5.1.3 Listwise

函数框架

L(F(x),y)=exp(−NDCG)

小结

./NOTE_a_short_intro_2_ltr-listwise_flow.png

6 效果评估

对于搜索结果 


  


  


  


，有多种量化搜索得分的计算方法
     
     
     
     ，这里介绍NDCG和MAP  


     


     


     


  。

6.1 NDCG（Normalized Discounted Cumulative Gain）

6.1.1 定义

NDCG(k)=G−1max,i(k)∑j:πi≦k2yi,j−1log2(1+πi(j))

计算前k条结果的相关性得分

i：第i次搜索

j：第j条结果

yi,j：第j条结果的相关性标注得分   




   




   




   



，5档制

πi(j)：这条结果在排序中的位置

6.1.2 描述

顾名思义 



 



 



 



，NDCG的公式由 N


















、D                    、C 



     



     



     



   、G 4部分组成


 




 




 




 
。将公式改写成

NDCG(k)=Gmax,i(k)∑j:πi≦kGi(j)Di(πi(j))

先看G部分   

   

   

   

。G是增益函数（Gain）,表示第j条结果在被给予评分yi,j之后所贡献的分值增益   

     

     

     

 。定义如下

Gi(j)=2yi,j−1

再看D部分



  




  




  




  。D是位置折算函数（Discounted）  


  


  


  


。因为不同位置的增益应该是不同的                   ，D函数给结果按照位置赋予一个权重    
     
     
     
。定于如下

D(πi(j))=1log2(1+πi(j))

C部分就是累加（Cumulative）
    




    




    




    


，将k条结果的得分加在一起




   




   




   




   。

N是归一化因子（Normalized）



















，取值是该位置上G函数理论上取得的最大值的倒数 



 



 



 


。目的是缩放不同位置上的得分到统一区间                    。

6.2 MAP（Mean Average Precision）

6.2.1 定义

AP=∑nij=1P(j)yi,j∑nij=1yi,j

P(j)=∑k:πi(k)≦πi(j)yi,kπi(j)

MAP中                   ，相关性评分yi,j只有2档：0和1

6.2.2 描述

P表示结果j的权重
     



     



     



     

，从位置j开始



















，相关（标记为1）的结果所在的比例

AP表示单query下 
    
    
    
  ，相关的结果的平均的加权得分

AP中
     


     


     


     
，只有标记为相关的结果才会参与加权的累加

AP是单query下的得分 




 




 




 




，多query的平均AP 

   

   

   

 ，就成了MAP

7 参考

Hang Li. Learning to Rank for Information Retrieval and Natural Language Processing

Hang Li. A Short Introduction to Learning to Rank

Author: Tan Menglong <tanmenglong AT gmail DOT com>

Date: 2011-12-17 17:11:51 CST

HTML generated by org-mode 6.33x in emacs 23