In this paper we present a method to enrich the hypothesis language which is used to construct the bottom clause. This approach, which is embedded in the Aleph system, is based on numerical xed subintervals and categorical subsets. Each subinterval/subset contains values, for each attribute which is prede ned, that are related with the example to saturate. The enriched language allows to reduce the number of rules of the nal theories and, in some cases, to improve the accuracy.
Most of the ILP algorithms induce one clause at a time in order to nd a theory T . Each clause in T is usually constructed with a single numerical (or categorical) value for each attribute1. This may result in inaccurate theories with a lot of rules. To overcome these drawbacks, some ILP systems use approaches which are based in the following strategies:
Discretization. Some ILP systems discretize numerical attributes in a global
way, and the nal intervals are used during the learning process. TILDE [
In this paper we present a method to enrich the hypothesis language which is used to construct the bottom clause. This approach deals with both categorical and numerical attributes, in a local or global way. The enriched language allows to reduce the number of rules of the nal theories and, in some cases, to improve the accuracy. This paper is organized as follows: section 2 describes the proposed method; section 3 shows the experimental results on several data sets; nally, section 4 presents our conclusions and future work. 2
To enrich the hypothesis language our method tests di erent numerical subintervals (or categorical subsets) according to an evaluation function, then the best quali ed are added into the background knowledge. Due to the great amount of subintervals/subsets that can be created we decided to use an evolutive approach to generate and evaluate them. This method was embedded in the basic algorithm of Aleph as follows:
0. State parameters. In addition to the mode declarations, types and determinations, users can also declare the attributes to be discretized/grouped in any of the two following ways: i. lit(: : : ; Attr; : : :), goal(: : : ; Class)
Where Attr is the attribute to discretize/group respect to Class which can have more than two values. The predicate lit is into the background knowledge (it is possible to declare two or more attributes in lit), and goal is the target predicate. ii. lit(: : : ; Attr; : : :)
In this case the corresponding classes are positive and negative.
1. Select an example e. In this step, a subset of values of Attr are related to the example selected. For instance, let e = goal(a) be the example selected and lit(a; 12), lit(a; 15), lit(a; 20), lit(b; 30), lit(b; 35) be ve facts in the background knowledge then the values 12; 15; 20 are related to e. If Attr is a numerical attribute, then these values form a FixedSubinterval. If Attr is a categorical attribute, then we call FixedSubset to these subset of values. These are xed because it will invariably be in all subintervals/subsets that will be tested.
1.5 Discretization/Grouping. Before saturation each attribute declared by the user is processed. Depending on the attribute type there are two possible cases.
i. Let Attr be a numerical attribute and F ixedSubinterval = [min; max] be the interval that contains all values in Attr that are related to e. Then the proposed genetic algorithm returns a set of numerical intervals In such that: jInj is de ned by the user and In = fx j x = [min0; max0] ^ min0 min ^ max max0g.
Furthermore each element in In represents a chromosome. To evolve the chromosomes several mutation operators are de ned. These can enlarge or shrink an interval, either on the left side, on the right side, or on both sides. The tness function for a chromosome x is given by the information gain, see Eq. (1). In this case the GA maximizes the information gain to nd better subintervals.
IG(x) = ent(Int) count(x) count(Int) ent(x) (1) The corresponding entropy for some interval Int is:
jSj ent(Int) = X p(Int; j)log2(p(Int; j))
j=1 where: jSj = number of classes, Int is the numerical interval of Attr, count(Int) = numeric values into interval Int, p(Int; j), is the proportion of values in Int that belong to the jth class.
ii. Let Attr be a categorical attribute and FixedSubset be the set of all values related to e. The proposed GA searches the best jCj subsets of categorical values with the following constraint: C = fy j FixedSubset yg.
A chromosome is represented by a subset y. The mutation operators de ned add a new categorical value in y, delete an element from the chromosome, or swap an element between the chromosome and the rest of categorical values, but maintaining the FixedSubset into each new chromosome. The crossover operator swaps an element between two chromosomes.
In this case, the tness function is based on the distance between two values
of a categorical attribute. The tness for a chromosome y is the total sum of
the distances for each value pair in y. In addition to this, if the sum of distances
for two or more chromosomes is the same, then the value jy1j is added, because
we want to minimize and to favor the subsets with more values. This tness
function, called DILCA [
Fitness(y) =
X s X (P (ci j st) P (cj j st))2 + y1 cicj2y st2S j j (2) where: ci; cj 2 y such as i 6= j. S is the set of classes de ned, P (ci j st) is the conditional probability for ci given st, and P (cj j st) is the conditional probability for cj given st. In both cases the user can give the number of chromosomes to be added. 2. Build a bottom clause that entails the example e. The enriched language is used to build a bottom clause. Consider the goal relation no payment(S) which is true for those students who do not need to repay its loan. If literals in background knowledge are unemployed(S), enrolled(S; School; U nits), where U nits is numerical and School is categorical, then a bottom clause would be like this: no_payment(A) :- unemployed(A),enrolled(A,B,C), interval(C,[11.0,13.4]),interval(C,[11.7,12.5]),interval(C,[11.3,13.3]), interval(C,[11.3,14.0]),interval(C,[11.0,13.5]),interval(C,[10.0,12.3]), member(B,[occ,smc,uci,ucla,ucsd]),member(B,[smc,ucb,ucla,ucsd]).
3. Search. Aleph uses several search strategies (best rst, depth rst search, etc.), re nement operators, and evaluation functions (as mentioned earlier).
4. Remove covered (redundant) examples and add the best clause found to the current theory. Go to step 1.
In the next section we present the experiments performed to compare the accuracy of our method.
In this section we compare our method (we call it Extended Aleph) with the
standard Aleph, and the lazy evaluation in Aleph [
From the UCI machine learning repository [
All these methods were executed in Yap Prolog version 6:0, with the global parameters: minpos = 2, and noise = 5; the remaining of the parameters are xed by default in Aleph. All experiments were performed on a modern multicore PC machine.
Extended Aleph vs Aleph. Table 1, shows that our implementation improves the accuracy in most databases, with the exception of two datasets: Pittsburgh Bridges and Moral Reasoner. We can also see ( gure 1) that the increase of the accuracy for the datasets Japanese Credit Screening and Iris is signi cant, 15% and 7:8% respectively. Regarding the simplicity of the nal theories, extended Aleph system does not improve the simplicity with two datasets: German Credit and KRKi, but with the other datasets (excepting Moral Reasoner) our approach decreases the number of rules in the nal theories. In particular, with Iris and Student Loan the reduction is almost 50% ( gure 2).
Extended aleph vs Lazy Evaluation in Aleph. As in the previous case, Extended Aleph improves the accuracy except in two datasets: Moral Reasoner and Student Loan (table 1). Furthermore, Lazy Evaluation overcomes our method only in one single dataset: Student Loan, ( gure 2). Although both have the same accuracy.
In general, Extended Aleph improves or maintains the accuracy ( gure 1),
and decreases the number of rules for most of datasets. With regard to the
running time, Extended Aleph signi cantly exceeds this measure with
Carcinogenesis: Aleph 36:1s, Lazy 222:33s, Ext. Aleph 698:9s; and Ecoli: Aleph 11:5s;
Lazy 63:2s; Ext. Aleph 707:5s.
With the obtained results, we can draw some conclusions: this method does not
guarantee to improve the accuracy and simplicity of the theories in all cases.
The improvement depends on the selected attributes, namely if an attribute is
relevant in the theory construction then its processing will help to improve the
nal theory. ILP problems whose nal theories do not need constants to be
induce on them can not bene t from this method. In this case, variables are useful
to better explain that concept. The size of the search space can be a ected with
the proposed method. On one hand a discretized/grouped attribute which is
not relevant can generate a large amount of unnecessary candidate rules. On
the other hand a discretized/grouped attribute which is relevant can decrease
signi cantly the number of candidate rules. Users do not know in advance which
attributes will be most useful, therefore the intuition is an important element to
select each attribute. Our method allows to experiment easily with di erent
attributes. Finally, unlike other genetic approaches like SMART+ [
Some considerations for further work are as follows. Since not all cases were successful it is necessary to test other tness functions and more datasets. These tests will help us to identify the factors which a ect both accuracy and simplicity of the nal theories, as well as the search space size. Another path of research is to look into multivariable predicates, if there are correlations between two or more attributes. Thus, we want to investigate if these correlations are relevant to improve the performance in ILP (accuracy and simplicity) and what kind of problems can be treated with these predicates. Finally, we want to implement in Aleph system these ideas and compare performance with other ILP systems that handle data types.