Document ranking by contextual vectors from natural language query

A set of keywords is extracted from a query. Natural Language Processing (NLP) is performed on the query to extract a set of contextual words for a keyword from the query. For the query, a first score of a first vector is computed, where the first vector represents a first contextual word. For a first result in a result set, a first result score of a first result vector is computed, where the first vector represents a first result contextual word in a set of result contextual words corresponding to the keyword in the first result. Using the first score and the first result score, a first similarity value is computed for the first result. The first result is re-ranked relative to a second result according to the first similarity value for the first result and a second similarity value for the second result in the result set.

TECHNICAL FIELD

The present invention relates generally to a method, system, and computer program product for ranking documents in a corpus. More particularly, the present invention relates to a method, system, and computer program product for document ranking by contextual vectors from natural language query.

BACKGROUND

A corpus (plural: corpora) is data, or a collection of data, used in linguistics and language processing. A corpus generally comprises large volume of data, usually text, stored electronically. Hereinafter, unless expressly distinguished where used, a document comprises any data that is available as text, can be converted to text, or is recognizable as text, in some natural language, for the purposes of Natural Language Processing (NLP).

A natural language (NL) is a written or a spoken language having a form that is employed by humans for primarily communicating with other humans or with systems having a natural language interface. Thus, a document contemplated herein can be text, audio data that can be transcribed into text, video data from which textual description or transcription is possible, or some combination thereof.

NLP is a technique that facilitates exchange of information between humans and data processing systems. For example, one branch of NLP pertains to transforming human readable or human understandable content from a document into machine usable data. For example, NLP engines are presently usable to accept input content such as a newspaper article or human speech, and produce structured data, such as an outline of the input content, most significant and least significant parts, a subject, a reference, dependencies within the content, and the like, from the given content.

NLP employs techniques such as shallow parsing and deep parsing. Shallow parsing is a term used to describe lexical parsing of a given content using NLP. For example, given a sentence, an NLP engine determining what the sentence semantically means according to the grammar of the language of the sentence is the process of lexical parsing, to wit, shallow parsing. In contrast, deep parsing is a process of recognizing the relationships, predicates, or dependencies, and thereby extracting new, hidden, indirect, or detailed structural information from distant content portions in a given document or a corpus.

Generally, not all documents are equally important, relevant, or useful for a given purpose, or contain equally useful information. Document ranking is a known process of arranging documents in some order of relevance according to a given condition. One known method of document ranking arranges the documents based on the frequency of occurrence of a given word or phrase therein. For example, a search query for “zebra” might result in one hundred documents. These one hundred documents are ranked according to a number of times the word “zebra” appears in them. The highest ranking document will have the most occurrences of the word, and the last ranking document the least.

Another known method of document ranking orders the documents, where the order is indicative of a sentiment expressed in the documents. For example, a search query for “favorable impression of Florida vacation” might find ten documents that each discuss vacation experiences in Florida. These ten documents are ranked by a degree of positive sentiment expressed towards the experience of vacationing in Florida.

SUMMARY

The illustrative embodiments provide a method, system, and computer program product. An embodiment includes a method that extracts a set of keywords from a query. The embodiment performs, for a keyword in the set of keywords, Natural Language Processing (NLP) on the query to extract a set of contextual words from the query. The embodiment computes, for the query, using a processor and a memory, a first score of a first vector, wherein the first vector represents a first contextual word in the set of contextual words. The embodiment computes, for a first result in a result set, a first result score of a first result vector, wherein the first vector represents a first result contextual word in a set of result contextual words corresponding to the keyword in the first result. The embodiment computes, using the first score and the first result score, a first result similarity value for the first result. The embodiment re-ranks, according to the first result similarity value for the first result and a second result similarity value for a second result in the result set, the first result relative to the second result.

DETAILED DESCRIPTION

The illustrative embodiments recognize that the existing methods of document ranking are deficient in answering many natural language queries. For example, in one case, a user might specify an NL statement for a query, e.g., “I would like to eat a juicy apple” hoping to find information about a fruit that is juicy. The illustrative embodiments recognize that a presently available method for search and ranking of matching documents would include documents that reference references to “apple” without discriminating between document that discuss “apple” as a fruit or a company. Often, the result set returned by the search engines at the very least mix documents that contain the keywords but are irrelevant to the context in which the keyword is used, and the worst populate the highest ranks with documents that have nothing to do with the context of the keyword.

