This research is focused on building a theoretical foundation for machine learning. In this theory, it can be shown whether or not learning is feasible in given situations, the nature of the resources required, and the possibility of extending learning algorithms successfully from one situation to another. The main approach is based on reductions - relationships between learning problems and better understood combinatorial optimization problems. The importance of this research is that programs which learn - improve their performance by experience, without explicit programming - will be a central part of future computer systems. In order to shed light on the many possible approaches to machine learning, it is vital to build theoretical foundations, describing what is learnable in theory and what is not, within practical limitations of time and resources. This award is being funded as one of the 1988 Research Initiation Awards for outstanding new investigators in the Computer and Information Science and Engineering (CISE) Directorate.
