Local-to-Global Support Vector Machines (LGSVMs)

For supervised classification tasks that involve a large number of instances, we propose and study a new efficient tool, namely the Local-to-Global Support Vector Machine (LGSVM) method. Its background somehow lies in the framework of approximation theory and of local kernel-based models, such as the Partition of Unity (PU) method. Indeed, even if the latter needs to be accurately tailored for classification tasks, such as allowing the use of the cosine semi-metric for defining the patches, the LGSVM is a global method constructed by gluing together the local SVM contributions via compactly supported weights. When the number of instances grows, such a construction of a global classifier enables us to significantly reduce the usually high complexity cost of SVMs. This claim is supported by a theoretical analysis of the LGSVM and of its complexity as well as by extensive numerical experiments carried out by considering benchmark datasets.