深入浅出搜索原理系列之(三)相关性算法

我们知道文本搜索中,召回率和准确率是很重要的两个指标,但是返回文档的相关性也很重要,这直接影响到返回文档集的优先顺序。最近在看ElasticSearch5.0(还是Alpha版),发现其基于的Lucene也升级到了6.X版本,重大变化之一就是把默认相关性算法从TF-IDF换成了BM25。这里大家一起了解下这两种算法及区别。

数据准备

这里为了更简单清晰的描述算法本身,演示数据尽可能简单点。假设有三篇文档(document),每个文档只有一个字段(field),字段名叫name。

doc0: tony is tony, my name is feiei
doc1: tony hehe
doc2: welcome pony

查询条件(query)“name, tony”先被分词成两个词语(term):name 和 tony,然后返回所有包含了 name 或者(or)tony 两个词语的文档。从上面的准备数据文档中,将会返回doc0和doc1两个文档。正确返回所有文档不难,但还要返回文档的优先级顺序,顺序在很多场景下都是很重要的因素,人们总是喜欢优先看到更匹配的内容。可以把每个返回的文档计算一个得分(score),然后按照得分大小排序后返回即可。计算得分的规则有不同的方式,下面我们就聊下几种算法。

这里说点题外话,估计大部分同学一看到数学公式就有点头晕,我觉得这是一种误解看法。数学公式就像我们做软件开发前画的UML设计图一样,都是对复杂规则的抽象描述表达,能用图表达的,就不要说一堆话来表达。一样的,数学公式可以从更高的层次把难以用语言表达清楚的概论给直观的抽象出来。我们有时候缺的是一种耐心去分析思考这公式后面所蕴含的意义。

TF-IDF算法

向量空间模型

TF-IDF是基于向量空间模型来计算,所以先介绍向量空间和余弦相似度。

f

上面公式中就是计算查询q和文档d之间的相似度。我们以上面的准备数据详细分析下:

V(q) = (tony在q中的频率次数, name在q频率次数) = (1, 1)
V(doc0) = (tony在doc0中的频率次数, name在doc0频率次数) = (2, 1)
V(doc1) = (tony在doc0中的频率次数, name在doc0频率次数) = (0, 1)

doc3中即不包含tony也不包含name,所以直接过滤去掉。V(q),V(doc1),V(doc2)都是二维向量,我们可以在平面坐标上画出来:

二维向量

从上面二维向量坐标图上容易看出,V(q)和V(doc0)的夹角比V(q)和V(doc1)小。在向量空间模型中,两个向量的夹角越小则越表示其越相似,在数学里叫做余弦相似度(cosine similarity)。

coso

下面分别计算下Sim(q, doc0)和Sim(q, doc1)的值:

我们可以用大白话解释下上面公式:分子是两个向量的元素点积,即两个向量在每个维度上的值两两相乘后相加,如果两个向量方向一致则形成合力变得更强大,如果两个向量方向相反,则相互抵消。比如(1, 1)是往左走,(-1,-1)往右走,相互作用后则完全抵消。但是(1,1)和(2,2)方向相同,则叠加后更加强大。而分母就是对刚才的分子结果作归一化,或者理解成单元化。举个例子就明白了:(1,1)和(2,2)两个向量方向一致,(1,1)和 (3,3)也是完全方向一致,而不用管两个向量的长度,所以为了消除其长度影响除了一个向量长度信息。

TF-IDF引入

上面章节中的向量空间模型中,每个向量的组成元素是词项出现次数:frequency(t,x)。即词项t在文档或者查询x中出现的次数。但是为了更好匹配质量,使用tf(t,x)*idf(t)来替代frequency(t,x)

tf(t,x)的定义:

tf

√frequency(t,x) q doc0 doc1 doc2
tony 1 √2 1 0
name 1 1 0 0

上面词项(第一列)和文档或查询(第一行)两两相交的地方就是其tf(t,x)值。

idf(t)定义:

tf

