Relevancy ranking using statistical ranking, semantics, relevancy feedback and small pieces of text

Abstract

Search system and method for retrieving relevant documents from a text data base collection comprised of patents, medical and legal documents, journals, news stories and the like. Each small piece of text within the documents such as a sentence, phrase and semantic unit in the data base is treated as a document. Natural language queries are used to search for relevant documents from the data base. A first search query creates a selected group of documents. Each word in both the search query and in the documents are given weighted values. Combining the weighted values creates similarity values for each document which are then ranked according to their relevant importance to the search query. A user reading and passing through this ranked list checks off which documents are relevant or not. Then the system automatically causes the original search query to be updated into a second search query which can include the same words, less words or different words than the first search query. Words in the second search query can have the same or different weights compared to the first search query. The system automatically searches the text data base and creates a second group of documents, which as a minimum does not include at least one of the documents found in the first group. The second group can also be comprised of additional documents not found in the first group. The ranking of documents in the second group is different than the first ranking such that the more relevant documents are found closer to the top of the list.

Claims

I claim:

1. A method for retrieving relevant text data from a text database collection in a computer without annotating, parsing or pruning the text database collection, comprising the steps of:

(a) searching a text database collection in a computer using a first search query of natural language to retrieve a first group of selected small pieces of text, where each of the selected small pieces of text corresponds to a document;

(b) ranking each of the selected small pieces of text into a first ranked list of relevant documents;

(c) applying feedback information based on a manual determination of the relevancy of each of the selected small pieces of text in the first ranked list to automatically create a second search query, the second search query being different than the first search query;

(d) repeating steps (a) to (b) to form a second ranked list, wherein the second ranked list includes a second group of selected small pieces of text, and the second group is different than the first group.

2. The method for retrieving relevant text data of claim 1, wherein each of the small pieces of text includes at least one of:

a sentence, a phrase, and a semantic unit.

3. The method for retrieving relevant text data of claim 1, wherein the second search query includes:

at least one less word from the first search query.

4. The method for retrieving relevant text data of claim 1, wherein the second search query includes:

at least one additional word to the first search query.

5. The method for retrieving relevant text data of claim 1, wherein the second group includes:

at least one less document that had been listed in the first group.

6. The method for retrieving relevant text data of claim 1, wherein the second group includes:

at least one additional document that was not found in the first group.

7. The method for retrieving relevant text data of claim 1, wherein the second ranked list includes:

a different ranked order of documents than the first ranked list.

8. A method for retrieving relevant text data from a text database collection in a computer without annotating, parsing or pruning, comprising the steps of:

(a) searching a text database collection in a computer using a first search query to retrieve a first group of selected small pieces of text, where each of the selected small pieces of text corresponds to a document;

(b) semantically weighting the selected small pieces of text to form document weighted values for each of the selected small pieces of text in the first group;

(c) semantically weighting the first search query to form query weighted values;

(d) combining the query weighted values and the document weighted values to form similarity values for each of the selected small pieces of text;

(e) ranking the similarity values for each of the selected small pieces of text to form a first ranked list;

(f) automatically updating the first search query into a second search query based on feedback information on whether documents in the first ranked list are relevant,

(g) repeating steps (a) to (e) to form a second ranked list, wherein the second ranked list includes a second group of selected small pieces of text which is different than the first group.

9. The method for retrieving relevant text data of claim 8, wherein each of the small pieces of text includes at least one of:

a sentence, a phrase, and a semantic unit.

10. A method for retrieving relevant text from a text database collection in a computer without annotating, parsing or pruning the text database collection, comprising the steps of:

(a) searching a text database collection in a computer using a first search query to retrieve a first group of selected text;

(b) ranking each of the selected text to form a first ranked list;

(c) determining relevancy of each of the selected text with a manual pass-through of the first ranked list; and

(d) automatically updating the first search query based on the relevancy determination of the manual pass-through into a second search query, the second search query being different than the first search query; and

(e) searching the text database collection using the second search query to retrieve a second group of selected text being different than the first group.

Description

BACKGROUND AND PRIOR ART

