小谈Learning to Rank模型

Learning to rank是一个很常见的在Information Retrieval当中的机器学习应用。Facebook用它来优化你的朋友圈文章,Airbnb用它来优化你的搜索结果排序,Quora用它来给各种答案进行排序。Bing常常标榜它有着最好的机器学习得到的搜索结果,但是Google从前常常标榜不怎么用Learning to rank

Learning to rank的局限性

用机器学习来解决search ranking一度在机器学习和Information retrieval领域得到了很多的重视,有很多来自于研究领域的进步。但是站在实用角度以及Information retrieval角度来看,Learning to rank常常会犯一些错误,忽略一些在Information retrieval中常见的问题。

首先,在一个机器学习的系统当中,人们很难理解为什么一个结果比另一个结果要好。机器学习系统像一个黑盒子,大部分时候告诉我们结果1比结果2更加相关的概率,但不会告诉我们是因为什么原因结果1比结果2要好。

其次,很多information retrieval当中发现的特征很难在机器学习模型中产生效果。因为这些特征常常是针对某一类检索问题,然而对于那一类检索问题,常见的机器学习算法可能会为了模型的概括性以及防止overfitting,忽略特定的特征。这也是为什么当有了足够多的ranking engineer,大部分人都会专注改进rule-based scoring方法,去直接针对特定问题进行改进。

直接优化的Learning to rank模型

上一段没有讲到的一点,就是Learning to rank很难直接优化我们最终对搜索结果排序的打分指标-Normalized Discounted Cumulative Gain(NDCG)。因为这个方程既不是连续的,也不是可导的。

对于一些线性的机器学习模型,一种直接优化的方法就是Grid Search。去枚举线性模型当中每一个特征的权重,假设每个特征有K种取值,而一共有d个特征,那么该算法的复杂度就是O(K^d),只有在特征很少的时候我们才能使用Grid Search的方式去求解。

当然,如果一个局部的最优解可以让你满足,你还可以采用Coordinate Descent算法来很快的找到一个局部最优解。采用Grid Search和Coordinate Descent来直接优化评价函数的好处是及时在训练数据极度不均衡时也能得到很好地效果。这一点是SVM和一些优化likelihood的算法无法做到的。

近似优化

更多Learning to rank的算法都不是直接去优化最终评价函数。而是通过优化一个近似的可导的凸代理函数。这个代理函数常常是我们评价函数的下界或是上界。这里我提到的三个方法都来自Microsoft Research,虽然Bing的搜索不怎么样,Research的工作还是蛮好的。

最简单的模型就是Perceptron Learning,通过基于perceptron的算法来优化mean average precision(Gao et al. 2005)。这个模型就像是神经网络中的单个神经元,对于一个线性模型用梯度下降来优化。

之后,Microsoft又提出了基于神经网络的RankNet(Chris et al. 2005),引入了基于cross entropy的优化方法,他们认为一个文档好于另一个文档的cost function为:

这里oij为两个文档的分差。当有了这些基础的定义后,他们通过神经网络来计算文档的得分,采用back propagation来调整神经网络的参数,得出非线性的结果。

再此神经网络的基础上,Chris et al又提出了能够优化不可导函数的神经网络模型,他们称为LambdaRank,用Lambda来近似该不可导函数。对于传统的NDCG,Lambda的定义如下:

更先进的模型

在LambdaRank之后,Microsoft还发明了LambdaMART,一举夺得了Yahoo举办的Learning to Rank Challenge的第一名。在我的理解中,LambdaMART是一种改进版的GBDT模型,利用Decision Tree能解决非线性问题的优势来更好地解决排序的问题。

另外Google的RankBrain以及Baidu最新的搜索算法还采用了很多深度学习的思想,使得最终方程变得更深,更加优化。

在我的理解当中,如果我们只是想像Google,Bing,Baidu那样返回最想关的10个结果,那么完全可以在二次排序的时候采用复杂的模型。可是如今的网络平台Facebook,Pinterest,Instagram每次搜索都要给用户返回上百个相关结果,采用复杂的模型给Infrastructure带了非常大的挑战,并不是很容易实现。所以人们采用GBDT或DNN来做feature的变型,然后采用一个线性模型对所有结果排序。

最后

不得不说的是,搜索引擎和推荐系统还是存在着很大的不同的。因为搜索引擎在一定程度上需要更加客观的给出搜索结果,这里隐含着一些规矩。而推荐系统则是主观的推测你对什么感兴趣,有着相对较少的规矩。

最后想到楼教主最近给我讲的无人车的道理。当无人车在一个Stop sign前看到一个人准备过马路,后面有车在催你,你的车到底过还是不过?这里你所期待的并不是一个机器学习模型告诉你有99%的可能性你可以启动车在人过马路前过去,而是一个规则告诉你请在Stop sign前等待准备要过马路的行人。

When I try out a new machine learning framework