System, method and computer program product for information sorting and retrieval using a language-modeling kernal function

• US 9,177,047 B2
• Filed: 06/22/2011
• Issued: 11/03/2015
• Est. Priority Date: 12/20/2005
• Status: Active Grant

• Current Assignee: Etsy Incorporated
• Original Assignee: Araicom Research LLC
• Inventors: Raghavan, Vijay V., Xie, Ying
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US13/166,011
• Publication Number:
  US 20110270829A1
• Time in Patent Office: 1,595 Days
• Field of Search: 707/999.102, 707/999.101, 707/678, 707/737, 707/609
• 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/3347 using vector based model
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

Various embodiments provide a system, method, and computer program product for sorting and/or selectively retrieving a plurality of documents in response to a user query. More particularly, embodiments are provided that convert each document into a corresponding document language model and convert the user query into a corresponding query language model. The language models are used to define a vector space having dimensions corresponding to terms in the documents and in the user query. The language models are mapped in the vector space. Each of the documents is then ranked, wherein the ranking is based at least in part on a position of the mapped language models in the vector space, so as to determine a relative relevance of each of the plurality of documents to the user query.

Claims

1. A system for sorting a plurality of documents based at least in part on a relationship between each of the plurality of documents and a user query, relevance feedback, and relations among plurality of documents, the system comprising:

a data source comprising the plurality of documents; and

a host computing element in communication with said data source and configured to receive an initial user input comprising the user query;

wherein said host computing element is further configured to convert each of the plurality of documents into a corresponding document language model, each document language model being associated with a distribution of a plurality document terms present in the plurality of documents and a distribution of a plurality document terms present in each of the plurality of documents;

wherein said host computing element is further configured to convert the user query into a corresponding query language model, the query language model being associated with a distribution of a plurality of query terms present in the user query and the distribution of the plurality document terms present in the plurality of documents;

wherein said host computing element is further configured to define a kernel function configured to evaluate a similarity relationship between two document language models under the influence of the query language model;

wherein said host computing element is further configured to automatically obtain via the defined kernel function a first vector space having a plurality of dimensions associated with at least two of the distribution of the plurality document terms present in the plurality of documents, the distribution of the plurality document terms present in each of the plurality of documents, and the distribution of the plurality of query terms present in the user query;

wherein said host computing element is further configured to map via the defined kernel function each of the plurality of the document language models and the query language model in the first vector space; and

wherein said host computing element is further configured to rank each of the plurality of documents based at least in part on a similarity relationship between each of the document language models and the query language model in the first vector space to determine a relative relevance of each of the plurality of documents to the user query.

2. A system according to claim 1, wherein the plurality of documents comprises relevant documents and non-relevant documents relative to the user query, and wherein said host computing element further receives a positive feedback input comprising a selection of at least one of the relevant documents;

wherein said host computing element is further configured to receive a negative feedback input comprising a selection of at least one of the non-relevant documents;

wherein said host computing element is further configured to refine the query language model based on the initial user input and at least one of the positive feedback input and the negative feedback input;

wherein said host computing element is further configured to re-compute the language-modeling kernel as an integration of the query language model and the document language models based at least in part upon replacing the query language model component of the language modeling kernel with the refined query language model;

wherein said host computing element is further configured to generate a decision boundary in a new vector space determined by the re-computed language-modeling kernel between the document language models corresponding to the selected relevant documents and the document language models corresponding to the selected non-relevant documents such that the decision boundary is substantially equidistant from the document language models corresponding to the relevant documents and the document language models corresponding to the non-relevant documents; and

wherein said host computing element is further configured to re-rank each of the plurality of documents based at least in part according to the generated boundary in the new vector space.

3. A system according to claim 2, further comprising a user interface in communication with said host computing element and configured to estimate the positive feedback input from at least one of user browsing activities detected via the user interface, user reading activities detected via the user interface, and user printing activities detected via the user interface.

4. A system according to claim 2, wherein said host computing element is further configured to refine the query language model by analyzing a distribution of the plurality of document terms present in the selection of relevant documents in the positive feedback input and a distribution of the plurality of query terms present in the selection of relevant documents in the positive feedback input.

5. A system according to claim 2, wherein said host computing element is further configured to determine the new vector space using the re-computed language-modeling kernel to automatically determine the dimensions of the new vector space based in part upon at least one of a plurality of document statistics, document collection statistics, and relevance statistics.

