A survey on universal approximation and its limits in soft computing techniques

Domonkos Tikk, László T. Kóczy, Tamás D. GedeonInt. J. Approx. Reason 2003 · DOI

TL;DR

This paper surveys the landscape of universal approximation in soft computing techniques like neural networks and fuzzy systems. It highlights that while these methods can approximate any function, the number of "building blocks" (neurons or rules) required grows exponentially with accuracy, posing practical challenges. The survey explores the trade-offs between accuracy and complexity, and discusses both positive and negative results in this domain.

What Problem Does This Paper Address?

The paper addresses a fundamental question in soft computing: how well can techniques like neural networks and fuzzy systems approximate arbitrary functions, and what are the practical limitations? Specifically, it delves into the concept of "universal approximation," which states that these systems can, in theory, learn any continuous function to an arbitrary degree of accuracy. However, a key challenge arises from the fact that achieving high accuracy often requires an impractically large number of computational units (neurons in neural networks or rules in fuzzy systems). This exponential growth in complexity, often referred to as the "curse of dimensionality," makes direct application of these theoretical results difficult in real-world scenarios. The paper aims to provide a comprehensive overview of the theoretical underpinnings, the positive results demonstrating universal approximation, and the negative results that highlight its limitations, particularly concerning the trade-off between approximation accuracy and the number of building blocks.

Methods

The paper surveys existing theoretical results and proofs related to universal approximation. It draws heavily on established mathematical concepts like topological spaces, dense and nowhere dense sets, and various norms (supremum norm, L_p norms) to formally define and analyze approximation properties. For neural networks, it discusses results based on Kolmogorov's representation theorem and extensions thereof, particularly focusing on multilayer feedforward networks with various activation functions (semilinear, sigmoidal, hard limiters). For fuzzy systems, it examines results for Mamdani and Takagi-Sugeno (TS) type controllers, often leveraging the Stone-Weierstrass theorem. The paper also discusses constructive proofs and methods for determining the number of building blocks required for a given accuracy, often involving characteristics of the function being approximated (e.g., modulus of continuity, Lipschitz constant).

Datasets

Not discussed in the paper. This paper is a theoretical survey and does not present experimental results or introduce new datasets.

Key Insights and Ideas

  • Universal Approximation is Commonplace but Costly: Both neural networks and fuzzy systems, in their various forms, are capable of universal approximation. However, the "cost" of this approximation (in terms of the number of building blocks) grows exponentially with the desired accuracy, making it impractical for many real-world applications.
  • The "Curse of Dimensionality" is Real: The number of neurons or rules needed to achieve a certain accuracy increases dramatically with the number of input variables to the function being approximated.
  • Trade-offs are Inevitable: Practical applications require a balance between approximation accuracy and computational complexity. The paper explores research that attempts to quantify this trade-off.
  • Smoothness Matters: The ability to achieve good approximation rates (how quickly accuracy improves with more building blocks) often depends on known smoothness properties of the function being approximated. If these properties are unknown, it's difficult to guarantee efficient approximation.
  • Architecture is Key: For neural networks, the multilayer feedforward architecture, rather than the specific choice of activation function, is identified as the primary reason for their universal approximation capabilities.
  • Negative Results are Crucial: The paper highlights important negative results, such as the discontinuity of the best approximation operator for certain network types and the "nowhere denseness" of function sets representable by fuzzy systems with a bounded number of rules. These findings underscore the practical limitations.

Key Results

  • Neural Networks:
    • Three-layered feedforward networks with semilinear hidden units can approximate any continuous function on a compact domain with arbitrary accuracy (supremum norm).
  • The number of hidden units can be estimated based on characteristics like the modulus of continuity, Lipschitz constant, or Jacobian derivative of the function.
  • For specific network types (e.g., Heaviside perceptrons, Gaussian RBFs), the best approximation operator is not continuous, leading to stability issues.
  • Fuzzy Systems:
    • Mamdani and Takagi-Sugeno (TS) fuzzy systems can approximate any continuous function on a compact domain with arbitrary accuracy.
  • For some fuzzy systems (e.g., Sugeno controllers with bounded rules), the set of representable functions is "nowhere dense," meaning they form an "almost discrete" set within the space of all continuous functions.
  • Sufficient conditions for the number of rules required for a prescribed accuracy have been derived, often showing dependence on the dimension of the input space and the desired accuracy. For example, one result suggests a number of rules proportional to $1/\epsilon$ for TS fuzzy systems, while another suggests $1/\epsilon^{1/2}$ for Sugeno controllers.

Limitations and Future Work

  • Unbounded Building Blocks: A recurring limitation across many positive results is that the number of building blocks (neurons or rules) required for universal approximation is unbounded, making direct practical implementation challenging.
  • Lack of Constructive Proofs: Early results were often existential, proving that an approximation exists but not providing a method to construct it. While later work has focused on constructive approaches, the number of units/rules can still be very large.
  • Dependence on Function Characteristics: Achieving good approximation rates often requires prior knowledge of the function's smoothness properties. If these are unknown, efficient approximation is difficult.
  • Future Work: The paper implicitly suggests continued research into finding tighter bounds on the number of building blocks, developing more efficient constructive methods, and exploring the practical implications of the identified trade-offs between accuracy and complexity. The focus on understanding the "saturation problem" (optimal approximation rate) and the "curse of dimensionality" remains a key area for future investigation.

Summary updated

BibTeX
@article{tikk2003survey,
  author = {Domonkos Tikk and László T. Kóczy and Tamás D. Gedeon},
  title = {{A survey on universal approximation and its limits in soft computing techniques}},
  journal = {Int. J. Approx. Reason.},
  year = {2003},
  doi = {10.1016/s0888-613x(03)00021-5},
}
Figure