Coping with exceptions in multiclass ILP problems using possibilistic logic

1 Introduction

The handling of exceptions is a serious bottleneck in ILP due to the formalization in first-order logic. Indeed, when a rule has some exceptions, i.e. some examples are misclassified by it, there is no way to compensate these exceptions by means of another rule. So, a hypothesis accumulates all the exceptions of the rules that appear in it. Moreover, when dealing with more than two classes, a rule with some exceptions may prevent another one to perform the right classification. A proper handling of exceptions can be made by adding to the standard ILP setting a logical constraint that expresses that an example can be only classified into one class. Thus, having some exceptions may lead to inconsistency. In contrast with first-order logic, default reasoning encoded in possibilistic logic is well-suited for dealing with inconsistency. In this paper, we extend the ILP settings in a possibilistic way in order to handle inconsistency due to exceptions.

2 Preliminaries

Stated in the general context of first-order logic, the task of ILP is to find a non-trivial set of formulas H such that B ∪ H |= E given a background theory B and a set of examples E of the form C(x, y) where x denotes the identification key of an example and y a class. E,B and H here denote sets of Horn clauses. In order to treat multiple classification of an example as inconsistency, we reformulate the ILP problem, by adding the following classification constraint D ≡ ∀X, Y, Z C(X, Y ) ∪ C(X, Z) → Y = Z, as follows : given B, D and E, the goal is to find H such as

Henri Prade

UPS, IRIT, 118 route de Narbonne, 31062 Toulouse, France prade@irit.fr

B ∪D ∪H |= E.

We extend propositional possibilistic logic [Dubois et al., 1994] to the first-order case. Possibilistic logic is sound and complete for refutation, using an extended resolution rule, with respect to a semantics in terms of a complete plausibility preorder on the interpretations (encoded by a possibility distribution) [Dubois et al., 1994]. S denotes a set of Herbrand interpretations. A possibility distribution can be defined on Herbrand interpretations as well. The possibilistic degree of a formula φ is the maximum possibility level of its models and is denoted Π(φ). Necessity is the dual notion of possibility. It refers to the possibility degrees of the counter-models of a formula :N(φ) = 1 - Π(¬φ). A possibilistic first-order formula is a pair (φ, α) where φ is a firstorder formula and α ∈]0, 1]. It is understood as a constraint on an unknown necessity measure of the form N(φ) ≥ α. Given a set K of possibilistic formulas, the α-cut of K is Kα = {φ|(φ, β) ∈ K, β ≥ α}. Given T a set of classical first-order formulas, T is minimal w. r. t. a formula φ iff T |= φ and ∀ψ ∈ T, T - ψ ̸|= φ. The following definition avoids the drowning problem (i.e., consequences are lost when their implicants are taken in inconsistent sets of formulas, although they don't contribute to inconsistency) by checking if it exists a proof of φ in Kα, which is free from inconsistencies at level α.

Definition 1 Given K a set of possibilistic first-order formulas, K |=π (φ, α) iff ∃K′ ⊂ Kα,K′ ̸|= ⊥ such as K′ minimal w. r. t. φ and ∄K′′ minimal w. r. t. ⊥ such that K′ ⊂ K′′ ⊆ Kα.

In practice, this definition makes sure that, if two logical consequences are inconsistent, the one which has the highest necessity degree is preferred. As already advocated in the introduction, we propose to use possibilistic logic in ILP for a better handling of exceptions.

3 Possibilistic ILP

Given H a standard ILP hypothesis, let NH denote a function (called priority function) which at each rule in H associates a priority level, to be understood as a necessity degree. This gives birth to a possibilistic hypothesis Hp = {(h,NH(h)); h ∈ H}. Let Bp and Dp be composed by all formulas that appear respectively in B and D, with 1 as necessity level. The priority function NE over the examples is deduced fromHp as follows :

Then, given D, B and E, the goal of possibilistic ILP is to find Hp, composed by a classical hypothesis H and an associated priority function NH such that Bp ∪Dp ∪Hp |=π Ep with Ep = {(e,NE(e)); e ∈ E}. Note that, if it exists such Hp, this hypothesis will be correct and complete. This enlarges the scope of classical ILP by learning sets of default rules in a framework that handles exceptions, the one of possibilistic logic.

Any possibilistic hypothesis, even it contains some rules with exceptions, can be completed in order to be correct and complete by adding the misclassified examples with 1 as necessity level. Then, the possibilistic ILP problem can be reformulated as an optimization problem :

Given D, B and E, the goal of possibilistic ILP is to find Hp that maximizes the accuracy (i.e. the proportion of wellclassified examples). This definition of possibilistic ILP problem is fully in agreement with the paradigm of the minimization of the empirical risk. Since here, necessity levels are only used for obtaining an ordering of the formulas in H, this induces equivalence classes of priority functions NH. Two priority functions NH and N ′H , belong to the same equivalence class, i.e. NH ≡ N ′H if and only if ∀h1, h2 ∈ H if NH(h1) > NH(h2) then N ′H (h1) > N ′H (h2).

Proposition 1 Given H, finding the class of equivalence of priority functions such the accuracy is maximal is NPcomplete with respect to the number of formulas in H.

It shows that, although using a possibilistic rather than the classical setting is always more effective, finding the best priority function over formulas in H may be computationally very costly. Note that choosing a particular ordering based on the confidence or the support degrees of the rules is not optimal in general. It suggests to use heuristics for inducing hypotheses together with their priority function.

4 Experimentations

In order to learn possibilistic logic rules, we learn a hypothesis directly together with its priority function. The hypotheses are learnt by using a stochastic exploration of the hypothesis space as explained in [Serrurier et al., 2004]. The priority is found by using a greedy algorithm based on the 2-opt method

(switching the order of rules two by two while accuracy increases). Our algorithm is denoted as Pilp. Since Pilp is a non deterministic algorithm, the results that are presented are average results on 50 running steps with the same settings. The value in the brackets are standard derivations for the 50 results. For each experiment, two results are shown : Pilp avg is the average result for the 50 tests, and Pilp max is the best result found in the 50 tests. The experimentation is made with the finite element MESH Design dataset because it represents a typical hard ILP multiple class problem. It describes the structure of a mesh with unary and binary predicates. The dataset contains 277 examples that describe 13 classes. The dataset is split in 5 sub datasets denoted by A, B, C, D and E. The test of the accuracy of the algorithm is made by testing on one subset a hypothesis induced from the other sub datasets. Results are shown in the previous table. The results for the algorithms other than Pilp can be found in [Kietz, 2002]. The results are clearly in the favor of Pilp algorithm which increases the number of examples covered by the most effective algorithm up to 10% in average and 20% at maximum.

5 Conclusion

In this paper, we have proposed a new ILP formalization for dealing with exceptions in a multiple class problem. In order to do that, we have extended possibilistic propositional logic to a first-order setting. Then, by treating exceptions as inconsistency, we have reformulate the ILP problem in firstorder possibilistic logic. In this reformulation, the ILP problem is turned in an optimization problem. This formalization allows our algorithm to learn sets of default rules. In this context, it may exist a correct and complete hypothesis which contains rules that have some exceptions. Possibilistic ILP is more flexible and more general than first-order decision lists [Mooney and Califf, 1995] and allows us to correctly cope with recursive hypotheses. Experiments have proved that an implementation of possibilistic ILP may be very effective for propositional or for relational learning and can compete with the best machine learning algorithms.