Locating information using large amounts of natural language documents (referred to often as text data) is an important problem. Current commercial text retrieval systems generally focus on the use of keywords to search for information. These systems typically use a Boolean combination of keywords supplied by the user to retrieve documents. See column 1 for example of U.S. Pat. No. 4,849,898, which is incorporated by reference. In general, the retrieved documents are not ranked in any order of importance, so every retrieved document must be examined by the user. This is a serious shortcoming when large collections of documents need to be searched. For example, some data base searchers start reviewing displayed documents by going through some fifty or more documents to find those most applicable.

Statistically based text retrieval systems generally rank retrieved documents according to their statistical similarity to a user's search request (referred to often as the query). Statistically based systems provide advantages over traditional Boolean retrieval methods, especially for users of such systems, mainly because they allow for natural language input.

A secondary problem exists with the Boolean systems since they require that the user artificially create semantic search terms every time a search is conducted. This is a burdensome task to create a satisfactory query. Often the user will have to redo the query more than once. The time spent on this task is quite burdensome and would include expensive on-line search time to stay on the commercial data base.

Using a list of words to represent the content of documents is a technique that also has problems of it's own. In this technique, the fact that words are ambiguous can cause documents to be retrieved that are not relevant to the search query. Further, relevant documents can exist that do not use the same words as those provided in the query. Using semantics addresses these concerns and can improve retrieval performance. Prior art has focussed on processes for disambiguation. In these processes, the various meanings of words (also referred to as senses) are pruned (reduced) with the hope that the remaining meanings of words will be the correct one. An example of well known pruning processes is U.S. Pat. No. 5,056,021 which is incorporated by reference.

However, the pruning processes used in disambiguation cause inherent problems of their own. For example, the correct common meaning may not be selected in these processes. Further, the problems become worse when two separate sequences of words are compared to each other to determine the similarity between the two. If each sequence is disambiguated, the correct common meaning between the two may get eliminated.

The inventor of the subject invention has used semantics to avoid the disambiguation problem. See U.S. patent application Ser. No. 08/148,688 filed on Nov. 5, 1993 which issued as U.S. Pat. No. 5,576,954 on Nov. 19, 1996. For semantics, the various meanings of words are not pruned but combined with the various meanings of other words and the statistically common meanings for small groups of words yield the correct common meaning for those words. This approach has been shown to improve the statistical ranking of retrieved information. In the semantic approach, the prunning process for common meaning is replaced by a statistical determination of common meaning. Crucial to this approach is the fact that retrieval documents must be small.

Relevance feedback has sometimes been used to improve statistical ranking. For relevance feedback, the judgements of the user concerning viewed information are used to automatically modify the search for more information. However, in relevance feedback, conventional IR (Information Retrieval) systems have a limited recall. G. Salton, Automatic Information Organization and Retrieval, McGraw-Hill, 1968. This limited recall causes only a few relevant documents are retrieved in response to user queries if the search process is based solely on the initial query. This limited recall indicates a need to modify (or reformulate) the initial query in order to improve performance. During this reformulation, it is customary to have to search the relevant documents iteratively as a sequence of partial search operations. The results of earlier searches can be used as feedback information to improve the results of later searches. One possible way to do this is to ask the user to make a relevance decision on a certain number of retrieved documents. Then this relevance information can be manually used to construct an improved query formulation and recalculate the similarities between documents and query in order to rank them. This process is known as relevance feedback.

A basic assumption behind relevance feedback is that, for a given query, documents relevant to it should resemble each other in a sense that they have reasonably similar keyword content. This implies that if a retrieved document is identified as relevant, then the initial query can be modified to increase its similarity to such a relevant document. As a result of this reformulation, it is expected that more of the relevant documents and fewer of the nonrelevant documents will be extracted. The automatic construction of an improved query is actually straightforward, but it does increase the complexity of the user interface and the use of the retrieval system, and it can slow down query response time. Essentially, document information viewed as relevant to a query can be used to modify the weights of terms and semantic categories in the original query. A modification can also be made using documents viewed as not relevant to a query.