Such a manner of present document ranking is at least frustrating to the user if not entirely defeating the purpose of the search. The illustrative embodiments recognize that this problem is exacerbated when the search queries specified by the user are natural language queries instead of keywords-based queries.

An NL query is a query that takes the form of a spoken or written sentence in a natural language, not necessarily in the form of a question, and not necessarily specifying an intent to perform a search using the sentence. For example, the example sentence used above—“I would like to eat a juicy apple” is a natural language sentence according to the grammar of the English language, is not posed as a question, and may or may not have been typed into a search engine interface—e.g., may be a part of a written or oral conversation the user might be having online.

To be able to understand a portion of an NL conversation or a search query input in a natural language, and be able to search and order the contextually correct information is a difficult and complex computational problem that ordinary computers and presently available search engines are insufficient to solve. Within the scope of the illustrative embodiments, a portion of an NL audio, video, or textual data based on which an embodiment searches and ranks documents is referred to as an NL query, regardless of whether that portion is specified as a search query by the user.

A sentence that forms an NL query includes some keywords and some surrounding words. As a non-limiting example, in many cases according to the grammar of the English language, the keywords may be usually found in the subject or the object in a grammatical structure of the sentence, although the verb and other parts of the sentence (adverbs, adjectives, etc.) may also operate as a keyword under certain circumstances.

Some or all of the surrounding words in the NL query operate to provide context—a frame of reference—to one or more keywords in the NL query. More particularly, a context can be an intention, meaning, limit, definition, purpose, usage, or scope within which the user expects a keyword to operate. For example, in the above example NL query, “I would like to eat a juicy apple,” the intent of the user is directed at the fruit and not the company, and this context is communicated by the presence of words and phrases, such as “like to eat” and “juicy,” in the NL query.

These examples of the English language and the parts of speech where the keywords and context may be found are not intended to be limiting. From this disclosure, those of ordinary skill in the art will be able to conceive many other languages and parts of NL sentences in those languages from where keywords and contextual information may be extracted, and the same are contemplated within the scope of the illustrative embodiments.

A result set of a search can easily return thousands of documents. The illustrative embodiments recognize that analyzing each document in the result set for contextual relevance is computationally very expensive to the point of being prohibitive. An efficient manner of determining whether a document in a result set is contextually relevant to the NL query is therefore needed.

The illustrative embodiments recognize that the presently available tools or solutions do not address these needs or provide adequate solutions for these needs. The illustrative embodiments used to describe the invention generally address and solve the above-described problems and other problems related to document ranking by contextual vectors from natural language query.

An embodiment can be implemented as a software application. The application implementing an embodiment can be configured as a modification of an existing search engine or document ranking system, as a separate application that operates in conjunction with an existing search engine or document ranking system, a standalone application, or some combination thereof.

A result set can include complete documents, a summarized version of a document, or some combination of both. Hereinafter, unless expressly distinguished where used, a reference to a “result” in a result set is a reference to a document, a summary, or both, as the case may be with a particular result set, with a particular manner of operation of a search engine or search algorithm, or a particular implementation.

Techniques are available presently to vectorize words—i.e., to construct one or more vectors from one or more words, where a vector represents one or more words. Generally, a vector represents a word with a set of numeric values. Neural networks are known to be configurable for vectorizing words.

An embodiment uses NLP to parse an NL query into keywords and contextual words. An NL query may have one or more keywords each of which can have one or more contexts. One embodiment constructs multiple vectors using different combinations of contextual words or phrases, which are deemed valid contexts by an NLP engine.

An embodiment constructs a vector for each context that is found for a keyword. The contexts of one or more keywords can overlap with the contexts of one or more other keywords in the NL query. The embodiment scores a vector. A score of a vector is a numerical value resulting from applying a function to the numerical values of the vector.

An embodiment performs a search using the NL query. In one embodiment, the keywords from the NL query are sent to a pre-existing search engine. In another embodiment, the entire NL query is sent to the existing search engine. In yet another embodiment, a search algorithm implemented within the embodiment accepts the keywords only or the NL query as a search input.

