Abstract:
The present invention provides methods for improving a ranking model. In one embodiment, a method includes the step of obtaining queries, documents, and document labels. The process then initializes active sets using the document labels, wherein two active sets are established for each query, a perfect active set and an imperfect active set. Then, the process optimizes an empirical loss function by the use of the first and second active set, whereby parameters of the ranking model are modified in accordance to the empirical loss function. The method then updates the active sets with additional ranking data, wherein the updates are configured to work in conjunction with the optimized loss function and modified ranking model. The recalculated active sets provide an indication for ranking the documents in a way that is more consistent with the document metadata.

Description:
BACKGROUND 
     In learning to rank for information retrieval, a ranking model is constructed with training data consisting of queries, their corresponding retrieved documents, and relevance levels given by humans. In ranking, given a new query, the retrieved documents are ranked by using the trained ranking model. 
     In Information Retrieval (IR), usually ranking results are evaluated in terms of evaluation measures such as MAP (Mean Average Precision) and NDCG (Normalized Discounted Cumulative Gain). Ideally a learning algorithm would train a ranking model by optimizing the performance in terms of a given evaluation measure. In this way, higher accuracy in ranking can be expected. However, this is usually difficult due to the non-continuous and non-differentiable nature of the IR measures. 
     Many learning to rank algorithms proposed so far typically minimize a loss function loosely related to the IR measures. For example, Ranking SVM and RankBoost minimize loss functions based on classification errors on document pairs. 
     Recently, researchers have developed several new algorithms that manage to directly optimize the performance in terms of the IR measures. For example, SVM map  and AdaRank minimize loss functions based on the IR measures. 
     There are still open questions regarding to the direct optimization approach. (1) Is there a general theory that can guide the development of new algorithms? (2) What is the relation between existing methods such as SVM map  and AdaRank? (3) Which direct optimization method performs the best empirically? 
     SUMMARY 
     In response to some of the issues described above, the present invention provides method for improving a ranking model. In one embodiment, a method includes the process of obtaining a data set of queries, documents, and document labels. The process then initializes active sets using the document labels, wherein two active sets are established for each query, a perfect active set and an imperfect active set. Then, the process optimizes an empirical loss function based on the first and second active set, whereby parameters of the ranking model are modified in accordance to the optimization of the empirical loss function. The method then updates the active sets with additional ranking data, wherein the updates are configured to work in conjunction with the optimized loss function and modified ranking model. The recalculated active sets provide an indication for ranking the documents in a way that is more consistent with the document labels. 
     This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a table of notations. 
         FIG. 2A  illustrates a type one bounds. 
         FIG. 2B  illustrates a type two bounds. 
         FIG. 3  illustrates a PermuRank algorithm in accordance with one aspect of the present invention. 
         FIG. 4  illustrates the relations in accordance with the summary of the upper bounds on the basic loss function. 
     
    
    
     DETAILED DESCRIPTION 
     The claimed subject matter is described with reference to the drawings, wherein like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the subject innovation. It may be evident, however, that the claimed subject matter may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing the subject innovation. 
     As utilized herein, terms “component,” “system,” “data store,” “evaluator,” “sensor,” “device,” “cloud,” ‘network,” “optimizer,” and the like are intended to refer to a computer-related entity, either hardware, software (e.g., in execution), and/or firmware. For example, a component can be a process running on a processor, a processor, an object, an executable, a program, a function, a library, a subroutine, and/or a computer or a combination of software and hardware. By way of illustration, both an application running on a server and the server can be a component. One or more components can reside within a process and a component can be localized on one computer and/or distributed between two or more computers. 
     Furthermore, the claimed subject matter may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof to control a computer to implement the disclosed subject matter. The term “article of manufacture” as used herein is intended to encompass a computer program accessible from any computer-readable device, carrier, or media. For example, computer readable media can include but are not limited to magnetic storage devices (e.g., hard disk, floppy disk, magnetic strips . . . ), optical disks (e.g., compact disk (CD), digital versatile disk (DVD) . . . ), smart cards, and flash memory devices (e.g., card, stick, key drive . . . ). Additionally it should be appreciated that a carrier wave can be employed to carry computer-readable electronic data such as those used in transmitting and receiving electronic mail or in accessing a network such as the Internet or a local area network (LAN). Of course, those skilled in the art will recognize many modifications may be made to this configuration without departing from the scope or spirit of the claimed subject matter. Moreover, the word “exemplary” is used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other aspects or designs. 
     The detailed description below first provides a description of embodiments of the present invention. The paragraphs that follow disclose a comprehensive study on direct optimization of IR measures in learning to rank. As described in more detail below, we conduct a general analysis on the approach. We indicate that direct optimization of IR measures amounts to minimizing different loss functions based on the measures. We first introduce one basic loss function which is directly defined on the basis of the IR measures. We then indicate that there are two types of upper bounds on the basic loss function. We refer to them as type one bound and type two bound respectively. Minimizing the two types of upper bounds leads to different learning algorithms. With the analysis, different algorithms can be easily studied and compared. Moreover, new algorithms can be easily derived. As example, we create a new algorithm called PermuRank. We show that existing algorithms of AdaRank and SVM map  manage to minimize loss functions which are type one upper bound and type two upper bound respectively. We have compared the performances of the exiting direct optimization methods using several benchmark data sets. Experimental results show that the direct optimization methods of SVM map , AdaRank, and PermuRank can always improve upon the baseline methods of Ranking SVM and RankBoost. Furthermore, the direct optimization methods themselves can work equally well. 
     Other sections of the detailed description describe the problem of learning to rank for information retrieval. Following that, we propose a general framework for directly optimizing evaluation measures. Two existing algorithms of SVM map  and AdaRank, and a new algorithm PermuRank are analyzed and discussed within the framework. The sections then following cover experimental results. 
     The key problem for document retrieval is ranking, specifically, to create a ranking model that can sort documents based on their relevance to the given query. Traditional ranking models such as BM25 and LMIR (Language Models for Information Retrieval) only have a few parameters to tune. As the ranking models become more sophisticated (with more features) and more labeled data become available, how to tune or train a ranking model becomes a challenging issue. 
     In recent years, methods of ‘learning to rank’ have been applied to ranking model construction and promising results have been obtained. Learning to rank is to automatically create a ranking model by using labeled training data and machine learning techniques. Several approaches have been proposed. The pairwise approach transforms the ranking problem into binary classification on document pairs. Typical methods include Ranking SVM, Rank-Boost, and RankNet. The methods of Ranking SVM, RankBoost, and RankNet minimize loss functions that are loosely related to the evaluation measures such as MAP and NDCG. 
     Recently, the approach of directly optimizing the performance in terms of IR measures have also been proposed. There are three categories. First, one can minimize loss functions upper-bounding the basic loss function defined on the IR measures. For example, SVM map  minimizes a hinge loss function, which upper bounds the basic loss function based on Average Precision. AdaRank minimizes an exponential loss function upper bounding the basic loss function. 
     Second, one can approximate the IR measures with functions that are easy to handle. For example, Softrank proposes an approximation of NDCG. Third, Genetic Programming (GP) is used to optimize the IR measures. For example, proposed a specifically designed GP for learn a ranking model for IR. Aspects of the technology herein involve the first category and take SVM map  and AdaRank as examples of existing methods. 
     Learning to rank for Information Retrieval is a problem as follows. In retrieval (testing), given a query the system returns a ranked list of documents in descending order of their relevance scores. In learning (training), a number of queries and their corresponding retrieved documents are given. Furthermore, the labels of the documents with respect to the queries are also provided. The labels represent ranks (i.e., categories in a total order). The objective of learning is to construct a ranking model which achieves the best result on test data in the sense of minimization of a loss function. Ideally the loss function is defined directly on an IR measure used in testing. 
     Suppose that Y={r 1 ,r 2 , . . . , r l } is the set of ranks, where l denotes the number of ranks. There exists a total order between the ranks r l &gt;r i−l &gt; . . . &gt;r 1 , where &gt; denotes the order. Suppose that Q={q 1 , q 2 , . . . , q m } is the set of queries in training. Each query q i , is associated with a list of retrieved documents d i ={d i1 , d i2 , . . . d i,n(q     i     ) } and a list of labels y i ={y i1 , y i2 , . . . , y i,n(q     i     ) }, where n(q i ) denotes the sizes of lists d i  and y i , d ij  denotes the j th  document in d i , and y ij εY denotes the label of document d ij . A feature vestor φ(q i ,d ij ) is created from each query-document pair (q i ,d ij ), i=1,2, . . . , m; j=1,2, . . . , n(q i ). The training set is denoted as S={(q i ,d i ,y i )} i=1   m . 
     Let the documents in d i  be identified by the integers {1,2, . . . , n(q i )}. We define permutation π i  on d i  as a bijection from {1,2, . . . , n(q i )} to itself. We use Π, to denote the set of all possible permutations on d i , and use π i (j) to denote the position of item j (i.e., d ij ). Ranking is nothing but to select a permutation π i εΠ, for the given query q i  and the associated list of documents d i  using the ranking model. 
     The ranking model is a real valued function of features. There are two types of ranking models. We refer to them as f and F respectively. 
     Ranking model f is a document level function, which is a linear combination of the features in feature vector φ(q i ,d ij ):
 
 f ( q   i   ,d   ij )= w   T φ( q   i   ,d   ij )  (1)
 
