Arguing from experience using multiple groups of agents

1.Introduction

Arguing from Experience was introduced in Wardeh, Bench-Capon, and Coenen (2008a) to provide a computational model of argument based on inductive reasoning from past experience. The model allows participants to draw directly from past examples to find reasons for coming to a view on some current example (case), without the need to analyse this experience into rules and rule priorities. Such reasoning can be found in informal everyday arguments, where we often make use of our (personal) experience when conversing with other people, by observing certain regularities in this experience, and then employing these regularities to back up what is being said. To model this, instead of drawing rules from a knowledge base, we construct our arguments on the fly using association rule mining (ARM) techniques (Coenen, Leng, and Ahmed 2004; Wardeh, Bench-Capon, and Coenen 2007).

The setting in which we explore this approach is a debate about how to classify an example, the identified associations then provide reasons for and against particular classifications. This form of argument differs from the more common style of arguments (Prakken 2006) generated from a knowledge base. In those arguments, the existence of a theory in the form of a collection of rules is presupposed. In systems based on knowledge bases, persuasion occurs through one participant telling the other(s) something previously unknown, either a fact or a rule: in arguing from experience, opinions on rules differ in respect of confidence, and the participants try to find a rule they both can accept on the basis of their different experience.

Argument from experience has several advantages:

In the context of previous work, the PADUA Protocol (Wardeh et al. 2008a) allowed two agents to dispute a binary classification. This was extended in Wardeh, Bench-Capon, and Coenen (2009a) to the PISA Framework to allow more than two participants to engage in the dialogue, and so support argument about problems with a range of classifications, with each participant championing a different possibility. In this paper, we present a more flexible version of the protocol, implemented in an extension to PISA, to allow groups of agents to argue for a classification. It is conjectured that groups of agents collaborating to produce some result will be more effective than if the agents were operating in isolation. Agents advocating the same or a similar thesis can confer and jointly select which arguments to put forward. This extension raises a number of issues:

For the first question, we suggest that such agents should form what we term a group of participants and make a single move rather than acting independently for the same position; our answers to the other two questions will be given later in the paper.

The rest of this paper is organised as follows. In Section 2, a summary of the PISA framework is given. The notion of strategy in PISA is introduced in Section 3. In Section 4, we explain the process by which agents can join forces and argue as a group (team) in PISA. Section 5 provides a detailed example of the process described in the previous section. In Section 6, we present the results of a series of experiments which we have performed to explore the operation of PISA with groups to determine whether groups improve the quality of the classifications. Section 7 provides some comparison with related previous work. Finally we conclude with a summary of the main points and some future directions.

2.PISA framework for arguing from experience

As described in Wardeh et al. (2009a), PISA concerns dialogues where there is a range of options (classes) for classification, and each of the participants is the advocate of one of these options. In order to accommodate situations where there are more agents than opinions, the extensions presented here will enable the agents to act in groups (Section 4), one group for each opinion. PISA dialogues are open: participants may enter or leave when they wish. For turn taking, a structure with rounds is adopted, rather than a linear structure where a given agent is selected as the next speaker (e.g. the turn taking protocol in Bel-Enguix and Lopez (2006) where the current speaker chooses who will speak next). In each round, any participant who can make a legal move may do so. There is no limitation on the number of parties that can participate in any round but, to simplify the game, each participant is limited to one move per round. This turn taking policy allows participants to place their attacks/counter attacks as soon as they become appropriate, without the need to wait for a turn to contribute. This is not perhaps the most usual structure for human meetings, but it can be found in some board games such as Diplomacy, which also has the feature of a many player game in which every player is the opponent of every other player.

It is suggested that the structure is particularly appropriate in order to achieve fairness in the situations where every participant is playing for themselves, and has to regard every other participant as an opponent. The game terminates when no participant makes a contribution for two rounds (to ensure that they have really finished and not withheld a move for tactical reasons) or after some limiting number of rounds have been played: thus the termination of the game is guaranteed. The model is essentially that of a facilitated discussion, with the chairperson acting as the facilitator. The realisation of this model and the choices summarised above are considered in the following sub-sections.

3.Strategy model for PISA