An embodiment receives a result set in response to performing the search. A result may be included in the result set due to the search engine or search algorithm's determination that the result is relevant to some or all keywords that were used in the search.

An embodiment analyzes a result to detect the presence of a keyword therein. The embodiment analyzes the data surrounding the keyword in the result for determining the context of the keyword in the result. The surrounding data may appear before the keyword, after the keyword, or both. Furthermore, the surrounding data may be immediately adjacent to the keyword, or may be separated from the keyword by other data in the result. In some cases, the surrounding data, which is usable to provide context for a keyword in a result, may be located in another document that is distinct from the result and may or may not be included in the result set.

Additionally, no limit as to the size of the surrounding data, or the distance of the surrounding data from the keyword is implied or necessary for the illustrative embodiments. In one example case, the surrounding data may only be fragment of a sentence, whereas in other cases, the surrounding data may be one or more sentences, one or more paragraphs, or other similarly purposed language-specific structures.

Furthermore, all, some, or none of the keywords from the NL query may be present in a particular result; a keyword from the NL query may be present more or less number of times in a result as compared to in the NL query; a context of a keyword may be different in a result as compared to in the NL query; and the contexts of one or more keywords can overlap with the contexts of one or more other keywords in a result.

For a result, an embodiment constructs a vector for each context found for each keyword in the result. The embodiment scores each contextual vector constructed in this manner. The embodiment aggregates the scores of all contextual vectors for all keywords found in the result. Other results in the result set are processed in a similar manner.

An embodiment compares a context vector of a keyword from the NL query with one or more context vectors of the same or similar keyword from a result. The embodiment compares the vectors that step from the same or similar keywords in the NL query and the result, e.g., by comparing the vector scores but not being limited to that method of comparison. Through this comparison, the embodiment produces a similarity value for the result. Note that the scoring of vectors and comparing the scores is only one non-limiting example method for comparing vectors. Essentially, an embodiment operates to compare one or more vectors, separately or collectively, with one or more vectors of a result, separately or collectively. One embodiment uses a cosine similarity method for determining the similarity between the vectors.

From this disclosure, those of ordinary skill in the art will be able to conceive other ways of adapting an embodiment to compare word vectors of contextual information from an NL query with word vectors of contextual information from a result. Such adaptations are contemplated within the scope of the illustrative embodiments.

Regardless of the ranking assigned to the results by the search engine or search algorithm, an embodiment re-ranks selected results. The re-ranking of the results in the result set can be performed in different ways. One embodiment optionally selects those results from the result set whose similarity values exceed a similarity threshold. Another embodiment selects all the results in the result set.

An embodiment arranges, orders, or ranks the selected results according to their similarity values. For example, the selected result with the highest similarity value is ranked the highest, the selected result with the next highest similarity value is ranked next, and so on. The re-ranked selection of results is output to the user.

The manner of document ranking by contextual vectors from natural language query described herein is unavailable in the presently available methods. A method of an embodiment described herein, when implemented to execute on a device or data processing system, comprises substantial advancement of the functionality of that device or data processing system in computationally efficient re-ranking a result of a result set according to the contextual relevance of the result to the NL query provided by a user.

The illustrative embodiments are described with respect to certain types of searches, queries, words, phrases, contexts, grammars, languages, scores, ranks, thresholds, values, algorithms, search engines, documents, corpora, devices, data processing systems, environments, components, and applications only as examples. Any specific manifestations of these and other similar artifacts are not intended to be limiting to the invention. Any suitable manifestation of these and other similar artifacts can be selected within the scope of the illustrative embodiments.

Application105implements an embodiment described herein. Search engine107is an example search engine or search algorithm that is used for obtaining a result set as described herein. Search engine103may be a separate pre-implemented search engine or a search algorithm implemented in or with application105. Interface134is a user interface, which is usable to allow a user to input an NL query, to capture an NL query from a natural language conversation, and interact with application105such as to receive re-ranked results, as described herein.

With reference toFIG. 3, this figure depicts a block diagram of an example configuration for document ranking by contextual vectors from natural language query in accordance with an illustrative embodiment. Application302is an example of application105inFIG. 1. Interface304is an example of interface134inFIG. 1. Search engine306is an example of search engine107inFIG. 1.

