Learning to Rank小结

    Searcher's 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