docCount表示文档总数,本文示例数据中,总共3篇文档(doc0,doc1,doc2),所以docCount为3。docFreq指包含了词项t的文档数量,所以docFreq(‘name’) = 1,因为name只出现在doc0中。docFreq(‘tony’) = 2 ,因为doc0和doc1都包含了tony。所以idf(t)可以表示词项t的特殊性,如果词项t在每篇文档都有出现,则说明t没有识别度,相反如果t只在少数个别文档中出现,即说明词项t非常特殊,应该拥有更高的权重地位。这里再个举个例子来更好理解,在一个卖手机的电商网站上,以“华为手机”为关键字搜索,因为“手机”这个词项基本在每个商品中都会出现,所以没有识别度,但是“华为”可能只在部分商品中出现,所以更是我们想要得到的。

从上面可以看出,无论是对tf公式中的平方根,还是idf的对数函数,都是基于现实的情况,两篇文档的相关度并不是简单和原始参数成正比,当值相差太大时,我们要调和这种差别。

Lucene基于TF-IDF其它优化

Lucene对tf-idf做了很了很多改进,这里一一说下。

引入文档长度影响因子

根据前面和向量空间模型中的余弦相似度公式,我们对向量做了归一化处理,所以向量 V(1,1) 和 V(2, 2) 的相似度和 V(1,1) 和 V(3,3)是一样的,这样完全忽略了文档本身的长度信息。这里举个数据例子,两个文档分别是:

文档1:i think that
文档2:”I think it’s unlikely to be a real thing. I’m sure it’s an overreaction about an already-skittish party,” Roberts said. “They have looked at what happens in that circumstance.”, hello, i love the word.

当我们搜索“think”关键字,虽然”think”在两篇文档中都只出现一次,如果按照之前公式,相似度值是一样的,但这里我们明显更希望返回文档1,因为文档2除了包含“think”,同时也包含了更多其它词项。所以在Lucene中,对文档长度归一化处理换了一种思路,引入了norm(t,d):相同的词项出现次数,如果文档更长,则norm(t,d)更小,如果文档更小,则norm(t,d)更大。

tf

公式中 numTerms 是文档d中包含的所有词项数量,从公式看出,文档越长,numTerms越大(不考虑词项大量重复出现情况),norm(t, d)越小。

引入词项权重,字段权重

在索引或者查询阶段,每个字段(field),每个词项(term)可以设置不同的权重值(boost),提高我们的期望返回准确率。

TF-IDF更多介绍文章

  1. 「Information Retrieval」,该教材是斯坦福大学信息检索课程,简称IR,是很好的入门学习教材。有中文译本。
  2. Lucene API Doc: TFIDFSimilarity 详细说明了if-idf的原理及lucene实现思路。

BM25算法

BM25算法则从概率模型理论出发推演出的一套相关性计算公式。相比TF-IDF算法还是复杂很多,其需要概率数学基础:概率事件,独立概率事件,贝叶斯定理,朴素贝叶斯定理等。详细算法及公式推演参考「信息检索导论」第11章内容。这里简短描述下大概理论依据:

  1. 在给定一个查询时,每篇文档可能与给定查询相关,或者不相关,所以这可以转化为一个概率问题。
  2. 如果用P(A)表示某篇文档和给定查询相关的概率值,P(B)表示该文档和给定查询不相关的概率,则有:P(A) + P(B) = 1。这点很好理解,文档要么和查询相关,要么和查询不相关。
  3. P(A)/P(B)这个值可以表示一篇文档和给定查询的相关性度量函数,该值越大,说明越相关。
  4. 词项(term)的文档频率越小(dft),则所在的文档具有更高的相关性概率。

虽然BM25和TF-IDF分别从完全不同的数学模型推算出来,但是从最终的数学公式可以看出其中又有很相似的地方,如果不想从复杂的数学公式来学习两者区别,这里有很篇很不错的文章比较直观的讲解了两者的区别和相似之处。

Lucene实现