Interface304supplies NL query NLQ to application302. Application302supplies query Q to search engine306, which obtains a result set from any number of data sources, such as data sources308,310, and312, over network314. Application302obtains result set R from search engine306. Query Q may be formed from NL query NLQ as described herein.

By processing result set R as described herein, application302produces contextually re-ranked result set CR

With reference toFIG. 4, this figure depicts a block diagram of a problem with prior-art search and document ranking that can be remedied using an illustrative embodiment. For example, search engine107operating alone and without the benefit of application105inFIG. 1would take keyword “apple” from query402: “I would like to eat a juicy apple” and construct search string404: “apple”. Searching using search string404, the search engine would produce result set406, which would include results408and410. Result408would be included in result set406because of text408A in result408including search string404. Result410would be included in result set406because of text410A in result408including search string404.

As a human can comprehend, result408is unhelpful in query402but result410is relevant to query402. If is quite likely that many more results similar to result408than result410exist in the result set. It is also likely that result408refers to “apple” numerous times in a manner similar to data408A. Disadvantageously, it is quite likely that result408ranks high—at or near the top—in result set406even though result408is unhelpful to the user.

With reference toFIG. 5, this figure depicts a block diagram of an example operation of a solution to the problem with prior-art search and document ranking in accordance with an illustrative embodiment. For example, application105inFIG. 1parses NL query402into keyword404and some contextual words. Keyword404supplied to search engine107produces result set406, which would include results408and410.

In addition, the application uses NLP analysis of NL query402to produce a set of vectors502,504,506,508, and510using contextual words extracted from NL query402. The application computes a score for each of vectors502,504,506,508, and510and performs vector aggregation as described herein.

Using NLP, the application analyzes data408A for contextual words and produces a set of contextual vectors512,514,516, and518. The application scores and aggregates vectors512,514,516, and518. Similarly, the application analyzes data410A for contextual words and produces a set of contextual vectors520,522,524, and526. The application scores and aggregates vectors520,522,524, and526.

The application performs an aggregated score comparison or another similarity analysis as described herein to determine a similarity value for result408and a similarity value for result410relative to the aggregated score of NL query402. The similarity value of result410being higher than the similarity value of result408, the application advantageously re-ranks result410higher than result408.

With reference toFIG. 6A, this figure depicts a block diagram of an application for document ranking by contextual vectors from natural language query in accordance with an illustrative embodiment. Application602can be used as application105inFIG. 1. NL query402is an example of NL query604.

Using an external NLP engine (not shown), or an implementation of an NLP engine (not shown) within application402, component608extracts keywords or key phrases from NL query604. Using NLP, component610extracts from NL query a set of one or more contextual words for each keyword or phrase. Component612constructs a vector for at least a subset of contextual words for a keyword or phrase. Component614scores the contextual word vectors.

Any number of keywords or phrases, or occurrences thereof, may be extracted from an NL query. Any number of contextual words may be associated with an occurrence of a keyword or phrase in the NL query. Any size or type of NL query may be processed in this manner.

Component618performs, or instructs a search engine to perform, a search using an extracted keyword or phrase. Using NLP, component620extracts a set of one or more contextual words for an occurrence of a keyword in a result in the result set of the search.

Component622constructs a vector for at least a subset of contextual words extracted for a keyword or phrase. Component624scores the contextual word vectors from the result.

Any number of keywords or phrases, or occurrences thereof, may be extracted from a result. Any number of contextual words may be associated with an occurrence of a keyword or phrase in the result. Any number of results may be processed in this manner.

Component628compares or otherwise determines the degree of similarity between the contextual vector scores of various results with the aggregated contextual vector score of NL query604. Component628computes a similarity value for at least a subset of the result set in this manner.

Depending upon the implementation, component630selects some results that have a similarity value exceeding a similarity threshold, or selects all results that have a similarity value. Component632re-ranks the selected results according to their respective similarity values. Application outputs contextual vector based re-ranked result set, or a portion thereof.

With reference toFIGS. 6B, and 6D, these figures depict an example operation for document ranking by contextual vectors from natural language query in accordance with an illustrative embodiment. An example NL query is depicted with example instances of keywords A, B, and C. Context vector formation is performed as described herein from the NL query for such keywords. An example result—“Document X” is obtained in response to a search. Keyword instances A and C are detected therein. Context vectors for the detected keyword instances are formed from the result, as described herein. Context vectors of the same or similar keywords are compared for similarities, and a document similarity score—Document X score—is computed in a non-limiting example manner, as described herein. The result—Document X—is then scored (not shown) using this score.

