Doctoral Dissertation

Computational Measures of Information Gain and Reinforcement in Inference Processes

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

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
    Contents V
    Extended Abstract XI
    Resumen Extendido XIII
    Authorship XV
    Acknowledgements XVII

    1. INTRODUCTION 21
        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. ON INFERENCE PROCESSES AND THEIR RELATIONSHIP 39
        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. INFORMATION AND REPRESENTATION GAINS 73
        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. INFORMATION GAIN AND INFERENCE PROCESSES 103
        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. CONSTRUCTIVE REINFORCEMENT 149
        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. INTENSIONALITY AND EXPLANATION 191
        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. EVALUATION AND GENERATION OF INDUCTIVE HYPOTHESES 219
        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. MEASURING INTELLECTUAL ABILITIES 241
        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. PROSPECTIVE APPLICATIONS 263
        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. CONCLUSIONS 299
        10.1 Introduction 300
        10.2 Main Contributions 301
        10.3 Open Questions and Future Work 303
        10.4 Concluding Remarks 306

    A. A BRIEF REVIEW OF KOLMOGOROV COMPLEXITY 307
        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

    B. PUBLICATIONS GENERATED FROM THIS THESIS 319

    C. REFERENCES 323

    D. ACRONYMS 353

    E. INDEX 355



Go back to my home page.


© 1995-1999 José Hernández Orallo.