Between-subclass piece-wise linear solutions in large scale kernel SVM learning. (November 2019) - Dhamecha, Tejas Indulal; Noore, Afzel; Singh, Richa; Vatsa, Mayank
Highlights: SRS-SVM and HSRS-SVM are proposed to efficiently apply SVM on large training data. They utilize the subclass structure of data to estimate the set of support vectors. Results on multiple real and synthetic databases show reduction in the training time. Results on the LFW face database show the suitability with deep representations also. Abstract: The paper proposes a novel approach for learning kernel Support Vector Machines (SVM) from large scale data with reduced computation time. The proposed approach, termed as Subclass Reduced Set SVM (SRS-SVM), utilizes the subclass structure of data to effectively estimate the candidate support vector set. Since the candidate support vector set cardinality is only a fraction of the training set cardinality, learning SVM from the former requires less time without significantly changing the decision boundary. SRS-SVM depends on a domain knowledge related input parameter, i.e., number of subclasses. To reduce the domain knowledge dependency and to make the approach less sensitive to the subclass parameter, we extend the proposed SRS-SVM to create a robust and improved hierarchical model termed as the Hierarchical Subclass Reduced Set SVM (HSRS-SVM). Since SRS-SVM and HSRS-SVM splits non-linear optimization problem into multiple (smaller) linear optimization problems, both of them are amenable to parallelization. The effectiveness of the proposed approaches is evaluated on four synthetic and six real-world datasets. The performance is also compared with traditional solver (LibSVM) and state-of-the-art approaches such as divide-and-conquer SVM, FastFood, and LLSVM. The experimental results demonstrate that the proposed approach achieves similar classification accuracies while requiring fewer folds of reduced computation time as compared to existing solvers. We further demonstrate the suitability and improved performance of the proposed HSRS-SVM with deep learning features for face recognition using Labeled Faces in the Wild (LFW) dataset.