Abstract:
A method and apparatus based on transposition to speed up learning computations on sparse data are disclosed. For example, the method receives an support vector comprising at least one feature represented by one non-zero entry. The method then identifies at least one column within a matrix with non-zero entries, wherein the at least one column is identified in accordance with the at least one feature of the support vector. The method then performs kernel computations using successive list merging on the at least one identified column of the matrix and the support vector to derive a result vector, wherein the result vector is used in a data learning function.

Description:
The present invention relates generally to Machine Learning (ML) and Information Retrieval (IR) and, more particularly, to a method for providing fast kernel learning on sparse data, e.g., Support Vector Machine (SVM) learning. 
   BACKGROUND OF THE INVENTION 
   Kernel-based methods such as Support Vector Machines (SVM) represent the state-of-the-art in classification techniques. Support Vector Machines are a set of related supervised learning methods used for data classification. However, their application is limited by the scaling behavior of their training algorithm which, in most cases, scales quadratically with the number of training examples. When dealing with very large datasets, a key issue in SVM learning is to find examples which are critical for defining the separation between two classification classes quickly and efficiently. Traditional SVM often relies on sequential optimization where only a few examples are added in each computation iteration and requires performing dot-products over sparse feature vectors. In most iterative algorithms, the kernel computation can be folded into a matrix-vector multiplication; however, these types of algorithms are extremely inefficient when dealing with sparse data. An m by n matrix M is a 2-dimensional array of numbers or abstract quantities with m rows and n columns. A vector is simply an m by 1 or a 1 by n matrix. A dot-product, also known as the scalar product, is a binary operation which takes two vectors over the real numbers R and returns a real-valued scalar quantity. In Machine Learning (ML), the kernel trick is a method for easily converting a linear classifier algorithm into a non-linear one, by mapping the original observations into a higher-dimensional non-linear space so that linear classification in the new space is equivalent to non-linear classification in the original space. 
   Therefore, a need exists for a method for providing fast kernel learning on sparse data in kernel based learning. 
   SUMMARY OF THE INVENTION 
   In one embodiment, the present invention enables a method based on transposition to speed up learning computations on sparse data. For example, the method receives an support vector comprising at least one feature represented by one non-zero entry. The method then identifies at least one column within a matrix with non-zero entries, wherein the at least one column is identified in accordance with the at least one feature of the support vector. The method then performs kernel computations using successive list merging on the at least one identified column of the matrix and the support vector to derive a result vector, wherein the result vector is used in a data learning function. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The teaching of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which: 
       FIG. 1  illustrates a matrix vector multiplication example related to the present invention; 
       FIG. 2  illustrates a pseudo code of a transpose matrix-vector multiplication function that represents the transpose computation method related to the present invention; 
       FIG. 3  illustrates a pseudo code of a vector to index-value transformation function related to the present invention; 
       FIG. 4  illustrates a pseudo code of a sparse list merging function related to the present invention; 
       FIG. 5  illustrates a transpose matrix-vector multiplication example of the present invention; 
       FIG. 6  illustrates a sparse list merging example of the present invention; and 
       FIG. 7  illustrates a high level block diagram of a general purpose computer suitable for use in performing the functions described herein. 
   

   To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures. 
   DETAILED DESCRIPTION 
   Machine learning algorithms often comprise of sequential procedures where a new example is added and the score of all training examples is modified accordingly. In particular, kernel based algorithms rely on the computation of kernels between pairs of examples to solve classification or clustering problems. Most of them require an iterative learning procedure. 
   The kernel classifier is represented as a list of support vectors x k  and their respective multipliers α k  (in the classification case, the label y k ε{−1,1} gives the sign of α k ). The classifier score for vector x is f(x)=Σ k α k K(x,x k ). Each iteration comprises of addition or modification of one or more support vectors. At each iteration, it is desirable to find the best candidate support vector to add or update. For that purpose, it is necessary to keep an update of the scores of all training examples or a large subset of these training examples (called the active set). When adding factor δα k  to the multiplier α k  of support vector x k , these scores must be incremented as follows:
 
