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 offering a good convergence rate, the authors demonstrate that achieving this rate in practice requires a very large number of basis functions and relies on statistical guarantees, posing challenges for real-world applications.

What Problem Does This Paper Address?

In modern engineering, especially in intelligent systems operating in uncertain environments, accurate modeling and control are crucial. This often involves approximating complex, unknown functions. While neural networks like Multilayer Perceptrons (MLPs) and Radial Basis Function (RBF) networks are popular for this, achieving high-precision approximation efficiently, especially in high-dimensional spaces, remains a challenge. Theoretical results suggest that both "greedy" approximation methods and "random basis function" methods can achieve a convergence rate of O(1/n) (where 'n' is the number of basis functions), independent of the input dimension. However, the practical implications and trade-offs of these methods, particularly the random basis approach, are not fully understood. This paper aims to bridge this gap by analyzing the conditions under which the O(1/n) convergence is achievable and discussing its practical limitations.

Methods

The paper compares two primary function approximation approaches:

  • Greedy Approximation: This method, based on Barron's construction and Jones' lemma, iteratively selects basis functions that optimally reduce the approximation error. The process is deterministic, and the error is measured using the L2-norm.
  • Random Basis Function Approximation (RVFL): Also known as Random Vector Functional-Link (RVFL) networks, this approach uses basis functions (like Gaussians in RBFs or sigmoids in MLPs) whose nonlinear parameters (weights and biases) are set randomly. Only the linear parameters (coefficients) are trained. The paper focuses on the RVFL approach motivated by Igelnik and Pao's work, which uses a Monte-Carlo integration method to approximate an integral representation of the target function. The error criterion here is statistical (variance-based).

The authors analyze the theoretical convergence rates of both methods and then illustrate their practical performance through a numerical example. They also demonstrate the performance of a standard MLP with full network training for comparison.

Datasets

The paper does not use specific named datasets. Instead, it defines a target function f(x) for its illustrative example. This function is a sum of three Gaussian functions, designed to be representative of a function that can be approximated by basis functions. The "training" data for the RVFL and MLP examples are generated by randomly sampling input points from the domain [0, 1] and using the defined target function to compute the corresponding output values.

Key Insights and Ideas

  • The O(1/n) convergence rate for random basis functions is a statistical guarantee for large n: While theoretically appealing, this rate is not guaranteed for every randomly chosen set of basis functions. It holds in a probabilistic sense, meaning the probability of achieving a certain accuracy increases with 'n'.
  • Practical performance gap: The paper's example shows that random basis function approximators, even with a large number of elements, often do not match the performance of greedy approximation or, more significantly, a standard MLP with full network training, especially for smaller network sizes.
  • Ill-conditioning and numerical issues: The random nature of basis function placement can lead to ill-conditioning, making it difficult to train the linear parameters effectively. This is a significant practical hurdle.
  • Statistical vs. Deterministic Error: The deterministic error criterion of greedy approximation provides a more direct guarantee of performance compared to the statistical criterion of RVFL, which requires careful interpretation and potentially re-initialization mechanisms.
  • Full network training offers superior performance: The MLP example with full network training (adjusting both linear and nonlinear weights) demonstrates significantly better performance with much smaller network sizes compared to RVFL.

Key Results

  • The paper's example illustrates that for the chosen target function, the greedy approximation method consistently reduces the normalized approximation error ēn as O(1/n) across multiple trials.
  • In contrast, the RVFL (Monte-Carlo based) approximation shows a much slower convergence for smaller 'n', and the error spread across trials is significant, indicating less consistent performance.
  • A fully trained MLP achieved very low approximation errors with network sizes as small as 10 elements, far outperforming the RVFL approach.
  • Even when only linear weights of the MLP were trained (fixing nonlinear weights randomly), the performance was still superior to the RVFL approach for comparable network sizes.

Limitations and Future Work

  • Statistical guarantees: The primary limitation of RVFL is its reliance on statistical guarantees. This means that for a given 'n', there's no absolute certainty of achieving the desired accuracy, necessitating mechanisms like re-initialization or supervisory monitoring in practical control systems.
  • Computational cost: While RVFL simplifies the training by only adjusting linear weights, achieving the theoretical O(1/n) convergence requires a very large 'n', which can still be computationally expensive.
  • Ill-conditioning: The random placement of basis functions can lead to ill-conditioning, hindering effective linear parameter training.
  • Future Work: The authors suggest that employing integration methods with variance minimization could improve RVFL performance, but this might require prior knowledge of the target function, diminishing the RVFL's advantage. They also propose combining unsupervised node placement (based on data density) with supervised or reinforcement learning for linear parameters as a potential avenue for improvement. However, they note that such combinations are non-trivial, especially for adaptive control where resource allocation needs to be dynamic.

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