Augmented Space Linear Model

Zhengda Qin, Badong Chen, Nanning Zheng, José C. Príncipe

Introduction

The Augmented Space Linear Model (ASLM) addresses a fundamental trade-off in machine learning: the choice between the computational efficiency of linear models and the predictive power of nonlinear systems. While linear models like Least Squares are easy to train due to their convex nature, they often fail to capture complex nonlinearities. Conversely, nonlinear models such as Neural Networks or Kernel methods offer high accuracy but suffer from high computational costs and optimization challenges like local minima. ASLM bridges this gap by functioning as a "Convex Universal Learning Machine" (CULM), maintaining the simplicity of linear training while achieving near-nonlinear accuracy.

Methodology

The ASLM approach treats training error not as a failure, but as a residual map of the underlying nonlinearity. The process involves two distinct phases: training and testing.

Training Phase

Initially, a standard Least Squares (LS) linear model is trained on the dataset. The error ($e$) for each training sample—the difference between the linear prediction and the actual target—is calculated. These errors are then stored in a lookup table, indexed by their corresponding input vectors. Geometrically, this can be viewed as augmenting the input space with a residual error dimension that captures what the linear hyperplane misses.

Testing and Prediction

During inference, a new input $\mathbf{x}$ is processed in two steps:

  1. Linear Baseline: A prediction is generated using the pre-trained linear weights $\mathbf{w}$.
  2. Error Correction: The system performs a "nearest neighbor" search in the training set to find the most similar historical input. The stored error ($e^*$) from this neighbor is retrieved and added to the baseline prediction.

The final prediction is formulated as: $$\hat{y} = \mathbf{w}^T\mathbf{x} + e^*$$

To ensure scalability, the authors utilize kd-trees for $O(\log N)$ search complexity and Vector Quantization (VQ) to compress the error table, which also serves to filter out noise. Furthermore, the search employs the Hadamard Metric, weighting distances by the linear model's coefficients to prioritize features relevant to the prediction.

Experimental Evaluation

The model was evaluated using the Lorenz System, a benchmark for chaotic nonlinear dynamics. The task involved predicting the $x$-component of the system (order $L=7$) using 2,000 training samples and 400 test samples. The model was tested under both noise-free conditions and environments with 20 dB Gaussian noise.

Results and Discussion

ASLM demonstrates a significant performance leap over traditional linear methods. In noise-free scenarios, ASLM achieved a Mean Squared Error (MSE) of $3.13 \times 10^{-3}$, approximately 100 times more accurate than standard Least Squares ($2.64 \times 10^{-1}$).

While Kernel Least Mean Square (KLMS) models may offer slightly higher peak accuracy, ASLM is orders of magnitude faster during inference, making it a superior candidate for real-time applications. Additionally, the quantized version (QASLM) proved robust against noise, consistently outperforming standard K-Nearest Neighbors (KNN).

Limitations

The primary limitation of ASLM is its reliance on the stationarity assumption; the lookup table becomes less effective if the underlying system dynamics shift over time. Additionally, despite the use of kd-trees, the nearest-neighbor search remains the primary computational bottleneck during inference.

Conclusion

By leveraging training residuals as a corrective map, the Augmented Space Linear Model provides a practical path toward universal learning without sacrificing the benefits of convex optimization. Future work may involve integrating Principal Component Analysis (PCA) for better space definition or adopting Bayesian frameworks to interpret error sensitivity.

Summary updated

Abstract

The linear model uses the space defined by the input to project the target or desired signal and find the optimal set of model parameters. When the problem is nonlinear, the adaption requires nonlinear models for good performance, but it becomes slower and more cumbersome. In this paper, we propose a linear model called Augmented Space Linear Model (ASLM), which uses the full joint space of input and desired signal as the projection space and approaches the performance of nonlinear models. This new algorithm takes advantage of the linear solution, and corrects the estimate for the current testing phase input with the error assigned to the input space neighborhood in the training phase. This algorithm can solve the nonlinear problem with the computational efficiency of linear methods, which can be regarded as a trade off between accuracy and computational complexity. Making full use of the training data, the proposed augmented space model may provide a new way to improve many modeling tasks.
BibTeX
@inproceedings{qin2018augmented,
  author = {Zhengda Qin and Badong Chen and Nanning Zheng and José C. Príncipe},
  title = {{Augmented Space Linear Model}},
  booktitle = {IJCNN},
  year = {2018},
  url = {https://openreview.net/forum?id=8Vbmg0LdiF},
}
Figure