The interaction of arguments in PISA is viewed as a form of argumentation dialogue game McBurney and Parsons 2002. This section is concerned with the strategy11 problem in PISA: choosing the best move among the set of possible moves available to each participant agent at each round of the PISA dialogues. The outline of PISA strategy problem is as follows: each agent must select (i) the kind of move to be presented in the dialogue; (ii) the particular content of the move; and, most importantly, (iii) an opponent to direct this move against. We think that the notion of speech acts and content selection in PISA is best captured at different levels, as suggested in Moore (1993). A six-level strategy model was therefore designed for individual player agents taking part in PISA dialogues. The proposed six levels are divided into two tiers. The lower tier encapsulates the basic strategy model, while the upper tier determines how PISA players use the argumentation tree in selecting their moves. The proposed strategy model works as explained below.

The lower tier comprises a four-level layered strategy model:

The upper tier identifies the manner by which PISA participant agents infer what move to play next from the current status of the argumentation tree. This tier comprises two strategy levels:

Level U1 of the layered strategy has three different modes for deducing the next moves from the current status of the argumentation trees:

Recall from Section 2 that a strategy function Play _a was identified for each PISA participant agent (a∈A). The details of this function are as follows:

A number of different strategies can be derived from the two-tier strategy model discussed above according to the values given to each of the parameters of S_a using the above strategy function. Three basic strategies were derived from the given model in relation to level U2 from the upper tier, from which a number of sub-strategies can be derived. Note that strategies are numbered from S1 to SN, and where appropriate sub-strategies of a strategy are indicated using SK-M, for example S1-1, and so on. Table 3 provides a summary of these strategies and sub-strategies. The table gives the strategy identifier (column 1) and where appropriate the root strategy (column 2); columns 3 and 4 provide the tree inference (Level U1) and strategy modes (respectively). The last column presents the ranking of each strategy: strategies are ranked from one downwards, with one being considered the smartest strategy. The significance of the rankings will be clarified in Section 4. The strategies are discussed in more detail below.

(S1) Attack whenever possible strategy: PISA participant agents may adopt this strategy to enhance their chances of winning the game by being as aggressive as possible: they attack whenever they can do so with a legal move. Three sub-strategies are derived from the attack whenever possible strategy according the modes of U1 identified above. Each mode will use a different process to identify its opponents:

(S2) Attack only when needed strategy: Here, participants attack their opponents only when all their proposed arguments so far have been successfully attacked, or when their attempts to undermine all the other participants have failed. S2 is further divided into six sub-strategies (S2-1-1, S2-1-2, S2-2-1, S2-2-2, S2-3-1, and S2-3-2), corresponding to the variants proposed for S1 (see above).

(S3) Attack to prevent forecasted threat strategy: S3 anticipates forthcoming attacks against the participant's existing proposals; thus it is the most sophisticated strategy type in PISA. Here agents deduce their best next moves based on the entire argumentation tree and use their own heuristics trying to calculate which of their previous moves may be the weakest link in their argument, and then either propose new rules to strengthen their position, or attack the positions of other participants before they have the chance to attack them.

4.Arguing in groups

Having introduced the PISA framework for multiparty arguing from experience, the process whereby PISA agents can collaborate together to jointly produce their arguments can be considered. In the extended variant of PISA described here, where there are more agents than opinions, individual participant agents advocating the same thesis (e.g. the same possible classification) are required to join forces and act as a single group of participants. Each group then acts as a single participant. This notion of groups prevents individual players sharing the same objective from arguing without consulting each other and consequently causing contradictions among themselves or attacking each other. Group formation in PISA is a straightforward process: before the start of a new dialogue, all participants advocating the same thesis (classification) are required to form a group of participants. This also applies to new agents joining an ongoing dialogue. In each group, one member is selected to be the leader of the group who is usually the smartest and most experienced member of the group. A player's smartness relates to its strategy. Hence, the smartest member is the one with the most sophisticated strategy among the group's members, where strategies are ranked according to their level of understanding of the history and the process of the dialogue. The leader guides the inter-group dialogue, and selects which of the moves suggested by the group's members to play in the next round. This inter-group dialogue is a variation of targeted broadcasting where only group members can listen to what is being discussed. The leader can also redirect other members’ moves against different opponents, or advise them to follow its own strategy. This allows the group to benefit from the different moves suggested by its members according to their different strategies and based on their different experiences.

