Learning to rank基本算法小结

最近工作中需要调研一下搜索排序相关的方法,这里写一篇水文,总结一下几天下来的调研成果。包括

  1. Learning to rank 基本方法
  2. Learning to rank 指标介绍
  3. LambdaMART 模型原理
  4. FTRL 模型原理

learning to rank

排序学习是推荐、搜索、广告的核心方法。排序结果的好坏很大程度影响用户体验、广告收入等。
排序学习可以理解为机器学习中用户排序的方法,这里首先推荐一本微软亚洲研究院刘铁岩老师关于LTR的著作,Learning to Rank for Information Retrieval,书中对排序学习的各种方法做了很好的阐述和总结。我这里是一个超级精简版。

排序学习是一个有监督的机器学习过程,对每一个给定的查询-文档对,抽取特征,通过日志挖掘或者人工标注的方法获得真实数据标注。然后通过排序模型,使得输入能够和实际的数据相似。
常用的排序学习分为三种类型:PointWise,PairWise和ListWise。

PointWise

单文档方法的处理对象是单独的一篇文档,将文档转换为特征向量后,机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分,打分结果即是搜索结果

PointWise

PointWise方法很好理解,即使用传统的机器学习方法对给定查询下的文档的相关度进行学习,比如CTR就可以采用PointWise的方法学习,但是有时候排序的先后顺序是很重要的,而PointWise方法学习到全局的相关性,并不对先后顺序的优劣做惩罚。

PairWise

对于搜索系统来说,系统接收到用户査询后,返回相关文档列表,所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算,没有考虑文档之间的顺序关系。文档对方法将排序问题转化为多个pair的排序问题,比较不同文章的先后顺序。

PairWise

但是文档对方法也存在如下问题:

  1. 文档对方法考虑了两个文档对的相对先后顺序,却没有考虑文档出现在搜索列表中的位置,排在搜索结果前面的文档更为重要,如果靠前的文档出现判断错误,代价明显高于排在后面的文档。

  2. 同时不同的査询,其相关文档数量差异很大,所以转换为文档对之后, 有的查询对能有几百个对应的文档对,而有的查询只有十几个对应的文档对,这对机器学习系统的效果评价造成困难

常用PairWise实现:

  1. SVM Rank
  2. RankNet(2007)
  3. RankBoost(2003)

ListWise:

单文档方法将训练集里每一个文档当做一个训练实例,文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例,文档列表方法与上述两种方法都不同,ListWise方法直接考虑整体序列,针对Ranking评价指标进行优化。比如常用的MAP, NDCG。常用的ListWise方法有:

  1. LambdaRank
  2. AdaRank
  3. SoftRank
  4. LambdaMART

Learning to rank指标介绍

  • MAP(Mean Average Precision):
    假设有两个主题,主题1有4个相关网页,主题2有5个相关网页。某系统对于主题1检索出4个相关网页,其rank分别为1, 2, 4, 7;对于主题2检索出3个相关网页,其rank分别为1,3,5。对于主题1,平均准确率为(1/1+2/2+3/4+4/7)/4=0.83。对于主题2,平均准确率为(1/1+2/3+3/5+0+0)/5=0.45。则MAP= (0.83+0.45)/2=0.64。

  • NDCG(Normalized Discounted Cumulative Gain):

NDCG.png

NDCG把相关度分为r个等级,如果r=5,等级设定分别文25-1,24-1等等

相关度等级

那么加入现在有一个query为abc, 返回如下图所示的列表,假设用户选择和排序结果无关,则累积增益值如右列所示:

返回结果

考虑到靠前的位置点击概率越大,那么靠下的位置需要加上衰减因子
log(1+j),求和就可以得到DCG的值,最后为了使得不同不搜索结果可以比较,用DCG/MaxDCG就可以得到NDCG的值了。
MaxDCG就是当前情况下最佳排序的DCG值。如图所示

NDCG值
  • MRR(Mean Reciprocal Rank)
    给定查询q,q在相关文档的位置是r,那么MRR(q)就是1/R

LambdaMART算法:

LambdaMART是Learning to rank其中的一个算法,在Yahoo! Learning to Rank Challenge比赛中夺冠队伍用的就是这个模型。

LambdaMART模型从名字上可以拆分成Lambda和MART两部分,训练模型采用的是MART也就是GBDT,lambda是MART求解使用的梯度,其物理含义是一个待排序文档下一次迭代应该排序的方向。

但Lambda最初并不是诞生于LambdaMART,而是在LambdaRank模型中被提出,而LambdaRank模型又是在RankNet模型的基础上改进而来。所以了解LambdaRank需要从RankNet开始说起。

论文:
From RankNet to LambdaRank to LambdaMART: AnOverview

RankNet

RankNet是一个pairwise模型,上文介绍在pairwise模型中,将排序问题转化为多个pair的排序问题,比较文档di排在文档dj之前的概率。如下图所示


RankNet

最终的输出的sigmoid函数,RankNet采用神经网络模型优化损失函数,故称为RankNet。

梯度下降法

可是这样有什么问题呢?排序指标如NDCG、MAP和MRR都不是平滑的函数,RankNet的方法采用优化损失函数来间接优化排序指标。

LambdaRank

pairwise error

如图所示,蓝色表示相关的文档,灰色表示不相关的文档。RankNet以pairwise计算cost左边为13,右图将第一个文档下调3个位置,将第二个文档下调5个位置,cost就降为11。如此以来,虽然RankNet的损失函数得到优化,但是NDCG和ERR等指标却下降了。
RankNet优化的方向是黑色箭头,而我们想要的其实是红色的箭头。LambdaRank就是基于这个,其中lambda表示红色箭头。

LambdaRank不是通过显示定义损失函数再求梯度的方式对排序问题进行求解,而是分析排序问题需要的梯度的物理意义,直接定义梯度,Lambda梯度由两部分相乘得到:(1)RankNet中交叉熵概率损失函数的梯度;(2)交换Ui,Uj位置后IR评价指标Z的差值。具体如下:

梯度

lambdaMART

我们知道GBDT算法每一次迭代中, 需要学习上一次结果和真实结果的残差。在lambdaMART中,每次迭代用的并不是残差,lambda在这里充当替代残差的计算方法。

LambdaMART算法流程
GBDT算法流程

对比lambdaMART和GBDT算法流程,主要框架是相同的,只不过LambdaMART模型用lambda梯度代替了GBDT的残差。

FTRL算法(Follow the regularized Leader Proximal)

点击率预估问题(CTR)是搜索、广告和推荐中一个非常重要的模块。在CTR计算的过程中,常常采用LR模型。

FTRL属于在线算法,和SGD等常用的在线优化方法对比,可以产生较好的稀疏性,非常适合ID特征较多,维度较高的特征。

google的论文中已经给出了很详细的工程化实现的说明,该方法也已经广泛的应用。

  • 参数优化:
参数更新

第一项:保证参数不偏移历史参数
第二项:保证w不会变化太大
第三项:代表L1正则,获得稀疏解

  • 算法流程:
FTRL算法流程

Ad click prediction: a view from the trenches

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,591评论 6 501
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,448评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,823评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,204评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,228评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,190评论 1 299
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,078评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,923评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,334评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,550评论 2 333
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,727评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,428评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,022评论 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,672评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,826评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,734评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,619评论 2 354

推荐阅读更多精彩内容