Optimization framework for tuning ranking engine

• US 8,108,374 B2
• Filed: 09/16/2008
• Issued: 01/31/2012
• Est. Priority Date: 09/16/2008
• Status: Active Grant

• Current Assignee: Yahoo AD Tech LLC
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Zhang, Ruofei, Mao, Jianchang
• Primary Examiner(s): TO, BAOQUOC N
• Application Number:
  US12/211,307
• Publication Number:
  US 20100070498A1
• Time in Patent Office: 1,232 Days
• Field of Search: None
• US Class Current: 707/705
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Disclosed are apparatus and methods for facilitating the ranking of web objects. The method includes automatically adjusting a plurality of weight values for a plurality of parameters for inputting into a ranking engine that is adapted to rank a plurality of web objects based on such weight values and their corresponding parameters. The adjusted weight values are provided to the ranking engine so as to generate a ranked set of web objects based on such adjusted weight values and their corresponding parameters, as well as a particular query. A relevance metric (e.g., that quantifies or qualifies how relevant the generated ranked set of web objects are for the particular query) is determined. The method includes automatically repeating the operations of adjusting the weight values, providing the adjusted weight values to the ranking engine, and determining a relevance metric until the relevance metric reaches an optimized level, which corresponds to an optimized set of weight values. The repeated operations utilize one or more sets of weight values including at least one set that results in a worst relevance metric value, as compared to a previous set of weight values, according to a certain probability in order to escape local optimal solution to reach the global optimal solution.

Claims

1. A method for facilitating the ranking of a plurality of web objects, comprising:

automatically adjusting a plurality of weight values for a plurality of parameters for inputting into a ranking engine that is adapted to rank a plurality of web objects based on such weight values and their corresponding parameters;

providing the adjusted weight values to the ranking engine so as to generate a ranked set of web objects based on such adjusted weight values and their corresponding parameters, as well as a particular query;

determining a relevance metric that quantifies or qualifies how relevant the generated ranked set of web objects are for the particular query; and

automatically repeating the operations of adjusting the weight values, providing the adjusted weight values to the ranking engine, and determining a relevance metric until the relevance metric reaches an optimized level, which corresponds to an optimized set of weight values, and wherein the repeated operations utilize one or more sets of weight values including at least one set that results in a worst relevance metric value, as compared to a previous set of weight values, according to a certain probability in order to escape a local optimal solution to reach a global optimal solution,

wherein the operation of automatically repeating the operations for adjusting the weights, providing the adjusted weight values, and determining a relevance metric is accomplished by;

generating a N+1 vertex data structure, wherein N corresponds to the number of parameters for which weight values are to be adjusted; and

transforming the data structure by a reflecting, expanding, and/or contracting operation on one or more vertices of the data structure whereby the transformed data structure'"'"'s resulting vertices correspond to the adjusted weight values that are provided to the ranking engine, and wherein the transforming of the data structure is dependent on a variable temperature, which decreases for one or more transformation operations based on a simulated annealing technique, so that the probability that the adjusted weight values results in a lower relevance metric is inversely proportional to a current temperature value of the variable temperature.

2. The method as recited in claim 1, wherein the data structure is in the form of a simplex.

3. The method as recited in claim 2, wherein the transforming operation is performed by a modified Nelder-Mead technique that includes a positive, logarithmically distributed random variable, proportional to the current temperature value, within each stored function value that is associated with each vertex of the simplex, and a similar random variable that is subtracted from the function value of every new point of the simplex.

4. The method as recited in claim 1, wherein the query includes one or more keywords and the ranking engine is adapted to locate web objects that are most relevantly associated with such keywords.

5. The method as recited in claim 1, wherein the query includes a web page and the ranking engine is adapted to locate web objects in the form of advertisement objects that are most relevantly associated with such web page.

6. The method as recited in claim 1, wherein the relevance metric is a normalized discounted cumulated gain (nDCG) value or a mean average precision (MAP) value.

7. An apparatus comprising at least a processor and a memory, wherein the processor and/or memory are configured to perform the following operations:

automatically adjusting a plurality of weight values for a plurality of parameters for inputting into a ranking engine that is adapted to rank a plurality of web objects based on such weight values and their corresponding parameters;

providing the adjusted weight values to the ranking engine so as to generate a ranked set of web objects based on such adjusted weight values and their corresponding parameters, as well as a particular query;

determining a relevance metric that quantifies or qualifies how relevant the generated ranked set of web objects are for the particular query; and