5.Example

One motivation for group formation in PISA is that agents advocating the same opinion should not attack each other. Another motivation is that the overall performance of PISA could benefit from dividing the same collection of data available to one agent between a reasonable number of agents forming a group arguing for the same opinion as the original agent. The idea is that the operation of the group would allow its members to jointly produce better arguments than would be the case if one agent used all the group's experience. This section illustrates this notion of groups by the means of an example using an artificial data set representing a fictional housing benefit scenario. This scenario concerns a fictional benefit, Retired Persons Housing Allowance (RPHA) (as previously used in Bench-Capon (1993) and Mozina, Zabkar, Bench-Capon, and Bratko (2005)), which is payable to a person who is of an age appropriate to retirement, whose housing costs exceed one-fifth of their available income, and whose capital is inadequate to meet their housing costs (established as less than £3000). Such persons should also be resident in the country, or absent only by virtue of service to the nation, and should have an established connection with the UK labour force. The scenario was interpreted in such a way that four classes could be identified:

In our experiment, we assume four different benefit offices providing RPHA in four different regions, each with a data set of 1500 benefit records. Each data set is assigned to a PISA participant agent. Thus a total of four participant agents engage in dialogues regarding the classification of RPHA claims, each agent defending one of the above four classifications. The support and confidence thresholds were set to 1% and 50%, respectively (the default thresholds in the data mining community). Given the specific new case of a female applicant, aged 78 years, who is a UK resident whose capital and income fall in the right range (≤ £ 2000 and ≤15%, respectively), and who has paid contributions in 4 out of the last 5 years them, according to the above listed conditions listed, the case should be classified as entitled with priority.

In one of the executions, the dialogue proceeds as illustrated by the argument tree presented in Figure 1(a). The diagram features four agents labelled PR (priority entitled), EN (entitled), PE (partially entitled) and NE (not entitled) who all apply the same focused build attack when possible strategy (S1-1-1). The diagram should be viewed in conjunction with Table 4 which presents the dialogue, and gives the premises and conclusions of the various rules put forward. The dialogue commences when the chairperson invites EN to propose the opening argument, EN proposes R1. R1 is then attacked by the other three agents in the second round (R2, R3, and R4). At the end of round 2, PE is ahead as it has the best un-attacked rule. In round three, PE proposes a counter rule against NE's previous rule (R5), EN proposes a new rule (R6) to attack the current best rule (R3) and NE distinguishes PE's argument (R7). Thus PE maintains its lead. Note that PR has not contributed to round three.

Figure 1.

The argumentation tree for the example presented in Section 5: (a) four individual participant agents; (b) three individual agents and one group (PR).

In round four: NE distinguishes PE's rule from round three (R8), PR proposes a counter rule against PE's rule of round three (R9), PE increases the confidence of its previous move (R3) by playing R10 and EN proposes a new rule R11. Now PR is winning, but in the fifth round its winning rule (R10) can be distinguished by NE (R12). Additionally, both EN and PE have moves in this round (R13 and R14, respectively). PR however can increase the confidence in its previous move (R4) by playing R15, but the resulting rule does not have enough confidence to maintain PR's lead. In the sixth round, NE distinguishes PE's argument (R13) using R16, PR distinguishes R13 using R17, and EN and PE play new rules (R18 and R19, respectively). No more arguments are now possible, and so the final classification is that the candidate should be entitled to normal rather than priority benefit, which is the wrong classification.

Let us now assume that the data available to the office arguing that the case should classify as priority entitled are divided between four PISA Participant Agents as follows: P1 (25%), P2 (15%), P3 (35%), and P4 (25%), and that these agents form a group with P3 being the most experienced agent. Let us also assume that P1 and P2 apply a build strategy (S1-1-1) and that P1 is selected as the GL. P3 and P4 apply a destroy strategy (S1-1-2). The new dialogue commences in the same manner as the previous one, and EN proposes the same rule R1 as before. In round two, the other three agents attack R1; EN and PE play the same moves they have used in the previous example (R2 and R3). PR however attacks using a different rule (Figure 1(b)). Both Leader and P2 propose a counter rule against EN's move from round one, while P3 and P4 suggest distinguishing this move. GL chooses its own move, as it has the highest confidence and consequently plays R4′22:

