Abstract:
A procedure for fast training and evaluation of support vector machines (SVMs) with linear input features of high dimensionality is presented. The linear input features are derived from raw input data by means of a set of m linear functions defined on the k-dimensional raw input data. Training uses a one-time precomputation on the linear transform matrix in order to allow training on an equivalent training set with vector size k instead of m, given a great computational benefit in case of m&gt;&gt;k. A similar pre-computation is used during evaluation of SVMs, so that the raw input data vector can be used instead of the derived linear feature vector.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to computer mediated object detection. More particularly, the present invention relates to improved support vector machines for classifying data.  
         BACKGROUND  
         [0002]    Any machine learning algorithm for classification/regression highly depends on the type and quality of the feature set. A feature set should ideally reduce intra-class variance and still be highly discriminative. Generally, it is desirable to use a rather small set of features to avoid dimensionality related problems and to speed up training and classification. Due to their simplicity, it is quite common to use linear features as the input to a classifier. There is a variety of powerful analysis methods, which derive linear features from raw input data including principal component analysis, Fisher discriminant analysis, Fourier transforms, Sobel-gradients, wavelets, and haar-likes.  
           [0003]    Support vector machines (SVMs) are a class of learning algorithms for classification/regression that are particularly useful for high dimensional input data with either large or small training sets. Support vector machines suitable for class identification problems work by mapping the input features to the SVM into a high-dimensional feature space and computing linear functions on those mapped features in the high-dimensional feature space. The optimization problem that must be solved during training of a support vector machine has a global minimum and can generally be solved with standard quadratic programming tools. In operation, a support vector machine creates a function from a set of labeled training data. The function can either be a classification function where the output is a binary decision (the input being a category) or the function can be a general regression function. For classification, support vector machines operate by finding a hypersurface in the feature space (of the SVM). This hypersurface will attempt to split the positive examples from the negative examples. The split will be chosen to have the largest distance from the hypersurface to the nearest of the positive and negative examples, generally making the classification correct for testing data that is near, but not identical to the training data.  
           [0004]    There are two simple conventional methods to train and evaluate a support vector machine using linear input features. The first method caches all linear feature vectors z i =Ax i , (i.e., it pre-computes the linear features z i ; x i  denotes the raw input data of training sample i, and A is a matrix specifying all the linear features that are to be derived from the input data x i .) and then uses these vectors to calculate kernel elements K(z i , z j ). Evaluation of a classifier then simply transforms an input pattern x to z=Ax and uses K(z, z i ) in  
         class        (   x   )       =       sign        [       (       ∑     i   =   1     n                       y   i          α   i          K        (     z   ,     z   i       )           )     +   b     ]       =     sign        [       (       ∑     i   =   1     n                       y   i          α   i          K        (     Ax   ,     z   i       )           )     +   b     ]                               
 
           [0005]    where α i  is the optimal solution of the maximization problem, b the associated threshold, and y i  ∈{−1,+1} the pattern label of support vector i.  
           [0006]    For a large number of linear features (e.g., larger than a few thousand) it is usually not possible to store all vectors z i  in memory, either for training or for evaluation. For instance, assuming a derivation of 250,000 linear features from each input data of dimension k&lt;&lt;250,000, a single feature vector may require more than one megabyte of memory storage making training sets with n&gt;1,000 prohibitively expensive with present day computational resources.  
           [0007]    Alternatively, to conserve memory, the function z i =Ax i  can be computed each time a kernel element K((z i , z j ) is accessed. This requires only storage of the original training examples x i . Evaluating a classifier then computes z=Ax and z i =Ax i  for each support vector i. However, this method is computationally very expensive because training a support vector machine needs many evaluations of the kernel function. Even with a kernel cache, far more than 10 6  kernel evaluations to train a classifier on a training set may be required.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]    The inventions will be understood more fully from the detailed description given below and from the accompanying drawings of embodiments of the inventions which, however, should not be taken to limit the inventions to the specific embodiments described, but are for explanation and understanding only.  
         [0009]    [0009]FIG. 1 schematically illustrates software module logic flow for an implementation of a fast support vector machine;  
         [0010]    [0010]FIG. 2 more specifically illustrates a training procedure for a support vector machine with linear input features; and  
         [0011]    [0011]FIG. 3 more specifically illustrates an evaluation procedure of a trained support vector machine with linear input features.  
     
    
     DETAILED DESCRIPTION  
       [0012]    [0012]FIG. 1 illustrates a general system  10  for high speed data analysis of large data sets using a support vector machine. Such data sets  12  can include static or video imagery  14  containing objects to be identified or classified; bioinformatic databases  16  containing, for example, gene or protein sequences, DNA microarray data, sequence data, phylogenetic information, promoter region information; or textual, linguistic, or speech analysis data suitable for machine learning/identification  18 . The same data set can be optionally used both to train and classify data with the appropriate training module  20  and classification module  50 , or alternatively, a novel data set can be classified after training on data set  12 . For example, speech data derived from a small number of persons can be used to train for machine identification of particular words from a large population of users.  
         [0013]    The processing procedure for system  10  may be performed by a properly programmed general-purpose computer alone or in connection with a special purpose computer. Such processing may be performed by a single platform or by a distributed processing platform. In addition, such processing and functionality can be implemented in the form of special purpose hardware, custom application specific integrated circuits (ASICs), configurable FPGA circuits, or in the form of software or firmware being run by a general-purpose or network processor. Data handled in such processing or created as a result of such processing can be stored in any memory as is conventional in the art. By way of example, such data may be stored in a temporary memory, such as in the RAM of a given computer system or subsystem. In addition, or in the alternative, such data may be stored in longer-term storage devices, for example, magnetic disks, rewritable optical disks, and so on. For purposes of the disclosure herein, a computer-readable media may comprise,any form of data storage mechanism, including such existing memory technologies as well as hardware or circuit representations of such structures and of such data.  
         [0014]    A support vector machine is used because it has good generalization performance even for high dimensional input data and small training sets. This makes them a method of choice for many binary classification tasks. A support vector machine solves the following quadratic program:  
           max     α   i              ∑     i   =   1     n                     α   i         -       1   2            ∑     i   =   1     n            ∑     j   =   1     n            y   i          y   j          α   i          α   j          K        (       x   i     ,     x   j       )                           subject                 to                     ∑     i   =   1     n                       y   i          α   i           =   0     ,     0   ≤       α   i          ∀   i                               
 
         [0015]    where n is the number of training examples, x i ∈R k  is the training example i and y i Å{−1,+1} is the class of x i .  
         [0016]    Other support vector machine formulations, e.g. with an L 1 -norm error penalty C, are transparent to this method. Common kernel functions K(x i , x j ) are the linear kernel K(x i ,x j )=x i   T x j , polynomial kernels K(x i ,x j )=(x i   T x j +c) d  of degree d, sigmoid kernels K(x i ,x j )=tan h(x i   T x j +c) and radial basis function (RBF) kernels K(x i ,x j )=exp(−∥x i −x j ∥ 2 /c) with c∈R.  
         [0017]    Computation speed during the support vector machine training procedure is improved by a one time pre-computation step. For example, if A∈R mxk  is the matrix that represents the linear transformation applied to the raw input data set to derive linear features, with vector size of the raw input data being k, with vector size of the linear features being m, and wherein B: =A T A, an upper triangular matrix U∈R kxk  such that B=U T U is determinable, and x i ″=Ux i  for all x i  of the training set is numerically calculated at improved speeds for k&lt;m.  
         [0018]    This can be seen with respect to FIG. 2, where a training software module and procedure  20  requires the linear transformation applied to the raw input data set to derive linear features as well as the raw training data as input ( 32 ), determines B: =A T A (module  34 ), optionally optimized for available memory (module  36 ). Factorization of B results in upper triangular matrix U∈R kxk  (module  38 ) suitable for training such that B=U T U.  
         [0019]    More specifically, a linear kernel evaluation is determined as  
           K(z   i , z j )=z i   T z j =x i   T A T Ax j =x i   T Bx j    
         [0020]    where B=A T A is symmetric and B∈E R kxk .  
         [0021]    A Cholesky factorization of B results in U T U=B where U∈R kxk  is an upper triangular matrix. If a SVM is trained on x i ″=Ux i  instead of z i =Ax i  the results of all kernel evaluations remain unchanged and the solution α i  is identical. However, there are several benefits of using x i ″∈R k  instead of z i ∈R m :  
         [0022]    1) evaluating a feature vector z i =Ax is not necessary.  
         [0023]    2) x i ″ can usually be stored in memory as it is just as large as the original training data x i .  
         [0024]    3) For over-complete feature sets, i.e. m&gt;k, the dot product x i ″ T x j ″ is of lesser complexity than z i   T z j .  
         [0025]    Polynomial kernels [(K(x i ,x j )=(x i   T x j +c) d  of degree d] and sigmoid kernels [K(x i ,x j )=tan h(x i   T x j +c)] also use the dot product z i   T z j  internally, allowing substitution of K(z i , z j ) with K(x i ″, x j ″).  
         [0026]    The same is true for RBF kernels [K(x i ,x j )=exp(−∥ 2 x i −x j ∥ 2 /c)], as can be seen after a few reformulations. A simple reformulation of ∥z i −z j ∥ 2  helps:  
                        z   i     -     z   j            2     =            A        (       x   i     -     x   j       )            2                 =         (       x   i     -     x   j       )     T          A   T          A        (       x   i     -     x   j       )                     =         (       x   i     -     x   j       )     T          U   T          U        (       x   i     -     x   j       )                     =            U        (       x   i     -     x   j       )            2                 =              Ux   i     -     Ux   j            2                                 
 
         [0027]    and substituting K(z i , z j ) with K(x i ″, x j ″) also can be used.  
         [0028]    Since the optimal solution is still the same, the support vector machine can be trained alternatively with x i ″ instead of with z i =Ax i .  
         [0029]    In certain situations, straightforward implementation of this procedure is not possible because of hardware limitations. For example, A might be too large to fit into available computer memory (e.g., in our application A is typically larger than 100,000×1000, while B is only 500×500). However, a blocking scheme can be used to split A into smaller matrices  
         A 1 , . . . , A p  with A T =[A 1   T , . . . , A p   T ] 
         [0030]    It follows that:  
           A   T   A=[A   1   T   , . . . , A   p   T   ][A   1   , . . . , A   p ] T   =A   1   T   A   1   +. . . +A   p   T   A   p    
         [0031]    Accordingly, B can be computed incrementally and only have to fit B and one of the smaller matrices into memory for each step.  
         [0032]    To maintain numerical stability, double or greater precision calculations are generally required. Relative errors of 30% and more for the values of K(x i ″,x j ″) can be encounter if single precision float values are used for A and B. Double precision floats usually provides enough significant digits and is more accurate than using K(z i , z j ) with single precision.  
         [0033]    The Cholesky factorization U T U=B also introduces some numerical inaccuracy. It is possible to avoid it completely with a low additional memory overhead. If x i ′=Bx i , x i ′∈R k  is computed (and keeping x i  in memory as well) every kernel function can be expressed without referring to U. More exactly K(z i , z j )=x i   T x j ′ for linear kernels and a similar result follows for polynomial and sigmoid kernels. For RBF kernels s i =x i   T Bx i  is storable and kernel evaluation is expressed as  
               K        (       z   i     ,     z   j       )       =     K        (       x   i   ″     ,     x   j   ″       )                   =     exp        (       -     (         x   i          U   T        U                   x   i       -     2        x   i          U   T        U                   x   j       +       x   j          U   T        U                   x   j         )       /   c     )                   =       exp        (       -     (       s   i     -     2        x   i   T          x   j   ′       +     s   j       )       /   c     )       .                                 
 
         [0034]    Computation speed during evaluation of a trained support vector machine is also improved by a one-time pre-computation step for evaluation/classification of data sets. As seen in FIG. 3, an evaluation software module and procedure  50  requires determination (module  52 ) of x i ′ for all support vectors x i , keeping the x i ′ in memory as the new support vectors. For linear kernels, K(x,x i ′)=x T x i ′ is determined (module  56 ), for polynomial kernels, K(x,x i ′)=(x T x i ′+c) d  is determined, for sigmoid kernels, and K(x,x i ′)=tan h(x T x i ′+c) is determined (Note K(z,z j )=K(x,x i ′).) The result is classified (module  60 ) For RBF kernels this procedure must be slightly modified as seen with respect modules  54  and  58  [K(x,x i ′)=exp(−(s i −2x T x i ′+x T Bx)/c)].  
         [0035]    More specifically, the pre-computations requires determination of x i ′=Bx i  for all support vectors x i , keeping the x i ′ in memory as the new support vectors. For linear, polynomial and sigmoid kernels:  
           K (( z,z   j )= K ( x,x   i ′)  
         [0036]    where z=Ax  
         [0037]    and, thus, no linear features have to be evaluated.  
         [0038]    For RBF kernels  
         s i   =x   i   T   Bx   i    
         [0039]    is also pre-computed for all support vectors x i  and kept in memory. More specifically, RBF kernels are evaluated as:  
           K (( x,x   i ′)=exp(−( s   i −2x T   x   i   ′+x   T   Bx )/ c )  
         [0040]    requiring linear feature evaluation of x T Bx.  
         [0041]    Computational complexity of classification mainly depends on three factors: feature evaluation, the dot product inside the kernel function and the number of support vectors. The evaluation scheme does not affect the number of support vectors. For m&gt;&gt;k classification is significantly faster, because dot product and feature evaluation are of lower complexity. For m≈k only feature evaluation is faster. This effect is almost negligible for high support vector counts.  
         [0042]    Reference in the specification to “an embodiment,” “one embodiment,” “some embodiments,” or “other embodiments” means that a particular feature, structure, or characteristic described in connection with the embodiments is included in at least some embodiments, but not necessarily all embodiments, of the invention. The various appearances “an embodiment,” “one embodiment,” or “some embodiments” are not necessarily all referring to the same embodiments.  
         [0043]    If the specification states a component, feature, structure, or characteristic “may”, “might”, or “could” be included, that particular component, feature, structure, or characteristic is not required to be included. If the specification or claim refers to “a” or “an” element, that does not mean there is only one of the element. If the specification or claims refer to “an additional” element, that does not preclude there being more than one of the additional element.  
         [0044]    Those skilled in the art having the benefit of this disclosure will appreciate that many other variations from the foregoing description and drawings may be made within the scope of the present invention. Accordingly, it is the following claims including any amendments thereto that define the scope of the invention.