where w denotes the weight vector. In ranking for query q i  we assign a score to each of the documents using f (q i ,d ij ) and sort the documents based on the scores. We obtain a permutation denoted as  π   i .
 
     Ranking model F as a query level function. We first introduce a query level feature vector for each triple of q i , d i  and π i , denoted as Φ(q i ,d i ,π i ). We calculate Φ by linearly combining the feature vectors of query-document pairs for q i : 
                       Φ   ⁡     (       q   i     ,     d   i     ,     π   i       )       =       1       n   ⁡     (     q   i     )       ·     (       n   ⁡     (     q   i     )       -   1     )         ⁢       ∑     k   ,       l   ⁢     :     ⁢   k     &lt;   l                 ⁢     [       z   kl     ⁡     (       ϕ   ⁡     (       q   i     ,     d   ik       )       -     ϕ   ⁡     (       q   i     ,     d   il       )         )       ]           ,           (   2   )               
where z kl =+1 if π i (k)&lt;π i (l) (d ik  is ranked ahead d il  in π i ), and −1 otherwise. We define F as a linear combination of the features in feature vector Φ:
 
 F ( q   i   ,d   i ,π i )= w   T Φ( q   i   ,d   1 ,π i ),  (3)
 
where w denotes the weight vector. In ranking, the permutation with the largest score given by F is selected:
 
     
       
         
           
             
               
                 
                   
                     
                       π 
                       ~ 
                     
                     i 
                   
                   = 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     max 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         F 
                         
                           
                             π 
                             i 
                           
                           ∈ 
                           
                             Π 
                             i 
                           
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             q 
                             i 
                           
                           , 
                           
                             d 
                             i 
                           
                           , 
                           
                             π 
                             i 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     It can be shown that, the two types of ranking models are equivalent, if the parameter vectors w&#39;s in the two models are identical. 
     THEOREM 1. Given a fixed parameter vector w, the two ranking models f and F generate the same ranking result. That is, permutations  π   i  and {tilde over (π)} i  are identical. 
     Theorem 1 implies that Equation (4) can be computed efficiently by sorting documents using Equation (1). 
     In IR, evaluation measures are used to evaluate the goodness of a ranking model, which are usually query-based. By query based, we mean that the measure is defined on a ranking list of documents with respect to the query. These include MAP, NDCG, MRR (Mean Reciprocal Rank), WTA (Winners Take ALL), and Precision@n. We utilize a general function E(π i ,y i )ε[0,+1] to represent the evaluation measures. The first argument of E is the permutation π i  created using the ranking model. The second argument is the list of ranks y i  given as ground truth. E measures the agreement between π i , and y i . Most evaluation measures return real values in [0, +1]. We denote the perfect permutation as π* i . Note that there may be more than one perfect permutation for a query, and we use Π* i  to denote the set of all possible perfect permutations for query q i . For π* i εΠ* i , we have E(π* i ,y i )=1.  FIG. 1  illustrates a table of the notations described above. 
     In this section, we give a general framework for analyzing learning to rank algorithms that directly optimize evaluation measures. 
     Ideally, we would create a ranking model that maximize the accuracy in terms of an IR measure on training data, or equivalently, minimize the loss function defined as follows: 
                       R   ⁡     (   F   )       =         ∑     i   =   1     m     ⁢     (       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )         )       =       ∑     i   =   1     m     ⁢     (     1   -     E   ⁡     (       π   i     ,     y   i       )         )           ,           (   5   )               
