Journal of Signal and Information Processing, 2011, 2, 170-174
doi:10.4236/jsip.2011.23022 Published Online August 2011 (http://www.SciRP.org/journal/jsip)
Copyright © 2011 SciRes. JSIP
A Genetic Programming-PCA Hybrid Face
Recognition Algorithm
Behzad Bozorgtabar, Gholam Ali Rezai Rad
School of Electrical Engineering, Iran University of Science and Technology, Tehran, Iran.
Email: b_bozorgtabar@elec.iust.ac.ir, Rezai@iust.ac.ir
Received June 11th, 2011; revised July 24th, 2011; accepted August 5th, 2011.
ABSTRACT
Increasing demand for a fast and reliable face recognition technology has obliged researchers to try and examine dif-
ferent pattern recognition schemes. But until now, Genetic Programming (GP), acclaimed pattern recognition, data
mining and relation discovery methodology, has been neglected in face recogn ition literature. This paper tries to apply
GP to face recognition. First Principal Component Analysis (PCA) is used to extract features, and then GP is used to
classify image groups. To further impro ve the results, a leveraging method is also u tilized. It is sho wn that althou gh GP
might not be efficient in its isolated form, a leveraged GP can offer results comparable to other Face recognition solu-
tions.
Keywords: Face Recognition, Principal Component Analysis, Genetic Programming, Leveraging Algorithm
1. Introduction
Face recognition has become one of the most active re-
search areas of pattern recognition since the early 1990s.
In the past 20 years, significant advances have been
made in design of successful classifier for face recogni-
tion [1]. However the diversity of the face patterns makes
it difficult to create robust recognition systems and the
complexity of the algorithms makes them hard to imple-
ment.
Principal components analysis (PCA) method [2],
which is the base of well-known face recognition algo-
rithm, Eigenfaces [3,4], is an appearance-based technique
used widely for the feature extraction and has recorded a
great performance in face recognition. PCA based ap-
proaches typically include two phases: training and clas-
sification. In the training phase, an eigenspace is estab-
lished from the training samples using PCA and the
training face images are mapped to the eigenspace for
classification. In the classification phase, an input face is
projected to the same eigenspace and classified by an
appropriate classifier, such as Support Vector Machines
(SVMs) or Neural Networks [5].
Genetic programming is an evolutionary algorithm
methodology inspired by biological evolution [6]. Evolu-
tionary algorithms create a population of abstract repre-
sentations of candidate solutions, which is evolved using
biology inspired operators such as selection, cross-over
and mutation towards better solutions.
In recent years, Genetic Programming and other evo-
lutionary algorithms has been used in classification and
pattern recognition problems [7,8], although to the au-
thors’ knowledge, Genetic Programming has never been
used in Face Recognition Domain.
In many applications, Genetic programming yields
simplified symbolical representation of the underlying
system it tries to model. This leads to efficient checking
of a new sample [9]. On the other hand the complexity
and the time needed to find such representation discour-
ages its use in many applications.
Leveraging algorithms are a group of deterministic
algorithms where a set of weak learners are used to cre-
ate a strong learner [10]. While it is not algorithmically
constrained, most leveraging algorithms iteratively em-
ploy weak learners based on a distribution and combine
them with weighting to form a final strong learner.
In this paper, Genetic Programming is utilized to clas-
sify face images. As images are usually large, PCA is
used to extract image features and thus reduce data di-
mension. The Genetic Programming is then applied to
the extracted features. Using a training group, Genetic
Programming discovers possible relationship between the
extracted features, which is in turn used to classify new
images. To improve results, a leveraging scheme is in-
troduced, which employs Genetic Programming as a
weak learner, and combine results of several Genetic
A Genetic Programming-PCA Hybrid Face Recognition Algorithm171
Programming classifications as a single strong classifier.
The rest of paper is organized as follows: in Sections 2
and 3, PCA and Genetic Programming are introduced
respectively. Section 4 presents the introduced algorithm,
where Genetic Programming is used with and without
leveraging. In Section 5, simulations are done on a se-
lected face database and results are compared to previous
studies.
2. Feature Extraction
Principal Compone nt Analysis
Let there be R face images in the training set, where each
image Xi is a 2-dimensional array of size m × n of inten-
sity values. The image Xi can be converted into a vector
of D (where D = m × n) pixels. The rows of pixels of the
image are placed one after another to form the vector.
If the training set of R images is defined by
12
,,
R
X
XX X, then the covariance matrix is de-
fined as:

1
1RT
ii
I
T
X
XX X
R
 

(1)
where

12
,,
D
R
R
 R and
1
1R
i
i
X
x
R
(2)
is the mean image of the training set. Also the dimen-
sion of the covariance matrix is D × D.
The eigenvalues and eigenvectors are then calculated
from the covariance matrix.
Let

12
,,
D
R
r
QQQ Q
R (generally, r < R) be
the r normalized eigenvectors corresponding to r largest
eigenvalues. Each of the r eigenvectors is called an Ei-
genface. Now, each of the face images of the training set
X is projected into the Eigenface space to obtain its cor-
responding Eigenface based feature
D
R
i
Z
R, which
is defined as:
,1.2,,
ii
QTY iR (3)
where is the mean-subtracted image of
i
Yi
X
[11].
3. Genetic Programming
Genetic programming is a methodology inspired by bio-
logical evolution to find equations, computer programs,
analog circuits or in general any suitable structure for a
predefined problem [9]. Genetic programming’s general
mechanisms are almost identical to genetic algorithms, as
genetic programming is considered either a specialized
form of genetic algorithms or an expansion of it [6]. Ge-
netic programming is usually implemented similar to the
following algorithm:
1) Create initial population. Individual solutions (call-
ed chromosomes) are usually generated randomly.
2) Evaluate the fitness of each individual in the popu-
lation.
3) Select best-ranking individuals to reproduce.
4) Breed new generation through crossover and/or
mutation (genetic operations) and give birth to offspring.
5) Repeat from step 2 until a termination condition is
reached (time limit or sufficient fitness achieved).
Figure 1 illustrates the general Genetic programming
algorithm.
In GP individual population members (chromosomes)
are not fixed length linear character strings that encode
possible solution to the problem like in GA, but they are
programs that, when executed, provide solution to the
problem.
These programs are expressed in GP as parse trees of
varying sizes and shapes, what makes these methods
flexible in their application to the wide range of prob-
lems.
The difference in chromosomes representation is the
main and almost the only difference between this method
and GA. The overall Darwinian idea of survival stays the
same, but there are changes in mutation and crossover
operators and in fitness function calculation.
Each node of tree can be function, operator, variable or
constant number. Trees can be evaluated in a recursive
manner, in which each node’s operator or function is
executed up on the results of its children’s evaluation.
Tree structure can easily represent a mathematical equa-
tion or a Turing complete program.
Create
Initial
Population
Apply
Selection
Evaluate Fitness of
Each Individual
Crossover /Mutati on
NO
END
Termination
Criteria Reac hed?
YES
Figure 1. Genetic programming’s flowchart.
Copyright © 2011 SciRes. JSIP
A Genetic Programming-PCA Hybrid Face Recognition Algorithm
Copyright © 2011 SciRes. JSIP
172
4. Classification Algorithm where fj,m is result of nth iteration on the jth group, n is
the iteration number from total N repetitions, and errj,k is
sum of total errors for all images in the training group.
4.1. Using Genetic Programming
To determine a new image’s class, all values acquired
from (6) are compared. The class which yields the great-
est C is nominated as the new candidate class. It should
be noted that a threshold could be defined, as if the re-
sults of all classifiers for an image yield lower than a
certain value, the image is certainly misclassified.
To classify a given dataset, it is usually enough to find a
way for differentiating classes. Using genetic program-
ming, this translates to finding a function which outputs a
unique value for each different class:

