Information retrieval using dynamic evidence combination

• US 6,269,368 B1
• Filed: 10/16/1998
• Issued: 07/31/2001
• Est. Priority Date: 10/17/1997
• Status: Expired due to Term

• Current Assignee: TextWise Company, LLC
• Original Assignee: TextWise Company, LLC
• Inventors: Diamond, Theodore G.
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/173,968
• Time in Patent Office: 1,019 Days
• Field of Search: 707/3-10, 707/100-104, 707/200-206, 707/513-532, 345/302
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for improving information retrieval effectiveness by dynamically combining evidence information produced by a plurality of retrieval systems matching alternative representations of queries and documents. The user enters a query and the system generates alternative representations of the query. The system also maintains a collection of documents and corresponding alternative representations of the documents. The system then performs matching between the alternative representations of the query and the corresponding alternative representations of the documents and generates individual matching scores for the alternative representation matches. Correlation information is also determined for the individual scores. The individual matching scores are combined using a dynamic combination regime which is adjusted for the query. The dynamic combination regime may be a function of query specific information, retrieved documents specific information, or correlation information. The documents are ranked based on the combined scores. The user may also mark specific documents as being relevant. This relevance feedback information may also be used to modify the dynamic combination regime.

Claims

1. A method of operating a computerized information retrieval system here information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a query specifying information to be retrieved;

processing the query to abstract the query to each of a plurality of alternative representations suitable for input to a database of documents, each document of which is abstracted to each of the plurality of alternative representations;

for each alternative representation, determining a set of documents, each of whose respective corresponding alternative representation bears a relationship to the alternative representation of the query representing a non-zero measure of similarity, the measure of similarity being referred to as an individual score;

combining the sets of documents, so determined, to define a combined set of documents, each document having a non-zero individual score for at least one of the plurality of alternative representations;

determining, for each query, a set of query specific parameters that depend on the query;

for at least some documents in the combined set, combining the individual scores according to a combination regime to produce a combined score, wherein the combination regime is a function of the plurality of individual scores and the set of query specific parameters.

2. The method of claim 1 further comprising:

generating a ranked list of documents from the combined set of documents on basis of the combined scores of the documents;

displaying the ranked list of documents;

receiving user input specifying selection of at least some of the documents from the displayed list of documents, the selected documents indicating documents relevant to the user;

determining relevance feedback information based on the selected documents; and

for at least some documents in the combined set, recombining the individual scores according to the combination regime to produce a second combined score, wherein the combination regime for producing the second combined score is a function of the plurality of individual scores, the set of query specific parameters, and the relevance feedback information.

3. The method of claim 1 wherein the combination regime is a function of a characteristic of at least some of the documents'"'"' individual scores.

4. The method of claim 1 wherein the set of query specific parameters depends on the length of the query.

5. The method of claim 1 wherein the set of query specific parameters depends on grammatical attributes of the query.

6. The method of claim 1 wherein the set of query specific parameters depends on terms contained in the query.

7. The method of claim 6 wherein the set of query specific parameters depends on synonyms for the terms contained in the query.

8. The method of claim 1 further comprising:

determining document specific information for at least some documents of the combined set of documents; and

wherein the combination regime is a function of the document specific information.

9. The method of claim 8 wherein the document specific information depends on length of the documents.

10. The method of claim 1 further comprising:

determining correlation information between the individual scores of the documents within the combined set of documents, the correlation information indicating a measure of the degree to which the individual scores exhibit similar distributions; and

wherein the combination regime is a function of the correlation information.

11. The method of claim 8 wherein the combination regime is determined such that contribution of one or more individual scores towards the combined score is decreased if the correlation information between the individual scores exhibits a high degree of similar distributions.

12. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a query specifying information to be retrieved;

processing the query to abstract the query to each of a plurality of alternative representations suitable for input to a database of documents, each document of which is abstracted to each of the plurality of alternative representations;

for each alternative representation,

determining a set of documents, each of whose respective corresponding alternative representation bears a relationship to the alternative representation of the query representing a non-zero measure of similarity, the measure of similarity being referred to as an individual score;

combining the sets of documents, so determined, to define a combined set of documents, each document having a non-zero individual score for at least one of the plurality of alternative representations;

performing, for the combined set of documents, a correlation operation between first and second individual scores to determine a measure of the degree to which the first individual scores and the second individual scores exhibit similar distributions among the documents in the combined set;

for each document in the combined set, combining the individual scores according to a combination regime to produce a combined score for the document, the combination regime being determined at least in part by reducing the amount that the first and second individual scores contribute to the combined score as a function of the correlation such that the amount that the first and second individual scores contribute to the combined score is decreased more for a larger correlation; and

ranking the documents on the basis of their combined scores.

13. The method of claim 12, and further comprising generating a document vector whose elements correspond to the documents and are weighted by the individual scores of the documents;

and

wherein performing a correlation operation comprises determining at least one correlation between at least one pair of document vectors; and

wherein combining comprises combining the document vectors according to the combination regime to produce a combined document vector whose elements are combinations of the respective elements of the document vectors.

14. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a query specifying information to be retrieved;

processing the query to abstract the query to each of a plurality of alternative representations suitable for input to a database of documents, each document of which is abstracted to each of the plurality of alternative representations;

for each alternative representation,

matching that alternative representation of the query to each document'"'"'s corresponding alternative representation to generate a score representing a measure of similarity, and

generating a document vector whose elements correspond to the documents and are weighted by the scores of the documents;