where π i  is the permutation selected for query q i  by ranking model F (or f). In this paper, we refer to the loss function R(F) (or R(f)) as the ‘basic loss function’.
 
     It is difficult to directly minimize the basic loss function R(F), because E is non-continuous and non-differentiable. We instead try to minimize upper bounds of it. In this paper, we call the approach the ‘direct optimization approach’. 
     We can consider two types of upper bounds. The first one is defined directly on the IR measures (type one bound). The second one is defined on the pairs between the perfect and imperfect permutations (type two bound). AdaRank and SVM map  turns out to be algorithms that minimize one of the two upper bounds, respectively. PermuRank which we propose in this paper is an algorithm that tries to minimize a type two bound. 
     The basic loss function can be upper bounded directly by the exponential function, logistic function, etc., which are widely used in machine learning. The logistic function is defined as 
     
       
         
           
             
               ∑ 
               
                 i 
                 = 
                 1 
               
               m 
             
             ⁢ 
             
               
                 
                   log 
                   2 
                 
                 ⁡ 
                 
                   ( 
                   
                     1 
                     + 
                     
                       ⅇ 
                       
                         - 
                         
                           E 
                           ⁡ 
                           
                             ( 
                             
                               
                                 π 
                                 i 
                               
                               , 
                               
                                 y 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   ) 
                 
               
               . 
             
           
         
       
     
     The exponential function is defined as 
     
       
         
           
             
               ∑ 
               
                 i 
                 = 
                 1 
               
               m 
             
             ⁢ 
             
               exp 
               ⁢ 
               
                 
                   { 
                   
                     - 
                     
                       E 
                       ⁡ 
                       
                         ( 
                         
                           
                             π 
                             i 
                           
                           , 
                           
                             y 
                             i 
                           
                         
                         ) 
                       
                     
                   
                   } 
                 
                 . 
               
             
           
         
       
     
     We can use the exponential function and logistic function as ‘surrogate’ loss functions in learning. Note that both functions are continuous, differentiable, and even convex w.r.t. E.  FIG. 2A  plots the basic loss function, exponential loss function, and logistic loss function. From the figure, we can see that exponential loss function is tighter than the logistic loss function. 
     The AdaRank algorithm actually minimizes the exponential loss function (type one bound). To do so, AdaRank repeats the process of re-weighting the training query, creating a weak ranker, and calculating a weight for weak the ranker, and finally linearly combines the weak rankers as the final ranking model. 
     Here, we, introduce a new loss function. 
                       ∑     i   =   1     m     ⁢       max         π   i   *     ∈     ∏   i   *       ;       π   i     ∈       ∏   i     ⁢     \   ⁢     ∏   i   *               ⁢     (       (       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )         )     ·     〚           ⁢     (       F   ⁡     (       q   i     ,     d   i     ,     π   i   *       )       ≤     F   ⁡     (       q   i     ,     d   i     ,     π   i       )         )     〛       )         ,           (   6   )               