6. A system according to claim 2, wherein said host computing element is further configured to generate the decision boundary in the new vector space determined by the re-computed language-modeling kernel by applying a kernel based learning algorithm to the received positive feedback input and the received negative feedback input.

7. A system according to claim 2, wherein the re-computed language modeling kernel integrates a query probability distribution expressed by the query language model corresponding to the user query and the positive feedback input with a similarity measure corresponding to a document probability distribution across the plurality of documents, the language modeling kernel providing a similarity measure between each of the plurality of documents biased at least in part by a user information need, the language modeling kernel being configured for modeling at least one of a plurality document statistics, a plurality of collection statistics, and a plurality of relevance statistics.

8. A system according to claim 2, wherein said host computing element is further configured to re-rank each of the plurality of documents based at least in part on the computed language modeling kernel.

9. A system according to claim 1, wherein said host computing element is further configured to convert each of the plurality of documents into a corresponding document language model by analyzing the distribution of the plurality document terms present in the plurality of documents to determine a statistical measure of at least one of a prevalence of at least one of the plurality of document terms present in each of the plurality of documents and a prevalence of at least one of the plurality of document terms present in the plurality of documents.

10. A system according to claim 1, wherein said host computing element is further configured to convert the user query into a corresponding query language model by analyzing the distribution of the plurality of query terms present in the user query relative to the distribution of the plurality of document terms present in the plurality of documents.

11. A system according to claim 1, wherein said host computing element comprises a memory device configured for storing a plurality of pre-computed document language models and at least a portion of the plurality of documents.

12. A system according to claim 2, wherein the new vector space comprises a high dimensional vector space, which is systematically and dynamically determined by the re-computed language-modeling kernel using a language modeling technique selected from the group consisting of:

term frequency determinations,

term-term co-occurrence relationship determinations,

term distribution determinations in the positive feedback input,

term distribution determinations in a pre-defined user profile,

term distribution determinations in a dynamically generated user profile, and

combinations thereof.

13. A method for sorting a plurality of documents based at least in part on a relationship between each of the plurality of documents and a user query, relevance feedback, and relationships among the plurality of document, the method comprising:

converting each of the plurality of documents into a corresponding document language model, each document language model being associated with a distribution of a plurality document terms present in the plurality of documents and a plurality document terms present in each of the plurality of documents;

converting the user query into a corresponding query language model, the query language model being associated with a distribution of a plurality of query terms present in the user query and the distribution of the plurality of document terms present in the plurality of documents;

defining a kernel function configured to evaluate a similarity relationship between two document language models under the influence of the query language model;

obtaining automatically via the defined kernel function a first vector space having a plurality of dimensions associated with at least two of the distribution of the plurality document terms present in the plurality of documents, the distribution of the plurality document terms present in each of the plurality of documents, and the distribution of the plurality of query terms present in the user query;

mapping via the defined kernel function each of the document language models and the query language model in the first vector space; and

ranking each of the plurality of documents based at least in part on a similarity relationship between each of the document language models and the query language model in the first vector space to determine a relative relevance of each of the plurality of documents to the user query.

14. A method according to claim 13, wherein the plurality of documents comprises relevant documents and non-relevant documents relative to the user query, the method further comprising:

receiving a positive feedback input comprising a selection of at least one of the relevant documents;

receiving a negative feedback input comprising a selection of at least one of the non-relevant documents;

refining the query language model based at least in part on the initial query and at least one of the positive feedback input and the negative feedback input;

re-computing a language-modeling kernel as an integration of the query language model and the document language models based at least in part upon replacing the query language model component of the language-modeling kernel with the refined query language model;

generating a decision boundary in a new vector space determined at least in part by the re-computed language-modeling kernel between the document language models corresponding to the selected relevant documents and the document language models corresponding to the selected non-relevant documents such that the decision boundary is substantially equidistant from the document language models corresponding to the relevant documents and the document language models corresponding to the non-relevant documents; and

re-ranking each of the plurality of documents based at least in part according to the generated boundary in the new vector space.

15. A method according to claim 14, wherein refining the query language model comprises analyzing a distribution of the plurality of document terms present in the selection of relevant documents in the positive feedback input and a distribution of the plurality of query terms present in the selection of relevant documents in the positive feedback input.

