Vocabulary for Universal Approximation: A Linguistic Perspective of Mapping Compositions
This foundational result offers a novel perspective on universal approximation for researchers in machine learning theory, potentially inspiring new compositional models.
The paper tackles the problem of representing deep neural networks as sequences of mappings by proving the existence of a finite vocabulary of O(d^2) mappings that can universally approximate any continuous function on compact domains with arbitrary error bounds.
In recent years, deep learning-based sequence modelings, such as language models, have received much attention and success, which pushes researchers to explore the possibility of transforming non-sequential problems into a sequential form. Following this thought, deep neural networks can be represented as composite functions of a sequence of mappings, linear or nonlinear, where each composition can be viewed as a \emph{word}. However, the weights of linear mappings are undetermined and hence require an infinite number of words. In this article, we investigate the finite case and constructively prove the existence of a finite \emph{vocabulary} $V=\{φ_i: \mathbb{R}^d \to \mathbb{R}^d | i=1,...,n\}$ with $n=O(d^2)$ for the universal approximation. That is, for any continuous mapping $f: \mathbb{R}^d \to \mathbb{R}^d$, compact domain $Ω$ and $\varepsilon>0$, there is a sequence of mappings $φ_{i_1}, ..., φ_{i_m} \in V, m \in \mathbb{Z}_+$, such that the composition $φ_{i_m} \circ ... \circ φ_{i_1} $ approximates $f$ on $Ω$ with an error less than $\varepsilon$. Our results demonstrate an unusual approximation power of mapping compositions and motivate a novel compositional model for regular languages.