Files in this item



application/pdf9114177.pdf (7MB)Restricted to U of Illinois
(no description provided)PDF


Title:Topics in computational learning theory and graph algorithms
Author(s):Board, Raymond Acton
Doctoral Committee Chair(s):Pitt, Leonard
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Computer Science
Abstract:The distribution-independent model of concept learning from examples ("PAC-learning") due to Valiant is investigated. It has previously been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class. (An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.) It is shown here that for any class satisfying the property of closure under exception lists, the PAC-learnability of the class implies the existence of an Occam algorithm for the class. Thus the existence of randomized Occam algorithms exactly characterizes PAC-learnability for all concept classes with this property. This reveals a close relationship between PAC-learning and information compression for a wide range of interesting classes.
The PAC-learning model is then extended to that of semi-supervised learning (ss-learning), in which a collection of disjoint concepts is to be simultaneously learned with only partial information concerning concept membership available to the learning algorithm. It is shown that many PAC-learnable concept classes are also ss-learnable. Several sets of sufficient conditions for a class to be ss-learnable are given. A prediction-based definition of learning multiple concept classes has been given and shown to be equivalent to ss-learning.
The predictive ability of automata less powerful than Turing machines is investigated. Models for prediction by deterministic finite state machines, 1-counter machines, and deterministic pushdown automata are defined, and the classes of languages that can be predicted by these types of automata are precisely characterized. In addition, upper bounds are given for the size of classes that can be predicted by such automata.
Two new online protocols for graph algorithms are defined. Bounds on the performance of online algorithms for the graph bandwidth, vertex cover, independent set, and dominating set problems are demonstrated. Various results are proved for algorithms operating according to a standard online protocol as well as the two new protocols.
Issue Date:1990
Rights Information:Copyright 1990 Board, Raymond Acton
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9114177
OCLC Identifier:(UMI)AAI9114177

This item appears in the following Collection(s)

Item Statistics