Fast Polynomial Kernel Based Algorithms For Classification

With the rapid development of data mining,large and diverse sets of data such as Internet data,medical data and image data exist in various engineering applications.The massive data makes the prediction much more precisely.However,it simultaneously produces a series of scientific challenges such as storage bottleneck,algorithmic scalability,and interpretability,which demand efficient machine learning algorithms.As a very important task in data mining,classification problem is also one of the important research contents in the field of machine learning.It is widely used in our real life,such as spam recognition,handwriting digital recognition,face recognition,speech recognition,recommendation system and so on.There have been scalable algorithms for classification,such as distributed SVM(Support Vector Machine),localized SVM and so on.Although these classification schemes can reduce the computational complexity of SVM,their performance is sensitive to the involved parameters,requiring delicate parameter-selection strategies,which usually results in huge computations in the training process.Furthermore,most of them lack theoretical verifications on the generalization ability.Therefore,developing scalable classification algorithms with theoretical verification not only has important scientific value,but also has important practical significance for the study of algorithms in the era of Big Data.This paper focuses on the study of scalable classification algorithms.Different from the maximum marginal principle of SVM,this paper presents a novel efficient classification algorithm named Fast Polynomial kernel Classification(FPC)to conquer the scalability of the algorithm and storage bottlenecks challenges.In addition,the corresponding distributed version is proposed to handle the classification tasks with larger scale data or those in the distributed data environment.The main contributions to this paper are as follows:(1)We propose a fast polynomial kernel algorithm for classification.We mainly use polynomial kernel to construct a feature map to project data into a feature space with "moderate dimensions" and adopt the Alternating Direction Method of Multipliers(ADMM)to quickly solve the corresponding classification models.(2)Theoretically,we establish the corresponding learning rate of the algorithm under the common noise hypothesis.(3)Effectiveness of the algorithm and the corresponding theory are verified by a series of simulations and real data applications.Numerical results demonstrate that the FPC significantly reduces the computational burden and storage memory of the existing learning schemes without sacrificing its generalization abilities much.Additionally,a series of experimental results show that the distributed version of the proposed algorithm can further effectively handle the classification tasks with larger data scale or those in a distributed environment.