Argumentation can be used by a group of agents to discuss about the validity of hypotheses. In this paper we propose an argumentationbased framework for distributed induction, where two agents learn separately from individual training sets, and then engage in an argumentation process in order to converge to a common hypothesis about the data. The result is a distributed induction strategy in which the agents minimize the set of examples that they have to share in order to converge to a common hypothesis. The proposed strategy works for any induction algorithm which expresses the hypothesis as a disjunction of rules. We show that the strategy converges to a hypothesis indistinguishable in training set accuracy from that learned by a centralized strategy.
Distributed induction is the problem of learning a hypothesis or model (such as a set of rules, or a decision true) from data when the data is distributed among di erent sources. Some real-life domains involve such forms of distributed data, where data cannot be centralized due to one or several of the following reasons: storage size, bandwidth, privacy, or management issues. Storage size and bandwidth are less and less a problem nowadays, however in large data sets they might still be an issue. In this paper we will propose a framework in which agents will use a limited form of argumentation in order to arrive to a model of all the data while minimizing the communication, and specially minimizing the amount of examples exchanged, and ensuring that the hypothesis found is exactly as good as if centralized induction with all the data was used.
Argumentation frameworks can be used in multi-agent systems for di erent
purposes such as joint deliberation, persuasion, negotiation, and con ict
resolution [
Formalizing agent communication as argumentation allows the distributed
induction strategies to abstract away from the induction algorithm used by the
agents. Thus, all the strategies presented in this paper can work with any
induction algorithm that satis es certain requirements. In particular, we require that
the hypotheses learnt can be expressed as a disjunction of independent rules.
So, for instance, algorithms such as FOIL [
The remainder of this paper is organized as follows. Section 2 presents our multi-agent learning framework, including our formalism for argumentation. Section 3 presents two strategies for distributed induction based on argumentation, and Section 4 empirically evaluates them, comparing them to other distributed induction strategies in the literature. Section 5 provides a quick overview of the related work, and nally the paper closes with conclusions and future work. 2
Let A1 and A2 be two agents who are completely autonomous and have access only to their individual and private training sets T1, and T2. A training set Ti = fe1; :::; eng is a collection of examples. Agents are able to individually apply induction in order to learn a hypothesis (or model) of the data and solve problems using the induced model, but they can also collaborate with other agents for both induction and problem solving. In the rest of this paper we will use the terms model and hypothesis indistinguishably. 2.1
Examples, Hypotheses and Rules Examples, hypotheses and rules are the three key concepts of the learning framework proposed in this paper.
We will restrict ourselves to analytical tasks, i.e. tasks, such as classi cation, where the solution of a problem is achieved by selecting a solution class from an enumerated set of solution classes. In the following we will note the set of all the solution classes by S = fS1; :::; SK g. Therefore, an example e = hP; Si is a pair containing a problem P and a solution class S 2 S. In the remainder of this paper, we will use the dot notation to refer to elements inside a tuple; e.g., to refer to the solution class of an example e, we will write e:S.
Our framework is restricted to hypotheses H that can be represented as a disjunctive set of rules: H = fr1; :::; rmg. A rule r = hH; Si is composed of a body r:H, and a solution, r:S. When a problem P matches the body r:H green
CC no Cross yes
Wait CN2 output: default: C red Wait C
A A
B
of a particular rule r, the rule predicts that the solution to the problem P is
r:S. When a problem matches the body of a rule r:H, we say that the body
subsumes the problem: r:H v P . A large number of induction algorithms can
generate hypothesis that can be represented using this formalism. In particular,
in our experimental section we have selected to use INDIE [
The framework introduced in this paper does not specify which induction algorithm or representation formalism agents use. In principle, any induction algorithm could be used, and any data representation (propositional, relational, or any other) could be used. The restriction on the hypothesis representation is imposed because agents will argue about each of these rules independently.
To illustrate how di erent induction algorithms can represent their hypothesis using our formalism, Figure 1 shows the equivalence between a decision tree and a set of rules. In the example, a simple decision tree with only two features (TL and CC) is shown, and three rules equivalent to the tree are constructed.
Further, as we mentioned earlier, when using algorithms such as CN2, that produce an ordered set of rules, the rules produced have to be postprocessed in order to remove the order relationship among them. The left hand side of Figure 2 shows a set of three rules generated by CN2 (plus the default class assigned by CN2 when no rule covers a problem). The center of Figure 2 shows a graphical representation of the way these rules partition the problem space among the three di erent solution classes A, B, and C (the three circles represent the subset of problems that are subsumed by each of the three conditions in the body of the rules: c1, c2 and c3). Notice for instance that rule r2 states that all the problems that are subsumed by c2 have solution B. However, r2 is only considered if r1 is not red. Therefore, that rule is postprocessed and converted into rule r0 , which 2 states that all examples that are subsumed by c2, but not by c1 have solution B. In general, a rule is postprocessed by adding the negations of all the previous rules to its body. Finally, the default solution computed by CN2 is converted also into a rule containing the conjunction of the negation of the body of all the rules generated by CN2. The result of this process is a set of independent rules, which can be used in our framework.
As illustrated by the previous two examples, a large collection of induction algorithms can represent their hypotheses in the form of rules. 2.2
Arguments and Counterarguments In order to use argumentation, two elements must be de ned: the argument language (that de nes the set of arguments that can be generated), and a preference relation (that determines which arguments are stronger than others). In our framework, the argument language is composed of two kinds of arguments: { A rule argument = hA; ri, is an argument generated by an agent :A stating that the rule :r is true. { A counterexample argument = hA; e; i, is an argument generated by an agent :A stating that a particular argument : is incorrect, because the example :e is a counterexample of such argument.
To de ne the relation among arguments, we have to take into account all the possible di erent situations that can arise while comparing two arguments consisting of rules or examples. Figure 3 shows all these situations. The top row of Figure 3 considers all the possible comparisons of two rule arguments, r1 and r2 such that r1:S = r2:S. Only three situations might arise: a) r1 and r2 are totally unrelated, b) the sets of problems covered by r1 and r2 have a non empty intersection, and c) one is more general than the other. The middle row of Figure 3 considers all the possible comparisons of two rule arguments, r1 and r2 but this time r1:S 6= r2:S. The same three situations arise (unrelated, non-empty intersection, and one more general than another). Notice that in the non-empty intersection situation we also require that no rule is more general than another (we don't include the extra restriction in the gure for clarity). Thus, when comparing any two rule arguments, only 6 situations might arise. Situations a), b), c) and d) represent rule arguments that are compatible, whereas situations e) and f) represent con icting arguments. Moreover situation c) is a special situation and we say that r1 subsumes r2.
The third row of Figure 3 shows all the possible situations that arise when comparing a rule argument with a counterexample argument: g) both the counterexample and the rule support the same class (in which case the counterexample is not such, and both arguments endorse each other), h) in which the counterexample, although supporting the same class, is not covered by the rule, i) where the counterexample supports a di erent solution than the rule, and the rule covers the counterexample, j) in which the counterexample, although supporting a di erent class, is not covered by the rule. In our framework, we assume that a counterexample cannot be defeated, and thus only the rule arguments can be defeated. Out of the four situations, the counterexample argument only defeats the rule in situation i), in all the other situations, they are compatible. The counterexample in situation i) is called a defeating counterexample of r1.
Using these two types of arguments and the compatible, con icting, subsumed, and defeated relations among arguments, next section introduces two di erent distributed induction strategies. 3
In this section we will present two strategies, ADI (Argumentation-based Distributed Induction) and RADI (Reduced Argumentation-based Distributed Induction), based on argumentation for distributed induction. Since the strategies involve communication among agents, they will be presented as communication protocols. Both strategies are based on the same idea, and share the same high level structure. 1. A1 and A2 use induction locally with their respective training sets, T1 and
T2, and obtain initial hypotheses H1 and H2 respectively. 2. A1 and A2 argue about H1, obtaining a new H1 derived from H1 that is consistent with both A1 and A2's data. 3. A1 and A2 argue about H2, obtaining a new H2 derived from H2 that is consistent with both A1 and A2's data. 4. A1 and A2 obtain a nal hypothesis H = H1 [ H2 . Remove all the rules that are subsumed by any other rule (situation c) in Figure 3).
Basically, the intuitive idea is the following. In step 1 both agents perform induction individually. Then in steps 2 and 3 (which are symmetric, and can actually be performed in parallel), the agents use argumentation to re ne the individually obtained hypotheses and make them compatible with the data known by both agents. Finally, when both hypothesis are compatible, a nal global hypothesis H is obtained by just computing the union of all the rules learned by both agents, removing all the rules that are subsumed by some other rule (since those would be redundant). Notice that, unless the induction algorithms are not able to learn rules with 100% accuracy in the training set, there should not be any con icting rules in H (at least not con icting in the classi cation of the examples of the training set). However, there might be rules that con ict in the classi cation of problems outside of the training set. If the learning algorithm computes con dence levels for rules, those can be used to arbitrate, otherwise random arbitration can be used. ADI and RADI only di er in the way steps 2 and 3 are performed.
Step 2 in ADI works as follows 1. Let H10 = H1, and t = 0. 2. If there is any rule r 2 H1t that still has not been accepted by A2, then send the argument = hA1; ri to A2. Otherwise, if all the rules in H1t have been accepted the protocol goes to step 5. 3. A2 analyzes :r and tries to nd a counterexample that defeats it (situation i) in Figure 3). If A2 can nd such counterexample e, then A2 sends the counterargument = hA2; e; i to A1. Otherwise, r is accepted and the protocol goes to step 2 again. 4. When A1 receives a counterexample , it appends :e to its training set T1, and updates its hypothesis. If the induction algorithm of A1 is not incremental, then A1 can simply use induction from scratch with the new extended set of examples that includes e. A1 updates the hypothesis obtaining H1t+1.
The protocol goes to step 2 again, and t = t + 1. 5. The protocol returns H1t.
The main idea is that A1 will generate hypotheses according to his local training set T1, and A2 evaluates them, trying to generate counterarguments to the hypotheses that do not agree with his own local data T2. Step 3 in ADI is just the reversed, where it is A2 that generates hypotheses, and A1 that tries to rebut them with counterexamples. One characteristic of ADI is that at each step, only one counterexample is exchanged.
If the induction algorithm of A1 and A2 was capable of achieving 100% accuracy if it was given the complete collection of examples that both A1 and A2 have, then the protocol always ends up converging to a hypothesis that also has 100% accuracy in both T1 and T2. Moreover, in order to prevent in nite iterations in the case of noisy data, the agents are not allowed to send the same counterexample twice during the protocol. This ensures that the protocol will eventually end.
The second strategy, RADI, improves over ADI in trying to minimize the number of times the hypothesis has to be updated while keeping the number of counterexamples exchanged low. Step 2 in RADI works as follows: 1. Let H10 = H1, and t = 0. 2. Let Rt H1t be the set of rules in the hypothesis of A1 not yet accepted by A2. If such set is empty, then the protocol goes to step 5. Otherwise, A1 sends the set of arguments Rt = f = hA1; rijr 2 Rtg to A2. 3. For each 2 Rt, A2 computes the set of examples C in its training set that are counterexamples that defeat :r: C = fe 2 T2j :r:H v e:P ^ :r:S 6= e:Sg. For each argument 2 Rt such that C = ;, :r is accepted by A2. Let It Rt be the subset of arguments for which A2 could nd defeating counterexamples. A2 computes the minimum set of counterexamples Bt such that 8 2It C \ Bt 6= ;. That is the minimum subset of examples that can defeat all arguments in It. A2 sends the set of counterexample arguments Bt consisting of a counterexample argument = hA2; e; i for each pair e, such that e 2 Bt, 2 Rt, and defeats . 4. When A1 receives a set counterexample arguments Bt, it appends all the examples on them to its training set T1, and updates its hypothesis. If the induction algorithm of A1 is not incremental, then A1 can simply use induction from scratch with the new extended set of examples. A1 updates the hypothesis obtaining H1t+1. The protocol goes to step 2 again, and t = t + 1. 5. The protocol returns H1t.
The idea behind RADI is that an example can be a defeating counterexample of more than one rule at the same time, thus, by selecting the minimum set of counterexamples, the number of examples exchanged is reduced. Also, by sending all the counterexample arguments at once, the number of times the hypothesis has to be updated is also reduced. This results in an e cient strategy for distributed induction that minimizes the number of examples being exchanged, and that can be used with any induction algorithm. Notice that nding such minimum subset of counterexamples is NP, however approximate methods to compute such minimum subset can be easily de ned.
Figure 4 illustrates the rst cycle of the RADI protocol. In the gure, agent A1 has learnt a hypothesis H10 from its original training set. A1 sends the set R0 of rule arguments to A2. In the middle part of Figure 4, we can see the training set of A2 (T2). In this example, there are only two classes, + and -. A2 evaluates all the arguments in R0 with his training set T2. In particular, in this example, A2 nds counterexamples for two of the arguments, namely 1 and 2. Thus, the set B0 = f 1; 2g. Then, A2 constructs the set B0 consisting of the minimum set of examples that contain counterexamples for all the arguments in I0. In this case, there is a particular example, e2, which is a counterexample of both arguments, so e2 is enough to contradict both. Therefore, A2 will construct the set of counterarguments B0 = fhA2; e2; 1i; hA2; e2; 3ig, and send it to A1, which will update his hypothesis by appending e2 to its training set T1, and will generate a new updated hypothesis H11, with which the next round of the protocol will start.
As explained in Section 6, it is part of our future work to investigate how the inclusion of additional types of counterarguments, such as rule counterarguments, can further reduce the amount of information exchanged during the distributed induction process. 4
In order to evaluate our approach, we tested the distributed induction strategies
in four di erent data sets: three propositional data sets from the Irvine machine
learning repository (soybean, zoology, cars), and a complex relational data set
(sponges). Moreover, we tested it using three di erent induction algorithms:
ID3, CN2 and INDIE (a relational inductive learner [
Induction
Individual Induction Induction
Union Induction Induction
T1 H1 T1 H1
T2 H2 T2 H2
ADI / RADI Induction Induction
T1 H1 ARGUMENTATION
T2 H2
DAGGER Induction
Induction T1 knowledge, see Section 5 for a brief explanation of DAGGER). Figure 5 presents a visual overview of the di erent strategies used in our evaluation. We evaluated convergence, time, number of examples exchanged, number of rules exchanged, number of induction calls, and both training and test set accuracy. All the results presented are the average of 10 fold cross validation runs.
Since sponge is a relational data set (introduced by Armengol and Plaza [
Table 1 presents the classi cation accuracy (both measured in training set and in test set). We ran each combination of induction algorithm (ID3, CN2, INDIE) with distributed induction strategy (centralized, individual, union, DAGGER, ADI and RADI) with all the data sets (except the combination of INDIEDAGGER, that is not possible, since DAGGER assumes propositional data sets, and INDIE requires them in relational form). In each experimental run the data set was split in two sets, a training set containing 90% of the examples, and a test set containing 10% of the examples. The training set was further split among two agents (except in the case of the centralized strategy, where there was only one agent). Accuracy is measured in the original training set (with 90% of the examples), and also in the remaining 10%, that forms the test set. The left hand side of Table 1 shows accuracy in the training set, and the right hand side shows accuracy in the test set.
Looking at the training accuracy, the rst thing that the experimental results con rm is that the hypotheses learnt by ADI and RADI are indistinguishable in training set accuracy from the one learnt by using centralized induction. Achieving a 100% accuracy all the times where centralized induction also does. When agents perform individual induction, of course, training accuracy diminishes (since agents only learn with 50% of the data in the training set), agents using the union strategy improve their accuracy, but still it is not guaranteed to be as good as that of centralized accuracy (and in the case of CN2, where the order of the rules matter, the accuracy drops drastically). DAGGER shows good accuracy (although not guaranteeing that of centralized induction).
Analyzing test set accuracy, we observe that, except in a few cases where DAGGER achieves higher accuracy (and one where surprisingly union does 3), ADI and RADI achieve same or higher accuracy than the centralized approach. Table 1 shows the highest results for each induction algorithm in boldface (when the di erence was not statistically signi cant, more than one result is highlighted). The explanation is that when agents use ADI or RADI, two di erent hypothesis of the data are learnt (one per agent), and, after inconsistencies are xed, they are merged. Therefore, the resulting hypothesis has potentially several rules that cover the same examples, but that were derived from di erent training sets (thus having di erent biases). This, alleviates over tting, and thus increases classi cation accuracy in unseen problems. The e ect achieved is similar to that of ensemble methods, but with the advantage of having a single hypothesis.
Another e ect that can be seen is that ID3 and CN2 cannot properly handle the complexity of the sponges data set, since, although they can achieve high training set accuracy, the rules they learn do not generalize and achieve very low test set accuracy. INDIE, however, being a relational learner, can handle sponges in its native representation formalism, and thus learn much more general rules, that generalize properly, achieving high test set accuracy.
Classi cation accuracy, however, is only one side of the coin. Table 2 shows
the amount of time used by each of the di erent distributed induction strategies
3 We repeated that experiment several times, with identical result, we are still in the
process of analyzing why union achieves such good result in the cars data set with
ID3.
per agent (averaged over all the data sets and induction algorithms), also the
percentage of the examples owned by each agent that had to be shared, the
number of rules exchanged, and also the number of times that the agents had to
call the base induction algorithm. Notice, that time is dominated by the slower
learning algorithm (CN2) and the most complex data set (sponges), the fastest
algorithm (ID3) required less than a tenth of a second for any strategy except
ADI and RADI (where it still required less than a second for any data set).
Table 2 shows that ADI and RADI, are the most computationally expensive
strategies, ADI taking 155.4 seconds and RADI 18.2, while centralized accuracy
required only 2.8 seconds. Moreover, most of the time consumed by ADI and
RADI corresponds to invocations to the base induction algorithm after receiving
new examples. If an incremental induction algorithm such as ID5R or ITI [
Table 2 shows that among all the distributed induction strategies, DAGGER is the one that requires exchanging the highest percentage of examples, 68.56%, while ADI and RADI exchange only 19.04% and 21.52% respectively. The union strategy, of course, does not force agents to exchange any example. However, ADI and RADI require the exchange of a large amount of rules, where as other strategies, such as DAGGER, or union only require sharing the nal hypothesis. While ADI shares slightly a lower amount of examples, RADI requires only a tenth of the time, a fth of the rules, and a tenth of the number of induction calls.
Summarizing the results, we can conclude that di erent distributed induction strategies have di erent strengths and weaknesses. Performing centralized induction has the problem of having to share all the examples, but achieves a high accuracy at the minimum computational cost. Next in line is DAGGER, which forces the agents to share most of their examples, but achieves a high accuracy also (although not guaranteed to be as high as centralized). On the other extreme, we have the individual and union strategies, that have the minimum computational cost, zero example exchange, but also the lowest classi cation accuracies. ADI and RADI sit in the middle, requiring the agents to share a small percentage of examples (around 20%), while ensuring the same or higher classi cation accuracy than centralized induction (especially in the test set, where they hypotheses learnt by ADI or RADI have less over tting). However, ADI and RADI have a higher computational cost. In between ADI and RADI, we can conclude that RADI is the most well balanced strategy, since it requires about a tenth of the computational cost, while only sharing a very small number of additional examples.
Moreover, notice that nothing stops ADI or RADI from working even if each of the agents had a di erent base induction algorithm. 5
Two areas of work are related to ours, namely distributed induction and incremental learning. Distributed induction has been attempted mainly from four di erent approaches: computing statistics in a distributed fashion and then aggregating, sharing example, sharing hypotheses or viewing induction as search and distributing the search process. Let us present examples of each of the approaches.
Caragea et al. [
A di erent approach is DAGGER, presented by Davies [
Another approach to distributed induction is that of Shaw and Sikora [
Another example of distributing induction for e ciency is that of
distributing the search process of nding rules among a series of distributed processors.
Provost and Hennessy [
Also related is the work on incremental learning, such as the incremental
versions of the ID3 algorithm ID4 and IdD4 by Schlimmer and Fisher [
Finally, the argumentation framework presented in this paper is
complementary to that introduced in [
In this paper we have introduced two di erent distributed induction strategies, ADI and RADI, that can be used on top of any induction algorithm capable of learning hypotheses that can be represented using an independent set of rules. ADI and RADI ensure that the hypothesis learnt will be undistinguishable in terms of training set accuracy from that produced by the base induction algorithm when learning from all the data. The main idea behind ADI and RADI is to let each agent perform induction individually, then argue about the learnt hypotheses to remove inconsistencies, and nally merge both hypotheses.
Experimental results show that, in addition to achieve the same training set accuracy than a centralized method, ADI and RADI have the advantage of obtaining hypotheses that are less prone to over tting, and thus achieve higher test set accuracy. Moreover, ADI and RADI require sharing only about 20% of the examples of each agent in order to converge to the common hypothesis. ADI and RADI also require that the agents perform several calls to the base induction algorithm, and thus are better suited to be paired with incremental learning algorithms (but this is not required).
ADI and RADI use counterexamples as the only form of counterargument.
However, we plan to investigate more complex argumentation protocols that let
agents use rule also as counterarguments. The problem of that, is that the base
learning algorithms would have to be modi ed to be able to take rules into
account, in addition to the examples in the training set. This is related to the
research in \argument based machine learning" by Mozina et al. [
Acknowledgements Support for this work came from the project MID-CBR TIN200615140-C03-01.