automatically repeating the operations of adjusting the weight values, providing the adjusted weight values to the ranking engine, and determining a relevance metric until the relevance metric reaches an optimized level, which corresponds to an optimized set of weight values, and wherein the repeated operations utilize one or more sets of weight values including at least one set that results in a worst relevance metric value, as compared to a previous set of weight values, according to a certain probability in order to escape a local optimal solution to reach a global optimal solution,

wherein the operation of automatically repeating the operations for adjusting the weights, providing the adjusted weight values, and determining a relevance metric is accomplished by;

generating a N+1 vertex data structure, wherein N corresponds to the number of parameters for which weight values are to be adjusted; and

transforming the data structure by a reflecting, expanding, and/or contracting operation on one or more vertices of the data structure whereby the transformed data structure'"'"'s resulting vertices correspond to the adjusted weight values that are provided to the ranking engine, and wherein the transforming of the data structure is dependent on a variable temperature, which decreases for one or more transformation operations based on a simulated annealing technique, so that the probability that the adjusted weight values results in a lower relevance metric is inversely proportional to a current temperature value of the variable temperature.

8. The apparatus as recited in claim 7, wherein the data structure is in the form of a simplex.

9. The apparatus as recited in claim 8, wherein the transforming operation is performed by a modified Nelder-Mead technique that includes a positive, logarithmically distributed random variable, proportional to the current temperature value, within each stored function value that is associated with each vertex of the simplex, and a similar random variable that is subtracted from the function value of every new point of the simplex.

10. The apparatus as recited in claim 7, wherein the query includes one or more keywords and the ranking engine is adapted to locate web objects that are most relevantly associated with such keywords.

11. The apparatus as recited in claim 7, wherein the query includes a web page and the ranking engine is adapted to locate web objects in the form of advertisement objects that are most relevantly associated with such web page.

12. The apparatus as recited in claim 7, wherein the relevance metric is a normalized discounted cumulated gain (nDCG) value or a mean average precision (MAP) value.

13. At least one computer readable storage medium having computer program instructions stored thereon that are arranged to perform the following operations:

automatically adjusting a plurality of weight values for a plurality of parameters for inputting into a ranking engine that is adapted to rank a plurality of web objects based on such weight values and their corresponding parameters;

providing the adjusted weight values to the ranking engine so as to generate a ranked set of web objects based on such adjusted weight values and their corresponding parameters, as well as a particular query;

determining a relevance metric that quantifies or qualifies how relevant the generated ranked set of web objects are for the particular query; and

automatically repeating the operations of adjusting the weight values, providing the adjusted weight values to the ranking engine, and determining a relevance metric until the relevance metric reaches an optimized level, which corresponds to an optimized set of weight values, and wherein the repeated operations utilize one or more sets of weight values including at least one set that results in a worst relevance metric value, as compared to a previous set of weight values, according to a certain probability in order to escape a local optimal solution to reach a global optimal solution,

wherein the operation of automatically repeating the operations for adjusting the weights, providing the adjusted weight values, and determining a relevance metric is accomplished by;

generating a N+1 vertex data structure, wherein N corresponds to the number of parameters for which weight values are to be adjusted; and

transforming the data structure by a reflecting, expanding, and/or contracting operation on one or more vertices of the data structure whereby the transformed data structure'"'"'s resulting vertices correspond to the adjusted weight values that are provided to the ranking engine, and wherein the transforming of the data structure is dependent on a variable temperature, which decreases for one or more transformation operations based on a simulated annealing technique, so that the probability that the adjusted weight values results in a lower relevance metric is inversely proportional to a current temperature value of the variable temperature.

14. The least one computer readable storage medium as recited in claim 13, wherein the data structure is in the form of a simplex.

15. The least one computer readable storage medium as recited in claim 14, wherein the transforming operation is performed by a modified Nelder-Mead technique that includes a positive, logarithmically distributed random variable, proportional to the current temperature value, within each stored function value that is associated with each vertex of the simplex, and a similar random variable that is subtracted from the function value of every new point of the simplex.

16. The least one computer readable storage medium as recited in claim 13, wherein the query includes one or more keywords and the ranking engine is adapted to locate web objects that are most relevantly associated with such keywords.

17. The least one computer readable storage medium as recited in claim 13, wherein the query includes a web page and the ranking engine is adapted to locate web objects in the form of advertisement objects that are most relevantly associated with such web page.

18. The least one computer readable storage medium as recited in claim 13, wherein the relevance metric is a normalized discounted cumulated gain (nDCG) value or a mean average precision (MAP) value.