Scott Dietzenu
ȥ
A Language for Higher-Order Explanation-Based Learning
January 1991
Certain tasks, such as formal program development and theorem proving, fundamentally rely upon the manipulation of higher- order objects such as functions and predicates. Computing tools intended to assist in performing these tasks are at present inadequate in both the amount of 'knowledge' they contain (i.e., the level of support they provide) and in their ability to 'learn' (i.e., their capacity to enhance that support over time). The application of a relevant machine learning technique - explanationbased generalization (EBG) - has thus far been limited to first-order problem representations. We extend EBG to generalize higher-order values, thereby enagbling its application to higher-order problem encodings. Logic programming provides a uniform framework in which all aspects of explanationbased generalization and learning may be defined and carried out. First-order Horn logics(e.g., Prolog) are not, however, well suited to higher-order applications. Instead, we employ Prolog, a higher-order logic programming language, as our basic framework for realizing higher-order EBG In order to capture the distinction between domain theory and training instance upon which EBG relies, we extend Prolog with the necessity operator * of modal logic. We then provide a formal characterization of both the extended logic, * Prolog, and of higher-order EBG over Prolog computation. We also illustrate applications of higher-order EBG within program development and theorem proving. Within the architectures of traditional learning systems, the language for problem representation and solution (i.e., the programming language) is separated from the underlying learning mechanism. Herein we propose an alternative paradigm in which generaization and assimilation are realized through integrated of the programming language, and are therefore under programmer control. In this way, the developer can leverage domain knowledge and provision for user interaction in the programming of learning tasks. Thus, while g Prolog - the logic extended with generalization and assimilation features - is not itself a learning system, it is intended to serve as a flexible, high- level foundation for the construction of such systems. For g Prolog to afford this programmable learning, constructs are necessary for controlling generalization, and for assimilating the results of generalization within the logic program. The problem with the standard means by which Prolog programs are extended - assert - is that the construct is not semantically well-behaved. A more elegant alternative (adopted, for example, in prolog) is implication with its intuitionistic meaning, but the assumptions so added to a logic program are of limited applicability. We propose a new construct rule, which combines the declarative semantics of implication with some of the power of assert. Operationally, rule provides for the extension of the logic program with results that deductively follow from that program. We then extend rule to address explanation-based generalization within another new construct, rule_ebg. While rule and rule_ebg are developed in the framework of prolog,the underlying ideas are general, and therefore applicable to other logic programming languages. In addition to developing and formally characterizing the g prolog language, this thesis also provides a prototype implementation and numerous examples.
ƥ
CMUTR
Category: CMUTR
Institution: Department of Computer Science, Carnegie
        Mellon University
Abstract: Certain tasks, such as formal program development and theorem 
        proving, fundamentally rely upon the manipulation of higher-
        order objects such as functions and predicates.
        Computing tools intended to assist in performing these tasks are		at present inadequate in both the amount of 'knowledge' they 
        contain (i.e., the level of support they provide) and in their
        ability to 'learn' (i.e., their capacity to enhance that support
        over time).
        The application of a relevant machine learning technique - 
        explanationbased generalization (EBG) - has thus far been 
        limited to first-order problem representations.
        We extend EBG to generalize higher-order values, thereby
        enagbling its application to higher-order problem encodings.
        
        Logic programming provides a uniform framework in which all 
        aspects of explanationbased generalization and learning may be
        defined and carried out.
        First-order Horn logics(e.g., Prolog) are not, however, well 
        suited to higher-order applications.
        Instead, we employ  Prolog, 
        a higher-order logic programming
        language, as our basic framework for realizing higher-order EBG		        In order to capture the distinction between domain theory and 
        training instance upon which EBG relies, we extend  
        Prolog with the necessity operator * of modal logic.
        We then provide a formal characterization of both the extended
        logic,   * Prolog, and of higher-order EBG over 
         Prolog computation.
        We also illustrate applications of higher-order EBG within 
        program development and theorem proving.
        
        Within the architectures of traditional learning systems, the
        language for problem representation and solution (i.e., the 
        programming language) is separated from the underlying learning
        mechanism.
        Herein we propose an alternative paradigm in which 
        generaization and assimilation are realized through integrated 	  		of the programming language, and are therefore under programmer
        control.
        In this way, the developer can leverage domain knowledge and 
        provision for user interaction in the programming of learning 
        tasks.
        Thus, while  g Prolog - the logic extended with 
        generalization and assimilation features - is not itself a 
        learning system, it is intended to serve as a flexible, high-
        level foundation for the construction of such systems.
        
        For  g Prolog to afford this programmable learning, 
        constructs  are necessary for controlling generalization, and 
        for assimilating the results of generalization within the 
        logic program.
        The problem with the standard means by which Prolog programs
        are extended - assert - is that the construct is not 
        semantically well-behaved.
        A more elegant alternative (adopted, for example, in 
        prolog) is implication with its intuitionistic meaning, but the 
        assumptions so added to a logic program are of limited 
        applicability.
        We propose a new construct rule, which combines the declarative
        semantics of implication with some of the power of assert.
        Operationally, rule provides for the extension of the logic 
        program with results that deductively follow from that program.
        We then extend rule to address explanation-based generalization
        within another new construct, rule_ebg.
        While rule and rule_ebg are developed in the framework of 
         prolog,the underlying ideas are general, and 
        therefore applicable to other logic programming languages.
        
        In addition to developing and formally characterizing the 
         g prolog language, this thesis also provides a 
        prototype implementation and numerous examples.
        
        
        
         
Number: CMU-CS-92-110
Bibtype: TechReport
Month: jan
Author: Scott Dietzenu
Title: A Language for Higher-Order Explanation-Based Learning
Year: 1991
Address: Pittsburgh, PA
Super: @CMUTR