Automated relevance tuning

• US 7,546,294 B2
• Filed: 03/31/2005
• Issued: 06/09/2009
• Est. Priority Date: 03/31/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Burkard, Timo, Hullender, Gregory
• Primary Examiner(s): Khakhar; Nirav K
• Application Number:
  US11/094,364
• Publication Number:
  US 20060224577A1
• Time in Patent Office: 1,531 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for optimizing the performance of a document ranker in a search engine. Weights are assigned to the document features considered by the document ranker. The weights are optimized to produce the highest possible relative ranking for a group of test documents in response to an associated group of search queries.

Claims

1. A method for performing a document search, comprising:

providing a plurality of documents, each document being associated with at least one search query;

identifying one or more feature parameters for use in a document ranker, each feature parameter having an initial parameter value;

ranking each of the plurality of documents relative to a test set of documents at each of a plurality of parameter variations using said document ranker, wherein each parameter variation comprises a parameter value for an associated feature parameter and the initial parameter value for all other feature parameters;

determining, for each of the plurality of documents, one or more parameter variations that produce a ranking change for a document relative to one or more of the test documents, wherein the determining one or more parameter variations is performed by at least one of one or more computing devices;

aggregating, for each feature parameter, the ranking changes for each of the plurality of documents for each parameter variation associated with the feature parameter, wherein the aggregating the ranking changes is performed by at least one of the one or more computing devices;

identifying, for each feature parameter, a parameter variation corresponding to a maximum relevance value based on the aggregated ranking changes for each of the plurality of documents, wherein the identifying a parameter variation is performed by at least one of the one or more computing devices;

adjusting the parameter values of the plurality of parameters based on the identified parameter variations corresponding to the maximum relevance values, wherein adjusting the parameter values comprises;

(1) calculating a parameter gain based on the identified parameter variation for each parameter value;

(2) determining a gain factor for each parameter value corresponding to the calculated parameter gain divided by the largest identified parameter gain; and

(3) modifying each parameter value by an amount proportional to the gain factor for the parameter value,

and wherein the adjusting the parameter values is performed by at least one of the one or more computing devices;

receiving a search query; and

calculating a ranking value for at least one document using the adjusted parameter value in response to the search query.

2. The method of claim 1, wherein adjusting the parameter values further comprises:

modifying each parameter value by an amount proportional to a difference between the initial parameter value and the parameter value of the identified parameter variation multiplied by the gain factor for the parameter value.

3. The method of claim 1, wherein aggregating the ranking changes comprising aggregating the ranking changes in a parameter gain array.

4. The method of claim 1, wherein each document associated with a search query is assigned a query value relative to the associated search query.

5. The method of claim 4, further comprising determining, for each parameter variation, a relative value based on a normalized discounted cumulated gain calculation of query values.

6. A method for recognizing a pattern, comprising:

providing a plurality of patterns, each pattern being associated with at least one pattern query;

identifying one or more feature parameters for use in a pattern ranker, each feature parameter having an initial parameter value;

ranking each of the plurality of patterns relative to a test set of patterns for each of a plurality of parameter variations using said pattern ranker, wherein each parameter variation comprises a parameter value for an associated feature parameter and the initial parameter value for all other feature parameters;

determining, for each of the plurality of patterns, one or more parameter variations that produce a ranking change for a pattern relative to one or more of the test patterns, wherein the determining one or more parameter variations is performed by at least one of one or more computing devices;

aggregating, for each feature parameter, the ranking changes for each of the plurality of patterns for each parameter variation associated with the feature parameter, wherein the aggregating the ranking changes is performed by at least one of the one or more computing devices;

identifying, for each feature parameter, a parameter variation corresponding to a maximum relevance value based on the aggregated ranking changes for each of the plurality of patterns, wherein the identifying a parameter variation is performed by at least one of the one or more computing devices;

adjusting the parameter values of the plurality of parameters based on the identified parameter variations corresponding to the maximum relevance values, wherein the adjusting the parameter values is performed by at least one of the one or more computing devices;

receiving a pattern query; and

calculating a ranking value for at least one pattern using the adjusted parameter values in response to the pattern query.

7. The method of claim 6, wherein adjusting the parameter values comprises modifying each parameter value by an amount proportional to the difference between the current parameter value and the parameter value of the identified parameter variation.

8. The method of claim 6, wherein adjusting the parameter values comprises:

calculating a parameter gain based on the identified parameter variation for each parameter value;

determining a gain factor for each parameter value corresponding to the calculated parameter gain divided by the largest identified parameter gain;

modifying each parameter value by an amount proportional to the gain factor for the parameter value.

9. The method of claim 6, wherein aggregating the ranking changes comprises aggregating the ranking changes in a parameter gain array.

10. The method of claim 6, wherein each pattern associated with a search query is assigned a query value relative to the associated search query, the method further comprising:

determining, for each parameter variation, a relevance value based on a normalized discounted cumulated gain calculation of query values.

11. The method of claim 6, wherein the plurality of patterns comprise alphanumeric characters and the pattern query comprises a handwriting sample.

12. The method of claim 6, wherein the plurality of patterns comprise strings of characters and the pattern query comprises one or more words in a document being checked for spelling.

13. A system, including a processor, for performing document searches, comprising:

a document feature evaluator for determining one or more document feature values for a document based on a search query;

a document ranker for calculating a ranking value based on the one or more document feature values and a feature parameter value associated with each document feature;

a document ranking aggregator for aggregating document ranking information, identifying variations in feature parameter values corresponding to ranking changes between two or more documents, and determining variations in feature parameter values corresponding to maximum relevance values for a collection of documents; and

a parameter optimizer for modifying the feature parameter values based on the variations corresponding to maximum relevance values for the collection of documents, wherein the parameter optimizer comprises;

(1) a parameter gain calculator for calculating a parameter gain based on the identified parameter variation for each parameter value;

(2) a gain factor calculator for calculating a gain for each parameter value corresponding to the calculated parameter gain divided by the largest identified parameter gain; and

(3) a parameter value modifier for modifying each parameter value by an amount proportional to the gain factor for the parameter value, wherein the parameter optimizer utilizes a computing device to optimize the feature parameters.

14. The system of claim 13, wherein the document ranker further comprises a feature parameter modifier for producing parameter variations.

15. The system of claim 13, wherein each document associated with a search query is assigned a query value relative to the associated search query, and wherein the document ranking aggregator determines variations in feature parameter values that correspond to maximum relevance values based on a discounted cumulated gain calculation of query values.

16. The system of claim 13, wherein the document ranking aggregator further aggregates ranking changes in a parameter gain array.

17. The method of claim 13, wherein the parameter value modifier further modifies each parameter value by an amount proportional to the difference between the current parameter value and the parameter value corresponding to the maximum relevance value.