Astro Teller

Algorithm Evolution with Internal Reinforcement for Signal Understanding Degree Type: Ph.D. in Computer Science
Advisor(s): Manuela Veloso
Graduated: December 1998

Abstract:

Automated program evolution has existed in some form for almost forty years. Signal understanding (e.g., signal classification) has been a scientific concern for longer than that. Generating a general machine learning signal understanding system has more recently attracted considerable research interest. First, this thesis defines and creates a general machine learning approach for signal understanding independent of the signal's type and size. This is accomplished through an evolutionary strategy of signal understanding programs that is an extension of genetic programming. Second, this thesis introduces a suite of sub-mechanisms that increase the power of genetic programming and contribute to the understanding of the learning technique developed.

The central algorithmic innovation of this thesis is the process by which a novel principled credit-blame assignment is introduced and incorporated into the evolution of algorithms, thus improving the evolutionary process. This principled credit-blame assignment is done through a new program representation called neural programming and applied through a set of principled processes collectively called internal reinforcement in neural programming. This thesis concentrates on these algorithmic innovations in real world signal domains where the signals are typically large and/or poorly understood.

This evolutionary learning of algorithms takes place in PADO, a system developed in this thesis for "parallel algorithm discovery and orchestration" and as a demonstrably effective strategy for divide-and-conquer in signal classification domains. This thesis includes an extensive empirical evaluation of the techniques developed in a rich variety of real-world signals. The results obtained demonstrate, among other things, the effectiveness of principled credit-blame assignment in algorithm evolution.

This work is unique in three aspects. No other currently existing system can learn to classify or otherwise "symbolize" signals with no space or size penalties for the signal's size or type. No other system based on genetic programming currently exists that purposefully generates and orchestrates a variety of experts along problem specific lines. And, most centrally, the thesis introduces the first analytically sound mechanism for explaining and reinforcing specific parts of an evolving program.

The goal of this thesis is to argue, explain, and demonstrate how representation and search are intimately connected in evolutionary computation and to address these dual concerns in the context of the evolution of Turing complete programs. Ideally, this thesis will inspire future research in this same area and along similar lines.

Thesis Committee:
Manuela M. Veloso (Chair)
Tom Mitchell
Katsushi Ikeuchi (University of Tokyo)
Rodney Brooks (MIT)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Machine learning, signal understanding, pattern recognition, genetic programming, evolutionary computation, internal reinforcement, bucket brigade, neural programming, Turing complete