A PSO and Pattern Search based Memetic Algorithm for SVMs Parameters Optimization

Yukun Bao; Zhongyi Hu; Tao Xiong

Source-linked AI summary

A PSO and Pattern Search based Memetic Algorithm for SVMs Parameters Optimization

Yukun Bao, Zhongyi Hu, Tao Xiong

arXiv:1401.1926v1Jan 9, 2014cs.LGcs.AIcs.NEstat.ML

TL;DR

SVM performance depends on selecting suitable parameters, motivating an efficient optimization method. The paper combines PSO exploration, pattern-search exploitation, and probabilistic local-refinement selection, with experiments reporting effective and robust performance against established counterparts.

Problem
SVM performance depends on adequately setting parameters such as the penalty coefficient C and kernel parameters.
Method
The proposed memetic algorithm uses PSO to explore and detect promising regions, pattern search to exploit them, and probabilistic selection to choose individuals for local refinement.
Results
The proposed PSO–PS memetic algorithm yields higher and more robust performance than other counterparts and outperforms single PSO and GS in error rates and standard deviations.
Takeaways & Limitations
The proposed PSO–PS memetic algorithm is presented as a promising alternative for SVM parameter optimization.

Abstract

from arXiv · show

Addressing the issue of SVMs parameters optimization, this study proposes an efficient memetic algorithm based on Particle Swarm Optimization algorithm (PSO) and Pattern Search (PS). In the proposed memetic algorithm, PSO is responsible for exploration of the search space and the detection of the potential regions with optimum solutions, while pattern search (PS) is used to produce an effective exploitation on the potential regions obtained by PSO. Moreover, a novel probabilistic selection strategy is proposed to select the appropriate individuals among the current population to undergo local refinement, keeping a well balance between exploration and exploitation. Experimental results confirm that the local refinement with PS and our proposed selection strategy are effective, and finally demonstrate effectiveness and robustness of the proposed PSO-PS based MA for SVMs parameters optimization.

A PSO and Pattern Search based Memetic Algorithm

The paper proposes a memetic algorithm for optimizing SVM parameters, combining PSO and pattern search.

The study is titled “A PSO and Pattern Search based Memetic Algorithm for SVMs Parameters Optimization.”
Yukun Bao, Zhongyi Hu, and Tao Xiong authored the study.
The authors are affiliated with the Department of Management Science and Information Systems at Huazhong University of Science and Technology.
The paper concerns parameter optimization, support vector machines, memetic algorithms, particle swarm optimization, and pattern search.

1. Introduction

The introduction motivates SVM parameter optimization as a difficult search problem and proposes a PSO–pattern-search memetic algorithm with probabilistic local-refinement selection.

SVM generalization ability depends strongly on parameter settings, including the penalty coefficient C and kernel parameters.
Grid search is computationally expensive because its cost scales exponentially with parameter count and sampling density.
Grid-search performance is sensitive to the range and coarseness chosen for each parameter.
Numerical optimization methods require differentiable, continuous error bounds and may become trapped in local optima or depend heavily on starting points.
The proposed method combines PSO exploration with pattern-search exploitation to optimize SVM parameters.
A probabilistic selection strategy chooses promising individuals for local refinement to balance exploration and exploitation.
Experimental comparisons demonstrate the effectiveness of the proposed PSO–PS memetic algorithm for SVM parameter optimization.

2. Support Vector Machines

This section describes SVM classification with kernel functions, emphasizing the roles of penalty and kernel parameters and focusing on the RBF-kernel setting.

SVMs classify data by finding a separating hyperplane while minimizing regularized training error.
The penalty coefficient C controls the trade-off between empirical risk and the regularization term.
Kernel functions represent inner products in high-dimensional feature spaces without explicitly computing the feature map.
The paper lists linear, polynomial, radial basis function, and sigmoid kernels, whose parameters include γ, r, and d.
The study focuses on SVMs with an RBF kernel, whose penalty parameter C and kernel parameter γ require careful selection.
The proposed PSO–PS memetic algorithm addresses optimization of these two parameters for RBF-kernel SVMs.

