Leila Amgoud
email: amgoud@irit.fr

Mathieu Serrurier
email: serrurier@irit.fr

An Argumentation Framework for Concept Learning

Concept learning is an important problem in AI that consists of, given a set of training examples and counter-examples on a particular concept, identifying a model that is coherent with the training examples, i.e that classifies them correctly. The obtained model is intended to be reused for the purpose of classifying new examples. Version space is one of the formal frameworks developed for that purpose. It takes as input a consistent set of training examples on the concept to learn, a set of possible models, called hypothesis ordered by generality, and returns the hypothesis that are coherent with the training examples. The returned set of hypothesis is called version space and is described by its lower and upper bounds.

This paper provides an argumentation-based framework that captures the results of the version space approach. The basic idea is to construct arguments in favor of/against each hypothesis and training example, to evaluate those arguments and to determine among the conflicting arguments the acceptable ones. We will show that the acceptable arguments characterize the version space as well as its lower and upper bounds. Moreover, we will show that an argumentationbased approach for learning offers an additional advantage by allowing the handling of common problems in classical concept learning. Indeed, it is possible to reason directly with sets of hypothesis rather than one, and to deal with inconsistent sets of training examples. Lastly, the framework translates the problem of classifying examples into a decision one.

Introduction

Machine learning aims at building models that describe a concept from a set of training examples. The models are intended to be sufficiently general in order to be reused on new examples. When teexhe concept to learn is binary, i.e. examples of that concept can be either true or false, the problem is called concept learning. In [START_REF] Mitchell | Generalization as search[END_REF], Mitchel has proposed the famous general and abstract framework, called version space learning, for concept learning. That framework takes as input a consistent set of training examples on the concept to learn, a set of possible models, called hypothesis ordered by generality, and returns the hypothesis that are coherent with the training examples. The returned set of hypothesis is called version space and is described by its lower and upper bounds. Besides, argumentation has become an Artificial Intelligence keyword for the last fifteen years, es-pecially in sub-fields such as non monotonic reasoning, inconsistency-tolerant reasoning, multiplesource information systems [START_REF] Amgoud | Inferring from inconsistency in preference-based argumentation frameworks[END_REF][START_REF] Prakken | Argument-based extended logic programming with defeasible priorities[END_REF][START_REF] Simari | A mathematical treatment of defeasible reasoning and its implementation[END_REF][START_REF] Gómez | Integrating defeasible argumentation with fuzzy art neural networks for pattern classification[END_REF].

Argumentartion follows three steps: i) to construct arguments and counterarguments for a statement, ii) to select the "acceptable" ones and, finally, iii) to determine whether the statement can be accepted or not.

This paper claims that argumentation can also be used as an alternative approach for concept learning, which not only retrieves in an elegant way the results of the version space learning framework, but also offers several other advantages. In this argumentation-based approach, the concept learning problem is reformulated as follows: given a set of examples (the training ones, and/or additional examples) and a set of hypothesis, what should be the class of a given example? To answer this question, arguments are constructed in favor of all the possible classifications of the examples. A classification can come either from an hypothesis or from a training example. The obtained arguments may be conflicting since it may be the case that the same example is affected to different classes. We will show that the acceptability semantics defined in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] allow us to identify and characterize the version space as well as its lower and upper bounds. The framework presents also the following features that make it original and flexible:

1. it handles i) the case of a consistent set of training examples; ii) the case of an inconsistent set of training examples; and iii) the case of an empty set of training examples;

2. it allows one to reason directly on the set of hypothesis;

3. examples are classified on the basis of the whole set of hypothesis rather than only one hypothesis as it is the case in standard concept learning. Indeed, in the standard approach, a unique hypothesis is chosen, and all the examples are classified on the basis of that hypothesis.

4. it presents different original and intuitive decision criteria for choosing the class of an example.

