arXiv:1405.4589v2 [cs.NE] 20 May 2014

A Parallel Way to Select the Parameters of SVM
Based on the Ant Optimization Algorithm
Chao Zhang

Hong-Cen Mei

Hao Yang

Software Engineering
Software College
SiChuan University,China
Email: zhch040200@gmail.com

Software Engineering
Software College
SiChuan University,China
Email: hongcenmei@yeah.net

Software Engineering
Software College
SiChuan University,China
Email: chongqingyanghao@yeah.net

Abstract—A large number of experimental data shows that
Support Vector Machine (SVM) algorithm has obvious a large
advantages in text classification, handwriting recognition, image
classification, bioinformatics, and some other fields. To some
degree, the optimization of SVM depends on its kernel function
and Slack variable, the determinant of which is its parameters δ
and c in the classification function. That is to say, to optimize the
SVM algorithm, the optimization of the two parameters play
a huge role. Ant Colony Optimization (ACO) is optimization
algorithm which simulate ants to find the optimal path. In the
available literature, we mix the ACO algorithm and Parallel
algorithm together to find a well parameters.
Keyword: SVM, Parameters, ACO, OpenCL, Parallel

I.

S UPPORT V ECTOR C LASSIFICATION

AND

PARAMETERS

SVM is based on the principle of structural risk minimization,using limited training samples to obtain the higher
generalization ability of decision function. Suppose a sample
set (xi , yi ) , where i = 1, 2...N means the number of training
samples, x∈R means the sample characteristics, y ∈ {+1, −1}
means the sample classification.
SVM Classification function:
y = ωx + b (ω means weight vector,b means setover)

to a certain extent.
Radial Basis Function kernel:
khx1 , x2 i = e−

kx1 −x2 k2
2σ2

Maximum margin classifier:
M AXγ2

s.tγ1i ≥ γ1 − εi , i = 1, 2, 3...n

Let: γ1 = 1,so
M AX

n
X
1
εi s.tγ1i ≥ γ1 − εi , i = 1, 2, 3...n
+C
kωk
i=1

The constraints is associated with objective function through
the Lagrange function:
L(ω, b, α) =

n
n
X
X
1
2
εi
αi (yi ((ωx + b) − 1) + C
kωk −
2
i=1
i=1

Let:
Θ(ω) = M AXL(ω, b, α)
When all the constraints is contented, the Θ(ω) = 12 k ω k2 is
the value that we first want to minimized.So objective function:
M IN Θ(ω) = M IN M AXL(ω, b, α)

Functional margin :

Dual function:

γ1 = y(x + b) = yf (x)
functional margin is the minimum margin from hyperplane
(ω, b) to T (xi , yi )

M IN Θ(ω) = M AXM IN L(ω, b, α)
To solve the problem, requiring:
n

X
∂L
αi xi yi
=0⇒ω=
∂ω
i=1

Geometrical margin:
γ2 =

|f (x)|
y(ωx + b)
=
kωk
kωk

When classifying a data point, the larger the margin is, the
more credible the classification is. So to improve the credibility
is to maximize the margin. The ω and b can be proportional
scaled through the functional margin, thus the value of y =
ωx + b can be any large. Such that it is not appropriate to
maximize a value. But in the geometrical margin, when scaling
the ω and b, the value of γ2 can’t be change. So it is appropriate
to maximize a value.
Slack variable:
εi > 0 Using to allow the data to deviate from the hyperplane

n

X
∂L
αi yi = 0
=0⇒
∂b
i=1
∂L
=0
∂εi

means C − αi − γi = 0, i = 1, 2...n

M AXM IN L(ω, b, α) =

= M AX

n
X
i=1

n
X
1
αi (yi ((ωx + b) − 1)
k ω k2 −
2
i=1

αi −

n
1 X
αi αj yi yj khx1 , xi
2 i,j=1

6)

The minimized duel problem:
M AX

n
X

αi −

i=1

n
X

1
αi αj yi yj khx1 , xi
2 i,j=1

s.t0 ≤ αi ≤ C, i = 1, 2, 3...n;

n
X

Make the training samples evenly divided into k
mutually exclusive subsets of S1 , S2 , ..., Sk ;
Calculate the cross-validation accuracy:
a) Initialize i=1;
b) Make the Si subset reserved for test sets, and
set the rest as the training set, training SVM;
c) Calculate the ith subsets Sample Classification Accuracy Acci ,set i = i + 1,When
i < k + 1, repeat the step b);
d) Calculate the mean of k Sample Classificaˆ :
tion Accuracy Acc
Right
Acc =
Error + Right
Pk
d = i=1 Acci
Acc
k
Right: Correctly classified (+1) number of samples
Error:Misclassification (-1) number of samples
Q̂ :the mean of Sample Classification Accuracy
Update the pheromone concentration τ (x, y) at each
ˆ . Clear P ath(ki );
points by Acc
Reset N = N + 1.When N ≤ Nmax , and the
entire colony has not converged to follow the same
path, then turn to step 3; N ≤ Nmax , and the entire
colony substantially converged to follow the same
path, then the algorithm ends. Take the last update
of the path and its mapping data to (c, δ),that is the
SVM parameters C, δ final optimization results.

