Using Errors to Create Piecewise Learnable Partitions

Oded MaronAAAI 1994

Abstract

In machine learning, error is typically viewed as a global performance metric. This paper proposes a paradigm shift: treating error as a spatial signal to identify regions of high difficulty. By detecting "ridges" of error, the input space can be intelligently partitioned into sub-regions where specialized learners can operate without interference from discontinuities. This approach isolates "hard" regions, preventing them from polluting the training of "easy" regions and transforming complex global problems into simpler local ones.

Introduction: Error as a Map

Traditional machine learning models often struggle with sharp transitions, such as the cusp of an absolute value function or sudden jumps in piecewise constant functions. When a single model is trained on such data, these difficult regions often "pollute" the rest of the model, leading to global inaccuracies. Oded Maron's 1994 AAAI Student Abstract argues that by looking at where a model fails, we can intelligently decompose a complex problem into smaller, learnable pieces.

Methodology: Detecting Error Ridges

The proposed algorithm treats error detection as a form of multi-dimensional edge detection. The process follows four key steps:

  1. Error Mapping: After training an initial model (e.g., local weighted regression), the system maps the distribution of errors across the input space using cross-validation.
  2. Ridge Detection: The algorithm searches for "hills" or "ridges" of high error. To maintain computational tractability, the author assumes these ridges occur in axis-parallel hyperplanes, similar to the splitting strategy in CART decision trees.
  3. Heuristic Splitting: Two heuristics are used to identify significant error hills:
  4. Height: The ridge must exceed the average error.
  5. Width: The ridge must be wider than $\sqrt{n}$ (where $n$ is the number of points in the partition) to ensure the split is not a reaction to outliers.
  6. Specialized Learning: Once partitioned into hyper-rectangles, a separate learner is assigned to each. New query points are handled by the local expert corresponding to their specific region.

Datasets and Illustrative Examples

The author demonstrates the intuition behind this approach using synthetic examples designed to highlight structural challenges.

Figure 1: A 2D piecewise constant function with sharp discontinuities.
  • The Absolute Value Function ($|x|$): Demonstrates how a "hill" of error at the cusp ($x=0$) can split the problem into two perfectly linear, easily learnable halves.
  • 2D Piecewise Constant Function: A more complex "step" function (shown in Figure 1) used to test multi-dimensional ridge detection and axis-parallel partitioning.

Key Results

The approach provides a qualitative proof-of-concept for using error as a structural signal. By identifying the ridges in the error distribution, the algorithm successfully partitions complex functions into independently learnable pieces.

Figure 2: The corresponding error distribution, revealing ridges at the function's discontinuities.

As seen in Figure 2, the error distribution clearly marks the boundaries between different "regimes" of the function. By isolating these misleading training points, the algorithm shields local learners from the noise of adjacent regions, effectively transforming a non-linear, discontinuous global problem into a set of simpler local tasks.

Discussion and Limitations

While promising, the method faces several challenges:

  • The Axis-Parallel Assumption: Assuming ridges are parallel to axes is a significant constraint. Diagonal ridges would require a "staircase" approximation, potentially leading to over-segmentation.
  • Heuristic Rigor: The rules for detecting hills are practical heuristics. Distinguishing between true structural ridges and random noise remains a challenge without a more rigorous mathematical framework.
  • Computational Complexity: High-dimensional "edge detection" on error distributions is computationally intensive, particularly as the number of features increases.

Despite these limitations, the core insight—that error is a signal about underlying data structure—remains a powerful concept for developing more robust, piecewise-learnable models.

Summary updated

BibTeX
@inproceedings{maron1994using,
  author = {Oded Maron},
  title = {{Using Errors to Create Piecewise Learnable Partitions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure