Research and Development in Intelligent Systems XXV (eBook)

TECHNICAL PROGRAMME CHAIR’S INTRODUCTION 5
ACKNOWLEDGEMENTS 6
TECHNICAL EXECUTIVE PROGRAMME COMMITTEE 7
TECHNICAL PROGRAMME COMMITTEE 8
Table of contents 10
BEST TECHNICAL PAPER 13
On the Classification Performance of TAN and General Bayesian Networks 14
1 Introduction 14
2 Bayesian Networks and Classification 15
2.1 Inductive Learning of Bayesian Networks 15
2.1.1 K2 Search with BDeu Scoring Approach 16
2.1.2 MDL Scoring Approach 17
2.1.3 Classification using a GBN 18
2.2 Restricted Bayesian Classifiers 18
2.3 Parameter Estimation 19
3 Experiments 20
3.1 Methodology 20
3.2 Results 21
3.3 Discussion of Results 23
4 Conclusions: Suitability of GBN as a Classifier 24
Acknowledgements 26
References 26
CBR AND CLASSIFICATION 28
Code Tagging and Similarity-based Retrieval with myCBR 29
1 A Programmer’s Dilemma 29
2 Related Work 31
3 Tag Retrieval from a CBR Perspective 32
4 coTag Architecture 34
4.1 Back End: Accessing myCBR 35
4.2 Front End: Tagging, Searching, and Similarity Modelling 36
4.2.1 Case Acquisition 36
4.2.2 Query Specification 37
4.2.3 Retrieval Results 38
4.2.4 Similarity Explanation and Customisation 39
5 First evaluation results 40
6 Looking Forward 41
References 42
Sparse Representations for Pattern Classification using Learned Dictionaries 43
1 Introduction 43
1.1 Sparse Coding of Signals 44
1.2 Template Matching 45
1.3 Proposed Classification Framework 47
2 Simultaneous Approximations 48
3 K-SVD Algorithm 48
4 Proposed Algorithm for Template Generation 49
4.1 Probability Source Model 50
4.2 Representation Step 50
4.3 Dictionary Update Step 51
4.4 Statistical Template Generation and Classification 51
5 Simulations 52
6 Conclusions 54
References 54
Qualitative Hidden Markov Models for Classifying Gene Expression Data 56
1 Introduction and Motivation 56
2 Hidden Markov Models 58
3 Order of Magnitude of Probabilities: the Kappa Calculus 59
3.1 Properties 59
4 A Qualitative HMM 60
4.1 Semantics 60
4.2 Independence Assumptions 61
4.3 Additional Properties 62
5 Evaluating Observed Output 62
5.1 The Evaluation Problem 62
5.2 Problem Reformulation 63
5.3 The Qualitative Forward Algorithm 63
6 A Qualitative HMM for Gene Expression Data 65
6.1 The Problem 65
6.2 Aim 66
6.3 The Structure of the HMM 66
6.4 Data Set 67
6.5 Obtaining HMM. 67
6.6 Experiment and Analysis 67
7 Conclusion and Future Work 68
References 68
Description Identification and the Consistency Problem 70
1 Introduction 70
2 The Description-Identification Problem 71
3 Version Spaces 73
4 The Boundary-Set Approach 74
5 The Consistency-Test Approach 76
6 Consistency Algorithms for Lower-Bounded Description Spaces 77
6.1 Definition of Lower-Bounded Description Spaces 78
6.2 Applicability Conditions of the Consistency Algorithms 79
6.3 Consistency Algorithms 80
6.4 Complexity Analysis 82
6.5 Consistency Algorithms for Upper-Bounded Description Spaces 82
7 Conclusion 83
References 83
AI TECHNIQUES 84
Analysing the Effect of Demand Uncertainty in Dynamic Pricing with EAs 85
1 Introduction 85
2 A Mathematical Model of Dynamic Pricing 87
3 Optimising Stochastic DP models using EAs 89
4 Experiments and Results 91
4.1 Results 93
5 Conclusion 97
References 97
Restart-Based Genetic Algorithm for the Quadratic Assignment Problem 99
1 Introduction 99
2 Preliminaries and General Aspects 100
3 Implementation of the Restart-Based Genetic Algorithm for the QAP 102
3.1 Tabu search procedure 105
3.2 Mutation procedure 107
4 Computational Experiments 109
5 Concluding Remarks 111
References 111
CONSTRAINT SATISFACTION AND FIXES: REVISITING SISYPHUS VT 113
On a Control Parameter Free Optimization Algorithm 127
1 Introduction 127
2 SASS2 128
2.1 Effect of Step Size s on Hill-Climbing 128
2.2 Basic SASS 130
2.3 Stopping Criterion 133
2.4 Population Size 135
2.5 SASS2 Algorithm 137
3 Conclusion 138
References 138
1 Introduction 113
2 The VT problem and VT Sisyphus-II Challenge 114
2.1 VT Problem 114
2.2 An Overview of Constraint Satisfaction Techniques 114
2.3 ECLiPSe - Constraint Logic Programming System 115
3 An Overview of Structure 116
3.1 Initial Structure of ExtrAKTor Generated Code 116
3.2 ExtrAKTor Structure Summary 117
4 Investigating the Sisyphus-VT Solution Space 118
4.1 Constraint Types for Relaxation 118
4.2 Early Performance Issue 118
4.3 Performance Enhancement - “domain” & “infers most”
4.3.1 Domain Declaration 119
4.3.2 Tuple Declaration 120
4.3.3 Domain Assignment 120
4.3.4 Infers Most 120
4.3.5 Final Code Structure 120
4.3.6 Summary 121
4.4 ExtrAKTor Upgrade 121
4.4.1 Summary 121
5 Experimentation - Exploring The VT Solution Space 122
6 Discussion of Related Work 123
6.1 Comparison with VITAL Results 123
6.2 Future Work 124
6.3 Conclusion 125
Acknowledgments 126
References 126
ARGUMENTATION AND NEGOTIATION 139
PISA - Pooling Information from Several Agents: Multiplayer Argumentation from Experience 140
1 Introduction 140
2 Need for Multiparty Dialogue 141
3 Arguing from Experience 143
4 PADUA Protocol 145
5 PISA 146
5.1 Control Structure 147
5.2 Turn Taking Policy 148
5.3 Game Termination 149
5.4 Roles of the Players 150
5.5 Argumentation Tree 150
5.6 Winner Announcement 152
6 Conclusions 152
References 153
Agent-Based Negotiation in Uncertain Environments 154
1 Introduction 154
2 Communication Model 155
3 Contract Acceptance 157
4 The Scenario 159
5 The Buyer Assesses A Contract 160
5 The Buyer Assesses A Contract 160
6 The Seller Models the Buyer 162
7 Strategies 163
8 Discussion 166
References 167
Automated Bilateral Negotiation and Bargaining Impasse 168
1 Introduction 168
2 Pre-Negotiation 170
3 Actual Negotiation 171
3.1 Equilibrium Strategies 172
4 Bargaining Impasse 178
5 Related Work 180
6 Conclusion 181
References 181
INTELLIGENT SYSTEMS 182
Exploring Design Space For An Integrated Intelligent System 183
1 Introduction 183
2 Background 184
3 From Requirements to Robots 185
4 Exploring Information Sharing Designs 187
4.1 Experimental System 188
4.2 Methodology 190
4.3 Results 191
5 Conclusions 195
References 196
A User-Extensible and Adaptable Parser Architecture 197
1 Introduction 197
2 Architecture 199
2.1 Framework 200
2.2 Actions 200
2.3 Rules 202
2.4 Architecture Characteristics 204
2.1 Framework 200
2.2 Actions 200
2.3 Rules 202
2.4 Architecture Characteristics 204
3 Results 204
3.1 Architecture Scalability: Input Size 205
3.2 Rule Ordering 205
3.3 Architecture Scalability: Number of Rules 207
3.4 Coverage 207
4 Conclusion 209
References 210
The Reactive-Causal Architecture: Introducing an Emotion Model along with Theories of Needs 211
1 Introduction 211
2 Architectures for Believable Agents 212
3 Proposed Emotion Model 213
4 The Reactive-Causal Architecture 219
4.1 Reactive Layer 219
4.2 Deliberative Layer 221
4.3 Causal Layer 222
5 Conclusion 223
References 223
Automation of the Solution of Kakuro Puzzles 225
1 Introduction 225
2 Problem Analysis 227
3 Automating the Solution 230
3.1 Selecting a Suitable Approach 230
3.2 Backtracking Solver 232
3.3 Modifications to the Backtracking Algorithm 233
3.3.1 Cell Ordering 233
3.3.2 Reverse Value Ordering 234
3.3.3 Projected Run Pruning 234
4 Results and Timings 235
5 Conclusion 237
References 238
FROM MACHINE LEARNING TO E-LEARNING 239
The Bayesian Learning Automaton —Empirical Evaluation with Two-Armed Bernoulli Bandit Problems 240
1 Introduction 240
1.1 The Two-Armed Bernoulli Bandit Problem 241
1.2 Applications 241
1.3 Contributions and Paper Organization 242
2 Related Work 242
2.1 Learning Automata (LA) —The LR I and Pursuit Schemes 242
2.2 The en -Greedy and en-Greedy Policies 243
2.3 Confidence Interval Based Algorithms 244
2.4 Bayesian Approaches 244
3 The Bayesian Learning Automaton (BLA) 245
4 Empirical Results 246
5 Conclusion and Further Work 252
References 253
Discovering Implicit Intention-Level Knowledge from Natural-Language Texts* 254
1 Introduction 254
2 Related Work 255
3 Discovering Rhetorical Relationships 257
3.1 Preprocessing and Training 258
3.2 Evolutionary Classification 259
3.2.1 Reproduction Operators 260
3.2.2 Fitness Evaluation 261
4 Analysis and Results 263
5 Conclusions 266
References 266
EMADS: An Extendible Multi-Agent Data Miner 268
1 Introduction 268
2 Previous Work 270
3 The EMADS Conceptual Framework 271
3.1 EMADS End User Categories 272
4 The EMADS Implementation 274
4.1 EMADS Wrappers 275
4.1.1 Data Wrappers 275
4.1.2 Tool Wrappers 276
5 EMADS Operation: Classifier Generation 276
6 Conclusions and Future Work 279
References 280
Designing a Feedback Component of anIntelligent Tutoring System for Foreign Language 281
1 Motivation 281
2 Feedback in ITS for FL 283
3 Empirical Studies in Spanish Feedback Corrective 284
4 A Model for Generating Effective Strategies in Spanish as a FL 288
4.1 Example of Feedback Generation 290
5 Conclusions 293
References 294
DECISION MAKING 295
An Algorithm for Anticipating Future Decision Trees from Concept-Drifting Data 296
1 Introduction 296
2 Related Work 298
3 Decision Trees 298
4 Predicting Decision Trees 299
4.1 Basic Idea 299
4.2 Notation 301
4.3 Predicting Attribute Evaluation Measures 302
4.4 Predicting the Majority Class in Leafs 303
4.5 Putting the Parts Together 304
5 Experimental Evaluation 305
6 Conclusion and Future Work 308
References 308
Polarity Assignment to Causal Information Extracted from Financial Articles Concerning Business Performance of Companies 310
1 Introduction 310
2 Related work 312
3 Extraction of causal expressions 313
3.1 Selection of frequent expressions 314
3.2 Acquisition of new clue expressions 315
3.3 Extraction of causal expressions by using frequent expressions and clue expressions 316
4 Polarity assignment to causal expressions 316
4.1 Classification of articles concerning business performance 316
4.2 Polarity assignment to causal expressions 318
5 Evaluation 319
5.1 Implementation 319
5.2 Evaluation results 319
6 Discussion 321
7 Conclusion 323
Acknowledgment 323
References 323
Reduxexp: An Open-source Justification-based Explanation Support Server 324
1 Motivation 324
2 Explanation 325
3 Decision Maintenance with the Redux’ Server 326
3.1 Planning, Design, and Heuristic Search 326
3.2 Truth Maintenance 327
3.3 The REDUX Model 328
3.4 The Redux’ Server 329
4 Extending Redux’: The Justification-based Explanation Support Server Reduxexp 331
4.1 Reduxexp Architecture 332
4.2 Behaviour Specifics 334
5 Explanation Support 335
6 Summary and Outlook 336
References 337
SHORT PAPERS 338
Immunity-based hybrid evolutionary algorithm for multi-objective optimization 339
1. Introduction 339
2. Immunity-based Hybrid Evolutionary Algorithm 340
2.1 Principles and theories 340
2.2 Algorithm Design 341
3. Simulations on Optimal Search Performance Benchmarking 341
3.1 Benchmarking Function Suite 341
3.2 Multi-objective Functions Benchmarking 342
3.3 Comparison with Evolutionary Algorithms 343
4. Conclusion 343
Acknowledgement 344
References 344
Parallel Induction of Modular Classification Rules 345
1. Introduction 345
2. P-Prism: A Parallel Modular Classification Rule Induction Algorithm 347
3. Experimental Results 349
4. Ongoing and Future Work 350
References 350
Transform Ranking: a New Method of Fitness Scaling in Genetic Algorithms 351
1 Introduction 351
2 Fitness scaling 352
3 A new scaling algorithm: transform ranking 353
4 Experimental method 353
5 Results and Discussion 354
6 Conclusions 356
References 356
Architecture of Knowledge-based Function Approximator 357
1 Introduction 357
2 Reinforcement Learning 358
2.1 A hybrid MDP 358
2.2 TD learning Error 358
2.3 Optimal Control 359
3 Random Forests in Reinforcement Learning 359
4 Random-TD Architecture 360
5 Experimental and Results 361
References 362
Applying Planning Algorithms to Argue in Cooperative Work 363
1 Introduction 363
2 Negotiation in cooperative work scenarios 364
3 Using planning algorithms in argumentation processes 365
4 Case study 367
5 Conclusions 368
References 368
Universum Inference and Corpus Homogeneity 369
1 Background & Method
2 Experiments 371
3 Final Remarks 374
References 374

"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 "