3. Proposed Memetic Algorithms

The proposed memetic algorithm combines PSO-based exploration of the SVM parameter space with pattern-search exploitation, using probabilistic selection to balance both roles. Particles represent candidate parameter solutions evaluated by cross-validation error, while PSO and pattern search iteratively update and refine them.

Background: Memetic algorithms combine population-based exploration with individual local refinement to balance exploration and exploitation.The paper notes that this hybridization can improve performance and robustness but may be more complex and expensive to implement.
Proposed PSO-PS Memetic Algorithm: The proposed method uses PSO for global exploration and pattern search for local exploitation of promising SVM parameter regions.PSO explores the global parameter space, while pattern search provides local exploitation based on simplicity, flexibility, and robustness.
Representation and Initialization: Each particle represents a candidate SVM parameter solution, with two dimensions corresponding to C and γ.The population is initialized randomly within parameter and velocity bounds, and particles are updated iteratively using position and velocity.
Fitness Function: The fitness function is the mean k-fold cross-validation misclassification rate, used as a criterion for model generalization ability.The study conducts 5-fold cross-validation and minimizes the validation error.
PSO based Operator: PSO updates particle velocities and positions using inertia, personal-best, and global-best information.The process tracks individual and global best parameter combinations and terminates when the predetermined maximum iteration count is reached.
A Probabilistic Selection Strategy: A probabilistic strategy selects non-crowded individuals for local refinement to prevent simultaneous exploitation of the same region.The selection strategy directly controls the exploration–exploitation balance under a limited computational budget.

4. Experimental Results and Discussions

Experiments evaluate PSO-PS memetic-algorithm variants on benchmark SVM parameter optimization tasks, testing local refinement, selection strategies, and comparisons with PSO, grid search, and established methods.

Experimental design: The study uses two experiments: selecting the best MA variant, then comparing it with established methods.The first experiment evaluates selection strategies; the second compares the best variant with literature counterparts.
Experimental setup: Thirteen benchmark datasets contain randomized training and testing groups for binary classification, with approximately 60% training and 40% testing data.Each group was normalized to zero mean and unit standard deviation.
Algorithm variants: PSO explores the parameter space, while pattern search locally refines selected particles in the proposed memetic algorithm.The variants differ in which particles receive pattern-search refinement, including all new particles, probabilistic selection, or the two best particles.
Experiment I: Across datasets, every MA selection strategy achieves lower mean error rates than single PSO and is more stable by standard deviation.Pattern-search refinement increases fitness evaluations, but the average increase over PSO is at most 13%.
Experiment I: MA4 achieves the lowest error rate on every dataset and across all datasets while avoiding a large increase in fitness evaluations.The results attribute this performance to the proposed probabilistic selection strategy balancing exploration and exploitation.

5. Conclusions

The study proposes a PSO–pattern search memetic algorithm for SVM parameter optimization, combining global exploration, local refinement, and probabilistic selection. Experiments on benchmark datasets report stronger and more robust performance than established alternatives, while the approach remains focused on SVM optimization.

SVM performance depends on adequately setting parameters such as penalty coefficient C and kernel parameters.
The proposed memetic algorithm uses PSO to explore the search space and identify promising regions, while pattern search refines those regions.
A probabilistic selection strategy chooses individuals for local refinement to balance PSO exploration with pattern-search exploitation.
The proposed MA variants outperform single PSO and grid search in error rates and standard deviations, although they generally consume more time than PSO.
The proposed selection strategy gives the best error-rate and standard-deviation performance among the MA variants.
Compared with established algorithms, the proposed PSO-PS MA with probabilistic selection yields higher and more robust performance, but the study focuses only on SVM parameter optimization.