Feasibility of random basis function approximators for modeling and control

Ivan Tyukin, Danil V. Prokhorov

TL;DR

This paper investigates the practical feasibility of using random basis function approximators (like RBF networks) for modeling and control. While theoretically promising with a favorable O(1/n) convergence rate, the authors show this rate is only achievable with substantial computational resources and often relies on statistical guarantees, posing challenges for real-world applications.

What Problem Does This Paper Address?

In modern engineering, especially in intelligent systems, accurately modeling and controlling complex systems with inherent uncertainties is crucial. Mathematical models are often unavailable, leading to the use of function approximators. Neural networks, particularly Multilayer Perceptrons (MLPs) and Radial Basis Function (RBF) networks, are popular choices. These networks approximate unknown functions using combinations of basis functions. A key theoretical result suggests that both MLPs and RBFs can achieve an approximation error rate of O(1/n) with respect to the number of basis functions (n). However, this theoretical guarantee often assumes that all network parameters (including the nonlinear ones like weights and biases) can be optimized. This paper focuses on a specific class of approximators, known as "random basis function approximators" (or RVFL networks), where the nonlinear parameters are fixed randomly, and only the linear weights are trained. The core problem addressed is understanding the practical implications and limitations of this "random basis" approach, particularly when compared to more traditional "greedy" approximation methods.

Methods

The paper compares two main approaches to function approximation:

  • Greedy Approximation: This method, based on Barron's construction and Jones' lemma, iteratively builds an approximation by selecting basis functions that satisfy specific optimality conditions. The process is deterministic, and the error is measured using the L2-norm.
  • Random Basis Function Approximation (RVFL): This approach, inspired by Igelnik and Pao's work, uses basis functions whose nonlinear parameters (locations and widths of Gaussians in RBFs, or weights and biases in sigmoids) are chosen randomly and fixed. Only the linear coefficients (weights) of these basis functions are trained. The approximation quality is assessed statistically, often using variance or probability.

The authors analyze the theoretical convergence rates of both methods and then illustrate their practical performance through a numerical example. They also compare these methods to a standard MLP trained with a gradient-based method.

Datasets

Not discussed in the paper. The paper uses a synthetic target function defined by a combination of Gaussian functions for its illustrative example.

Key Insights and Ideas

  • The O(1/n) convergence rate is a double-edged sword: While theoretically attractive, achieving this rate with random basis functions requires a very large number of elements (n) and often relies on statistical guarantees (probability of being close to the true function), not deterministic bounds.
  • Random basis functions are not a free lunch: Fixing nonlinear parameters randomly means these basis functions are unlikely to be optimally placed for the specific target function. This can lead to significantly worse performance compared to methods that optimize these parameters, even if the latter are more computationally intensive.
  • Statistical vs. Deterministic Guarantees: The RVFL approach provides statistical guarantees (e.g., "the probability of error being less than ε is high"), whereas greedy methods offer deterministic guarantees (e.g., "the error is always less than ε"). For critical control applications, deterministic guarantees are often preferred.
  • Practical performance gap: The paper's example demonstrates that RVFL networks, even with many elements, can underperform compared to greedy methods or even standard MLPs with full network training, especially for smaller network sizes.
  • Ill-conditioning is a concern: The random placement of basis functions can lead to ill-conditioned systems, making the training of linear weights unstable and requiring careful handling.

Key Results

  • The paper shows that the O(1/n) convergence rate for random basis function approximators is achievable only for large values of 'n' and is probabilistic in nature.
  • In the provided example, RVFL networks did not match the performance of greedy approximation for networks of reasonable size. The errors for RVFLs showed a wider spread across trials and were not as consistently decreasing as with the greedy method.
  • A standard MLP trained with full network training (adjusting both linear and nonlinear weights) significantly outperformed the RVFL approach, even with a much smaller number of elements.
  • The authors highlight that while RVFLs simplify the analysis by fixing nonlinear parameters, this simplification comes at the cost of potentially poorer approximation quality and the need for robust mechanisms to handle statistical guarantees and potential ill-conditioning.

Limitations and Future Work

  • Computational Cost: The paper implies that achieving the theoretical O(1/n) rate with random basis functions requires substantial computational resources, making it less practical for many applications.
  • Statistical Guarantees: The reliance on statistical guarantees for RVFLs might be a limitation in applications requiring strict, deterministic bounds on approximation error.
  • Future Work: The authors suggest that improving RVFL performance might involve employing integration methods with variance minimization or combining unsupervised placement of network nodes with supervised or reinforcement learning for linear parameters. They also note the challenge of adaptively allocating approximation resources, which full network training handles more naturally. The paper also implicitly points towards the need for robust supervisory mechanisms to re-initialize networks if required accuracy is not met.

Summary updated

Abstract

We discuss the role of random basis function approximators in modeling and control. We analyze the published work on random basis function approximators and demonstrate that their favorable error rate of convergence O(1/n) is guaranteed only with very substantial computational resources. We also discuss implications of our analysis for applications of neural networks in modeling and control.
BibTeX
@inproceedings{tyukin2009feasibility,
  author = {Ivan Tyukin and Danil V. Prokhorov},
  title = {{Feasibility of random basis function approximators for modeling and control}},
  booktitle = {CCA/ISIC},
  year = {2009},
  doi = {10.1109/cca.2009.5281061},
}
Figure