Determining a relevance function based on a query error derived using a structured output learning technique

• US 8,005,774 B2
• Filed: 11/28/2007
• Issued: 08/23/2011
• Est. Priority Date: 11/28/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chapelle, Olivier
• Primary Examiner(s): Gaffin; Jeffrey A
• Assistant Examiner(s): BROWN JR, NATHAN H
• Application Number:
  US11/946,552
• Publication Number:
  US 20090138463A1
• Time in Patent Office: 1,364 Days
• Field of Search: 706/16
• US Class Current: 706/16
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Methods, systems, and apparatuses for generating relevance functions for ranking documents obtained in searches are provided. One or more features to be used as predictor variables in the construction of a relevance function are determined. The relevance function is parameterized by one or more coefficients. An ideal query error is defined that measures, for a given query, a difference between a ranking generated by the relevance function and a ranking based on a training set. According to a structured output learning framework, values for the coefficients of the relevance function are determined to substantially minimize an objective function that depends on a continuous upper bound of the defined ideal query error. The query error is determined using a structured output learning technique. The query error is defined as a maximum over a set of permutations.

Claims

1. A method of determining a relevance function, comprising:

determining one or more features to be used as predictor variables in the construction of a relevance function;

parameterizing the relevance function by one or more coefficients at least partially using hardware;

defining a query error that is a continuous upper bound on an ideal query error, the ideal query error being a difference between a relevance measure on a ranking generated by the relevance function and a ranking based on a training set, said defining including deriving the query error using a structured output learning technique, wherein the query error is defined as a maximum over a set of permutations; and

determining values for the coefficients of the relevance function by gradient descent to substantially minimize an objective function that depends on the defined query error.

2. The method of claim 1, wherein said defining comprises:

defining the relevance measure in the ideal query error to be a discounted cumulative gain (DCG) error.

3. The method of claim 1, wherein the objective function is a sum over a set of queries of the defined query error, wherein said determining comprises:

determining values for the coefficients of the relevance function that substantially minimize the sum over a set of queries of the defined query error.

4. The method of claim 1, wherein said defining the query error comprises:

defining the query error as

5. The method of claim 1, wherein said defining the query error comprises:

defining the query error as

6. The method of claim 3, further comprising:

adjusting a parameter and repeating said determining values for the coefficients of the relevance function that substantially minimize a sum over a set of queries of the defined query error if the relevance function does not satisfy said testing.

7. The method of claim 4, further comprising:

testing the relevance function having the determined values for the one or more coefficients.

8. The method of claim 7, further comprising:

enabling the relevance function to be used to rank documents returned by queries if the relevance function satisfies said testing.

9. A system for determining a relevance function, comprising:

at least one computer that includes hardware;

a relevance function constructor implemented at least partially using the hardware that is configured to construct a relevance function based on one or more features used as predictor variables and one or more coefficients; and

a relevance function tuner configured to determine values for the one or more coefficients of the relevance function by gradient descent to substantially minimize an objective function that depends on a query error, wherein the query error is a continuous upper bound on an ideal query error, the ideal query error being a difference between a relevance measure on a ranking generated by the relevance function and a ranking based on a training set, wherein the query error is determined by a structured output learning technique, wherein the query error is defined as a maximum over a set of permutations.

10. The system of claim 9, wherein the relevance measure in the ideal query error is the discounted cumulative gain (DCG) error.

11. The system of claim 9, wherein the objective function is a sum over a set of queries of the query error.

12. The system of claim 9, wherein the query error is

13. The system of claim 11, wherein the query error is

14. The system of claim 13, further comprising:

a relevance function tester configured to test the relevance function having the values for the one or more coefficients determined by the relevance function tuner.

15. The system of claim 14, wherein the relevance function tuner is configured to adjust a parameter and to repeat the determination of values for the coefficients of the relevance function if the relevance function does not satisfy the test by the relevance function tester.

16. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for determining a relevance function, comprising:

a first computer readable program code means for enabling a processor to determine values for one or more coefficients of a relevance function that is based on one or more features used as predictor variables and the one or more coefficients, wherein the first computer readable program code means is configured to enable the processor to determine values for the one or more coefficients by gradient descent to substantially minimize an objective function that depends on a query error, wherein the query error is a continuous upper bound on an ideal query error, the ideal query error being a difference between a relevance measure on a ranking generated by the relevance function and a ranking based on a training set;

wherein the first computer readable program code means comprises;

a second computer readable program code means for enabling a processor to determine the query error using a structured output learning technique, wherein the query error is defined as a maximum over a set of permutations.