by Jose Hernandez-Orallo
Supervisor: Prof. Dr. Rafael
Beneyto-Torres
Department of Logic and Philosophy
of Science, University of Valencia
Successfully defended 16th December, 1999.
Any comment, suggestion and critique (even hostile) will be appreciated.
Keywords
Evaluation Measures, Inference Processes, Induction,
Deduction, Information, Kolmogorov Complexity, Reasoning, Inference Paradox,
Information Gain, Inference Confirmation, Reinforcement, Intensionality,
Measurement of Cognitive Abilities, Evaluation of Logical Theories, Knowledge-Based
Systems, Machine Learning, Inductive Logic Programming, Intensionality.
Click here to download
the whole thesis, 24-9-99, 350 pp. approx (also in postscript: thesis.ps.zip)
This work is devoted to the formal study of inductive
and deductive concept synthesis usefulness and aftermath in terms of information
gain and reinforcement inside inference systems. The set of measures which
are introduced allow a detailed and unified analysis of the value of the
output of any inference process with respect to the input and the context
(background knowledge or axiomatic system).
Although the main measures, computational information
gain, reinforcement and intensionality, are defined independently, they
(alone or combined) make it possible to formalise or better comprehend
several notions which have been traditionally treated in a rather ambiguous
way: novelty, explicitness/implicitness, informativeness, surprise, interestingness,
plausibility, confirmation, comprehensibility, ‘consilience’, utility and
unquestionability.
Most of the measures are applied to different
kinds of theories and systems, from the appraisal of predictiveness, the
representational optimality and the axiomatic power of logical theories,
software systems and databases, to the justified evaluation of the intellectual
abilities of cognitive agents and human beings.
Contents
Abstract and Keywords III
1. INTRODUCTION 21
2. ON INFERENCE PROCESSES
AND THEIR RELATIONSHIP 39
3. INFORMATION AND REPRESENTATION
GAINS 73
4. INFORMATION GAIN AND
INFERENCE PROCESSES 103
5. CONSTRUCTIVE REINFORCEMENT 149
6. INTENSIONALITY AND EXPLANATION
191
7. EVALUATION AND GENERATION
OF INDUCTIVE HYPOTHESES 219
8. MEASURING INTELLECTUAL
ABILITIES 241
9. PROSPECTIVE APPLICATIONS
263
10. CONCLUSIONS 299
A. A BRIEF REVIEW OF KOLMOGOROV
COMPLEXITY 307
B. PUBLICATIONS GENERATED
FROM THIS THESIS 319
C. REFERENCES 323
D. ACRONYMS 353
E. INDEX 355
Click here to
download a pdf for the presentation (44 slides), also as a zipped
PowerPoint (275 KB) or zipped Postscript
(127 KB).
Hay también un resumen
en castellano, 24-9-99, (70 págs. aprox.), también en postscript. También la presentación. .
Abstract
Contents V
Extended Abstract XI
Resumen Extendido XIII
Authorship XV
Acknowledgements XVII
1.1 Introduction 22
1.2 Motivation and Precedents 24
1.3 Aims 30
1.4 Overview and Organisation 32
1.5 Terminology and Notation 37
2.1 Introduction 40
2.2 Deduction 44
2.2.1 Automated Deduction and Logic Programming 46
2.2.2 Resource-Bounded and Non-omniscient Deduction 49
2.3 Induction 50
2.3.1 The MDL principle and other Selection Criteria 52
2.3.2 Grammatical Inference and Induction of Functional Programs 55
2.3.3 Inductive Logic Programming (ILP) 56
2.4 Abduction 59
2.5 Reasoning by Analogy 61
2.5.1 Case-Based Reasoning 62
2.6 On the Relation between Inference Processes 63
2.6.1 Inference Processes, Effort and Lazy/Eager Methods 65
2.6.2 Inference Processes and Confirmation 68
2.6.3 Towards a Combination of Inference Processes 70
3.1 Introduction 74
3.2 Resource Consumption and Gain 77
3.3 Relative Information Value 79
3.3.1 Properties 80
3.4 Time-Ignoring Information Gain 82
3.5 Computational Information Gain 84
3.5.1 Fundamental Properties 85
3.5.2 Unique Interface Formulation 86
3.5.3 Other Properties 87
3.6 Information Gain and Complexity 88
3.7 True Information Gain 90
3.8 Representation Gain 91
3.8.1 Universal Simplification 92
3.8.2 Representational Optimality 94
3.9 Comparison with Related Information Measures 96
3.9.1 Kirsh’s Theory of Explicitness 97
3.9.2 Nake’s Theory of Aesthetics and Schmidhuber’s Interestingness 98
3.10 Summary and Contributions of This Chapter 99
4.1 Introduction 104
4.2 Information Gain and Induction 108
4.3 Creativity, Learning and Discovery 111
4.4 Quinlan’s Information Gain and Gain Ratio 114
4.5 Information Gain and Deduction 117
4.5.1 Example: Information Gain for Logical Theories 120
4.6 Hintikka’s Surface and Depth Information 131
4.7 Axiomatic Systems Optimisation 132
4.7.1 Single Evidence Representational Optimality 133
4.7.2 Theory Optimisation for Multiple Evidence 135
4.7.3 Pietarinen’s Systematic Power 137
4.8 A Characterisation of Lazy and Eager Inference Methods 138
4.9 Induction, Deduction and Information 140
4.9.1 Intermediate Information 141
4.9.2 Resource-Bounded and Fallible Inference 142
4.10 Summary and Contributions of This Chapter 146
5.1 Introduction 150
5.1.1 Reinforcement as Selection Criterion 151
5.2 Reinforcement Learning 151
5.3 Reinforcement with respect to the Theory Use 153
5.4 Reinforcement with respect to the Evidence 155
5.5 Evaluation of Inductive Theories 156
5.5.1 Knowledge Construction, Revision and Abduction 157
5.5.2 Consilience can be precisely defined 160
5.5.3 Intrinsic Exceptions, Consilience and Noise 163
5.5.4 Reinforcement, Intensionality and Cross-Validation 164
5.6 Analogy, Consilience and Reinforcement 165
5.7 Extended and Balanced Reinforcement 166
5.8 Rewarded Reinforcement 170
5.9 External Inconsistencies. Negative Reinforcement 171
5.10 Reinforcement and Deduction 174
5.10.1 Derived Rules Explicitation 174
5.10.2 Non-Omniscient Deduction 178
5.10.3 Reinforcement, Consilience and Interestingness in Mathematics 179
5.11 Reinforcement as a Theory of Confirmation 180
5.12 Reinforcement and Information Gain 181
5.12.1 Reinforcement vs. Gain 181
5.12.2 Combination of Gain and Reinforcement 182
5.12.3 Forgetting Highly Reinforced Parts 183
5.13 Reinforcement and Theory Understandability 184
5.14 Computing Reinforcement 187
5.15 Summary and Contributions of This Chapter 188
6.1 Introduction 192
6.2 Extensional and Intensional Definitions 194
6.3 Exception-Free Descriptions 195
6.3.1 Exception-Free Logic Programs 197
6.4 Subprograms and General Reinforcement 200
6.4.1 Subpart and partitions 200
6.4.2 Subprogram 201
6.4.3 General Reinforcement 201
6.5 Projectible Descriptions and ‘Pattern’ 203
6.6 Intensionality, Informativeness and Explanatory Induction 207
6.6.1 Descriptive vs. Explanatory Induction 210
6.6.2 Unquestionability 211
6.7 Information Gain and Intensionality 212
6.8 Intensionality, Learning, and Meaning 213
6.9 Summary and Contributions of This Chapter 215
7.1 Introduction 220
7.2 Evaluation of Inductive Logical Theories 221
7.2.1 Generality Measures: GD(T|E) and g(H) 222
7.2.2 The MDL principle based on Model Complexity 222
7.2.3 The MDL principle based on Proof Complexity 223
7.2.4 Information Gain revisited: G (T|E) 224
7.2.5 Reinforcement Revisited 224
7.2.6 Example 225
7.3 Generation of Inductive Hypotheses 236
7.3.1 Information Gain and the Enumeration Approach 236
7.3.2 Randomised example-driven Induction, Reinforcement and Gain 238
7.4 Summary and Contributions of This Chapter 239
8.1 Introduction 242
8.2 Requirements and Technical Problems 242
8.3 Unquestionability 246
8.4 Establishing Absolute Difficulty 247
8.5 The Test 248
8.6 Measurement of Pretended Intelligent Systems 250
8.7 Factorisation 252
8.7.1 Inductive Factors 252
8.7.2 Deductive Abilities 253
8.7.3 Other factors 255
8.8 The C-test and The Turing Test 256
8.9 Summary and Contributions of This Chapter 257
8.10 Appendix. An Example of C-Test 258
8.10.1 A Toy Memory-less Abstract Machine 259
8.10.2 The Generation of k-Hard Strings 260
8.10.3 The Tests 260
8.10.4 Subjects and Administration 261
8.10.5 Results 261
9.1 Introduction 264
9.2 Representational Data-Mining and Data Quality 265
9.2.1 Knowledge Discovery in Databases (KDD) 266
9.2.2 Relationship between Intensionality and Data Quality 268
9.3 Software Topologies and Reinforcement 271
9.3.1 Adapting the ML framework 272
9.3.2 Sample data. Training set 273
9.3.3 Granularity of propagation 273
9.3.4 Validation data. User’s accordance 274
9.3.5 Software and reinforcement 275
9.3.6 Validation propagation by reinforcement 278
9.3.7 Measurement in practice 280
9.3.8 Modification propagation 281
9.3.9 Modification dependencies 283
9.3.10 System topologies and maintenance cost 286
9.4 Other Applications 291
9.4.1 Meaning and Language Understanding 291
9.4.2 Agent Communication 292
9.5 Summary 293
9.6 Appendix 294
10.1 Introduction 300
10.2 Main Contributions 301
10.3 Open Questions and Future Work 303
10.4 Concluding Remarks 306
A.1 Introduction 308
A.2 Mathematical Definition and Properties 308
A.3 Mutual Information and Information Distance 311
A.4 Algorithmic Probability and Inductive Reasoning 313
A.5 Resource-bounded Complexity and Universal Search 314
A.6 Algorithmic Potential 317
A.7 Algorithmic (or Logical) Depth and Sophistication 317
Go back to my home page.