A guided tour of artificial intelligence research. Vol 1

General Presentation of the Guided Tour of Artificial Intelligence Research......Page 6
Contents......Page 8
Preface: Knowledge Representation, Reasoning and Learning......Page 10
Foreword: Knowledge Representation and Formalization of Reasoning......Page 12
Elements for a History of Artificial Intelligence......Page 15
 1 Introduction......Page 16
 2 The First Steps: From Antiquity to the XVIth Century......Page 17
 3 The XVIIth Century: Preliminary Steps Towards Modernity......Page 21
 4 The XVIIIth Century: The Age of Enlightenment......Page 24
 5 The XIXth Century: The Rise of Modern Logic......Page 27
 6 The First Half of the XXth Century: From Mathematical Logic to Cybernetics......Page 30
 7 The Beginnings of the AI Era......Page 37
 8 Conclusion......Page 42
 References......Page 43
 1 Introduction......Page 58
  2.1 The Modal Logic K......Page 62
  2.2 The Modal Logic S5......Page 64
  3.1 The Normal Conditional Logic CK and Its Extensions......Page 65
  3.2 The Logic of Lewis–Burgess CL and Its Extensions......Page 67
 4 From Default Logic to Two Classes of Nonmonotonic Formalisms......Page 69
  4.2 Rational Formalisms......Page 72
  5.1 Dynamic Epistemic Logics: Public Announcement Logic......Page 73
  5.2 Public Announcement Logic as a Conditional Logic......Page 74
  5.3 Discussion......Page 76
 6 Conclusion......Page 77
 References......Page 78
 1 Introduction......Page 82
  2.1 Imprecise Information......Page 84
  2.2 Contradictory Information......Page 85
  2.3 Uncertain Information......Page 86
  2.4 Graduality and Fuzzy Sets......Page 87
  2.5 Degree of Truth Versus Degree of Certainty: A Dangerous Confusion......Page 89
  2.6 Granularity and Rough Sets......Page 90
 3 Uncertainty: The Probabilistic Framework......Page 91
  3.1 Frequentists Versus Subjectivists......Page 92
  3.2 Conditional Probabilities......Page 94
  3.3 Bayes Rule: Revision Versus Prediction......Page 96
  3.4 Probability Distributions and Partial Ignorance......Page 98
  3.5 Conditional Events and Big-Stepped Probabilities......Page 100
  4.1 General Setting......Page 102
  4.2 Qualitative Possibility Theory......Page 110
  4.3 Quantitative Possibility and Bridges to Probability......Page 117
 5 The Cube of Opposition: A Structure Unifying Representation Frameworks......Page 120
 References......Page 123
 1  Introduction......Page 131
 2 Theory of Belief Functions......Page 132
  2.1 Random Code Semantics......Page 133
  2.2 Basic Set Functions......Page 134
  2.3 Combination Rules......Page 136
  2.4 Imprecision, Specialization and Information Measures......Page 141
  2.5 Criteria for Decision Under Uncertainty......Page 144
  2.6 Applications to Statistical Learning and Data Analysis......Page 146
  3.1 Basic Definitions and Interpretations......Page 150
  3.2 Two Types of Conditioning......Page 154
 References......Page 157
 1 Introduction......Page 163
  2.1 Historical Outline......Page 164
  2.2 Different Aspects of Qualitative Reasoning......Page 166
  2.3 Evolutions and Trends......Page 170
  3.1 An Overview of the Field......Page 172
  3.2 Qualitative Calculi......Page 174
  3.3 Main Problems and Results......Page 177
  3.4 Perspectives......Page 180
  3.5 Alternative Approaches......Page 182
  3.6 Applications of Qualitative Spatial and Temporal Reasoning......Page 184
 References......Page 187
 1 Introduction......Page 196
 2 Description Logics......Page 199
  2.1 Preliminaries: DL Syntax and Semantics......Page 200
  2.2 Lightweight Description Logics: mathcalFL0 and mathcalEL......Page 201
  2.3 DL-Lite: Another Lightweight Description Logic......Page 204
  2.4 mathcalALC: The Prototypical Description Logic......Page 206
  2.5 From mathcalALC to mathcalSHIQ to mathcalSROIQ: Highly Expressive DLs......Page 207
 3 Conceptual Graphs......Page 208
  3.1 The Kernel: Basic Conceptual Graphs......Page 209
  3.2 Simple Extensions of the Support......Page 213
  3.3 Conceptual Graph Rules......Page 214
  3.4 Conceptual Graph Constraints......Page 215
  3.5 Relationships with Description Logics......Page 216
 4 Existential Rules......Page 217
  4.1 The Existential Rule Framework......Page 218
  4.2 Relationships with Database Theory......Page 219
  4.3 Decidability Results......Page 220
 5 Conclusion......Page 222
 References......Page 223
 1 Introduction......Page 227
 2 Compact Preference Representation Languages......Page 230
  3.1 Preferential Independence......Page 231
  3.2 CP-Nets......Page 232
  3.3 Semantics of CP-Nets......Page 233
  3.4 CP-Nets: Comparison and Optimisation......Page 235
  3.5 Constrained CP-Nets......Page 237
  3.6 Extensions and Variants of CP-Nets......Page 238
  3.7 Elicitation and Learning......Page 240
 4 Graphical Languages and Cardinal Representations  of Preferences: Utility Networks......Page 241
  4.1 Additively Decomposable Utilities......Page 242
  4.2 Graphical Models Associated with a Decomposable Utility Function......Page 244
  5.1 Logics, Priorities and Weights......Page 250
  5.2 Preference Logics......Page 254
 6 Conclusion......Page 257
 References......Page 258
 1 Introduction......Page 263
  2.1 Standard Deontic Logic......Page 265
  2.2 Deontic Logic of Actions......Page 268
  3.1 Dyadic Deontic Logic......Page 269
  3.2 Exceptions......Page 272
  3.3 Violations......Page 273
 4 Obligations with Delays......Page 275
  4.2 Criteria and Choice Points for Designing an Operator......Page 276
 5 Collective Obligation......Page 278
 6 Conclusion......Page 279
 References......Page 281
 1 Introduction......Page 285
  2.1 Basic Issues and Principles Underlying Causal Links......Page 287
  2.2 The Use of Causality in AI......Page 292
  3.1 Relational Models of Causality......Page 296
  3.2 Modal Logic Setting for Counterfactual Causality......Page 297
  3.3 Probabilistic Modeling of Causality......Page 298
  3.4 Causal Bayesian Networks and Interventions......Page 299
  3.5 Shafer Trees Approach to Causal Conjectures......Page 300
  3.6 The Preferential Approach to Plausible Causality  and Abnormality......Page 302
  3.7 Actual Causality: Action Logic......Page 304
  3.8 The Halpern and Pearl Approach......Page 306
  3.9 Psychological Models......Page 308
  3.10 Towards Comparing Models......Page 309
 References......Page 310
 1 Introduction......Page 316
 2 Case-Based Reasoning......Page 317
  2.1 Basic Notions Related to CBR......Page 318
  2.2 The CBR Steps......Page 320
  2.3 Knowledge Acquisition for a CBR System......Page 325
  2.4 Some CBR Systems......Page 327
 3 Reasoning by Analogy and Analogical Proportions......Page 330
  3.1 Analogy in Terms of Mappings......Page 331
  3.2 Analogy in Terms of Proportions......Page 333
  3.3 Proportional Analogy in Boolean Logic......Page 335
  3.4 Analogical Proportions Between Sequences......Page 338
  4.1 Fuzzy Sets and Approximate Reasoning......Page 339
  4.2 Graduality and Interpolation......Page 340
  4.3 Similarity-Based Qualitative Reasoning......Page 341
 References......Page 342
 1 Introduction......Page 349
  2.1 Tasks......Page 352
  2.2 Models......Page 353
  2.4 The Framework......Page 356
  3.1 Sample Complexity......Page 358
  3.2 Runtime Complexity......Page 360
  4.1 Optimization Principles......Page 362
  4.2 Conditions for Learnability......Page 366
  5.1 VC-Dimension......Page 370
  5.2 Realizable Concept Learning......Page 372
  5.3 Agnostic Concept Learning......Page 374
  5.4 Bagging and Boosting......Page 375
  6.1 Convex Learning Problems......Page 377
  6.2 Convex Learning Algorithms......Page 380
  6.3 Support Vector Machines......Page 383
 7 Conclusion......Page 386
 References......Page 389
