ICML-98 Submission #198

   Q2: Memory-Based Active Learning for Optimizing 
   Noisy Continuous Functions

   Andrew W. Moore, Jeff Schneider, Justin Boyan and Mary Soon Lee

   All authors are at: The Robotics Institute
                       Carnegie Mellon University
                       5000 Forbes Ave, Pittsburgh, PA 15213
   
Abstract

This paper introduces a new algorithm, Q2, for optimizing the expected
output of a multi-input noisy continuous function. It is designed to
need only a small number of experiments, it avoids strong assumptions
on the form of the function, and it is autonomous in that it requires
little problem-specific tweaking.

These capabilities are directly applicable to industrial processes,
and may become increasingly valuable elsewhere as the machine learning
industry expands beyond prediction and function identification, and
into embedded actively learning subsystems in robots, vehicles and
consumer products.

Four pre-existing approaches to this problem (response surface
methods, numerical optimization, supervised learning and evolutionary
methods) all have inadequacies when the requirement of "black box"
behavior is combined with the need for few experiments. Q2 is a new
approach that uses instance-based determination of a convex region of
interest for performing experiments. In conventional supervised
learning, previous instance-based approaches defined a neighborhood by
proximity to a query point, according to some definition of
similarity. In contrast, Q2 defines the neighborhood by a new
geometric procedure that captures the size and shape of the zone of
possible optimum locations. Q2 can also optimize weighted combinations
of outputs, or find inputs to produce desired outputs in a numerically
stable and efficient way.

We compare Q2 with other optimizers of noisy functions on a variety of
problems, including optimization of a simulated noisy process with
both non-linear continuous dynamics and discrete-event queueing
components.  Results on these domains are encouraging in terms of
both speed and autonomy.

Keywords:

   Active Learning, Memory-based Learning, Instance-based Learning,
   Learning Control, Statistical Learning, Optimization.

Email address of contact author:   awm@cs.cmu.edu

Phone number of contact author:   412-268-7599