A study of parallelism in the classifier system and its application to classification in kl-one semantic networks (artificial intelligence, fine-grained)
Stephanie Forrest · Deep Blue (University of Michigan) · 1985
Current techniques for knowledge representation in artificial intelligence limit their applicability in many domains. One reason for this limitation is the large amount of computation involved in processing reasonably-sized knowledge-bases. Current research in parallelism suggests that one promising direction is the development of parallel architectures that are designed for applications in artificial intelligence. In the dissertation, I show how one model of fine-grained parallelism, the Classifier System, can be used to implement a set of useful operations for the classification of knowledge in semantic networks. The Classifier System appears amenable to hardware implementation, but for the dissertation, a software simulation was written. The "classification" problem was selected as the focus of the investigation because it is a central problem for many knowledge-based systems. Of the various knowledge representation paradigms in use today, the KL-ONE family has addressed the problem of classification most directly. I therefore, have used a subset of this language for my investigations. I have implemented a compiler that translates KL-ONE definitions into a Classifier System representation. In addition, I have developed a group of parallel algorithms that uses the Classifier System representation to decide where an incoming concept should be classified in an existing KL-ONE network. A significant part of the work on this project has consisted of developing a collection of more general algorithms for the Classifier System (set operations, numerical processing, and the construction of default hierarchies) that have formed the basis for the classification algorithms. The study was divided into three major phases: designing and implementing the general operations for controlling the Classifier System, reformulating the KL-ONE formalism in terms of these operations, and analyzing the efficiency of the parallel algorithms with respect to the inherent computational tradeoffs among the number of processors, length of computation, and degree of inter-processor communication. The study concludes that architectures of this type are capable of significantly reducing the time complexity of common semantic network operations.