The Covering Problem: Learning Decision Regions
via Adaptive Algorithms

by James. A. Bucklew and William A. Sethares

This paper presents a family of techniques called Adaptive Covering Algorithms, which solve a particular covering problem - how to best cover a target shape using a set of simply parameterized elements. The algorithms, inspired by adaptive filtering techniques, provide a computationally simple, robust, and efficient alternative to more traditional methods such as Baysian approaches, convex hulls, and multi-layer perceptrons. The paper develops a theoretical understanding of the adaptive covering algorithms by relating their behavior to the evolution of a deterministic ordinary differential equation. Stability and instability of the ODE can be interpreted in terms of local stability/instability of the algorithm. In terms of the covering problem, candidate coverings tend to improve as more data is gathered whenever the ODE is stable. Several examples are given which demonstrate the ideas, and which verify that the analysis accurately prdicts the true behavior of the algorithms.

This technique of solving the covering problem first appeared in the IEEE Transactions on Signal Processing in October 1994.

To get to my homepage, click here.