The paper is organized as follows. We first present the version space learning framework, then we introduce the basic argumentation framework of Dung [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. The third section introduces our argumentation-based framework for learning.

Vesion Space Learning

The aim of this section is to introduce the version space framework developed by Mitchel in [START_REF] Mitchell | Generalization as search[END_REF]. Let X denote a feature space used for describing examples. Elements of X may then be pairs (attribute, value), first order facts, . . . This set X is supposed to be equipped with an equivalence relation ≡. Let U = {0, 1} be a concept space, where 1 means that the example of the concept is positive, and 0 means that the example is negative.

consistent iff (x 1 , u 1 ), (x 2 , u 2 ) ∈ S such that x 1 ≡ x 2 and u 1 = u 2 . Otherwise, S is said inconsistent.
Regarding the hypothesis space H, it may be, for instance, decision trees, propositional sets of rules, neural nets . . . An hypothesis h is a mapping from X to U (i.e. h: X → U). The set H is supposed to be equipped with a partial preorder that reflects the idea that some hypothesis are more general than others in the sense that they classify positively more examples. This preorder defines a lattice on the hypothesis space. Formally: Definition 2 (Generality order on hypothesis

) Let h 1 , h 2 ∈ H. h 1 is more general than h 2 , denoted by h 1 h 2 , iff {x ∈ X |h 1 (x) = 1} ⊇ {x ∈ X |h 2 (x) = 1}.
Before defining the output of the framework, let us first introduce a key notion, that of soundness.

Definition 3 (Soundness) Let h ∈ H. An hypothesis h is sound with respect to a training example (x, u) ∈ S iff h(x) = u. If ∀(x i , u i ) ∈ S, h is sound w.r.t (x i , u i ), then h is said to be sound with S.
The framework identifies the version space, which is the set V of all the hypothesis of H that are sound with S. From the above definition, we have the following simple property characterizing the elements of V.

Property 1 [START_REF] Mitchell | Generalization as search[END_REF])

V = {h ∈ H|∃h 1 ∈ V S , ∃h 2 ∈ V G , h 2 h h 1 }
In [START_REF] Mitchell | Generalization as search[END_REF], an algorithm that computes the version space V by identifying its upper and lower bounds V S and V G has been proposed.

The above framework has some limits. First, finding the version space is not sufficient for classifying examples out of the training set. This is due to possible conflicts between hypothesis. Second, it has been shown that the complexity of the algorithm that identifies V S and V G is very high. In order to palliate that limit, learning algorithms try in general to reach only one hypothesis in the version space by using heuristical exploration of H (from general to specific exploration, for instance FOIL [START_REF] Quinlan | Learning logical definitions from relations[END_REF], or from specific to general exploration, for instance PROGOL [START_REF] Muggleton | Inverse entailment and Progol[END_REF]). That hypothesis is then used for classifying new objects. Moreover, it is obvious that this framework does not support inconsistent set of examples:

Property 2 [START_REF] Mitchell | Generalization as search[END_REF] If the set S is inconsistent, then the version space V = ∅.

A consequence of the above result is that no concept can be learned. This problem may appear in the case of noisy training data set.

Let us illustrate the above definitions through the following example in which we try to learn the concept "a sunny day".

Example 1 (Learning the concept sunny day) In this example, the feature space is a pair (attribute, value)

Abstract Argumentation Framework

Argumentation is a reasoning model that follows the following steps:

1. Constructing arguments and counter-arguments.

2. Defining the strengths of those arguments.

3. Evaluating the acceptability of the different arguments.

4. Concluding or defining the justified conclusions.

In [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]), an argumentation system is defined as follows:

Definition 7 (Argumentation system) An argumentation system (AS) is a pair A, R . A is a set arguments and R ⊆ A × A is a defeasibility relation. We say that an argument

A defeats an argument B iff (A, B) ∈ R (or A R B).
Note that to each argumentation system is associated an oriented graph whose nodes are the different arguments, and the edges represent the defeasibility relationship between them. Among all the conflicting arguments, it is important to know which arguments to keep for inferring conclusions or for making decisions. In [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], different semantics for the notion of acceptability have been proposed. Let's recall them here.

Definition 8 (Conflict-free, Defence) Let B ⊆ A.

• B is conflict-free iff there exist no A i , A j ∈ B such that

A i R A j . • B defends an argument A i iff for each argument A j ∈ A, if A j R A i , then there exists A k ∈ B such that A k R A j .
Definition 9 (Acceptability semantics) Let B be a conflictfree set of arguments, and let F:

