A General Boosting Method and its Application to Learning Ranking Functions for Web Search
Zhaohui Zheng Hongyuan Zha Tong Zhang Olivier Chapelle Keke Chen Gordon Sun Yahoo! Inc. 701 First Avene Sunnyvale, CA 94089 zhaohui,tzhang,chap,kchen,gzsun @yahoo-inc.com College of Computing Georgia Institute of Technology Atlanta, GA 30032 zha@cc.gatech.edu

Abstract
We present a general boosting method extending functional gradient boosting to optimize complex loss functions that are encountered in many machine learning problems. Our approach is based on optimization of quadratic upper bounds of the loss functions which allows us to present a rigorous convergence analysis of the algorithm. More importantly, this general framework enables us to use a standard regression base learner such as single regression tree for fitting any loss function. We illustrate an application of the proposed method in learning ranking functions for Web search by combining both preference data and labeled data for training. We present experimental results for Web search using data from a commercial search engine that show significant improvements of our proposed methods over some existing methods.

1 Introduction
There has been much interest in developing machine learning methods involving complex loss functions beyond those used in regression and classification problems [13]. Many methods have been proposed dealing with a wide range of problems including ranking problems, learning conditional random fields and other structured learning problems [1, 3, 4, 5, 6, 7, 11, 13]. In this paper we propose a boosting framework that can handle a wide variety of complex loss functions. The proposed method uses a regression black box to optimize a general loss function based on quadratic upper bounds, and it also allows us to present a rigorous convergence analysis of the method. Our approach extends the gradient boosting approach proposed in [8] but can handle substantially more complex loss functions arising from a variety of machine learning problems. As an interesting and important application of the general boosting framework we apply it to the problem of learning ranking functions for Web search. Specifically, we want to rank a set of documents according to their relevance to a given query. We adopt the following framework: we extract so that we can rank the a set of features for each query-document pair, and learn a function documents using the values , say with larger values are ranked higher. We call such a function a ranking function. In Web search, we can identify two types of training data for learning a ranking function: 1) preference data indicating a document is more relevant than another with respect to a query [11, 12]; and 2) labeled data where documents are assigned ordinal labels representing degree of relevancy. In general, we will have both preference data and labeled data for 1

 
Љ ЄІ ЈЇЅ

 
Ѓ

Љ ЄІ ЈЅ

 
Ё

Є

Ё

Љ ЄІ ЈЇЅ

 
Ђ Є Љ ЄІ ЈЇЅ


training a ranking function for Web search, leading to a complex loss function that can be handled by our proposed general boosting method which we now describe.

2 A General Boosting Method

where denotes a prediction function which we are interested in learning from the data, is a prechosen function class, and is a risk functional with respect to . We consider the following form of the risk functional :

For example, each function can be a single variable function ( ) such as in regression: ; or a two-variable function ( ), such as those in ranking based on pairwise comparisons: , where indicates whether is preferred to or not; or it can be a multi-variable function as used in some structured prediction problems: , where is a loss function [13]. Assume we do not have a general solver for the optimization problem (1), but we have a learning algorithm which we refer to as regression weak learner. Given any set of data points , with corresponding target values , weights , and , the regression weak learner produces a function such tolerance that

(3)

Friedman [8] proposed a solution when the loss function in (2) can be expressed as

which he named as gradient boosting. The idea is to estimate the gradient using regression at each step with uniform weighting, and update. However, there is no convergence proof. Following his work, we consider an extension that is more principly motivated, for which a convergence analysis can be obtained. We first rewrite (2) in the more general form: (5) 1 where . Note that depends on only through the function values and from now on we identify the function with the vector . Also the function is considered to be a function of variables.

where lies between and . The right hand side is almost quadratic, and we can then replace it by a quadratic upper-bound

1 We consider that all inequality.

are different, but some of the

in (2) might have been identical, hence the

2

 Ѕ

