Query Reformulation Using Post-Execution Results Analysis

• US 20130086024A1
• Filed: 09/29/2011
• Published: 04/04/2013
• Est. Priority Date: 09/29/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Yi, Chen, Yu, Yu, Qing, Wen, Ji-Rong
• Application Number:
  US13/248,894
• Publication Number:
  US 20130086024A1
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Systems, methods, devices, and media are described to facilitate the training and employing of a three-class classifier for post-execution search query reformulation. In some embodiments, the classification is trained through a supervised learning process, based on a training set of queries mined from a query log. Query reformulation candidates are determined for each query in the training set, and searches are performed using each reformulation candidate and the un-reformulated training query. The resulting documents lists are analyzed to determine ranking and topic drift features, and to calculate a quality classification. The features and classification for each reformulation candidate are used to train the classifier in an offline mode. In some embodiments, the classifier is employed in an online mode to dynamically perform query reformulation on user-submitted queries.

Claims

1. A computer-implemented method for search query reformulation, comprising:

generating a query reformulation candidate for an original query;

receiving a first set of documents in response to a search based on the original query;

receiving a second of documents in response to a search based on the query reformulation candidate;

extracting one or more features that indicate a relevance of the first set of documents to the second set of documents; and

providing the one or more features to a classifier, wherein the classifier determines whether the query reformulation candidate will generate more relevant search results than the original query.

2. The method of claim 1, wherein the original query is submitted to a search engine online, and wherein the classifier is trained offline.

3. The method of claim 1, wherein the classifier is a three-class classifier that classifies the query reformulation candidate into one of a set of categories that includes a positive category, a negative category, and a neutral category.

4. The method of claim 1, wherein the classifier is trained offline using a supervised learning method.

5. The method of claim 4, wherein the supervised learning method is at least one of a decision tree method or a support vector machine method.

6. The method of claim 1, further comprising:

generating a reformulated query that is a combination of the original query and the query reformulation candidate, based on the determination that the query reformulation candidate will generate more relevant search results; and

searching using the reformulated query.

7. The method of claim 1, wherein the query reformulation candidate includes a term of the original query and a possible substitute term.

8. The method of claim 1, wherein the one or more features include at least one ranking feature and at least one topic drift feature.

9. A server device, comprising:

at least one processor; and

a query processing component, executable by the at least one processor and configured to perform operations including;

generating a query reformulation candidate for an original query submitted to a search engine;

employing the search engine to execute a search based on the original query;

receiving a first set of web documents in response to the search based on the original query;

employing the search engine to execute a search based on the query reformulation candidate;

receiving a second set of documents in response to the search based on the query reformulation candidate;

extracting one or more features that indicate a relevance of the first set of web documents to the second set of web documents; and

providing the one or more features as input to a multi-class classifier model, wherein the multi-class classifier model determines whether

the query reformulation candidate will generate improved search results compared to the original query.

10. The server device of claim 9, wherein the operations further include filtering one or more query reformulation candidates prior to employing the search engine to execute the search based on the query reformulation candidate.

11. The server device of claim 10, wherein the filtering includes removing at least one query reformulation candidate that is irrelevant or redundant.

12. The server device of claim 9, wherein the multi-class classifier model is a three-class classifier model that classifies the query reformulation candidate into one of a set of categories that includes a positive category, a negative category, and a neutral category.

13. The server device of claim 12, wherein the positive category indicates an improved search result, wherein the negative category indicates a worse search result, and wherein the neutral category indicates a substantially similar search result compared to searching based on the original query.

14. The server device of claim 9, wherein the search engine receives the original query in an online mode, and wherein the multi-class classifier model is trained in an offline mode.

15. The server device of claim 9, wherein the one or more features include at least one ranking feature and at least one topic drift feature.

16. A computer-implemented method for search query reformulation, comprising:

generating at least one query reformulation candidate for a training query;

retrieving one or more candidate search result documents in response to a search based on the at least one query reformulation candidate;

retrieving one or more original search result documents in response to a search based on the training query;

extracting one or more quality features based on the one or more candidate search result documents and on the one or more original search result documents;

computing a quality score for each of the at least one query reformulation candidate, wherein the quality score indicates a relative quality of the at least one query reformulation candidate compared to the training query;

based on the computed quality score, classifying each of the at least one query reformulation candidate into one of a set of categories that includes a positive category, a negative category, and a neutral category;

employing the classified at least one query reformulation candidate to train a classifier, using a supervised learning method; and

employing the classifier to dynamically reformulate one or more online queries received at a search engine.

17. The method of claim 16, wherein each of the at least one query reformulation candidate includes a term from the training query and a possible substitute term for the term.

18. The method of claim 16, wherein the one or more quality features include at least one ranking feature and at least one topic drift feature.

19. The method of claim 16, further comprising randomly selecting the training query from a query log of previous search queries.

20. The method of claim 16, further comprising filtering the at least one query reformulation candidate prior to retrieving the one or more candidate search result documents.