Training a ranking function using propagated document relevance

Abstract

A method and system for propagating the relevance of labeled documents to a query to unlabeled documents is provided. The propagation system provides training data that includes queries, documents labeled with their relevance to the queries, and unlabeled documents. The propagation system then calculates the similarity between pairs of documents in the training data. The propagation system then propagates the relevance of the labeled documents to similar, but unlabeled, documents. The propagation system may iteratively propagate labels of the documents until the labels converge on a solution. The training data with the propagated relevances can then be used to train a ranking function.

1 - 20 . (canceled) 
     
     
         21 . A computer-readable storage medium containing instructions for controlling a computer system to augment a set of labeled documents, by a method comprising:
 providing documents that include labeled documents and unlabeled documents, each labeled document having a label that indicates relevance of the labeled document to a query;   storing a representation of a graph with nodes representing the documents and edges connecting the nodes representing similarity between documents represented by the connected nodes, each document having a feature vector in a feature space, the similarity between two documents being based on a metric derived from the feature vectors of the two documents;   iteratively propagating relevance of the labeled documents to the unlabeled documents based on similarity between documents as indicated by the graph until the propagated relevance of the unlabeled documents converge on a solution.   
     
     
         22 . The computer-readable storage medium of  claim 21  wherein the propagating of the relevance propagates relevance separately for each of a plurality of queries. 
     
     
         23 . The computer-readable storage medium of  claim 21  including establishing edges between nodes using a nearest neighbor algorithm. 
     
     
         24 . The computer-readable storage medium of  claim 21  wherein similarity is calculated based on a Euclidean distance metric. 
     
     
         25 . The computer-readable storage medium of  claim 21  wherein each pair of nodes is connected by an edge. 
     
     
         26 . The computer-readable storage medium of  claim 21  wherein the relevance of the labeled documents is generated by searching for documents related to the query in a corpus of documents and the unlabeled documents are not included in the corpus of documents. 
     
     
         27 . The computer-readable storage medium of  claim 21  wherein the propagate relevance component propagates relevance using a manifold ranking based algorithm. 
     
     
         28 . The computer-readable storage medium of  claim 21  wherein the relevance is propagated according to the following equation:
     f *=(1−α)( I−αS ) −1   y  
 
 
       where f* represents a propagated relevance vector, S is a similarity matrix, y represents an initial relevance vector, and α represents a decay rate. 
     
     
         29 . The computer-readable storage medium of  claim 21  wherein the relevance is propagated according to the following equation:
     f *=( I+αS+α   2   S   2 + . . . +α N   S   N ) y  
 
 
       where f* represents a propagated relevance vector, S is a similarity matrix, y represents an initial relevance vector, and α represents a decay rate, and where n represents an exponent for which f* converges on a solution. 
     
     
         30 . A computing device with a processor and memory for propagating relevance from documents having a known relevance to documents not having a known relevance, comprising:
 a training data store that contains training data including representations of documents and, for each query of a plurality of queries, a labeling of some of the documents with relevance of the documents to the query;   a graph component that creates a representation of a graph of the documents with the documents represented as nodes being connected by edges representing similarity between documents; and   a propagate relevance component that propagates relevance of the labeled documents to the unlabeled documents based on similarity between documents.   
     
     
         31 . The computing device of  claim 30  wherein the similarity between two documents is calculated based on a metric derived from the feature vectors representing the two documents. 
     
     
         32 . The computing device of  claim 30  wherein the similarity is based on the following: 
       
         
           
             
               
                 W 
                 ij 
               
               = 
               
                 
                   ∏ 
                   
                     l 
                     = 
                     1 
                   
                   t 
                 
                  
                 
                     
                 
                  
                 
                   exp 
                    
                   
                     ( 
                     
                       
                         - 
                         
                            
                           
                             
                               x 
                               il 
                             
                             - 
                             
                               x 
                               jl 
                             
                           
                            
                         
                       
                       / 
                       
                         σ 
                         l 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       where W ij  represents the similarity between documents i and j, x il  and x jl  represent the l th  dimension of the feature vectors x i  and x j  respectively, t represents the dimensionality of the feature space, and σ l  represents a positive parameter that reflects weights of different dimensions in the calculating of similarity. 
     
     
         33 . The computing device of  claim 30  wherein the similarity is based on a Euclidean distance. 
     
     
         34 . The computing device of  claim 30  wherein the similarity is based on a cosine similarity metric. 
     
     
         35 . The computing device of  claim 30  wherein the relevance is propagated iteratively until the propagated relevance of the unlabeled documents converge on a solution. 
     
     
         36 . The computing device of  claim 30  wherein the relevance of the labeled documents is generated by searching for documents related to a query in a corpus of documents and the unlabeled documents are not included in the corpus of documents. 
     
     
         37 . A method performed by a computer system to propagate relevance from documents labeled with relevance to a query to documents not labeled with relevance to the query, the method comprising:
 providing documents that include labeled documents and unlabeled documents, each labeled document having a label that indicates relevance of the labeled document to the query;   storing a representation of a graph with nodes representing the documents and edges connecting the nodes representing similarity between documents represented by the connected nodes, each document having a feature vector in a feature space, the similarity between two documents being based on a metric derived from the feature vectors of the two documents;   propagating relevance of the labeled documents to the unlabeled documents based on similarity between documents as indicated by the graph.   
     
     
         38 . The method of  claim 37  wherein the propagating of the relevance propagates relevance separately for each of a plurality of queries. 
     
     
         39 . The method of  claim 37  including establishing edges between nodes using a nearest neighbor algorithm. 
     
     
         40 . The method of  claim 37  wherein similarity is calculated based on a Euclidean distance metric.