2 A → 2 A be a function such that F(B) = {A | B defends A}. • B is a complete extension iff B = F(B). • B is a grounded extension iff it is the minimal (w.r.t. set- inclusion) complete extension. • B is a preferred extension iff it is a maximal (w.

r.t. setinclusion) complete extension. • B is a stable extension iff it is a preferred extension that defeats all arguments in A\B.

Let {E 1 , . . ., E n } be the set of all possible extensions under a given semantics.

Note that there is only one grounded extension which may be empty. It contains all the arguments which are not defeated, and also the arguments which are defended directly or indirectly by non-defeated arguments. The last step of an argumentation process consists of determining, among all the conclusions of the different arguments, the "good" ones, called justified conclusions.

An Argumentation Framework for Concept Learning

The aim of this section is to propose an instantiation of the general and abstract framework of Dung that allows learning concepts from sets of trainng examples. We will show that this argumentation-based model captures the results of the version space learning presented in a previous section. The sets of version space, specific and general hypothesis are characterized in our model. Since the classical approach of version space learning considers only the case where the set of training examples is consistent, we will present two versions of our model. In the first one, the set S is supposed to be consistent. This model is then generalized to the case where S can be inconsistent. We will show that even in this latter case, the version space V is not always empty, thus it is still possible to learn concepts.

Throughout this section, we will consider a features space X , a concept space U = {0, 1}, a hypothesis space H, which is equipped with a partial preordering (see Definition 2), and a set S of m > 0 training examples.

Consistent Case

In order to instantiate the abstract framework of Dung, one needs to define the set A or arguments as well as the defeasibility relationship between those arguments. In our particular application, one needs to argue about particular classifications, thus arguments are constructed in favor of assigning particular values from U to an example in X . Indeed, an argument in favor of the pair (x, u) represents the reason of assigning the value u to the example x. Two reasons can be distinguished:

1. (x, u) is a training example in S,
2. there exists a hypothesis h ∈ H that classifies x in u.

Definition 10 (Argument) An argument is a triplet

A = h, x, u such that: 1. h ∈ H, x ∈ X , u ∈ U 2. If h = ∅, then u = h(x) 3. If h = ∅, then (x, u) ∈ S
h is called the support of the argument, and (x, u) its conclusion. Let Example(A) = x, and Value(A) = u. Let A be the set of arguments built from (H, X , U).

Note that from the above definition for any trainng example Proof This follows from the above definition, and from the fact that a hypothesis h cannot be empty.

(x i , u i ) ∈ S, ∃ ∅, x i , u i ∈ A. Let A S = { ∅, x, u ∈ A} (i.
Since the set S of training examples is not empty, then A S is not empty as well.

Property 4 A S = ∅.
Proof This follows directly from the above property, i.e. |S| = |A S |, and the assumption that S = ∅.

Let us illustrate the notion of argument through example 1.

Example 2 In example 1, there are exactly four arguments with an empty support, and they correspond to the training examples:

A ∅ = {a 1 = ∅, (pressure, low) ∧ (temperature, medium) ∧ (humidity,high), 0 , a 2 = ∅, (pressure, medium) ∧ (temperature, medium) ∧ (humidity, low), 1 , a 3 = ∅, (pressure, low) ∧ (temperature, medium) ∧ (hu- midity, medium), 0 , a 4 = ∅, (pressure, medium) ∧ (temperature, high) ∧ (hu- midity, medium), 1 }.
There are also arguments with a nonempty support such as: a 5 = ? , medium ∨ high, ? , (pressure, low) ∧ (temperature, high) ∧ (humidity, high), 1 }, a 6 = medium∨ high, ?, ? , (pressure, low) ∧ (temperature, high) ∧ (humidity, high), 0 , a 7 = medium, medium∨ high, ? , (pressure, low) ∧ (temperature, high) ∧ (humidity, high), 0 .

In [START_REF] Amgoud | Inferring from inconsistency in preference-based argumentation frameworks[END_REF][START_REF] Prakken | Argument-based extended logic programming with defeasible priorities[END_REF][START_REF] Simari | A mathematical treatment of defeasible reasoning and its implementation[END_REF], it has been argued that arguments may have different strengths depending on the quality of information used to construct them. In [START_REF] Simari | A mathematical treatment of defeasible reasoning and its implementation[END_REF], for instance, arguments built from specific information are stronger than arguments built from more general ones. In our particular application, it is clear that arguments with an empty support are stronger than arguments with a nonempty one. This reflects the fact that classifications given by training examples take precedence over ones given by hypothesis in H. It is also natural to consider that arguments using more general hypothesis are stronger than arguments with less general hypothesis.

