Two-hidden-layer Feedforward Neural Networks are Universal Approximators: A Constructive Approach
Rocio Gonzalez-Diaz Miguel A. Gutiérrez-Naranjo Eduardo Paluzo-Hidalgo
cs.LG math.AT stat.ML

1
.001



Universal approximation theorem by simplicial approximation
Paluzo-Hidalgo E., Gonzalez-Diaz R., Gutiérrez-Naranjo M. A.

mode = title]Two-hidden-layer Feed-forward Networks are Universal Approximators: a Constructive Approach 

                      










1]Eduardo Paluzo-Hidalgo[orcid=0000-0002-4280-5945]
[1]

epaluzo@us.es
[URL]https://personal.us.es/epaluzo
1]Rocio Gonzalez-Diaz[orcid=0000-0001-9937-0033]


rogodi@us.es
[url]https://personal.us.es/rogodi
[1]Department of Applied Mathematics I, School of engineering, University of Seville, Seville, Spain

2]Miguel A. Gutiérrez-Naranjo[orcid=0000-0002-3624-6139]
magutier@us.es
[URL]http://www.cs.us.es/ naranjo/
[2]Department of Computer Science and Artificial Intelligence, School of engineering, University of Seville, Seville, Spain

[cor1]Corresponding author








It is well-known that artificial neural networks are universal approximators. The classical existence result proves that, given a continuous function on a compact set 
embedded in
an n-dimensional space, 
there exists a one-hidden-layer feed-forward network that
approximates the function. 
In this paper, a constructive approach to 
this problem
is given for the case of a
continuous function on triangulated spaces.
Once a triangulation of the space is given, a 
two-hidden-layer feed-forward network with a concrete set of weights
is computed.
The 
level
of the approximation depends on the refinement of the 
triangulation.













Universal Approximation Theorem Simplicial Approximation Theorem Multi-layer feed-forward network Triangulations 



