Information Technology Reference
In-Depth Information
Table 17.2
Uniform generalization bounds for ranking
Approaches
Document ranking
Subset ranking
Two-layer ranking
Pointwise
-
-
-
Pairwise
[
2
,
9
,
10
,
15
]
-
[
8
]
Listwise
-
[
13
]
-
Table 17.3
Algorithm-dependent bounds for ranking
Approaches
Document ranking
Subset ranking
Two-layer ranking
Pointwise
-
-
-
Pairwise
[
1
,
3
]
[
14
]
-
Listwise
-
-
-
17.5 Exercises
17.1 Two-layer learning is meaningful not only for information retrieval, but also
for many other applications. Please give two example applications where there
are hierarchical structures in the data, and two-layer sampling is needed to
generate the training data.
17.2 Investigate whether RankBoost, RankNet, and FRank are stable with respect
to their pairwise loss functions, and derive their stability coefficients if they
exist.
17.3 Investigate whether ListNet and ListMLE are stable with respect to their list-
wise loss functions, and derive their query-level stability coefficients if they
exist.
17.4 Generalization analysis is mainly a theoretical tool. However, the result can
also be empirically verified to some extent. Design an experiment to validate
the results presented in Sect.
17.2.3
.
References
1. Agarwal, S.: Generalization bounds for some ordinal regression algorithms. In: Proceedings
of the 19th International Conference on Algorithmic Learning Theory (ALT 2008), pp. 7-21
(2008)
2. Agarwal, S., Graepel, T., Herbrich, R., Har-Peled, S., Roth, D.: Generalization bounds for the
area under the roc curve. Journal of Machine Learning
6
, 393-425 (2005)
3. Agarwal, S., Niyogi, P.: Stability and generalization of bipartite ranking algorithms. In: Pro-
ceedings of the 18th Annual Conference on Learning Theory (COLT 2005), pp. 32-47 (2005)
4. Bartlett, P.L., Mendelson, S.: Rademacher and Gaussian complexities risk bounds and struc-
tural results. Journal of Machine Learning
3
, 463-482 (2003)
5. Bousquet, O., Boucheron, S., Lugosi, G.: Introduction to statistical learning theory. In: Ad-
vanced Lectures on Machine Learning, pp. 169-207. Springer, Berlin (2004)