Where [[.]] is one if the condition is satisfied, otherwise zero.
 
     The loss function measures the loss when the worst prediction is made, specifically, the difference between the performance of the perfect permutation (it equals one) and the minimum performance of an incorrect permutation (it is less than one). 
     The following theorem holds with regard to the new loss function. 
     THEOREM 2. The basic loss function in (5) is upper bounded by the new loss function in (6). 
     The loss function (6) is still not continuous and differentiable because it contains the 0-1 function [[.]], which is not continuous and differentiable. We can consider using continuous, differentiable, and even convex upper bounds on the loss function (6), which are also upper bounds on the basic loss function (5). 
     1) The 0-1 function [[.]] in (6) can be replaced with its upper bounds, for example, hinge, exponential, and logistic functions, yielding 
                 ∑     i   =   1     m     ⁢       max         π   i   *     ∈     ∏   i   *       ;       π   i     ∈       ∏   i     ⁢     \   ⁢     ∏   i   *               ⁢       (       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )         )     ·     ⅇ     -     (       F   ⁡     (       q   i     ,     d   i     ,     π   i   *       )       -     F   ⁡     (       q   i     ,     d   i     ,     π   i       )         )               ;                   ∑     i   =   1     m     ⁢       max         π   i   *     ∈     ∏   i   *       ;       π   i     ∈       ∏   i     ⁢     \   ⁢     ∏   i   *               ⁢       (       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )         )     ·       log   2     ⁡     (     1   +     ⅇ     -     (       F   ⁡     (       q   i     ,     d   i     ,     π   i   *       )       -     F   ⁡     (       q   i     ,     d   i     ,     π   i       )         )           )             ;                   ∑     i   =   1     m     ⁢       max         π   i   *     ∈     ∏   i   *       ;       π   i     ∈       ∏   i     ⁢     \   ⁢     ∏   i   *               ⁢       (       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )         )     ·       [     1   -     (       F   ⁡     (       q   i     ,     d   i     ,     π   i   *       )       -     F   ⁡     (       q   i     ,     d   i     ,     π   i       )         )       ]     +           ;                   ∑     i   =   1     m     ⁢       [       max         π   i   *     ∈     ∏   i   *       ;       π   i     ∈       ∏   i     ⁢     \   ⁢     ∏   i   *               ⁢     (       (       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )         )     -     (       F   ⁡     (       q   i     ,     d   i     ,     π   i   *       )       -     F   ⁡     (       q   i     ,     d   i     ,     π   i       )         )       )       ]     +       ,         
