IEEE Computational Intelligence Magazine - August 2020 - 38

can remain fixed. Only the minimum accuracy minAcc and the number of representatives
R have an important impact on the results,
because they are directly related to the problem noise and the additional search effort,
respectively. Analyzing R in depth would
require a very long and complex experimentation. For simplicity in this paper we have set the hyperparameter to a value (10) that in preliminary work showed to
be suitable for all tested scenarios, although a smaller R would
also work in some of the easier datasets. Moreover, it should be
noted that the reason why the P(rep) function has a score lower
than the two other metrics is because, in preliminary experimentation, this metric was not as reliable as the other ones.

If the number of attributes in the terms is k the
adequate coverage breakpoint to solve the problem is
2k. This translates the problem of finding the adequate
coverage breakpoint to finding k.
6.1. Analysis of the Hyper-Parameter Setting Approach
Over Binary Problems

In this section we analyze the performance of our approach over a
wide variety of k-DNF problems, in terms of probability of success
(finding the adequate hyper-parameter value). At the end, we also
comment briefly on the additional effort incurred by the heuristic
in terms of additional evaluation operations.
The k-DNF problems used in this section have the following
characteristics: d = 20, k = {2 - 9} , and r = {5, 10, 20, 40} .
Moreover, we introduced output noise of 0%, 1%, 5% and 10%
over the problems to determine how robust was the classification process towards noise. We generated 5 different problems
of each k-DNF scenario, and each problem was run with 5 different seeds. Also, all these runs were performed using fixed
default class 0. Since in the k-DNF problems all the generated
terms map to class 1, this setting prevents the system form
learning the inverse problem, over which calculating the success would not be straightforward.
The learning process was not performed during this stage of
experiments, but only the hyper-parameter setting stage. In
these experiments, we want to quantify how many times the
heuristic finds the optimal k for the problem (or at least a larger
one) which would ensure the learning.
We also experiment changing the hyper-parameter minAcc
(the minimum accuracy demanded in a rule to become a representative) to determine how this hyper-parameter affects the
search, and show how it can help tackling problems with
noise more efficiently. In these experiments we tested hyperparameter values minAcc = {1.0, 0.95, 0.9}. To determine significant differences among using different minAcc values we
used a Friedman test with its post-hoc Holm test, as shown
by [66].
The rest of the hyper-parameters in our approach are
shown in Table 1 for clarity and replication purposes. However,
according to our preliminary experiments, the hyper-parameters shown in this table can be considered constants and they

TABLE 1 Hyper-parameters for the heuristic used to characterize
and find the coverage breakpoint for k-DNF problems.
HYPER-PARAMETER
NUMBER OF REPRESENTATIVES NEEDED - R

EVALUATED POPS TO CHANGE p

MOST FREQUENT k IN REPRESENTATIVES - SCORE A

IMBALANCE FUNCTION - SCORE B

PREP FUNCTION - SCORE C
SAMPLE SIZE - N

VALUE

1
500

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | AUGUST 2020

6.1.1. Results
Table 2 presents the results for the different k-DNF configurations and different values of minAcc in terms of percentage of
success (finding the k of the problem or at least a larger one).
Results for k = 2 and r = 40 are omitted because in these setting all instances belong to class 1. The cells emphasized represent the configurations where the success rate is less than 100%.
For minAcc < 1, the cells marked with red show the cases
where the success rate is lower than the base case (minAcc =
1.0), and the cells marked with green show the cases where the
success rate increased. In this table we can observe that using
minAcc = 1 the heuristic is able to find the appropriate coverage breakpoint for most of the configurations with no noise.
Moreover, it is noticeable that the output noise affects the performance of the heuristic.
On the other hand, we can observe that the heuristic fails in
the cases where there is very high rule overlapping. These problems are very difficult to solve by the system because of the class
imbalance [30], so it is not surprising that they are difficult for
the heuristic as well. Such large overlapping makes the heuristic
think that the k is smaller than the real one. In the case of a synthetic problem like the k-DNF, where we know the correct
answer, this is incorrect. However, what the system is trying to
do is not completely wrong, because it is trying to solve the
problem with less complex rules compromising the accuracy
slightly, which in real-life domains can be advantageous. To
understand better these domains further research focusing specifically on the rule overlapping scenario is required.
Figure 6 shows an example of the final score grid of the
heuristic using minAcc = 1 for a problem with k = 5 and r = 20
with the 4 levels of noise. In each of the four plots (for a different level of noise) the vertical stripe corresponds to the 2 points
that are awarded to the most frequent number of attributes
observed in the representatives. The curved stripes correspond
to the scores awarded by the other two criteria of the heuristic.
In this figure we can see that while the problem increases the
representatives present a higher number of attributes. When this
happens this area does not intersect the two other areas, thus
the heuristic fails to find the appropriate k value. This is
because the constraint of minAcc = 1.0 is too strict in these

IEEE Computational Intelligence Magazine - August 2020

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2020