Universal approximation property of neural networks is one of the motivations to use these models in various real-world problems. However, this property is not the only characteristic that makes neural networks unique as there is a wide range of other approaches with similar property. Another characteristic which makes these models interesting is that they can be trained with the backpropagation algorithm which allows an efficient gradient computation and gives these universal approximators the ability to efficiently learn complex manifolds from a large amount of data in different domains. Despite their abundant use in practice, neural networks are still not well understood and a broad range of ongoing research is to study the interpretability of neural networks. On the other hand, topological data analysis (TDA) relies on strong theoretical framework of (algebraic) topology along with other mathematical tools for analyzing possibly complex datasets. In this work, we leverage a universal approximation theorem originating from algebraic topology to build a connection between TDA and common neural network training framework. We introduce the notion of automatic subdivisioning and devise a particular type of neural networks for regression tasks: Simplicial Complex Networks (SCNs). SCN's architecture is defined with a set of bias functions along with a particular policy during the forward pass which alternates the common architecture search framework in neural networks. We believe the view of SCNs can be used as a step towards building interpretable deep learning models. Finally, we verify its performance on a set of regression problems. It is well-known that under mild assumptions on the activation function, a neural network with one hidden layer and a finite number of neurons can approximate continuous functions. This characteristic of neural networks is generally referred to as the universal approximation property. There are various theoretical universal approximators. For example, a of the Stone-Weierstrass theorem; is that multivariate polynomials are dense in the space of continuous real valued functions defined over a hypercube. Another example is that the reproducing kernel Hilbert space (RKHS) associated with kernel functions with particular properties can be dense in the same space of functions. Kernel functions with this property are called universal kernels. A subsequent of this theory is that the set of functions generated by a Gaussian process regression with an appropriate kernel can approximate any continuous function over a hypercube with arbitrary precision. Although multivariate polynomials and Gaussian processes also have this approximation property, each has practical limitations that cause neural networks to be used more often in practice compared to these approaches. For instance, polynomial interpolations may a model that overfits to the data and suffers from a poor generalization, and Gaussian processes often become computationally intractable for a large number of training data Bernardo et al.. Neural networks, with an efficient structure for gradient computation using backpropagation, can be trained using gradient based optimization for large datasets in a tractable time. Moreover, in contrast to existing polynomial interpolations, neural networks generalize well in practice. Theoretical and empirical understanding of the generalization power of neural networks is an ongoing research;. Topological Data Analysis (TDA), a geometric approach for data analysis, is a growing field which provides statistical and algorithmic methods to analyze the topological structures of data often referred to as point clouds. TDA methods mainly relied on deterministic methods until recently where w l,0 w l,1...... statistical approaches were proposed for this purpose;. In general, TDA methods assume a point cloud in a metric space with an inducing distance (e.g. Euclidean, Hausdorff, or Wasserstein distance) between samples and build a topological structure upon point clouds. The topological structure is then used to extract geometric information from data. These models are not trained with gradient based approaches and they are generally limited to predetermined algorithms whose application to high dimensional spaces may be challenging. In this work, by leveraging geometrical perspective of TDA, we provide a class of restricted neural networks that preserve the universal approximation property and can be trained using a forward pass and the backpropagation algorithm. Motivated by the approximation theorem used to develop our method, Simplicial Complex Network (SCN) is chosen to refer these models. SCNs do not require an activation function and architecture search in the way that conventional neural networks do. Their hidden units are conceptually well defined, in contrast to feed-forward neural networks for which the role of a hidden unit is yet an ongoing problem. SCNs are discussed in more details in later sections. Our contribution can be summarized in building a novel class of neural networks which we believe can be used in the future for developing deep models that are interpretable, and robust to perturbations. The rest of this paper is organized as follows: Section 2 is specified for the explanation of SCNs and their training procedure. In section 3, related works are explained. Sections 4, 5, and 6 are specified to experiments, limitations, and . We first describe some necessary notation in the section 2.1. In section 2.2, we discuss the barycentric subdivision and the simplicial approximation theorem. In section 2.3, we modify the barycentric subdivision in order to develop an approach that allows us to learn a subdivision of the input space into small simplexes. We then introduce a general framework for defining an SCN for regression tasks that simultaneously learns a subdivision of the input space and a piece-wise linear mapping where the linear pieces are defined on each simplex of the subdivision. We consider a dataset D = {( Let f θ denotes a mapping from the input to the output space in which θ represents its parameters. In a regression task, we wish to minimize Similarly, we assume each y (i) also lies in the standard probability k-simplex. Simplicial approximation theorem allows the approximation of continuous functions using simplicial mappings. Before stating the theorem, we borrow a few definitions from the algebraic topology literature. Definition 1. (simplicial complex) A simplicial complex K is a set of simplexes such that: 1) Every face of a simplex of K is in K. 2) The intersection of any two simplexes in K is a face of each of them. (A simplicial complex can be informally defined as a set of simplexes glued together through their faces.) Definition 2. (simplicial mapping) A mapping between two simplicial complexes is called simplicial mapping if the images of the vertices are vertices. We also use the definition of a standard subdivisioning method which is used to break a d-simplex (or any other simplicial complex) into arbitrary small simplexes with the same dimension. Figure 2(a), (b) visualize examples of BCS for a 2-simplex, and a 3-simplex. Note that i-th BCS is the of applying BCS to each simplex in the (i − 1)-th BCS. Using these definitions, simplicial approximation theorem can be stated as follows, Theorem 1. (Simplicial Approximation Theorem) Let X and Y be two simplicial complexes and f: X → Y be a continuous function. Then for an arbitrary, there exist sufficiently large k and l and a simplicial mapping g: represent the k-th and l-th barycentric subdivision of X and Y, respectively. In the appendix A, we provide a short topological proof for this theorem. Although the theorem provides a general approximation framework, its approximation is through using BCS of the input and output spaces. Each time BCS is applied, the number of simplexes is multiplied by (d + 1)! and simplexes in higher order subdivisions become flatter and flatter. This fact limits the use of this subdivision algorithm in practice. Moreover, BCS subdivides input or output space completely independent of the data. In the next section, we modify the BCS to a data-driven approach which allows us to learn a suitable subdivision given data. Apart from BCS, in TDA, building simplicial complexes from data is often based on deterministic approaches. For instance, Vietoris-Rips complex; is the set of all simplexes which their vertices are data points that their pair distances are less than a threshold. Cech complex; , is the set of all those simplexes that completely lie in a closed ball with specific radius. While these non-parametric data driven methods can extract rich topological structures of the data using mathematical tools such as persistent homology, they are not often used as standard features in machine learning algorithms immediately;. In the next section, we modify BCS to a parametric framework that allows automation of the subdivisioning process and it can be used directly during the training of an SCN. In the Algorithm 1, we have shown the process of generating a random simplex from the set of all simplexes in BCS of a d-simplex. The algorithm gives an uncommon view for identification of a simplex in the BCS which is through a set of nested simplexes. We modify this view to a data driven approach in a way that BCS is a special case of the modified version. In the Algorithm 1, for a random permutation P, This fact is visualized in Figure 2 (c), (d). N d indicates the simplex in the BCS that corresponds to P. Knowing the nested sequence uniquely determines a simplex in the BCS. Also, we note that each N i can be obtained by replacing one of the vertices of N i−1 with a new vertex inside or on the boundary (closure) of it. Thereby, since the new vertex is in the closure of N i−1, it can be represented as a convex combination of the vertices of N i−1. The weights of these convex combinations can be computed in a straightforward way as shown in the Algorithm 1. Note that these weights are specified to the BCS. To build a data driven approach initially we eliminate two restrictions of the Algorithm 1. First, we allow the number of repeats to be any arbitrary integer l rather fixing it to d. This number is later referred as the subdivision depth. Second, at each repeat, we let the weights to freely have any arbitrary values as long as they can be used as a convex combination weights. This removes the restriction of having deterministic weights specified for BSC. This modification allows us to learn the weights through an optimization process. A natural approach to make the subdivision process data-driven is to, instead of randomly sampling a simplex as in the Algorithm 1, sample a simplex with the probability proportion to the likelihood that it contains data and update the subdivision parameters accordingly. However, the number of all possible simplexes grows exponentially as l increases, thereby making the computation of all these probabilities intractable. Alternatively, we sample from data and identify the simplex in the subdivision that contains the sample and use that simplex in an stochastic optimization framework to update the subdivision towards a desired one. But how can we identify the simplex that contains a given sample? Our parameterization of the subdivisioning process using the nested sequence of simplexes along with the following lemma help to locate the input using a forward pass, Proof. x can be represented with the following convex combination which the lemma, Similar to the steps of Algorithm 1 and based on our view for identification of the target simplex through a nested set of simplexes, at the first step, a point is added inside the simplex using a convex combination of vertices of σ with weights w 1. Then lemma 1 can be used to locate the x in the σ and accordingly replace one of its vertices with the new vertex. This process is repeated with the new d-simplex up to l times to extract the simplex in the subdivision that contains x. Having the final simplex and a given cost function, parameters of the subdivision can be updated accordingly using the backpropagation and gradient descent framework. The procedure is formally shown in the Algorithm 2. We refer the general procedure described in Algorithm 2 to as automatic subdivision. Note that the barycentric subdivision can be a particular outcome of the automatic subdivisioning. Algorithm 1 Generating a simplex in barycentric subdivision of a d-simplex Algorithm 2 One gradient step in automatic subdivisioning of a d-simplex using one data sample Set N j+1 = N j with k-th vertex replaced with u Set w x as convex combination weights of x represented with vertices in N j+1 As theorem 2 states, any continuous function from a simplicial complex to another can be approximated with a simplicial mapping from BCSs of the input space to BCSs of the output space. In the last section we explained how we can subdivision the input space through the automatic subdivision process where BCS was a particular outcome. In this section, we develop SCNs to parameterize a class of simplicial mappings with trainable values on vertices of the input space subdivision and it is defined linearly on the d-simplexes of the subdivision using the evaluations at its vertices, ing a piece-wise linear simplicial mapping. Parameters of this simplicial mapping are then optimized for function approximation or a regression tasks. We leverage a same technique used in the previous section to parameterize the SCN output. Recalling our initial assumption that inputs lie in a d-simplex σ = [v 0, ..., v d] (v 0 representing the origin and other v i are the standard basis vectors), a given input x can be represented with the following convex combination, In the previous section, we showed that how the position of x can be found in σ through the subdivisioning process. SCN's output at x is calculated using the values of its mapping at the vertices of σ and added vertices during locating x. Simplicial mapping at the m-th added vertex is defined recursively using its preceding vertices. Assuming that the m-th added vertex represented as h m = d i=0 w m,i u i, where u i are vertices of the preceding simplex in the nested sequence of simplexes used to locate x and w m,i are its corresponding convex combination weights, the value of the simplicial mapping at h m is defined as, In other words, f (h m) is defined using a convex combination of f (u i) with the same weights, added with a bias which is a function of h m. A geometrical view of equation 2 for a 2-simplex is shown in the Appendix C. Using our proof of simplicial approximation theorem in the appendix A, it is straightforward to show that as long as we consider each b m is an arbitrary function of the h m, the simplicial mapping holds the universal approximation property. In our experiments, however, we used a primitive model for biases and defined them as constant parameters. We will empirically show that even this simple model for biases can complicated simplicial mappings and accurate approximations. All in all, an SCN is defined using the mentioned process (Figure 1 visualizes a general architecture). Parameters that should be learned are bias function parameters, and the weights that we used to subdivision the input space. All these parameters can be updated using the backpropagation algorithm. Another point that must be noted here is that, as shown in Figure 1, inputs to h 2,..., h l are not specified. Even though we described how to obtain the value of these inputs using lemma 1, the order that the vertices of the preceding simplex are combined is not specified. We refer to the policy on the ordering of the vertices used to fed to the next convex combination as the SCN's network policy. Specifying the depth, network policy, and the bias functions fully determines the architecture of an SCN. To train an SCN, the derivative of the loss function over mini-batches is taken with respect to the weights and the bias function parameters, and these parameters are updated using a gradient descent approach such as stochastic gradient descent, or. General training process for an SCN is shown in the Algorithm 3. Note that after updating weights of the network, for each hidden node, a projection of weights is used such that their summation is equal to 1. This projection can be avoided through use of logits and the Softmax function in parameterizing the weights. Algorithm 3 training procedure for a general SCN bias function, and weight params), P (network policy), Extract j and update w x using x, S, and lemma 1 project w m on the standard d-simplex end for In TDA, Persistent homology methods are commonly used to extract features that are robust to perturbations of the input;. A range of works use these features in a feed-forward architecture. For instance, in , persistence landscape, a topological summary of data, is used to develop persistent layers. These layers are used in a neural network architecture along with convolutional layers and the ing architecture is applied to the problem of music tagging , and multi-label classification. A similar approach is applied in for the time series classification. introduces TopologyNet, an architecture that uses a persistent homology method for 3D biomolecular structures to extract features suitable for convolutional layers. proposes a trainable layer to learn suitable representation from persistence diagram of the data. This layer which extracts topological signatures from the data is used along with a common neural network architecture and their approach achieved the state-of-the-art in a specific task on classification of social network graphs at the time. Although aforementioned methods try to improve the performance of neural networks through using topological scenarios, the TDA geometrical perspective vanishes as they are aligned with commonly used architectures. In addition, a specific persistent homology method is applied for a determined task. SCNs are single-model architectures that can be trained with the common forward and backward passes. In addition, no specific persistent homology is used to extract the topological geometry of the inputs, which enables its generalization to other domains. We perform regression tasks in order to evaluate the performance and the complexity of functions that SCN can learn. Mean squared error was used as the loss function in all the experiments. In some cases, an SCN with a few number of parameters can estimate a function better than a neural network with fully connected layers even with around 10 times more parameters. In the appendix B, with a straightforward derivation, we also show that how does an SCN without a hidden unit reformulates the linear regression problem. As a primary experiment, we approximate sum of three Gaussian functions with an SCN with a depth of 4 and constant parameters as the biases. The ing simplicial mapping and the learned subdivision is shown in Figure 3. We compare the performance of using an SCN in the problem of learning particular structures to the obtained by a neural network with fully-connected layers and ReLU activations. This is a more general experiment done in to learn the absolute value function. The experiment was used in to show the limitations of specific activation functions for neural networks in learning some of the basic functions. Here, we show that SCN can learn more complicated structures even with constant parameters as its bias functions. Models are trained using with learning rate 0.001, and a same mini-batch size. Figure 4 represents the comparison. More details about the experiments, and a binary classification experiment on the MNIST dataset can be found in the appendix F. here, to backpropagate through the SCN's architecture it is required to store only d out of d + 1 vectors and their function evaluations, which were used to extract the last hidden node and evaluate its function value, latest convex weights for the input in the forward pass, and an array of integers with a length of l indicating the order that nodes were removed during the forward pass. Storing these values is enough for the gradient computation of the network parameters. Interestingly, it is not needed to store the weights of the network and function evaluations at the previous nodes as they all can be extracted with these information (proof in the Appendix E). This approach trades the cost of memory with an additional computational cost and can be helpful in training very deep SCNs. In some conditions, the bias function for a hidden node may outputs high norm vectors. In these conditions, output may not be close to a smooth curve. Accordingly, SCN's output not behave well in practice and potentially overfits to data. In case of using a conventional neural networks, to increase the stability of the output, one approach is to enforce Lipschitz constraints Anil et al. In some cases, input weights to a hidden node might converge to degenerate values with the value one in one position and zero elsewhere. In these cases, the corresponding layer does not change the learned subdivision and it may be assumed as a redundant layer. We refer to this phenomena as weight drifting. In situations that we have a deep SCN architecture with higher than the true required capacity, these layers with a bias value close to zero may be helpful to automatically adjust the capacity of the model and prevent SCN from overfitting. Throughout this work we assumed that inputs lie in a given d-simplex. The assumption was used just for the sake of presentation. It can be assumed that samples lie in any given simplicial complex, not a specific d-simplex. The vertices of any simplex in the simplicial complex that a sample falls in can be used as the primary nodes in the network. Choosing an appropriate network policy for SCNs may be assumed as a challenging task in different domains. In our experiments, we observed that even simple policies a proper function approximation. In fact, in one dimensional case, a direct use of the Stone-Weierstrass theorem can be used to prove that SCNs are universal approximators even with random policies and fixed weights. In our experiments, the sensitivity of SCNs to the choice of their bias function observed to be larger than the network policy. In this work, we have used techniques from topological data analysis to build a class of neural network architectures with the universal approximation property which can be trained using the common neural network training framework. Topological data analysis methods are based on the geometrical structure of the data and have strong theoretical analysis. SCNs are made using the geometrical view of TDA and we believe that they can be used as a step towards building interpretable deep learning models. Most of the experiments in the paper are synthetic. More practical applications of the paper is considered as an immediate continual work. Moreover, throughout this work, bias functions of the simplest kinds (constant parameters) were used. We mentioned earlier that a bias function may be an arbitrary function of its input to keep the universal approximation property of SCNs. A natural idea is to use common neural network architectures as the bias function. In this case, backpropagation can be continued to the bias function parameters as well. This is also considered as another continuation of this work. We provide a short topological proof of the approximation theorem we used in main text. Some mathematical precision is dropped throughout the proof. (v) is less than δ (proof is shown in figure 6). So, for each v ∈ V, there exist a w ∈ W such that St(v) ⊂ f −1 (St(w)). We define the simplicial map g such that g(v) = w. Also, note that f (St(v)) ⊂ St(w). Now we prove that g approximates f as desired. Let σ ∈ X (k) be a simplex in A. Let v 1, v 2,..., v p denote the vertices of this simplex. For any x ∈ σ and a vertex v i, i ∈ {1, 2, ..., p}, x is in the. Using the last note in the previous paragraph, we have x ∈ ∩ p i=1 St(g(v i)). This fact means that f (x) lies in the simplex that its vertices are We now extend the definition of g for all non-vertex elements of X. Let x ∈ |X| be a non-vertex element represented as a convex combination of a number of vertices of V as x = Σt i v i. We define g(x) as, Straightforward steps can be used to prove that g is a continuous simplicial mapping. Using the facts in the last two paragraphs, we conclude that for each x ∈ |X| and a simplex σ ∈ X containing x, both f (x), and g(x), lie in the simplex with vertices {g(v)} v∈σ. Due to the initial choice of l, we know that diameter of this simplex is less than, which means sup x∈X f (x) − g(x) <. In case that an SCN has no hidden node (no subdivisioning process), it can be viewed as linear regression reformulation. A real valued linear function f: Assume a data matrix X ∈ R N ×d of N samples within ∆ d, and their corresponding output in a vector y. We formulate the linear regression problem with training a weight w that minimizes ||Xw − y|| We represent the coefficients of representing samples in X as a convex combination of v 0,..., v d in a matrix C ∈ R N ×(d+1) with a rank of at most d, where i-th row indicates the corresponding coefficients for i-th sample. Then the linear regression problem can be reformulated as, where f is a (d + 1) dimensional vector representing the function value at v i as its i-th element. With a straightforward computation, One can verifies that the optimal w or f can be computed from the optimal value of the other one. Figure 7: A geometrical view of how does equation 2 evaluates the simplicial mapping at m-th added point using its preceding vertices u i. A same convex combination of u i used to generate h m is applied to the corresponding f (u i). This value added with a bias term determines f (h m). x can be represented with the following convex combination which the lemma, In contrast to; , no separation of input into blocks is needed for SCNS to extract outputs of the previous layers. Retrieving the values for previous in SCN is a of the fact that knowing all weights, all vertices except one, and the ing vector of a convex combination is enough to extract the missing vertex. Formally, let x =. Assume an SCN with a depth of l. Given the SCN's last layer weights w l, the bias functions b 1,..., b l, and its network policy P, the following algorithm shows that knowing the last d hidden nodes, their function values, and an array indicating the order of vertices that was removed during the forward pass to locate x, is enough to extract all the previous function values, hidden nodes, and also the weights. For simplicity of the algorithm, u 0,..., u l+d is used as indicators for v 0,..., v d, h 1,..., h l with the same order. Algorithm 4 Retrieving preceding layers and parameters for the backward pass of an SCN given u l+d, u l+d−1,..., u l+1, f (u l+d), f (u l+d−1),..., f (u l+1), and convex weights w x of representing the input x as the convex combination of u l+d, u l+d−1,..., u l, array a = [a 1, ..., a l−d] of integers storing the indices of u i were removed during the forward pass with the exact order. Extract w l−j as the convex combination weights of representing u l+d−j using u l+d−j−1,..., u l−j Extract w (u l+d−j−i) l−j, (∀0 ≤ i ≤ d) (element of w l−j that is assigned to u l+d−j−i) using the network policy P, and a l−d−j. Update w x to the convex combination weights of x represented using u l+d−j−1,..., u l−j, u l−j−1 j+ = 1 until j = d − 1 We provide the details of the experiments in the main text as well as of a binary classification experiment on MNIST as a primary proof of concept for practical usages of SCNs. In all the three toy experiments, the neural network consisted of two fully connected layers with 300 and 2 hidden neurons respectively. ReLU activations was used for both layers. The SCN model had a depth of 4. Accordingly, the network had 4 bias functions which all were constant parameters. A learning rate of 0.001, mini-batches of size 100 were used. The network policy was random. Thereby, preceding nodes were assigned randomly to the next convex combination weights (recall the fact that in one dimensional case, SCNs are universal approximators even with a random policy and fix convex combination weights. Thereby the optimization can be done through their biases only). In the sum of Gaussians experiment, inputs lied in a 2-simplex with vertices,, and as the way that SCNs are presented throughout the paper. Similarly, in the one dimensional case inputs lied in the interval (1-simplex). To provide an observation that SCNs can be used in practice, we did a primary experiment on the MNIST data set. The aim was the binary classification of zeros and ones. We lessened the dimensionality of the data to 20 using PCA. We compared SCN to a simple logistic regression, and a neural network with the same architecture used in our synthetic experiments. Logistic regression can be seen as an SCN without any hidden nodes followed by a Sigmoid. We used a single unit SCN where its bias function was again a single constant parameter. Models were trained using the binary cross entropy loss and a same learning rate and mini-batch size were used in training the models. The performance is shown in the Figure 8 and the test accuracy and the number of parameters are shown in the Table 1. Although the performance of the SCN with a single hidden unit is not as good as the neural network with fully connected layers, SCN could improve the accuracy of logistic regression by around 7% with adding a single hidden node to its architecture. Scaling up the SCN architecture to higher dimensional spaces is considered as a continuation of the paper.
A novel method for supervised learning through subdivisioning the input space along with function approximation.