Where [.] +  denotes the hinge function.
 
       FIG. 2B  shows the relations between the loss function (6) and its upper bounds, where E(π* i ,y i )−E(π i ,y i ) is set to 0.5. From the figure, we can see that it is not possible to say which upper bound is the tightest. Different upper bounds may be suitable for different data sets. 
     2) The max function can also be replaced with its upper bound of sum function. This is because 
                 ∑   i     ⁢     x   i       ≥       max   i     ⁢       x   i     ⁢           ⁢   if   ⁢           ⁢     x   i         ≥   0         
holds for all i.
 
     3) Relaxations 1 and 2 can be applied simultaneously. 
     For example, replacing [[.]] with hinge function and max with sum, we obtain: 
     
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       i 
                       - 
                       1 
                     
                     m 
                   
                   ⁢ 
                   
                     
                       ∑ 
                       
                         
                           
                             π 
                             i 
                             * 
                           
                           ∈ 
                           
                             ∏ 
                             i 
                             * 
                           
                         
                         ; 
                         
                           
                             π 
                             i 
                           
                           ∈ 
                           
                             
                               ∏ 
                               i 
                             
                             ⁢ 
                             
                               \ 
                               ⁢ 
                               
                                 ∏ 
                                 i 
                                 * 
                               
                             
                           
                         
                       
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             E 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   π 
                                   i 
                                   * 
                                 
                                 , 
                                 
                                   y 
                                   i 
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             E 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   π 
                                   i 
                                 
                                 , 
                                 
                                   y 
                                   i 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                       · 
                       
                         
                           [ 
                           
                               
                           
                           ⁢ 
                           
                             1 
                             - 
                             
                               ( 
                               
                                 
                                   F 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         q 
                                         i 
                                       
                                       , 
                                       di 
                                       , 
                                       
                                         π 
                                         i 
                                         * 
                                       
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   F 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         q 
                                         i 
                                       
                                       , 
                                       
                                         d 
                                         i 
                                       
                                       , 
                                       
                                         π 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                           ] 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     We can derive different algorithms by using the upper bounds as surrogate loss functions. SVM map  and PermuRank are two examples. 
     SVM map  solves the following quadratic programming problem: 
                         min     _       w   →     ;     ξ   ≥   0           ⁢       1   2     ⁢            w   →          2         +       C   m     ⁢       ∑     i   -   1     m     ⁢     ξ   i           ⁢     
     ⁢       s   .   t   .     ∀   i       ,     ∀       π   i   *     ∈     ∏   i   *         ,     ∀       π   i     ∈           ∏   i     ⁢     \   ⁢       ∏   i   *     ⁢       :     ⁢     F   ⁡     (       q   i     ,     d   i     ,     π   i   *       )               -     F   ⁡     (       q   i     ,     d   i     ,     π   i       )         ≥       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )       -     ξ   i             ,             (   8   )               