Definition 11 (Comparing arguments) Let

h, x, u , h , x , u be two arguments of A. h, x, u is preferred to h , x , u , denoted by h, x, u Pref h , x , u , iff:

• h = ∅ and h = ∅, or • h h .

Property 5 The relation Pref is a partial preorder.

Proof This is due to the fact that the relation is a partial preorder.

Now that the set of arguments is built, it is possible to define the defeasibility relation R between arguments in A. Here again, there are two ways in which an argument A can attack another argument B: Example 5 With the argument defined in ex. 2 we have for instance : a 1 defeats a 5 , a 2 defeats a 5 , a 3 defeats a 5 , a 4 defeats a 5 , a 5 defeats a 6 , a 5 defeats a 7 and a 6 defeats a 5 .

From the above definition, it is easy to check that an argument with a empty support cannot be defeated by an argument with a non-empty support. From the above proposition and Property 4, it is clear that the ASCL has a non-empty grounded extension. Proposition 2 (Grounded extension) If S is consistent, then the argumentation system A, def eat has a non empty grounded extension E. Proof This is due to the fact that A S = ∅ and A S ⊆ C. Note that the system A, def eat is not always finite. By finite we mean that each argument is defeated by a finite number of arguments. This is due to the fact that H and X are not always finite. Proposition 3 If H and X are finite, then the system A, def eat is finite. When an argumentation system is finite, its characteristic function F is continuous. Consequently, the least fixed point of this function can be defined by an iterative application of F to the empty set. Proposition 4 If the argumentation system A, def eat is finite, then the grounded extension E is:

E = F i≥0 (∅) = C ∪ [ i≥1 F i (C)].
Let us now analyze the other acceptability semantics, namely preferred and stable ones. From Proposition 2, one concludes that the ASCL A, def eat has at least one nonempty preferred extensions.

Proposition 5 If S is consistent, then the ASCL A, def eat has n ≥ 1 non-empty preferred extensions. Proof In [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], it has been shown that the grounded extension is included in very preferred extension. Since the grounded extension is not empty (according to Proposition 2, then there exists at least one non-empty preferred extension). In general, the preferred extensions of an argumentation system are not stable. However, in our ASCL these extensions coincide. This result is due to the fact that the oriented graph associated to the above ASCL has no odd length circuits. However, it may contain circuits of even length.

Proposition 6

• The graph associated with the system A, def eat has no odd length circuits. • The preferred extensions and stable extensions of the system A, def eat coincide. Part 2: This is a consequence of the fact that there is no odd circuits in the system.

Proof (Sketch of the proof)

Note, however, that the intersection of all the preferred (stable) extensions coincides with the grounded extension.

Proposition 7 Let A, def eat be a ASCL. Let E be its grounded extension, and E 1 , . . . , E n its preferred (stable) extensions. E = i=1,...,n E i .

Let us now show how the above ASCL can retrieve the results of the version space learning, namely the version space and its lower and upper bounds. Before doing that, we start first by introducing some useful notations.

Let Hyp be a function that returns for a given set of arguments, their non empty supports. In other words, this function returns all the hypothesis used to build arguments:

Definition 16 Let T ⊆ A.
Hyp(T ) = {h | ∃ h, x, u ∈ T and h = ∅} Now we will show that the argumentation-based model for concept learning computes in an elegant way the version space V (see Definition 4).

Proposition 8 Let A, def eat be a ASCL. Let E be its grounded extension, and E 1 , . . . , E n its preferred (stable) extensions. If the set S is consistent then:

Hyp(E) = Hyp(E 1 ) = . . . = Hyp(E n ) = V
where V is the version space.

Proof Let E i be an extension under a given semantics.