V  y   y q 6 o w o  o 194І 2 |194І 2 @Љ o c 2 x Љ o b94І 2 i Љ  Ѕ  ЉЅ І Ѕ A   9Ѕ o 9Ѕ q 6 o c4І 2 i w o  o )94І 2 |1e4І 2 @Љ o b94І 2 Љ Ѕ  Љ  Ѕ  ЉЅ  Ѕ

2

Our main observation is that for twice differentiable risk functional we can expand around using Taylor expansion as

, at each tentative solution

 }8

Our goal is to use this weak learner to solve the original optimization problem (1). Here , i.e., can be expressed as with .

(4)

(6)

GЅ

u  Љl6 6 6 iІ  ht77sf r 4qp o  d 6``` e TSRS6 G  ji k   k

V Ѕ6``` bU aSRSR6 G Ѕ

where

is a loss function with respect to the first

arguments

8

Љ ЈЇЅ ЄІ

E

Љ ЄІ Ѕ YЉ Ј4І

E

E

I  Љ 6 ЅІ  g Љ  6 ЅІ   Љ 6 XІ      Љ X cX 4Ha4hЇ75ЈyЇ5yYtscY6 V U aRRSR6 i G 4І Ѕ6``` Ѕ IЅ E Ѓ  X iЉ Ѕ pYЉ i g G 4ug yxutscX 6 i a6 G 4І ЅІ X 6 wІ v  !  Љ ЅЅ I A 1Ђ A q r d iЉ X g ЅІ  Љ X6 Ѕ pch4fbeY4І I E d A I E E Љ V Ѕ6``` Ѕ cX 6 bU aRSRR6 G 4І Ed E IG HF E B @54І 2 6 X6 V ЄІ Ѕ 6 Q Q Q 6 7Љ E Y7Љ WU P ЈTRSR7Љ G P ЈЇ4І ЄІ Ѕ ЉЅ

`Tl| i Љ v HЉ v ЈІ o І v gЄ h k

2

I


u q v Ѕ

E

Ѕ

d ЄІ 4Љ ЈЇЅ Ѕ Ѕ 2 6ЉЉ  ЄІ Ѕ 6 ` ` 6 ЄІ Ѕ 7YЈЇaRSE` RR7Љ G ЈЇ4І 2 @54І 2 ЉЅ

d 6``` S RRSR6 G  gf h h

E

A

ЉЄ ЈІ v Ѕ v Їv @ЈЅ    Љ ЄІ

I GHF 67ЉYЉ ЈІЇЅ4І Є ЉЅ w54І 2 C ED

6 Љ Ѕ 2 % 0 $!'    754І 3&1)" Ѕ #(  E E E  E

We consider the following general optimization problem:

(1)

GHF v z G wF v %{ u y1( ! # gЄ x i Љ v HЉ v ЈІ o І v kD h D 

C ED A 

ЉЅ 94І 2  5Ѕ

2

ЉЅ 54І 2

8 qЅ

E

dx

wnm$l d Є6``` eYRSRR6 G Є  


Ѕ

Љ uІ %   Ї~19p


Ѕ

(2) .

,


is a diagonal matrix upper bounding the Hessian between and . If we define , then is equal to the above quadratic form (up to a constant). So can be found by calling the regression weak learner . Since at each step we try to minimize an upper bound of , if we let the minimum be , it is clear that . This means that by optimizing with respect to the problem that can be handled by , we also make progress with respect to optimizing . The algorithm based on this idea is listed in Algorithm 1 for the loss function in (5). Convergence analysis of this algorithm can be established using the idea summarized above; see details in appendix. However, in partice, instead of the quadratic upper bound (which has a theoretical garantee easier to derive), one may also consider minimizing an approximation to the Taylor expansion, which would be closer to a Newton type method.