where C is the coefficient for trade-off between total empirical loss and model complexity, and ξ i  represents the empirical loss for q i . One can easily verify that in the constraints the empirical loss ξ i  is the maximum among all the losses of permutations for query q 1 . Equivalently, SVM map  minimizes the following regularized hinge loss function
 
                         ∑     i   =   1     m     ⁢       [       max         π   i   *     ∈     ∏   i   *       ;       π   i     ∈       ∏   i     ⁢     \   ⁢     ∏   i   *               ⁢     (       (       E   ⁡     (       π   i   *     ,     y   i       )       -     E   ⁡     (       π   i     ,     y   i       )         )     -     (       F   ⁡     (       q   i     ,     d   i     ,     π   i   *       )       -     F   ⁡     (       q   i     ,     d   i     ,     π   i       )         )       )       ]     +       +     λ   ⁢            w   →          2         ,           (   9   )               
where [.] is hinge function.
 
     Intuitively, the first term calculates the total maximum empirical loss when selecting the best permutation for each of the queries. Specifically, if the difference between the permutations F(q i ,d i ,π* i )−F(q i ,d i ,π i ) is less than the difference between the corresponding evaluation measures E(π* i ,y i )−E(π i ,y i )), then there will be a loss, otherwise not. Next, the maximum loss is selected for each query and they are summed up over all the queries. 
     Since c*[[x≦0]]&lt;[c−x] +  holds for all cε            and xε         , it is easy to see that the upper bound in (9) also bounds the basic loss function in (5) (See also  FIG. 2B ).
     In principle, any type two bound can be optimized using optimization techniques such as those in Perceptron, Support Vector Machines, and Boosting. However, the sizes of permutation sets Π*, and Π i †Π* i  are both of order O(n!), which makes the optimization infeasible. Here n denotes the numbers of documents associated with query q i . 
     Here we propose a new direct optimization algorithm which efficiently minimizes one of the type two bounds as loss function in a greedy way. The algorithm is referred to as PermuRank and is shown in  FIG. 3 . The key idea in PermuRank is to maintain a set of perfect permutations and a set of imperfect permutations as working sets, in stead of using the entire set of perfect permutations and the entire set of imperfect permutations. 
     PermuRank takes a training set S={(q i ,d i ,y i )} i=1   m  as input and takes evaluation measure E and number of iterations T as parameters. PermuRank runs T rounds and at each round it creates a ranking model F i (t=1, . . . , T). Finally, it outputs a ranking model F created at the last round. 
     At each round t, PermuRank maintains a set of perfect permutations and a set of imperfect permutations for each query q i , denoted as B i   t  and C i   t , respectively. These two sets are initialized with an arbitrary perfect permutation π* i εΠ* i  and an arbitrary imperfect permutation π i εΠ i †Π* i . At each round, the two sets are updated by adding the most violated perfect and imperfect permutations respectively: 
     
       
         
           
             
               B 
               i 
               
                 t 
                 + 
                 1 
               
             
             ← 
             
               
                 B 
                 i 
                 t 
               
               ⋃ 
               
                 
                   { 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     min 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         F 
                         l 
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             q 
                             i 
                           
                           , 
                           
                             d 
                             i 
                           
                           , 
                           
                             π 
                             i 
                           
                         
                         ) 
                       
                     
                   
                   } 
                 
                 
                   π 
                   ∈ 
                   
                     ∏ 
                     i 
                     * 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 C 
                 i 
                 
                   t 
                   + 
                   1 
                 
               
               ← 
               
                 
                   C 
                   i 
                   t 
                 
                 ⋃ 
                 
                   
                     { 
                     
                       arg 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       max 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           F 
                           l 
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               q 
                               i 
                             
                             , 
                             
                               d 
                               i 
                             
                             , 
                             
                               π 
                               i 
                             
                           
                           ) 
                         
                       
                     
                     } 
                   
                   
                     
                       π 
                       i 
                     
                     ∈ 
                     
                       
                         ∏ 
                         i 
                       
                       ⁢ 
                       
                         \ 
                         ⁢ 
                         
                           ∏ 
                           i 
                           * 
                         
                       
                     
                   
                 
               
             
             , 
           
         
       
     
     At each round t, a ranking model F i  is created using the permutation sets B i   t  and C i   t , i=1, . . . , m created so far 
                       F   l     =     arg   ⁢           ⁢       max     F   ∈   ℱ       ⁢     L   ⁡     (       ℬ   1   t     ,     ??   1   t     ,   …   ⁢           ,     ℬ   m   t     ,     ??   m   t       )             ,           (   10   )               