16. A method according to claim 14, wherein determining the new vector space comprises using the re-computed language-modeling kernel to automatically determine the dimensions of the new vector space based in part upon at least one of a plurality of document statistics, document collection statistics, and relevance statistics.

17. A method according to claim 13, wherein converting each of the plurality of documents into a corresponding document language model further comprises analyzing the distribution of the plurality document terms present in the plurality of documents to determine a statistical measure of at least one of a prevalence of at least one of the plurality of document terms present in each of the plurality of documents and a prevalence of at least one of the plurality of document terms present in the plurality of documents.

18. A method according to claim 13, wherein converting the user query into a corresponding query language model further comprises analyzing the distribution of the plurality of query terms present in the user query relative to the distribution of the plurality of document terms present in the plurality of documents to determine a statistical measure of the relative relevance of each of the plurality of documents to the user query.

19. A computer program product for sorting a plurality of documents based at least in part on a relationship between each of the plurality of documents and a user query, relevance feedback, interest, and relations among plurality of documents, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code instructions stored therein comprising:

a first set of computer instructions for converting each of the plurality of documents into a corresponding document language model, each document language model being associated with a distribution of a plurality document terms present in the plurality of documents and a plurality document terms present in each of the plurality of documents;

a second set of computer instructions for converting the user query into a corresponding query language model, the query language model being associated with a distribution of a plurality of query terms present in the user query and the distribution of the plurality of document terms present in the plurality of documents;

a third set of computer instructions for defining a kernel function configured to evaluate a similarity relationship between two document language models under the influence of the query language model;

a fourth set of computer instructions for automatically obtaining via the defined kernel function of the third set of computer instructions a first vector space having a plurality of dimensions associated with at least two of the distribution of the plurality of document terms present in the plurality of documents, the distribution of the plurality of document terms present in each of the plurality of documents, and the distribution of the plurality of query terms present in the user query;

a fifth set of computer instructions for mapping via the defined kernel function each of the document language models and the query language model in the first vector space; and

a sixth set of computer instructions for ranking each of the plurality of documents based at least in part on a similarity relationship between each of the document language models and the query language model in the first vector space to determine a relative relevance of each of the plurality of documents to the user query.

20. A computer program product according to claim 19, wherein the plurality of documents comprises relevant documents and non-relevant documents relative to the user query, the computer program product further comprising:

a seventh set of computer instructions for receiving a positive feedback input comprising a selection of at least one of the relevant documents;

a eighth set of computer instructions for receiving a negative feedback input comprising a selection of at least one of the non-relevant documents;

an ninth set of computer instructions for refining the query language model based on the initial user input and at least one of the positive feedback input and the negative feedback input; and

a tenth set of computer instructions for re-computing a language-modeling kernel as an integration of the query language model and the document language models based at least in part upon replacing the query language model component of the language-modeling kernel with the refined query language model;

a eleventh set of computer instructions for generating a decision boundary in a new vector space automatically determined at least in part by the re-computed language-modeling kernel between the document language models corresponding to the selected relevant documents and the document language models corresponding to the selected non-relevant documents such that the decision boundary is substantially equidistant from the document language models corresponding to the relevant documents and the document language models corresponding to the non-relevant documents; and

a twelfth set of computer instructions for re-ranking each of the plurality of documents based at least in part according to the generated boundary in the new vector space.

21. A computer program product according to claim 19, wherein the first set of computer instructions for converting each of the plurality of documents into a corresponding document language model further comprises analyzing the distribution of the plurality document terms present in the plurality of documents to determine a statistical measure of at least one of a prevalence of at least one of the plurality of document terms present in each of the plurality of documents and a prevalence of at least one of the plurality of document terms present in the plurality of documents.

22. A computer program product according to claim 19, wherein the second set of computer instructions for converting the user query into a corresponding query language model further comprises analyzing the distribution of the plurality of query terms present in the user query relative to the distribution of the plurality of document terms present in the plurality of documents to determine a statistical measure of the relative relevance of each of the plurality of documents to the user query.

23. A computer program product according to claim 20, wherein the eleventh set of computer instructions comprise computer instructions for determining the dimensions of the new vector space based in part upon at least one of a plurality of document statistics, document collection statistics, and relevance statistics.