Mark W.Perlin

著者: Automating the Construction of Efficient Artificial , Intelligence Algorithms
タイトル: Mark W.Perlin
日時: Sep 1991
概要: The scaling up of Artificial Intelligence (AI) systems to large real-world applications requires the use of efficient underlying AI algorithms and methods. Such efficiency, however, comes at a price: the increased conceptual and implementational complexity of developing, maintaining, and refining these efficient algorithms. What is needed is a medium for rapid specification, and a mechanism for then automatically constructing efficient AI algorithms from such specifications. Recursion is an elegant and intuitive medium for algorithm specification. Standard recursive evaluation, however, may be very inefficient. Call-Graph Caching (CGC) is the preservation of the control flow of a computational process into a graph; subsequent reuse of this graph can often result in highly efficient evaluation. Our thesis is that a large number of efficient AI algorithms can be decomposed into a conceptually trasparent recursive specification, and an implementationally efficient CGC-based evaluation. This decomposition enables an AI algorithm to be rapidly specified, and then efficiently executed. In this thesis, we introduce Call-Graph Caching. We show how to use CGC to automatically construct a variety of important efficient AI algorithms, including RETE matching, Earley and Tomita parsing, linear unification, arc consistency, classical planning, and learning algorithms. We describe MatchBox and Linear MatchBox, new algorithms for incremental conjunctive match. We present CACHE, a development environment for automatically constructing and visualizing CGC-based computation. CGC evaluation transforms search into knowledge, and represents an important first step toward a unified theory of AI computation.
カテゴリ: CMUTR

Category: CMUTR Institution: Department of Computer Science, Carnegie Mellon University Abstract: The scaling up of Artificial Intelligence (AI) systems to large real-world applications requires the use of efficient underlying AI algorithms and methods. Such efficiency, however, comes at a price: the increased conceptual and implementational complexity of developing, maintaining, and refining these efficient algorithms. What is needed is a medium for rapid specification, and a mechanism for then automatically constructing efficient AI algorithms from such specifications. Recursion is an elegant and intuitive medium for algorithm specification. Standard recursive evaluation, however, may be very inefficient. Call-Graph Caching (CGC) is the preservation of the control flow of a computational process into a graph; subsequent reuse of this graph can often result in highly efficient evaluation. Our thesis is that a large number of efficient AI algorithms can be decomposed into a conceptually trasparent recursive specification, and an implementationally efficient CGC-based evaluation. This decomposition enables an AI algorithm to be rapidly specified, and then efficiently executed. In this thesis, we introduce Call-Graph Caching. We show how to use CGC to automatically construct a variety of important efficient AI algorithms, including RETE matching, Earley and Tomita parsing, linear unification, arc consistency, classical planning, and learning algorithms. We describe MatchBox and Linear MatchBox, new algorithms for incremental conjunctive match. We present CACHE, a development environment for automatically constructing and visualizing CGC-based computation. CGC evaluation transforms search into knowledge, and represents an important first step toward a unified theory of AI computation. Number: CMU-CS-91-176 Bibtype: TechReport Month: Sep Author: Automating the Construction of Efficient Artificial Intelligence Algorithms Title: Mark W.Perlin Year: 1991 Address: Pittsburgh, PA Super: @CMUTR