A Genetic Algorithm For Solving SVM Inverse Problem And Its Implementation On Computer-cluster

Minimum entropy is chosen as a heuristic strategy in decision tree (DT) learning algorithm such as ID3. The method can learn smaller trees with lower computational complexity, but its generalization ability is not better. It is well known that Support Vector Machine (SVM) aim to optimize generalization related to margin. To improve generalization of DT, we can put SVM's margin as a criterion into the heuristic search for a split. The maximal margin can be attained to solve the inverse problem of SVM, whose time complexity is higher. A genetic algorithm for solving our problem has been proposed, but its efficiency is also poor when problem size is increased. Our work concerns how to improve the efficiency of the genetic algorithm for solving the inverse problem of SVM.The simple genetic algorithm for solving the inverse problem of SVM is studied and a parallel version is proposed with the corresponding cluster. First, serial process to solve our problem is discussed and its time complexity and time-consuming scale of each operator are analyzed. Second, aecording to parallelizability of serial process, master-slave parallel processing strategy is proposed as follows: evaluation operator, which consumes 90% of the total time, is done simultaneously on slave nodes, and other operators, which consumes less time, are done on master node. Finally, the proposed algorithm is implemented and some experiments are presented. The testing results show that the proposed algorithm is efficient and reasonable.