Source: http://www.google.com/patents/US8005774?dq=7493558
Timestamp: 2016-12-11 14:46:00
Document Index: 402044678

Matched Legal Cases: ['art 600', 'art 400', 'art 600', 'art 600', 'art 600', 'art 600', 'art 600', 'art 600', 'art 400', 'art 400', 'art 600', 'art 600', 'art 3', 'art3']

Patent US8005774 - Determining a relevance function based on a query error derived using a ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsMethods, 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....http://www.google.com/patents/US8005774?utm_source=gb-gplus-sharePatent US8005774 - Determining a relevance function based on a query error derived using a structured output learning techniqueAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS8005774 B2Publication typeGrantApplication numberUS 11/946,552Publication dateAug 23, 2011Filing dateNov 28, 2007Priority dateNov 28, 2007Fee statusPaidAlso published asUS20090138463Publication number11946552, 946552, US 8005774 B2, US 8005774B2, US-B2-8005774, US8005774 B2, US8005774B2InventorsOlivier ChapelleOriginal AssigneeYahoo! Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (3), Non-Patent Citations (5), Referenced by (6), Classifications (7), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetDetermining a relevance function based on a query error derived using a structured output learning technique
US 8005774 B2Abstract
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.
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.
defining the relevance measure in the ideal query error to be a discounted cumulative gain (DCG) error.
4. The method of claim 1, wherein said defining the query error comprises:
w=is a vector of coefficients,
f(xi, w)=the relevance function evaluated on document i,
D=a discount function,
G(yi)=a mapping function for yi,
A=a non-increasing function,
π=a permutation from Uq to 1-NDq, and
π0=a permutation from Uq to 1-NDq obtained by sorting yi in descending order.
5. The method of claim 1, wherein said defining the query error comprises:
π1=a permutation from Uq to 1-NDq obtained by sorting f(xi,w) in descending order.
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.
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
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.
The query error, as defined herein, is a continuous upper bound of an ideal query error. For a provided relevance measure, such as the Discounted Cumulative Gain (DCG), the ideal query error is defined as the difference between the best possible value of the relevance measure and the value corresponding to the ranking induced by the relevance function. Because the ideal query error depends on a sorting operation, the ideal query error is not continuous. Therefore, it is conventionally difficult to find the coefficients of the ranking function which minimize the sum of the query errors. In an aspect of the present invention, the continuous upper bound of the ideal query error can be optimized efficiently by gradient descent. This upper bound can be derived using the structured output learning framework, for example.
In another example, a system for determining a relevance function is provided. The system includes a relevance function constructor and a relevance function tuner. The relevance function constructor is configured to construct a relevance function based on one or more features used as predictor variables and one or more coefficients. The relevance function tuner is 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. 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.
G(y)=2y−1, D ( r ) = 1 log 2 ( r + 1 ) if r is less or equal to p; 0 otherwise,
Referring to FIG. 4, in step 406, a query error is defined. In embodiments, the query error is an error related to a particular relevance measure, such as a discounted cumulative gain (DCG) error. For a provided relevance measure, such as the DCG, the ideal query error is defined as the difference between the best possible value of the relevance measure and the value corresponding to the ranking induced by the relevance function. Because the ideal query error depends on a sorting operation, the ideal query error is not continuous. Therefore, it is conventionally difficult to find the coefficients of the ranking function which minimize the sum of the query errors. In an embodiment, the continuous upper bound of the ideal query error can be optimized efficiently by gradient descent, as further described below.
Embodiments of the present invention incorporate aspects of a structured output learning framework. For further description of a structured output learning framework, refer to Tsochantaridis et al., “Large Margin Methods for Structured and Interdependent Output Variables,” Journal of Machine Learning Research, Vol. 6, September 2005, pages 1453-1484, which is incorporated by reference herein in its entirety. In an embodiment, the structured output learning framework is applied where the input corresponds to a set of documents, the output is a ranking, and the discrepancy measure is the difference with respect to the relevance measure of two rankings.
In an embodiment, the query error is defined according to Equation 5 shown below:
max π ∑ i ∈ U q ( A ( π ( i ) ) - A ( π 0 ( i ) ) ) f ( x i , w ) + ( D ( π 0 ( i ) ) - D ( π ( i ) ) ) G ( y i ) Equation 5 where
Uq=the set of documents for the query q,
Equation 5 has been derived using the structured output learning framework mentioned above where the scoring function between the input {xi, i ε Uq}, and the output permutation π is defined as ΣiεU q A(π(i)f(xi,w).
Note that when π is a permutation obtained by sorting f(xi,w) (i.e., when π is the predicted relevance ranking), the first term ΣiεU q (A(π(i))−A(π0(i)))f(xi,w) in Equation 5 is non-negative, while the second term ΣiεU q (D(π0(i))−D((i)))G(yi) is a difference between the best DCG and the predicted DCG. As a consequence, Equation 5 is an upper bound on this difference. If f is a continuous function of the parameter vector w, so is Equation 5. Likewise, if f is a convex function in w, Equation 5 is convex because of a pointwise maximum of convex functions is convex.
Discount function D(j) may be configured to discount documents to any degree and/or manner, as desired for a particular application. For example, in an embodiment, the discount function D(j) may be expressed as shown below in Equation 6:
D ( j ) = 1 log 2 ( j + 1 ) Equation 6 D(j) can also be optionally truncated at a certain rank p, such that D(j)=0 for j>p.
The function A measures the importance of documents at different positions and can be any non-decreasing function. It can for instance be chosen to be equal to D, but in embodiments, other choices for function A may be made. In particular, function A may be tuned as described in step 416 below.
In another embodiment, the query error is defined according to Equation 7 shown below:
max π ∑ i ∈ U q ( A ( π ( i ) ) - A ( π 1 ( i ) ) ) f ( x i , w ) + ( D ( π 0 ( i ) ) - D ( π ( i ) ) ) G ( y i ) Equation 7 where
As in Equation 5, Equation 7 is a continuous upper bound on the difference between the best DCG and the predicted DCG. Moreover, this upper bound is tighter than the one provided in Equation 5. However, even if f is convex in w, Equation 7 may not necessarily be convex.
In step 408, an objective function that depends on the defined query error is defined. The objective function may be defined to be a sum over a set of queries of the defined query error, a weighted sum over the set of queries of the defined query error, or a regularized sum over the set of queries of the defined query error, in some example embodiments.
In an embodiment, Equation 9 shown below may be used to calculate a sum of query errors based on the defined query error of Equation 5:
In an embodiment, Equation 10 shown below may be used to calculate a sum of query errors based on the defined query error of Equation 7:
In step 410, values for the coefficients of the relevance function are determined to substantially minimize an objective function that depends on the defined query error. For example, in an embodiment where the objective function is a sum over a set of queries of the defined query error, this minimization may be carried out through the process shown in FIG. 6. FIG. 6 shows a flowchart 600 for determining values for the coefficients of the relevance function in step 410 of flowchart 400, according to an example embodiment of the present invention. Flowchart 600 determines values for the coefficients according to an example gradient descent technique. In further embodiments, techniques other than shown in FIG. 6, such as those described in the previous paragraph, may be used to determine values for the coefficients. Further structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart 600. Flowchart 600 is described as follows.
Flowchart 600 begins with step 602. In step 602, the one or more coefficients is/are initialized. The weight vector w, which contains the coefficients of the relevance function, can be initialized to a random vector, or may be initialized to vector that has already been determined (e.g., by a different optimization technique). For instance, w may be initialized to a value of w0 determined by a regression solution, such as where w is selected to minimize the mean squared error, as described in U.S. Pat. No. 7,197,497 to David Cossack, which was incorporated herein by reference in its entirety further above.
In step 604, a permutation maximizing the query error is calculated for each query. When the query error is defined as a maximum over permutations such as Equation 5 or Equation 7, step 604 computes for each query the permutation that maximizes the query error. For Equations 5 and 7, this is a linear assignment problem (also called bipartite graph matching) which can solved in polynomial time using suitable algorithms, such as the Kuhn-Munkres algorithm. Linear assignment problem solving techniques, such as the Kuhn-Munkres algorithm, are well known to persons skilled in the relevant art(s). When several permutations maximizing the query error exist, one of them may be selected for further processing according to flowchart 600 in any manner, including selecting one of them at random.
In step 606, an objective function and a gradient of the objective function are calculated. The objective function defined in step 408 is calculated over the number of queries, nq, with the relevance function having coefficients as initialized in step 602 (first iteration) or as modified as described below (e.g., as modified in step 606 for a subsequent iteration). Because the permutations maximizing the query errors have be found in step 604, it is straightforward to compute the objective function and its gradient.
In step 608, the one or more coefficients is/are modified in a negative direction of the calculated gradient. Values of the one or more coefficients may be modified by any amount, as appropriate for the particular application. In one example embodiment, the values of the coefficients may be modified through a “line search,” where an approximate minimum of the function along the gradient direction is found.
Note that the objective function is non-differentiable. Non-differentiability occurs when the permutation maximizing the query error is not unique. As explained above, in this case, we may select any maximizer (e.g., selected at random). Thus, to be more precise, the described technique is not a typical gradient descent algorithm, but instead is a subgradient descent algorithm (which may be considered a form of gradient descent algorithm). However, such a technique can be slow to converge, and therefore, an alternative non-differentiable optimization technique may be used, such as the so-called bundle method. Bundle methods are well known to persons skilled in the relevant art(s).
In step 610, whether the training is complete is evaluated. For instance, in an embodiment, if the norm of the calculated gradient is less than a predetermined value, the training is determined to be complete. If the norm of the calculated gradient is greater than the predetermined value, the training is determined to not be complete. If the training is determined to be complete in step 610, operation proceeds to step 612. If the training is determined to not be complete in step 610, operation proceeds to step 604. In such case (training not complete), step 604 can be repeated (recalculating for each query the permutation maximizing the query error), step 606 can be repeated (recalculating the objective function and recalculating the gradient), and step 608 can be repeated (modifying the one or more coefficients in a negative direction of the recalculated gradient). Step 610 may then be repeated to determine whether training is complete, with steps 604, 606, and 608 being repeated until training is determined to be complete in step 610.
In step 612, flowchart 600 is completed. In an embodiment, as shown in FIG. 4, operation may proceed to step 412 if it is desired to test the relevance function generated by steps 402-410 of flowchart 400. Alternatively, operation of flowchart 400 may be complete after completion of flowchart 600.
In step 416, at least one parameter of the defined query error is adjusted. For example, the function A of Equation 5 or 7 may be adjusted. After step 416 is complete, operation proceeds to step 410. Steps 416, 410, and 412 may be repeated as many times as necessary, until the performance of the relevance function is determined to be sufficient in step 414.
Relevance function tuner 704 is configured to determine values for the one or more coefficients of the relevance function to substantially minimize a defined objective function, such as an objective function of the sum of query errors defined by Equation 5 shown above. As shown in FIG. 7, relevance function tuner 704 includes a query error function 724, which may be Equation 5. Thus, in an embodiment, relevance function tuner 704 may store/utilize the query error defined in step 406, and may perform step 410 to determine values for the coefficients of base relevance function 708. As shown in FIG. 7, relevance function tuner 704 receives base relevance function 708, feature vectors 720 for each document of each query to be processed, and a first portion 722 a of training information 118 having training queries, retrieved documents, and relevance scores (e.g., generated by human subjects 110). In embodiments, relevance function tuner 704 determines values for the one or more coefficients of base relevance function 708 using a gradient descent technique (e.g., according to flowchart 600 of FIG. 6), a gradient boosting procedure, or other technique described elsewhere herein or otherwise known, such as utilizing Equation 9 or Equation 10 (if a regularized sum is used).
Relevance function tuner 704 generates a determined relevance function 716 formed from base relevance function 708 with coefficients having values as determined by relevance function tuner 704. Relevance function tester 706 receives determined relevance function 716. Relevance function tester 706 is configured to test determined relevance function 716. For example, in an embodiment, relevance function tester 706 may perform steps 412 and 414, as described above. In an embodiment, relevance function tester 706 may receive a second portion 722 b of training information 118, having test queries, retrieved documents, and relevance scores (e.g., generated by human subjects 110). If relevance function tester 706 determines that the performance of determined relevance function 716 is not sufficient, relevance function tester 706 generates an indication 718 that is received by relevance function tuner 704. If relevance function tuner 704 receives indication 718, relevance function tuner 704 is configured to adjust one or more parameters of the defined query error. Relevance function tuner 704 may then re-determine values of the coefficients of the relevance function, and generate a re-determined version of relevance function 716 for test by relevance function tester 706.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS7197497Apr 25, 2003Mar 27, 2007Overture Services, Inc.Method and apparatus for machine learning a document relevance functionUS20040215606 *Apr 25, 2003Oct 28, 2004David CossockMethod and apparatus for machine learning a document relevance functionUS20070094171Dec 16, 2005Apr 26, 2007Microsoft CorporationTraining a learning system with arbitrary cost functions* Cited by examinerNon-Patent CitationsReference1"What is overfitting and how can I avoid it?", Part 3 of 7 of a posting to Usenet newsgroup comp.ai.neural-nets, Copyright 2002 by Warren S. Sarle, Cary, North Carolina; http://www.faqs.org/faqs/ai-faq/neural-nets/part3/section-3.html, (2002), 3 pages.2 *Burges et al., Learning to Rank using Gradient Descent, Proceedings of the 22nd International Conference on Machine Learning, Bonn, Germany, 2005.3Burges, Christopher J., et al., "Learning to Rank with Nonsmooth Cost Functions", Neural Information Processing Systems Conference, Vancouver, B.C., (2006), 8 pages.4Le, Quoc V., et al., "Direct Optimization of Ranking Measures", arXiv:0704.3359v1 [cs.IR], (Apr. 25, 2007), 25 pages.5Tsochantaridis, Ioannis et al., "Large Margin Methods for Structured and Interdependent Output Variables", Journal of Machine Learning Research 6, (2005), 1453-1484.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8326845Jan 24, 2012Dec 4, 2012Vast.com, Inc.Predictive conversion systems and methodsUS8375037Jan 24, 2012Feb 12, 2013Vast.com, Inc.Predictive conversion systems and methodsUS8868572Oct 30, 2012Oct 21, 2014Vast.com, Inc.Predictive conversion systems and methodsUS9104718Jun 26, 2013Aug 11, 2015Vast.com, Inc.Systems, methods, and devices for measuring similarity of and generating recommendations for unique itemsUS9324104Jul 2, 2015Apr 26, 2016Vast.com, Inc.Systems, methods, and devices for measuring similarity of and generating recommendations for unique itemsUS9465873Jun 21, 2013Oct 11, 2016Vast.com, Inc.Systems, methods, and devices for identifying and presenting identifications of significant attributes of unique itemsClassifications U.S. Classification706/16, 707/728International ClassificationG06F17/30, G06F15/18, G06F17/10Cooperative ClassificationG06F17/30867European ClassificationG06F17/30W1FLegal EventsDateCodeEventDescriptionNov 28, 2007ASAssignmentOwner name: YAHOO! INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:CHAPELLE, OLIVIER;REEL/FRAME:020171/0048Effective date: 20071127Feb 11, 2015FPAYFee paymentYear of fee payment: 4Apr 18, 2016ASAssignmentOwner name: EXCALIBUR IP, LLC, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:YAHOO! INC.;REEL/FRAME:038383/0466Effective date: 20160418Jun 1, 2016ASAssignmentOwner name: YAHOO! INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:EXCALIBUR IP, LLC;REEL/FRAME:038951/0295Effective date: 20160531Jun 3, 2016ASAssignmentOwner name: EXCALIBUR IP, LLC, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:YAHOO! INC.;REEL/FRAME:038950/0592Effective date: 20160531RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services