信息检索

信息检索(IR)是基于用于查询检索信息的任务。流行的信息检索模型包括布尔模型、向量空间模型、概率模型和语言模型。信息检索最典型和最常见的应用是搜索引擎。

来源:机器之心
简介

信息检索(IR)是基于用于查询检索信息的任务。流行的信息检索模型包括布尔模型、向量空间模型、概率模型和语言模型。信息检索最典型和最常见的应用是搜索引擎。

术语信息检索的含义可以是非常广泛的。作为一个学术研究领域,信息检索可能如此定义:

信息检索(IR)是从集合(通常存储在计算机中)中找到满足信息需求的非结构化性质(通常是文本)的材料(通常是文档)。

IR还可以涵盖超出上述核心定义所指定的其他类型的数据和信息问题。术语“非结构化数据”是指没有明确的、语义上明显的、易于计算机操作的结构的数据。这与结构化数据相反——其典型例子是关系数据库——这种结构化数据通常用于维护产品库存和人员记录。实际上,几乎没有数据真正是“非结构化”的。IR还用于简化“半结构化”搜索,例如查找标题包含Java并且主体包含线程的文档。

信息检索领域还包括支持用户浏览或过滤文档集合或进一步处理一组检索到的文档。给定一组文档,聚类就是根据其内容对文档进行很好的分组。这与根据主题将在书架上书籍分类类似。

信息检索系统也可以根据它们的操作范围来区分,根据这三个不同的范围系统需要满足不同的要求。在网络搜索中,系统必须提供对数百万计算机上存储的数十亿文件的搜索。因此一个重要的问题是需要建立索引文件、建立能够在这个巨大规模下高效工作的系统、以及处理网络的特定方面,例如利用超文本,而不是被网站提供商在试图操纵页面内容时所迷惑并错误地提高他们的搜索引擎排名。另一个极端是个人信息检索。在过去的几年中,消费者操作系统集成了信息检索功能(如Apple的Mac OS X Spotlight或Windows Vista的即时搜索)。电子邮件程序通常不仅提供搜索,而且还提供文本分类:它们至少提供垃圾邮件(垃圾邮件)过滤器,并且通常还提供手动或自动手段来分类邮件,以便将其直接放置到特定文件夹中。这项任务带来的要求是轻量化以及软件免费化。在这两者之间是企业、机构和域特定搜索(domain-specific search)——即第三类范围。在这种情形下信息检索技术需要为诸如公司内部文档、专利数据库或生物化学研究文章等集合提供检索。

[描述来源:Manning, C. D.; Raghavan, P. and Schütze, H.(2008). Introduction to Information Retrieval, Cambridge University Press.]

发展历史

数百年来,存储和检索书面信息的需求变得越来越重要,特别是在纸张和印刷机等发明之后。计算机发明后不久,人们意识到它们可用于存储和机械检索大量信息。1945年,Vannevar Bush发表了一篇题为“ As We May Think”的突破性文章,它催生了自动获取大量存储知识的想法。1948年,Univac 诞生,这是最早的基于计算机的搜索系统。1950年,Calvin Mooers首先使用了「信息检索(Information Retrieval)」这个名词。1957年Hans Peter Luhn 他提出用单词作为索引单位来检索文档和单词重叠作为检索的标准。

IR领域的几项重要发展发生在20世纪60年代。1960年,Melvin Earl (Bill)Maron 和 J. L. Kuhns 发表《关于相关性、概率索引和信息检索(On relevance, probabilistic indexing, and information retrieval)》,提供了一种在机械化(自动化)图书馆系统中进行文献索引和检索的新技术。1962年,Cyril W. Cleverdon的《关于索引系统相对效率调查的测试和分析报告(Report on the Testing and Analysis of an Investigation into the Comparative Efficiency of Indexing Systems)》 介绍了用于信息检索的评估模型。1963年左右,国家医学图书馆开发了MEDLARS医学文献分析和检索系统,这是第一个机器可读数据库和批量检索系统。

在这些工作中最引人注目的是Gerard Salton及其学生首先在哈佛大学和后来在康奈尔大学开发的SMART系统,为信息检索领域引入了大量概念,包括向量空间模型、相关性反馈、Rocchio模型等;以及由克里菲尔德航空学院的Cyril Cleverdon和他的团队在他1962年文章之上所完成的Cranfield测试。由Cranfield测试为基础所开发的检索系统评估方法在今天的IR系统中仍在使用。另一方面,SMART系统允许研究人员试验想法以提高搜索质量。实验系统与良好的评估方法相结合,使得该领域的快速发展,并为许多关键的发展铺平了道路。

