Research On Large Margin Classifier Based On Optimizing Margin Distribution

Classification is a core problem of machine learning belonging to supervised learning, which tries to train a classification model to predict unknown data categories. In classification problems, the model is generally a decision function with the feature value of the training data as input and output the prediction of the unknown data. Margin theory is the theoretical basis of many classification algorithms such as SVM and Adaboost, which obtain the decision function by maximizing the minimum margin. While recent theoretical results indicate that optimizing the margin mean and variance has better performance generalization than maximizing the minimum margin. It has been proved that Large Margin Distribution Machine(LDM) obtains a smaller error bound than the maximum margin model. There are two training methods for LDM, dual coordinate descent(CD) and averaged stochastic gradient descent(ASGD). The experimental results show that CD cannot be applied to large scale data because of its time complexity O(m3). ASGD can deal with large scale data but only for linear kernel. Nystr?m method is a low-rank matrix approximation algorithm based on sampling. In this paper, Nystr?m method is used to approximate the kernel matrix of CD. When dealing with large scale data, Nystr?m-CD has a slight decrease(2% to 3% in experiment) in accuracy compared to CD, but it’s training efficiency has a big advance for 7.8 to 16.5 times and can deal with the problems in which CD cannot give results within 24 hours.Multi-instance multi-label(MIML) is a framework for complex classification problems which have several objects in one instance and several labels to be classified. This paper designs a multi-label version of LDM model inspired by this MIML framework and proposes the Nystr?m method for large scale data. That is, CD for ML-LDM and CD for ML-LDMNystr?m. ML-LDM is easy for modeling and expansion. Experimental results show that, ML-LDM can achieve better classification accuracy, recall rate and F1 values, so does ML-LDMNystr?m.