Coenen / Bramer / Petridis Research and Development in Intelligent Systems XXV

Proceedings of AI-2008, The Twenty-eighth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence
1. Auflage 2010
ISBN: 978-1-84882-171-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 372 Seiten

The papers in this volume are the refereed technical papers presented at AI-2008, the Twenty-eighth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence, held in Cambridge in December 2008. They present new and innovative developments in the field, divided into sections on CBR and Classification, AI Techniques, Argumentation and Negotiation, Intelligent Systems, From Machine Learning To E-Learning and Decision Making. The volume also includes the text of short papers presented as posters at the conference. This is the twenty-fifth volume in the Research and Development series. The series is essential reading for those who wish to keep up to date with developments in this important field. The Application Stream papers are published as a companion volume under the title Applications and Innovations in Intelligent Systems XVI.

Autoren/Hrsg.

Bramer, Max

Coenen, Frans

Petridis, Miltos

Inhaltsverzeichnis

1;TECHNICAL PROGRAMME CHAIR’S INTRODUCTION;5
2;ACKNOWLEDGEMENTS;6
3;TECHNICAL EXECUTIVE PROGRAMME COMMITTEE;7
4;TECHNICAL PROGRAMME COMMITTEE;8
5;Table of contents ;10
6;BEST TECHNICAL PAPER;13
6.1;On the Classification Performance of TAN and General Bayesian Networks;14
6.1.1;1 Introduction;14
6.1.2;2 Bayesian Networks and Classification;15
6.1.2.1;2.1 Inductive Learning of Bayesian Networks;15
6.1.2.1.1;2.1.1 K2 Search with BDeu Scoring Approach;16
6.1.2.1.2;2.1.2 MDL Scoring Approach;17
6.1.2.1.3;2.1.3 Classification using a GBN;18
6.1.2.2;2.2 Restricted Bayesian Classifiers;18
6.1.2.3;2.3 Parameter Estimation;19
6.1.3;3 Experiments;20
6.1.3.1;3.1 Methodology;20
6.1.3.2;3.2 Results;21
6.1.3.3;3.3 Discussion of Results;23
6.1.4;4 Conclusions: Suitability of GBN as a Classifier;24
6.1.5;Acknowledgements;26
6.1.6;References;26
7;CBR AND CLASSIFICATION;28
7.1;Code Tagging and Similarity-based Retrieval with myCBR;29
7.1.1;1 A Programmer’s Dilemma;29
7.1.2;2 Related Work;31
7.1.3;3 Tag Retrieval from a CBR Perspective;32
7.1.4;4 coTag Architecture;34
7.1.4.1;4.1 Back End: Accessing myCBR;35
7.1.4.2;4.2 Front End: Tagging, Searching, and Similarity Modelling;36
7.1.4.2.1;4.2.1 Case Acquisition;36
7.1.4.2.2;4.2.2 Query Specification;37
7.1.4.2.3;4.2.3 Retrieval Results;38
7.1.4.2.4;4.2.4 Similarity Explanation and Customisation;39
7.1.5;5 First evaluation results;40
7.1.6;6 Looking Forward;41
7.1.7;References;42
7.2;Sparse Representations for Pattern Classification using Learned Dictionaries;43
7.2.1;1 Introduction;43
7.2.1.1;1.1 Sparse Coding of Signals;44
7.2.1.2;1.2 Template Matching;45
7.2.1.3;1.3 Proposed Classification Framework;47
7.2.2;2 Simultaneous Approximations;48
7.2.3;3 K-SVD Algorithm;48
7.2.4;4 Proposed Algorithm for Template Generation;49
7.2.4.1;4.1 Probability Source Model;50
7.2.4.2;4.2 Representation Step;50
7.2.4.3;4.3 Dictionary Update Step;51
7.2.4.4;4.4 Statistical Template Generation and Classification;51
7.2.5;5 Simulations;52
7.2.6;6 Conclusions;54
7.2.7;References;54
7.3;Qualitative Hidden Markov Models for Classifying Gene Expression Data;56
7.3.1;1 Introduction and Motivation;56
7.3.2;2 Hidden Markov Models;58
7.3.3;3 Order of Magnitude of Probabilities: the Kappa Calculus;59
7.3.3.1;3.1 Properties;59
7.3.4;4 A Qualitative HMM;60
7.3.4.1;4.1 Semantics;60
7.3.4.2;4.2 Independence Assumptions;61
7.3.4.3;4.3 Additional Properties;62
7.3.5;5 Evaluating Observed Output;62
7.3.5.1;5.1 The Evaluation Problem;62
7.3.5.2;5.2 Problem Reformulation;63
7.3.5.3;5.3 The Qualitative Forward Algorithm;63
7.3.6;6 A Qualitative HMM for Gene Expression Data;65
7.3.6.1;6.1 The Problem;65
7.3.6.2;6.2 Aim;66
7.3.6.3;6.3 The Structure of the HMM;66
7.3.6.4;6.4 Data Set;67
7.3.6.5;6.5 Obtaining HMM.;67
7.3.6.6;6.6 Experiment and Analysis;67
7.3.7;7 Conclusion and Future Work;68
7.3.8;References;68
7.4;Description Identification and the Consistency Problem;70
7.4.1;1 Introduction;70
7.4.2;2 The Description-Identification Problem;71
7.4.3;3 Version Spaces;73
7.4.4;4 The Boundary-Set Approach;74
7.4.5;5 The Consistency-Test Approach;76
7.4.6;6 Consistency Algorithms for Lower-Bounded Description Spaces;77
7.4.6.1;6.1 Definition of Lower-Bounded Description Spaces;78
7.4.6.2;6.2 Applicability Conditions of the Consistency Algorithms;79
7.4.6.3;6.3 Consistency Algorithms;80
7.4.6.4;6.4 Complexity Analysis;82
7.4.6.5;6.5 Consistency Algorithms for Upper-Bounded Description Spaces;82
7.4.7;7 Conclusion;83
7.4.8;References;83
8;AI TECHNIQUES;84
8.1;Analysing the Effect of Demand Uncertainty in Dynamic Pricing with EAs;85
8.1.1;1 Introduction;85
8.1.2;2 A Mathematical Model of Dynamic Pricing;87
8.1.3;3 Optimising Stochastic DP models using EAs;89
8.1.4;4 Experiments and Results;91
8.1.4.1;4.1 Results;93
8.1.5;5 Conclusion;97
8.1.6;References;97
8.2;Restart-Based Genetic Algorithm for the Quadratic Assignment Problem;99
8.2.1;1 Introduction;99
8.2.2;2 Preliminaries and General Aspects;100
8.2.3;3 Implementation of the Restart-Based Genetic Algorithm for the QAP;102
8.2.3.1;3.1 Tabu search procedure;105
8.2.3.2;3.2 Mutation procedure;107
8.2.4;4 Computational Experiments;109
8.2.5;5 Concluding Remarks;111
8.2.6;References;111
9;CONSTRAINT SATISFACTION AND FIXES: REVISITING SISYPHUS VT;113
9.1;On a Control Parameter Free Optimization Algorithm;127
9.1.1;1 Introduction;127
9.1.2;2 SASS2;128
9.1.2.1;2.1 Effect of Step Size s on Hill-Climbing;128
9.1.2.2;2.2 Basic SASS;130
9.1.2.3;2.3 Stopping Criterion;133
9.1.2.4;2.4 Population Size;135
9.1.2.5;2.5 SASS2 Algorithm;137
9.1.3;3 Conclusion;138
9.1.4;References;138
9.2;1 Introduction;113
9.3;2 The VT problem and VT Sisyphus-II Challenge;114
9.3.1;2.1 VT Problem;114
9.3.2;2.2 An Overview of Constraint Satisfaction Techniques;114
9.3.3;2.3 ECLiPSe - Constraint Logic Programming System;115
9.4;3 An Overview of Structure;116
9.4.1;3.1 Initial Structure of ExtrAKTor Generated Code;116
9.4.2;3.2 ExtrAKTor Structure Summary;117
9.5;4 Investigating the Sisyphus-VT Solution Space;118
9.5.1;4.1 Constraint Types for Relaxation;118
9.5.2;4.2 Early Performance Issue;118
9.5.3;4.3 Performance Enhancement - “domain” & “infers most”;119
9.5.3.1;4.3.1 Domain Declaration;119
9.5.3.2;4.3.2 Tuple Declaration;120
9.5.3.3;4.3.3 Domain Assignment;120
9.5.3.4;4.3.4 Infers Most;120
9.5.3.5;4.3.5 Final Code Structure;120
9.5.3.6;4.3.6 Summary;121
9.5.4;4.4 ExtrAKTor Upgrade;121
9.5.4.1;4.4.1 Summary;121
9.6;5 Experimentation - Exploring The VT Solution Space;122
9.7;6 Discussion of Related Work;123
9.7.1;6.1 Comparison with VITAL Results;123
9.7.2;6.2 Future Work;124
9.7.3;6.3 Conclusion;125
9.7.4;Acknowledgments;126
9.7.5;References;126
10;ARGUMENTATION AND NEGOTIATION;139
10.1;PISA - Pooling Information from Several Agents: Multiplayer Argumentation from Experience;140
10.1.1;1 Introduction;140
10.1.2;2 Need for Multiparty Dialogue;141
10.1.3;3 Arguing from Experience;143
10.1.4;4 PADUA Protocol;145
10.1.5;5 PISA;146
10.1.5.1;5.1 Control Structure;147
10.1.5.2;5.2 Turn Taking Policy;148
10.1.5.3;5.3 Game Termination;149
10.1.5.4;5.4 Roles of the Players;150
10.1.5.5;5.5 Argumentation Tree;150
10.1.5.6;5.6 Winner Announcement;152
10.1.6;6 Conclusions;152
10.1.7;References;153
10.2;Agent-Based Negotiation in Uncertain Environments;154
10.2.1;1 Introduction;154
10.2.2;2 Communication Model;155
10.2.3;3 Contract Acceptance;157
10.2.4;4 The Scenario;159
10.2.5;5 The Buyer Assesses A Contract;160
10.2.6;5 The Buyer Assesses A Contract;160
10.2.7;6 The Seller Models the Buyer;162
10.2.8;7 Strategies;163
10.2.9;8 Discussion;166
10.2.10;References;167
10.3;Automated Bilateral Negotiation and Bargaining Impasse;168
10.3.1;1 Introduction;168
10.3.2;2 Pre-Negotiation;170
10.3.3;3 Actual Negotiation;171
10.3.3.1;3.1 Equilibrium Strategies;172
10.3.4;4 Bargaining Impasse;178
10.3.5;5 Related Work;180
10.3.6;6 Conclusion;181
10.3.7;References;181
11;INTELLIGENT SYSTEMS;182
11.1;Exploring Design Space For An Integrated Intelligent System;183
11.1.1;1 Introduction;183
11.1.2;2 Background;184
11.1.3;3 From Requirements to Robots;185
11.1.4;4 Exploring Information Sharing Designs;187
11.1.4.1;4.1 Experimental System;188
11.1.4.2;4.2 Methodology;190
11.1.4.3;4.3 Results;191
11.1.5;5 Conclusions;195
11.1.6;References;196
11.2;A User-Extensible and Adaptable Parser Architecture;197
11.2.1;1 Introduction;197
11.2.2;2 Architecture;199
11.2.2.1;2.1 Framework;200
11.2.2.2;2.2 Actions;200
11.2.2.3;2.3 Rules;202
11.2.2.4;2.4 Architecture Characteristics;204
11.2.2.5;2.1 Framework;200
11.2.2.6;2.2 Actions;200
11.2.2.7;2.3 Rules;202
11.2.2.8;2.4 Architecture Characteristics;204
11.2.3;3 Results;204
11.2.3.1;3.1 Architecture Scalability: Input Size;205
11.2.3.2;3.2 Rule Ordering;205
11.2.3.3;3.3 Architecture Scalability: Number of Rules;207
11.2.3.4;3.4 Coverage;207
11.2.4;4 Conclusion;209
11.2.5;References;210
11.3;The Reactive-Causal Architecture: Introducing an Emotion Model along with Theories of Needs;211
11.3.1;1 Introduction;211
11.3.2;2 Architectures for Believable Agents;212
11.3.3;3 Proposed Emotion Model;213
11.3.4;4 The Reactive-Causal Architecture;219
11.3.4.1;4.1 Reactive Layer;219
11.3.4.2;4.2 Deliberative Layer;221
11.3.4.3;4.3 Causal Layer;222
11.3.5;5 Conclusion;223
11.3.6;References;223
11.4;Automation of the Solution of Kakuro Puzzles;225
11.4.1;1 Introduction;225
11.4.2;2 Problem Analysis;227
11.4.3;3 Automating the Solution;230
11.4.3.1;3.1 Selecting a Suitable Approach;230
11.4.3.2;3.2 Backtracking Solver;232
11.4.3.3;3.3 Modifications to the Backtracking Algorithm;233
11.4.3.3.1;3.3.1 Cell Ordering;233
11.4.3.3.2;3.3.2 Reverse Value Ordering;234
11.4.3.3.3;3.3.3 Projected Run Pruning;234
11.4.4;4 Results and Timings;235
11.4.5;5 Conclusion;237
11.4.6;References;238
12;FROM MACHINE LEARNING TO E-LEARNING;239
12.1;The Bayesian Learning Automaton —Empirical Evaluation with Two-Armed Bernoulli Bandit Problems;240
12.1.1;1 Introduction;240
12.1.1.1;1.1 The Two-Armed Bernoulli Bandit Problem;241
12.1.1.2;1.2 Applications;241
12.1.1.3;1.3 Contributions and Paper Organization;242
12.1.2;2 Related Work;242
12.1.2.1;2.1 Learning Automata (LA) —The LR I and Pursuit Schemes;242
12.1.2.2;2.2 The en -Greedy and en-Greedy Policies;243
12.1.2.3;2.3 Confidence Interval Based Algorithms;244
12.1.2.4;2.4 Bayesian Approaches;244
12.1.3;3 The Bayesian Learning Automaton (BLA);245
12.1.4;4 Empirical Results;246
12.1.5;5 Conclusion and Further Work;252
12.1.6;References;253
12.2;Discovering Implicit Intention-Level Knowledge from Natural-Language Texts*;254
12.2.1;1 Introduction;254
12.2.2;2 Related Work;255
12.2.3;3 Discovering Rhetorical Relationships;257
12.2.3.1;3.1 Preprocessing and Training;258
12.2.3.2;3.2 Evolutionary Classification;259
12.2.3.2.1;3.2.1 Reproduction Operators;260
12.2.3.2.2;3.2.2 Fitness Evaluation;261
12.2.4;4 Analysis and Results;263
12.2.5;5 Conclusions;266
12.2.6;References;266
12.3;EMADS: An Extendible Multi-Agent Data Miner;268
12.3.1;1 Introduction;268
12.3.2;2 Previous Work;270
12.3.3;3 The EMADS Conceptual Framework;271
12.3.3.1;3.1 EMADS End User Categories;272
12.3.4;4 The EMADS Implementation;274
12.3.4.1;4.1 EMADS Wrappers;275
12.3.4.1.1;4.1.1 Data Wrappers;275
12.3.4.1.2;4.1.2 Tool Wrappers;276
12.3.5;5 EMADS Operation: Classifier Generation;276
12.3.6;6 Conclusions and Future Work;279
12.3.7;References;280
12.4;Designing a Feedback Component of anIntelligent Tutoring System for Foreign Language;281
12.4.1;1 Motivation;281
12.4.2;2 Feedback in ITS for FL;283
12.4.3;3 Empirical Studies in Spanish Feedback Corrective;284
12.4.4;4 A Model for Generating Effective Strategies in Spanish as a FL;288
12.4.4.1;4.1 Example of Feedback Generation;290
12.4.5;5 Conclusions;293
12.4.6;References;294
13;DECISION MAKING;295
13.1;An Algorithm for Anticipating Future Decision Trees from Concept-Drifting Data;296
13.1.1;1 Introduction;296
13.1.2;2 Related Work;298
13.1.3;3 Decision Trees;298
13.1.4;4 Predicting Decision Trees;299
13.1.4.1;4.1 Basic Idea;299
13.1.4.2;4.2 Notation;301
13.1.4.3;4.3 Predicting Attribute Evaluation Measures;302
13.1.4.4;4.4 Predicting the Majority Class in Leafs;303
13.1.4.5;4.5 Putting the Parts Together;304
13.1.5;5 Experimental Evaluation;305
13.1.6;6 Conclusion and Future Work;308
13.1.7;References;308
13.2;Polarity Assignment to Causal Information Extracted from Financial Articles Concerning Business Performance of Companies;310
13.2.1;1 Introduction;310
13.2.2;2 Related work;312
13.2.3;3 Extraction of causal expressions;313
13.2.3.1;3.1 Selection of frequent expressions;314
13.2.3.2;3.2 Acquisition of new clue expressions;315
13.2.3.3;3.3 Extraction of causal expressions by using frequent expressions and clue expressions;316
13.2.4;4 Polarity assignment to causal expressions;316
13.2.4.1;4.1 Classification of articles concerning business performance;316
13.2.4.2;4.2 Polarity assignment to causal expressions;318
13.2.5;5 Evaluation;319
13.2.5.1;5.1 Implementation;319
13.2.5.2;5.2 Evaluation results;319
13.2.6;6 Discussion;321
13.2.7;7 Conclusion;323
13.2.8;Acknowledgment;323
13.2.9;References;323
13.3;Reduxexp: An Open-source Justification-based Explanation Support Server;324
13.3.1;1 Motivation;324
13.3.2;2 Explanation;325
13.3.3;3 Decision Maintenance with the Redux’ Server;326
13.3.3.1;3.1 Planning, Design, and Heuristic Search;326
13.3.3.2;3.2 Truth Maintenance;327
13.3.3.3;3.3 The REDUX Model;328
13.3.3.4;3.4 The Redux’ Server;329
13.3.4;4 Extending Redux’: The Justification-based Explanation Support Server Reduxexp;331
13.3.4.1;4.1 Reduxexp Architecture;332
13.3.4.2;4.2 Behaviour Specifics;334
13.3.5;5 Explanation Support;335
13.3.6;6 Summary and Outlook;336
13.3.7;References;337
14;SHORT PAPERS;338
14.1;Immunity-based hybrid evolutionary algorithm for multi-objective optimization;339
14.1.1;1. Introduction;339
14.1.2;2. Immunity-based Hybrid Evolutionary Algorithm;340
14.1.2.1;2.1 Principles and theories;340
14.1.2.2;2.2 Algorithm Design;341
14.1.3;3. Simulations on Optimal Search Performance Benchmarking;341
14.1.3.1;3.1 Benchmarking Function Suite;341
14.1.3.2;3.2 Multi-objective Functions Benchmarking;342
14.1.3.3;3.3 Comparison with Evolutionary Algorithms;343
14.1.4;4. Conclusion;343
14.1.5;Acknowledgement;344
14.1.6;References;344
14.2;Parallel Induction of Modular Classification Rules;345
14.2.1;1. Introduction;345
14.2.2;2. P-Prism: A Parallel Modular Classification Rule Induction Algorithm;347
14.2.3;3. Experimental Results;349
14.2.4;4. Ongoing and Future Work;350
14.2.5;References;350
14.3;Transform Ranking: a New Method of Fitness Scaling in Genetic Algorithms;351
14.3.1;1 Introduction;351
14.3.2;2 Fitness scaling;352
14.3.3;3 A new scaling algorithm: transform ranking;353
14.3.4;4 Experimental method;353
14.3.5;5 Results and Discussion;354
14.3.6;6 Conclusions;356
14.3.7;References;356
14.4;Architecture of Knowledge-based Function Approximator;357
14.4.1;1 Introduction;357
14.4.2;2 Reinforcement Learning;358
14.4.2.1;2.1 A hybrid MDP;358
14.4.2.2;2.2 TD learning Error;358
14.4.2.3;2.3 Optimal Control;359
14.4.3;3 Random Forests in Reinforcement Learning;359
14.4.4;4 Random-TD Architecture;360
14.4.5;5 Experimental and Results;361
14.4.6;References;362
14.5;Applying Planning Algorithms to Argue in Cooperative Work;363
14.5.1;1 Introduction;363
14.5.2;2 Negotiation in cooperative work scenarios;364
14.5.3;3 Using planning algorithms in argumentation processes;365
14.5.4;4 Case study;367
14.5.5;5 Conclusions;368
14.5.6;References;368
14.6;Universum Inference and Corpus Homogeneity;369
14.6.1;1 Background & Method;369
14.6.2;2 Experiments;371
14.6.3;3 Final Remarks;374
14.6.4;References;374