Algorithm 1 Greedy Algorithm with Quadratic Approximation Input: let for let , with either or % Newton-type method with diagonal Hessian global diagonal upper bound on the Hessian % Upper-bound minimization let , where pick let pick step-size , typically by line search on let end The main conceptual difference between our view and that of Friedman is that he views regression as a "reasonable" approximation to the first order gradient , while our work views it as a natural consequence of second order approximation of the objective function (in which the quadratic term serve as an upper bound of the Hessian either locally or globally). This leads to algorithmic difference. In our approach, a good choice of the second order upper bound (leading to tighter bound) may require non-uniform weights . This is inline with earlier boosting work in which samplereweighting was a central idea. In our framework, the reweighting naturally occurs when we choose a tight second order approximation. Different reweighting can affect the rate of convergence in our analysis. The other main difference with Friedman is that he only considered objective functions of the form (4); we propose a natural extension to the ones of the form (5).

3 Learning Ranking Functions
We now apply Algorithm 1 to the problem of learning ranking functions. We use preference data as well as labeled data for training the ranking function. For preference data, we use to mean that is preferred over or should be ranked higher than , where and are the feature vectors for corresponding items to be ranked. We denote the set of available preferences as In addition to the preference data, there are also labeled data, where is the feature of an item and is the corresponding numerically coded label.2 We formulate the ranking problem as computing a ranking function , such that satisfies as much as possible the set of preferences, i.e., , if while at the same time matches the label in a sense to be detailed below.
2 Some may argue that, absolute relevance judgments can also be converted to relative relevance judgments. and labeled as perfect, good, and bad, For example, for a query, suppose we have three documents is preferred over , is preferred respectively. We can obtain the following relative relevance judgments: over and is preferred over . However, it is often the case in Web search that for many queries there only exist documents with a single label and for such kind of queries, no preference data can be constructed.

3

2

wАs67Љ 76 ГІ |В Д   Є fЏ Ђ  ЂE E X Ў|Є

E

ЗК Ж )Ж

6ЈY6R`R`SR6 А 6 Ќ Є ` X A 8ЈЕЅ Ѕ E E

 o 9Ѕ o 

2

X

 Ѕ

Є

З yЖ Л Ж

2

К ЖИЗ 1ЙayЖ

i pЉ v Љ v ЈІ o І v v TH o  gЄ 6 u h k X Љ ЈЇnЉ ЈЇЅ XІ Ѕ І ЄІ E Љ  ЄІ  Ѕ aeЈy9Ѓ  2 Ѓ  Ђ  G k Ѕ h 2 E ДE 2 2 E i Д

 ЉЅ 194І 2 x ) o c 2 x ) o e4І 2 ЉІ Љ  Ѕ

Л 1Ж

 o eЇ9Ќ G SeЅ Њ  Ѕ Ћ wІ ЇseЊ Љ1 aЉf ЈY4qtt o l6 6 6 iІ   wІ Їs l  P  P wF &p f  G d h i iІ Ѕ pЉaeЄЈy9Ѓ  2 ЄЂ iЃ  P    P GHF ydY   Ёi k `` 6 SR`S qa6 k  yu 6w  A eЅ w   

Є

P G d     P wF &peЄ

o

X

g v k v 4)e4І 2    v h  dЉ  Ѕ i E  Љ ГЇЅ І К 1Ж A Л Ж Є E

where