7)

αi yi = 0

i=1

The final classification function:
y = ωx + b
n
X

αi yi khx1 , xi + b

i=1

II.

M ODIFIED A NT C OLONY O PTIMIZATION A LGORITHM

Different from traditional problem of TCP, in this algorithm,the coordinate is used to represented the node. In a twodimensional rectangular coordinate system, the significance of
X is defined as the significant digit of parameters C and δ,
Y is varied from 0 to 10.[1] The significant digit of C are
assumed to be the five, and the highest level of C is hundred’s
place. Similarly, assume that the significant digit of δ are also
assumed to be the five, and the highest level of δ is The Unit.
To realize the ant colony optimization, we follow the steps
below:
1)

2)
3)

Suppose there are m ants. Each ant k(k = 1∼m)has
a one-dimensional array P ath(k) which has n elements(n is the total significant digit of C and δ), its
used to store the vertical coordinates y of each point
which the ant k visited.
Set the loop time N=0 to Nmax . Initialize the each
points pheromone concentration τ (x, y) = τ0 (x =
0 ∼ n, y = 0 ∼ 9).Set x = 1.
Set y = 1 to n.Calculate the deflection probability Pk
of each ant move to the node vertical line Lx .Then
select the next point via roulette wheel and store the
points vertical coordinates y to P athk

8)
9)

In order to validate the algorithm,we do simulation experiment
on matlab R2010b and PC with windows7 64-bit operating system, 4 G memory, core i5 processor. We divide the
wine SV M data set into a sample set and a test set. Then
we will have 90 training datas and 88 test datas. We set
ACO parameter m=30, N=500, ρ=0.7, Q=100, α=1, β=1. In
order to calculate the classification accuracy, we introduced the
LIBSVM.[3].LIBSVM has gained wide popularity in machine
learning and many other areas.[2]

τ α (x, y)η β (x, y)
Pk (x, y) = P9
α
β
j=0 τ (x, y)η (x, y)

10

9

9

8

8

7

7

τ (x, y) = ρτ (x, y) + ∆τ (x, y)

6

6

∆τ (x, y) =

∆τ (x, y) =

4)
5)



y

5

m
X

∆τk (x, y)

k=1
Q
1−Acck

0

,if ant k visited the point(x,y)
,others

The Acck mean the ant k s accuracy of
cross-validation
Pk means the deflection probability point(x − 1, y)
to (x, y)
Q is a constant
W:the weight coefficient;
Set:the minimum acceptable accuracy;
Let :x = x + 1,if x ≤ n,turn to step 3;else turn to
step 5.
Record this motion path P athk calculate the mapping
data (c, δ).

5
4
4
3

3

2

2

1

1
0

0

2

4

6

8

10

0

0

2

4

6

8

10

c,sigma

(a) The best accuracy’s path

(b) All accuracy’s paths

The best accuracy is 95.4545% and the convergence accuracy
is 86.3636% (76/88).
The parameter c: 18.605, parameter σ: 0.6643
III.

PARALLEL O PTIMIZE THE PARAMETERS

The Open Computing Language, is an open specification
for heterogeneous computing released by the Khronos Group2
in 2008. It resembles the NVIDIA CUDA3 platform, but can

be considered as a superset of the latter, they basically differ
in the following points[4]:
•

OpenCL is an open specification that is managed by a
set of distinct representatives from industry, software
development, academia and so forth.

•