Hyp(E i ) ⊆ V: Let h ∈ Hyp(E i ), then ∃ h, x, u ∈ E i .
Let us assume that ∃(x i , u i ) ∈ S such that h(x i ) = u i . This means ∅, x i , u i undercuts h, x, u (according to Definition 13). Consequently, ∅, x i , u i defeats h, x, u . However, according to Property 3, ∅,

x i , u i ∈ A S , thus ∅, x i , u i ∈ E i . Contradiction because E i is an extension, thus by definition it is conflict-free. V ⊆ Hyp(E i ): Let h ∈ V, and let us assume that h / ∈ Hyp(E i ). Since h ∈ V, then ∀(x i , u i ) ∈ S, h(x i ) = u i (1)
Let (x, u) ∈ S, thus h(x) = u and consequently h, x, u ∈ A. Moreover, since h / ∈ Hyp(E), then h, x, u / ∈ E. Thus, ∃ h , x , u that defeats h, x, u . • Case 1: h = ∅. This means that ∅, x , u undercuts h, x, u and h(x ) = u Contradiction with (1). • Case 2: h = ∅. This means that h , x , u rebuts h, x, u . Consequently, x ≡ x and u = u . However, since h ∈ V, then h is sound with S. Thus, ∅, x, u defeats h , x , u , then ∅, x, u defeats h, x, u . Since ∅, x, u ∈ S, then h, x, u ∈ F(C) and consequently, h, x, u ∈ E i . Contradiction.

The above result is of great importance. It shows that to get the version space, one only needs to compute the grounded extension.

We can also show that if a given argument is is an extension E i , then any argument based on an hypothesis from the version space that supports the same conclusion is in that extension. Formally:

Proposition 9 Let A, def eat be a ASCL, and E 1 , . . . , E n its extensions under a given semantics.

If < h, x, u >∈ E i , then ∀h ∈ V s.t. h = h if h (x) = u then < h , x, u >∈ E i .
Proof Let E i be a given extension, and let h, x, u

∈ E i . Let h ∈ V such that h (x) = u. Let us assume that h , x, u / ∈ E i .
Case 1: E i ∪ { h , x, u } is not conflict-free. This means that ∃ h", x", u" ∈ E i such that h", x", u" defeats h , x, u . Consequently, h", x", u" undercuts h , x, u if h" = ∅, or h", x", u" rebuts h , x, u if h" = ∅. If h" = ∅, then h (x") = u", this contradicts the fact that h ∈ V. If h" = ∅, then x" ≡ x and u" = u and either h" h , or h , h" are not comparable. Thus, h", x", u" rebuts h, x, u . Since h, x, u , h", x", u" ∈ E i , then h and h" are not comparable. But, this means that h, x, u defeats h", x", u" , and h", x", u" defeats h, x, u . Consequently, E i is not conflict-free. Contradiction because E i is an extension. Case 2: E i does not defend h , x, u . This means that ∃ h", x", u" defeats h , x, u .

• Case 1: h" = ∅. This means that h (x") = u". Contradiction because h ∈ V. • Case 2: h" = ∅. This means that x ≡ x", u = u", and h" h . Thus, h", x", u" rebuts h, x, u . If h h", then h, x, u defeats h", x", u" , thus h, x, u defends h , x, u . If h" h, then h", x", u" defeats h, x, u . However, since h, x, u ∈ E, then E defends h, x, u against h", x", u" . Thus, E defends h , x, u . Contradiction Using the grounded extension, one can characterize the upper and the lower bounds of the version space. The upper bound corresponds to the most preferred w.r.t Pref arguments of the grounded extension, whereas the lower bound corresponds to the less preferred ones. Proposition 10 Let A, def eat be a ASCL, and E its grounded extension.