E  6 6``` Ѓ B RRSR6 ` Ѓ 6``` БYRRSR6 ws6 A X А


THE O B J E C T I V E F U N C T I O N . We use the following objective function to measure the empirical risk of a ranking function ,

The objective function consists of two parts: 1) for the preference data part, we introduce a margin parameter and would like to enforce that ; if not, the difference is quadratically penalized; and 2) for the labeled data part, we simply minimize the squared errors. The parameter is the relative weight for the preference data and could typically be found by cross-validation.

Q UA D R AT I C A P P ROX I M AT I O N . To this end consider the quadratic approximation (6) for . For simplicity let us assume that each feature vector , and only appears in and once, otherwise we need to compute appropriately formed averages. We consider

as the unknowns, and compute the gradient of with respect to those unknowns. The comis just The components of the ponents of the negative gradient corresponding to negative gradient corresponding to and , respectively, are

Both of the above equal to zero when . For the second-order term, it can be readily verified that the Hessian of is block-diagonal with -by- blocks corresponding to and and -by- blocks for . In particular, if we evaluate the Hessian at , the -by- block equals to

for with and , respectively. We can upper bound the first matrix by the diagonal matrix leading to a quadratic upper bound. We summarize the above derivations in the following algorithm.

and

The fitting of is done by using a base regressor with the above training set; We weigh the above preference data by and the labeled data by respectively. 2) forming where is found by line search to minimize the objective function. is a shrinkage factor.

The shrinkage factor by default is 1, but Friedman [8] reported better results (coming from better regularization) by taking . In general, we choose and by cross-validation. could be the degree of preference if that information is available, e.g., the absolute grade difference between each prefernce if it is converted from labeled data. Otherwise, we simply set it to be 1.0. When there is no preference data and the weak regression learner produces a regression tree, QBrank is identical to Gradient Boosting Trees (GBT) as proposed in [8]. can appear multiple times in Step 1), in this case we use the average gradient R E M A R K . An values as the target value for each distinct .

UЊ Ю 6Љ Є 7ЈІ U o U eМ G Ѕ U Ќ U Ѕ ЊЮ Ѕ g kA k ЉЄ ЈІ U o ` 6``` Ѓ B RSRR6 wБ7YЉ ГІ G Ѕ U Мg 76 ГІ  А 6Љ  Ѕ Д A Ђ 6Љ Н  71ЃМЉ ЄЈІ G Ѕ U ЅМgHЉ XЈІ G Ѕ U ЅTyw 3!ТgS6 ЈІW71МЉ ЈІ G Ѕ U hwЉ ЈІ E G Ѕ U Tyw 3! E6 ЈІ 6v X 6ЉЃ Н  Є Ѕg X Ѕ 6 v E Є Ђ Ђ Џq XY6 Ь Є ЉЈІ U Є o E ```6q SRS a6 E gd   eЅ E A

4

Э E

E

E

Algorithm 2 Boosted Ranking using Successive Quadratic Approximation (QBRank) Start with an initial guess , for , 1) we construct a training set for fitting by adding the following for each

ЉЅ 94І 2

q q Љ ЈЅ ЄІ

E

В

Н

Џ

8

The optimization problem we seek to solve is argmin function class. Note that depends only on the values using the general boosting framework discussed in section 2.

E E GHF G HF q q ` i YЉ ГІЅМg xІ Љ Д  i 1МЉ ЈЇМHЉ ЈTyw 3ЈІ Љ Ѓ Н  ЄІ Ѕ g XІ Ѕ 6 v  ! ЉЅ @54І 2 g Ђ  ED k C ED k A `ЃНМЉ ЈІЇhgHЉ ЈЇayw 3ТС)hЉ ЈМHЉ ЈЇayw 3!  ЄЅ X І Ѕ 6 v  ! g E 6 Ѓ Н E Є І Ѕ g X І Ѕ 6 v  Ђ Ђ E E E Љ ЈЅ XІ Љ E ЈЇЅ ЄІ ` І 7Љ ГЇЅРg Д Љ ГЇЅ І E ЉЅ 94І E 2 E  А 6 І Ѕ 6 6``` HБ7Љ ГПr RRRS6 wБ7Љ ЈT7Љ ЈЇЅ  А 6 XІ Ѕ 6 ЄІ Ѕ Љ ГЇa7Љ ЈЇa7Љ ЈЇЅ І Ѕ 6 XІ Ѕ 6 ЄІ 6794І 2 )' ЉЅ 0( E E E E 6``` B RRSR6 E A E  E w Ц 6 Ф Цww E w q k Н  XІ Ѕ І ЄІ БЉ ЈЇt"Љ ЈЇЅ E Љ q 6 qІ  # )aЫГ5ЪcЩ Н І XІ Ѕ g ЄІ tWЉ ЈЇЧwЉ ЈЅ Н Ш XІ Ѕ g ЄІ tbЉ ЈЇЧwЉ ЈЇЅ E X q E Ю Є Н І XІ Ѕ g ЄІ Ї"Љ ЈЇ$Љ ЈЇЅ У E О Ѕ 6E Ф ХA g A E A Є A A g У E Љ ГЅ І ЉЅ 54І 2 E A E Ш rЮ E 2 Ю E E A Є