OpenCL is meant to be implemented by any compute
device vendor, whether they produce CPUs, GPUs,
hybrid processors, or other accelerators such as digital
signal processors (DSP) andfield-programmable gate
arrays (FPGA).

•

OpenCL is portable across architectures, meaning that
a parallel code written in OpenCL is guaranteed to
correctly run on every other supporte device.

In this ant colony optimization algorithm, we have m ants and
we loop it N max times. If we give m a large number, such
as ten thousand or one hundred thousand, our update of node
pheromone concentration will be more accurate and reliable,
but we will spend more time. As we all know, every cycle,
each ant’s access to nodes are unrelated with others,so we can
parallel the ant access process. In this article, we use openCL
to realize the parallel of ant[4].

OpenCL kernel for the ant-based solution construction
globalsize = numberants ;
visited[globalesize × numbernodes ] = {−1};
for ( i=0 to n-1) do
{
sumprob = 0;
for (j=0 to 9) do
{
selectionprob [globalid × numbernodes + j]
= choiceinf o [i × n + j];
Sumprob = sumprob +
selectionprob [globalid × numbernodes + j];
}
j=0;
p = selectionprob[globalid × numbernodes + j];
while p < random(0, sumprob ) do
{
j=j+1;
p = p + selectionprob[globalid × numbernodes + j];
}
visited[globalid × numbernodes + i] = j;
}

Training samples are divided into subset number subset on
average and each subset has sample number samples. One
subset(Si ) see as test set and the other subsets (S1∼i , Si∼k )
see as a training set(each subset has c samples), then according
to the current parameters (c, δ)training the SVM, calculating
error of K-flod cross validation.

OpenCL kernel for sample classification accuracy
groupsize = subset number;
localsize = sample number;
for (i=0 to groupsize − 1)
{
Right = Error = Q = 0;
f or(j = 0 to localsize − 1)
{
P
f (x) = sign( ni=1 αi yi khgroupid , localid i+b);
if f (x) = 1
Right + +;
esle
Error + +;
}
Right
Q = Q + Right+Error
;
}
Q = Q/groupsize ;
IV.

C ONCLUSION

Through the ant colony optimization algorithm, we can find
a satisfactory parameter of SVM, and the convergence accuracy can be guaranteed more than 85%. There are also many
other ways to optimize parameters, such as Genetic algorithm
(GA)[5], dynamic encoding algorithm [6] for handwritten digit
recognition, Particle swarm optimization(PSO)[7]. We also can
parallel Ant Colony Optimization,article [8] introduced a new
way which parallel Ant Colony Optimization on Graphics
Processing Units.Article [9] improving ant colony optimization
algorithm for data clustering.
ACKNOWLEDGMENT
R EFERENCES
[1]

[2]
[3]
[4]

[5]
[6]

[7]

[8]

[9]

P. F. LIU Chun-bo, WANG Xian-fang, “Paramters selection and stimulation of support vector machines based on ant colony optimization
algorithm,” J.Cent,South Univ, 2008.
C. chung Chang and C.-J. Lin, “Libsvm : a library for support vector
machines,” Linux Journal, 2001.
C.-C. Chang and C.-J. Lin, “LIBSVM: A library for support vector
machines,” vol. 2, pp. 1–27, 2011.
E. by Helio J.C. Barbosa, Ant Colony Optimization - Techniques and
Applications. InTech, Chapters published February 20, 2013 under CC
BY 3.0 license, ISBN 978-953-51-1001-9,203 pages.
J. L.-c. ZHENG Chun-hong, “Automatic parameters selection for SVM
based on GA[C],” NJ:IEEE Press,2004:1869-1872.
Y. Park, S.-W. Kim, and H.-S. Ahn, “Support vector machine parameter
tuning using dynamic encoding algorithm for handwritten digit recognition,” 2005.
X. Li, S. dong Yang, and J. xun Qi, “A new support vector machine
optimized by improved particle swarm optimization and its application,”
Journal of Central South University of Technology, vol. 13, pp. 568–572,
2006.
A. Delevacq, P. Delisle, and M. Gravel, “Parallel Ant Colony Optimization on Graphics Processing Units,” Journal of Parallel and Distributed
Computing, vol. 73, 2013.
R. Tiwari, M. Husain, S. Gupta, and A. Srivastava, “Improving ant colony
optimization algorithm for data clustering,” pp. 529–534, 2010.