1968年,J. W. Sammon 正式发表向量模型,《关于信息存储和检索的一些数学分析(Some Mathematics of Information Storage and Retrieval)》。该报告解释了当时正在使用的一些数学技术以及正在考虑用于解决信息存储和检索问题的一些技术。 文章主要讨论了两个问题:第一个是统计描述,另一个是向量空间表征。 第二年,Sammon的《一种用于数据结构分析的非线性映射(A nonlinear mapping for data structure analysis)》 提出了信息检索系统的可视化接口,他使用了多元数据分析算法来实现基于从L空间到较低维空间的N个L维矢量的点映射来近似保留固有数据“结构”的想法。1971年,MEDLINE (MEDLARS 的在线版本)发布。1972年,Luhn 和 Sparck Jones 提出 TF-IDF。这是一种常用加权技术。tf-idf是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降。直到目前tf-idf加权的各种形式仍然常被搜索引擎应用,作为文件与用户查询之间相关程度的度量或评级。

1975年,Salton 发表了三篇该领域的重要论文:1.《一种索引理论(A Theory of Indexing)》 ;2.《一种自动文本分析中项重要性理论(A theory of term importance in automatic text analysis )》;3.《一种用于自动索引的向量空间模型(A vector space model for automatic indexing)》 。在第二篇文章中他提出了称为判别价值分析(discrimination value analysis)的新技术,该方法根据文本词语能够区分一个集合内的文件的程度来对文本词语排序。在第三篇文章中,他则提出了向量空间模型。这是一个把文本文件表示为标识符(比如索引)向量的代数模型。他是基于线性代数的简单模型,允许根据文档间可能的相关性来进行排序同时允许局部匹配。这三篇文章对IR领域造成了巨大的影响。

1978年,第一届 ACM SIGIR 会议举办。1979年,van Rijsbergen,Robertson, Porter提出 Porter stemmer,又称Porter stemming算法,是一个从英语单词中去除平常词形态和不完全结尾的过程。 它主要用在建立信息检索系统时需要完成的术语标准化过程中。英国科学家Tim Berners-Lee于1989年发明了万维网。1990年他在瑞士CERN的工作期间编写了第一个网页浏览器。网页浏览器于1991年在CERN向外界发表,1991年1月开始发展到其他研究机构,1991年8月在互联网上向公众开放。万维网的出现使信息的数量和流通速度都取得了突破,也更凸显了IR技术的重要性。然而,由于缺乏大型文本集的可用性,当时所提出模型和技术能否扩展到更大的语料库这个问题仍然没有得到答案。这一情形 1992年随着文本检索会议(TREC)的启动而发生了变化。TREC是由NIST主持的各种美国政府机构主办的一系列评估会议,旨在鼓励从大型文本集合中对IR进行研究。差不多在同一时期,Stephen E. Robertson等学者提出 BM25。这是在信息检索系统中根据提出的query对document进行评分的算法。BM25算法首先由OKapi系统实现,所以又称为OKapi BM25。也是在这一时间,Norbert Fuhr 提出了 learn2rank 的一般思想。

另外两个在IR领域有重要影响的算法是HITS算法和PageRank算法。Larry Page 和 Sergey Brin 于1996年开发出 PageRank,这是一种用于客观地对网页进行评级的方法,可有效衡量人类对其的兴趣和关注,这也是Google算法的重要内容。HITS 算法则是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。在这一时期的研究中,信息检索技术逐渐开始使用语言模型并且取得了不少技术上的突破。进入各种21世纪以来,不同平台开始广泛应用搜索引擎,并且单纯的搜索已经可以取得很不错的结果,搜索工作开始向更加精准的问答系统转移。如卡内基梅隆大学和谷歌大脑的研究者在2018年提出的新型问答模型 QANet,仅使用神经网络中的卷积和自注意力机制,性能大大优于此前最优的模型。另外一个不得不提的算法是word2vec,为一群用来产生词向量的相关模型。这些模型为双层的浅层神经网络。训练完成之后,word2vec模型可将每个词映射到一个向量,可用来表示词对词之间的关系。

我们将信息检索划入社会影响阶段,因为它通过搜索引擎等应用已经在我们的日常生活中实现了普及并具有显著的影响力,它已经是互联网时代每位网民都会用到的背景技术。

主要事件