where is some given and we can optimize it

E

E

E

E

Ѕ

A

Н

E

X 

E

Љ ЈЇЅ XІ

E

Є

k

,


4 Experiment Results
We carried out several experiments illustrating the properties and effectiveness of QBrank using combined preference data and labeled data in the context of learning ranking functions for Web search [3]. We also compared its performance with QBrank using preference data only and several existing algorithms such as Gradient Boosting Trees [8] and RankSVM [11, 12]. RankSVM is a preference learning method which learns pair-wise preferences based on SVM approach. DATA C O L L E C T I O N . We first describe how the data used in the experiments are collected. For each query-document pair we extracted a set of features to form a feature vector. which consists of three parts, where 1) the query-feature vector comprises features dependent on the query only and have constant values across all the documents in the document set, for example, the number of terms in the query, whether or not the query is a person name, etc.; 2) the document-feature vector comprises features dependent on the document only and have constant values across all the queries in the query set, for example, the number of inbound links pointing to the document, the amount of anchor-texts in bytes for the document, and the language identity of the document, etc.; and 3) the query-document feature vector which comprises features dependent on the relation of the query with respect to the document , for example, the number of times each term in the query appears in the document , the number of times each term in the query appears in the anchor-texts of the document , etc. We sampled a set of queries from the query logs of a commercial search engine and generated a certain number of query-document pairs for each of the queries. A five-level numerical grade is assigned to each query-document pair based on the degree of relevance. In total we have 4,898 queries and 105,243 query-document pairs. We split the data into three subsets as follows: 1) we extract all the queries which have documents with a single label. The set of feature , which contains around 2000 queries vectors and the corresponding labels form training set giving rise to 20,000 query-document pairs. (Some single-labeled data are from editorial database, where each query has a few ideal results with the same label. Other are bad ranking cases submitted internally and all the documents for a query are labeled as bad. As we will see those type of singlelabeled data are very useful for learning ranking functions); and 2) we then randomly split the remaining data by queries, and construct a training set containing about 1300 queries and 40,000 query-document pairs and a test set with about 1400 queries and 44,000 query-document pairs. or to generate a set of preference data as follows: given a query and two documents We use and . Let the feature vectors for and be and , respectively. If has a higher grade than , we include the preference while if has a higher grade than , we include the preference . For each query, we consider all pairs of documents within the search results for that query except those with equal grades. This way, we generate around 500,000 preference pairs in total. We denote the preference data as and corresponding to and , respectively. E VA L UAT I O N M E T R I C S . The output of QBrank is a ranking function which is used to rank the documents according to . Therefore, document is ranked higher than by the ranking function if , and we call this the predicted preference. We propose the following two metrics to evaluate the performance of a ranking function with respect to a given set of preferences which we considered as the true preferences. 1) Precision at %: for two documents and (with respect to the same query), it is reasonable to assume that it is easy to compare and if is large, and and should have about the same rank if is close to . Base on this, we sort all the document pairs according to . We call precision at %, the fraction of non-contradicting pairs in the top % of the sorted list. Precision at 100% can be considered as an overall performance measure of a ranking function. 2) Discounted Cumulative Gain (DCG): DCG has been widely used to assess relevance in the context of search engines [10]. For a ranked list of documents ( is set to be 5 in our experiments), we use the following variation of DCG, , where represents the weights assigned to the label of the document at position . Higher degree of relevance corresponds to higher value of the weight. We will use the symbol to indicate the average of this value over a set of queries in our experiments. 5

