Research On String Kernel Function SVM With Two Threshold Parameters

The Support Vector Machine(SVM) based on the Statistical Learning Theory is a new approach to machine learning.It is built on the principia of Structural Risk Minimization(SRM),and can avoid the problems of overfiting,dimension disaster and local minimum point,etc.Moreover,it still possesses good performance under the condition of small sample.The aim of the paper is to improve on the Sequential Minimal Optimization algorithm(SMO) and to classfy strings with a string kernel function.After analysing SMO in detail,this paper points out an important source of inefficiency in Platt's sequential minimal optimization(SMO) algorithm that is caused by the use of a single threshold value.Using clues from the KKT conditions for the dual problem,two threshold parameters are employed to derive modifications of SMO.These modified algorithms perform significantly faster than the original SMO.In addition,this article discusses information of structured data vector is lost in the process of transformation, and introduce the concept of kernel function based on structureed data.According to structural characteristics of the string,we construct a string kernel function,which accurately descripes the similarity between strings.We applied it to form Support Vector Machine based on the string kernel function(SSVM),which expands the application scope of SVM to structured data.Experiments show that SSVM performs well in string classification.At the end of this paper,a dual-threshold SSVM system is built up based on LIBSVM.