Best-First Model Merging for Dynamic Learning and Recognition

Stephen M. OmohundroNeurIPS 1991

Published in the early 1990s by Stephen M. Omohundro, this paper presents a fundamental shift in how we approach model architecture. Instead of pre-defining a fixed network structure and "fitting" parameters to it, the author proposes Best-First Model Merging. This bottom-up technique starts with a highly complex model—where every single data point is its own component—and iteratively simplifies it by merging components, provided the data justifies the generalization.

The Problem with Fixed Architectures

In the early 90s, the dominant paradigm was backpropagation within fixed-structure neural networks. Omohundro identified several critical flaws in this standard approach:

  1. Fixed Complexity: Standard networks maintain a "complete" model of the domain from the start. This initial guess is usually wrong and lacks a mechanism to represent the strength of evidence or confidence.
  2. The Guessing Game: Choosing the right number of parameters (to balance overfitting and underfitting) before seeing the data is inherently flawed.
  3. Biological Inconsistency: Humans and animals do not start with a global model of the world. They begin by remembering specific, critical experiences in detail, only generalizing into reliable rules once they have accumulated enough "data."

Omohundro's work seeks a middle ground between "table-lookup" (memory-based) methods, which memorize but generalize poorly, and "parameter-fitting" (global) models, which are prone to overfitting.

The Best-First Merging Method

The core algorithm is a greedy, "best-first" search designed to discover the optimal model structure dynamically:

  1. Initialization: Start with a "memory-based" model where every data point is represented by a local component (e.g., a single Radial Basis Function or a tiny line segment).
  2. The Merge: Identify all possible pairs of components that could be merged into a single, more general component.
  3. Best-First Selection: Utilize a priority queue to find the pair whose merger increases the global error (or decreases the likelihood of the data) the least.
  4. Iteration: Execute the best merge and update the list of potential future merges.
  5. Stopping Criteria: Halt the merging process when a specific threshold is reached, such as a limit based on cross-validation, Bayesian Occam factors, or Vapnik-Chervonenkis (VC) bounds.

A key advantage of this method is locality. Because model components only affect a subset of the data, the algorithm can be made highly efficient—potentially $O(N \log N)$ or even $O(N)$—by only considering merges between neighboring components.

Key Insights

  • Bottom-Up Outperforms Top-Down: Top-down approaches (like splitting a single segment into two) often force major structural decisions too early, based on insufficient local data. Merging, conversely, makes global decisions only after many local, well-justified decisions have been established.
  • Function-Aware Clustering: Unlike standard $k$-means clustering, which places model centers based solely on data density, model merging places them based on how the underlying function behaves. It smartly allocates more resources to complex regions, like "corners" or areas of high variance.
  • The Three Priors: The author argues successful learning relies on three properties of the world: Continuity (preferring continuous models), Sparseness (components should only affect a few others), and Locality (data should be decomposable into components affected by only a few parameters).

Experimental Results

The paper demonstrates the technique using several illustrative datasets designed to highlight structural discovery:

Structural Discovery in 2D Curves

Using a set of 2D points forming a complex shape, the algorithm was tested on piecewise linear segment modeling. It successfully identified "corners" in the curves, placing boundaries between linear segments exactly where the curve's direction changed most sharply.

Piecewise linear approximation of a hand-drawn curve at various error thresholds.

Balltree Efficiency

The technique was also applied to a synthetic dataset of 500 5D hyper-balls to evaluate hierarchical spatial construction. When building these geometric structures, the merging approach resulted in significantly lower "total volume" (a proxy for search error) compared to traditional top-down or incremental construction methods.

Comparison of balltree construction methods showing Best-First Merge achieving the lowest error.

RBF Performance

In a 2D task where a sigmoid varies along one axis but is constant along the other, model merging achieved a training error 10 times lower and a test error 3 times lower than the standard $k$-means approach for choosing Radial Basis Function (RBF) centers.

Limitations and Future Directions

While highly effective, the approach has limitations. The "best-first" search requires maintaining a priority queue of all potential merges, which could become a computational bottleneck for extremely high-dimensional or non-geometric data. Furthermore, while the paper mentions various stopping criteria, it does not prescribe a definitive "one-size-fits-all" rule for when to halt the merging process.

Foreshadowing much of the structural learning research of the late 90s and 2000s, Omohundro concluded by suggesting the application of Best-First Model Merging to more complex structures, including Hidden Markov Models (HMMs), stochastic context-free grammars, and Bayesian networks.

Summary updated

BibTeX
@inproceedings{omohundro1991best,
  author = {Stephen M. Omohundro},
  title = {{Best-First Model Merging for Dynamic Learning and Recognition}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1991},
}
Figure