Chunking-Synthetic Approaches to Large-Scale Kernel Machines

Abstract

We consider a kernel-based approach to nonlinear classification that combines the generation of ?synthetic? points (to be used in the kernel) with ?chunking? (working with subsets of the data) in order to significantly reduce the size of the optimization problems required to construct classifiers for massive datasets. Rather than solving a single massive classification problem involving all points in the training set, we employ a series of problems that gradually increase in size and which consider kernels based on small numbers of synthetic points. These synthetic points are generated by solving relatively small nonlinear unconstrained optimization problems. In addition to greatly reducing optimization problem size, the procedure that we describe also has the advantage of being easily parallelized. Computational results show that our method efficiently generates high-performance classifiers on a variety of problems involving both real and randomly generated datasets.