熟悉算法 --Learning to Rank & KL 距离

本贴最后更新于 2218 天前,其中的信息可能已经时过境迁

KL 距离

先简单介绍下:KL 距离--Kullback-Leibler Divergence

KL 距离,是 Kullback-Leibler 差异(Kullback-Leibler Divergence)的简称,也叫做相对熵(Relative Entropy)。它衡量的是 相同事件空间里的两个概率分布的差异情况。其物理意义是:在相同事件空间里,概率分布 P(x)的事件空间,若用概率分布 Q(x)编码时,平均每个基本事件(符号)编码长度增加了多少比特。我们用 D(P||Q)表示 KL 距离,计算公式如下:

当两个概率分布完全相同时,即 P(x)=Q(X),其相对熵为 0 。我们知道,概率分布 P(X)的信息熵为:

其表示,概率分布 P(x)编码时,平均每个基本事件(符号)至少需要多少比特编码。通过信息熵的学习,我们知道不存在其他比按照本身概率分布更好的编码方式了,所以 D(P||Q)始终大于等于 0 的。虽然 KL 被称为距离,但是其不满足距离定义的三个条件:**1)非负性;**2)对称性(不满足);3)三角不等式(不满足)

Learning to Rank

机器学习排序方法分为以下 3 种:单文档方法(Pointwise)、文档对方法(Pairwise)和文档列表方法(Listwise)。
注:

总体来说
Pointwise:用单个文档去训练,判断单个文档是否是跟输入的搜索是相关的
Pairwise:用 <doc1,doc2> 文档对去训练,doc1 和 doc2 都是与输入相关的,判断 doc1 是否比 doc2 更相关
Listwise:给定一个根据搜索得到的文档 list,训练一个打分函数,给 list 中的各个文档分别打分,然后根据得分进行排序

下面的似乎不太重要,想了解可以看一下

具体如下:

  • 单文档方法(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} 共五个类别。

  • 文档对方法(PairWise Approach)

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

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

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

根据转换后的训练实例,就可以利用机器学习方法进行分类函数的学习,具体的学习方法有很多,比如 SVM. Boosts、神经网络等都可以作为具体的学习方法,但是不论具体方法是什么,其学习目标都是一致的,即输入- 个査询和文档对, 机器学习排序能够判断这种顺序关系是否成立,如果成立,那么在搜索结果中 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 阶模型的表现。

  • 文档列表方法(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 的那个函数作为训练结果,将来作为在搜索时的评分函数。

  • 算法
    388 引用 • 254 回帖 • 21 关注
  • 文档
    56 引用 • 1288 回帖 • 2 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Gitea

    Gitea 是一个开源社区驱动的轻量级代码托管解决方案,后端采用 Go 编写,采用 MIT 许可证。

    4 引用 • 16 回帖 • 7 关注
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    59 引用 • 29 回帖 • 18 关注
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    170 引用 • 414 回帖 • 430 关注
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    66 引用 • 124 回帖
  • 强迫症

    强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。

    15 引用 • 161 回帖
  • OnlyOffice
    4 引用 • 19 关注
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    103 引用 • 294 回帖
  • Sublime

    Sublime Text 是一款可以用来写代码、写文章的文本编辑器。支持代码高亮、自动完成,还支持通过插件进行扩展。

    10 引用 • 5 回帖 • 1 关注
  • SQLite

    SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。

    4 引用 • 7 回帖 • 1 关注
  • JSON

    JSON (JavaScript Object Notation)是一种轻量级的数据交换格式。易于人类阅读和编写。同时也易于机器解析和生成。

    51 引用 • 190 回帖
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 346 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖 • 3 关注
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 41 关注
  • NetBeans

    NetBeans 是一个始于 1997 年的 Xelfi 计划,本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE,直到 1999 年 Sun 买下此公司。Sun 于次年(2000 年)六月将 NetBeans IDE 开源,直到现在 NetBeans 的社群依然持续增长。

    78 引用 • 102 回帖 • 636 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 247 回帖 • 212 关注
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    81 引用 • 122 回帖 • 614 关注
  • Markdown

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    163 引用 • 1446 回帖 • 1 关注
  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖 • 1 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    3 引用 • 74 回帖 • 3 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    116 引用 • 99 回帖 • 275 关注
  • OkHttp

    OkHttp 是一款 HTTP & HTTP/2 客户端库,专为 Android 和 Java 应用打造。

    16 引用 • 6 回帖 • 56 关注
  • App

    App(应用程序,Application 的缩写)一般指手机软件。

    90 引用 • 383 回帖
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    41 引用 • 130 回帖 • 294 关注
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖 • 8 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 426 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