Linear combination of rankers

• US 8,392,410 B2
• Filed: 07/15/2010
• Issued: 03/05/2013
• Est. Priority Date: 10/19/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Burges, Christopher J. C.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US12/836,660
• Publication Number:
  US 20100281024A1
• Time in Patent Office: 964 Days
• Field of Search: 707/705, 707/706, 707/758, 707/759, 707/709, 707/734, 707/761, 707/769, 707/723
• US Class Current: 707/723
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Described herein is a system that includes a receiver component that receives first scores for training points and second scores for the training points, wherein the first scores are individually assigned to the training points by a first ranker component and the second scores are individually assigned to the training points by a second ranker component. The apparatus further includes a determiner component in communication with the receiver component that automatically outputs a value for a parameter α based at least in part upon the first scores and the second scores, wherein α is used to linearly combine the first ranker component and the second ranker component.

Claims

1. An apparatus, comprising:

a processor; and

a memory that comprises a plurality of components that are executed by the processor, the plurality of components comprising;

a receiver component that receives first scores for training points and second scores for the training points, wherein the first scores are individually assigned to the training points by a first ranker component and the second scores are individually assigned to the training points by a second ranker component; and

a determiner component in communication with the receiver component that automatically outputs a value for a parameter α

based at least in part upon the first scores and the second scores, wherein α

is used to linearly combine the first ranker component and the second ranker component, the determiner component comprising a metric computer component that uses an information retrieval metric method to determine the value of α

, such that the value α

corresponds to an optimal linear combination of the first and second ranker components with respect to the information retrieval metric method, the information retrieval metric method being one of Normalized Discounted Cumulative Gain, Mean Average Precision, Mean Reciprocal Rank, Bpref, Q-measure, or generalized average precision.

2. The apparatus of claim 1, wherein the linear combination of the first and second ranker components is of the form S=(1−

α

)S₁+α

S₂, wherein S₁ represents scores output by the first ranker component for the training points, S₂ represents scores output by the second ranker component for the training points, and S represents a final score output by the linear combination of the first and second ranker components.

3. The apparatus of claim 1, wherein the linear combination of the first and second ranker components is of the form S=S₁+α

S₂, wherein S₁ represents scores output by the first ranker component for the training points, S₂ represents scores output by the second ranker component for the training points, and S represents a final score for the linear combination of the first and second ranker components.

4. The apparatus of claim 1, wherein the training points include one or more of a uniform resource locator (URL) or a file.

5. The apparatus of claim 1, the plurality of components further comprising an interface component that locates the training points when given a query, wherein located training points are assigned scores by the first and second ranker components.

6. The apparatus of claim 1, the plurality of components further comprising a combiner component that automatically linearly combines the first ranker component and the second ranker component upon the determiner component outputting the value for α

.

7. The apparatus of claim 1, the plurality of components further comprising a locator component that determines values of α

that correspond to instances that scores of different training points are equal when the first and second ranker components are linearly combined using the determined value of α

.

8. The apparatus of claim 1, the plurality of components further comprising a resolver component that recognizes values of α

that cause scores of three or more training points to be equal when the first and second ranker components are linearly combined as a function of α

.

9. The apparatus of claim 1, wherein the determiner component determines a value for α

used to linearly combine three or more ranker components, wherein the value of α

is selected to optimize the linear combination of the three or more ranker components with respect to an information retrieval metric method.

10. A method for linearly combining ranker components, comprising:

receiving first scores for a plurality of training points, wherein each training point in the plurality of training points is individually assigned a score by a first ranker component;

receiving second scores for the plurality of training points, wherein each training point in the plurality of training points is individually assigned a score by a second ranker component; and

linearly combining the first ranker component and the second ranker component to generate a linear combination of the first ranker component and the second ranker component based at least in part upon the first scores and the second scores, wherein the linear combination of the first ranker component and the second ranker component is optimal or substantially optimal with respect to an information retrieval metric method, wherein linearly combining the first ranker component and the second ranker component comprises determining a value of a parameter α

that is used to modify at least one of first scores output by the first ranker component or second scores output by the second ranker component, the value of the parameter α

determined to optimize the linear combination of the first ranker component and the second ranker component with respect to an information retrieval metric, the information retrieval metric being one of Normalized Discounted Cumulative Gain, Mean Average Precision, Mean Reciprocal Rank, Bpref, Q-measure, or generalized average precision.

11. The method of claim 10, wherein the linear combination of the first and second ranker components is of the form S=(1−

α

)S₁+α

S₂, wherein S₁ represents scores output by the first ranker component for the plurality of training points, S₂ represents scores output by the second ranker component for the plurality of training points, and S represents a final score output by the linear combination of the first and second ranker components.

12. The method of claim 10, wherein the linear combination of the first and second ranker components is of the form S=S₁+α

S₂, wherein S₁ represents scores output by the first ranker component for the plurality of training points, S₂ represents scores output by the second ranker component for the plurality of training points, and S represents a final score for the linear combination of the first and second ranker components.

13. The method of claim 10, further comprising:

determining a value for α

that causes an output of the linear combination of the first and second ranker components to be equal for two different training points;

determining a first quality metric for a value of α

that is less than the determined value of α

;

determining a second quality metric for a value of α

that is greater than the determined value of α

;

comparing the first and second quality metrics; and

selecting a value for α

based at least in part upon the comparison.

14. The method of claim 10, further comprising linearly combining the first ranker component and the second ranker component with a plurality of other ranker components, wherein the linear combination of the first, second, and plurality of other ranker components is based at least in part upon scores individually assigned to each training point in the plurality of training points by each of the plurality of ranker components.

15. The method of claim 10, further comprising:

using the first ranker component to generate a score for each training point in the plurality of training points; and

using the second ranker component to generate a score for each training point in the plurality of training points.

16. A search engine that includes a ranker component, the search engine comprising a processor and a memory, the ranker component being a linear combination of at least a first ranker component and a second ranker component, the ranker component created by way of a series of acts, the acts comprising:

receiving first scores that are individually assigned to training points by the first ranker component;

receiving second scores that are individually assigned to the training points by the second ranker component;

determining a first value of a parameter α

that causes scores assigned to different training points to be equal, wherein α

is used to linearly combine scores output by the first ranker component with scores output by the second ranker component;

assigning a second value to α

that is less than the first value of α

;

assigning a third value to α

that is greater than the first value of α

;

determining first and second quality metrics for the linear combination of the first ranker component and the second ranker component that correspond to the second value of α and

the third value of α

, respectively;

comparing the first and second quality metrics; and

selecting either the second value of α

or the third value of α

to use to linearly combine the first ranker component and the second ranker component based at least in part upon the comparison.

17. The search engine of claim 16, wherein the selecting either of the second value of α

or the third value of α

to use to linearly combine the first ranker component and the second ranker component is based at least in part upon performance of the ranker component for the training points with respect to an information retrieval metric.

18. The search engine of claim 17, wherein the selecting of either of the second value of α

or the third value of α

to use to linearly combine the first ranker component and the second ranker component is based upon which of the second value of α

or the third value of α

results in a higher score with respect to the information retrieval metric.

19. The search engine of claim 18, the information retrieval metric being one of Normalized Discounted Cumulative Gain, Mean Average Precision, Mean Reciprocal Rank, Bpref, Q-measure, or generalized average precision.