In round three, PE, EN, and NE play the same moves as before (R5′, R6, and R7, respectively). However, here PE directs its move against PR's previous move (R4′). In round 4, NE and PE play the same moves (R8 and R10) as before; EN also has the same move (R11′), but here it is directed against NE's move from round two (R2). In the PR group, participants P2 and P4 have no moves, the leader suggests a counter move against PE but it cannot be played (has confidence of 61.83% only), and P3 suggests distinguishing PE's move from the last round (R6). GL, however requests the following from P3:

P3 succeeds in mining the requested move, and GL puts forward the resulting move (R9′):

In round five, NE PE and EN play the same moves as before (R12, R13 and R14, respectively). In the group PR, a similar decision to the previous round is taken, and the leader puts forward the move requested from P3:

Finally, in round six, all participants make moves:

No more arguments are possible at this stage, and so the final classification is that the candidate should classify as priority entitled. Note that the right class emerged as a result of PR being a group of four agents, and even though each agent individually had less data than the first example; collectively they were able to generate better arguments.

6.Experimental evaluation

The effectiveness of Arguing from Experience has been demonstrated through a number of experiments reported in previous papers (e.g. PADUA was evaluated in Wardeh, Bench-Capon, and Coenen (2008b)). PISA was first evaluated in Wardeh et al. (2009a), in which it was shown that PISA also performed better than, or as well as, its competitors. The particular benefits of Arguing from experience for classification were, however, shown most clearly in Wardeh, Bench-Capon, and Coenen (2009b), where PISA was shown to produce robust results even when the data sets of the included agents were infected with different levels of noise (up to 50%).

In this section, we empirically evaluate the proposed extension to the PISA framework for argumentation-based classification using groups. The evaluation comprises a number of experiments designed to test the hypothesis that argumentation-based classification using groups improves the quality of the resulting predictions compared with other methods such as decision trees or ensemble paradigms. Moreover, we also conjecture that the improved accuracy achieved will increase as the number of agents supporting each possible classification increases. Four categories of experiments were conducted to investigate both the application of the extended version of PISA (with groups) as a classifier and the operation of the group concept in general. The four categories of experiment may be itemised as follows:

These experiments are discussed in detail in the following four subsections.

6.1.Effectiveness of groups in argumentation

The first set of experiments applied PISA to a number of real-world data sets taken from the UCI Repository of machine learning databases Blake and Merz (1998), selected to cover a wide variety of domains. Two experimental setups were used. In the first, each data set was equally divided among a number of participant agents equal to the number of possible classes in each data set; while in the second, PISA was run using a number of groups (equal to the number of possible classes in each data set), each comprising four participant agents. Figure 2 show the classification accuracies (The percentage of correctly classified cases) of ten cross validation (TCV) tests, applied using PISA with and without groups. These results are compared against those of C4.5 (Quinlan 1993) and Bagging (Brieman 1996). The results indicate that PISA performs consistently well (producing high accuracy with most of the data sets), often outperforming the other two classification paradigms included in the experiment; and giving comparable results to the decision tree methods, which are particularly well suited to data sets such as the nursery data set. The results demonstrate that PISA tends to perform better using groups than individual agents: it seems that the greater the number of separate databases (group size) the greater the number of arguments found, enabling a more thorough exploration of the problem. Note that the only data set where the accuracy of the predictions generated using PISA with groups is worse than all the other paradigms is the relatively small Pima data set, where each participant could be assigned only 96 records.

Figure 2.

Results of TCV tests using the same number of players per group using UCI repository data sets.

6.2.Group size

