使用混合最佳化技術化簡支撑向量機之解

A Hybrid Optimization Strategy for Simplifying the Solutions of Support Vector Machines

葉日斌(Jih-Pin Yeh)

指導教授 ： 林慧珍

淡江大學/工學院/資訊工程學系博士班/博士(2009年)

https://doi.org/10.6846/TKU.2009.00149

摘要

本論文研究使用最佳化技術(粒子尋優演算法及遺傳演算法) 簡化支撐向量機(SVM)之解。計畫的主要之議題為“找出SVM的解集合的最佳部分解”，並使得此SVM的解集合的最佳部分解形成之判斷函數(discriminant function)能最逼近原來未簡化解時的判斷函數。而SVM的解集合的最佳部分解是選自原來之SVM的解集合，並以一適應函數(fitness)為指標來選出，而且此一適應函數能評量所形成之判斷函數的好壞。而使用之最佳化技術(粒子尋優法及遺傳演算法)也是利用所定的適應函數(fitness)來搜尋找出SVM的解集合的最佳部分解。結果顯示所定出之適應函數的好壤及使用那一種搜尋技術會影響所得的SVM的近似判斷函數的性能。本論文所提之方法可應用於任一種SVM的核函數所形成之判斷函數。另外識別率可依工作需要做適應性的調整。而所提之方法也會在標準的資料庫上實驗。而實驗結果指出混合最佳化技術的策略的確能有效地找出SVM的解集合的最佳部分解。並得到搜尋演算法在找此SVM的解集合的最佳部分解的性能比較好壞依次為PSO-GA，GA-PSO，PSO，及GA。

關鍵字

支撐向量機 ； 粒子尋優演算法 ； 遺傳演算法 ； 最佳化 ； 判斷函數

並列摘要

This thesis investigates and compares the performance of reduction of solutions for SVMs using two optimization techniques, namely particle swarm optimization (PSO) and genetic algorithm (GA). The main issue is to search for a subset of the support vector solutions produced by an SVM that forms a discriminant function best approximating the original one. The work is accomplished by giving a fitness that fairly indicates how well the discriminant function formed by a set of selected vectors approximates the original one, and searching for the set of vectors having the best fitness using PSO, GA, or a hybrid approach combining PSO and GA. Both the defined fitness function and the adopted search technique affect the performance. Our method can be applied to SVMs associated with any general kernel. The reduction rate can be adaptively adjusted based on the requirement of the task. The proposed approach is tested on some benchmark datasets. From the test results, it can be observed that the combination of the particle swarm optimization algorithm and genetic algorithm can improve search results; that is, both PSO-GA and GA-PSO outperform both PSO and GA.

並列關鍵字

support vector machine ； particle swarm optimization ； genetic algorithm ； optimization ； discriminant function.

參考文獻

[1] P. Angeline, “Evolutionary Optimization Versus Particle Swarm Optimization: Philosophy and Performance Difference,” in Proceedings of the Seventh Annual Conference on Evolutionary Programming, pp. 601-610, 1998.

[6] C. Cortes and V. Vapnik, “Support Vector Networks,” Machine Learning, Vol. 20, pp. 273-297, 1995.

[7] B. Chakraborty and P. Chaudhuri, “ On the Use of Genetic Algorithm with Elitism in Robust and Nonparametric Multivariate Analysis,” Austrian Journal of Statistics, Vol. 32, pp. 13-27, 2003.

[8] M. Clerc, “The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization,” in Proceedings of the Congress on Evolutionary Computation, Washington DC, USA, 3, pp. 1951-1957, 1999.

[11] S. Esquivel and C. Coello, “On the Use of Particle Swarm Optimization with Multimodal Functions,” in Proceedings of IEEE Congress on Evolutionary Computation, pp. 1130-1136, 2003.