HeroSVM Support Vector Machine User Guide
Contents
1. SvmTrain_Parallel d data feature dat d data label dat d data pos_samples dat d data 3 3 SvmTrain_Sequential Name SvmTrain_Sequential Train support vector machines sequentially Header file SVMTrain h Synopsis int SvmTrain_Sequential char szDataFilePathName char szTargetFilePathName int nClassID char szSummaryFilePathName char szSvFilePathName char szSvIndexFilePathName Parameters szDataFilePathName a pointer to feature vector filename sz IargetFilePathName a pointer to target filename This file consists of target values of samples 1 0 or 1 0 nClassID Identity number of one class szoummaryFilePathName a pointer to summary filename szSvFilePathName a pointer to a filename This file stores support vectors and trained parameters szSvIndexFilePathName a pointer to index filename Return Value If succeed return 0 otherwise 1 3 4 SVMCLEAN Remarks Feature vector and target files are both read written in binary mode See Also Example 3 4 SvmClean Name SvmClean Free dynamically allocated memory in terms of training type Header file SVMTrain h Synopsis void SvmClean int TrainingType Parameters TrainingType 0 Parallel optimization 1 Sequential optimization Return Value NONE Remarks See Also Svmlnit Example SvmClean 0 11 12 CHAPTER 3 FUNCTION REFERENCE Chapter 4 Appendix The chapter2. Press Oxford 1995 6 Jian xiong Dong Krzyzak A and Suen C Y A fast SVM Training Algorithm Proceedings of International workshop on Pattern Recognition with Support Vector Machines S W Lee and A Verri Eds Springer Lecture Notes in Computer Science LNCS 2388 pp 53 67 Niagara Falls Canada August 10 2002 7 Jian xiong Dong Krzyzak A and Suen C Y Fast SVM Training Algorithm with Decomposi tion on Very Large Datasets IEEE Transactions on Pattern Analysis and Machine Intelligence vol 27 no 4 pp 603 618 April 2005 8 C J C Burges A tutorial on support vector machines for pattern recognition in Data Mining and Knowledge Discovery pp 121 167 1998 9 J Mercer Functions of positive and negative type and their connection with the theory of integral equations Philos Trans Roy Soc London vol A 209 pp 415 446 1909 10 C J C Burges and D J Crisp Uniqueness of the SVM solution in Advances in Neural Infor mation Processing Systems to appear in NIPS 12 11 S S Keerthi S K Shevade C Bhattachayya and K R K Murth Improvements to Platt s SMO Algorithm for SVM classifier design Neural Computation vol 13 pp 637 649 March 2001 12 Lin Chih Jen Formulations of support vector machines A note from an optimization point of view Neural Computation vol 13 pp 307 317 2001 19
3. feature vectors of all training samples which are shared by all classes The other stores corresponding labels of training samples A sample is labeled by an integer in an interval from 0 to m 1 where m is the number of classes After parallel optimization training sets for each class are collected Two files for each class will be generated One is called feature vector file The other is called target file which sequentially stores target values 1 0 or 1 0 The training method is one against the rest Note that feature vectors are stored in binary format and each component is represented as a 4 byte float data type For example feature vector file Input feature vector of sample 1 Input feature vector of sample 2 Input feature vector of sample n label file Label of sample 1 Label of sample 2 Label of sample n This integer is called class label of a sample 2 3 BASIC DATA STRUCTURES 5 2 3 4 Summary information After training for each class ends the summary information will be stored in a file We describe its format with an example as follows class Label 0 User specified kernel is used The size of working set is 2000 The size of the training set is 7291 b low 0 528602 b up 0 507482 cache hit 6219030 total kernel evaluations Actual kernel evaluations cache hit ratio 0 696504 C 10 0000 Bias 0 518042 Iterations 91 Training time CPU seconds 13 390000 Max alpha 4 608595
4. important to develop a fast training algorithm for SVM in order to apply it to various engineering problems in other fields HeroSVM package has been implemented based on our proposed method 6 7 In order to simplify the description of implementation we give simple introduction of support vector machine The details are referred to Burge s tutorial 8 Given that training samples x y i 1 N vi 1 1 x R where y is the class label support vector machine first maps the data to the other Hilbert space H also called feature space using a mapping 1 1 The mapping is implemented by a kernel function K that satisfies Mercer s conditions 9 such that k x x P x P x Then in the high dimensional feature space H we find an optimal hyperplane by maximizing the margin and bounding the number of training errors The decision function can be given by f z 0 w D x b 202 yia xi B x b 1 2 1 2 CHAPTER 1 INTRODUCTION 103 Yiaik zi x b where 1 df DE 1 otherwise 13 If a is nonzero the corresponding data x is called support vector Training a SVM is to find 05 7 1 N which can be achieved by minimizing the following quadratic cost function maximize Lp a SE Qi i Xe ojo 5y y k mi T3 subject to Em sC 1 1 N 1 4 0 where C is a parameter chosen by the user a larger C corresponds to a higher penalty allocated
5. HeroSVM Support Vector Machine User Guide version 2 1 August 2005 Jianxiong Dong Ph D Centre for Pattern Recognition and Machine Intelligence Concordia University Montreal Quebec Canada Copyright Information Manual Copyright c 2005 Jianxiong Dong Software Copyright c 2005 Jianxiong Dong Visual C is microsoft registered trademark Visual C is a software development platform This software can be used for research over the world and is free of charge Anybody who likes to use it for a commercial purpose should obtain the permission of the author Arrangements can probably be worked out Note that distributing this software bundled in with any product is considered to be a commercial purpose THE SOFTWARE IS PROVIDED AS IS AND WITHOUT WARRANTY OF ANY KIND EXPRESS IMPLIED OR OTHERWISE INCLUDING WITHOUT LIMITATION ANY WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL INCIDENTAL INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OR USE DATA OR PROFITS WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAM AGE AND ON ANY THEORY OF LIABILITY ARISING OUT OF OR IN CON NECTION WITH THE USE OR PERFORMANCE THIS SOFTWARE Contents 1 Introduction 1 1 1 What is Support Vector Machine 1 1 2 Support Vector Machine saa sea taie etae eri 1 2 How to use HeroSVM 3 2 1 Design philosophy of Hero
6. Number of support vectors 330 Number of bounded support vector 0 IW 2 159 62 margin of separation 0 158301 8928917 2709887 In the above example Bias means b in Eq 1 2 The cache hit ratio can be calculated by he_hit cache hit ration MM nn 2 4 total kernel evaluations blow and b_up are two thresholds in modified SMO 11 and margin is equal to 1 w P If alpha value of one support vector is equal to C we call it bounded support vector 2 3 5 Save training results We save training results into two files One is used to store kernel paramters support vectors and the corresponding a The other index file is to store the sequential number of support vectors on the training set in order to merge them during the testing stage and reduce unnecessary kernel re evaluations Users can read training results with C language as follows fp fopen file name rb fread amp C sizeof float 1 fp for user specified kernel skip the following three statements fread amp kernel paral sizeof float 1 fp 6 CHAPTER 2 HOW TO USE HEROSVM fread amp kernel para2 sizeof float 1 fp fread amp kernel para3 sizeof float 1 fp fread amp threshold sizeof float 1 fp fread amp sv sizeof int 1 fp for i 0 lt sv i vec dim read the support vector fread vec sizeof float dim fp read the target value of the above support vector fread amp target i sizeo
7. SVM 3 22 rab ompotents s s e m o aS tu 3 23 Basie data struct res a o xao geh ri BU ds exer ex ara 3 MESE TS A XT 3 2 3 2 The size of 4 2 3 3 Training data format 4 2 3 4 Summary information 5 20 0 training 5 nar A io da OUO fa Gre 5 24 Wired IS 2 acd fee nf Ia e d aer b e i hoe A ee do Ne awe th Ana dd 6 3 Function Reference 7 S jn ge oat he ht AG Be Bl BOS Bl a a e o ene 7 8 2 Vid sib v 4 aber Ste UU TS he 9 3 3 POV ram Sequential 0 52 scuta cR td So ew Soda SE d d 10 Khon dm tac Soak eR XE E d 11 4 Appendix 13 CONTENTS Chapter 1 Introduction 1 1 What is Support Vector Machine 1 2 Support Vector Machine Support vector machines SVM have recently generated a great interest in the community of machine learning due to its excellent generalization performance in wide variety of learning problems such as handwritten digit recognition see 1 2 classification of web pages 3 and face detection 4 Some classical problems such as multi local minima curse of dimensionality and overfitting in neural networks 5 seldom occur in support vector machines However training support vector machines is still bottleneck especially for a large scale learning problem 2 Therefore it is
8. alDptimization char 1 200 char fname2 200 char buf 200 char fname3 200 char fname4 200 int classNum nClass int 1 int nRes char fname 256 int SvOfClass nClass FILE fp strcpy fname FilePath strcat fname SvNum dat fp fopen fname rb fread SvOfClass sizeof int nClass fclose fp int Size fWorkingSet for i 0 i lt nClass i d n i SvOfClass i printf n Class Size 0fWorkingSet nRes float 1 0 15 fp SvmInit DIM SizeDfWorkingSet SvOfClasslil float 0 0 float 0 3 1 nClass 10 0 1 0 if nRes 1 printf n Intialization fails return 1 itoa i fnamei 10 strcpy buf FilePath strcpy fname4 buf strcat fname4 fnamel strcat fname4 dat strcat fnamel tgt strcat buf fnamel itoa i fname2 10 strcpy fname3 fname2 strcat fname3 index strcat fname2 res dat 16 CHAPTER 4 APPENDIX strcpy fname FilePath strcat fname info2 txt nRes SvmTrain Sequential fname4 buf i fname fname2 fname3 if nRes 1 printf n SVM training fails SvmClean 1 return 1 SvmClean 1 return 0 int main 1 printf n printf n printf n printf n printf n printf Nn printf Yn printf n Please activate the specified step Collect positive samples Parallel optimization Merge index Generate train
9. contains contact information and an example that shows how to use HeroSvm Jianxiong Dong Ph D Centre of Pattern Recognition and Machine Intelligence 1455 de Maisonneuve Blvd West Suite EV003 403 Montreal Quebec H3G 1M8 Canada E mail jdongca2003 gmail com homepage http www cenparmi concordia ca jdong include include include include include lt stdio h gt lt stdlib h gt lt string h gt global h SVMTrain h extern void GeneratePositiveSamples extern void MergeOrderIndex extern void GenerateMergeSet extern void GenerateFinalSvIndex extern void CreateSvmTrainingDictionary extern void LoadSv extern void SvmTest Step 1 int TestParallelOptimization int nRes 13 14 CHAPTER 4 APPENDIX nRes SvmInit DIM 8000 TotalSamplesNumber 11632 1 0 float 0 0 float 0 3 1 nClass 10 0 0 0 if nRes printf n Intialization fails return 1 char dataFileName 256 char labelFileName 256 char posSampleFileName 256 strcpy dataFileName FilePath strcat dataFileName feature dat strcpy labelFileName FilePath strcat labelFileName label dat strcpy posSampleFileName FilePath strcat posSampleFileName pos samples dat nRes SvmTrain Parallel dataFileName labelFileName posSampleFileName FilePath if nRes 1 printf n Training fails return 1 SvmClean 0 return 0 step 2 int TestSequenti
10. f float 1 fp fread amp alphalil sizeof float 1 fp The format of the index file is illustrated by seguential number of support vector 1 seguential number of support vector 2 seguential number of support vector n 2 4 Thread issues Although a single thread is considered parallel optimization of the proposed algorithm is suitable for multi thread programming in multi processor platform In the next version multi thread programming will be supported to speed up the training on multi processor s platform Chapter 3 Function Reference This chapter describes the interface function reference These functions are sorted by name For each routine we refer to format of xlib reference manual including declarations of the arguments return type and description 3 1 Svmlnit Name Svmlnit Set SVM training parameters and allocate the memory Header file SVMTrain h Synopsis int SvmInit int nDim int nWorkingSetSize int nTrainingSetSize float kernel Paral float kernel Para2 float kernel Para3 unsigned short int nKernelType int ClassNum float C int TrainingType int nApplicationType Parameters CHAPTER 3 FUNCTION REFERENCE nDim The parameter specifies the dimension of input feature vector n WorkingSetSize Size of working set nTrainingSetSize Number of training samples kernel_Paral Kernel parameter kernel_Para2 Kernel parameter kernel_Para3 Kernel parameter nKernelTy
11. ing sets for sequential optimization Sequential optimization Create recognition dictionary for sm Testing n NX FP ON Hr int step scanf d amp step switch step case 1 GeneratePositiveSamples break case 2 TestParallelOptimization break case 3 MergeOrderIndex break case 4 GenerateMergeSet break case 5 TestSequential0ptimization break case 6 GenerateFinalSvIndex CreateSvmTrainingDictionary break case 7 LoadSv SvmTest break return 0 17 18 CHAPTER 4 APPENDIX Bibliography 1 B Scholkopf C J C Burges and V Vapnik Extracting support data for a given task in Proceedings First International Conference on Knowledge Discovery and Data Mining Fayyad and R Uthurusamy Eds pp 252 257 Press Menlo Park CA 1995 2 D DeCoste and B Scholkopf Training invariant support vector machines Machine Learning vol 46 no 1 3 pp 161 190 2002 3 T Joachims Text categorization with support vector machine in Proceedings of European Conference on Machine Learning ECML 1998 4 E Osuna Freund and F Girosi Training support vector machines An application to face detection in Proceedings of the 1997 conference on Computer Vision and Pattern Recogni tion CVPR 97 Puerto Rico June 17 19 1997 5 C M Bishop Neural Networks for Pattern Recognition Clarendon
12. ion can be used to remove most non support vectors quickly so that the computational cost for sequential optimization can be dramatically reduced Sequential optimization is a working set algorithm where several strategies such as kernel caching shrinking are effectively integrated into it to speed up training 2 3 Basic data structures 2 3 1 Kernel In HeroSVM some classical kernels such as radial basis function RBF polynomial and linear kernels have been implemented Users can choose the above kernels or use their own customized kernel Let a b c are kernel parameters Then three classical kernels can 3 4 CHAPTER 2 HOW TO USE HEROSVM be written as by 2 RBF exp Ball 2 1 Polynomial lt 21 22 gt b c Linear lt 211 12 gt b c 2 3 where 1 R and z2 R a is a positive integer lt gt and denote dot product and Euclidean norm respectively 2 3 2 The size of working set Usually the total training set is much larger than the number of final support vectors The size of the working set should be large enough to contain these support vectors Before the training the number of support vectors is unknown Therefore users can estimate it in terms of the number of training samples Experiments 6 have shown that generalization performance is insensitive to this paper if it is large enough 2 3 8 Training data format Parallel optimization needs two files One sequentially stores the
13. pe Kernel type There are four categories as follows 1 RBF kernel 2 Polynomial kernel 3 Linear kernel ClassNum Number of classes C Upper bound of alpha in eq 1 4 Training Type Specify the optimization step 0 Parallel optimization 1 Sequential optimization nApplicationType Application type for the output of error message 0 Console application 1 Window application Return Value If succeed return 0 otherwise 1 Remarks See Also 3 2 SVMTRAIN_PARALLEL 9 SvmClean Example create a SVM with RBF kernel for parallel optimization 1 1 576 8000 60000 1 0 0 0 0 3 1 10 10 05 O 0 3 2 SvmTrain_Parallel SvmTrain Parallel Train support vector machines with multi classes to remove non support vectors quickly Header file SVMTrain h Synopsis int SvmTrain Parallel char szDataFilePathName char szLabelFilePathName char PositiveSamplesFilePathName char SaveFilePath Parameters szDataFilePathName a pointer to feature vector filename szLabelFilePathName a pointer to labelling filename This file consists of identity numbers of samples PositiveSamplesFilePathName a pointer to positive sample file name This file contains one sample of each class SaveFilePath Saved file path Return Value If succeed return 0 otherwise 1 Remarks Feature vector and label files are both read written in binary mode See Also 10 CHAPTER 3 FUNCTION REFERENCE Example
14. to the training errors Since kernel K is semi positive definite and constraints define a convex set the above optimization reduces to a convex quadratic programming The weight W is uniquely determined but with respect to the threshold b there exist several solutions in the special cases see 10 11 12 Further an interesting fact is that the solution is not changed if any non support vector is removed from Eq 1 4 In the next chapter we describe basic data structures and show users how to use the package The function reference is given in the chapter 3 Chapter 2 How to use HeroS VM 2 1 Design philosophy of HeroSVM HeroSVM was implemented based on our proposed methods 6 7 In order to facilitate the software portability and maintainess an object oriented method has been applied to design the package Error handling was implemented for the robustness of software HeroSVM is written using C language and developed under Microsoft visual C 6 0 In the current version a dynamical link library in Windows or a shared library in Linux is provided to train SVM on a large scale learning problem efficiently for research purpose in PC platform We expect that HeroSVM can facilitate the training of support vector machine and solve some real world problems in various engineering fields 2 2 Components The proposed SVM training algorithm consists of two components parallel optimization and sequential optimization Parallel optimizat
Download Pdf Manuals
Related Search