1 Introduction........................................
1 1.1 Summary...................................... 9
2 Abstraction in Different Disciplines....................... 11
2.1 Philosophy..................................... 11
2.2 Natural Language................................ 18
2.3 Mathematics ................................... 20
2.4 Computer Science................................ 23
2.5 Art(Mostly Peinture) ............................. 28
2.6 Cognition...................................... 31
2.7 Vision........................................ 37
2.8 Summary...................................... 47
3 Abstraction in Artificial Intelligence...................... 49
3.1 Theoretical Approaches............................ 49
3.2 Abstraction in Planning............................ 55
3.3 Abstraction in Constraint Satisfaction Problems . . . . . . . . . . . 59
3.4 Abstraction in Knowledge Representation............... 60
3.5 Abstraction in Agent-Based Modeling.................. 62
3.6 Summary...................................... 63
4 Definitions of Abstraction.............................. 65
4.1 Giunchiglia and Walsh’ Theory...................... 66
4.2 Abstraction in Philosophy.......................... 70
4.2.1 Wright and Hale’s Abstraction Principles . . . . . . . . . 70
4.2.2 Floridi’s Levels of Abstraction................. 71
4.3 Abstraction in Computer Science..................... 77
4.4 Abstraction in Databases........................... 79
4.4.1 Miles Smith and Smith’s Approach ............. 79
4.4.2 Goldstein and Storey’s Approach............... 83
4.4.3 Cross’ Approach........................... 84
4.5 Granularity .................................... 87
4.5.1 Hobbs’ Approach.......................... 87
4.5.2 Imielinski’s Approach....................... 89
4.5.3 Fuzzy Sets............................... 91
4.5.4 Rough Sets .............................. 92
4.6 Syntactic Theories of Abstraction..................... 94
4.6.1 Plaisted’s Theory of Abstraction................ 94
4.6.2 Tenenberg’s Theory ........................ 96
4.6.3 DeSaeger and Shimojima’s Theory............. 99
4.7 Semantic Theories of Abstraction..................... 103
4.7.1 NayakandLevy’s Theory.................... 103
4.7.2 Ghidini and Giunchiglia’s Theory............... 106
4.8 Reformulation .................................. 111
4.8.1 Lowry’s Theory........................... 112
4.8.2 Choueiryetal.’s Approach ................... 113
4.8.3 Subramanian’s Approach..................... 114
4.9 Summary...................................... 115
5 Boundaries of Abstraction ............................. 117
5.1 Characteristic Aspects of Abstraction .................. 118
5.1.1 Abstraction as Information Reduction. . . . . . . . . . . . 118
5.1.2 Abstraction as an Intensional Property ........... 120
5.1.3 Abstraction as a Relative Notion ............... 123
5.1.4 Abstraction as a Process ..................... 125
5.1.5 Abstraction as Information Hiding .............. 129
5.2 Boundaries of Abstraction.......................... 130
5.2.1 Abstraction and Generalization/Categorization . . . . . . 130
5.2.2 Abstraction, Approximation, and Reformulation. . . . . 135
5.3 Summary...................... ................ 139
6 The KRA Model.................... ................ 141
6.1 Query Environment, Description Frame,and ConfigurationSpace........................... 142
6.2 Query Environment............................... 152
6.3 Data Generation................................. 161
6.4 The KRA Model of Abstraction ..................... 163
6.5 Summary...................................... 175
7 Abstraction Operators and Design Patterns................. 179
7.1 A Classification of Abstraction Operators............... 179
7.2 Hiding Operators ................................ 180
7.2.1 Hiding Element Operators.................... 181
7.2.2 Hiding Value Operators...................... 182
7.2.3 Hiding Argument Operators................... 184
7.3 Building Equivalence Classes Operators ................ 185
7.3.1 Operators Building Equivalence Classes of Elements.............................. 186
7.3.2 Operators Building Equivalence Classes of Values . . . 189
7.3.3 Operators Building Equivalence Classes of Arguments............................. 190
7.4 Hierarchy Generating Operators...................... 190
7.4.1 Operator that Builds a Hierarchy of Types:ωhiertype.......................... 191
7.4.2 Operator that Builds a Hierarchy of Attribute Values:ωhierattrval .......................... 192
7.5 Composition Operators............................ 193
7.5.1 Operator that Builds a Collective Object: ωcoll . . . . . . 193
7.5.2 Operator that Aggregates Objects/Types: ωaggr. . . . . . 194
7.5.3 Operator that Builds up a Group of Objects: ωgroup.......................... 195
7.5.4 Operator that Constructs a New Description Element: ωconstr ........................... 196
7.6 Approximation Operators........................... 197
7.6.1 Replacement Operator: ρrepl................... 199
7.6.2 Identification Operator ...................... 199
7.7 Reformulation .................................. 201
7.8 Overview of Operators ............................ 202
7.9 Abstraction Processes............................. 203
7.10 Applying Abstraction: the Method .................... 204
7.10.1 Abstracting a P-Set with a Method.............. 204
7.11 Abstraction Processes and Query Environment. . . . . . . . . . . . 213
7.12 From Abstraction Operators to Abstraction Patterns . . . . . . . . 216
7.12.1 Design Patterns ........................... 217
7.12.2 Use and Motivation for Design Patterns .......... 218
7.12.3 Abstraction Patterns ........................ 218
7.12.4 Abstraction Pattern:Hiding................... 220
7.13 Summary...................................... 220
8 Properties of the KRA Model.......................... 223
8.1 Abstraction, Approximation, and Reformulation . . . . . . . . . . . 223
8.2 Abstraction and Information......................... 227
8.3 Approximation and Information...................... 230
8.4 Reformulation and Information ...................... 232
8.5 Query Environment and Abstraction Operators. . . . . . . . . . . . 232
8.6 Abstraction versus Concretion....................... 234
8.7 Inconsistency Problem............................. 239
8.8 KRA’s Unification Power.......................... 244
8.8.1 Theories Defined at the Perception
(Observation)Level ........................ 244
8.8.2 Semantic Theories of Abstraction............... 255
8.8.3 Syntactic Theories of Abstraction............... 264
8.9 KRA and Other Models of Abstraction ................ 266
8.10 Special Cases................................... 268
8.11 Summary...................................... 270
9. Abstraction in Machine Learning........................ 273
9.1 A Brief Introduction to Machine Learning............... 275
9.2 Abstraction in Learning from Examples or Observations. . . . . 277
9.2.1 Feature Selection .......................... 278
9.2.2 Instance Selection.......................... 283
9.2.3 Feature Discretization....................... 285
9.2.4 Constructive Induction ...................... 286
9.3 Abstraction in Reinforcement Learning................. 294
9.3.1 State Space Abstraction in Reinforcement Learning................................ 297
9.3.2 Function Approximation in Reinforcement Learning................................ 299
9.3.3 Task Decomposition and Hierarchical Reinforcement Learning ..................... 300
9.3.4 Temporal Abstraction in Reinforcement Learning. . . . 302
9.4 Abstraction Operators in Machine Learning.............. 303
9.4.1 Modeling Propositional Concept Learning in the KRA Model ......................... 303
9.4.2 Answering a Query Q in Propositional Concept Learning.......................... 305
9.4.3 Feature Selection in Propositional Learning . . . . . . . . 307
9.4.4 Modeling Relational Concept Learning in the KRA Model ......................... 309
9.4.5 Modeling Reinforcement Learning ιn the KRA Model ......................... 320
9.5 Summary...................................... 326
10 Simplicity,Complex Systems,and Abstraction............... 329
10.1 Complex Systems................................ 329
10.1.1 Abstraction in Complex Systems ............... 334
10.2 Complexity and Simplicity ......................... 338
10.3 Complexity Measures............................. 341
10.3.1 Kolmogorov Complexity..................... 342
10.3.2 Normalized Complexity...................... 346
10.3.3 Logical Depth ............................ 347
10.3.4 Thermodynamic Depth ...................... 349
10.3.5 Gamma Function (Simple Complexity). . . . . . . . . . . 349
10.3.6 Sophistication............................. 350
10.3.7 Effective Complexity ....................... 351
10.3.8 Predictive Information Rate................... 352
10.3.9 Self-Dissimilarity.......................... 353
10.4 Abstraction and Complexity......................... 354
10.4.1 Turing Machine-Based Complexity Measures . . . . . . 354
10.4.2 Stochastic Measures of Complexity ............. 357 Summary...................................... 361
11 Case Studies and Applications........................... 363
11.1 Model-Based Diagnosis............................ 363
11.1.1 An Example: The Fragment of an Hydraulic System...................... 367
11.2 Cartographic Generalization......................... 371
11.2.1 Operator Learning for Cartographic Generalization. . . 378
11.3 Hierarchical Hidden MarkovModels................... 384
11.4 Summary...................................... 387
12 Discussion ......................................... 389
12.1 Analogy ...................................... 389
12.2 Computational Complexity ......................... 393
12.2.1 Complexity Reduction in Search ............... 394
12.2.2 Complexity Reduction in CSPs ................ 395
12.2.3 Complexity Reduction in Machine Learning . . . . . . . 397
12.3 Extensions of the KRAModel ...................... 402
12.3.1 The G-KRA Model........................ 402
12.3.2 Hendriks’ Model .......................... 403
12.4 Summary...................................... 404
13 Conclusion......................................... 407
13.1 Ubiquity of Abstraction............................ 407
13.2 Difficulty o f a Formal Definition..................... 408
13.3 The Need for an Operational Theory of Abstraction . . . . . . . . 408
13.4 Perspectives of Abstraction in AI..................... 410
Appendix A: Concrete Art Manifesto......................... 413
Appendix B: Cartographic Results for Roads................... 415
Appendix C: Relational Algebra ............................ 417