Lucene内置了TF-IDF和BM25及其它的一些相关算法,并从6.0版本开始把默认的TF-IDF算法换成了BM25,这也说明了经过这些年的实践反馈BM25在文本检索场景表现得很好。

你也可以继承Similarity类或者SimilarityBase类编写自己的相关算法。

1
2
IndexSearcher searcher = new IndexSearcher(reader);
searcher.setSimilarity(new ClassicSimilarity());

猫友会其事

本无心插柳, 却慢慢有一定影响力,猫友会是一个邀请制的互联网优秀人才的交流平台, 以鄂籍或在鄂求学过的同学们为主。 目前在推进的一些事情:

  • 猫友会大讲坛,分享产品/技术/创业心得
  • 猫友信息平台,对接武汉最优秀的团队以及愿意回武汉的优秀人才。
  • 猫友公众号,优质原创产品/技术文章
  • 猫友读书会,阅读+思考+总结,筹备中

长按关注猫头鹰技术公众号(mtydev)

img

深入浅出搜索原理系列之(二)查询构建

上篇文章中我们了解了一个完整搜索系统的基本构建和运作流程,去掉细节不谈,最重要的两步就是:构建索引 和 执行查询。而本篇文章里我们比较系统的了解下查询的一些常用方法,及背后的大概原理。

从一个搜索系统用户的角度出来,打交道最多的就是查询。说到查询,大部分人觉得没什么,无非就是输入关键词并希望系统返回具有相关性的结果。一个查询系统其实提供了很多丰富的查询方式供我们使用,而我们大多数情况下只使用一些最基本的查询方法。这里以 Google 为例,查看它的帮助文档,发现查询本身也是一门技术活,了解更多的查询方法,可以帮助我们提高查询返回的准确率且平衡好召回率。

阅读全文

js设计模式系列之(三)命令模式

命令模式

望文生义,所谓的命令模式其实就是:
发出一定的指令,然后由对象接受并且执行

需要强调一点,就是对于命令的发出者来说,他并不知道该命令是给谁,执行效果是怎样,他只管发出命令就行。听到这里感觉和发布订阅者模式有异曲同工的效果。 但事实上,他们两者应用的场景还是有比较大的区分。不仅写法上有不同,而且执行的过程也有所不同。要知道在命令模式里面执行的效果是1对1,而在订阅者模式里面是1对>=1的.

你在逼逼什么?

哦,说明白一点。 就和上课一样。 老师进教室了,首先说:“上课!”. 接着,你们的monitor 会立马接上: “起立!”。 然后,你们就会异口同声的说:”老湿好~”。 没错,分析一下。 当老师说上课的时候,他并不会知道谁会说起立,比如今天班长谈恋爱去了,那副班长顶上。 而且,说完起立之后,副班长也不知道谁会说老湿好。 也就是命令的发出者,只管发出一个命令,然后你们只管执行就over了.

阅读全文

js设计模式系列之(二)订阅发布模式

订阅发布模式如果按数学翻译其实就是,一对多的映射关系。怎么解释呢? 就是一个开关,同时并联几个灯泡(在不同房间),触发的时候,几个灯泡都会得到指令,然后执行发光的行为。首先,这几个灯泡,并不知道我和哪些灯泡连在一起(其实,也不用知道),只需要你给一个按下开关的指令就over了。
懂么? 不懂~
行,大爷,我这还有一个栗子==>《收音机和电台的午夜故事》
午夜时分,电台正发送着无线电波(触发事件), 这时候小明,打开了收音机,拨到固定的频率(订阅事件), 突然,电台里响起了18岁少女般的声音(触发事件). 此时此刻,还有无数和小明一样,使用着收音机收听的人,但是他们之间相互都不认识。 只是他们都在听一个电台.

阅读全文

js设计模式系列之(一)请节约你的请求-代理模式

What’s the proxy pattern?