• V G = {h | ∃ <h, x, u> ∈ E s.t ∀ <h , x , u > ∈ E, not (<h , x , u > Pref <h, x, u>)}. • V S = {h | ∃ <h, x, u> ∈ E s.t ∀ <h , x , u > ∈ E, not (<h, x, u> Pref <h , x , u >)}. Proof V G = {h | ∃ <h, x, u> ∈ E s.t ∀ <h , x , u > ∈ E, not (<h , x , u > Pref <h, x, u>)}. • Let h ∈ V G , thus h ∈ V,
∀ h ∈ Hyp(E), not(h h), thus h ∈ V G . V S = {h | ∃ <h, x, u> ∈ E s.t ∀ <h , x , u > ∈ E, not (<h, x, u> Pref <h , x , u >)}. • Let h ∈ V S , thus h ∈ V such that h h . Since h ∈ V S , then h ∈ V and consequently, h ∈ Hyp(E). This means that ∃ h, x, u ∈ E. Let us assume that ∃ h , x , u ∈ E such that h, x, u P ref h , x , u , thus h h . Contradiction with the fact that h ∈ V S . • Let h, x, u ∈ E such that ∀ h , x , u ∈ E,
U V = {(x, u)|∃ < h, x, u >∈ E}
It is easy to check that the set of universally classified examples is included in the set of majoritarily classified ones.

Property 9 Let A, def eat be a ASCL, and E 1 , . . . , E n its extensions under a given semantics :

U V ⊆ M V
Proof This result follows directly from the fact that the extensions are conflict-free.

Inconsistent Case

Let us now consider the case where S is inconsistent, with S can be partionned into S 1 , . . . , S n , suth that each S i is a maximal (for set inclusion) consistent subsets of S. This means that some training examples are classified in different classes. However, all the elements of S are supposed to be equally preferred. In this case, two arguments supporting such conflicting training examples rebut each other, thus can defeat each other as well.

Let A S1 , . . ., A Sn be the sets of arguments with an empty support and whose conclusions are respectively in the subsets of training examples S 1 , . . . , S n . It is clear that each set A Si is conflict-free, however, it is defeated by arguments in A Sj with i = j.

As in the consistent case, arguments with an empty support are preferred to arguments built from hypothesis. In what follows, ASCL i will denote the argumentation system in the inconsistent case. Note that all the above definitions of an argument, of defeat, do not change. It can be checked that the corresponding oriented graph of ASCL i does not contain odd length circuits.

Proposition 11

• The graph associated to the system ASCL i has no odd length circuits. • In the ASCL i A, def eat , preferred extensions and stable ones coincide.

As a consequence of the above result, the system ASCL i has preferred extensions that are also stable. Moreover, the grounded extension of this system coincides with the intersection of all the preferred extensions. Let E 1 , . . . , E n be the preferred extensions of that system, and E its grounded extension.

Proposition 12 If S is inconsistent and non empty, then the ASCL i A, def eat has still n ≥ 1 non-empty preferred extensions. Moreover, E = i=1,...,n E i .

However, the grounded extension can be empty in this particular case of inconsistent training examples. The above result is of great importance since it shows that even in this particular case of inconsistent training example, it is still possible to classify examples.

Note that each preferred/stable extension contains one of the sets A S1 , . . ., A Sn . Moreover, the same set A Si may belong to several extensions at the same time. It can be shown that all the hypothesis that are used to build arguments in a given extension are sound with the subset of training examples of that extension. Indeed, for each consistent subset of S, we get the extensions of the consistent case previously studied.

Case of an Empty Set of Training Examples

Another interesting case is when the set of training examples is empty. In this case, the learning problem consists of classifying examples only on the basis of a set H of hypothesis. This is, indeed, a particular case of the previous case where S is inconsistent. The corresponding argumentation system constructs then arguments only on the basis of hypothesis, thus there is no argument with an empty support. This system satisfies exactly the same properties as the ASCL i . For instance, the corresponding graph has no odd length circuits. Moreover, it contains at least one non-empty preferred extension, which is also stable. The grounded extension of this sytstem is the intersection of all the preferred extensions.

Conclusion

This paper has proposed, to the best of our knowledge, the first argumentation-based framework for concept learning. This framework considers the learning problem as a process that follows four main steps: it first constructs arguments in favor of classifications of examples from a set of training examples, and a set of hypothesis. Conflicts between arguments may appear when two arguments classify the same example in different classes. Once the arguments identified, it is possible to compare them on the basis of their strengths. The idea is that arguments coming from the set of training examples are stronger than arguments built from the set of hypothesis. Similarly, arguments based on general hypothesis are stronger than arguments built from more specific hypothesis. Indeed, such preference relation between arguments ensures that during the learning process, only hypothesis that are sound with the training examples are kept, and general hypothesis are privileged to less specific ones. We have shown that acceptability semantics of the ASCL retrieves and even characterizes the version space and its upper and lower bounds. Thus, the argumentation-based approach gives another interpretation of the version space as well as its two bounds in terms of arguments. We have also shown that when the set of training examples is inconsistent, it is still possible to learn concepts, and to classify examples of it. Indeed, in this particular case, the version space is empty as it is the case in the version space learning framework. A last and not least feature of our framework consists of defining the class of each example on the basis of all the hypothesis and not only one, and also to suggest four intuitive decision criteria for that purpose. A first extension of this framework would be to explore the proof theories in argumentation that test directly whether a given argument is in the grounded extension without com-puting this last. This means that one may know the class of an example without exploring the whole hypothesis space.

