We study a class of algorithms that speed up the training process of support vector machines (SVMs) by returning an approximate SVM. We focus on algorithms that reduce the size of the optimization problem by extracting from the original training dataset a small number of representatives and using these representatives to train an approximate SVM. The main contribution of this paper is a PAC-style generalization bound for the resulting approximate SVM, which provides a learning theoretic justification for using the approximate SVM in practice. The proved bound also generalizes and includes as a special case the generalization bound for the exact SVM, which denotes the SVM given by the original training dataset in this paper.

We address the problem of human motion recognition in this paper. The goal of human motion recognition is to recognize the type of motion recorded in a video clip, which consists of a set of temporarily ordered frames. By defining a Mercer kernel between two video clips directly, we propose in this paper a recognition strategy that can incorporate both the information of each individual frame and the temporal ordering between frames. Combining the proposed kernel with the support vector machine, which is one of the most effective classification paradigms, the resulting recognition strategy exhibits excellent performance over real data sets

We propose to speed up the training process of support vector machines (SVM) by resorting to an approximate SVM, where a small number of representatives are extracted from the original training data set and used for training. Theoretical studies show that, in order for the approximate SVM to be similar to the exact SVM given by the original training data set, kernel k-means should be used to extract the representatives. As practical variations, we also propose two efficient implementations of the proposed algorithm, where approximations to kernel k-means are used. The proposed algorithms are compared against the standard training algorithm over real data sets.

We propose a motion recognition strategy that represents a videoclip as a set of filtered images, each of which encodes a short period of motion history. Given a set of videoclips whose motion types are known, a filtered image classifier is built using support vector machines. In offline classification, the label of a test videoclip is obtained by applying majority voting over its filtered images. In online classification, the most probable type of action at an instance is determined by applying the majority voting over the most recent filtered images, which are within a sliding window. The effectiveness of this strategy was demonstrated on real datasets where the videoclips were recorded using a fixed camera whose optical axis is perpendicular to the person's trajectory. In offline recognition, the proposed strategy outperforms a principal component analysis based recognition algorithm. In online recognition, the proposed strategy cannot only classify motions correctly and identify the transition between different types of motions, but also identify the existence of an unknown motion type. This latter capability and the efficiency of the proposed strategy make it possible to create a real-time motion recognition system that can not only make classifications in real-time, but also learn new types of actions and recognize them in the future.

Training support vector machines involves a huge optimization problem and many specially designed algorithms have been proposed. In this paper, we proposed an algorithm called ClusterSVM that accelerates the training process by exploiting the distributional properties of the training data, that is, the natural clustering of the training data and the overall layout of these clusters relative to the decision boundary of support vector machines. The proposed algorithm first partitions the training data into several pair-wise disjoint clusters. Then, the representatives of these clusters are used to train an initial support vector machine, based on which we can approximately identify the support vectors and non-support vectors. After replacing the cluster containing only non-support vectors with its representative, the number of training data can be significantly reduced, thereby speeding up the training process. The proposed ClusterSVM has been tested against the popular training algorithm SMO on both the artificial data and the real data, and a significant speedup was observed. The complexity of ClusterSVM scales with the square of the number of support vectors and, after a further improvement, it is expected that it will scale with square of the number of non-boundary support vectors.