The main problems with using relevance feedback are many. First, the original query becomes very large whenever all the words in a viewed relevant document are added to the original query. Secondly, it takes a long time to read large documents and decide if they are relevant or not. Another problem is that often only part of a large document is actually relevant. Other patents have tried to address this problem. See U.S. Pat. No. 5,297,027 to Morimoto et al.

The inventor is not aware of any prior art that combines statistical ranking, semantics, relevance feedback and using sentences (or clauses) as documents when queries are expressed in natural language in order to be able to search for and retrieve relevant documents.

SUMMARY OF THE INVENTION

The first objective of the present invention is to provide a natural language retrieval system which combines statistical ranking, semantics, relevance feedback and using sentences (or clauses) as documents when using natural language queries in order to be able to search for and retrieve relevant documents.

The second object of this invention is to provide an automated document retrieval system that minimizes the reading efforts of the user.

The third object of this invention is to provide an automated document retrieval system that minimizes the need for highlighting relevant words on a screenful of text in order to be able to indicate relevant information from a query.

The prefered method of the invention uses statistical ranking and the concept of semantics as shown in U.S. patent application Ser. No. 08/148,688 filed on Nov. 5, 1993, in order to rank relevant documents retrieved for a user's original query. After submitting a query, the user then reads one or more of the topmost documents in the ranked list of documents produced for the query. Since each document is very small (a clause, or a sentence at most), it is very easy for the user to quickly indicate if the document is relevant or not relevant to the original query. For each document flagged as relevant or not relevant, an automatic modification is made to the original query to essentially increase or decrease the importance of words. The new query is used to create another ranked list of documents. The feedback process repeats until the user stops the process.

In the subject invention, semantics helps to push relevant documents upward in a statistically ranked list. Relevance feedback helps the user automatically identify alternative words useful for expressing the query. The effort displayed by the user is minimal since the user views only small amounts of text and makes only a single judgement call on whether the small piece of text is relevant or not relevant for each small amount of text.

The invention can be applied to tasks such as retrieving documents relevant to a search request (sometimes referred to as archival retrieval), filtering documents which are relevant to a search request (sometimes referred to as routing) and answering questions from general information data bases.

Further objects and advantages of this invention will be apparent from the following detailed description of a presently preferred embodiment which is illustrated schematically in the accompanying drawings.

BRIEF DESCRIPTION OF THE FIGURES

FIG. 1 illustrates the preferred embodiment of the invention.

FIG. 2 illustrates the procedure used in patent application with Ser. No. 08/148,688 (filed on Nov. 5, 1993 which issued as U.S. Pat. No. 5,576,954 on Nov. 19, 1996) to determine a number to indicate the relevance or similarity of a document to a query.

FIG. 3 illustrates an example of an original user query and a collection of eight documents.

FIG. 4 is a list of words considered too general to have any value as a keyword, or as a word having any useful semantic value.

FIG. 5 is a list of words used in the original query of FIG. 3; this list becomes Query Word List in Step 100 of FIG. 1.

FIG. 6 provides the list of words used in each of the eight documents of FIG. 3.

FIG. 7 is a list of statistical data for all the words in the eight documents of FIG. 3; the information shown is a count of the number of documents containing each word, and the IDF of each word.

FIG. 8 reveals semantic information about each word used in the original query in FIG. 3; for each word listed in FIG. 5, this figure shows a count of the semantic categories triggered by the word, along with a list of the numeric codes for those categories. This information comes for Roget's International Thesaurus (5th Edition), edited by Robert L. Chapman, HarperCollins Publishers, 1992.

FIGS. 9A-9E reveal semantic information about each word used in the collection of eight documents in FIG. 3; for each word listed in FIG. 6, this figure show a count of the semantic categories triggered by the word, along with a list of the numeric codes for those categories. This information comes from Roget's International Thesaurus (5th Edition), edited by Robert L. Chapman, HarperCollins Publishers, 1992.

FIG. 10 provides the Document List of DocIds created in Step 200 of FIG. 1 for the example of FIG. 3.

FIG. 11 is a list of the eight documents in the example of FIG. 3 ranked in order of their relevance or similarity (SIM value) to the words used in the original query of FIG. 3 and shown in FIG. 5; both the DocId and the SIM value are shown as a pair in this list. This list is a sorted Relevancy List created at Step 900 in FIG. 1.