This framework can easily be generalized to the case of classification problems in which an example can be affected to a class among a set of possible classes. It could also be extended in order to handle qualitative uncertainty and preferences on examples. It can also be extended to handle the regression problem in which the concept takes the form of a continuous function.

  e. the set of arguments coming from the training examples). Property 3 Let S be a set of training examples. |S| = |A S | 1 .

Part 1 :Case 1 :

 11 Let A, B, C be three arguments such that A defeats B, B defeats C, and C defeats A. Let us suppose that A ∈ A S . Accroding to Property 6, B ∈ A\A S . According to Property 7, C should be in A\A S . Contradiction because according to Property 7, C cannot defeat A, which is in A S . Case 2: Let us suppose that A, B, C ∈ A\A S . This means that A rebuts B, B rebuts C, and C rebuts A (according to Definition 13). Consequently, Example(A) ≡ Example(B) ≡ Example(C), and Value(A) = Value(B), Value(B) = Value(C). Due to the fact that U = {0, 1}, we have Value(A) = Value(C). This contradicts the assumption that C rebuts A.

  The version space framework takes as input a hypothesis space H, and a set S of m training examples.S = {(x i , u i ) i=1,...,m s.t x i ∈ X and u i ∈ U}Note that the set S contains both positive examples (i.e. the value of x -i is equal to 1), and negative ones (i.

e. the value of x -i is equal to 0). Otherwise, the learning problem becomes trivial and not genuine. An important notion in concept learning is that of consistency. In fact, a set of examples is said to be consistent if it does not contain two logically equivalent examples with two different values. Formally: Definition 1 (Consistency) The set S of training examples is