0
1
0
1
n
X
C
X
C
fX
nXC
(4) 5. Simulation and Results
The algorithms were implemented in Python and then
were tested on the AT&T face image database [12]. The
AT&T database consists of 40 groups, each containing
ten 112 × 92 gray scale images of a single subject. Each
subject’s images differ in lighting, facial expression and
details (smiling/frowning, glasses/no glasses, etc.).
This is proven to be difficult. As a result, genetic pro-
gramming is used to find a function per class that can
discriminate only a certain class from others:

1
01
i
ii
X
C
fX
X
C
(5) Two set of images were created from the AT&T data-
base; For the Five-to-Five dataset, five random images of
each group were selected for training while the others
were used for testing. For the Leave-One-Out set, 9 im-
ages were used for training and the remaining image was
kept for validation.
This method creates N different functions for a total of
N classes. Test images are tested one by one against the
functions, and the first function to return a non-zero val-
ue is used to determine the image’s class. First Genetic Programming was tested without lever-
aging. To evolve the population, an Evolutionary Strat-
egy (ES) of 1 + λ with λ = 4 was chosen. Mutation rate
was set to 15 percent.
4.2. Leveraging Algorithm
Leveraging is a method of using multiple results to im-
prove detection. A leveraging algorithm employs multi-
ple weak classifiers to create a strong classifier. The fol-
lowing leveraging algorithm is used in this paper: Instead
of using all training images as input, the whole group is
partitioned to k different groups. Figure 2 shows sample
face images which are partitioned to three various clusters.
The selected function set was {+,, ×, <, >, MIN,
MAX, AND, OR, NOT, CNST} where Boolean operators
first compare their operands with 0 and CNST returns a
random constant floating point number in range of [–10,
10]. Inputs were chosen from all available PCA results.
To limit algorithm time and prevent bloat, each chromo-
some’s depth was limited to 25 and a maximum of 20000
iterations for each evolution was maintained.
Detector function fi,j is then obtained as a function
which can detect class i from other classes in group j. To
further improve the results of classification, algorithm
above could be repeated N times. For a given image X,
the following equation creates the results of classifica-
tion:
To test the leveraged algorithm, algorithm was exe-
cuted with the same parameters. Also the number of it-
erations was set to N = 8, while the set was divided to k =
8 different groups.