Reinforcement Learning......Page 397
 2 Background for RL......Page 398
  3.1 Stochastic Gradient Descent Methods......Page 402
  3.2 Least-Squares Methods......Page 405
  3.4 Value-Based Deep Reinforcement Learning......Page 406
 4 Policy-Search Approaches......Page 408
  4.1 Model-Free Policy Search......Page 409
  4.2 Model-Based Policy Search......Page 411
  5.1 Reward Learning......Page 412
  5.3 Risk-Sensitive Criteria......Page 415
 6 Conclusion......Page 416
 References......Page 417
 1 Introduction......Page 423
  2.1 Introduction......Page 424
  2.2 Models for Reasoning from Inconsistency......Page 425
  3.1 Introduction......Page 427
  3.2 Presentation of Some Variants......Page 428
  3.3 An Illustrative Example......Page 429
  4.1 Foundations......Page 431
  4.2 Paraconsistent Inference......Page 433
  4.3 An Example: In the Beginning Was the Egg…......Page 434
  5.1 Introduction......Page 435
  5.2 Architecture of an Argumentation System......Page 436
 6 Reasoning in Peer-to-Peer Inference Systems......Page 440
  6.2 Inconsistency in Peer-to-Peer Inference Systems......Page 441
  6.3 Illustrative Example......Page 442
 References......Page 444
 Main Issues in Belief Revision, Belief Merging and Information Fusion......Page 449
 1 Introduction......Page 450
  2.1 Principles and Belief Revision Approaches......Page 452
  2.2 The AGM Approach and its Variants......Page 454
  2.3 Representation Theorems......Page 457
  3.1 Postulates for Iterated Revision......Page 460
  3.2 Extension to Partial Pre-orders......Page 462
  3.3 Comments on Iterated Revision......Page 464
 4 Logical Approaches to Merging......Page 465
  4.1 Semantic Approach to Merging Under Constraint......Page 466
  4.2 Families of Merging Operators......Page 468
  4.4 Merging in Other Logical Frameworks......Page 471
 5 Non-Boolean Approaches to Information Revision  and Fusion......Page 474
  5.1 Valued Revision......Page 475
  5.2 Information Fusion......Page 479
  5.3 Semantic Fusion of Weighted Knowledge Bases......Page 482
 6 Conclusion......Page 485
 References......Page 486
 1 Introduction......Page 494
  2.1 Basic Concepts and the Corresponding Models......Page 495
  2.2 Types of Reasoning and Their Implementations......Page 499
  3.1 Problems Related to the Representation of Actions......Page 503
  3.2 The Situation Calculus......Page 504
  3.3 Propositional Action Languages......Page 507
  3.4 Dynamic Logic......Page 512
  3.5 Dynamic Bayesian Networks......Page 513
 4 Reasoning About Change: Update......Page 514
 5 Conclusion......Page 521
 References......Page 522
 1 Introduction......Page 526
 2 Multicriteria Decision Problems......Page 527
 3 Preference Aggregation......Page 529
 4 Decision Models in the CA Approach......Page 533
  4.1 Dominance Relations......Page 534
  4.2 Concordance Relations......Page 538
  5.1 The Weighted Mean......Page 540
  5.2 The Weighted Tchebycheff Norm......Page 541
  5.3 The Ordered Weighted Average (OWA)......Page 543
  5.4 The Weighted OWA (WOWA)......Page 544
  5.5 The Choquet Integral......Page 546
  5.6 The Sugeno Integral......Page 550
 6 Conclusion......Page 551
 References......Page 552
 1 Introduction......Page 556
 2 The Expected Utility Criterion (EU)......Page 558
  2.1 von Neumann-Morgenstern\'s Axiomatic Foundation......Page 559
  2.2 Risk Measures......Page 566
  2.3 Attitude of Agents with Respect to Risk......Page 568
  2.4 Some Descriptive Limits of the EU Model......Page 571
 3 Non-linear Models for Decision Under Risk......Page 573
 4 Decision Models Outside the Probabilistic Framework......Page 578
  4.1 Qualitative Decision Models Under Uncertainty......Page 582
 5 Sequential Decision Models......Page 584
 6 Conclusion......Page 589
 References......Page 590
  1.1 Collective Decision Making Problems......Page 594
  1.2 The Basic Model: Ordinal Preferences......Page 596
  1.3 The Utilitarian Model, or the Model of Quantitative Preferences......Page 597
  1.4 Centralized Versus Distributed CDM......Page 598
  1.5 Discussion......Page 599
  2.1 Introduction to Voting Theory......Page 600
  2.2 Computing Voting Rules......Page 605
  2.3 Voting on Combinatorial Domains......Page 606
  2.4 Computational Barriers to Strategic Behaviour......Page 608
  2.5 Incomplete Knowledge and Communication......Page 610
  3.1 Fair Allocation Problems......Page 613
  3.2 Some Real World Fair Allocation Problems......Page 614
  3.3 How to Define Fairness?......Page 615
  3.4 Main Aggregation Functions......Page 618
  3.5 Procedural Allocation of a Divisible and Heterogeneous Resource (Cake-Cutting)......Page 619
  3.6 Fair Division and Computer Science......Page 621
  4.1 From Classical to Combinatorial Auctions......Page 624
  4.2 Bidding Languages......Page 626
  4.3 The Winner Determination Problem......Page 628
 5 Conclusion......Page 629
 References......Page 630
 1 Introduction......Page 635
  2.1 Short History of BDI Systems......Page 637
  2.2 Basic Concepts......Page 639
 3 Formalization of Trust......Page 646
  3.1 Logic-based Trust Models......Page 647
  3.2 Numerical Models of Trust......Page 648
  3.3 Applications of Trust Systems......Page 649
  4.1 Logical Formalization of Emotions......Page 651
  4.2 Numerical Models of Emotions......Page 652
 5 Conclusion......Page 653
 References......Page 654
 1 Introduction......Page 657
  2.1 Money......Page 658
  2.2 Domains of Negotiation......Page 659
  3.1 The Axiomatic Perspective......Page 660
  3.2 Protocols and Strategies for Bilateral Negotiation......Page 663
  4.1 Coordinating Negotiation with a Mediator......Page 666
  4.2 Extending Bilateral Protocols to the Multilateral Setting......Page 667
  4.3 Multilateral Negotiation by Local Deals......Page 668
 5 Persuasion-Based Negotiation......Page 670
  5.1 Agent Theory......Page 671
  5.2 Negotiation Dialogues......Page 673
 References......Page 675
 1 Introduction......Page 679
 2 Logical Framework for Diagnosis......Page 680
  2.1 Consistency-Based Logical Approach......Page 681
  2.2 Abductive Approach......Page 687
  2.3 Extensions......Page 688
  3.1 Temporal Representation and Diagnosis......Page 690
  3.2 Models of Discrete Event Systems......Page 691
  3.3 Faults, Observations and Diagnosis of DES......Page 693
  3.4 Diagnoser Approach and Other Centralized Approaches......Page 695
  3.5 Distributed and Decentralized Approaches......Page 696
  3.6 Diagnosability......Page 698
  4.1 FDI Community and Approaches for Continuous Systems: Quick Panorama......Page 699
  4.2 Comparative Analysis and Concept Mapping  for the Model-Based Logical Diagnosis Approach  and the Analytical Redundancy Approach......Page 701
  4.3 Approaches Taking Advantage of Techniques of Both Fields......Page 704
 5 Conclusion......Page 707
 References......Page 708
 1 Introduction......Page 713
  2.1 Different Validation Approaches......Page 715
  2.2 Knowledge Base Coherence......Page 717
  2.3 Models Validation......Page 719
  2.4 Validation, Refinement and Incoherencies Explanation......Page 720
 3 Explanation: Issues and Solutions......Page 721
  3.1 From the Track/log of Reasoning to the Explanation......Page 722
  3.2 Explanation as a Specific Task......Page 723
  3.3 From Reactive Explanation to Explanatory Dialogue......Page 725
  3.4 The Dialogical Explanation: the Limits of One Paradigm......Page 727
  4.1 Validation and Systems Engineering......Page 728
  4.2 Validation, Explanation and Semantic Web......Page 729
  4.3 Validation and Ontology......Page 731
 5 Conclusion......Page 732
 References......Page 733
 1 Introduction......Page 738
  2.1 The Notion of Conceptual Model......Page 739
  2.2 Problem Solving Models......Page 740
  2.3 From Conceptual Models to Ontologies......Page 741
  3.1 Knowledge Sources......Page 744
  3.2 From Knowledge Sources to Models: Research Issues......Page 745
  3.3 Designing Models: Techniques, Methods and Tools......Page 747
  3.4 Model Reuse......Page 754
  3.5 Knowledge Representation in Models......Page 757
 4 Methodological Issues and Today\'s Applications......Page 759
  4.1 Linking Language, Knowledge and Media......Page 760
  4.2 Coping with Data Explosion......Page 761
  4.3 Managing Distributed Data......Page 763
  4.4 Leveraging New Knowledge Sources......Page 764
  4.5 Coping with Knowledge Evolution......Page 765
  4.6 Collective Versus Personal Knowledge......Page 766
 5 Conclusion......Page 767
 References......Page 769
Afterword – From Formal Reasoning to Trust......Page 774
Index......Page 778