∀ i;f ( x   i )= f ( x   i )+δα k   K ( x   i   ,x   k )  Eq. 1
 
   For each modification of a support vector multiplier, the main required computation is the kernels K(x, x k ) between the support vector x k  and each vector of the active set. 
   Given the algorithm, one usually attempts to optimize the computation of each kernel individually. This focus on the optimization of a single kernel does not take into account the fact that entire line of kernels must be computed at the same time. However, in the case of very sparse data, a very different speedup strategy may be needed. Take a sequential optimization algorithm which adds a single training vector to the set of support vectors: one must look for the vectors in the training set whose score need to be updated after this addition. Only vectors which share features with the added support vector need to have their score updated, and their proportion can be small if the data is extremely sparse. 
   This indicates that, in this case, the most time consuming part of the learning process is to retrieve the small proportion of training vectors which have features in common with the added support vector, and, as in information retrieval, the concept of inverted index can be useful. 
   For instance, suppose that our new support vector corresponds to the sentence “I want to check my bill”, and that we reduced it to a vector with 3 active features (“want”, “check”, “bill”), ignoring function words such as “I”, “to” and “my”. The inverted index approach would retrieve the list of vectors including these three words and merge them. Thus, rather than computing the kernels with every possible example, one would rather focus on examples which contain “want”, “check” and “bill”. 
   To formalize this intuition, it is convenient to define a matrix multiplication framework, which is presented in the subsequent paragraphs. 
   The kernel can often be expressed as a function of the dot-product K(x i , x 2 )=φ(           x 1 ,x 2           ). This includes most major vector kernels such as polynomial, Gaussian and Sigmoid kernels. For instance, in the Polynomial case, φ(t)=(at+b) p . The Gaussian kernel can be written as:
                   K   ⁡     (       x   1     ,     x   2       )       =     exp   -       1     σ   2       ⁢     (            x   1          +          x   2          -     2   ⁢     〈       x   1     ,     x   2       〉         )                 Eq   .           ⁢   2               
