Gradient based optimization of a ranking measure
View Patent ↗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. A query error is defined that measures a difference between a relevance ranking generated by the relevance function and a training set relevance ranking based on a query and a set of scored documents associated with the query. The query error is a continuous function of the coefficients and aims at approximating errors measures commonly used in Information Retrieval. Values for the coefficients of the relevance function are determined that substantially minimize an objective function that depends on the defined query error.
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 using at least one processor;
parameterizing the relevance function by one or more coefficients;
defining a query error that measures, for a given query, a difference between a ranking generated by the relevance function and a ranking based on a training set, the defined query error being a continuous function of coefficients, wherein said defining comprises defining the query error as a difference between an optimal discounted cumulative gain (DCG) function and an approximated version of a DCG; and
determining values for the coefficients of the relevance function that substantially minimize an objective function that depends on the defined query error.
2. The method of claim 1 , wherein said defining comprises:
defining the query error to be an approximation of 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 as a difference between an optimal DCG function and an approximated version of a DCG comprises:
defining the query error as
max
π
∑
i
∈
U
q
D
(
π
(
i
)
)
G
(
y
i
)
-
∑
j
=
1
ND
q
D
(
j
)
∑
i
∈
U
q
G
(
y
i
)
h
ij
∑
i
∈
U
q
h
ij
where
D(j)=a discount function,
NDq=a number of documents in the set of documents for the query,
Uq=the set of documents for the query,
π=a permutation from Uq to 1-NDq,
y i =a training relevance for document i,
G(y i )=a mapping function for y i , and
h ij =a continuous version of an indicator function where document i is ranked in a position j by the relevance function.
5. The method of claim 4 , wherein said defining comprises:
defining h ij as
h
ij
=
exp
(
-
f
(
x
i
,
w
)
-
f
(
r
(
j
)
,
w
)
2
2
σ
2
)
,
where
x i =a feature vector containing evaluated feature information for document i of the set of documents,
r(j)=the j-th document in the ranking induced by the relevance function,
w=a coefficient vector,
f(x i , w)=the relevance function evaluated on document i, and
σ=a smoothing length-scale parameter.
6. The method of claim 4 , further comprising:
testing the relevance function having the determined values for the one or more coefficients.
7. The method of claim 5 , further comprising:
adjusting the σ 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.
8. The method of claim 6 , further comprising:
enabling the relevance function to be used to rank documents returned by queries if the relevance function satisfies said testing.
9. The method of claim 3 , wherein 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 comprises:
initializing the one or more coefficients;
calculating a sum of query errors based on the defined query error for a plurality of queries;
calculating a gradient of the calculated sum of the query errors; and
modifying the one or more coefficients in a negative direction of the calculated gradient.
10. The method of claim 9 , wherein if the calculated gradient is greater than a predetermined value, repeating said calculating the sum of query errors, said calculating the gradient, and said modifying the one or more coefficients in a negative direction of the calculated gradient.
11. The method of claim 9 , wherein said calculating a sum of query errors based on the defined query error for a plurality of queries comprises:
calculating a regularized sum of query errors based on the defined query error for a plurality of queries.
12. The method of claim 11 , wherein said calculating a regularized sum of query errors based on the defined query error for a plurality of queries comprises:
calculating the regularized sum of query errors according to
λ
2
w
-
w
0
2
+
∑
q
=
1
n
q
(
max
π
∑
i
∈
U
q
D
(
π
(
ⅈ
)
)
G
(
y
i
)
-
∑
j
=
1
NDq
D
(
j
)
∑
i
∈
U
q
G
(
y
i
)
h
ij
∑
i
∈
U
q
h
ij
)
,
where
λ=a regularization parameter,
w 0 =a weight vector, and
n q =a number of queries.
13. The method of claim 3 , wherein the objective function is a weighted 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 weighted sum over a set of queries of the defined query error.
14. A system for determining a relevance function, comprising:
at least one server that includes at least one processor;
a relevance function constructor implemented at least partially by the at least one processor 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 to substantially minimize an objective function that depends on a query error, wherein the query error measures a difference between a ranking generated by the relevance function and a ranking based on a training set, wherein the query error is a continuous function of coefficients, wherein the query error is defined as a difference between an optimal discounted cumulative gain (DCG) function and an approximated version of a DCG.
15. The system of claim 14 , wherein the query error is an approximation of a discounted cumulative gain (DCG) error.
16. The system of claim 14 , wherein the objective function is a sum over a set of queries of the query error.
17. The system of claim 16 , wherein the query error is
max
π
∑
i
∈
U
q
D
(
π
(
ⅈ
)
)
G
(
y
i
)
-
∑
j
=
1
NDq
D
(
j
)
∑
i
∈
U
q
G
(
y
i
)
h
ij
∑
i
∈
U
q
h
ij
where
D(j)=a discount function,
NDq=a number of documents in the set of documents for the query,
Uq=the set of documents for the query,
π=a permutation from Uq to 1-NDq,
y i =a training relevance for document i,
G(y i )=a mapping function for y i , and
h ij =a continuous version of an indicator function where document i is ranked in a position j by the relevance function.
18. The system of claim 17 , wherein
h
ij
=
exp
(
-
f
(
x
i
,
w
)
-
f
(
r
(
j
)
,
w
)
2
2
σ
2
)
,
where
x i =a feature vector containing evaluated feature information for document i of the set of documents,
r(j)=the j-th document in the ranking induced by the relevance function,
w=a coefficient vector,
f(x i , w)=the relevance function evaluated on document i, and
σ=a smoothing length-scale parameter.
19. The system of claim 18 , 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.
20. The system of claim 19 , wherein the relevance function tuner is configured to adjust the σ 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.
21. The system of claim 16 , wherein the relevance function tuner is configured to initialize the one or more coefficients, to calculate a sum of query errors based on the query error for a plurality of queries, to calculate a gradient of the calculated sum of the query errors, and to modify the one or more coefficients in a negative direction of the calculated gradient.
22. The system of claim 21 , wherein if the calculated gradient is greater than a predetermined value, the relevance function tuner is configured to recalculate the sum of query errors, to recalculate the gradient, and to repeat modification of the one or more coefficients in a negative direction of the recalculated gradient.
23. The system of claim 21 , wherein the relevance function tuner is configured to calculate a regularized sum of query errors based on the query error for a plurality of queries to calculate the sum of query errors.
24. The system of claim 16 , wherein the objective function is a weighted sum over a set of queries of the defined query error.
25. A tangible 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 to substantially minimize a query error, wherein the query error measures a difference between a ranking generated by the relevance function and a ranking based on a training set, wherein the query error is a continuous function of coefficients, wherein the query error is defined as a difference between an optimal discounted cumulative gain (DCG) function and an approximated version of a DCG.