Leseproben

"ARGUMENTATION AND NEGOTIATION PISA - Pooling Information from Several Agents: Multiplayer Argumentation from Experience (p. 133-134)

Maya Wardeh, Trevor Bench-Capon and Frans Coenen

 Abstract In this paper a framework, PISA (Pooling Information from Several Agents), to facilitate multiplayer (three or more protagonists), “argumentation from experience” is described. Multiplayer argumentation is a form of dialogue game involving three or more players. The PISA framework is founded on a two player argumentation framework, PADUA (Protocol for Argumentation Dialogue Using Association Rules), also developed by the authors.

One of the main advantages of both PISA and PADUA is that they avoid the resource intensive need to predefine a knowledge base, instead data mining techniques are used to facilitate the provision of “just in time” information. Many of the issues associated with multiplayer dialogue games do not present a significant challenge in the two player game. The main original contributions of this paper are the mechanisms whereby the PISA framework addresses these challenges.

1 Introduction

In many situations agents need to pool their information in order to solve a problem. For example in the field of classification one agent may have a rule that will give the classification, but that agent may be unaware of the facts which will enable the rule to be applied, whereas some other agent does know these facts. Individually neither can solve the problem, but together they can. One method to facilitate information sharing is to enable a dialogue between the two agents.

Often this dialogue takes the form of a persuasion dialogue where two agents act as advocates for alternative points of view. A survey of such approaches is given in (Prakken 2006). The systems discussed by Prakken suppose that agent knowledge is represented in the form of belief bases, essentially a set of rules and facts. In consequence dialogue moves are strongly related to knowledge represented in this form. A typical set of moves for the systems in (Prakken 2006) are:

- Claim P: P is the head of some rule
- Why P: Seeks the body of rule for which P is head
- Concede P: agrees that P is true
- Retract P: denies that P is true "