Algorithm Evolution for Signal Understanding

Algorithm Evolution for Signal Understanding

Astro Teller*

Computer Science Department Carnegie Mellon University Pittsburgh, PA 15213

astro@cs.cmu.edu http://www.cs.cmu.edu/ astro

Automated program evolution has existed in some form for over thirty years. Signal understanding (e.g., signal classifi­ cation) has been a scientific concern for even longer than that. Interest in generating, through machine learning techniques, a general signal understanding system is a newer topic, but has recently attracted considerable attention. First, I have proposed to define and create a machine learning mechanism for generating signal understanding systems independent of the signal's type and size. Second, I have proposed to do this through an evolutionary strategy that is an extension of genetic programming. Third, I have proposed to introduce a suite of sub-mechanisms that not only contribute to the power of the thesis mechanism, but are also contributions to the un­ derstanding of the learning technique developed and genetic programming in general.

Existing machine learning techniques have both advantages and disadvantages in their solutions to the general signal-to­ symbol problem. Concretely, the goal of this thesis work is to overcome some of these disadvantages without losing any of the important advantages of existing systems.

Two particularly prominent disadvantages of existing ma­ chine learning techniques for signal understanding are that the input must almost always be preprocessed and that do­ main knowledge must be input in the form of preprocessing or technical details that are not obvious to a signal expert. These two disadvantages can be avoided by the evolution of programs that use parameterized signal primitives.

Three prominent advantages of existing machine learning techniques for signal understanding are: that "real-world" signals can be handled; that, even when learning must be done off line, the learned function can be run in real time; and that the technique mechanisms are well understood, thereby generating faith in the method. One of the thesis goals is to transfer these advantages to the evolution of algorithms.

My thesis work involves iteratively improving the represen­ tation, evolutionary environment, and coordination of evolved programs . . These evolved programs are each expected to learn to discriminate one signal type from all others in a set of signal training examples. Then multiple, highly fit programs from each discrimination pool are orchestrated in a signal under­ standing system. I have called this paradigm PADO: Parallel Algorithm Discovery and Orchestration. My work develop­ ing the PADO architecture can be seen in papers such as [1 ; 2; 3;5].

· Astro is supported through the generosity of the Fannie and John Hertz Foundation.

Neural Programming (e.g., [4]) is the last step in a series of improved representations for genetic programming that the thesis will detail. The thesis will describe Internal Reinforce­ ment, the mechanism for the explanation and improvement of focused elements of evolving programs, in the context of neural programming (e.g., [4]).

My work concentrates on these learning mechanism inno­ vations and in real world signal domains where the signals are typically large and/or poorly understood. This thesis work is unique in three aspects: No general signal classification system currently exists that can learn to classify signals with no space or size penalties for the signal's size or type. No ge­ netic programming system currently exists that purposefully generates and orchestrates a variety of experts along prob­ lem specific lines. There is currently no analytically sound mechanism for explaining and reinforcing specific parts of an evolved program.

The main question that this thesis will answer is:

Can the genetic programming paradigm be extended (and how far) to apply successfully as a machine learning technique to the generalsignal­ to-symbol problem?