[
    [
    December 30, 2023
=====================









§ INTRODUCTION

One of the first results in the development of neural networks is 
the Universal Approximation Theorem
<cit.>. This classical result shows that any  continuous function on a compact set in ℝ^n can be approximated by a multi-layer feed-forward network with only one hidden layer and non-poly­nomial activation function (like the sigmoid function).
It is well-known that 
this result has
two important drawbacks for 
its practical use: firstly,
the width of the hidden layer grows exponentially and, 
secondly,
the proofs developed in <cit.>
do not provide a practical algorithm for building such a network.

Bearing these results in mind, many researchers are paying attention to theoretical aspects of the current success of neural network architectures and searching
for bounds for the depth and width of such networks and the possibility 
that they act
as universal approximators (see, e.g., <cit.> among many others).


Undoubtedly,
the use of many hidden layers is a big contribution to the success of deep learning architectures <cit.>, but instead of exploring the power of depth, recently several studies have made interesting contributions 
about
the power of width <cit.>. To sum up, 
these works
show that there exist continuous functions on compact sets that
cannot be approximated by  
any
neural network if the width of the layers is not larger than a bound, regardless of the depth of the network. In <cit.>, the authors constructively proved  that single-hidden-layer feed-forward networks with fixed weights are universal approximators for univariate functions, and they provided a step-by-step construction. However, as the authors claimed, 
not all continuous multivariate functions can be approximated by such neural networks. Their case of study could be considered somehow a particular case of our approach for the 1-dimensional case. 

Other interesting research line on the expressive power of neural networks follows an algebraic approach. In <cit.>, sum product networks are explored and tensor properties are studied in <cit.>. A different perspective was introduced in <cit.> where "deep polynomial neural networks" (where the activation function is a polynomial exponentiation) are considered.

In this paper, we provide an effective method for finding the weights of a two-hidden-layer
feed-forward network which approximates 
a given continuous 
function between two triangulable 
metric spaces.
Let us remark that the method is constructive, and it only depends on the desired level of approximation to the 
given function.

Our approach is based on a classical result from algebraic topology. Roughly speaking, our result is 
based on
two observations:
Firstly, triangulable 
spaces
can be “modelled” 
using
simplicial complexes, and a continuous 
function between two triangulable spaces can be approximated by a simplicial map
between simplicial complexes. Secondly,
a simplicial map between simplicial complexes can be “modelled” as a two-hidden-layer feed-forward network.

Let us remark that the classical result Universal Approximaton Theorem is valid for all compact set on ℝ^n and our 
results presented here are valid for triangulable 
 spaces.
However, triangulable 
 spaces
are  
common in real-world problems. 

Furthermore, we would like to highlight that an advantage of our approach from a theoretical and practical point of view is that it can be useful to solve real-world problems that can be modeled by triangulable spaces.




The paper is organized as follows: In Section <ref>, the preliminary notions about multi-layer feed-forward networks and simplicial complexes are provided. Then, in Section <ref>, a concrete architecture 
of such networks
that acts equivalently to a given simplicial map is given. In Sections <ref> and <ref>, we extend the 
Simplicial Approximation Theorem and Universal Approximation Theorem, respectively. The complexity of the architecture is studied in Section 6.
A specific example is described in Section <ref>. Finally, conclusions are given in Section <ref>.






§ BACKGROUND


In this section, we recall some notions about artificial neural networks and simplicial complexes.



 §.§ Multi-layer 
Feed-forward Networks 




Artificial neural networks are 
inspired 
by 
biological networks of alive neurons in a brain. The number of different architectures, algorithms, and areas of application has recently grown in many directions. In general, a neural network can be formalized as a 
function
N_ω,Θ: ℝ^n →ℝ^m 
that
depends on a set of weights
ω and a set of parameters Θ 
which involves the description of activation functions, layers, synapses between nodes (neurons), and whatever other consideration in its architecture. A good introduction to artificial neural networks can be found in <cit.>.

In this paper, we focus on one of the simplest classes of artificial neural networks:  multi-layer feed­for­ward networks. They
consist of three or more  fully connected layers of nodes:
an input layer, an output layer, and one or more hidden layers. Each node in one layer has an 
activation function and it 
is connected with
every node in the following layer. The next definition formalizes this idea.



A multi-layer feed-forward network defined on a real-valued n-dimensional space is a 
function
N: ℝ^n →ℝ^m  such that, for each x ∈ℝ^n, N(x) is 
the composition of
k+1
functions

    N(x) =  
    f_k+1∘ f_k∘…∘   f_1  (x)

where k∈ℤ is the number of hidden layers,  
k≥ 1, and, for  1≤ i≤ k+1,
 f_i:  ℝ^d_i-1→ℝ^d_i  
 is defined as 
  
    f_i(y) =ϕ_i(W^(i); y;b_i)
 being
 W^(i)
 a real-valued d_i-1× d_i matrix,
 (that is, W^(i)∈ M_d_i-1× d_i),
 b_i∈ℝ^d_i  the bias term, and ϕ_i 
 a bounded,  continuous, and non-constant function (called activation function). 
 Notice that d_0=n, d_k+1=m and d_i∈ℤ, 1≤ i≤ k, is called the width of the i-th  hidden layer. 



Next, we rewrite one of the most important theoretical results of multi-layer feed-forward networks adapted to our notation.



Let A be any compact subset of ℝ^n 
and let C(A) be the space of real-valued continuous functions on A.
Then, given any ϵ>0 and any function g∈ C(A), 
there exists a multi-layer feed-forward network N:ℝ^n→ℝ
approximating g,  that is,
||g- N||<ϵ. 



As far as we know, the existing
proofs 
of
this theorem are non-constructive. See <cit.>
where it is claimed 
that 
there exists a one-hidden-layer feed-forward network N:ℝ^n→ℝ, defined as N(x)=f_2∘ f_1 (x) with f_1(y)= ϕ_1 (W^(1); y;b_1) and f_2(y)=W^(2) y, 
approximating 
g, that is,
||g- N||<ϵ,
but  no general algorithm to build N is given. 
In this paper, we will provide a constructive approach to
Theorem <ref> through a two-hidden-layer feed-forward network.
The most important restriction to our approach is that our result is valid for triangulable spaces
instead of compact ones but, as pointed out above, 
triangulable spaces cover
most of the real-world problems.



 §.§ Simplicial Complexes

In this subsection, we recall the main result used in this paper based on a 
classical theorem from algebraic topology
known as the Simplicial Approximation Theorem. 
For a further comprehension of the field, <cit.> can be consulted.

Simplicial complexes are a data structure widely used to represent topological spaces. They are 
versatile mathematical objects
that decompose a given
topological space into pieces 
called simplices.


Let v_0,v_1,…,v_i be  i+1 affinely independent points in ℝ^n 
(being i≤ n).
An i-simplex, σ = (v_0,v_1, …, v_i), is the convex set

    {x∈ℝ^n   |  x= ∑_j=0^i λ_j v_j   λ_j≥ 0
    ∑_j=0^i λ_j=1
    }.

The points v_0,v_1,…,v_i are the vertices of σ. 
The dimension of σ
is i.
We say that 
σ' is a face of σ
(denoted as 
σ'≼σ)
if σ' is an i'-simplex, with i'≤ i, and whose vertices are also vertices of σ. 


When several simplices are joint together, a more complex structure called simplicial complex is built. The following definition exhibits the way simplices can be glued together to obtain such a simplicial complex. 


    A     simplicial complex K is a 
    collection of simplices  such that:
    
        
  * σ∈ K and 
        σ'≼σ
        implies σ'∈ K;
        
  * σ, μ∈ K implies σ∩μ is either empty or a face of both.
    
If such collection is finite, then K is a finite simplicial complex.    


  The  underlying space of K, denoted by |K|, is the union of the simplices of K together with the topology inherited from the ambient Euclidean space where the simplices are placed.
  
  
    A simplex σ∈ K is maximal if it is not a face of any other simplex in K.
The dimension of K, denoted by (K)  is the largest  of the dimensions of its maximal simplices. The simplicial complex K is pure if  
    all the maximal simplices have  dimension equal to (K).
    
  
  
  
  A subcomplex L of K is a simplicial complex such that L⊆ K.
  The skeleton of K is a particular subcomplex of K. Let us remark that the 0-skeleton of K is its vertex set.
  
  
  The subcomplex of K consisting of all the simplices of K of dimension j or less is called the j-skeleton of K and it is denoted by K^(j). 
    
 


Next, we recall 
the concept of the star of a simplex σ in a simplicial complex K. Intuitively, it is the subcomplex of K whose maximal simplices share σ as a face.


    Let K be a simplicial complex and σ a simplex
    of K. The star of σ in K, denoted by (σ), is defined as:
   
    (σ) = {μ∈ K  |  ∃ ξ∈ K σ≼ξμ≼ξ}.



As said above, simplicial complexes are combinatorial data structures used to model topological spaces. A way to obtain a refined model from an existing one is to subdivide  it into small pieces so
that the result is  topologically equivalent to the 
former.
 

Let K and K' be simplicial complexes. It is said that K' is a subdivision of K if:

    
  * |K|=|K'|;
    
  * σ' ∈ K' implies that there exists σ∈ K such that σ'
    is contained in
    σ.



The barycentric subdivision is a concrete example of subdivision of simplicial complexes.
Using that the barycenter of an
 i-simplex σ= (v_0… v_i) is 
    b(σ) = ∑_j=0^i1/j+1v_j,


the definition
of barycentric subdivision of a simplicial complex arises in a natural way.



Let K be a simplicial complex. The
barycentric subdivision of the 0-skeleton of K is defined as the set of vertices of K, that is, K^(0) = K^(0). Assuming
we have K^(i-1), which denotes the barycentric subdivision of the (i-1)-skeleton of K, K^(i) is built by adding the barycenter of every i-simplex as a new vertex and connecting it to the simplices that subdivide the boundary of such i-simplex.
The barycentric subdivision of K, denoted by K, is K^(u) where u is the dimension of K.
The iterated application of barycentric subdivisions is denoted by ^t K where t is the number of iterations.








Let us see now how the “geometric size” of the simplices of a simplicial complex can be measured.


    Let K be a  finite simplicial complex. The diameter of a simplex σ in K is defined as 
    
    δ(σ) =    max{ ||x-y||   x,y
        σ}
 
        and  the  mesh of K is defined as 
    
    m(K) = max{δ(σ)   σ∈ K }.




 Given a simplicial complex K and  a real number ϵ>0, there exists an integer  t>0 such that m(^t K)≤ϵ.



Let us now think about maps between simplicial complexes. These maps can be considered as extensions of simpler maps defined 
between the corresponding vertices of two given simplicial complexes. Interestingly, such maps can be considered as approximations of continuous functions defined on the underlying topological spaces that the simplicial complexes are modeling. Let us formalize these notions.



    Let K and L be two simplicial complexes. A vertex map is a 
    map
     φ:K^(0)→ L^(0)
     with the property that 
     for every simplex σ in K there exists a simplex μ in L such that the vertices of σ map to vertices of μ.


A vertex map φ can be extended to a continuous function φ_c:|K|→ |L| in the following way.


Let K and L be two  simplicial complexes and let  φ:K^(0)→ L^(0) be a vertex map.
The simplicial map φ_c  induced by φ is defined as follows.
Let x∈ |K|. Then there exists an i-simplex  σ=(v_0,…,v_i) in K and numbers 
    λ_j≥ 0 
    such that
     
    ∑_j=0^i λ_j=1  
     x= ∑_j=0^i 
     λ_j v_j.
 Then

    φ_c(x) = ∑_j=0^i  λ_j  φ(v_j).



Any vertex map φ induces a simplicial map φ_c, but if we want that 
map to be a simplicial
approximation of a continuous function
between the underlying spaces of
two simplicial complexes K and L, a restriction
on the star of each vertex of K must
be added.


 
    Let K and L be simplicial complexes and  g:|K|→ |L| a continuous 
    function.
    A simplicial map φ_c: |K|→ |L| induced by a vertex map φ: K^(0)→ L^(0) is a simplicial approximation of g if 
    g(| (v) |)⊂ | (φ(v)) |

    for each vertex v of K.


The Simplicial Approximation Theorem 
ensures the existence of simplicial maps that approximate continuous functions as close as we want.




If g:|K|→ |L| is continuous then there is a sufficiently large integer t>0 such that φ_c:|^t K|→ |L| is a simplicial approximation of g.


Theorems <ref> and <ref> 
are key results in their respective fields. Our aim in this paper is to consider Theorem <ref> as a pillar to obtain a 
constructive approach to
Theorem <ref>. Roughly speaking, the idea is to consider a simplicial approximation 
of a continuous function
between two simplicial complexes.
Such a simplicial approach is characterized through
a vertex map which can be expressed as a neural network. 
Besides,
the simplicial approximation can be chosen in such a way that it approximates the continuous function
between the underlying spaces of two simplicial complexes. Since the parameters of the neural network can be effectively obtained from the vertex map, this method provides a constructive way to find a neural network
that
approximates a continuous function between
the underlying spaces of two simplicial complexes.

Following that aim, let us formalize the relationship between topological spaces and simplicial complexes.


    A triangulation of a topological space X consists of a simplicial complex K and a homeomorphism τ:X→ |K|.
    We say that the triangulation is finite if K is finite. We say that X is (finitely) triangulable if such (finite) triangulation exists.


The spaces that can be triangulated by simplicial complexes (see <cit.>) are 
compact, locally contractible spaces
that can be embedded in ℝ^n for some n. Let us remark that the Universal Approximation Theorem (Theorem <ref>) is valid for any compact subset of ℝ^n, regardless 
of whether
they are locally contractible or not. Not all compact sets in a metric space are locally contractible (see <cit.>).
Nevertheless, as far as we know, non-locally contractible spaces are very odd in ℝ^n and this technical topological property has no practical application in real-world problems. Therefore, we can say that the results proved on triangulable spaces are true on a large amount of current neural network problems. Besides, 
we will restrict ourselves to finite pure 
triangulations. 
The other cases could be obtained using homotopies. 
For example, given a sphere and a circumference that intersect transversely, the sphere can be triangulated  using 2-simplices, and the circumference can be covered by 2-simplices obtaining a finite pure triangulation of a space homotopic to the initial one (see Figure <ref>). 



Next, we  extend the definition of a mesh of a simplicial complex in the following way.


    Let X be a  triangulable  
    metric
    space and (K,τ) a finite triangulation of X. The mesh of X induced by (K,τ) is defined as 
    
    m̃_(K,τ)(X) = max{δ̃(σ)  |  σ∈ K }

    where 
  
    δ̃(σ) = max{   d_X(x,y)
      
       |  x = τ^-1(a),  y = τ^-1(b);  
      a,b∈σ}

    is the extended diameter of a simplex.













§ MULTI-LAYER FEED-FORWARD NETWORKS AND SIMPLICIAL MAPS


In this section, we will show that 
simplicial maps can be modelled via multi-layer feed-forward networks in a straightforward way. 

In the following theorem, we will compute a two-hidden-layer feed-forward network to
model a simplicial map φ_c: |K|→ |L| where 
K and L are
finite pure simplicial complexes.  
This is not an important constraint in our case, since our final aim is to design a multi-layer feed-forward network that approximates a continuous function between finitely triangulable spaces. 



Let us consider
 a simplicial map φ_c:|K|→ |L| 
 between the underlying space of two finite pure simplicial complexes K and L.
 Then a two-hidden-layer feed-forward network N_φ 
  such that φ_c(x) =  N_φ(x) for all x∈ |K| can be explicitly defined.



 
Let us assume that (K)=n and (L)=m.
Besides, 
let {σ_1,…σ_k} be the maximal n-simplices of K,  where σ_i = [v_0^i,…,v_n^i] for all i; and let {μ_1,…,μ_ℓ} be the maximal m-simplices of L,
 where μ_j = [u_0^j, …, u_m^j] for all j. 

Let us consider a multi-layer feed-forward network N_φ with the following architecture: 


(1) An input layer composed by d_0=n neurons; 


(2) a first hidden layer composed by d_1=k· (n+1) neurons; 


(3) a second hidden layer composed by d_2=ℓ· (m+1) neurons; and


(4) an output layer with d_3=m neurons. 


Then, let N_φ = f_3∘ f_2∘ f_1 being f_i (y)= ϕ_i (W^(i);y;b_i), i=1,2,3. 

Now, the idea  is to encode
the simplicial complexes involved in the mapping in the hidden layers of the multi-layer feed-forward network. Firstly, a point x in ℝ^n is transformed into a k · (n+1) vector. This vector can be seen as the juxtaposition of k vectors of dimension n+1, one for each of the k simplices in K. Each vector of dimension n+1 represents the barycentric coordinates of x with respect to the corresponding simplex. 
The matrix W^(1)∈ M_k(n+1)× n and the bias term b_1 can be obtained from the barycentric coordinates relations
as follows.
Firstly, 

    W^(1) = 
    [ W^(1)_1;       ⋮; W^(1)_k ]


where W^(1)_i∈ M_(n+1)× n 
is:

    [ v_0^i     ⋯ v_n^i;     1     ⋯     1 ]^-1
    =
    [ W^(1)_i       |     B_i ]

being {v_0^i, …, v_n} the set of vertices of the maximal simplex σ_i of K, and second, b_1 ∈ℝ^n+1 is:

    b_1 = [ B_1;   ⋮; B_k ].

The function ϕ_1 is then defined as:
 
    ϕ_1 (W^(1);y;b_1)=W^(1)y+b_1.


The matrix of weights W^(2)∈ M_ℓ(m+1)× k(n+1) between the first and the second hidden layer of N_φ
encodes the vertex map
φ.
The first hidden layer is composed by k · (n+1) neurons that correspond to the vertices of the maximal simplices of K.
The second hidden layer is composed by  ℓ· (m+1) neurons that correspond to the vertices of the maximal simplices of L.
The matrix W^(2) is composed by values zeros and ones. On the one hand, an element of W^(2) has value 1 if 
the corresponding vertices 
in
K and L are related by
the vertex map φ, and, on the other hand, it has  value 0 if
they are not related by φ. Then,  

    W^(2) = (W^(2)_s_1,s_2)
 
where
    W^(2)_s_1,s_2 = {[ 1 φ (v^i_t)=u^j_r ,;                   0 ].

being s_1 = j(r+1) and s_2 = i(t+1) for i=1,…, k; j = 1,…, ℓ; t =0,…,n; and  r = 0,…, m.
The bias term b_2 is the null vector.
Then, the function ϕ_2 is defined as:

    ϕ_2 (W^(2);y;b_2)=W^(2)y.


The output of the second hidden layer can be seen as the juxtaposition of ℓ vectors of dimension m+1, one vector for each simplex in the simplicial complex L. Each of these vectors represents the barycentric coordinates of φ_c(x) with respect to the corresponding simplex in L. 
In the next step, only vectors whose all
coordinates are greater than or equal to zero are considered. This condition encodes the simplices of L to which φ_c(x) belongs. 
Then, ϕ_3(W^(3);y;b_3) maps
the barycentric coordinates of φ_c(x) with respect to each maximal simplex of L to which φ_c(x) belongs, to the Cartesian coordinates of φ_c(x). Specifically,  

    W^(3) = 
    [ W^(3)_1       ⋯ W^(3)_ℓ ]∈ M_m×ℓ(m+1) ,


being W^(3)_j=
[ u_0^j     ⋯ u_m^j ]; and
 b_3 is the null vector.

Finally,
ϕ_3 is defined as:


    ϕ_3 (W^(3);y;b_3)=∑_j=1^ℓz^jψ(y^j)/∑_j=1^ℓψ(y^j)

for
y = 
[ y^1;   ⋮; y^ℓ ]∈ M^ℓ· (m+1),
with
z^j = W^(3)_j y^j and  ψ(y^j) = 1 if all the coordinates of y^j are greater than or equal to 0 and ψ(y^j)=0 otherwise. 

 
The 
particular choice
of ϕ_3 and ψ is motivated by the use of the barycentric coordinates. 
Let us observe that the barycentric coordinates vary with respect to the maximal simplex considered to compute them and that the barycentric coordinates are computed from the  coordinates of the vertices of the maximal simplex considered. Besides, maximal simplices can share common vertices. Then, the map
ψ is used to determine if a given input is located in a specific simplex. The map ϕ_3 is used to normalize the result in case that a point belongs to more than one simplex.



Summing up, Theorem <ref> establishes that a two-hidden-layer feed-forward network can act equivalently to a simplicial map. 
The  architecture and the specific computation of the parameters of the network are  provided in the proof of the theorem.





§ SIMPLICIAL APPROXIMATION THEOREM EXTENSION


In this section, 
we provide an extension of the Simplicial Approximation Theorem together with an explicit algorithm to compute a simplicial approximation “as close as desired” to a given continuous function g:|K|→|L|  between the underlying spaces of
two simplicial complexes K and L. 

The first observation is that the Simplicial Approximation Theorem (Theorem <ref>) refers to any continuous function. 
Nevertheless, continuity is a property of functions between  topological spaces, not necessarily metric spaces. The next result introduces the concept of closeness between simplicial approximations and continuous functions. 



 Given ϵ>0 and a continuous function g:|K|→ |L| between the underlying spaces of two simplicial complexes K and L, there exist t_1,t_2>0 such that φ_c: |^t_1K|→ |^t_2L| is a simplicial approximation of g and ||g-φ_c||≤ϵ.



By Theorem <ref>, there exists t_2 such that m(^t_2L)≤ϵ. Then, by Theorem <ref>, there exists t_1 such that φ_c:|^t_1K| →  |^t_2L| is a simplicial approximation of g: 


    
    | K|[r, "g"]          | L |
    
    K [u, hook] [d, ""]     L [u, hook] [d, ""] 
    ^t_1K  [d,hook]    ^t_2L [d,hook] 
    |^t_1K |[r, "φ_c"]                  |^t_2L |



Besides, ||g-φ_c||≤ϵ because m(^t_2L)≤ϵ.





  
  A continuous function g:|K|→ |L|  between the underlying spaces of two simplicial complexes K and L, and an integer t where ^t k satisfies the star condition:
  for each v∈^t K^(0) there exists w∈ L^(0) such that
   g(|st(v)|)⊆ |st(w)|.
 
  A vertex map φ that induces simplicial approximation φ_c of g.
   
  vertex v∈^t K^(0)
  
  
  Choose w∈ L^(0) such that g(|st(v)|)⊆ |st(w)| and define
  φ(v):=w.
   
 Computing a vertex map that induces a simplicial approximation
  
  





Algorithm <ref> is inspired in the proof of the Simplicial Approximation Theorem given in <cit.> and computes a 
vertex map φ: ^t K^(0)→ 
L^(0) from which we can define 
the 
simplicial approximation 
 φ_c: |^t K| → |L|
of a continuous function g:|K|→ |L|.



 Given a continuous function g:|K|→ |L| and ϵ>0, a two-hidden-layer feed-forward network N such that ||g- N||≤ϵ can be explicitly defined.



By Proposition <ref>, there exists a simplicial approximation φ_c of g such that ||g-φ_c||≤ϵ, that can be computed using Algorithm <ref>. Then,
by Theorem <ref> there exists N_φ such that φ_c= N_φ. 





§ UNIVERSAL APPROXIMATION THEOREM EXTENSION



In the previous sections, we have proved that a continuous function between triangulable 
spaces can be approximated by using the Simplicial Approximation Theorem. In this section, using the extension of the Simplicial Approximation Theorem given in Proposition <ref>, we provide a constructive version of the Universal Approximation Theorem that approximates any continuous function (under some specific conditions) arbitrarily close. 


 Let 
 (K,τ) be a finite triangulation of a metric space X.
  
 For all ϵ>0 there exists t>0 and γ>0 such that if m(^t K)≤γ then m̃_(^t K,τ)(X)≤ϵ.


Let us consider 
a,b_0∈ |K|. 
Then, a∈σ_0 
for some maximal simplex σ_0∈ K.
If b_0 belongs to σ_0 then ||a-b_0||≤δ(σ_0) and
d_X(x,y_0)≤δ̃(σ_0), being
x=τ^-1(a) and y_0=τ^-1(b_0).
Otherwise, we repeat the reasoning with K.

Now, 
a and b_0
can belong to the same simplex  in K or not. If they belong to  the same simplex in K, 

write 
b_1=b_0.
If not, take a new point 
b_1
such that 
a,b_1
∈σ_1 and σ_1∈σ_0.
Therefore, ||a-b_1||
≤δ(σ_1)≤δ (σ_0). Besides,  d_X(x,y_1)
≤δ̃(σ_1)≤δ̃(σ_0)
being x=τ^-1(a) and y_1=τ^-1(b_1)
This process can be iterated:  ||a-b_t||
≤δ(σ_t) ≤…≤δ(σ_1)≤δ (σ_0) and d_X(x,y_t)≤δ̃(σ_t)≤…≤δ̃(σ_1)≤δ̃(σ_0),
being x=τ^-1(a) and y_t=τ^-1(b_t). By this, we have defined a sequence {b_i}_i=0^t that converges to a.
Therefore, given ϵ>0, there exists t such that d_X(x,y_t)≤ϵ, being
x=τ^-1(a) and y_t=τ^-1(b_t). 
Let us suppose, without loss of generality, that δ̃(σ_t)=m̃_(^t K,τ)(X). Then, we can consider γ = m(^t K).



Given ϵ>0 and a finite triangulation (K,τ) of a metric space X, 
there exists t such that 
    m̃_(^t K,τ)(X)≤ϵ.



By Theorem <ref> there exists t' such that m(^t'K) ≤γ. Then, by Proposition <ref>, there exists t such that m̃_(^t K,τ)(X) ≤ϵ.



Given two continuous function g_1 and g_2 between two metric spaces X and Y, we denote sup{d_Y(g_1(x),g_2(x)) |  x∈ X} also by ||g_1-g_2||.
Now, given a continuous function g between two finitely triangulable metric spaces X and Y, there exists
a  simplicial approximation φ_c 
“arbitrarily close” to g.



Let X and Y be two finitely triangulable
metric
spaces, g:X→ Y a continuous 
function,
and ϵ>0. Then, there exist two finite triangulations (K,τ_K) and (L,τ_L) of X and Y, respectively, 
and a simplicial approximation φ_c: |^t_1K|→ |^t_2L|
such that 
||g-φ̃_̃c̃||≤ϵ
being φ̃_̃c̃=τ^-1_L∘φ_c∘τ_K.



 First, by Corollary <ref>, there exists t_2 such that m̃_(^t_2L,τ_L)(Y)≤ϵ. Next, by Theorem <ref>, there exists t_1>0 and a vertex map φ: (^t_1K)^(0)→ (^t_2L)^(0) such that φ_c:|^t_1K|→ |^t_2L| is a simplicial approximation of
 τ_L∘ g∘τ^-1_K. 
 Take
 into account that |^t_1K|= |K| and |^t_2L|= |L|.
Finally, 
since 
m̃_(L,τ_L)(Y)≤ϵ then
||g-φ̃_̃c̃||≤ϵ.
Below, a diagram that schematizes the proof:

    X [d, "τ_K"] [r, "g"]       Y [d, "τ_L"]            
    | K |[r, "φ_c"]    | L |
    
    K [u, hook] [d, ""]          L  [u, hook] [d, ""] 
    ^t_1K      ^t_2L    
    
    (^t_1K)^(0)[u, hook] [r, "φ"]          (^t_2L)^(0)[u, hook]




Finally, we reach the main result of this section: Given a continuous function
g between two finitely triangulable spaces X and Y, we can obtain two finite simplicial complexes K and L associated to them, and a 
multi-layer feed-forward network
between the underlying spaces of K and L  which “approximates” g. 



 Given a continuous function g:X→ Y between two finitely triangulable metric spaces X and Y and finite triangulations (K,τ_K) and (L,τ_L) of, respectively, X and Y,
a two-hidden-layer feed-forward network 𝒩 such that ||g-Ñ||≤ϵ, being Ñ=τ_L^-1∘ N∘τ_K, can be explicitly defined.


By Proposition <ref>, there exists a simplicial approximation φ_c 
such that 
||g-φ̃_̃c̃||≤ϵ.
Finally, by Theorem <ref>, there exists 𝒩 such that 𝒩 = φ_c in all the domain. 





§ COMPLEXITY OF THE ARCHITECTURE OF THE NETWORK


In previous sections, we have provided a constructive approach to build neural networks to approximate continuous functions as close as desired. Now, let us study
how the “complexity” of the 
architecture of the neural network
increases in terms of the number of neurons in each hidden layer. 


    The complexity of a
    neural network is the maximum of the widths of its hidden layers. 


First, let us observe that we can infer an upper bound for the amount of barycentric subdivisions of a simplicial complex needed to reach an specific 
mesh.



Let us consider a finite pure simplicial complex K. Let (K)=n and let 0<ε<m(K).
If 

    t ≥log(m(K))-log(ε)/log(n+1)-log(n)

then m(^t(K))≤ε.




Let us observe that m(^t(K))≤ m(K)·(n/n+1)^t. Then, 

    m(^t(K))≤ε⇐
    m(K)·(n/n+1)^t≤ε⇔
    t≥log(ε/m(K))/log(n/n+1).







Let us recall that, given two finite pure simplicial complexes 
K and L with, respectively, k and ℓ maximal simplices, being, respectively, (K)=n and (L)=m,
the width of  the first  and  the second hidden layer of the neural network 𝒩 described in Theorem <ref> 
is, respectively, 
k·(n+1) and
ℓ·(m+1).
Let us describe how the complexity of 𝒩 increases with the iterated applications of the barycentric subdivisions. Let us consider, without loss of generality, that we apply one
barycentric subdivision to K.
Then, the width of the first hidden layer increases from k·(n+1) to k ·(n+1)!·(n+1).



 Let us consider a simplicial approximation ψ_c:|^t_1 K|→ 
|^t_2 L| of a continuous function,  being K and L two finite pure simplicial complexes of dimension n and m, and with k and ℓ maximal simplices, respectively.
The complexity of the two-hidden-layer feed-forward network N_ψ
is

    C(t_1,t_2)=max{k((n+1)!)^t_1(n+1), ℓ((m+1)!)^t_2(m+1)}.







We can relate the modulus of continuity of the
input function g and the modulus of continuity of the simplicial approximation
φ_c between triangulations of the input spaces. Let us recall the definition of modulus of continuity of a function.


The modulus of continuity of a continuous function g:X→ Y 
between two metric spaces X and Y 
is given by:

    ρ(δ,g)=
     sup{d_Y(g(x),g(y)) |  d_X(x,y)≤δ}.

In particular we have that:

    d_X(x,y)≤δ⇒ d_Y(g(x),g(y))≤ρ(δ,g).





Now, let us study the complexity of the resulting network in terms of the mesh
of the triangulation  and on the modulus of continuity of the considered function.


Let g: X→ Y be a continuous function between two triangulable metric spaces with modulus of continuity ρ(δ, g)≥ 0. Let us suppose that there exist finite triangulations (K,τ_K) and (L,τ_L) of X and Y, respectively. Then, there exists a two-hidden-layer feed-forward network N 

such that 
ρ(δ,Ñ)≤ 2ρ(δ,g) and ||g-Ñ||≤ρ(δ,g)/2
being Ñ=τ^-1_L∘ N∘τ_K.




Let ϵ=ρ(δ,g)/2.
By Theorem <ref>, there exists a two-hidden-layer feed-forward network N such that 
||g-Ñ||≤ϵ.
Consider x,y∈ X such that d_X(x,y)≤δ.
then,

    [                                   d_Y(Ñ(x),Ñ(y)); ≤  d_Y(g(x),Ñ(x))+
    d_Y(g(x),g(y))+d_Y(g(y),Ñ(y));                    ≤  2||g-Ñ||+ρ(δ,g)
    ≤ 2ρ(δ,g). ]









§ EXAMPLE



In this section, 
we show a concrete example 
of a multi-layer feed-forward network approximating a continuous function between two triangulable spaces.The following diagram illustrates the example:

    B^3  [r, "g"] [d, "τ_K"]      B^2   [d, "τ_L"]          
    
        < g r a p h i c s >
    [r, "φ_c"]    
        < g r a p h i c s >
    
    
    K [u, hook]      L [u, hook] 
    
    K^(0)[u, hook] [r,"φ"]      L^(0)[u, hook]


Let us consider the n-dimensional ball B^n={x∈ℝ^n |  1≥ ||x||}.
Then, a triangulation of B^3 is the simplicial complex K whose maximal simplex is a a tetrahedron with set of vertices K^(0)={(0,0,0), (1,0,0), (0,1,0), (0,0,1)} 
and a homeomorphism τ_K:B^3→ |K|
whose inverse
is defined
for any point
P∈ |K|
as follows:

    P'=τ^-1_K(P)=λ(P)·(P-(1/4,1/4,1/4))

where λ(P)
is 
the quotient |OB|/|OA|
being point O=(0,0,0), point A the intersection
of the boundary of the tetrahedron with the 
line that goes through O and P, and point B the intersection of such line with the sphere 
S^2={x∈ℝ^3 |  1=||x||}.
See Figure <ref> for a similar homeomorphism  in the 2-dimensional case.


Besides, let us consider the continuous function
g:B^3→ B^2 where
g:B^3→ B^2 is the projection
given by g:(P_x,P_y,P_z)→ (P_x,P_y)
being P=(P_x,P_y,P_z)∈ B^3. 
Besides,
B^2 can be triangulated by  the simplicial complex L whose maximal simplex is the triangle
with set of vertices L^(0)={(0,0), (1,0), (0,1)} and the homeomorphism τ_L:B^2→ |L|, whose inverse is 

    P'=τ^-1_L(P)=λ(P)·(P-(1/4,1/4))

where P∈ |L| and λ(P) is computed in a similar way than above.  See Figure <ref>. 





Now, let us approximate g with a two-hidden-layer neural network. First,
let us observe that a simplicial approximation φ_c of
τ_L∘ g∘τ^-1_K is given by the vertex set 
φ:K^(0)→ L^(0)
defined as φ((0,0,0)) = (0,0), φ((1,0,0))=(1,0), φ((0,1,0))=(0,1), and φ((0,0,1))=(0,1). Once the simplicial approximation is computed, we can determine the specific two-hidden-layer neural network N_φ
that acts equivalently to φ_c. Concretely, the architecture of N_φ is composed by an input layer with 3 neurons, a first hidden layer with 4 neurons, a second hidden layer with 3 neurons, and an output layer with 2 neurons. The weights and bias can be computed following the proof of Theorem <ref>:

    [ 0 1 0 0; 0 0 1 0; 0 0 0 1; 1 1 1 1 ]^-1=
    [ -1 -1 -1  1  1;  1  0  0  1  0;  0  1  0  1  0;  0  0  1  1  0 ]

Then, 
W^(1)=[ -1 -1 -1;  1  0  0;  0  1  0;  0  0  1 ]
and
b_1 = [ 1; 0; 0; 0 ].


    W^(2)=
    [ 1 0 0 0; 0 1 0 0; 0 0 1 1 ]


    W^(3) = 
    [ 0 1 0; 0 0 1 ]



In this 
straightforward
example, the spaces
B^3 and  B^2 are approximated by just one 3-simplex and one 2-simplex, respectively. Therefore, m̃_(K,τ_K)(B^3) and m̃_(L,τ_L)(B^2) are upper bounded by the size of B^3 and B^2, respectively. If we want  a better approximation  to g, we should apply the barycentric subdivision to K and L, respectively. Doing that,
 we would  obtain six maximal 2-simplices in L, and  sixteen maximal 3-simplices in K. Hence, the architecture of the neural network will consist of 64 neurons in the first hidden layer, and 18 neurons in the second hidden layer.




§ CONCLUSION

In this paper, we have provided an effective method to build a multi-layer feed-forward network which approximates a continuous function between triangulable spaces. The main contribution of the paper is the proof that the weights can be exactly 
computed without any training process. 
Although the homeomorphisms between the triangulable spaces and the simplicial complexes can be hard to find and  the classic theorem for approximations through
neural networks is valid for compact sets and our result is only valid for triangulable spaces,
most of the real-world problems are covered by our result 
and, therefore, approximations to continuous functions 
through
neural networks can  effectively be built. Besides,
our method can be considered a suitable and powerful tool for the approximation 
of continuous functions on triangulable
spaces. Two of the 
main advantages of the proposed method are: (1)
knowing
a priori how many hidden neurons are needed 
to reach the desired accuracy; and (2) 
no need for a training process.















cas-model2-names








figs/edu.jpg
Eduardo Paluzo-Hidalgo
He received the degree in Mathematics in 2017 and the MSc in Logic, Computation, and Artificial Intelligence in 2018 from the University of Seville. He is currently a PhD student and researcher in the Department of Applied Math I at the University of Seville, Spain. He is a member of the Combinatorial Image Analysis group. His research interests are primarily machine learning and computational topology.




figs/ro2.jpeg
Rocio Gonzalez-Diaz

Associate Professor in the Department of Applied Math I at the University of Seville since 2004. Head of the Computational Image Analysis group since 2010. Principal Researcher of the Spanish project Computational Algebraic Topology for Computer Vision (MTM2015-67072-P Project) from 01-2016 to 12-2018. 





figs/Miguel_2.jpeg
Miguel A. Gutiérrez-Naranjo
Associate professor in the Department of Computer Science and Artificial Intelligence at the University of Seville, Spain. His research interest includes topics related to Artificial Intelligence and Natural Computing, both from a theoretical and practical point of view. He has coauthored more than 40 scientific papers in these areas.