In the second set of experiments, PISA was applied to a number of variation of the artificial housing benefits data sets (introduced in Section 5). The objective was to investigate the operation of groups within PISA with respect to group size. This experiment assumed that the amount of data available to each PISA group was fixed and equally divided among its members, similar to an ensemble-like approach to classification (Brieman 1996). Thus, if too many players were assigned to a single group, each will be assigned a very small data set and the members would not be able to mine adequate rules. Five sets of TCV tests were carried out using the housing benefits data set. PISA was run using four groups comprising (respectively) 2, 4, 6, 8, and 10 (participant) agents each, each group corresponding to one of the possible four classes in the data set. In each test, the original data set was divided equally among the players. Figure 3(a) presents the results of these tests, which indicate that, in general, PISA operates better when using groups of players. More than one agent advocating the same classification, using the notion of groups, seems to have positive effects on the accuracy of the resulting dialogues, due to the fact that a range of arguments can be mined from the different data sets, each presenting different experience. Thus more options will be available to the group as a whole, from which the group's leader can select the best course of action. However, the increase in accuracy is relative to the amount of data given to each agent in the dialogues. If the data is not sufficient to mine adequate ARs, the operation of PISA will not benefit from dividing the data any further. Thus, for a fixed amount of data, performance begins to degrade if there are too many players in the group (i.e. the data available to each individual gets too small).

Figure 3.

Relation between number of players and PISA accuracy when players are given fixed amount of data. (a) Results of the TCV tests using the same number of agents per group. Error bars represent the standard deviation. (b) Results of the TCV tests using same number of players per group. Error bars represent the standard deviation.

7.Related work

Concerning the automatic generation of arguments from collections of previous examples, the work in Governatori and Stranieri (2001) investigates the feasibility of knowledge discovery and data mining in order to facilitate the discovery of defeasible rules for legal decision-making. Arguing from experience presents an approach to argumentation related to that of Governatori and Stranieri (2001) and bridges the gaps in their proposal (e.g. their technique can operate only on small data sets). More importantly, PISA offers a more efficient means to exploit databases for the production of arguments.

In Ontañon and Plaza (2008), an argumentation framework for learning agents is articulated. This framework has similarities with the one proposed here in that it takes the experience, in the form of past cases, of agents into consideration. However, the work in Ontañon and Plaza (2008) uses Case-Based reasoning techniques to generate arguments from past examples and provides a means to define the preference relation between the generated arguments. PISA, on the other hand, implements a more straightforward ARM techniques to produce arguments and applies a preference relation based upon the support/confidence measures. Ontañon and Plaza (2008) also presented a framework for multiparty argumentation to enable a committee of agents to jointly deliberate about given cases. However, unlike PISA, the communication between the arguing agents is direct (there is no mediator agent).

An earlier example of un-mediated multi party argumentation can be found in Tambe and Jung (1999)), where turn taking is tokenised. The protocol consists of a series of rounds. In the initial round, the agents state their individual predictions of the discussed case, and broadcast these predictions to the involved agents. Then, in the subsequent rounds, a token passing mechanism enables agents (one at a time) to attack other agents (also one at a time) if they disagree with their prediction. When an agent receives an attack, it informs the attacker whether it accepts the counterargument (and changes its prediction) or not. Also, when an agent has the token, it can answer to such attacks by generating the counter attacks. When all the agents have had the token once, the token returns to the first agent, and so on. The communication between the agents continues in the same manner until they all agree on a prediction, or if a given number of rounds has passed and no agent has generated any counterargument. Moreover, if – at the end of the argumentation – the agents have not reached an agreement, then a voting mechanism that uses the confidence of each prediction as weights is used to decide the final solution. PISA differs in that it relies on an argumentation artefact (the argumentation tree), and mediator agent (the chairperson) to facilitate the argumentation process between a number of agents. Thus, PISA agents focus on generating the best arguments rather than on the communication among themselves. Additionally, instead of voting, PISA applies a tie-resolution mechanism where agreement cannot be reached in a given number of rounds.

Some work has also been done regarding n-person argumentation games. Pham, Thakur, and Governatori (2008) presents a defeasible logic approach to address situations requiring agents to settle on a common goal despite the fact that their agendas may contain conflicting goals. This group of agents applies the majority rule to identify the “most common” claim. This approach is argued to simplify the complexity of n-person argumentation games into two-group games: one supports the major claim, the other opposing it. PISA, on the other hand, addresses situations where there is no “major claim”, but rather each participant has its own claim, and the situation requires consideration of each of these claims as legitimate stand-alone claims.

