The objective of this research is to make a large group of machine learning algorithms more useful in practice. This research focuses on formal models of machine learning, an area known as computational learning theory. The overall goal of this field is to give formal, mathematical definitions of learning problems, and to provide efficient algorithms to solve these problems. The computational learning theory community has proposed a large number of algorithms for solving low-level induction problems, but there are certain properties such learning algorithms must have if they are going to be used in real-world software. Practitioners, such as builders of large artificial intelligence systems, have complained that these algorithms require too much data to reach conclusions, and are too sensitive to noise in the data. This project will attempt to prove that much less data is necessary for average cases than the estimates given by theorists for the worst case, and to study how such algorithms can be modified to resist noise. The proposed project consists of the design and analysis of algorithms, and is essentially mathematical in nature. Nevertheless, if successful, this project should allow the practical application of recently developed machine learning algorithms.
