1. Field of the Invention
The present invention relates to a support vector (SV) reduction method for multi-class support vector machine (hereinafter, “SVM”), and particularly relates to an SV reduction method for multi-class SVM by which a number of SVs can be reduced at high precision and high speed. In the following, “support vector” may at times be indicated as “SV.”
2. Description of the Related Art
Although initially, support vector machines were designed for binary-class classification tasks, support vector machines designed for multi-class classification have also been developed in recent years. In a multi-class classification problem, more than one SVM are used to perform classification into multiple classes. In a multi-class SVM, a final decision function ft is calculated based on a function ft (where t=1, 2, . . . , T) of time t that is from 1 to T:
                    [                  Formula          ⁢                                          ⁢          1                ]                                                                                                f              t                        ⁡                          (              x              )                                =                                                    ∑                                  i                  =                  1                                                  N                  S                                            ⁢                                                α                  ti                                ⁢                                  K                  ⁡                                      (                                                                  x                        i                                            ,                      x                                        )                                                                        +                          b              t                                      ,                  t          =          1                ,        …        ⁢                                  ,        T                            (        1        )            
In the above, K(x, y) is a kernel function that calculates a dot product of two vectors x and y in some feature space. A time complexity of calculation of Formula (1) above increases with a number xi (i=1, . . . , NS) of SVs.
Reduced set methods for reducing the number of SVs are thus being studied. A main task is to construct a new set of vectors zi (i=1, . . . , NZ) that are reduced in number and coefficients βti (i=1, . . . , Nz, t=1, . . . , T) corresponding thereto. The new functions f′t are as indicated in Formula (2) below.
                    [                  Formula          ⁢                                          ⁢          2                ]                                                                                                f              t              ′                        ⁡                          (              x              )                                =                                                    ∑                                  i                  =                  1                                                  N                  Z                                            ⁢                                                β                  ti                                ⁢                                  K                  ⁡                                      (                                                                  z                        i                                            ,                      x                                        )                                                                        +                          b              t                                      ,                  t          =          1                ,        …        ⁢                                  ,        T                            (        2        )            
In the above, NZ<<NS, and the new functions f′t(x) are thus calculated simpler and run faster when evaluating a new vector x.
As conventional methods for deriving Formula (2) from Formula (1), in other words, as conventional methods for reducing the number of SVs, the following methods (1) to (3) have been proposed.
(1) Top-Down Method for Two-Class SVM (Binary SVM) (Non-Patent Documents 1 and 2)
In a two-class SVM (an SVM for performing a process of classifying into two classes), each SV is associated with a single coefficient. In the method described in Non-Patent Documents 1 and 2, temporary vectors zi (i=1, 2, . . . , Nz) are derived using Formulae (3) and (4) shown below. Once the temporary vectors zi are derived, the coefficients βi are determined.
                              [                      Formula            ⁢                                                  ⁢            3                    ]                ⁢                                                                                                (                                    z              i                        ,                          β              i                                )                =                                            arg              ⁢                                                          ⁢              min                                      z              ,              β                                ⁢                                                                Ψ                                  i                  -                  1                                            -                              βΦ                ⁡                                  (                  z                  )                                                                                                    (        3        )            
In the above, ψi is expressed by Formula (4) shown below:
                    [                  Formula          ⁢                                          ⁢          4                ]                                                                                  Ψ            i                    =                                                    ∑                                  k                  =                  1                                                  N                  S                                            ⁢                                                α                  k                                ⁢                                  Φ                  ⁡                                      (                                          x                      k                                        )                                                                        -                                          ∑                                  k                  =                  1                                i                            ⁢                                                β                  k                                ⁢                                  Φ                  ⁡                                      (                                          z                      k                                        )                                                                                      ,                              Ψ            0                    =                                    ∑                              k                =                1                                            N                S                                      ⁢                                          α                k                            ⁢                              Φ                ⁡                                  (                                      x                    k                                    )                                                                                        (        4        )            
The classification function Φ(z) of Formula (3) is a multivariable function of multiple variables z (=z1, z2, . . . , zn) and thus a problem of a local minimum optimization solution occurs as be described below.
(2) Bottom-Up Method for Two-Class SVM (Non-Patent Document 3)
A method of reducing the number of SVs by a bottom-up method, that is, a method of iteratively selecting two SVs and replacing these by a newly constructed vector is proposed in Non-Patent Document 3.
(3) Top-Down Method for Multi-Class SVMs (Non-Patent Document 4)
A method of simplifying multi-class SVMs by extension of the reduced set construction method of Non-Patent Documents 1 and 2 is proposed in Non-Patent Document 4. In each iteration, a single, new, reduced SVz in a single SVM is generated and shared with the others by retraining all of the SVMs.
Non-Patent Document 1: Burges, C. J. C. 1996. Simplified support vector decision rules. International Conference on Machine Learning, 71-77.
Non-Patent Document 2: B. Scholkopf, S. Mika, C. J. C. Burges, P. Knirsch, K.-R. Muller, G. Ratsch, and A. Smola, “Input Space vs. Feature Space in Kernel-Based Methods,” IEEE Trans. Neural Networks, vol. 10, pp. 1,000-1,017, September 1999.
Non-Patent Document 3: Nguyen D. D., Ho, T. B. 2005. An Efficient Method for Simplifying Support Vector Machines. International Conference on Machine Learning, ICML 2005, Bonn, Aug. 7-11, 2005, 617-624.
Non-Patent Document 4: Tang, B. and Mazzoni, D. 2006. Multi-class reduced-set support vector machines. International Conference on Machine Learning, Jun. 25-29, 2006. ICML'06, vol. 148. ACM, New York, N.Y., 921-928.
However, the conventional methods (1) to (3) described above have the following issues:
1. Top-Down Method for Two-Class SVM (Binary SVM) (Non-Patent Documents 1 and 2)
Main drawbacks of this method are that the SVM is poor in performance in that trapping in a local minimum optimization solution occurs readily and that the search for z in Formula (3) must be repeated many times to obtain a satisfactorily simplified SVM. A cause of becoming trapped in the local minimum optimization solution is that the classification function Φ(z) is a multivariable function.
2. Bottom-Up Method for Two-Class SVM (Non-Patent Document 3)
This method has the issues of being poor in precision due to trapping in a local minimum occurring readily and being applicable only to a two-class SVM with which each SV simply corresponds to only a single coefficient.
3. Top-Down Method for Multi-Class SVMs (Non-Patent Document 4)
In this method, the two-class SVM is extended and there is thus the issue of the SVMs being poor in precision due to trapping in a local minimum optimization solution occurring readily. To alleviate the problem of the local minimum optimization solution, a different evolution algorithm is used in combination with a gradient descent method in the process of constructing the reduced vectors. However, due to the nature of the problem, the classification result is unstable.