Abstract:
Computer-implemented systems and methods, including servers, perform structure-based recognition processes that include matching and classification. Preprocessing subsystems and sub-methods embed a set of classes on which a loss function is defined into a semantic space and learn an input mapping between an input space and the semantic space. Recognition subsystems and methods accept a test object, representable in the input space, and apply the input mapping to the test object as part of a recognition process.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to classification and matching with a large number of structured classes. 
         [0003]    2. Art Background 
         [0004]    The problem of classification with a very large number of structured classes is of increasing interest in Internet business: many systems in search and advertising depend on query, page and ad categorization. For instance, in typical content match schemes both the page and the ads are placed into a hierarchy of topics; the selection of the ads is such that the topic of the page and the ad are similar; in this way, the advertisement appears to be relevant to the content of the page. 
         [0005]    Given a set of classes organized in a taxonomy, and a collection of objects potentially classifiable into a class from the set of classes, there are related problems of classifying the objects classification and of matching objects to one anther. One approach is termed “one-vs.-the-rest”, where a classifier is trained for each class. The most-common classification strategy employed is “flat” classification, which ignores the hierarchical relationship between classes. For example, “scuba diving” and “swimming” classes are both similar to each other and very different from an “automobile” class. 
       SUMMARY OF THE INVENTION 
       [0006]    In the case of a taxonomy of classes, a loss function on a set of classes, or some other structure defining relationships between classes, there exists information about the relationship between different classes. Embodiments consistent with the present invention use this information to embed the different classes into a semantic space, where similar classes are close together, preferably in terms of vector similarity within the semantic space, and different classes are far away. Methods and systems consistent with some embodiments then cast the structured classification problem into a (computationally easier) multidimensional regression problem. These embodiments learn a mapping from an input space to the semantic space. For a test pattern, the predicted class is the one with the smallest distance in that space between the mapped test point and the class representatives. In case of matching, the distance between two entities reflect their semantic dissimilarity and the class information is not needed. 
         [0007]    In one aspect, embodiments of the present invention relate to computer-implemented system for structure-based recognition. For example, one system comprising a preprocessing subsystem for embedding a set of classes on which a loss function is defined into a semantic space and for learning an input mapping between an input space and the semantic space, and a recognition subsystem for accepting a test object that is representable in the input space and applying the input mapping to the test object as part of a recognition process. In this aspect preferred recognition processes include matching and classification. 
         [0008]    In another aspect, embodiments relate to computer-implemented methods of structure-based recognition. For example, a method comprising an embedding step, a learning step, and applying step. The embedding step comprises a set of classes on which a loss function is defined into a semantic space. The learning step comprises learning an input mapping between an input space and the semantic space. The applying step comprises applying the input mapping to a test object that is representable in the input space as part of a recognition process. In this aspect preferred recognition processes include matching and classification. 
         [0009]    In still another aspect, embodiments relate to recognition servers. For example a recognition server that operates on a collection of objects, wherein each object belongs to an input space, and on a hierarchy of classes. For example, such a server includes a preprocessing module and a recognition module. The preprocessing module is for embedding the classes from the hierarchy of classes into a semantic space and for learning an input mapping between an input space and the semantic space. The input mapping is based on a training set of objects from the input space associated with classes in the hierarchy of classes. The recognition module is for applying the input mapping to the collection of objects as part of a recognition process. In this aspect preferred recognition processes include matching and classification. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0010]      FIG. 1   a  is an exemplary search results page of a commercial search engine, which comprises algorithmic search results and advertisements in various locations of the page. 
           [0011]      FIG. 1   b  is an exemplary web page running content matched advertisements; the page comprises content and advertisements in various locations of the page. 
           [0012]      FIG. 2  is a diagram outlining backend processing steps required to produce a search results page and a content-matched advertising page. 
           [0013]      FIG. 3   a  is a conceptual depiction of a set of classes arranged in a hierarchy consistent with some embodiments of the present invention. 
           [0014]      FIG. 3   b  is a conceptual depiction of a semantic space, an input space, and a set of classes consistent with some embodiments of the present invention. 
           [0015]      FIG. 4  is a flowchart illustrating a hierarchical recognition system consistent with some embodiments of the present invention. 
           [0016]      FIG. 5   a  is a flowchart illustrating an embedding step of a preprocessing portion of a hierarchical recognition system consistent with some embodiments of the present invention. 
           [0017]      FIG. 5   b  is a flowchart illustrating a regression step of a preprocessing portion of a hierarchical recognition system consistent with some embodiments of the present invention. 
           [0018]      FIG. 5   c  is a flowchart illustrating a matching application of a hierarchical recognition system consistent with some embodiments of the present invention. 
           [0019]      FIG. 5   d  is a flowchart illustrating a classification application of a hierarchical recognition system consistent with some embodiments of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
     Advertising 
       [0020]    Users of the Internet are familiar with typical commercial search engines.  FIG. 1   a  illustrates an exemplary search results page (SRP) returned by a commercial search engine in response to a query. The right column of the page comprises advertisements. The left column of the page comprises algorithmic search results. 
         [0021]    Internets users also recognize typical advertisement serving schemes.  FIG. 1   b  illustrates an exemplary web page with advertisements served based on web page content. The right column of the page comprises advertisements. The left column of the page comprises content. 
         [0022]      FIG. 2  shows a typical workflow by which an SRP or set of content-matched ads is generated in response to a search query or web page content. In the case of a query, the query is first processed. Typical processing operations include filtering, sanitization, stemming, stop-word removal, and canonical format conversion. The processed query is provided to two separate sub-process pipelines. The first pipeline ranks all web content, which is usually referenced by a URL or URI on the World-Wide-Web, in order of relevance to the pre-processed query. This ranking forms the algorithmic search results set for query. The second pipeline ranks all available ads, either text-based or graphical, also in order of relevance to the pre-processed query. The SRP delivered in response to the query draws on both rankings: of ads and of algorithmic results. Typically, SRP construction involves both rankings and includes a default sub-process to determine the layout of the ads on the page. Typically the rankings determine placement of ads within the layout. Though such advertising layout algorithms may formulate advertisement placement in different ways, they use query and individual ad-level features to determine placement. 
         [0023]    In the case of web page content, the content is also processed first. Again, typical processing operations include filtering, sanitization, stemming, stop-word removal, and canonical format conversion. The processed content is provided to an ad-ranking pipeline that ranks all available ads, either text-based or graphical, also in order of relevance to the pre-processed query. Ad serving typically involves determining the layout of the ads on the page. Typically the rankings determine placement of ads within the layout. Though such advertising layout algorithms may formulate advertisement placement in different ways, they use page content and individual ad-level features to determine placement. 
         [0024]    In either the search or web page contexts, the ordering of advertisements often relies on a matching process. In the search context, advertisements are matched to the query. In the web page context, ads are matched to page content. 
       Classification and Taxonomies 
       [0025]    In the abstract, embodiments of the present invention are concerned with classes. For example, in some cases there are 10 classes. Preferably the classes are organized in a taxonomy, such as shown in  FIG. 3   a  where class  1  is the root class and classes  7 ,  8 ,  9 , and  10  are leaves. More generally, we only need to know a loss (or equivalent similarity) function L defined between two classes. From a taxonomy, there are several ways of defining this loss function. For example, the path length between classes defines one type of loss function, e.g. L( 7 , 8 ) is less than L( 7 , 10 ). 
         [0026]    As another example, in a case where there are k classes c 1 , . . . c k  it&#39;s possible to define a loss function based on class probabilities: 
         [0000]        L ( c   1   , c   2 )=2 log( p ( Anc ( c   1   , c   2 )))−log( p ( c   1 ))−log( p ( c   2 )). 
         [0000]    Here Anc(c 1 , c 2 ) is the common ancestor of c 1  and c 2  and p(c) is the fraction of training samples, from a set of training samples, whose class is in the sub tree rooted at c. Connecting this example back to the previous case, perhaps the training samples are in classes 2, 7, 8, and 10, and we wish to compare L(7,10) to L(7,8). Here Anc(7,10) is class 1 and Anc(7,8) is class 4. Meanwhile p(1)=1, p(7)=0.25, p(8)=0.25, p(4)=0.5 and p(10)=0.25. Thus, L(7,10)=2*log(1)−2*log(0.25) and L(7,8)=2*log(0.5)−2*log(0.25). Here it is clear that L(7,8) is less than L(7, 10) as log(1) evaluates to zero. 
         [0027]    It is important to note that some embodiments of the present invention need only a defined loss function and not a taxonomy; in other words, the function L might have been constructed without a taxonomy. 
         [0028]      FIG. 3   b  illustrates the general approach of some embodiments. Given an Input Space and k classes c 1 , . . . , c k , a Semantic Space, preferably of lower dimensionality than the input space, is constructed and each class c p  is mapped to a class “representative” Ψ(c p ). The mapping Ψ is constructed such that the distance between two representatives is related to the similarity between the classes. In the example of this figure, the class c 2  is similar to c 3  but very different from c 1 . Then a linear mapping Φ is learned from the Input Space to the Semantic Space. 
         [0029]    Methods consistent with some embodiments are powerful classification algorithms. However, they also excel at the following matching problem: given an instance, find another similar instance (with respect to the given taxonomy). The so-called content match problem described above—for a given page find a semantically related ad—is an instance of the matching problem. As mentioned earlier, many current systems work by classifying the instances into a taxonomy. Note that in this case, classification is a means not an end. Methods consistent with some embodiments of the present invention are able to shortcut the classification problem and solving the matching problem directly. 
         [0030]    Implementations 
         [0031]      FIG. 4  illustrates a hierarchical recognition system consistent with some embodiments of the present invention. The system of  FIG. 4  supports multiple recognition processes, including Classification and Matching. In  FIG. 4 , the system includes preprocessing and application subsystems. 
         [0032]    The preprocessing subsystem performs Embedding and Regression processes. The Embedding process takes a set of classes C and a Loss Function defined over C as inputs. During the Embedding process the preprocessing subsystem learns a first mapping of C to a Semantic Space wherein a distance measure between a first mapped class and a second mapped class correlates to the Loss Function on those two classes. The First Mapping learned during this process relates classes to the Semantic Space. 
         [0033]    The Regression process takes the First Mapping as an input. In some embodiments the Regression process takes the Semantic Space as an input, though preferably the Semantic Space is an implicit input given the classes and the First Mapping. Another input to the Regression process is a set of training examples, which correlate objects in an Input Space to classes in C. The Second Mapping learned during this process relates the Input Space to the Semantic Space. 
         [0034]    At run time, the Second Mapping, or the Second and the First Mappings, are used in recognition processes by an application subsystem. In some embodiments, a classification process is performed at run time on a Test Object from the Input Space. In this process, the application subsystem finds a class of the Test Object by mapping it to the Semantic Space using the Second Mapping comparing the mapped Test Object to the distribution of C mapped by the First Mapping. 
         [0035]    In some embodiments a matching process is performed at run time on a Test object from the Input Space and a set of Candidate Object from the Input Space. The matching process, given the Test Object and the set of Candidate Object, finds the closest Candidate Object by mapping the Test Object and all Candidate Objects to the Semantic Space using the Second Mapping and comparing the mapped the Test Object to the distribution of the mapped Candidate Objects. 
         [0036]    Further Details 
         [0037]    To simplify notation, the description below refers to a set of k classes c 1 , . . . , c k , termed C and a set of N training examples, (x i , y i ), 1≦i≦n, where x i εER d  and y i ε{c 1 , . . . , c k }. 
         [0000]    The classes are preferably organized in a taxonomy, but more generally, we only need to know a loss (or equivalent similarity) function L defined between two classes. 
         [0038]      FIGS. 5   a  and  5   b  illustrate a preprocessing portion of some embodiments of the invention in more detail.  FIG. 5   a  illustrates an embedding step. Embedding comprises finding a mapping Ψ on C that approximately satisfies ∥Ψ(c p )−Ψ(c q )∥=L(c p , c q ), ∀1≧p, q≧k. Application of the mapping Ψ to C produces a semantic space S. Each class c p  is represented in that space by a vector Ψ(c p )εS. The distances in that space are supposed to reflect semantic dissimilarity, where the dissimilarity is quantified through the loss function L. 
         [0039]    In embodiments of the invention embedding is achieved through various techniques such as Multidimensional Scaling (MDS). MDS finds the Ψ(c p ) such that the above equalities are approximately satisfied in the mean squared sense. The dimensionality of S is automatically found by MDS algorithms. However, in some embodiments during this embedding phase components with small variance are eliminated to further reduce the dimensionality of S. 
         [0040]      FIG. 5   b  illustrates a regression step. In some embodiments regression involves learning a mapping Φ: R d →S from the d dimensional Input Space to the Semantic Space. Preferably this is achieved by a standard regression algorithm. For example, some embodiments use regularized linear regression, Φ(x)=W x, where the m×d matrix W is found as the minimizer of the following objective function: 
         [0000]    
       
         
           
             W 
             = 
             
               
                 
                   arg 
                 
                  
                 
                   
                     min 
                     W 
                   
                    
                   
                     
                       1 
                       2 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           , 
                           k 
                         
                       
                        
                       
                         W 
                         
                           j 
                           , 
                           k 
                         
                         2 
                       
                     
                   
                 
               
               + 
               
                 
                   ∑ 
                   i 
                 
                  
                 
                   
                     ( 
                     
                       
                         Wx 
                         i 
                       
                       - 
                       
                         Φ 
                          
                         
                           ( 
                           
                             u 
                             i 
                           
                           ) 
                         
                       
                     
                     ) 
                   
                   2 
                 
               
             
           
         
       
     
         [0041]      FIGS. 5   c  and  5   d  illustrate application steps completed at run time in some embodiments consistent with the invention. In both FIGS. a pattern is mapped into the semantic space.  FIG. 5   c  illustrates a matching process. Consistent with some embodiments the matching process operates on a test object from the input space and a collection of candidate objects from the input space. In the case of a d dimensional input space, for example x, a d dimensional vector, is a test object and X a set of d dimensional vectors is the collection of candidate objects. Also consistent with some embodiments a matching process takes a mapping from the input space to the semantic space, e.g. Φ, as an input. Proceeding with this notation, a matching process operating on x and X finds a closest match within X by mapping x and members of X to S using Φ and comparing Φ (x) the distribution of Φ (X) in S. 
         [0042]    Preferably in the case of matching, the Euclidian distance of the mapped points reflects their dissimilarity. In some embodiments, given the test point x and X a set of points we would like to match x against, the match is given by: 
         [0000]    
       
         
           
             
               match 
                
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               
                 arg 
               
                
               
                 
                   min 
                   
                     
                       x 
                       ′ 
                     
                     ∈ 
                     X 
                   
                 
                  
                 
                    
                   
                     
                       φ 
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     - 
                     
                       Φ 
                        
                       
                         ( 
                         
                           x 
                           ′ 
                         
                         ) 
                       
                     
                   
                    
                 
               
             
           
         
       
     
         [0043]      FIG. 5   d  illustrates a classification process. Consistent with some embodiments the classification process operates on a test object from the input space. In the case of a d dimensional input space, for example x, a d dimensional vector, is a test object. Also consistent with some embodiments a classification process takes a mapping from the input space to the semantic space, e.g. Φ, and a mapping from the classes to the semantic space, e.g. Ψ, and a set of classes C as inputs. Proceeding with this notation, a classification process operating on x and C finds the class of x by mapping x to S using Φ and comparing Φ(x) the distribution of Ψ(C) in S. 
         [0044]    Preferably in the case of classification, the class membership can be inferred from the distances to the class representatives in the semantic space. In various embodiments this inference proceeds either probabilistically or by looking at the minimum distance. For example, in some embodiments the predicted class of a test example x is given by the following: 
         [0000]    
       
         
           
             c 
             = 
             
               
                 arg 
               
                
               
                 
                   min 
                   
                     x 
                     ∈ 
                     
                       ( 
                       
                         
                           c 
                           i 
                         
                         , 
                         
                             
                         
                          
                         … 
                          
                         
                             
                         
                         , 
                         
                           c 
                           j 
                         
                       
                       ) 
                     
                   
                 
                  
                 
                    
                   
                     
                       Φ 
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     - 
                     
                       Φ 
                        
                       
                         ( 
                         c 
                         ) 
                       
                     
                   
                    
                 
               
             
           
         
       
     
         [0045]    Advantages 
         [0046]    Embodiments of the invention account for class hierarchy in ways that result in greater matching and classification accuracy. In many embodiments training and test times are shorter than prior methods because the dimensionality of the semantic space is lower than the number of classes. 
         [0047]    In matching problems such as encountered in sponsored search and content match, both ads and pages can be mapped to a semantic space, providing a measure of semantic similarity. Thus for matching, embodiments of the present invention need not even infer class membership. 
         [0048]    In the case of content match, embedding of page and ad features into a semantic space provides a measure of dissimilarity as well as similarity. This can be useful in scenarios when the compatibility of ads and web pages needs to be established. 
         [0049]    Methods and systems consistent with the present invention incorporate relationships among classes. Such methods can scale up to very large taxonomies and can handle cases where there are more classes than training examples; in such cases a flat classification algorithm is bound to fail. 
         [0050]    Although the present invention has been described in terms of specific exemplary embodiments, it will be appreciated that various modifications and alterations might be made by those skilled in the art without departing from the spirit and scope of the invention. The scope of the invention is not limited to the exemplary embodiments described and should be ascertained by inspecting the appended claims.