Lazy Learning Meets the Recursive Least Squares Algorithm

Mauro Birattari, Gianluca Bontempi, Hugues BersiniNeurIPS 1998

Introduction: The Bandwidth Selection Problem

In "lazy learning"—a family of memory-based techniques that includes $k$-Nearest Neighbors—the system defers computation until a specific query arrives. Once a query is received, it identifies nearby data points (neighbors) to construct a local model.

The critical challenge in local learning is bandwidth selection: determining exactly how many neighbors ($k$) to include. Including too few neighbors results in a noisy, overfitted model with high variance. Conversely, including too many smooths over the local nuances of the data, leading to high bias.

Ideally, the number of neighbors $k$ should be optimized for every single query, as data density and complexity vary across the feature space. However, testing every possible value of $k$ using standard cross-validation is computationally prohibitive. This paper introduces an efficient method to perform this query-specific optimization rapidly and accurately.

Efficient Optimization via Recursive Local Regression

The authors propose a "Recursive Local Regression" approach that innovatively navigates the neighborhood of a query point using two key mathematical techniques:

  1. Recursive Least Squares (RLS): Traditionally used for time-series data, the authors adapt RLS by treating "distance from the query point" as a pseudo-time dimension. Instead of calculating a new regression model from scratch every time a neighbor is added, RLS allows the system to update the model parameters incrementally as it moves from the $k$-th to the $(k+1)$-th nearest neighbor.
  2. The PRESS Statistic: To validate these incrementally built models, the authors utilize the Predicted Residual Sum of Squares (PRESS). This statistic acts as a mathematical shortcut to calculate the leave-one-out cross-validation error without actually removing each point and retraining the model. Because the system already uses RLS, the components needed for the PRESS statistic are readily available, making validation computationally inexpensive.

With these tools, the authors compare two strategies for producing a final prediction:

  • Winner-takes-all: Selecting the single $k$ that yields the lowest mean square error.
  • Local Combination: An ensemble approach that takes a weighted average of the top $b$ models, where weights are based on the inverse of their cross-validation errors.

Experimental Setup

The proposed method was evaluated on six well-known regression datasets, primarily sourced from the UCI Machine Learning Repository (Housing, CPU, Prices, Mpg, Servo) and Leo Breiman (Ozone).

Dataset characteristics

These datasets vary significantly in size (ranging from 159 to 506 examples) and complexity (from 6 to 16 regressors), providing a robust testbed for evaluating local modeling techniques.

Key Results and Performance

The experimental results demonstrate that tailoring the bandwidth ($k$) to each specific query point generally outperforms using a single "global" $k$ optimized for the entire dataset. Furthermore, cooperation beats competition: the "Local Combination" (ensemble) approach consistently outperformed the "Winner-takes-all" method, proving more robust to noise in the local neighborhood.

Performance comparison across datasets

As shown in the performance benchmarks, the recursive method—specifically the combination variant (lbC)—performed better on average than both linear and constant local models using a single best $k$.

The authors also benchmarked their approach against Cubist, a state-of-the-art rule-based tool for piecewise-linear modeling. The recursive lazy learning method achieved highly comparable results, outperforming Cubist on datasets like Housing, Cpu, and Mpg, while trailing on others. This is particularly impressive given the relative simplicity of the underlying linear models used in the lazy learning framework.

Limitations and Future Directions

While highly efficient, the current approach has a few limitations that present opportunities for future research:

  • The Metric Problem: The method relies on a simple global Euclidean metric to find neighbors. Implementing a "local metric" that adapts its shape based on the data space's local topology could further improve performance.
  • Model Complexity: The study focused primarily on local linear and constant models. Extending this recursive framework to higher-order polynomials is a logical next step.
  • Weighting Functions: The current implementation uses a simple indicator function (a point is either in the top $k$ or it isn't). Exploring smoother weighting functions, such as Gaussian kernels, within the recursive framework remains an open area for exploration.

Summary updated

BibTeX
@inproceedings{birattari1998lazy,
  author = {Mauro Birattari and Gianluca Bontempi and Hugues Bersini},
  title = {{Lazy Learning Meets the Recursive Least Squares Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
}
Figure