Search

Computer task automation is part of the natural progression of encoding information. This thesis considers the automation process to be a question of whether it is possible to automatically learn the encoding based on the behavior of the system to be described. A variety of representation languages are considered, as are means for the learner to acquire a variety of types of data about the system in question. The learning process is abstracted as a learning problem in which the goal is to efficiently collect sufficient information to identify some hidden concept using a particular language. The source of information about the concept is its relationship to some class of examples that is assumed to be reasonably available even if the concept is not. The goal of inquiry is to produce a learning algorithm that automates encoding of any representation (or to show that none is possible). It is argued that learning algorithms exist for two natural representation languages: propositional Horn sentences and the CLASSIC description logic, a natural first-order class used in the knowledge representation community. A new method is introduced for modeling uncertainty in the information being collected. Tools that have been developed in computational learning theory can be used for automation in real world tasks outside learning theory. Twenty-two figures are included. (Contains 101 references.) (Author/SLD)

This thesis addresses problems from two areas of theoretical computer science. The first area is that of computational learning theory, which is the study of the phenomenon of concept learning using formal mathematical models. The goal of computational learning theory is to investigate learning in a rigorous manner through the use of techniques from theoretical computer science. Much of the work in this field is in the context of "probably approximately correct" (PAC) model of learning, which is carried out in a probabilistic environment. Of particular interest are the questions of determining for which classes of concepts the PAC-learning problem is tractable and discovering efficient learning algorithms for such classes. The second area from which topics are drawn is that of online algorithms for graph-theoretic problems. Many problems in such fields as communications, transportation, scheduling, and networking can be reduced to that of finding a good graph algorithm. After an introduction in Chapter 1, some background information is provided in Chapter 2 on the field of computational learning theory. In Chapter 3 it is shown that for any concept class having a particular closure property, the existence of a graph algorithm implies that the class is PAC-learnable. Chapter 4 defines a variation on the standard PAC model of learning called semi-supervised learning, a model which permits the rigorous study of learning situations where the teacher plays only a limited role. Chapter 5 deals with the problem of prediction as performed by deterministic finite automata, counter machines, and deterministic pushdown automata. Chapter 6 investigates the power and the performance of online algorithms for a certain class of graph problems, referred to as vertex labeling problems. (77 references) (JJK)

An obstacle in Natural Language understanding is the existence of lexical gaps, i.e. words or word senses that are not in the lexicon of the system. This thesis describes the implementation of MURRAY, a learning mechanism which infers the properties of a new lexical item from its syntactical environment and infers its meaning based on context and a domain-specific database of real-world knowledge. It combines these syntactic and semantic properties to result in a version space of possible lexical entries for the unknown. MURRAY is an extension to an existing unification-based grammar processing system, UNICORN. It is compatible with grammars written in the style of head-driven phrase structure grammar. For each word that does not exist in the lexicon, MURRAY constructs a lexical version hyperspace, and then from multiple inputs the system converges on the target definition of the new world. Included in the five appendixes are sample grammars and entries, learning procedure code, and some sample learning episodes. (Contains 64 references.) (Author/SLD)

In constructing a knowledge-based system, the knowledge engineer must convert rules of thumb provided by the domain expert and previously solved examples into a working system. Research in machine learning has produced algorithms that create rules for knowledge-based systems, but these algorithms require either many examples or a complete domain theory (often in the form of rules). In many real-world situations, only a limited number of examples and an incomplete domain theory are available. This thesis presents a new paradigm for machine learning--knowledge-based learning (KBL)--which combines the strengths of empirical learning with the strengths of explanation-based learning to overcome previous limitations. Two systems--KBL0 and KBL1--are used to illustrate the new paradigm. These systems have been designed and implemented to work with domains requiring a representation of real numbers and mathematical formulas, such as engineering. This research has shown not only that it is possible to use a domain theory to guide induction using examples, but that when there are few examples available compared to the size of the problem space, the resulting rules are more accurate and stable than those from pure empirical techniques. In addition, knowledge-based algorithms free the user from selecting relevant examples and attributes for learning by using an incomplete domain theory to determine where knowledge needs to be added. A problem unsolved by the current domain knowledge helps to determine where new knowledge needs to be incorporated into the domain theory and what the context is for the learning. The context is used to select relevant examples from an example base and to reduce the number of attributes needed during the induction. With the control structure provided by knowledge-based systems, inductive learning can be used to extend an existing knowledge base. (69 references) (Author/DB)

The University of Illinois at Urbana-Champaign (UIUC) has a large campus computer network serving a community of about 20,000 users. With such a large network, it is inevitable that there are a wide variety of technologies co-existing in a multi-vendor environment. Effective network monitoring tools can help monitor traffic and link usage, as well as detect faults and correct them before serious degradation or loss of service to the user community occurs. This report describes a network monitoring and fault detection tool that has been developed and is currently in operation at UIUC. This tool makes use of the Simple Network Management Protocol (SNMP) to collect data from the various network elements monitored and process the data into reports for the network administrator. The report contains discussions of internet subnetting, UIUCnet architecture, motivation and design considerations, data collection and processing, fault detection and isolation, and evaluation, together with comments. The appendices contain a description of the SNMP variables monitored, an SNMPLog, and examples of fault isolation. A glossary of terms and abbreviations is also provided. (52 references) (Author/DB)

A prototype package of interactive computer programs for automating the information processing needs of the academic advisor in large educational systems is described in this report. This on-line filing (OLF) package is basically a program which retrieves an existing student record and allows easy interaction with a set of subroutines that perform a variety of operations on the record. The OLF package is written in CALL/360-OS FORTRAN for use on the University of Illinois IBM 360/75 facility. Operations that can be performed with the subroutines described include the calculation of grade point averages and other simple statistics. The system is structured in such a way that additional routines can be easily incorporated into the existing package. There are four appendixes that are of high importance: A) computing services office documents relevant to OLF; B) OLF operations manual; C) new Processors; D) OLF program listings. (WDR)

The trend toward on-line utilization of computers in recent years has included the emergence of computer support systems to fill the information processing needs of individuals engaged in scientific research. In this study, a new approach to document description is applied to the design of a personal information storage and retrieval system, AUTONOTE2. The system enables the user to: (1) define the topical content of each text items with phrasal descriptions, and (2) specify structural associations among the defined topics. A detailed discussion of both the design and implementation of AUTONOTE2 is provided, together with a case study of system performance during the description of a realistically diverse document collection. The results of the analyses suggest that the referential mechanisms used in the system constitute a viable alternative to keyword indexing in personal information systems. (Author/DGC)