9.4 Multi-class algorithm based on RankBoost. This problem requires familiarity with the material presented both in this chapter and in chapter 10. An alternative boosting-type multi-class classication algorithm is one based on a ranking criterion. We will dene and examine that algorithm in the mono-label setting.

Let H be a family of base hypotheses mapping XY to f????1; +1g. Let F be the following objective function dened for all samples S = ((x1; y1); : : : ; (xm; ym)) 2 (X  Y)m and  = (1; : : : ; N) 2 RN, N  1, by F( ) = Xm i=1 X l6=yi e????(fN(xi;yi)????fN(xi;l)) = Xm i=1 X l6=yi e????
PN j=1 j (hj (xi;yi)????hj (xi;l)):
(9.26)
where fN = PN j=1 jhj .

(a) Show that F is convex and dierentiable.

(b) Show that 1 m Pm i=1 1fN (xi;yi)  1 k????1F( ), where fN = PN j=1 jhj .

(c) Give the pseudocode of the algorithm obtained by applying coordinate descent to F. The resulting algorithm is known as AdaBoost.MR. Show that AdaBoost.MR exactly coincides with the RankBoost algorithm applied to the problem of ranking pairs (x; y) 2 X  Y. Describe exactly the ranking target for these pairs.

(d) Use question (9.4b) and the learning bounds of this chapter to derive marginbased generalization bounds for this algorithm.

(e) Use the connection of the algorithm with RankBoost and the learning bounds of chapter 10 to derive alternative generalization bounds for this algorithm.
Compare these bounds with those of the previous question.