Evolutionary Based Optimization of String Kernels for Support Vector Machine

Abstract

We introduce a novel approach that automatically develops a new optimized string kernel using evolutionary approaches. The new evolved kernel is used to enhance the prediction performance of Support Vector Machines (SVMs) especially in biological sequences, as it is one of the most promising classifiers in this field. The proposed approach is based on a hybrid model that combines the evolutionary algorithm with a kernel based SVM classifier. This model creates the optimized kernel from available string kernels and it optimizes the kernels and SVM parameters. Two evolutionary approaches are examined, the Genetic Programming (GP) and the Genetic Algorithm (GA). In GP each individual represents a tree that encodes the mathematical expression of the evolved kernel. The evolved kernel could be either a combination of weighted sum of existing string kernels, or could be a mathematical expression of kernels. Many experiments with varying parameters are made to evolve the best optimized string kernel, and to optimize the kernel and SVM parameters. However, GA is used to evolve a new string kernel, either by combining some kernels, or by making a weighted combination of all string kernels. Using two standard benchmark datasets, signal peptide and Major Ristocompatibility Complex(MHC), our evolutionary optimized kernel in combination with SVM outperforms the available string kernels and produces high 11