Teamwork has been the focus of much research in the fields of distributed AI and multi agent systems. Horling and Lesser (2005) identifies an agent team as consisting of a number of cooperative agents which have agreed to work together towards a common goal. Additionally, teams attempt to maximise the utility of the team (goal) itself, rather than that of the individual members. Thus, the notion of groups in PISA can be likened to teamwork: the group members share the common goal of establishing their mutual point of view. Within a team, each agent will take on one or more roles as needed to address the subtasks required by the team goal. The roles may change over time in response to planned or unplanned events, while the high-level goal itself usually remains relatively consistent. In PISA groups, there are only two roles: team leader and regular member. The leader role can shift to new members if they have a better strategy or more experience than the current leader. Thus it is a dynamic role. A similar notion of leadership can be found in literature (Klusch and Gerber 2001; Bai and Zhang 2005) in which the leading agent acts as a representative and intermediary for the group as a whole.

In Dignum, DuninKeplicz, and Verbrugge (2001), a four-stage formal model of teamwork is presented. The first stage is potential recognition in which the agent that takes the initiative tries to find out which agents are potential candidates for achieving a given overall goal and how these can be combined in a team. The second stage is team formation to construct the team that will try to achieve the goal. The third stage is plan formation. Here the team divides the goal into subtasks, associates these with actions and allocates these actions to team members. The last stage is plan execution in which the team members execute the allocated actions and monitor the appropriate colleagues. The first stage is straightforward in PISA, because the chairperson assign participants to groups (teams) according to their goals. Thus, the agents need not to carry these tasks themselves. Additionally, group formation in PISA is a clear-cut process when compared with the work on team formation in the literature (a survey of which can be found in Horling and Lesser (2005)). This is mainly because PISA groups members aim at achieving one task: mining the best possible argument in the context of the ongoing dialogue, according to their strategy and experience. The in-group dialogue process presented in this paper falls under the last two stages. Again the task in PISA is relatively simple and homogeneous: the group members attempt to generate the best possible argument, from their individual sets of experience, and then apply this argument in the best way in the current dialogue, whereas teams more generally are seen as undertaking much more complex and varied tasks, and may even require different abilities from different team members.

Finally, some work on the use of argumentation to facilitate classification can be found in the literature. Amgoud and Serrurier (2008) propose a formal argumentation framework for classification, in which arguments can be constructed for and against each possible classification of a given example. Similar to PISA, these arguments can then be evaluated and a plausible classification of the example suggested. However, the work in Amgoud and Serrurier (2008) assumes that a set of hypothesis is associated with the learning examples, whereas PISA has no such assumption. Additionally, the strength of each argument is identified such that the arguments coming from the set of training examples are stronger than arguments built from the set of hypotheses, whereas PISA applies support/confidence measures (Agrawal et al. 1993) to evaluate the strength of the generated arguments. Moreover, the work in Amgoud and Serrurier (2008) only focuses on the single agent situation.

Other work has tried to improve the performance of classification methods by combining them with argumentation techniques. In Mozina et al. (2005), the idea of augmented examples is introduced to improve the results of one machine learning technique CN2 (Clark and Niblett 1989). However, their approach requires consulting an expert, who decides on the right class labels for misclassified cases. The expert also generates the arguments associated with such cases, so as to drive a refinement process. Their approach has a single learning agent, and a human expert to explain misclassifications. Additionally, their argumentation process involves two options only, while PISA can handle any number of options. In Ontañon and Plaza (2010), the concept of learning from communication was introduced to show that the accuracy of the learning process can benefit from communication (via argumentation) among a number of agents.

8.Conclusions and future directions

We have provided a mechanism by which any number of agents can participate in a dialogue to decide how a case should be classified using arguments mined (on the fly) from their individual data sets. The agents form groups of agents supporting each possible classification and these groups collaborate to decide on the best next move. Using groups can improve the quality of the classification, even when the data are simply divided among different agents (i.e. no more additional data made available) over the situation where each classification was supported by a single agent. Our experiments suggest that for any given problem there is an optimal size for the agent's data sets, and allowing the available data to be divided among agents in this way ensures that the available data can be deployed to the best effect, whatever be its size. Further experiments show that more data improve the quality of classification provided that the data can be deployed in optimally sized chunks. In future work, it would be interesting to explore dynamic groups, whereby agents that become convinced of a different classification can join the appropriate group rather than leaving the game. Also we intend to explore the effect of coalitions whereby two groups can temporarily join forces against a currently stronger adversary.