where the norms ∥x 1 ∥ and ∥x 2 ∥ are computed in advance.
 
   In summary, for a large class of vectorial kernels, one must compute, for each vector x i  in the active set, the dot-product y i =           x i ,x k           . By defining the matrix M with rows M i =x i , we obtain the matrix-vector multiplication y=Mx k . As shown in the following table 1, the notation in the rest of this document has both a “matrix multiplication” and “SVM training” interpretation and departs from the traditional SVM notation.
   
     
       
             
             
             
             
             
           
         
             
                 
               TABLE 1 
             
             
                 
                 
             
             
                 
               Symbol 
               Type 
               Matrix 
               SVM Training 
             
             
                 
                 
             
           
           
             
                 
               N r   
               Number 
               rows 
               Train samples 
             
             
                 
               N c   
               Number 
               columns 
               Total features 
             
             
                 
               x 
               Vector 
               multiplicand 
               Input 
             
             
                 
               y 
               Vector 
               product 
               Dot-product 
             
             
                 
                 
             
           
        
       
     
   
     FIG. 1  illustrates a matrix vector multiplication example  100  related to the present invention. As shown in  FIG. 1 , the example matrix M has six (6) rows corresponding to active set vectors {X 1 , . . . , X 6 } and six (6) columns corresponding to features {F 1 , . . . , F 6 }. For illustrative purposes, all non-zero matrix or vector elements have values of 1 and are represented by either an outlined or a solid circle. The result Y of the matrix-vector multiplication of X and X i  appears in the right column, where each element is a dot-product that counts the number of circles shared by X and X i . Solid circles represent features in matrix M, comprising of rows X 1  through X 6 , that have non-zero contributions to the dot-product results and outlined circles represent features in matrix M that have zero contributions to the dot-product results. A standard dot-product will have to access every non-zero feature in each vector, a total of 14 feature instances represented by 10 outlined circles and 4 solid circles, even when features F 2 , F 3 , F 5 , and F 6  are not present in the support vector X and when the product produces zero contribution to the result. Therefore, traditional kernel methods requires dot-product computations over non-overlapping features, represented by the 10 outlined circles, even though these computations do not have any contributions to the final dot-product results. In other words, 10 out of the 14 dot-product related computations are unnecessarily performed in traditional methods. Therefore, a need exists for a method for providing fast kernel learning with sparse data in kernel based learning. 
   In one embodiment, the present invention enables a method based on transposition to speed up SVM learning computations on sparse data. Data is considered sparse when the number of active or non-zero features in a training vector is much lower than the total number of features. Instead of performing dot-products over sparse feature vectors, the present invention enables SVM learning computations to incrementally merge lists of training examples to minimize access to the sparse data, and hence providing dramatic speedup in SVM learning computations when compared to traditional kernel learning methods on sparse data. 
   Referring back to  FIG. 1  to further illustrate the present invention, the transpose approach of the present invention only considers columns F 1  and F 4 : the 6 dot products in column Y are obtained by merging the lists represented by columns F 1  and F 4 . The total number of operations is only proportional to the number of solid circles in these columns. When compared to the traditional dot-product algorithm that has to access every single circle to perform a total of 14 dot-product related computations, the present inventions only performs 4 dot-product computations to obtain the same dot-product results as shown in column Y. 
   The transpose, or the inverted index, approach to matrix-vector multiplication is the following.  FIG. 1  shows that only the columns of the matrix M that correspond to components that are non-zero in X contribute to the result Y and suggests an algorithm whose complexity would be a function of |X| where |X| is the number of non-zero components in vector X. A transpose representation of the matrix, where columns are accessed first, is therefore required. 
   Instead of going through each row M i , the procedure goes through each column M., j . Instead of computing each component of Y=MX separately, successive refinements of Y are computed iteratively over the columns of M that correspond to non-zero values of X. 
     FIG. 2  illustrates a pseudo code of a transpose matrix-vector multiplication function  200  that represents the transpose computation method related to the present invention. The transpose sparse matrix vector multiplication algorithm relies on function TADD, pseudo code section  220  as shown in  FIG. 2 , that performs a component-wise addition between v 1 =Y and v 2 =M., j  weighted by w=x j . 
   The transpose algorithm presented produces a dense Y vector as a result. As to be shown later, a list of (index, value) pairs (e.g., broadly a list format) will be much more efficient for further processing.  FIG. 3  illustrates a pseudo code of a vector to index-value transformation function  300  related to the present invention. To obtain this list, the transformation described in the algorithm VEC 2 LIST as shown in  FIG. 3  is required. The operation, as shown in pseudo code section  310  in  FIG. 3 , is simply to access each Y element, and must be performed N T  times, where N r  is the number of elements in Y. 
   In order to avoid any transformation from dense vectors to (index, value) lists, the TADD function shown in  FIG. 2  can be modified to exploit sparsity by also encoding the Y vector as an (index, value) list. 
     FIG. 4  illustrates a pseudo code of a sparse list merging function  400  related to the present invention. Initially, Y′ is an empty list, and an incremental process merges Y′ with the list M., j . During each iteration of computations, Y′ is appropriately updated during each pass of the while loop as shown in pseudo code section  410  in  FIG. 4 . When the while loop terminates, the updated vector Y′ produced in the computations so far will be used as the initial vector for the next iteration of merging. Note also that the very first initial vector used for the computations of the dot-product result is simply the encoded vector of the first non-zero feature column in M. 
   The TMRG function shown in  FIG. 4  becomes the merging of two sorted lists with addition of the values when the same index is found in both lists. This corresponds to pseudo section  420  shown in  FIG. 4 . 
   When an index is found in Y′ that does not match any index in the next non-zero feature column M., j , where column j is the next non-zero feature column in matrix M that needs to be merged, the TMRG function shown in  FIG. 4  simply copies the (index, value) pair corresponding to that index to the merged list Y′. This corresponds to pseudo section  440  shown in  FIG. 4 . 
   When an index is found in the next non-zero feature column M., j  where j is the next non-zero feature column in matrix M that needs to be merged, that does not match any index in the initial vector list Y′, the TMRG function shown in  FIG. 4  performs a multiplication computation between the value corresponding to the index and its associated weight and updates the result vector Y′ with the multiplication computation result. This corresponds to pseudo section  430  shown in  FIG. 4 . 
   Function TMRG has the same number of multiplication and addition operations, corresponding to pseudo code section  420  and  430  as shown in  FIG. 4 , as function TADD but it also requires copy operations, corresponding to pseudo code section  440  as shown in  FIG. 4 , as well. 
   To further illustrate the transpose matrix-vector function  200  computation example using matrix, M, and support vector, X, shown in  FIG. 1 ,  FIG. 5  illustrates a transpose matrix-vector multiplication example or method  500  using function  200  of the present invention. Note that X only contains feature F 1  and F 4  with corresponding columns  1  and  4  in M and the initial result vector Y is initialized to zero. Note also that the non-zero entries in X all have values of one; hence, all non-zero weightings used in the dot-product computations are ones. In example  500 , during the first iteration of the computation, the initial full result vector is initialized to all zero. The first column of matrix M representing feature F 1  is encoded using (index, value) pairs as shown in list  510 . 
   In step  515 , function  200  performs a multiplication and add operation between the second entry in the initial full vector Y and the corresponding first entry of the (index, value) pair list  510  to produce a resulting value of 1 in index position  2  of the updated result vector Y. 
   In step  520 , function  200  performs a multiplication and add operation between the fourth entry in the initial full vector Y and the corresponding second entry of the (index, value) pair list  510  to produce a resulting value of 1 in index position  4  of the updated result vector Y. This completes the first iteration of the TADD function corresponding to pseudo code section  220  as shown in  FIG. 2 . 
   Then, the updated result vector Y produced in the previous iteration of the computations will now be used as the initial full vector for the current iteration of the computations. In other words, the updated result vector  525  is used as the initial full result vector for the next iteration of the computation. The fourth column of matrix M representing feature F 4  is encoded using (index, value) pairs as shown in list  530 . 
   In step  535 , function  200  performs a multiplication and add operation between the first entry in the initial full result vector Y and the corresponding first entry of the (index, value) pair list  530  to produce a resulting value of 1 in index position  1  of the updated result vector Y. 
   In step  540 , function  200  performs a multiplication and add operation between the fourth entry in the initial full result vector Y and the corresponding second entry of the (index, value) pair list  530  to produce a resulting value of 2 in index position  4  of the updated result vector Y. This completes the second or final iteration of the TADD function corresponding to pseudo code section  220  as shown in  FIG. 2  and the latest updated result vector Y is the final result vector. At this point, the computation of the final result vector  545  has been computed. In addition, the final result vector  545  can be further encoded as (index-value) pair format as shown in list  550  in  FIG. 5  using function  300  as shown in  FIG. 3  to facilitate more efficient storage and processing of the final result vector. 
   To further illustrate the sparse list merging function  400  computation example using matrix, M, and training vector, X, shown in  FIG. 1 ,  FIG. 6  illustrates a sparse list merging example  600  using function  400  of the present invention. Note the X only contains features F 1  and F 4  with corresponding column  1  and column  4  in M. Note also that the non-zero entries in X all have values of one; hence, all non-zero weightings used in the dot-product computations are ones. In example  600 , the initial sparse vector is simply the encoded vector of feature column  1  in M representing feature F 1 ; therefore, the initial sparse vector representing feature F 1  is encoded in (index, value) pair as shown in list  610 . The fourth column of matrix M representing feature F 4  is encoded using (index, value) pairs as shown in list  615 . 
   In step  620 , function  400  performs a copy operation of the first entry, of the initial sparse vector to produce a resulting value of 1 in index position  1  of the final result vector  635 . 
   In step  625 , function  400  performs a multiplication operation on the first entry of the (index, value) pair list  615  to produce a resulting value of 1 in index position  2  of the final result vector  635 . 
   In step  630 , function  400  performs a multiplication and add operation between the second entry of the initial sparse vector  610  and the corresponding (index, value) pair, the second entry, in list  615  to produce a resulting value of 2 in index position  3  of the final result vector  635 . At this point, the final result vector computations are completed since both non-zero feature columns F 1  and F 4  have been merged. 
     FIG. 7  depicts a high level block diagram of a general purpose computer suitable for use in performing the functions described herein. As depicted in  FIG. 7 , the system  700  comprises a processor element  702  (e.g., a CPU), a memory  704 , e.g., random access memory (RAM) and/or read only memory (ROM), a module  705  for providing fast kernel learning on sparse data, and various input/output devices  706  (e.g., storage devices, including but not limited to, a tape drive, a floppy drive, a hard disk drive or a compact disk drive, a receiver, a transmitter, a speaker, a display, a speech synthesizer, an output port, and a user input device (such as a keyboard, a keypad, a mouse, and the like)). 
   It should be noted that the present invention can be implemented in software and/or in a combination of software and hardware, e.g., using application specific integrated circuits (ASIC), a general purpose computer, a Graphical Processing Unit (GPU) or any other hardware equivalents. In one embodiment, the present module or process  705  for providing fast kernel learning on sparse data can be loaded into memory  704  and executed by processor  702  to implement the functions as discussed above. As such, the present process  705  for providing fast kernel learning on sparse data (including associated data structures) of the present invention can be stored on a computer readable medium or carrier, e.g., RAM memory, magnetic or optical drive or diskette and the like. 
   While various embodiments have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of a preferred embodiment should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.