Advances in artificial intelligence : 19th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2006, Québec City, Québec, Canada, June 7-9, 2006 : proceedings

This book constitutes the refereed proceedings of the 19th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2006, held in Québec City, Québec, Canada in June 2006. The 47 revised full papers presented were carefully reviewed and selected from 220 submissions. The papers are organized in topical sections on agents, bioinformatics, constraint satisfaction and distributed search, knowledge representation and reasoning, natural language, reinforcement learning and, supervised and unsupervised learning. Front matter......Page 1 Introduction......Page 12 A Hybrid Transfer of Control Model......Page 13 Strategy Generation......Page 15 Strategy Evaluation......Page 16 Examples......Page 18 Discussion and Related Work......Page 21 Conclusions......Page 23 Introduction......Page 24 Coalition in Linear Production Domains......Page 26 Best Coalition and Coalition Structure Pattern......Page 27 Deliberating Process......Page 28 Generating Coalition Structure......Page 30 Example......Page 31 Related Work......Page 33 Conclusion and Future Work......Page 34 Introduction......Page 36 Recognition Space Model......Page 37 Variable Plan......Page 38 Plans Composition......Page 39 Disunification for Recognition Space Lattices......Page 40 Recognition of Activities in a Smart Home......Page 42 High-Level Recognition Service......Page 43 Related Works......Page 45 Conclusion......Page 46 Introduction......Page 48 Constraints of Web and Mobile Map Generation......Page 49 Knowledge-Based Approaches for On-the-Fly Map Generation......Page 50 Use of Multiagent Systems for On-the-Fly Map Generation......Page 51 Agents’ Interactions......Page 52 Architecture of Our Multiagent System......Page 54 Application: The SIGERT System......Page 55 Conclusion......Page 58 References......Page 59 Introduction......Page 60 Multiagent Task Associated Markov Decision Process (MTAMDP)......Page 61 The MTAMDP Functions......Page 64 Value Iteration for MTAMDPs......Page 65 Acyclic Decomposition Algorithm......Page 67 Discussion and Experimentations......Page 68 Conclusion and Future Work......Page 70 Introduction......Page 72 Satisfaction Equilibrium......Page 73 Satisfaction Function and Equilibrium......Page 74 Satisfying Strategies and Other Problematic Games......Page 75 Mixed Satisfaction Equilibrium......Page 76 Pure Satisfaction Equilibrium with Fixed Constants......Page 77 Empirical Results with the PSEL Algorithm......Page 78 Convergence of the PSEL Algorithm......Page 79 Limited History Satisfaction Learning (LHSL) Algorithm......Page 80 Empirical Results with the LHSL Algorithm......Page 81 Conclusion and Future Works......Page 83 Introduction......Page 84 Previous Research Works......Page 85 Requirements for ‘Believable’ Simulation......Page 86 The MAGS: The MultiAgent GeoSimulation Platform......Page 87 The Mall-MAGS Prototype: A Multiagent-Based Simulator of the Shopping Behavior in a Mall......Page 89 A ‘Usable’ Agent-Based Geosimulation Prototype: The Case of the Square One Shopping Mall (Toronto)......Page 91 The Use of the Mall_MAGS Prototype......Page 92 Conclusion and Future Works......Page 94 References......Page 95 Introduction......Page 97 Minimum-Square-Error Profile Alignment......Page 99 Optimizing the Number of Clusters......Page 100 Experimental Results......Page 102 Conclusions......Page 107 Introduction......Page 109 Macroscopic and Volumetric Modeling......Page 110 Glioma Modeling Based on White Matter Invasion......Page 111 Diffusion Models......Page 112 Experiments......Page 114 Feature Selection......Page 115 Model Performance Versus Tumor Grade......Page 117 Statistical Evaluation of the Three Models......Page 118 Contributions and Future Work......Page 119 Introduction......Page 121 Data Specification......Page 123 Learning by Bayesian Inference......Page 124 Developing Environment......Page 127 Results and Discussion......Page 128 Conclusion......Page 130 References......Page 131 Introduction......Page 133 Constraint Relaxation with Two Semirings......Page 134 Example Relaxation Problem......Page 136 Relaxing Other Solutions......Page 137 Constraint Relaxation with One Semiring......Page 138 Example......Page 141 Applications......Page 143 Introduction......Page 145 Specification of an IP Problem......Page 146 Information Personalization Requirements......Page 147 Defining IP as a Constraint Satisfaction Problem......Page 148 Constraint Satisfaction Based IP Framework......Page 149 Our Approach for Consistency Constraint Acquisition......Page 150 Solving the Constraint Satisfaction Problem for Information Personalization......Page 151 Evaluations of Variants of Partial Forward Checking......Page 154 Concluding Remarks and Future Work......Page 155 References......Page 156 Introduction......Page 157 Preliminaries......Page 159 The Quality of Random Decisions......Page 160 Quantity of Randomness......Page 164 Conclusions......Page 167 Introduction......Page 170 Modelling Arguments......Page 171 Solving with Arguments......Page 173 Results......Page 176 Comparisons......Page 179 Conclusion......Page 180 Introduction......Page 182 Background......Page 183 Noisy-AND Gates for Reinforcement and Undermining......Page 184 Noisy-AND Trees......Page 185 Noisy-AND Tree Evaluation......Page 187 Relaxing Default Assumptions......Page 188 Elicitation of CPTs with Noisy-AND Trees......Page 189 Related Models of Causal Interaction......Page 190 Conclusions......Page 193 Introduction......Page 194 Bayesian Networks......Page 195 Probabilistic Inference......Page 197 Arc Reversal......Page 198 New Approach LAZY-ARVE for BN Inference......Page 199 Related Works......Page 201 Conclusions......Page 204 Introduction......Page 206 Default Logic......Page 207 Four-Valued Logic......Page 208 Four-Valued Default Logic......Page 209 Transformation of Formulae......Page 212 Relation Between Models and Extensions......Page 213 Related Work......Page 215 Conclusion......Page 216 Introduction......Page 217 Elimination Trees and Conditioning Graphs......Page 218 Relevant Variables......Page 221 Results......Page 225 Conclusions and Future Work......Page 227 Introduction......Page 229 Graphical Models......Page 230 Melodic Representation......Page 231 Modeling Root Note Progressions......Page 232 Chord Model......Page 235 Chord Model Given Root Note Progression and Melody......Page 236 Conclusion......Page 239 d-Separation, Stochastic Independence, and the Faithfulness Assumption......Page 241 An Example Where the IC Algorithm Fails......Page 243 Failure of Faithfulness Due to Deterministic Relations......Page 244 Statistical Indistinguishability Imposed by Determinism......Page 246 A Sufficient Condition for Identifiability......Page 247 Detecting Deterministic Relations......Page 248 Experimental Results......Page 249 Discussion and Open Problems......Page 251 Introduction......Page 253 Abstract Argumentation Framework......Page 255 Argumentation Semantics......Page 258 Progressive Defeat Paths......Page 260 Conclusions......Page 263 Subject Agreement......Page 265 Addressee Agreement......Page 266 Lexicon and Subject Agreement......Page 267 Object and Oblique Agreement......Page 269 Multiple Honorification......Page 270 Agreement in Auxiliary Constructions......Page 271 Addressee Agreement......Page 274 Testing the Feasibility of the Analysis......Page 275 Conclusion......Page 276 Introduction......Page 277 Generating Gazetteers......Page 278 Resolving Ambiguity......Page 280 Evaluation with the MUC-7 Enamex Corpus......Page 282 Evaluation with Car Brands......Page 285 Supervised Versus Unsupervised......Page 286 References......Page 287 Introduction......Page 289 Related Work......Page 290 Cluster Labeling......Page 292 The Algorithm......Page 293 Experimental Setup and Results......Page 294 The Test Set Results......Page 295 Conclusion......Page 297 Introduction......Page 299 Negotiation Strategies and Communication......Page 300 Language and Strategies......Page 301 Building Language Patterns for Influence......Page 302 Extraction of Language Patterns from E-Negotiation Texts......Page 304 Early Classification of the Negotiation Outcomes......Page 306 Conclusions and Future Work......Page 308 References......Page 309 The Problem......Page 311 A Comparison......Page 312 Proposed Solution......Page 313 Indexing......Page 314 Query Rewriting and Reformulation......Page 316 Evaluation......Page 318 Quantitative Evaluation......Page 319 Conclusion and Future Work......Page 321 Objectives......Page 323 Potential for Dependency Analyses......Page 324 Filtering......Page 326 Anti-filters......Page 327 Evaluation......Page 328 Results......Page 329 Compression......Page 330 Some Problems with the Grammar or the Corpus......Page 331 Possible Improvements......Page 332 Conclusion and Future Work......Page 333 Introduction......Page 335 Related Work......Page 336 Our Approach and Dataset......Page 337 Syntactic Representation and Experiments......Page 338 Relational Representation and Experiments......Page 341 Conclusions and Future Work......Page 343 References......Page 344 Introduction......Page 347 Sentiment Tag Extraction from WordNet Glosses......Page 349 NP-Based Filtering: Senti-Sense System......Page 350 Results and Evaluation......Page 353 Conclusions and Future Work......Page 355 Introduction......Page 358 Complications in Practical Fraud Detection Research......Page 359 Benford's Law......Page 360 Reinforcement Learning......Page 361 Algorithm......Page 362 Experiments......Page 365 Conclusions......Page 368 Introduction......Page 370 Formal Model and Algorithms......Page 371 Problem Description......Page 372 Partial Observability......Page 373 FriendQ with a Partial Local View......Page 374 Results......Page 375 Related Work......Page 379 Conclusion......Page 380 Introduction......Page 382 Defining a Game Using Traces......Page 383 Constructing the MDP M......Page 385 Value of a Policy in M......Page 387 Theorems and Definition of divtrace( ."026B30D .)......Page 388 Implementation and PAC Guarantees......Page 390 Experimental Results......Page 391 Conclusion......Page 392 Introduction......Page 394 Background on Partially Observable Markov Decision Processes......Page 395 Belief Point Selection......Page 397 Selecting Belief States Based on Reachability......Page 398 Value-Based Selection......Page 402 Empirical Evaluation......Page 403 References......Page 405 Introduction......Page 406 Related Work......Page 407 Hierarchical Categorization Task......Page 408 Hierarchical Global Learning Algorithm......Page 409 Hierarchical Evaluation Measure......Page 411 Datasets......Page 414 Comparison with Hierarchical Local Approach......Page 415 Conclusion......Page 416 Introduction......Page 418 Theoretical Model......Page 419 The $Core Based Adaptive k-Means$ Algorithm......Page 421 The $Hierarchical Core Based Adaptive$ Algorithm......Page 422 Quality Measures......Page 423 $CBAk$ Results......Page 425 Adaptive Horizontal Fragmentation in Object Oriented Databases......Page 427 Conclusions and Future Work......Page 428 Introduction......Page 430 Information Tables and a Decision Logic Language......Page 431 Formal Concept Analysis......Page 432 Logical Concept Analysis Limited to Conjunction......Page 433 Classification Rules......Page 434 Consistent Classification Rules and Consistent Concepts......Page 435 An Algorithm for Finding the Most General Consistent Concepts......Page 437 Experiments......Page 439 Conclusion......Page 440 Introduction......Page 442 Review of Quantum Information Processing Concepts......Page 443 Previous Encounters of Machine Learning with Quantum Information Processing......Page 444 Training with a Quantum Dataset......Page 445 Possible Learning Strategies......Page 446 Hierarchy of Quantum Learning Classes......Page 447 Measure of Distance Between Quantum States......Page 448 Examples of Possible Quantum Clustering Algorithms......Page 449 Experimentation......Page 450 Conclusions and Open Problems......Page 452 Introduction......Page 454 Gait Signature Extraction......Page 455 Pattern Classification......Page 457 Gait Cycle Estimation......Page 458 CMU Database......Page 460 NLPR Database......Page 462 KTU Database......Page 463 Conclusion......Page 464 Introduction......Page 466 Related Work in Decision Tree Probability Estimation......Page 468 The Performance Evaluation Metrics......Page 469 A New Algorithm for Learning CLLTree......Page 470 Experimental Methodology and Results......Page 472 Conclusion......Page 477 Introduction......Page 478 Linear Dimensionality Reduction Schemes......Page 479 Performance on Synthetic Data......Page 482 Performance on Real-Life Data......Page 485 Conclusions......Page 488 Introduction......Page 490 Discriminative vs. Generative Classifiers......Page 491 Cost Curves......Page 492 Decision Trees......Page 494 Support Vector Machines......Page 496 Neural Networks......Page 498 Conclusions......Page 500 Introduction......Page 502 Problem Formulation......Page 503 Known Uses......Page 504 Enumerating the K Best Paths......Page 505 Target Utilities......Page 506 Choosing a Good $K$......Page 507 Experimental Results......Page 508 Constructing the Training Set......Page 509 Results......Page 510 Discussion and Future Work......Page 511 Introduction......Page 514 Related Work......Page 516 Feature Selection for Probability Estimation of Naive Bayes......Page 518 Conclusions and Future Work......Page 523 Introduction......Page 526 Related Work......Page 528 Lazy Averaged One-Dependence Estimators......Page 530 Experimental Methodology and Results......Page 532 Conclusions......Page 535 Introduction......Page 537 Related Work......Page 539 An Example......Page 540 Performing Classification and Ranking Based on Probability......Page 541 Experiments......Page 544 Conclusions......Page 547 Introduction......Page 549 Background......Page 550 Related Work......Page 551 Motivation......Page 552 One-Class Classification Framework......Page 553 Parameter Search Algorithms......Page 554 Evaluation Measurement......Page 556 Results......Page 557 Conclusion......Page 559 Introduction......Page 561 Background......Page 563 Mixed Initiative System......Page 564 Sudoku Strategy Graphs......Page 567 Sudoku Skill Matrix......Page 568 Initializing the Student Model......Page 569 A Sample Session......Page 570 Conclusions and Further Research......Page 571 References......Page 572 Back matter......Page 573 Followingalongtraditionofexcellence,theseventeentheditionoftheconference of the Canadian Society for the Computational Studies of Intelligence continued the success of its predecessors. This edition re?ected the energy and diversity of the Canadian AI community and the many international partnerships that this community has successfully established. AI 2004 attracted high-quality submissions from Canada and around the world. All papers submitted were thoroughly reviewed by the program comm- tee. Eachpaperwasassignedtoatleastthreeprogramcommitteemembers. Out of105submissionstothemainconference,29paperswereincludedasfullpapers inthisvolume,and22asshort/positionpapers. Threeworkshopsandagraduate symposium were also associated with AI 2004. In this volume, 14 papers selected from 21 submissions to the graduate symposium have been included. We invited three distinguished researchers to give talks representing their active research in AI: Fahiem Bacchus, Michael Littman, and Manuela Veloso. It would have been impossible to organize such a successful conference wi- out the help of many individuals. We would like to express our appreciation to the authors of the submitted papers, and to the program committee members and external referees who provided timely and signi?cant reviews. In particular, we would like to thank Luis Rueda for organizing the reviewing of the graduate symposium submissions, and Eric Mulvaney for providing valuable assistance in thepreparationoftheproceedings. Tomanagethesubmissionandreviewingp- cess we used CyberChair developed by Richard van de Stadt. Christine Gun ̈ ther from Springer has patiently attended to many editorial details. We owe special thanks to Bob Mercer for handling the local arrangements.

This book constitutes the refereed proceedings of the 19th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2006, held in Québec City, Canada in June 2006. The book presents 47 carefully reviewed, revised full papers. These are organized in topical sections on agents, bioinformatics, constraint satisfaction and distributed search, knowledge representation and reasoning, natural language, reinforcement learning and, supervised and unsupervised learning.