Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
2000-08-22
2003-12-09
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
C706S020000, C706S012000
Reexamination Certificate
active
06662170
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to support vector machines (SVMs), and more particularly to methods and systems for boosting SVMs.
2. Description of the Related Art
Machine learning algorithms are used in many applications, such as, for instance, handwriting recognition and optical character recognition, other pattern recognition such as face recognition, eye detection, and credit card fraud detection. Machine learning algorithms are also used in, e.g., high-dimensional search in multimedia databases that contain text documents, audio, and video.
One type of machine learning algorithm is the so-called Support Vector Machine (SVM) introduced by V. N. Vapnik in
Statistical Learning Theory
, John Wiley & Sons, New York, 1998, incorporated herein by reference. Like other types of classifiers such as neural networks and decision trees, SVMs require training. Specifically, using a set of training data, classification parameters for a classifier are developed and then applied to other data for classifying the data in accordance with the classification parameters learned from the training data.
SVMs are trained using quadratic programming. Unfortunately, this training becomes impractical when the amount of training data becomes large, because a relatively large amount of memory is required and because the training process becomes excessively slow. In other words, methods for training SVMs do not scale well for large training data sets. It is nonetheless desirable to use a large amount of training data, however, for optimal training, i.e., for the highest classification accuracy.
One way to improve the performance of classifiers such as neural networks and decision trees is to use “boosting”, a term for a statistical resampling technique for generating a series of training data sets for training an ensemble of classifiers. In boosting, the distribution of a training set in a series of training sets is overrepresented by training patterns that earlier classifiers in the ensemble incorrectly classified. Accordingly, in boosting the individual classifiers are trained hierarchically to learn progressively more difficult parts of a classification problem.
Heretofore, boosting has not been used with SVMs, particularly linear SVMs, because linear SVMs are so-called “stable” classifiers and it has been believed that boosting improves the performance only of unstable classifiers such as decision trees and neural networks, and not the performance of stable classifiers. Thus, the only previous motivation for using boosting—improving classifier performance—was inapplicable to SVMs. We have recognized, however, that boosting can be used for another reason in the context of SVMs which has not yet been recognized in the prior art. Specifically, we have recognized that while improving the performance of SVMs might not provide motivation for boosting, boosting can nevertheless be used to solve the above-noted scaling problem of SVMs, i.e., boosting can be used to speed up training time while reducing memory requirements.
SUMMARY OF THE INVENTION
The invention is a general purpose computer programmed according to the inventive steps herein. The invention can also be embodied as an article of manufacture—a machine component that is used by a digital processing apparatus and which tangibly embodies a program of instructions that are executable by the digital processing apparatus to undertake the logic disclosed herein. This invention is realized in a critical machine component that causes a digital processing apparatus to undertake the inventive logic herein.
In accordance with the present invention, a computer-implemented method is disclosed for training a support vector machine (SVM) useful in machine learning that includes boosting the SVM. Preferably, the act of boosting includes providing successive subsets of data from a training data set, with data being provided in at least one subset based on data in at least one preceding subset.
More specifically, the boosting act includes providing a subset of data from a training data set. Using the subset of data, at least one parameter (and preferably both parameters W and B) of an optimal hyperplane is obtained. Then, a classifier weight is derived based at least in part on the current values of the hyperplane parameters and on a classification error. The hyperplane parameters are updated based at least in part on the classifier weight, and the above steps are iteratively repeated. The subset of data used in an iteration is based at least in part on data in a prior subset, and more particularly on whether data in a prior subset was correctly classified as indicated by a probability distribution. Data is inserted into a subset in accordance with at least the probability distribution.
In another aspect, a computer is programmed to undertake logic for providing a support vector machine (SVM). The logic includes inputting successive subsets of training data into successive SVMs to obtain a final SVM having iteratively derived parameters of an optimal hyperplane.
In still another aspect, a computer program product includes computer readable code means for receiving at least one support vector machine (SVM). Computer readable code means boost the SVM using iterations of training data subsets.
REFERENCES:
Raetsch, Gunnar et al, SVM and Boosting: One Class, Sankt Augustin:GMD—Forschungszentrum Informationstechnik, 2000. —36 S.—(GMD report; 119), pp. 1-23.*
Boser, Bernhard E., A Training Algorithm for Optimal Margin Classifiers, 5th Ann. Workshop on Computational Learning Theory 1992, Pittsburgh ACM, Jul. 1992, pp. 144-152.*
Chen, Yunqiang, One-class SVM for learning in image retrieval, Image Processing, 2001. Proceedings 2001 International Conference on, vol.: 1, Oct. 7-10, 2001, pp. 34-37.*
G. Guo, H. Zhang, S. Z. Li, “Boosting for Content-Based Audio Classification and Retrieval: An Evaluation,” Microsoft Research Technical Report: MSR-TR-2001-15.*
Pavlov, Dmitry, Scaling-Up Support Vector Machines Using Boosting Algorithm, International Conference on Pattern Recognition (ICPR'00)-vol. 2, Sep. 3-8, 2000, Barcelona, Spain, pp. 2219-2222.*
Publication: “Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods”. Schapire et al. The Annals of Statistics, 26(5): 1651-1686. pp. 1-30. 1998.
Publication: “A Brief Introduction to Boosting”. Robert E. Schapire. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. pp. 1-6. Jul. 31, 1999.
Publication: “Trends and Controversies. Support Vector Machines”. Marti A. Hearst. IEEE Intelligent Systems. pp. 18-28. Jul./Aug. 1998.
Book: Chapter 12 “Fast Training of Support Vector Machines Using Sequential Minimal Optimization”, John C. Platt. Generic Author Design Sample Pages. pp. 41-64. Aug., 1998.
Publication: “Arcing Classifiers”. Breiman. The Annals of Statistics. 26(3):801-849. pp. 1-23. 1998.
Publication: “A Tutorial on Support Vector Machines for Pattern Recognition”, Burges. Knowledge Discovery and Data Mining, 2(2), pp. 1-43. 1998.
Dom Byron Edward
Mao Jianchang
Pavlov Dmitry
Rogitz John L.
Starks, Jr. Wilbert L.
LandOfFree
System and method for boosting support vector machines does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for boosting support vector machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for boosting support vector machines will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3106703