It is important to note that many techniques exist for using vectors to calculate similarity between a query and a document, e.g. doc2vec, tf-idf weighted sum of word2vec methods. However, disadvantageously, these techniques compare a single vector that represents an entire query with a single vector that represents an entire document. This type of coarse comparison is insufficient and inaccurate for determining contextual relevance of the results with an NL query. Single vector comparisons, as in these techniques, cannot detect subtle contextual nuances or phrase, especially when a result document, the NL query, or both exceed a certain size of complexity.

The illustrative embodiments construct detailed contextual vectors to compare detailed local information of an NL query and a result document. The illustrative embodiments generate context vector per keyword appearance and compute the vector similarity per context per keyword instance.

With reference toFIG. 7, this figure depicts a flowchart of an overall process for document ranking by contextual vectors from natural language query in accordance with an illustrative embodiment. Process700can be implemented in application602inFIG. 6.

The application accepts as input an NL query (block702). The application extracts a set of keywords or phrases from the NL query (block704). The application extracts a set of contextual words for a keyword or phrase and computes a context vector for each context word (block706). Block706repeats for as many keywords and their instances/occurrences as may have to be processed from the NL query.

The application submits all or a portion of the NL query for search (block708). The application extracts a set of keywords or phrases, and some or all instances thereof from a result (block710). The application computes a set of context vectors for the extracted keywords/phrases and their instances (block712). Blocks710and712repeat for as many results as may have to be processed in this manner.

The application computes vector scores for the context vectors in the results of the result set (block714). The application computes aggregate scores and contextual vectors based similarly values for the results (block716). The application selects at least some of the results, and re-ranks the selected results according to their similarity values (block718). The application outputs the contextual vector based re-ranked results to the user (block720). The application ends process700thereafter.

With reference toFIG. 8, this figure depicts an example manner of vectorizing contexts of words in a NL query in accordance with an illustrative embodiment. Process800is a non-limiting method of vectorization, and can be implemented as blocks706and712inFIG. 7.

The application extracts, e g, through NLP, a context that relates to a keyword in an NL query (block802). The application computes and aggregates scores of vectors of words that are contextually near or related to a keyword in the NL query (block804). If more contexts exist for the keyword for which word vectors and their scores have to be computed (“Yes” path go block806), the application returns process800to block802. If no more contexts exist for the keyword for which word vectors and their scores have to be computed (“No” path go block806), the application ends process800thereafter.

With reference toFIG. 9, this figure depicts a flowchart of an example process for computing a similarity value of a result in accordance with an illustrative embodiment. Process900can be implemented as block716inFIG. 7.

The application initializes a similarity value of a result (block902). If no contextual scores for any keywords instances in the result remain to be evaluated (“No” path of block904), the application sums up all the max-similarity values computed thus far in through process900for any keywords (block904A). The application ends process900thereafter. If at least some contextual scores for some keywords instances in the result remain to be evaluated (“Yes” path of block904), the application selects a keyword (block905). The application initializes a max_similarity value for the keyword (block906).

If no contextual vector exists in the result that matches, at least within a tolerance, with a contextual vector in the NL query (“No” path of block908), the application returns to block904.

If a contextual vector exists in the result that matches, at least within a tolerance, with a contextual vector in the NL query (“Yes” path of block908), the application calculates a similarity between the vectors (block910). If the calculated similarity value is greater than the max_similarity value (“Yes” path of block912), the application sets the max_similarity value to the calculated similarity value (block914), and returns to block908. If the calculated similarity value is not greater than the max_similarity value (“No” path of block912), the application returns to block908.

Thus, a computer implemented method, system or apparatus, and computer program product are provided in the illustrative embodiments for document ranking by contextual vectors from natural language query and other related features, functions, or operations. Where an embodiment or a portion thereof is described with respect to a type of device, the computer implemented method, system or apparatus, the computer program product, or a portion thereof, are adapted or configured for use with a suitable and comparable manifestation of that type of device.