л

Э

X6 Є YЇЬ

и г и  г

з бж

E

г

X

т

г

аЯ ~~Є

X

в

iж

г

Є

Љ

Ѕ

A

х o  г А А ЈІ i  yH HF фу т G

Я Є г

X

Є

Gж


г

E

й  г

м Љ XІ Ѕ g Љ ЄІ ScЈЇ|@ЈЅ м X

Є

з Hк

iж

Љй 6в г  xІ


E

  по срtbн 

iк

в

XЄБЄ Љиг6в Ы7 xІ

X

Є

в

л

в

з "ж

ЉcЈІЇЅ X Є

Љ ЄІ ЈЅ

6d а Я 6 а Є6 Я Гб~Є YЄ а Є

Љ XІ Ѕ m Љ ЄІ cЈЂЈЅ

Љ ЄІ ЈЇЅ

Є ЄЈX


м Љ XІ Ѕ g Љ ЄІ ScЈЈЇЅ м

з бж

л

в  qЄ в Є

й г

Љ 6д6q 6w Ые  aЫ76 yxІ A й i ж г Ѕ

и  г


%K 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

QBrank 0.9446 0.903 0.8611 0.8246 0.7938 0.7673 0.7435 0.7218 0.7015 0.6834

PA R A M E T E R S. There are three parameters in QBrank: , , and . In our experiments, is the absolute grade difference between each pair . We simply set to be 0.05, and to be 0.5 without detailed tuning. For a fair comparsion, we used single regression tree with 20 leaf nodes as the base regressor of both GBT and QBrank in our experiments. E X P E R I M E N T S A N D R E S U LT S . We are interested in the following questions: 1) How does GBT using labeled data compare with QBrank or RankSVM using the preference data extracted from in GBT and QBrank? the same labeled data: ? and 2) Is it useful to include single-labeled data To this end, we considered the following six experiments for comparison: 1) GBT using , 2) GBT using , 3) GBT using , 4) RankSVM using , 5) QBrank using , and 6) QBrank using . Table 1 presents the precision at % on data for the ranking function learned from GBT with labeled training data , and QBrank and RankSVM with the corresponding preference data . This shows that QBrank outperforms both GBT and RankSVM with respect to the precision at % metric. The DCG-5 for RankSVM using is 6.181 while that for the other five methods are shown in Figure 1, from which we can see it is useful to include single-labeled data in GBT training. In case of preference learning, no preference pairs could be extracted from single labeled data. Therefore, existing methods such as RankSVM, RankNet and RankBoost that are formulated for preference data only can not take advantage of such data. The QBrank framework can combine preference data and labeled data in a natural way. From figure 1, we can see QBrank using combined preference data and labeled data outperforms both QBrank and RankSVM using preference data only, which indicates that singled labeled data are also useful to QBrank training. Another observation is that GBT using labeled data is significantly worse than QBrank using preference data extracted from the same labeled data3 . We suspect the deeper reason lies at the fundamental difference between a ranking problem and a regression problem. GBT is designed for regression problems and is therefore not necessarily the optimal choice for ranking problems. Ranking web search results is fundamentally a preference learning problem rather than a regression problem, i.e., we just want to rank more relevant results higher than those less relevance ones, we do not need to care about accurately predicting the grades of the documents. Notice that, we exclude all tied data (pairs of documents with the same grades) when converting preference data from the absolute relevance judgments, which can be significant information loss, i.e., including tied data can further improve performance. We further explore the effectiveness of including single-labeled data in QBrank and plot the dcgs against each iteration in Figure 1. The results indicate the usefulness of single-labeled data in QBrank. The clear convergence trend of QBrank is also demonstrated.

3

a 1% dcg gain is considered signficant on this data set for commercial search engines.