Specific hypothesis) The

  set of specific hypothesis is V S = {h ∈ H | h is sound with S and h ∈ H with h sound with S, and h h }.

	Definition 5 (General hypothesis) The set of general hy-
	pothesis is V G = {h ∈ H | h is sound with S and h ∈ H
	with h sound with S, and h	h}.
	Definition 6 (
	The
	idea is that a "good" hypothesis should at least classify the
	training examples correctly.
	Definition 4 (Version space)
	V = {h ∈ H| h is sound with S}
	Version space learning aims at identifying the upper and the
	lower bounds of this version space V. The upper bound will
	contain the most general hypothesis, i.e the ones that clas-
	sify more examples, whereas the lower bound will contain
	the most specific ones, i.e the hypothesis that classify less
	examples.

1

  || denotes the cardinal of a given set 1. by rebutting its conclusion. This situation occurs when the two arguments have contradictory conclusions, i.e. the same example is classified in different ways. 2. by undercutting its support. This occurs when the support of B classifies in a different way the example of the conclusion of A. However, this relation is only restricted to training examples. Indeed, only arguments built from training examples are allowed to undercut other arguments. The idea behind this is that training examplesare the only, in some sense, certain information one has, and thus cannot be defeated by hypothesis. However, hypothesis have controversial status. Let h, x, u , h , x , u be two arguments of A. h, x, u rebuts h , x , u iff x ≡ x , u = u . In example 2, we have for instance : a 5 rebuts a 6 , a 5 rebuts a 7 , a 6 rebuts a 5 , and a 7 rebuts a 5 . In example 2, we have for instance : a 1 undercuts a 5 , a 2 undercuts a 5 , a 3 undercuts a 5 , and a 4 undercuts a 5 .

	Definition 12 (Rebutting) Example 3

Definition 13 (Undercutting) Let h, x, u , h , x , u be two arguments of A. h, x, u undercuts h , x , u iff h = ∅ and h (x) = u.

Example 4

The rebutting and undercutting relations are used in most argumentation systems that handle inconsistency in knowledge bases.

Property 6 If S is consistent, then A, B ∈ A S such that A rebuts B, or A undercuts B.

Proof Let A = ∅, x, u , B = ∅, x , u ∈ S such that A rebuts B. According to Definition 12, x ≡ x and u = u . This contradicts the fact that S is consistent.

The two above conflict relations are brought together in a unique relation, called "Defeat". Definition 14 (Defeat) Let A = h, x, u , B = h , x , u be two arguments of A. A defeats B iff: 1. A rebuts (resp. undercuts) B, and 2. (A Pref B), or (not(A Pref B) and not(B Pref A))

  If S is consistent, then A S ⊆ C. Proof Let A ∈ A S . Let us assume that ∃B ∈ A such that B defeats A. According to Property 7, B / ∈ A\A S . Thus, B ∈ A S . Moreover, B defeats A means that B rebuts A. This means then that A classifies a training example in u, and B classifies an equivalent example in u = u. This contradicts the fact that the set S is consistent.

	The argumentation system for concept learning is then the
	following:
	Definition 15 (Argumentation system) An argumentation
	system for concept learning (ASCL) is a pair A, def eat ,
	where A is the set of arguments (see Definition 10) and de-
	feat is the relation defined in Definition 14.
	Let us now identify the acceptable arguments of the above
	ASCL. It is clear that the arguments that are not defeated at
	all will be acceptable. Let C denote that set of non-defeated
	arguments.
	Proposition 1
	This means that B rebuts A (because according to Definition
	13, an argument with a non-empty support cannot undercut
	an argument with an empty one. Moreover, according to

Property 7 ∀ A ∈ A S , B ∈ A\A S s.t B defeats A. Proof Let A ∈ A S and B ∈ A\A S such that B defeats A. Definition 14, we have either B Pref A, or (not(B Pref A) and not(A Pref B)). This is impossible because according to Definition 11, arguments in A S are always preferred to arguments with a non-empty support.

  and ∀h ∈ V, h h . Since h ∈ V, thus, h ∈ Hyp(E), with E an extension. Then, ∃ h, x, u ∈ E. Since h h for any h ∈ V, then h h for any h ∈ Hyp(E). Thus, h, x, u Pref h , x , u , ∀ h , x , u ∈ E. • Let h, x, u ∈ E such that ∀ h , x , u ∈ E,and not( h , x , u P ref h, x, u ). Thus, h ∈ Hyp(E), and

  and not( h, x, u P ref h , x , u ), thus not(h h ). Since h ∈ V, and ∀h ∈ V, not(h h ), then h ∈ V S . Let A, def eat be a ASCL, and E 1 , . . . , E n its extensions under a given semantics. Let x ∈ X and u ∈ U.Universal vote: x is universally classified in u iff ∀E i , ∃ <h, x, u> ∈ E i . U V denotes the set of all universally classified examples. Majority vote: x is majoritarily classified in u iff |{< h, x, u > |∃E i , < h, x, u >∈ E i }| ≥ |{< h, x, u > |u = u, ∃E i , < h, x, u >∈ E i }|. M Vdenotes the set of all majoritarily conclusions accepted by majority vote. The universally classified examples are those which are supported by arguments in all the extensions. From a learning point of view, these correspond to examples classified by the most general hypothesis in the version space. Thus, according to Proposition 7, we have the following result: Property 8 Let A, def eat be a ASCL, and E its grounded extension :

	As said before, the last step of an argumentation process
	consists of defining the status of the conclusions, in our case,
	the classification of examples. In what follows we present
	two decision criteria: The first one, called universal vote,
	consists of accepting those classifications that are in any ex-
	tension. However, it is clear that this kind of voting may not
	classify all the examples. Thus, we propose a second cri-
	terion, called majority vote, that allows to associate a class
	to each example. The conclusions here are the ones that are
	supported by a majority of arguments that appear in the dif-
	ferent extensions. Formally:
	Definition 17

Acknowledgments

This work was supported by the Commission of the European Communities under contract IST-2004-002307, ASPIC project "Argumentation Service Platform with Integrated Components".