where L(B 1   t ,C 1   t ,B m   t ,C m   t  is a type two bound, based on B i   t  and C i   t  instead of Π* i  and Π i †Π* i .
 
     In this description, without loss of generality, we use the hinge loss function of Equation (7). The total empirical loss L becomes 
     
       
         
           
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       
                         
                           L 
                           ⁡ 
                           
                             ( 
                             
                               
                                 B 
                                 1 
                               
                               , 
                               
                                 C 
                                 1 
                               
                               , 
                               … 
                               ⁢ 
                               
                                   
                               
                               , 
                               
                                 B 
                                 m 
                               
                               , 
                               
                                 C 
                                 m 
                               
                             
                             ) 
                           
                         
                         = 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             m 
                           
                           ⁢ 
                           
                             l 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   B 
                                   i 
                                 
                                 , 
                                 
                                   C 
                                   i 
                                 
                               
                               ) 
                             
                           
                         
                       
                       , 
                       
                         
 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       where 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         l 
                         ⁡ 
                         
                           ( 
                           
                             
                               B 
                               i 
                             
                             , 
                             
                               C 
                               i 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         
                           1 
                           
                              
                             
                               B 
                               i 
                             
                              
                           
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               
                                 π 
                                 i 
                                 * 
                               
                               ∈ 
                               
                                 B 
                                 i 
                               
                             
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 
                                   π 
                                   i 
                                   * 
                                 
                                 ∈ 
                                 
                                   C 
                                   i 
                                 
                               
                             
                             ⁢ 
                             
                               
                                 ( 
                                 
                                   
                                     E 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           π 
                                           i 
                                           * 
                                         
                                         , 
                                         
                                           y 
                                           i 
                                         
                                       
                                       ) 
                                     
                                   
                                   - 
                                   
                                     E 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           π 
                                           i 
                                         
                                         , 
                                         
                                           y 
                                           i 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                               · 
                               
                                 
                                   
                                     [ 
                                     
                                       1 
                                       - 
                                       
                                         ( 
                                         
                                           
                                             F 
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 
                                                   q 
                                                   i 
                                                 
                                                 , 
                                                 
                                                   d 
                                                   i 
                                                 
                                                 , 
                                                 
                                                   
                                                     π 
                                                     i 
                                                     * 
                                                   
                                                   ; 
                                                   w 
                                                 
                                               
                                               ) 
                                             
                                           
                                           - 
                                           
                                             F 
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 
                                                   q 
                                                   i 
                                                 
                                                 , 
                                                 
                                                   d 
                                                   i 
                                                 
                                                 , 
                                                 
                                                   
                                                     π 
                                                     i 
                                                   
                                                   ; 
                                                   w 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     ] 
                                   
                                   + 
                                 
                                 . 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     In this paper, we employ the SVM technique to minimize the regularized hinge loss function. 
     The learned ranking model F t  is then used to update B i   t+1  and C i   t+1  for training the next ranking model F i+1 . 
     At each round, PermuRank checks whether the permutation sets B i   t  and C i   t  are changed. If there is no change, the algorithm will stop and return F i  as the final ranking model. 
     We give a summary on the upper bounds on the basic loss function.  FIG. 4  shows the relations. There is a basic loss function (5). On the left hand side is type one bound. The upper bounds of exponential loss function, logistic loss function, etc can be used. On the right hand side is type two bound. Equation (6) is the loss function for type two bound, which also upper bounds the basic loss function. Furthermore, the upper bounds of exponential loss function, logistic loss function, hinge loss functions, etc can be considered.