6

i кл

Н

Gж

k

Gж

iк

Ю

k

ЮН

iк

Э E

XЄ Y6 Ь

з @к

E

л

Table 1: Precision at

% for QBrank, GBT, and RankSVM GBT 0.9328 0.8939 0.8557 0.8199 0.7899 0.7637 0.7399 0.7176 0.6977 0.6803 RankSVM 0.8524 0.8152 0.7839 0.7578 0.7357 0.7151 0.6957 0.6779 0.6615 0.6465

iк

л

iж ц5G ж i кi ж iж

i iG жж ц к


DCG-5 v. Iterations
6. 9 6. 85 6. 8
DCG-5

6. 75 6. 7 6. 65 6. 6 50 100 150 200 250 300 350 400 I te ra ti ons (Number of trees) GBT using L2 GBT using L1 GBT using L1+L2 QBrank using P2 QBrank using P2+L1

5 Conclusions and Future Work
We proposed a general boosting method for optimizing complex loss functions. We also applied the general framework to the problem of learning ranking functions. Experimental results using a commercial search engine data show that our approach leads to significant improvements. In future work, 1) we will add regularization to the preference part in the objective function; 2) we plan to apply our general boosting method to other structured learning problems; and 3) we will also explore other applications where both preference and labeled data are available for training ranking functions.

Appendix: Convergence results
We introduce a few definitions. Definition 1 Definition 2 is scale-invariant if and . . , .

Although we only consider global upper bounds, it is easy to see that results with respect to local upper bounds can also be established.

If we choose

on

such that and , and the rate of convergence compared to any target , and the sequences and . 7

Ѓvј Ђ ЉЇ~19p їЅ uІ %   Љ)e4І3ёЇCDB!&# у Ѕ A 8 ШЉ @) l  eї Њ  Sї Њ І   i 8  9eї Њ  І   763#З   "З 0 Іў ( &$ І   )0 '%ЇЇ  " #  И Љ Ј Є § Ј   З 0 њ "  џ 72 ў 42 Є§ ќ Їћ !ћ !ќ ќ џ 23ќ џ 2 53ќ 0 І   ЉЈ Є § Ј 1 Љq  Sї Њ Ч )q ї Њ І v iђ l  Ќ v ј ЉEuІ %     Ї~19pЕЈїЅ љ E E xE њ Ѕ ё

Theorem 1 Consider Algorithm 1, where is a convex function of . Let be an upper bound of the Hessian of . Assume that is scale-invariant. Let . Let be the normalized step-size, , and , then

, then

ъ P Re o eenseї Њ щш шЊ  

ъ P щTш ш ѕ i є i Љ ЅІ ё  ѓ  Љ ЅІ ѓ  ЅІ o іђ   o  943uHh943ё x Љ o h43ё o ђ Ѕ

ђ

