Information Technology Reference
In-Depth Information
17.3.2 For Subset Ranking
In [ 14 ], the stability theory [ 6 ] is extended to perform query-level generalization
analysis on the pairwise approach, under the framework of subset ranking. In par-
ticular, the average view is taken in the analysis.
To assist the analysis, the concept of uniform leave-one-query-out pairwise loss
stability (also referred to as query-level stability for short) is proposed in [ 14 ]. Sup-
pose we have learned a ranking model f 1 from a training set with n queries, using
an algorithm
.
Then we randomly remove a query and all its associated document pairs from the
training data, and learn a ranking model f 2 from the new training set. If the dif-
ference between the losses with respect to f 1 and f 2 on any unseen document pair
(x u ,x v ) is smaller than τ(n) , we say the algorithm
A
. Suppose L is the loss function that is minimized in algorithm
A
has uniform leave-one-query-
out pairwise loss stability with coefficient τ with respect to L .
Based on the concept of the query-level stability, a query-level generalization
bound has been derived in [ 14 ], as shown in Theorem 17.8 . The theorem states that if
a pairwise ranking algorithm has query-level stability, then with a large probability,
the expected query-level risk can be bounded by the empirical query-level risk and
a term that depends on the query number and the stability of the algorithm.
A
be a pairwise ranking algorithm , (q 1 ,S ( 1 ) ),...,(q n ,S (n) ) be
n training queries and their associated labeled documents , and let L be the pairwise
loss function . If
1.
Theorem 17.8 Let
A
(q 1 ,S ( 1 ) ), . . . , (q n ,S (n) ),
2
q
Q
,(x u ,x v ,y u,v )
X
× Y
,
|
L(f (q i ,S (i) ) i = 1 ;
x u ,x v ,y u,v )
|≤
B ,
2.
A
has query-level stability with coefficient τ ,
(q i ,S (i) )
n
i
{
}
then with probability at least 1
δ( 0 <δ< 1 ) over the samples of
in the product space i = 1 { Q ×
=
1
2
) }
(
X
× Y
, the following inequality holds :
log δ
2 n
+ 4 nτ (n)
B
R(f
+
+
R(f
1 )
1 )
2 τ(n)
.
(17.13)
n
i =
n
i =
{ (q i ,S (i) ) }
{ (q i ,S (i) ) }
When using this theorem to perform the query-level generalization analysis on
pairwise ranking algorithms, what one needs to do is to compute the query-level
stability coefficient τ(n) of the algorithms.
For example, as shown in [ 14 ], Ranking SVM [ 11 , 12 ] has a query-level stability
with coefficient τ(n)
4 κ 2
m (i)
˜
m (i) is the number of document
=
λn ×
max
m (i) , where
˜
n i = 1
1
κ 2 <
pairs associated with query q i , and
. On this basis, one
can have the following discussions regarding the query-level generalization ability
of Ranking SVM.
x
X
,K(x,x)
When the number of training queries approaches infinity, with a large probability
the empirical risk of Ranking SVM will converge to its expected risk, at a rate of
O( 1
n ) .   Search WWH ::

Custom Search