FIG. 12 is a list of words in a second query built from the original query after removing the words found in Document 5 (only the word "travel" was removed). This list is created by Step 1300 in FIG. 1.

FIG. 13 is a list of seven documents in the example of FIG. 3 (Document 5 has been removed) ranked in order of their relevance or similarity (SIM value) to the words of the second query of FIG. 12; both the DocID and the SIM value are shown as a pair in this list. This list is a sorted Relevancy List created at Step 900 in FIG. 1.

FIG. 14 is a list of words in a third query built by adding words found in Document 4 to the words of the second query of FIG. 12; this list is created by Step 1200 in FIG. 1.

FIG. 15 is a list of six documents in the example of FIG. 3 (Document 5 and Document 4 have been removed) ranked in order of their relevance or similarity (SIM value) to the words of the third query of FIG. 14; both the DocId and the SIM value are shown as a pair in this list. This list is a sorted Relevancy List created by Step 900 in FIG. 1. The top document on this list (Document 2) provides the answer to the original query of FIG. 3.

DESCRIPTION OF THE PREFERRED EMBODIMENT

Before explaining the disclosed embodiment of the present invention in detail it is to be understood that the invention is not limited in its application to the details of the particular arrangement shown since the invention is capable of other embodiments. Also, the terminology used herein is for the purpose of description and not of limitation.

A prototype of the inventor's process has been successfully used at the NASA KSC Public Affairs Office. The performance of the prototype was measured by a count of the number of documents one must read in order to find an answer to a natural language question. In some queries, a noticeable semantic improvement has been observed. For example, if only keywords are used for the query "How fast does the orbiter travel on orbit?" then 17 retrieved paragraphs must be read to find the answer to the query. But if semantic information is used in conjunction with key words then only 4 retrieved paragraphs need to be read to find the answer to the query. Thus, the prototype enabled a searcher to find the answer to their query by a substantial reduction of the number of documents that must be read.

Reference will now be made in detail to the present preferred embodiment of the invention as illustrated in the accompanying drawings.

The present preferred embodiment is demonstrated using an environment where a user's original query is a simple question and the user is searching for an answer to the question. During the search, we expect the user to see relevant and non-relevant documents. The user is expected to continue until a document answering the question is read, or until there are no more documents left to read.

The detailed description refers to acronyms and terminology that is described in the following chart.

TERMINOLOGY

    ______________________________________
    SIM for a query
              A number which measures the relevance of a docu-
    and a document
              ment to a query.
    qword     A word in the list of words used in a query.
    cat       A semantic category code.
    qp        The probability a qword triggers a cat.
    dword     A word in the list of words used in a document.
    dp        The probability a dword triggers a cat.
    DocId     The identifier for a document, the document number
    N         Total number of documents.
    NDOCS     The number of documents a word is in.
    for a word
    IDF       The inverse document frequency which is defined
    for a word
              here to be log.sub.2 (N/NDOCS for the word).
    Document  List of words used in a document. FIG. 6 shows
    Word List eight of these lists.
    Query     List of words used in a query.
    Word List
    Document List
              List of DocIds.
    Relevancy List
              List of DocId, SIM pairs.
    ______________________________________

• Inventors
  Driscoll, James R.;
• Assignee
  University of Central Florida (Orlando, FL)
• Published
  Apr-6-1999
• Current US Classes:
  704/9
  707/3
  707/5
  715/500
• Application #
  880807
• International Classes
  G06F 017/30
• Field of Search
  707/5 707/3 707/500 704/9
• Examiner
  Black; Thomas G.
• Agent
  Brian S. Steinberger, Steinberger; Brian S.
• US Patent References:
  5251316
  5293552
  5297027
  5297039
  5299125
  5301109
  5305208
  5309359
  5321608
  5321609
  5321833
  5323313
  5325298
  5325465
  5331554
  5331556
  5351190
  5404295
  5418951
  5537586
  5544352
  5598557
  5642502
  5694592
  5724567