ъ P T~їЅ ш Ѓ щш vЂ Љ їЅ І T R Q P I G ( E' ь % 9Й3ё S{ SЁ3H)Fc&#  wІ ЎТeї Њ  І   ў  І Ђ  ЃЁЗ Љ Ј Є § Ј Ї   Є§ ќ Ѕћ џ ЫЈћ ў §ќ Љ Ј Є § Ј ї Њ  F Ќ  v u Ev ё

E

ѓ6 Ѕ p Љ ЅІ 54uё

Definition 4 Let satisfy:

be a function of , an global upper bound and :

ящ №u б v o sъ P Tш v o ш v o v ч v Ќyм v ч м v wcyt ъ P S~Rш   Ѕю  э ь %# щш Ѕ 

Љ uІ %    Ї~19pТТЅ

Definition 3 Let

, then

of its Hessian with respect to .

iк

Figure 1: DCG v. Iterations. Notice that DCG for RankSVM using

is 6.181.

u  o ч

f hч

i aeЈІ o    C r ъ P Rш o ш Љ Є ы щ G k

u q o 

u

d 6 rYi


only depends


The proof is a systematic application of the idea outlined earlier and will be detailed in a separate publication. In practice, one often set the step size to be a small constant. In particular, for for some fixed , we can choose , and when ( otherwise). Theorem 1 gives the following bound when ,

The convergence results show that in order to have a risk not much worse than any target function , the approximation function does not need to be very complex when the complexity is measured by its 1-norm. It is also important to see that quantities appearing in the generalization analysis do not depend on the number of samples. These results imply that statistically, Algorithm 1 (with small step-size) has an implicit regularization effect that prevents the procedure from overfiting the data. Standard empirical process techniques can then be applied to obtain generalization bounds for Algorithm 1.

References
[1] BA L C A N N . , B E Y G E L Z I M E R A . , L A N G F O R D J . , Classification, manuscript, 2007.
AND

S O R K I N G . Robust Reductions from Ranking to

[2] B E RT S E K A S D . Nonlinear programming. Athena Scientific, second edition, 1999. [3] B U R G E S , C . , S H A K E D , T. , R E N S H AW, E . , L A Z I E R , A . , D E E D S , M . , H A M I LT O N , N . , A N D H U L L E N D E R , G . Learning to rank using gradient descent. Proc. of Intl. Conf. on Machine Learning (ICML) (2005). [4] D I E T T E R I C H , T. G . , A S H E N F E LT E R , A . , B U L AT OV, Y. Training Conditional Random Fields via Gradient Tree Boosting Proc. of Intl. Conf. on Machine Learning (ICML) (2004). [5] C L E M E N C O N S . , L U G O S I G . , A N D VAYAT I S N . Ranking and scoring using empirical risk minimization. Proc. of COLT (2005). [6] C O H E N , W. W. , S C H A P I R E , R . E . , A N D S I N G E R , Y. Learning to order things. Journal of Artificial Intelligence Research, Neural Computation, 13, 14431472 (1999). [7] F R E U N D , Y. , I Y E R , R . , S C H A P I R E , R . E . , A N D S I N G E R , Y. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research 4 (2003), 933­969. [8] F R I E D M A N , J . H . Greedy function approximation: A gradient boosting machine. Annals of Statistics 29, 5 (2001), 1189­1232. [9] H E R B R I C H , R . , G R A E P E L , T. , sion. 115­132.
AND

O B E R M AY E R , K . Large margin rank boundaries for ordinal regres-

[10] JA RV E L I N , K . , A N D K E K A L A I N E N , J . Ir evaluation methods for retrieving highly relevant documents. Proc. of ACM SIGIR Conference (2000). [11] J OAC H I M S , T. Optimizing search engines using clickthrough data. Proc. of ACM SIGKDD Conference (2002). [12] J OAC H I M S , T. , G R A N K A , L . , PA N , B . , A N D G AY, G . Accurately interpreting clickthough data as implicit feedback. Proc. of ACM SIGIR Conference (2005). [13] T S O C H A N TA R I D I S , I . , J OAC H I M S , T. , H O F M A N N , T. , A N D A LT U N , Y. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6:1453­1484, 2005.

8

iЊ


ъ P Re o eeЊ щш ш `WЊ ђ )XnЧ

ђ ъ P R~eSY9Й3h~x37yx3! ы ЧЇ9puё x Љ G Se43ё щ ш їЅ ш Љ Љ їЅ І ё g Љ w І ё 6 w І v  Њ q  Љ їЅ І Ћ ЅІ

q  i Ўђ Њ

x

E

l 1q

њ

Љ їЅ І ё g Љ w І ё 6 w І v  щ ш їЅ І з Ѕ ЊЎђ  ЉY9Й3БH xuayx3! ъ P RHeш ы  Љ Uo    Ѕ І w П Sї Њ )e43ё x ) Veї Њ Тe43ё  Љ  ЅІ w ЎЊ m  5Ѕ Љ uІ %    Ї~5pТТїЅ