A Language for Higher-Order Explanation-Based Learning

著者: 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