III: Small: Matching and Ranking via Proximity Graphs: Applications to Question Answering and Beyond

III：小：通过邻近图进行匹配和排名：在问答及其他领域的应用

• 批准号: 1618159
• 负责人: Eric Nyberg
• 金额: $ 49.85万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618159&HistoricalAwards=false
• 关键词: III; Small; Matching; Ranking; via

This project will explore novel alternatives to a classic term-based full-text search, which is one of the most widely used computer algorithms. The current full-text search approaches heavily rely on memorizing which words and phrases appear in which text documents. The proposed research, in contrast, will examine methods that deviate from this well-studied path by using more generic similarity search methods. In doing so, the proposed research will pursue the following two objectives: (1) mitigating limitations of the existing approaches such as the mismatch between words that appear in queries and documents; and (2) developing approaches that permit an efficient separation of labor between data scientists and designers of retrieval algorithms. The latter would allow data scientists to focus on development of effective similarity models without worrying too much about low-level performance issues, while designers of retrieval algorithms and software engineers will be able to focus on development of more efficient and/or scalable approaches having fewer concerns about quality of results.The proposed research will investigate at least two scenarios where a term-based full-text search is replaced with a more generic high-accuracy k-nearest (k-NN) neighbor search. In the first scenario, it will develop a similarity function that goes beyond pure lexical matching and takes into account distributional similarity, similarity learned from a parallel (monolingual) corpus, and so on. In this scenario, the similarity function will be used as a black-box function coupled with a generic similarity search engine, implemented as a part of the Non-Metric Space Library (NMSLIB). Several search algorithms will be explored. One of the search approaches will rely on building a proximity graph (also known as a neighborhood graph), where nodes are objects and similar nodes are connected by edges. In the second scenario, the proposed research will build a pseudo inverted file over super terms. Super terms are (dense or sparse) vectorial representations of words appearing within a sliding window of small size. The super terms form a pseudo-vocabulary that can be indexed using a proximity graph (or any other efficient k-NN search method). At query time, the super terms will be extracted from the query and matched against the pseudo-vocabulary to obtain k nearest super terms (as well as documents where they occur). This approach will incorporate term proximity and term similarity (the latter will make the approach less affected by the vocabulary mismatch). Because preliminary experiments demonstrated that proximity graphs are not sufficiently accurate and efficient for the task in hand, the proposed research will also attempt to develop better variants of the proximity graphs methods. Should such an improvement fail, alternative search methods will also be explored. Experimental insights, algorithmic improvements, and new challenging datasets (resulting from the proposed work) will advance the state of the art in k-NN search, which is another widely used method. This, in turn, will benefit a variety of other NLP tasks such as classification, dictionary-based entity detection, and first story detection, which all heavily relying on the k-NN search. Additional project information will be made available at the project website: http://www.lti.cs.cmu.edu/PGraph

这个项目将探索传统的基于术语的全文搜索的新替代方案，这是最广泛使用的计算机算法之一。当前的全文搜索方法严重依赖于记住哪些单词和短语出现在哪些文本文档中。相比之下，拟议的研究将通过使用更通用的相似性搜索方法来研究偏离这一研究路径的方法。在此过程中，拟议的研究将追求以下两个目标：（1）减轻现有方法的局限性，例如查询和文档中出现的单词之间的不匹配;（2）开发允许数据科学家和检索算法设计者之间有效分离的方法。后者将使数据科学家能够专注于开发有效的相似性模型，而无需过多担心低级别的性能问题，而检索算法的设计者和软件工程师将能够专注于开发更有效和/或可扩展的方法，对结果质量的关注较少。文本搜索被更通用的高精度k-最近（k-NN）邻居搜索所取代。在第一种情况下，它将开发一个相似性函数，超越纯粹的词汇匹配，并考虑到分布相似性，从平行（单语）语料库中学习的相似性，等等。在这种情况下，相似性函数将被用作黑盒函数，与通用相似性搜索引擎相结合，作为非度量空间库（NMSLIB）的一部分实现。将探讨几种搜索算法。其中一种搜索方法将依赖于构建一个邻近图（也称为邻域图），其中节点是对象，相似的节点由边连接。在第二种情况下，所提出的研究将建立一个伪倒排文件的超级条款。超级术语是出现在小尺寸滑动窗口内的单词的（密集或稀疏）矢量表示。超级术语形成了一个伪词汇表，可以使用邻近图（或任何其他有效的k-NN搜索方法）进行索引。在查询时，将从查询中提取超级术语，并与伪词汇表进行匹配，以获得k个最近的超级术语（以及它们出现的文档）。这种方法将结合术语接近度和术语相似度（后者将使该方法受词汇不匹配的影响较小）。由于初步的实验表明，接近图是不够准确和有效的手头的任务，拟议的研究还将尝试开发更好的变体的接近图方法。如果这种改进失败，还将探索其他搜索方法。实验见解、算法改进和新的具有挑战性的数据集（由拟议的工作产生）将推进k-NN搜索的最新技术水平，这是另一种广泛使用的方法。反过来，这将有利于各种其他NLP任务，如分类，基于字典的实体检测和第一个故事检测，这些都严重依赖于k-NN搜索。更多的项目信息将在项目网站上提供：http://www.lti.cs.cmu.edu/PGraph