年份事件相关论文/Reference
1945Vannevar Bush发表了一篇题为“ As We May Think”的突破性文章,它催生了自动获取大量存储知识的想法Bush, V. (1945).As We May Think. Atlantic Monthly, 176:101–108.
1948Univac (最早的基于计算机的搜索系统)诞生Mander, M. (1983). From ENIAC to UNIVAC: An Appraisal of the Eckert-Mauchly Computers by Nancy Stern. Technology and Culture, 24(1), 148-150.
1957Hans Peter Luhn 提出用单词作为索引单位来检索文档和单词重叠作为检索的标准Luhn, H. P. (1957). A statistical approach to mechanized encoding and searching of literary information. IBM Journal of Research and Development.
1960Melvin Earl (Bill)Maron 和 J. L. Kuhns 发表《关于相关性、概率索引和信息检索(On relevance, probabilistic indexing, and information retrieval)》Maron, M. E.; Kuhns, J. L. (1960). On relevance, probabilistic indexing, and information retrieval. Journal of the ACM (JACM). 7(3): 216-244.
1962Cyril W. Cleverdon的《关于索引系统相对效率调查的测试和分析报告(Report on the Testing and Analysis of an Investigation into the Comparative Efficiency of Indexing Systems)》 介绍了用于信息检索的评估模型Cleverdon, C. W. (1962). Report on the Testing and Analysis of an Investigation into the Comparative Efficiency of Indexing Systems.
1963/1964第一个机器可读的数据库和批处理检索系统 MEDLARS (医学文献分析与检索系统)诞生Charles, J. A. (1968). MEDLARS, 1963-1967. ERIC.
20世纪60年代康奈尔大学开发了 SMART 信息检索系统,为信息检索领域引入了大量概念,包括向量空间模型、相关性反馈、Rocchio模型等Salton, G. (1971). The SMART Retrieval System—Experiments in Automatic Document Retrieval. Prentice Hall Inc., Englewood Cliffs, NJ.
1968J. W. Sammon 正式发表向量模型,《关于信息存储和检索的一些数学分析(Some Mathematics of Information Storage and Retrieval)》Sammon, J. W. (1968).Some Mathematics of Information Storage and Retrieval.
1969Sammon的《一种用于数据结构分析的非线性映射(A nonlinear mapping for data structure analysis)》 提出了信息检索系统的可视化接口Sammon, J. W. (1969).A Nonlinear Mapping for Data Structure Analysis.IEEE Transactions on Computers. 18(5): 401-409.
1972Luhn 和 Sparck Jones 提出 TF-IDFJones, K. S. (1972). A Statistical Interpretation of Term Specificity and Its Application in Retrieval. Journal of Documentation. 28: 11–21.
1975Salton 发表了三篇该领域的重要论文:1.《一种索引理论(A Theory of Indexing)》 ;2.《一种自动文本分析中项重要性理论(A theory of term importance in automatic text analysis )》;3.《一种用于自动索引的向量空间模型(A vector space model for automatic indexing)》Salton, G. , Yang, C. S. and Yu, C. T. (1975), A theory of term importance in automatic text analysis. J. Am. Soc. Inf. Sci., 26: 33-44.//Salton, G.; Wong, A. and Yang, C. S. (1975), A Vector Space Model for Automatic Indexing. Communications of the ACM, 18(11): 613–620.
1979受 Van Rijsbergen 影响,信息检索开始关注概率模型;提出 Porter stemmervan Rijsbergen, C. J.; Robertson, S. E. and Porter, M. F. (1980).New models in probabilistic information retrieval. Program. 14(3): 130-137.
20世纪90年代Stephen E. Robertson 提出 BM25Robertson, S. E.; Walker, S.; Jones, S. (1994). Okapi at TREC-3. Proceedings of the Third Text REtrieval Conference (TREC 1994). Gaithersburg, USA.
1996Larry Page 和 Sergey Brin 开发出 PageRank (用做谷歌的搜索算法)Page, L. (1998). The pagerank citation ranking : bringing order to the web. Stanford Digital Libraries Working Paper, 9(1), 1-14.
1999Jon Kleinberg 博士正式提出HITS算法Kleinberg, J, (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM. 46 (5): 604–632.
2013Tomas Mikolov等谷歌研究者开发出 word2vecMikolov, T. et al. (2013). Efficient Estimation of Word Representations in Vector Space. arXiv:1301.3781
2018卡内基梅隆大学和谷歌大脑的研究者提出 QANetYu, A. W. et al. (2018).QANET: COMBINING LOCAL CONVOLUTION WITH GLOBAL SELF-ATTENTION FOR READING COMPREHENSION. ICLR.

发展分析

瓶颈

不同的公司、组织或联盟分割或限制了数据库和信息的访问权限。另外,用户隐私对于信息检索也是一个敏感的话题——如何在提供信息检索的便利的同时,确保用户隐私得到有效脱敏和保护是当前研究的热点问题。

未来发展方向

  • 高水平的语义理解可能会实现在检索用的查询或需求的构建上,这样用户就无需过多思考他们输入的短语了。
  • 可以期待未来将能无限制地访问所有存在的数据库或信息,从而形成一个统一的信息检索系统/搜索引擎。
  • 除了简单地呈现一个排序后的列表,信息检索的结果可能还有更加智能的呈现方式。
  • 可以期待信息检索与机器人和语音识别等其它技术的结合。(最近的一个例子是 IRGAN,将生成对抗网络用于信息检索。)
  • 智能问答系统的发展带来的更简单、更个性化的搜索体验。

Contributor:Yuanyuan Li Mos Zhang

相关人物
托马斯米科洛夫
托马斯米科洛夫
Word2vec为托马斯·米科洛夫(Tomas Mikolov)在Google带领的研究团队创造。该算法渐渐被其他人所分析和解释。Tomas Mikolov是一位产出多篇高质量paper的学者,从RNNLM、Word2Vec再到最近流行的FastText都与他息息相关。一个人对同一个问题的研究可能会持续很多年,而每一年的研究成果都可能会给同行带来新的启发。
万尼瓦尔·布什
万尼瓦尔·布什
1890-1974,美国工程师、发明家。于二战期间为曼哈顿计划发挥了巨大的政治作用。写了《科学,无尽的边疆》(Science, the Endless Frontier)一文给小罗斯福总统,建议美国政府大力支持科学研究,而且政府不需自己设立研究机构,只需提供研究经费,让大学和私人企业依照研究表现来竞争政府的研究经费。此后美国政府提供的科学研究经费大幅增加,研究成果也很杰出,成为全球科技第一的国家。他在一篇文章中提出Memex概念,可以被看成为是现代万维网的先锋。
杰佛瑞·艾德盖尔·迪恩/杰夫·迪恩
杰佛瑞·艾德盖尔·迪恩/杰夫·迪恩
计算机科学家与软件工程师。现为Google公司员工,在谷歌的成长过程中,他设计和实现了支撑谷歌大部分产品的许多分布式计算基础设施。曾参与开发BigTable、MapReduce等产品,也是TensorFlow的作者之一。Jeff Dean联合创建和领导了谷歌大脑团队,2018年4月起担任谷歌人工智能部分的领导人。
Stephen E. Robertson
Stephen E. Robertson
Melvin Earl (Bill) Maron
Melvin Earl (Bill) Maron
C. J. “Keith” van Rijsbergen
C. J. “Keith” van Rijsbergen
西里尔·克利夫尔登
西里尔·克利夫尔登
英国图书管理员和计算机科学家,以其在信息检索系统评估方面的工作而闻名。
John W. Sammon
John W. Sammon
拉里·佩奇
拉里·佩奇
美国计算机科学家和互联网企业家,1998年与谢尔盖·布林创造了Google,现为Alphabet公司CEO。他是Google最著名的搜索排名算法发明者,2004年获得马可尼奖。
杰拉德·索尔顿
杰拉德·索尔顿
哈佛大学应用数学博士,“信息检索之父”。1965年,他加入康奈尔大学担任计算机科学教授并共同创立了该校的计算机科学系。他在康奈尔大学的团队开发了智能信息检索系统(SMART Information Retrieval System),是第一个使用现在流行的向量空间模型进行信息检索的系统。
Hans Peter Luhn
Hans Peter Luhn
IBM计算机科学、图书馆和信息科学领域的研究员,也是Luhn算法、KWIC(上下文关键词)索引和信息选择性传播(SDI)的创造者。他的发明已经在计算机科学、纺织工业、语言学和信息科学等不同领域得到应用。他获得了80多项专利。
乔恩·克莱因伯格
乔恩·克莱因伯格
Jon Kleinberg(乔恩·克莱因伯格,1971-)是美国计算机科学家,康奈尔大学计算机科学教授,于2006年获得国际数学联盟的Nevanlina奖。Kleinberg以解决重要和实际问题以及发现深刻的数学思想而闻名。 他的研究范围从计算机网络到数据挖掘到生物结构比较。 他最着名的成就是“小世界理论”和万维网搜索算法。 他设计了HITS算法,该算法的相关研究工作激发了Google的PageRank算法的诞生。
简介
相关人物