IEEE Computational Intelligence Magazine - May 2022 - 71

which is trained by two sorted sets sampled
from search spaces corresponding to
the two tasks. Then multiple top individuals
on each task are transferred to other
tasks through the learned M. Next, populations
with shared individuals undergo
environmental selection until a specific
stopping criterion is met. Thanks to the
EA's implicit parallelism in EMEA, individuals
are regarded as explicit knowledge
transfer carriers. More details of EMEA
can be found in [26].
IV. AUC Optimization
The AUC, an important metric, is widely
employed to measure classification
performance. The AUC optimization
aims to minimize the pairwise loss
between two instances from a training
dataset. Let (xn, yn) be a training instance,
where xRn
d d and {, }.
y 11n
d -+
Then a binary training set D with T+
positive instances and Tnegative
instances
can be described as
73.09
S 11
11
=+ +
- " ^
+
^
1
xx
xx
1
,, ,,
,, ,
h f ^ T+
+
,
-- h, (2)
h f ^ T-,
The objective function of AUC optimization
on training set D [21] is defined as
-
T
AUC wh =
^
where ()g $
+
T
/ / ^ wx wxi(, )( ,)h
+
gff -
2
i =1 j=1
TT+
j
(3)
is
the indicator function
which outputs 1 if the argument is valid
and 0 otherwise, and :f RRd
f wxT
= $
Then (3) can be rewritten as
T
AUC wh =
^
TT+
-
=
T
=1
+
+
T
-
/
/
/ /
T
+
T
-
g $$^ SS -h
+
wx wxj
i #
i =1 j=1
+
T
-
/ / wx wxj
i =1 j=1
TT
g
+
#
-
It can be seen from the above equation
that the AUC optimization is an
^ SS -h$$i
+
(4)
TTi
=1 j =1
TT
g
^ SS -h
+
wx wxj$$i
2
+0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
1
4.788
9.907
16.721
27.167
42.394
52.788
73.086
89.361
101.401
0.01
× T+ × T−
0.04 × T+ × T−
0.09 × T+ × T−
0.16 × T+ × T−
0.25 × T+ × T−
0.36 × T+ × T−
0.49 × T+ × T−
0.64 × T+ × T−
0.81 × T+ × T−
T+ × T−
" is a
real-valued function [3]. This paper focuses
on learning a linear classification model
.
FIGURE 1 Variation of the average computational cost with the sampling rate on the a9a dataset.
TABLE I The computational cost of the AUC optimization on the a9a dataset.
SAMPLING RATE S
ACTUAL
COMPUTATIONAL COST
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Sampling Rate
1
9.91
4.79
40
27.17
20
16.72
42.39
h
60
52.79
expensive NP-hard problem. To find the
optimal parameter of the linear classifier,
the following objective is minimized
T
min AUC wh =
w
^
+
T
-
/ / wx wxj$$i #
i =1 j =1
TT
g
+
m
2
2
w
(5)
where |w|2 is regularization. m is the
penalty parameter, which balances the
feasibility and sparsity of the model f.
Note that different numbers of instances
in the AUC optimization result in different
computational costs. From (5), it
can be seen that the time complexity of
100
89.36
80
^ SS+
+-h
calculating
the objective function of
AUC optimization once is O(T+×T-).
As the number of instances increases,
the optimization objective (5) becomes
very expensive. For this reason, the a9a
dataset [5] is used as an example to
simulate the computational time of the
objective function value with different
sampling rates s ranging from 0.1 to 1
over 1000 independent runs, where the
sampling rate refers to the ratio of the
number of instances used for training to
the number of instances in the total
dataset, and the proportion of positive
and negative samples remains
unchanged during the sampling process.
Figure 1 and Table I show the variation
101.4
THEORETICAL
COMPUTATIONAL COST
MAY 2022 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 71
Computational Cost
IEEE Computational Intelligence Magazine - May 2022

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - May 2022