combining the document vectors according to a combination regime to produce a combined document vector whose elements are combinations of the respective elements of the document vectors, referred to as combined scores, the combination regime being determined at least in part by determining at least one correlation between at least one pair of document vectors and reducing the weights of the pair of document vectors in the combination regime as a function of the correlation such that the weights are decreased more for a larger correlation; and

ranking the documents on the basis of their combined scores.

15. A computer program product for operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the product comprising:

code for receiving a query specifying information to be retrieved;

code for processing the query to abstract the query to each of a plurality of alternative representations suitable for input to a database of documents, each document of which is abstracted to each of the plurality of alternative representations;

code for determining, for each alternative representation, a set of documents, each of whose respective corresponding alternative representation bears a relationship to the alternative representation of the query representing a non-zero measure of similarity, the measure of similarity being referred to as an individual score;

code for combining the sets of documents, so determined, to define a combined set of documents, each document having a non-zero individual score for at least one of the plurality of alternative representations;

code for determining, for each query, a set of query specific parameters that depend on the query;

for at least some documents in the combined set, code for combining the individual scores according to a combination regime to produce a combined score, wherein the combination regime is a function of the plurality of individual scores and the set of query specific parameters; and

a computer-readable storage medium that stores the codes.

16. The product of claim 15 wherein the set of query specific parameters depends on the length of the query.

17. The product of claim 15 wherein the set of query specific parameters depends on grammatical attributes of the query.

18. The product of claim 15 wherein the set of query specific parameters depends on terms contained in the query.

19. The product of claim 18 wherein the set of query specific parameters depends on synonyms for the terms contained in the query.

20. The product of claim 15 further comprising:

code for determining document specific information for at least some documents of the combined set of documents; and

wherein the combination regime is a function of the document specific information.

21. The product of claim 20 wherein the document specific information depends on length of the documents.

22. The product of claim 15 further comprising:

code for determining correlation information between the individual scores of the documents within the combined set of documents, the correlation information indicating a measure of the degree to which the individual scores exhibit similar distributions; and

wherein the combination regime is a function of the correlation information.

23. The product of claim 22 wherein the combination regime is determined such that contribution of one or more individual scores towards the combined score is decreased if the correlation information between the individual scores exhibits a high degree of similar distributions.

24. The product of claim 15 further comprising:

code for generating a ranked list of documents from the combined set of documents on basis of the combined scores of the documents;

code for displaying the ranked list of documents;

code for receiving user input specifying selection of at least some of the documents from the displayed list of documents, the selected documents indicating documents relevant to the user;

code for determining relevance feedback information based on the selected documents; and

for at least some documents in the combined set, code for recombining the individual scores according to the combination regime to produce a second combined score, wherein the combination regime for producing the second combined score is a function of the plurality of individual scores, the set of query specific parameters, and the relevance feedback information.

25. The product of claim 15 wherein the combination regime is a function of a characteristic of at least some of the documents'"'"' individual scores.

26. A computerized information retrieval network system comprising:

at least one server data processing system coupled to a network, the server data processing system configured to retrieve information in response to a query;

a database of documents accessible to the server data processing system via the network;

at least one client system coupled to the server data processing system via the network, said client system configured to receive the query specifying information to be retrieved, and configured to communicate the query to the server data processing system via the network; and

the server data processing system further comprising

a query processor configured to abstract the query to each of a plurality of alternative representations suitable for input to the database of documents;

a document processor configured to abstract the documents in the database to each of the plurality of alternative representations;

a match score generator configured to determine a set of documents for each alternative representation, the alternative representation of each document bearing a relationship to the corresponding alternative representation of the query and indicating a non-zero measure of similarity, the measure of similarity being referred to as an individual score;

a score combiner configured to combine the sets of documents, so determined, to define a combined set of documents, each document in the combined set of documents having a non-zero individual score for at least one of the plurality of alternative representations;

the score combiner further configured to receive from the query processor, for each query, a set of query specific parameters that depend on the query; and

the score combiner further configured to, for at least some documents in the combined set, combine the individual scores according to a combination regime to produce a combined score, wherein the combination regime is a function of the plurality of individual scores and the set of query specific parameters.

27. The computerized information retrieval network system of claim 26 wherein:

said score combiner is further configured to receive document specific information from the document processor for at least some documents of the combined set of documents; and

wherein the combination regime is a function of the document specific information.

28. The computerized information retrieval network system of claim 26 wherein:

the server data processing system further comprises a score correlator, the score correlator configured to determine correlation information between the individual scores of the documents within the combined set of documents, the correlation information indicating a measure of the degree to which the individual scores exhibit similar distributions;

the score combiner is further configured to receive the correlation information from the score correlator for at least some documents of the combined set of documents; and

wherein the combination regime is a function of the correlation information.

29. The computerized information retrieval network system of claim 28 wherein the combination regime is determined such that contribution of one or more individual scores towards the combined score is decreased if the correlation information between the individual scores exhibits a high degree of similar distributions.

30. The computerized information retrieval network system of claim 26 wherein:

the server data processing system is further configured to generate a ranked list of documents from the combined set of documents on basis of the combined scores of the documents, the server data processing system configured to communicate the ranked list of documents to the client system via the network;

the client system configured to display the ranked list of documents, the client system further configured to receive user input specifying selection of at least some of the documents from the displayed list of documents, the selected documents indicating documents relevant to the user, the client system configured to communicate the selected documents to the server data processing system; and

the server data processing system configured to determine relevance feedback information based on the selected documents, and for at least some documents in the combined set, configured to recombine the individual scores according to the combination regime to produce a second combined score, wherein the combination regime is a function of the plurality of individual scores, the set of query specific parameters, and the relevance feedback information.