代理模式其实就是将违反单一性原则的类给抽离出来,尽量满足开放和封闭的原则。 相当于一个类的行为只是一种,但是你可以给这个类添加额外的行为。比如: 一个工厂制造伞,你可以给这个工厂设置一个代理,提供订单,运货,淘宝网店等多种行为。当然,里面还有最关键的一点就是,这个代理能把一些骗纸和忽悠都过滤掉,将最真实最直接的订单给工厂,让工厂能够放心的让工人加班,顺利的发年终奖.
!!!说人话:
就是将你的本体请求,放在代理的怀抱里,让他来帮你挡风挡雨。

阅读全文

猫队长读书系列之运营篇

在知识爆炸的互联网时代,精华内容是非常有价值的,猫队长花在阅读上的时间不少,所以想把最近半年的一些阅读做一些梳理,同时加上自己的一些理解,预计会有运营篇,产品篇,技术篇,创业篇,团队篇和神秘篇。之所以会从运营篇开始,是因为最近在这块花的学习时间较多。

为什么会有想法写这个系列? 纯粹的梳理会不会有拾人牙慧的感觉?最终决定写是因为被下面这段话打动.

既然觉得有用,那就开始吧.

阅读全文

分布式存储产品的测试实践及心得

背景介绍

这几年我一直从事分布式存储产品的测试开发工作,伴随着产品的第一次上线,第一次升级,一直到今天。期间参与发布了无数个版本,支持着海量的用户对我们存储产品的需求。
想写一篇文章,总结下自己的工作,记录工作中的一些心得。
如果有人能从中获得一些启发或者收获,那将是我莫大的荣幸。

主要讲几个方面:

  • 测试角色在整个分布式存储产品发展过程中的变化
  • 分布式存储产品的测试实践
  • 测试实践碰到的问题
  • 一点心得

阅读全文

猫友会大讲坛第1期 - 基于iOS逆向工程的微信机器人

猫友会大讲坛

猫友会大讲坛是“猫友会”开设的一个知识分享栏目,”知识分享,是能力的锻炼,双方都会有收获。只要真诚,只要是自己觉得好的东西,都可以来分享”,

所以欢迎大家踊跃报名,不限主题。

  • 本期内容:结合一个iOS微信机器人的实现,介绍iOS逆向工程相关的概念,工具等。
  • 策划:侠天
  • 编辑:刘子洋

“猫友会” 是什么?参看文章末的公众号.

阅读全文

大数据系列之(一) Streaming模式基础知识

译者摘要

现在大数据,云计算已经成为互联网的标配,但是现在主流的大数据处理依旧是使用batch模式,batch模式就是将数据按某种规则分成块,然后对整个块跑计算逻辑,缺点是延迟太高(至少是分钟),常用的工具就是Hadoop。在日益变化的需求面前,高延迟越来越不能忍受,因此Streaming模式应运而生,他最大的特点就是低延迟,最快能到毫秒级别,常用的Streaming工具主要是storm,spark等,但是这些工具都有各自的优缺点,功能上不能完全取代batch,这篇文章就是想深入分析什么样的Streaming系统能彻底替代batch,并最终打败batch。

阅读全文

游戏开发之状态机的实现与优化

引言

你是否还在面对乱作一团的代码束手无策?你是否仍然觉得复杂的逻辑无从下手?你是否觉得游戏AI高端得毫无头绪?本文将以一个复杂的弹窗逻辑和RPG游戏挂机AI的实现为案例,讲述状态机的概念及其写法。

本文分为以下部分:

  • 有限状态机(finite-state machine):对状态机一些概念的解释。
  • 案例对照:将一个复杂弹窗的普通写法和状态机编程两种实现进行对比。这里状态机的实现是多个if-else的最简单的状态机实现。
  • 有限状态机的优势:通过上面的对比总结状态机的优势。
  • 如何优雅地使用状态机:以游戏挂机自动刷怪的AI为例,提供状态模式的代码实现。
  • 状态机的使用场景:对状态机的使用做了一些扩充。
  • 总结:对本文内容的总结。
  • 参考资料:文中部分概念的来源以及扩展阅读的链接。

阅读全文

本站总访问量