,
,
,
1
1
1
jn
jn
j
n
Cfp err
N

(6) Table 1 shows a few of discovered relationship func-
tions for a set of pictures. It could be seen that the gener-
ated formulas are often simple while only depending on a
partitioning


f
p
1
f
p
2
f
p
3
f
p
Figure 2. Partitioning sample AT&T face database.
A Genetic Programming-PCA Hybrid Face Recognition Algorithm173
Table 1. Examples of Acquired Relationship Functions for
Detecting Image Group 1. PCA[n] Is the Nth Value on PCA
Vector.
No Function
1 (PCA[8]- MAX(PCA[19], PCA[7]))> PCA[12]
2 AND((PCA[2]< PCA[13]), MIN(PCA[1], 1))
3 (PCA[0]× NOT(PCA[5]))
4 (PCA[1]× (PCA[21]> (PCA[2]-PCA[18])))
few components and as a result have a relatively low
computational overhead.
Results are brought in Table 2, where they are com-
pared to EigenFace [3] and SVM [13] clustering methods.
It is observed that Genetic Programming without lever-
aging has the worst results. On the other hand, Leveraged
Genetic programming beats other methods in Five-to-
Five. In leave-one-out the results are repeated for Genetic
Programming, although this time Leveraged Genetic
Programming fell %2.5 (one image in total of 40 images)
short of SVM.
While it could be inferred that the Genetic Program-
ming is usable as a feature detector, it is believed that
PCA is limited in reducing data dimension [14]. Further
research is required to investigate Genetic Program-
ming’s results with 2D PCA and Multilinear PCA.
To further investigate Genetic Programming’s per-
formance, number of partitioned class groups was
changed and the results were brought in Table 3. It was
observed that the further partitioning of the images in-
creases recognition error, while decreasing k might man-
dates increase in time spent for Genetic Programming’s
evolution.
6. Conclusions
Genetic programming is a general purpose search algo-
rithm that can be utilized in classification problems. In
this paper, Genetic programming was exploited to clas-
sify face images. The results showed that Genetic Pro-
gramming alone is not suitable, as required time and
computational overhead surpasses that of other methods,
and also its recognition ratio is usually lower.
Table 2. Comparision of Different Algorithms Recognition
Rate.
Method Five-to-Five Leave One Out
Eigenface 87.0% 85.0%
SVM 91.0% 95.0%
GP 63.5% 67.5%
Leveraged GP 91.5% 92.5%
Table 3. Effect of Number of Partitions in Leveraged Ge-
netic Programming on Recognition Rate.
Number of Partitions Recognition Rate
2 88.5%
4 91.5%
5 91.5%
8 91.0%
10 89.0%
To improve results, a leveraging algorithm was ap-
plied to Genetic Programming. The leveraged Genetic
Programming showed a good recognition rate, compara-
ble to or in some cases even better than that of other me-
thods.
REFERENCES
[1] S. Liu, Y. Tian and D. Li, “New research Advances of
Facial Expression Recognition,” International Conference
on Machine Learning and Cybernetics, Baoding, Vol. 2,
July 2009, pp. 1150-1155.
[2] I. T. Jolliffe, “Principal Component Analysis,” Springer-
Verlag New York, Inc., 2002.
[3] M. Turk and A. Pentland, “Eigenfaces for Recognition,”
Journal of Cognitive Neurosicence, Vol. 3, No. 1, 1991, pp.
71-86.
[4] A. Pentland, B. Moghaddam and T. Starner, “View-Based
and Modular Eigenspaces for Face Recognition,” Pro-
ceedings CVPR’94, 1994 IEEE Computer Society Con-
ference on, Seattle, July 1994, pp. 84-91.
[5] A. Eleyan and H. Demirel, “PCA and LDA Based Face
Recognition Using Feedforward Neural Network Classi-
fier,” Lecture Notes in C omputer Scien ce, Vol. 4105, 2006,
pp. 199-206.
doi:10.1007/11848035_28
[6] J. R. Koza, “Genetic Programming: On the Programming
of Computer by Means of Natural Selection,” MIT Press:
Cambridge, 1992.
[7] S. Xuesong and Y. Zhou, “Gray Intensity Images Proc-
essing for PD Pattern Recognition Based on Genetic Pro-
gramming,” International Joint Conference on Artificial
Intelligence JCAI’09, Haikou, 2009, pp. 711-714.
[8] A. Teredesai and V. Govindaraju, “Issues in Evolving GP
Based Classifiers for a Pattern Recognition Task,” Pro-
ceedings of the 2004 IEEE Congress on Evolutionary
Computation, 20-23 June 2004, pp. 509-515.
[9] J. R. Koza, M. A. Keane, M. J. Streeter, W. Mydlowec, J.
Yu and G. Lanza, “Genetic Programming IV: Routine
Human-Competitive Machine Intelligence,” Kluwer Aca-
demic Publishers, Norwell, 2003.
[10] N. Krause and Y. Singer, “Leveraging the Margin More
Carefully,” Proceedings of the Twenty-First International
Conference on Machine Learning, Banff, 2004, p. 63.
Copyright © 2011 SciRes. JSIP
A Genetic Programming-PCA Hybrid Face Recognition Algorithm
174
[11] J. K. Sing, S. Thakur, D. K. Basu and M. Nasipuri1, “Di-
rect Kernel PCA with RBF Neural Networks for Face
Recognition,” IEEE TENCON Region 10 Conference,
Hyderabad, 2008, pp. 1-6.
[12] AT&T, “The Database of Faces,” 2011.
http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatas
e.html.
[13] Y. Q. Pan and Y. Liu, “Face Recognition Using Kernel
PCA and Hybrid Flexible Neural Tree,” Proceedings of
the 2007 International Conference on Wavelet Analysis
and Pattern Recognition, Beijing, 2-4 November 2007, pp.
1361-1366.
[14] J. Wang, Y. Chen and M. Adjouadi, “A Comparative
Study of Multilinear Principal Component Analysis for
Face Recognition,” 37th IEEE Applied Image Pattern
Recognition Workshop, 2008, pp. 1-6.
doi:10.1109/AIPR.2008.4906476
Copyright © 2011 SciRes. JSIP