Abstract: Standard Support Vector Machine (SVM) training has O(l3) time and O(l3)space complexities,where L is the training set size. It is thus computationally infeasible on very large data sets. A novel SVM training method, Approximatc Vector Machine (AVM)，based on approximate solution was presented to scale up kernel methods on very large data sets. This approach only obtains an approximately optimal hyper plane by incremental learning, and uses probabilistic speedup and hot start tricks to accelerate training speed during each iterative stage. hheoretical analysis indicates that AVM has the time and space complexities that are independent of training set size. Experiments on very large data sets show that the proposed method not only preserves the generalization performance of the original SVM classifiers,but outperforms existing scalcup methods in terms of training time and number of support vectors.

Key words: Support vector machine, Kernel function, Incremental learning, Approximate solution, Core set