Enhanced Training Data for Learning-To-Rank

• US 20120109860A1
• Filed: 11/03/2010
• Published: 05/03/2012
• Est. Priority Date: 11/03/2010
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Hang, Xu, Gu, Xu, Jingfang
• Application Number:
  US12/939,008
• Publication Number:
  US 20120109860A1
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Training data is used by learning-to-rank algorithms for formulating ranking algorithms. The training data can be initially provided by human judges, and then modeled in light of user click-through data to detect probable ranking errors. The probable ranking errors are provided to the original human judges, who can refine the training data in light of this information.

Claims

1. A method of producing training data for a learning-to-rank algorithm, the method comprising:

obtaining {x^m}_m=1^M corresponding to {d^m}_m=1^M where x is a set of click-through data corresponding to a set of search results d;

modeling the training data in accordance with the following conditional probability function that indicates the probability of y given x;

2. A method as recited in claim 1, wherein {y*^m}_m=1^M is calculated in accordance with the following equation:

y*=arg max_yPr_θ

(y|x).

3. A method as recited in claim 1, further comprising correcting the existing rankings based on the predicted rankings.

4. A method as recited in claim 1, further comprising obtaining the existing rankings from human judges.

5. A method of producing training data for a learning-to-rank algorithm, the method comprising:

obtaining {x^m}_m=1^M corresponding to {d^m}_m=1^M where x is a set of click-through data corresponding to a set of search results d;

modeling the training data in accordance with the following conditional probability function that indicates the probability of y given x;

6. A method as recited in claim 5, further wherein {y*^m}_m=1^M is calculated using quadratic programming relaxation.

7. A method as recited in claim 5, further comprising correcting the existing rankings based on the predicted rankings.

8. A method as recited in claim 5, further comprising obtaining the existing rankings from human judges.

9. A method of producing training data for a learning-to-rank algorithm, the method comprising:

modeling search results as having rankings according to relevance to a query;

further modeling the ranking of any particular search result as depending on the relevance of search results other than the particular search result;

calculating model parameters for the modeling based on (a) existing rankings of the search results and (b) click-through data corresponding to the search results; and

calculating predicted rankings of the search results based on the modeling using the model parameters and the click-through data corresponding to the search results.

10. A method as recited in claim 9, further comprising comparing the predicted rankings with the existing rankings to produce enhanced rankings.

11. A method as recited in claim 9, further comprising obtaining the existing rankings from human judges.

12. A method as recited in claim 9, further comprising assuming within the modeling that the relevance of any individual search result depends on the relevance of an adjacent search result that is adjacent to the individual search result in an ordering of the search results based on their rankings.

13. A method as recited in claim 12, wherein the modeling is performed in accordance with the following equation:

14. A method as recited in claim 13, wherein:

Z(x)=Σ

_yexp(Σ

_i,kλ

_kⁱf_k(y_i-1,y_i,x)+Σ

_i,kμ

_kⁱg_k(y_i,x)).

15. A method as recited in claim 13, wherein calculating the model parameters comprises identifying the model parameters θ

=(λ

₁, λ

₂ . . . ;

μ

₁, μ

₂ . . . ) that maximize the log-likelihood objective function of {(x^m, y^m)}_m=1^M with respect to the modeling.

16. A method as recited in claim 13, wherein calculating the model parameters comprises identifying the model parameters θ

=(λ

₁, λ

₂ . . . ;

μ

₁, μ

₂ . . . ) in accordance with the following;

θ

=arg max_θ

L(θ

)=arg max_θ

Σ

_m=1^M log(Pr_θ

(y^m|x^m)).

17. A method as recited in claim 9, further comprising assuming within the modeling that the relevance of any individual search result depends on the relevance of all other search results.

18. A method as recited in claim 17, wherein the modeling is performed in accordance with the following equation:

19. A method as recited in claim 18, wherein:

Z(x)=Σ

_yexp(Σ

_i,j,kλ

_k^i,jf_k(y_i,y_j,x)+Σ

_i,kμ

_kⁱg_k(y_i,x)).

20. A method as recited in claim 18, wherein calculating the model parameters comprises identifying the model parameters θ

=(λ

₁, λ

₂ . . . ;

μ

₁, μ

₂ . . . ) that maximize the log-likelihood objective function of {(x^m, y^m)}_m=1^M with respect to the modeling.