精华内容
下载资源
问答
  • 机器学习排序方法
    千次阅读 多人点赞
    2020-03-04 11:40:59

    排序“损失”定义


    (本文为个人学习总结笔记)

    排序损失loss

    形式化地看, AUC考虑的是样本预测的排序质量,因此它与排序误差有紧 密联系.给定 m + m^{+} m+个正例和 m − m^{-} m个反例?令 D + D^{+} D+ D − D^{-} D分别表示正、反例集合, 则排序"损失" (loss)定义为:

    ℓ rank = 1 m + m − ∑ x + ∈ D + ∑ x − ∈ D − ( I ( f ( x + ) < f ( x − ) ) + 1 2 I ( f ( x + ) = f ( x − ) ) ) \ell_{\text {rank}}=\frac{1}{m^{+} m^{-}} \sum_{x^{+} \in D^{+}} \sum_{x^{-} \in D^{-}}\left(\mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\frac{1}{2} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right)\right) rank=m+m1x+D+xD(I(f(x+)<f(x))+21I(f(x+)=f(x)))

    l rank l_{\text {rank}} lrank即为ROC曲线上的面积,如下:
    在这里插入图片描述
    在这里插入图片描述

    更多相关内容
  • 推荐系统、搜索引擎的排序学习,适合入门以及提高机器排序学习的读者
  • 人工智能-机器学习
  • 人工智能-机器学习
  • 机器学习-推荐系统--排序
  • 机器学习-推荐系统--排序
  • 简单的源代码,针对大数据中的数据 对数据进行的排序。 mapreduce
  • 人工智能-机器学习-面向网页排序的关键词权值计算.pdf
  • 机器学习排序":  http://blog.csdn.net/hguisu/article/details/7989489  最近需要完成课程作业——分布式排序学习系统.它是在M/R、Storm或Spark架构上搭建分布式系统,并使用学习排序Pointwise、...

    PS:文章主要转载自CSDN大神hguisu的文章"机器学习排序":
              http://blog.csdn.net/hguisu/article/details/7989489
          最近需要完成课程作业——分布式排序学习系统.它是在M/R、Storm或Spark架构上搭建分布式系统,并使用学习排序Pointwise、Pairwise和Listwise三大类算法实现对微软数据集(Microsoft Learning to Rank Datasets)进行学习排序,这篇文章是对其入门介绍.感觉很难啊~
          推荐&参考资料:
        《Learning to Rank for Information Retrieval By:Tie-Yan Liu》
        《这就是搜索引擎 核心技术详解 著:张俊林》
          论文《Learning to rank From Pairwise Approach to Listwise Approace》
          论文《Adapting Ranking SVM to Document Retrieval By:Tie-Yan Liu》
          维基百科介绍 Learning to rank
          开源软件 Rank SVM Support Vector Machine for Ranking 
          开源软件 RankLib包括RankNet RankBoost AdaRank
          博客园文章 Learning to Rank入门小结

           从使用的数据类型,以及相关的机器学习技术的观点来看,互联网搜索经历了三代的发展历程。
           第一代技术,将互联网网页看作文本,主要采用传统信息检索的方法。
           第二代技术,利用互联网的超文本结构,有效地计算网页的相关度与重要度,代表的算法有 PageRank 等。
           第三代技术,有效利用日志数据与统计学习方法,使网页相关度与重要度计算的精度有了进一步的提升,代表的方法包括排序学习、网页重要度学习、匹配学习、话题模型学习、查询语句转化学习。
           这里主要介绍机器学习排序。

    1. 机器学习排序(Learning to Rank)

           利用机器学习技术来对搜索结果进行排序,这是最近几年非常热门的研究领域。信息检索领域已经发展了几十年,为何将机器学习技术和信息检索技术相互结合出现较晚?主要有两方面的原因。

           一方面是因为:在前面几节所述的基本检索模型可以看出,用来对査询和文档的相关性进行排序,所考虑的因素并不多,主要是利用词频、逆文档频率和文档长度这几个因子来人工拟合排序公式。因为考虑因素不多,由人工进行公式拟合是完全可行的,此时机器学习并不能派上很大用场,因为机器学习更适合采用很多特征来进行公式拟合,此时若指望人工将几十种考虑因素拟合出排序公式是不太现实的,而机器学习做这种类型的工作则非常合适。随着搜索引擎的发展,对于某个网页进行排序需要考虑的因素越来越多,比如网页的pageRank值、查询和文档匹配的单词个数、网页URL链接地址长度等都对网页排名产生影响,Google目前的网页排序公式考虑200多种因子,此时机器学习的作用即可发挥出来,这是原因之一。
          另外一个原因是:对于有监督机器学习来说,首先需要大量的训练数据,在此基础上才可能自动学习排序模型,单靠人工标注大量的训练数据不太现实。对于搜索引擎来说, 尽管无法靠人工来标注大量训练数据,但是用户点击记录是可以当做机器学习方法训练数据的一个替代品,比如用户发出一个查询,搜索引擎返回搜索结果,用户会点击其中某些网页,可以假设用户点击的网页是和用户查询更加相关的页面。尽管这种假设很多时候并 不成立,但是实际经验表明使用这种点击数据来训练机器学习系统确实是可行的。

          PS:简言之,上面两个原因论述了为什么会出现学习排序?
          传统的排序方法是通过构造一个排序函数实现,在Information Retrieval领域一般按照相关度进行排序。比较典型的是搜索引擎中一条查询query,将返回一个相关的文档document,然后根据(query,document)之间的相关度进行排序,再返回给用户。而随着影响相关度的因素变多,使用传统排序方法变得困难,人们就想到通过机器学习来解决这一问题,这就导致了LRT的诞生。

    2. 机器学习的基本思路

          传统的检索模型靠人工拟合排序公式,并通过不断的实验确定最佳的参数组合,以此来形成相关性打分函数。机器学习排序与此思路不同,最合理的排序公式由机器自动学习获得,而人则需要给机器学习提供训练数据。

          图1是利用机器学习进行排序的基本原理图。 机器学习排序系统由4个步骤组成:人工标注训练数据、文档特征抽取、学习分类函数、在实际搜索系统中采用机器学习模型。

          

      图1  机器学习排序原理

           首先,由人工标注训练数据。也就是说,对于某个查询Q,人工标出哪些文档是和这个査询相关的,同时标出相关程度,相关程度有时候可以用数值序列来表示,比如从1分到5分为3个档次,1代表微弱相关,5代表最相关,其他数值代表相关性在两者之间。对于某个查询,可能相关文档众多,同时用户査询也五花八门,所以全部靠人工标注有时候 不太可能。此时,可以利用用户点击记录来模拟这种人工打分机制。
          对于机器学习来说,输入是用户查询和一系列标注好的文档,机器学习系统需要学习打分函数,然后按照打分函数输出搜索结果,但是在其内部,每个文档由若干特征构成的,即每个文档进入机器学习系统之前,首先需要将其转换我饿滴特征向量,比较常用的特征包括:
          ·查询词在文档中的词频信息 
          ·查询词的IDF信息
          ·文档长度
          ·网页的入链数量
          ·网页的出链数量
          ·网页的pageRank值
          ·网页的URL松度
          ·査询词的Proximity值:即在文档中多大的窗口内可以出现所有査询词。

           以上所列只是影响排序的一部分特征,实际上还有很多类似的特征可以作为特征向量中的一维加入。在确定了特征数量后,即可将文档转換为特征向量X,前面说过每个文档会人工标出其相关性得分y。这样每个文档会转換为<X,Y>的形式,即特征向量及其对应的相关性得分,这样就形成了一个具体的训练实例。

           通过多个调练实例,就可以采用机器学习技术来对系统进行训练,训练的结果往在是一个分类函数或者回归函数,在之后的用户搜索中,就可以用这个分类函数对文档进行打分,形成搜索结果。

           从目前的研究方法来说,可以将机器学习排序方法分为以下3种:单文档方法(Pointwise)、文档对方法(Pairwise)和文档列表方法(Listwise)。

           PS:Ranking学习作为机器学习研究的一个新方向,在信息检索、协同滤波、专家发现等领域广泛应用。Ranking学习是指通过使用机器学习技术和有标签的数据来产生一个ranking模型,它是一种新的学习,一种介于分类和回归之间的学习。
           Pointwise和Pairwise把排序问题转换成 回归 、分类或有序分类问题。Listwise把Query下整个搜索结果作为一个训练的实例。3种方法的区别主要体现在损失函数(Loss Function)上:
           •Regression: treat relevance degree as real values
           •Classification: treat relevance degree as categories
           •Pairwise classification: reduce ranking to classifying the order between each pair of documents.

           下面是两张图,第一张表示学习排序的过程,第二章是基本的实现算法。

     

     

    3. 单文档方法(PointWise Approach)

           单文档方法的处理对象是单独的一篇文档,将文档转换为特征向量后,机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分,打分结果即是搜索结果。下面我们用一个简单的例子说明这种方法。 
           图2是人工标注的训练集合,在这个例子中,我们对于每个文档采用了3个特征: 査询与文档的Cosme相似性分值、査询词的Proximity值及页面的PageRank数值,而相关性判断是二元的,即要么相关要么不相关,当然,这里的相关性判断完全可以按照相关程度扩展为多元的,本例为了方便说明做了简化。

     

     

      图2 训练数据

            例子中提供了5个训练实例,每个训练实例分别标出来其对应的查询,3个特征的得分情况及相关性判断。对于机器学习系统来说,根据训练数据,需要如下的线性打分函数:
            Score(Q, D)=a x CS+b x PM+cx PR+d 
            这个公式中,cs代表Cosine相似度变徽,PM代表Proximity值变量,PR代表pageRank, 而a、b、c、d则是变量对应的参数。

            如果得分大于设定阀值,则叫以认为是相关的, 如果小于设定闽值则可以认为不相关。通过训练实例,可以获得最优的a、b、c、d参数组合,当这些参数确定后,机器学习系统就算学习完毕,之后即可利用这个打分函数进行相关性判断。对于某个新的查询Q和文档D,系统首先获得其文档D对应的3个特 I特征值,之后利用学习到的参数组合计算两者得分,当得分大于设定的闽值,即可判断文档是相关文档,否则判断为不相关文档。

            PS:而微软给定的数据如下
              =============================================================
                                          0 qid:1 1:3 2:0 3:2 4:2 ... 135:0 136:0 
                                          2 qid:1 1:3 2:3 3:0 4:0 ... 135:0 136:0 
              =============================================================
            其数据格式: label qid:id  feaid:feavalue  feaid:feavalue ...
            每行表示一个样本,相同的查询请求的样本qid相同,上面就是两个对qid为“1”的查询;label表示该样本和该查询请求的相关程度,该label等级划分方式为 {Perfect, Excellent,Good, Fair, Bad} 共五个类别。

    4. 文档对方法(PairWise Approach)

            对于搜索系统来说,系统接收到用户査询后,返回相关文档列表,所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算,没有考虑文档之间的顺序关系。文档对方法则将重点转向量对文档顺序关系是否合理进行判断。

            之所以被称为文档对方法,是因为这种机器学习方法的训练过程和训练目标,是判断任意两个文档组成的文档对<D0C1,D0C2>是否满足顺序关系,即判断是否D0C1应该排在DOC2的前面。图3展示了一个训练实例:査询Q1对应的搜索结果列表如何转换为文档对的形式,因为从人工标注的相关性得分可以看出,D0C2得分最高,D0C3次之,D0C1得分最低,于是我们可以按照得分大小顺序关系得到3个如图3所示的文档对,将每个文档对的文档转换为特征向量后,就形成了一个具体的训练实例。

        

    图3  文档对的方法训练实例

           根据转换后的训练实例,就可以利用机器学习方法进行分类函数的学习,具体的学习方法有很多,比如SVM. Boosts、神经网络等都可以作为具体的学习方法,但是不论具体方法是什么,其学习目标都是一致的,即输入- 个査询和文档对<Docl,DOC2>, 机器学习排序能够判断这种顺序关系是否成立,如果成立,那么在搜索结果中D0C1应该排在D0C2 前面,否则Doe2应该摔在Docl前面,通过这种方式,就完成搜索结果的排序任务。
            尽管文档对方法相对单文档方法做出了改进,但是这种方法也存在两个明显的问题:

           一个问题是:文档对方法只考虑了两个文档对的相对先后顺序,却没有考虑文档出现在搜索列表中的位置,排在搜索站果前列的文档更为重要,如果前列文档出现判断错误,代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素,即每个文档对根据其在列表中的顺序具有不同的权重,越是排在前列的权重越大,即在搜索列表前列如 果排错顺序的话其付出的代价更高?
            另外一个问题是:不同的査询,其相关文档数量差异很大,所以转换为文档对之后, 有的查询对能有几百个对应的文档对,而有的查询只有十几个对应的文档对,这对机器学习系统的效果评价造成困难 ?我们设想有两个查询,査询Q1对应500个文文档对,查询Q2 对应10个文档对,假设学习系统对于査询Ql的文档对能够判断正确480个,对于査询 Q2的义格对能够判新正确2个,如果从总的文档对数量来看,这个学习系统的准确率是 (480+2)/(500+10)=0.95.即95%的准确率,但是从査询的角度,两个査询对应的准确率 分别为:96%和20%,两者平均为58%,与纯粹从文档对判断的准确率相差甚远,这对如何继续调优机器学习系统会带来困扰。

           PS:Pairwise方法有很多的实现,比如SVM Rank(开源), 还有RankNet(C. Burges, et al. ICML 2005), FRank(M.Tsai, T.Liu, et al. SIGIR 2007),RankBoost(Y. Freund, et al. JMLR 2003)等等。
            你通常会看到微软数据集每个Fold文件夹下有train.txt test.txt vail.text三个文件,它们分别的作用是什么呢?
            训练集--用于学习参数,比如可以训练10个不同阶的线性模型,这里得到每个特征值的权值;验证集--用来选择模型,主要考虑的准则是在新的数据上的泛化能力,比如根据各个模型在验证集上的权值,选择了3阶的模型;测试集--测试模型,测试这个被选中的3阶模型的表现。

     

    4. 文档列表方法(ListWise Approach)

              单文档方法将训练集里每一个文档当做一个训练实例,文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例,文档列表方法与上述两种表示方式不同,是将每一个查询对应的所有搜索结果列表整体作为一个训练实例,这也是为何称之为文档列表方法的原因。
            文档列表方法根据K个训练实例(一个査询及其对应的所有搜索结果评分作为一个实 例)训练得到最优评分函数F, 对于一个新的用户査询,函数F 对每一个文档打分,之后按照得分顺序由高到低排序,就是对应的搜索结果。 所以关键问题是:拿到训练数据,如何才能训练得到最优的打分函数?

            这里介绍一种训练方法,它是基于搜索结果排列组合的概率分布情况来训练的,图4是这种方式训练过程的图解示意。

          

    图4 不同评分函数的KL距离

            首先解释下什么是搜索结果排列组合的概率分布,我们知道,对于搜索 引擎来说,用户输入査询Q, 搜索引擎返回搜索结果,我们假设搜索结果集合包含A. B 和C 3个文档,搜索引擎要对搜索结果排序,而这3个文档的顺序共有6种排列组合方式:

            ABC, ACB, BAG, BCA, CAB和CBA,

            而每种排列组合都是一种可能的搜索结果排序方法。

            对于某个评分函数F来说,对3个搜索结果文档的相关性打分,得到3个不同的相关度得分F(A)、 F(B)和F(C), 根据这3个得分就可以计算6种排列组合情况各自的概率值。 不同的评分函数,其6种搜索结果排列组合的概率分布是不一样的。
          了解了什么是搜索结果排列组合的概率分布,我们介绍如何根据训练实例找到最优的 评分函数。图4展示了一个具体的训练实例,即査询Q1及其对应的3个文档的得分情况,这个得分是由人工打上去的,所以可以看做是标准答案。可以设想存在一个最优的评分函数g,对查询Q1来说,其打分结果是:A文档得6分,B文档得4分,C文档得3分, 因为得分是人工打的,所以具体这个函数g是怎样的我们不清楚,我们的任务就是找到一 个函数,使得函数对Ql的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分 (虚拟的函数g) 已知,那么我们可以计算函数g对应的搜索结果排列组合概率分布,其具体分布情况如图4中间的概率分布所示。假设存在两个其他函数h和f,它们的计算方法已知,对应的对3个搜索结果的打分在图上可以看到,由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布,那么h与f哪个与虚拟的最优评分函数g更接近呢?一般可以用两个分布概率之间的距离远近来度量相似性,KL距离就是一种衡量概率分布差异大小的计算工具,通过分别计算h与g的差异大小及f与g的差异大小,可以看出f比h更接近的最优函数g,那么在这个函数中,我们应该优先选f作为将来搜索可用的评分函数,训练过程就是在可能的函数中寻找最接近虚拟最优函数g的那个函数作为训练结果,将来作为在搜索时的评分函数。

           上述例子只是描述了对于单个训练实例如何通过训练找到最优函数,事实上我们有K 个训练实例,虽然如此,其训练过程与上述说明是类似的,可以认为存在一个虚拟的最优 评分函数g (实际上是人工打分),训练过程就是在所有训练实例基础上,探寻所有可能的 候选函数,从中选择那个KL距离最接近于函数g的,以此作为实际使用的评分函数。 经验结果表明,基于文档列表方法的机器学习排序效果要好于前述两种方法。

           声明:本博客摘自《这就是搜索引擎:核心技术详解》 第五章关于机器学习排序的内容。转载请说明摘自出处。
           最后希望文章对大家有所帮助吧!虽然是我转载的一篇文章,但是它真心很好,是对Learning to Rank的基础入门介绍文章,从为什么引入学习排序,到介绍三种方法。

    原文地址:https://blog.csdn.net/eastmount/article/details/42367515

    展开全文
  • 基于ListMLE排序学习方法机器译文自动评价研究
  • 机器学习排序

    千次阅读 2019-01-16 16:52:15
    机器学习排序
                   

           从使用的数据类型,以及相关的机器学习技术的观点来看,互联网搜索经历了三代的发展历程。

           第一代技术,将互联网网页看作文本,主要采用传统信息检索的方法。

           第二代技术,利用互联网的超文本结构,有效地计算网页的相关度与重要度,代表的算法有 PageRank 等。

           第三代技术,有效利用日志数据与统计学习方法,使网页相关度与重要度计算的精度有了进一步的提升,代表的方法包括排序学习、网页重要度学习、匹配学习、话题模型学习、查询语句转化学习。

           这里主要介绍机器学习排序。

    1. 机器学习排序(Learning to Rank)

            利用机器学习技术来对搜索结果进行排序,这是最近几年非常热门的研究领域。信息检索领域已经发展了几十年,为何将机器学习技术和信息检索技术相互结合出现较晚?主要有两方面的原因。

            一方面是因为:在前面几节所述的基本检索模型可以看出,用来对査询和文档的相关性进行排序,所考虑的因素并不多,主要是利用词频、逆文档频率和文档长度这几个因子来人工拟合排序公式。因为考虑因素不多,由人工进行公式拟合是完全可行的,此时机器学习并不能派上很大用场,因为机器学习更适合采用很多特征来进行公式拟合,此时若指望人工将几十种考虑因素拟合出排序公式是不太现实的,而机器学习做这种类型的工作则非常合适。随着搜索引擎的发展,对于某个网页进行排序需要考虑的因素越来越多,比如网页的pageRank值、查询和文档匹配的单词个数、网页URL链接地址长度等都对网页排名产生影响,Google目前的网页排序公式考虑200多种因子,此时机器学习的作用即可发挥出来,这是原因之一。
           另外一个原因是:对于有监督机器学习来说,首先需要大量的训练数据,在此基础上才可能自动学习排序模型,单靠人工标注大量的训练数据不太现实。对于搜索引擎来说, 尽管无法靠人工来标注大量训练数据,但是用户点击记录是可以当做机器学习方法训练数据的一个替代品,比如用户发出一个查询,搜索引擎返回搜索结果,用户会点击其中某些网页,可以假设用户点击的网页是和用户查询更加相关的页面。尽管这种假设很多时候并 不成立,但是实际经验表明使用这种点击数据来训练机器学习系统确实是可行的。

    2. 机器学习的基本思路

           传统的检索模型靠人工拟合排序公式,并通过不断的实验确定最佳的参数组合,以此来形成相关性打分函数。机器学习排序与此思路不同,最合理的排序公式由机器自动学习获得,而人则需要给机器学习提供训练数据。

           图1是利用机器学习进行排序的基本原理图。 机器学习排序系统由4个步骤组成:人工标注训练数据、文档特征抽取、学习分类函数、在实际搜索系统中采用机器学习模型.

                   

                                                      图1  机器学习排序原理

     


           首先,由人工标注训练数据。也就是说,对于某个查询Q,人工标出哪些文档是和这个査询相关的,同时标出相关程度,相关程度有时候可以用数值序列来表示,比如从1分 到5分为3个档次,1代表微弱相关,5代表最相关,其他数值代表相关性在两者之间。对于某个查询,可能相关文档众多,同时用户査询也五花八门,所以全部靠人工标注有时候 不太可能。此时,可以利用用户点击记录来模拟这种人工打分机制。
          对于机器学习来说,输入是用户查询和一系列标注好的文档,机器学习系统需要学习打分函数,然后按照打分函数输出搜索结果,但是在其内部,每个文档由若干特征构成的,即每个文档进入机器学习系统之前,首先需要将其转换我饿滴特征向量,比较常用的特征包括:

    • 查询词在文档中的词频信息
    • 查询词的IDF信息
    • 文档长度:
    • 网页的入链数量:
    • 网页的出链数量:
    • 网页的pageRank值;
    • 网页的URL松度:
    • 査询词的Proximity值:即在文档中多大的窗口内可以出现所有査询词。

            以上所列只是影响排序的一部分特征,实际上还有很多类似的特征可以作为特征向量中的一维加入。在确定了特征数量后,即可将文档转換为特征向量X,前面说过每个文档会人工标出其相关性得分y.这样每个文档会转換为<X,Y>的形式,即特征向量及其对应的相关性得分,这样就形成了一个具体的训练实例。

           通过多个调练实例,就可以采用机器学习技术来对系统进行训练,训练的结果往在是 ―个分类函数或者回归函数,在之后的用户搜索中,就可以用这个分类函数对文档进行打分,形成搜索结果 

        从目前的研究方法来说,可以将机器学习揉序方法分为以下3种:单文档方法、文档对方法和文档列表方法。

     

    3. 单文档方法(PointWise Approach》

            单文档方法的处理对象是单独的一篇文档,将文档转换为特征向量后,机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分,打分结果即是搜索结果。下面我们用一个简单的例子说明这种方法。 
            图2是人工标注的训练集合,在这个例子中,我们对于每个文档采用了3个特征: 査询与文档的Cosme相似性分值、査询词的Proximity值及页面的PageRank数值,而相关性判断是二元的,即要么相关要么不相关,当然,这里的相关性判断完全可以按照相关程度扩展为多元的,本例为了方便说明做了简化。

              

                                              图2 训练数据
            

          例子中提供了5个训练实例,每个训练实例分别标出来其对应的查询,3个特征的得分情况及相关性判断。对于机器学习系统来说,根据训练数据,需要如下的线性打分函数:
     
           Score(Q, D)=a x CS+ b x PM+cx PR+ d
            这个公式中,cs代表Cosine相似度变徽,PM代表Proximity值变量,PR代表pageRank, 而a、 b、 c、 d则是变量对应的参数。

            如果得分大于一设定阀值,则叫以认为是相关的, 如果小于设定闽值则可以认为不相关。通过训练实例,可以获得最优的a、 b,、c、d参数组合,当这些参数确定后,机器学习系统就算学习完毕,之后即可利用这个打分函数进行相关性判断。对于某个新的查询Q和文档D,系统首先获得其文档D对应的3个特 I特征值,之后利用学习到的参数组合计算两者得分,当得分大于设定的闽值,即可判断文档是相关文档,否则判断为不相关文档。

     

    4. 文档对方法(PairWise Approach)

            对于搜索系统来说,系统接收到用户査询后,返回相关文档列表,所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算,没有考虑文档之间的顺序关系。文档对方法则将重点转向量对文档顺序关系是否合理进行判断。

            之所以被称为文档对方法,是因为这种机器学习方法的训练过程和训练目标,是判断任意两个文档组成的文档对<D0C1,D0C2>是否满足顺序关系,即判断是否D0C1应该排在DOC2的前面。图3展示了一个训练实例:査询Q1对应的搜索结果列表如何转换为文档对的形式,因为从人工标注的相关性得分可以看出,D0C2得分最高,D0C3次之,D0C1得分最低,于是我们可以按照得分大小顺序关系得到3个如图3所示的文档对,将每个文档对的文档转换为特征向量后,就形成了一个具体的训练实例。

         

                                                图3  文档对的方法训练实例


           根据转换后的训练实例,就可以利用机器学习方法进行分类函数的学习,具体的学习方法有很多,比如SVM. Boosts、神经网络等都可以作为具体的学习方法,但是不论具体方法是什么,其学习目标都是一致的,即输入- 个査询和文档对<Docl,DOC2>, 机器学习排序能够判断这种顺序关系是否成立,如果成立,那么在搜索结果中D0C1应该排在D0C2 前面,否则Doe2应该摔在Docl前面,通过这种方式,就完成搜索结果的排序任务。
            尽管文档对方法相对单文档方法做出了改进,但是这种方法也存在两个明显的问题:

           一个问题是:文档对方法只考虑了两个文档对的相对先后顺序,却没有考虑文档出现在搜索列表中的位置,排在搜索站果前列的文档更为重要,如果前列文档出现判断错误,代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素,即每个文档对根据其在列表中的顺序具有不同的权重,越是排在前列的权重越大,即在搜索列表前列如 果排错顺序的话其付出的代价更高•
            另外一个问题是:不同的査询,其相关文档数量差异很大,所以转换为文档对之后, 有的查询对能有几百个对应的文档对,而有的查询只有十几个对应的文档对,这对机器学习系统的效果评价造成困难 •我们设想有两个查询,査询Q1对应500个文文档对,查询Q2 对应10个文档对,假设学习系统对于査询Ql的文档对能够判断正确480个,对于査询 Q2的义格对能够判新正确2个,如果从总的文档对数量来看,这个学习系统的准确率是 (480+2)/(500+10)=0.95.即95%的准确率,但是从査询的角度,两个査询对应的准确率 分别为:96%和20%,两者平均为58%,与纯粹从文档对判断的准确率相差甚远,这对如何继续调优机器学习系统会带来困扰。

     

    4. 文档列表方法(ListWise Approach)

              单文档方法将训练集里每一个文档当做一个训练实例,文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例,文档列表方法与上述两种表示方式不同,是将每一个查询对应的所有搜索结果列表整体作为一个训练实例,这也是为何称之为文档列表方法的原因。
            文档列表方法根据K个训练实例(一个査询及其对应的所有搜索结果评分作为一个实 例)训练得到最优评分函数F, 对于一个新的用户査询,函数F 对每一个文档打分,之后按照得分顺序由高到低排序,就是对应的搜索结果。 所以关键问题是:拿到训练数据,如何才能训练得到最优的打分函数?

            这里介绍一种训练方法,它是基于搜索结果排列组合的概率分布情况来训练的,图4是这种方式训练过程的图解示意。

           

                                           图4 不同评分函数的KL距离

     

           首先解释下什么是搜索结果排列组合的概率分布,我们知道,对于搜索 引擎来说,用户输入査询Q, 搜索引擎返回搜索结果,我们假设搜索结果集合包含A. B 和C 3个文档,搜索引擎要对搜索结果排序,而这3个文档的顺序共有6种排列组合方式:

          ABC, ACB, BAG, BCA, CAB和CBA,

            而每种排列组合都是一种可能的搜索结果排序方法。

            对于某个评分函数F来说,对3个搜索结果文档的相关性打分,得到3个不同的相关度得分F(A)、 F(B)和F(C), 根据这3个得分就可以计算6种排列组合情况各自的概率值。 不同的评分函数,其6种搜索结果排列组合的概率分布是不一样的。
          了解了什么是搜索结果排列组合的概率分布,我们介绍如何根据训练实例找到最优的 评分函数。图4展示了一个具体的训练实例,即査询Q1及其对应的3个文档的得分情况,这个得分是由人工打上去的,所以可以看做是标准答案。可以设想存在一个最优的评分函数g,对查询Q1来说,其打分结果是:A文档得6分,B文档得4分,C文档得3分, 因为得分是人工打的,所以具体这个函数g是怎样的我们不清楚,我们的任务就是找到一 个函数,使得函数对Ql的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分 (虚拟的函数g) 已知,那么我们可以计算函数g对应的搜索结果排列组合概率分布,其具体分布情况如图4中间的概率分布所示。假设存在两个其他函数h和f,它们的计算方法已知,对应的对3个搜索结果的打分在图上可以看到,由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布,那么h与f哪个与虚拟的最优评分函数g更接近呢?一般可以用两个分布概率之间的距离远近来度量相似性,KL距离就是一种衡量概率分布差异大小的计算工具,通过分别计算h与g的差异大小及f与g的差异大小,可以看出f比h更接近的最优函数g,那么在这个函数中,我们应该优先选f作为将来搜索可用的评分函数,训练过程就是在可能的函数中寻找最接近虚拟最优函数g的那个函数作为训练结果,将来作为在搜索时的评分函数。

           上述例子只是描述了对于单个训练实例如何通过训练找到最优函数,事实上我们有K 个训练实例,虽然如此,其训练过程与上述说明是类似的,可以认为存在一个虚拟的最优 评分函数g (实际上是人工打分),训练过程就是在所有训练实例基础上,探寻所有可能的 候选函数,从中选择那个KL距离最接近于函数g的,以此作为实际使用的评分函数。 经验结果表明,基于文档列表方法

    的机器学习排序效果要好于前述两种方法。

    声明:本博客摘自《这就是搜索引擎:核心技术详解》 第五章关于机器学习排序的内容。转载请说明摘自出处。

               

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • 人工智能-机器学习
  • 目前在美团的团购系统中大量地应用到了机器学习和数据挖掘技术,例如个性化推荐、筛选排序、搜索排序、用户建模等等,为公司创造了巨大的价值。本文主要介绍在美团的推荐与个性化团队实践中的数据清洗与特征挖掘方法...
  • 排序学习技术尝试用机器学习方法解决排序问题,已被深入研究并广泛应用于不同的领域,如信息检索、文本挖掘、个性化推荐、生物医学等.将排序学习融入推荐算法中,研究如何整合大量用户和物品的特征,构建更加贴合用户...
  • 大数据-算法-机器学习效应的两类排序问题.pdf
  • 机器学习在搜索排序中应用.ppt
  • 同时,在每个算法的内部,不同item的顺序也只是简单的由一个或者几个因素决定,这些排序方法只能用于第一步的初选过程,最终的排序结果需要借助机器学习方法,使用相关的排序模型,综合多方面的因素来确定。...
    【转】http://blog.csdn.net/chndata/article/details/43405641

    编者按:在用户意图明确时,我们通常用搜索引擎来解决互联网时代的信息过载问题,但当用户的意图不明确或者很难用清晰的语义表达,搜索引擎就无能为力。此时,借助推荐系统通过用户行为的分析理解其意图,为其推送个性化的结果,便成为一种更好的选择。美团作为国内发展较快的O2O网站,有着大量的用户和丰富的用户行为,这些为推荐系统的应用和优化提供了很好的条件。本文由美团技术团队成员撰写,介绍其推荐系统的构建和优化过程中的一些做法。
    框架



    从框架的角度看,推荐系统基本可以分为数据层、触发层、融合过滤层和排序层。数据层包括数据生成和数据存储,主要是利用各种数据处理工具对原始日志进行清洗,处理成格式化的数据,落地到不同类型的存储系统中,供下游的算法和模型使用。候选集触发层主要是从用户的历史行为、实时行为、地理位置等角度利用各种触发策略产生推荐的候选集。候选集融合和过滤层有两个功能,一是对出发层产生的不同候选集进行融合,提高推荐策略的覆盖度和精度;另外还要承担一定的过滤职责,从产品、运营的角度确定一些人工规则,过滤掉不符合条件的item。排序层主要是利用机器学习的模型对触发层筛选出来的候选集进行重排序。

    同时,对与候选集触发和重排序两层而言,为了效果迭代是需要频繁修改的两层,因此需要支持ABtest。为了支持高效率的迭代,我们对候选集触发和重排序两层进行了解耦,这两层的结果是正交的,因此可以分别进行对比试验,不会相互影响。同时在每一层的内部,我们会根据用户将流量划分为多份,支持多个策略同时在线对比。

    数据应用

    数据乃算法、模型之本。美团作为一个交易平台,同时具有快速增长的用户量,因此产生了海量丰富的用户行为数据。当然,不同类型的数据的价值和反映的用户意图的强弱也有所不同。



    1.用户主动行为数据记录了用户在美团平台上不同的环节的各种行为,这些行为一方面用于候选集触发算法(在下一部分介绍)中的离线计算(主要是浏览、下单),另外一方面,这些行为代表的意图的强弱不同,因此在训练重排序模型时可以针对不同的行为设定不同的回归目标值,以更细地刻画用户的行为强弱程度。此外,用户对deal的这些行为还可以作为重排序模型的交叉特征,用于模型的离线训练和在线预测。
    2.负反馈数据反映了当前的结果可能在某些方面不能满足用户的需求,因此在后续的候选集触发过程中需要考虑对特定的因素进行过滤或者降权,降低负面因素再次出现的几率,提高用户体验;同时在重排序的模型训练中,负反馈数据可以作为不可多得的负例参与模型训练,这些负例要比那些展示后未点击、未下单的样本显著的多。
    3.用户画像是刻画用户属性的基础数据,其中有些是直接获取的原始数据,有些是经过挖掘的二次加工数据,这些属性一方面可以用于候选集触发过程中对deal进行加权或降权,另外一方面可以作为重排序模型中的用户维度特征。
    4.通过对UGC数据的挖掘可以提取出一些关键词,然后使用这些关键词给deal打标签,用于deal的个性化展示。
    策略触发

    上文中我们提到了数据的重要性,但是数据的落脚点还是算法和模型。单纯的数据只是一些字节的堆积,我们必须通过对数据的清洗去除数据中的噪声,然后通过算法和模型学习其中的规律,才能将数据的价值最大化。在本节中,将介绍推荐候选集触发过程中用到的相关算法。

    1. 协同过滤

    提到推荐,就不得不说协同过滤,它几乎在每一个推荐系统中都会用到。基本的算法非常简单,但是要获得更好的效果,往往需要根据具体的业务做一些差异化的处理。

    • 清除作 弊、刷单、代购等噪声数据。这些数据的存在会严重影响算法的效果,因此要在第一步的数据清洗中就将这些数据剔除。
    • 合理选取训练数据。选取的训练数据的时间窗口不宜过长,当然也不能过短。具体的窗口期数值需要经过多次的实验来确定。同时可以考虑引入时间衰减,因为近期的用户行为更能反映用户接下来的行为动作。
    • user-based与item-based相结合。

     


     

    • 尝试不同的相似度计算方法。在实践中,我们采用了一种称作loglikelihood ratio[1]的相似度计算方法。在mahout中,loglikelihood ratio也作为一种相似度计算方法被采用。


    下表表示了Event A和EventB之间的相互关系,其中:

    k11 :Event A和EventB共现的次数
    k12 :Event B发生,EventA未发生的次数
    k21 :Event A发生,EventB未发生的次数
    k22 :Event A和EventB都不发生的次数



    则logLikelihoodRatio=2 * (matrixEntropy - rowEntropy -columnEntropy)

    其中

    rowEntropy = entropy(k11, k12) + entropy(k21, k22)
    columnEntropy = entropy(k11, k21) + entropy(k12, k22)
    matrixEntropy = entropy(k11, k12, k21, k22)

    (entropy为几个元素组成的系统的香农熵)

    2. location-based

    对于移动设备而言,与PC端最大的区别之一是移动设备的位置是经常发生变化的。不同的地理位置反映了不同的用户场景,在具体的业务中可以充分利用用户所处的地理位置。在推荐的候选集触发中,我们也会根据用户的实时地理位置、工作地、居住地等地理位置触发相应的策略。

    • 根据用户的历史消费、历史浏览等,挖掘出某一粒度的区域(比如商圈)内的区域消费热单和区域购买热单
    •  

     


     

    区域消费热单

     


     

    区域购买热单

     

    • 当新的线上用户请求到达时,根据用户的几个地理位置对相应地理位置的区域消费热单和区域购买热单进行加权,最终得到一个推荐列表。
    • 此外,还可以根据用户出现的地理位置,采用协同过滤的方式计算用户的相似度。


    3. query-based

    搜索是一种强用户意图,比较明确的反应了用户的意愿,但是在很多情况下,因为各种各样的原因,没有形成最终的转换。尽管如此,我们认为,这种情景还是代表了一定的用户意愿,可以加以利用。具体做法如下:

    • 对用户过去一段时间的搜索无转换行为进行挖掘,计算每一个用户对不同query的权重。

     


     

    • 计算每个query下不同deal的权重。

     


     

    • 当用户再次请求时,根据用户对不同query的权重及query下不同deal的权重进行加权,取出权重最大的TopN进行推荐。


    4. graph-based

    对于协同过滤而言,user之间或者deal之间的图距离是两跳,对于更远距离的关系则不能考虑在内。而图算法可以打破这一限制,将user与deal的关系视作一个二部图,相互间的关系可以在图上传播。Simrank[2]是一种衡量对等实体相似度的图算法。它的基本思想是,如果两个实体与另外的相似实体有相关关系,那它们也是相似的,即相似性是可以传播的。


    5. 实时用户行为

    目前我们的业务会产生包括搜索、筛选、收藏、浏览、下单等丰富的用户行为,这些是我们进行效果优化的重要基础。我们当然希望每一个用户行为流都能到达转化的环节,但是事实上远非这样。

    当用户产生了下单行为上游的某些行为时,会有相当一部分因为各种原因使行为流没有形成转化。但是,用户的这些上游 行为对我们而言是非常重要的先验知识。很多情况下,用户当时没有转化并不代表用户对当前的item不感兴趣。当用户再次到达我们的推荐展位时,我们根据用户之前产生的先验行为理解并识别用户的真正意图,将符合用户意图的相关deal再次展现给用户,引导用户沿着行为流向下游 行进,最终达到下单这个终极目标。

    目前引入的实时用户行为包括:实时浏览、实时收藏。

    6. 替补策略

    虽然我们有一系列基于用户历史行为的候选集触发算法,但对于部分新用户或者历史行为不太丰富的用户,上述算法触发的候选集太小,因此需要使用一些替补策略进行填充。

    • 热销单:在一定时间内销量最多的item,可以考虑时间衰减的影响等。
    • 好评单:用户产生的评价中,评分较高的item。
    • 城市单:满足基本的限定条件,在用户的请求城市内的。


    子策略融合

    为了结合不同触发算法的优点,同时提高候选集的多样性和覆盖率,需要将不同的触发算法融合在一起。常见的融合的方法有以下几种:

    • 加权型:最简单的融合方法就是根据经验值对不同算法赋给不同的权重,对各个算法产生的候选集按照给定的权重进行加权,然后再按照权重排序。
    • 分级型:优先采用效果好的算法,当产生的候选集大小不足以满足目标值时,再使用效果次好的算法,依此类推。
    • 调制型:不同的算法按照不同的比例产生一定量的候选集,然后叠加产生最终总的候选集。
    • 过滤型:当前的算法对前一级算法产生的候选集进行过滤,依此类推,候选集被逐级过滤,最终产生一个小而精的候选集合。


    目前我们使用的方法集成了调制和分级两种融合方法,不同的算法根据历史效果表现给定不同的候选集构成比例,同时优先采用效果好的算法触发,如果候选集不够大,再采用效果次之的算法触发,依此类推。

    候选集重排序

    如上所述,对于不同算法触发出来的候选集,只是根据算法的历史效果决定算法产生的item的位置显得有些简单粗暴,同时,在每个算法的内部,不同item的顺序也只是简单的由一个或者几个因素决定,这些排序的方法只能用于第一步的初选过程,最终的排序结果需要借助机器学习的方法,使用相关的排序模型,综合多方面的因素来确定。

    1. 模型

    非线性模型能较好的捕捉特征中的非线性关系,但训练和预测的代价相对线性模型要高一些,这也导致了非线性模型的更新周期相对要长。反之,线性模型对特征的处理要求比较高,需要凭借领域知识和经验人工对特征做一些先期处理,但因为线性模型简单,在训练和预测时效率较高。因此在更新周期上也可以做的更短,还可以结合业务做一些在线学习的尝试。在我们的实践中,非线性模型和线性模型都有应用。

    • 非线性模型


    目前我们主要采用了非线性的树模型Additive Groves[4](简称AG),相对于线性模型,非线性模型可以更好的处理特征中的非线性关系,不必像线性模型那样在特征处理和特征组合上花费比较大的精力。AG是一个加性模型,由很多个Grove组成,不同的Grove之间进行bagging得出最后的预测结果,由此可以减小过拟合的影响。



    每一个Grove有多棵树组成,在训练时每棵树的拟合目标为真实值与其他树预测结果之和之间的残差。当达到给定数目的树时,重新训练的树会逐棵替代以前的树。经过多次迭代后,达到收敛。


     

    • 线性模型


    目前应用比较多的线性模型非Logistic Regression莫属了。为了能实时捕捉数据分布的变化,我们引入了online learning,接入实时数据流,使用google提出的FTRL[5]方法对模型进行在线更新。



    主要的步骤如下:

    • 在线写特征向量到HBase
    • Storm解析实时点击和下单日志流,改写HBase中对应特征向量的label
    • 通过FTRL更新模型权重
    • 将新的模型参数应用于线上


    2. 数据

    采样:对于点击率预估而言,正负样本严重不均衡,所以需要对负例做一些采样。
    负例:正例一般是用户产生点击、下单等转换行为的样本,但是用户没有转换行为的样本是否就一定是负例呢?其实不然,很多展现其实用户根本没有看到,所以把这样样本视为负例是不合理的,也会影响模型的效果。比较常用的方法是skip-above,即用户点击的item位置以上的展现才可能视作负例。当然,上面的负例都是隐式的负反馈数据,除此之外,我们还有用户主动删除的显示负反馈数据,这些数据是高质量的负例。
    去噪:对于数据中混杂的刷单等类作 弊行为的数据,要将其排除出训练数据,否则会直接影响模型的效果。
    3. 特征

    在我们目前的重排序模型中,大概分为以下几类特征:

    • deal(即团购单,下同)维度的特征:主要是deal本身的一些属性,包括价格、折扣、销量、评分、类别、点击率等
    • user维度的特征:包括用户等级、用户的人口属性、用户的客户端类型等
    • user、deal的交叉特征:包括用户对deal的点击、收藏、购买等
    • 距离特征:包括用户的实时地理位置、常去地理位置、工作地、居住地等与poi的距离
    • 对于非线性模型,上述特征可以直接使用;而对于线性模型,则需要对特征值做一些分桶、归一化等处理,使特征值成为0~1之间的连续值或01二值。


    总结

    以数据为基础,用算法去雕琢,只有将二者有机结合,才会带来效果的提升。对我们而言,以下两个节点是我们优化过程中的里程碑:

    • 将候选集进行融合:提高了推荐的覆盖度、多样性和精度
    • 引入重排序模型:解决了候选集增加以后deal之间排列顺序的问题

     



    原文链接: 美团推荐算法实践

    感谢 mengyidan1988 投递这篇资讯

    资讯来源: 美团推荐算法实践

    展开全文
  • 大数据-算法-机器具有学习效应的两类分批排序问题.pdf
  • 机器学习在搜索排序中的应用一淘及搜索事业部-搜索技术 仁重agenda背景LTR方法评估并行化与多目标第一部分 背景LTR在淘宝搜索应用的背景背景用户输入Query引擎召回商品商品计算featureRank项目背景-特征商业业务逻辑...
  • 在AI场景下,我们同样需要定量的数值化指标,来指导我们更好地应用模型对数据进行学习和建模。本文讲解模型评估的一般流程,以及分类评估指标、回归评估指标的计算方式和适用场景。
  • 机器学习数据集划分方法

    千次阅读 2022-04-23 14:08:13
    3、在给定训练/测试样本的比例后,仍然存在多种划分方法对初始数据集 DDD 进行分割,如把 DDD 中样本进行排序,然后把前350个正例放到训练集中,也可把后350个正例放到训练集中。一般采用若干次随机划分、重复进行...
  • 机器学习排序

    2018-08-16 16:01:23
    从使用的数据类型,以及相关的机器学习技术的观点来看,互联网搜索经历了三代的发展历程。  第一代技术,将互联网网页看作文本,主要采用传统信息检索的方法。  第二代技术,利用互联网的超文本结构,有效地计算...
  • kaggle机器学习实战

    2018-06-27 20:29:21
    机器学习算法、工具与流程概述 经济金融领域的应用 排序与CTR预估 自然语言处理类问题 能源预测与分配问题 走起-深度学习 推荐与销量预测相关问题 金融风控问题
  • 本文来自于网络,本文将结合广告特殊的业务场景,介绍美团搜索广告场景下深度学习的应用和...传统的CTR/CVR预估,典型的机器学习方法包括人工特征工程+LR(LogisticRegression)[1]、GBDT(GradientBoostingDecisionT
  • R语言进行机器学习方法及实例 机器学习的研究领域是发明计算机算法,把数据转变为智能行为。机器学习和数据挖掘的区别可能是机器学习侧重于执行一个已知的任务,而数据发掘是在大数据中寻找有价值的东西。 机器...
  • 【大纲】 ·苏宁易购搜索介绍 ·搜索排序&影响排序内容 ·如何利用机器学习解决搜索问题 ·总结与思考
  • 本文覆盖机器学习常见知识要点,包括机器学习流程、算法分类(监督学习、无监督学习、强化学习)、依托的问题场景(分类、回归、聚类、降维)、机器学习模型评估与选择等。
  • 融合多种神经网络与多特征的答案排序方法.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 146,571
精华内容 58,628
热门标签
关键字:

机器学习排序方法