搜索排序跟自己的工作比较相关，最近打算仔细拜读一下刘铁岩老师的经典作品《Learning to Rank for Information Retrieval》，配合自己的理解整理一下。
第一部分：L2R回顾
1.1 回顾
作者首先以文献检索为例，给出了一个搜索排序系统的结构图。
可以看出，由底向上。首先由爬虫去收集数据，解析器解析以后，建立索引与网页拓扑图；索引分为正排索引与倒排索引。简单来说，正排索引是从文档的角度出发的，记录每个文档里面有那些词汇，分别出现了多少次，在什么位置；倒排索引则是从关键词出发的，记录每个关键词分别出现在多少个文档中，在每个文档中处于什么位置。通过倒排索引，就可以根据用户输入的关键词很快找到对应的文档。另一端通过网页拓扑图可以分析各个网页的超链接，从而进行页面分层处理，以及爬虫优先级的确定。
在这些确定好之后，用户给一个查询请求过来，此时就需要对查询的结果进行排序。可以看出图中的ranker是一个很重要的中间件。从索引中提取与关键词相关的文献给到用户，并且要以合理的顺序去展示。合理的定义有很多，满足用户的意图最重要。对于文献检索来说，可能就是与关键词最相关的文献；如何定义相关呢，标题中出现查询词应该就比正文中出现更为相关；在电商的场景，除了相关性，销量质量等也是很重要的因素。需要结合具体场景，找数据找特征去逐步完善优化排序的效果。
收集训练集数据，利用机器学习的方法去做排序，探索更好的排序效果，这个就叫做‘learing to rank’，简称L2R。这是一个比较热门的研究方向，学术界与工业界都在探索，有很多相关的算法被提出。
作者在书中提出了几个问题：
•这些L2R算法有什么相似与不同？每种算法的优缺点是什么？
•从经验上讲，哪一种L2R算法才是最好的？
•从理论上讲，L2R算法是一个新的机器学习问题，还是可以归结到已有的机器学习问题中？L2R算法有什么独特之处值得深入研究探讨呢？
•L2R算法是否还有许多问题值得未来去研究？
1.2 信息检索中的排序
1.2.1 传统排序模型
相关性排序模型，是按照文档与查询词的相关度进行排序。一般简单的做法就是计算每一篇文档与查询词的相关度，然后降序排序。
早期的Boolean model只能检测文档与查询词是否相关，但无法计算相关程度。后面提出了一种Vector Space model(VSM)模型。文档与查询词都被向量化，然后用内积去衡量它们的相关性。向量一般是用TFIDF算法生成的。可以看出这种方法确实比较粗糙，没有考虑词之间的相关性。Late nt Semantic Indexing(LSI)潜语义索引是用矩阵分解(SVD)的方法去做,会考虑到词的相关性，本质上是一种线性变换。
最近一些年基于概率的模型，表现更好一点。文中列举了BM25与language model for information retrieval(LMIR)两个模型。简单看了一下，BM25是先把query分词，然后计算每个分词与文档的相关性，最后加权。在计算相关性时，在TFIDF的基础上做了一些新的考量与处理，提供了一些参数用于调节算法的效果。LMIR则是利用极大似然的方法求一个文档中出现query中分词的概率。还有类似的其他方法不再赘述。
还有一些算法是根据自定义的重要性来进行排序的，一个典型的算法就是PageRank算法，该算法是一种随机游走算法，利用网页之间的超链接关系去计算各个网页的重要性。
假设共有N个页面，N1、N2、N3...每个页面的初始PR值设为1/N，然后依次迭代计算N1、N2、N3...的值，直至平稳。这样就得出了每个页面最终的PR值。
这种算法的设计思想就是，被重要页面链接的页面，一般也会是重要的页面。
1.2.2 Query下的排序效果评估
这一节主要讲了评估排序效果的一些方法与指标。
要评估排序，首先最好要有一个标准的答案。这往往是个关键却又麻烦的事，排序这种东西不像分类回归那样label比较明显，而是要结合业务去选择合适的指标。
文中给出了在某个query下三种确定排序标准的方式，第一种是给每一个产品打一个分，分数有高低差距；第二种是确定产品两两之间的顺序，比如A比B好，B比C好；第三种是直接给出整体的最合理的排序。这三种对label或者说优化目标的不同定义方式，也对应了pointwise、pairwise、listwise的学习目标，而且从某种角度上来说是可以互相进行形式转化的（书中1.3节给到了转换的方法，但可能损失一些排序信息）。第一种方法就比较像我们平时做的回归问题，相对来说也最容易去制定label。
接下来介绍了评估排序效果的一些指标。这里介绍最常见的两种，MAP与NDCG。
关于这两个指标，推荐一篇博文https://blog.csdn.net/simple_the_best/article/details/52296608。AP其实是平均准确率，指的是每个相关结果的前面序列（包括自己）的排序准确率的均值。MAP是所有query的AP的均值。MAP只能将排序结果分成相关与不相关两类，不能分多个相关性层级，而且没有考虑位置的影响。
位置影响是比较好理解的，排序展示给用户后，头部的流量肯定要比后面高得多。自己也利用线上数据做过一些统计，不同位次，用户的点击UV的确是逐步下降的。而且分屏会有一个小断崖式的下跌，这个也很好理解。比如你一屏有5个商品，那么1-5名商品的流量会依次下降，但差距不会过大。第5名跟第6名由于曝光量的不同（由用户是否拖屏决定），点击UV就会有一个断崖式下跌。
NDCG就考虑到了这些因素，指标有一个CG-DCG-IDCG-NDCG的发展过程，应该是目前最常用的排序指标。
1.3 Learning to Rank
前面提到的传统算法模型，大部分都有参数需要调整。一般我们是看验证集上的效果去调整这些参数，由于评价指标对于参数往往是不可微的，所以参数调整起来也不是一件容易的事，而且还很容易过拟合。单个算法的效果也不太好，可能需要把多个算法结合起来，但这不是一件容易的事。
话锋一转，作者就指出，机器学习算法好像可以解决上面的几个问题。可以自动调参，可以做融合，而且也不容易过拟合。当然，我觉得只是相对来说的，任何算法都有困境，在有足够的数据情况下，有监督机器学习是比传统算法有优势的。
作者提出了L2R的框架，主要由input space、output space、hypothesis space、loss function四个部分组成。按照优化目标的不同，可以分为pointwise、pairwise、listwise三种方式，对应前面提到的三种优化目标。
pointwise的局限性在于，它没有考虑两个产品之间的相对好坏，不关心排序的位置；它忽略了排序是有一个召回集合的事实，只关注在每个产品的好坏上。
pairwise的局限性在于，它只考虑两个产品之间的相对好坏，不关心排序的位置；它忽略了排序是有一个召回集合的事实，只关注两两产品对之间的好坏上。跟整体的用户对列表的感受还是有差距的。
Different approaches regard the same training data as in different input and output spaces, and use different loss functions and hypotheses. Accordingly, they will have difference theoretical properties. 事实上，这三种方法的四要素都是不同的，可以看作是三种理论了。作者用一个表做了很好的对比总结。
