Computational topology on neural networks: from the data to the model

Eduardo Paluzo Hidalgo Tesis doctoral Computational Topology on Neural Networks: From the data to the model Advisors: Rocío González Díaz Miguel Ángel Gutiérrez Naranjo Eduardo Paluzo Hidalgo Computational Topology on Neural Networks: From the data to the model Abstract: Machine learning is drawn from a dataset that needs to be explained. Following this aim, a model is described to make predictions. These datasets can be of very different nature, as well as the problems they pose: supervised or unsupervised classification, regression... In this work, we have studied, from a computational topology point of view, two machine learning’s pillars: the datasets considered as sets of 𝑛-dimensional points, and a specific model, artificial neural networks. we have applied topological data analysis techniques to classify literary trends from a literature dataset and to reduce the size of datasets controlling the loss of information, and, finally, we have developed a new neural network architecture based on simplicial complexes and the maps defined between them, and we have also proved certain properties such as that the new family of neural networks are universal approximators and robust to "adversarial examples". Resumen: En aprendizaje automático partimos de un conjunto de datos que queremos explicar. Con ese objetivo, se diseña un modelo que permite hacer predicciones. Estos conjuntos de datos pueden ser de muy distinta naturaleza, así como los problemas que plantean: clasificación supervisada o no supervisada, regresión... En este trabajo, hemos estudiado, desde el punto de vista de la topología computacional, dos pilares del aprendizaje automático: los conjuntos de datos vistos como un conjunto de puntos 𝑛 -dimensionales; y un modelo en concreto, las redes neuronales artificales. Más concretamente, hemos aplicado técnicas propias del análisis topológico de datos para clasificar tendencias literarias de un conjunto de datos literario, hemos estudiado cómo reducir un conjunto de datos de manera que podamos controlar la información que perdemos y, finalmente, hemos desarrollado una nueva arquitectura de red neuronal basada en complejos simpliciales y en las aplicaciones que se definen entre ellos, demostrando que esta nueva familia de redes neuronales son aproximadores universales y robustas ante "adversarial examples". Me siento en deuda con mis padres y mi pareja por darme un entorno feliz en el que me siento querido. Con mi profesora de instituto Mari Carmen, que me engatusó y encauzó mi vida a las Matemáticas. Con Rafael Ayala y José Antonio Alonso, que fueron pilares indiscutibles durante la carrera, además de unos profesores maravillosos. Con mi tutor Miguel Ángel que me ha aportado su sabiduría y comprensión siempre que la he necesitado. Y, sobre todo, con mi tutora Rocío que me tendió la mano, me dio un campo de investigación, las herramientas y su apoyo. Gracias a todos. Contents Contents ix 1 Introduction 1 2 A bit of history of... 5 2.1 Neural networks ................................. 5 2.2 Computational topology ............................ 6 2.3 The confluence of the two fields ........................ 8 2.4 The story of this thesis .............................. 8 3 Background 13 3.1 Computational topology ............................ 13 3.2 Topological data analysis ............................ 17 3.3 Neural networks ................................. 20 Part I: Applying Computational Topology Techniques to the Data 23 4 Towards a Philological Metric 25 4.1 Introduction ................................... 25 4.2 Word embedding ................................ 26 4.3 Description of the methodology ........................ 27 4.4 Experiment .................................... 28 The context: Spanish Golden Age literature . . . . . . . . . . . . . . . . . . 28 The corpus and the preprocessing step . . . . . . . . . . . . . . . . . . . . 30 Application of the word2vec algorithm . . . . . . . . . . . . . . . . . . . . 31 The Vietoris-Rips filtration and the bottleneck distance . . . . . . . . . . . 31 Results ...................................... 31 5 Representative datasets 33 5.1 Introduction ................................... 33 5.2 Representative datasets ............................. 34 Proximity graph algorithm ........................... 36 5.3 The perceptron case ............................... 37 5.4 Applying persistent homology to infer the representativeness of a dataset 42 5.5 Experimental results: the perceptron case ................... 43 Two interlaced solid torus dataset ....................... 43 1 Introduction 2 7: Roughly speaking, algebraic topology uses tools from abstract algebra to study topological spaces. Then, with the need of computing the algorithms that emerged in algebraic topology, researchers started to develop a new field called computational topology as an union between algebraic topology and computer sciences. Finally, with the study of data a group of techniques emerged forming the field topological data analysis. 8: Persistent homology is a computational topology tool to study topological features that persist across an increasing parameter. 9: Neural networks are usually described as graphs that are organized by layers. There exist different types of architectures depending on how these layers are organized, connected and the kind of operations that are computed. One classic architecture is the multi-layer feed-forward neural network which is composed of fully dense layers such that its neurons are connected to all the neurons of the next layer. 10: Simplicial complexes are topological spaces built gluing combinatorial elements such as vertices, edges, triangles... Then,themappingsdefinedbetweenthese simplicial complexes are called simplicial maps. results from algebraic topology, and using tools from computational topology and topological data analysis 7 . Datasets are one of the main elements of neural networks, they are used to feed and to train them. We have considered datasets as the first element to study, shaping the first part of the thesis called Applying computational topology techniques to the data. Using an exotic application far from computer science as illustration, we have shown how the topology of a given dataset can be studied to describe its nature and infer new information. In Chapter 4, we have analyzed the literary production of three of the greatest exponents of the Spanish Golden age literature. Using a dataset composed of sonnets, we obtained an embedding using a word2vec neural network architecture. Then, persistent homology 8 was applied to the embeddings to be able to define some kind of distance criteria. By this, we could observe that the topology of the dataset let us infer information about the difference between the literary trends of the three poets. After analyzing data by itself, we studied the relationship between datasets and neural networks. As previously mentioned, neural networks are commonly trained using huge datasets and this leads to long training time and high computational costs. To overcome this issue, we have studied some aspects of the information encoded in datasets as 𝑛 -dimensional points and have shown how persistent homology can be applied to reduce the size of the huge mass of data commonly used to train neural networks. By this, in Chapter 5, we have measured and provided results of how the output of neural networks changes when deleting instances of a dataset. Using persistent homology, we characterized qualitative features of data encoded in multisets called persistence diagrams. Then, we deleted instances of the dataset keeping the persistence diagram close (respect to the bottleneck distance) to the one of the full dataset, ensuring that the qualitative features remain. The idea is that if these qualitative features are kept while reducing the size of the dataset, the learning of the neural network will be similar but using less data. Finally, once we have studied datasets and their relationship with neural networks, we focused on neural networks capabilities and deficiencies in the second part of the thesis entitled Applying computational topology techniques to the model. A classical result of neural networks is the Universal Approximation Theorem. Roughly speaking, neural networks with just one hidden layer 9 can approximate any continuous function. This result can be considered the theoretical foundation of the power of neural networks. However, it has some deficiencies such as that it is not known how big will be the hidden layer nor if it is easy to train, and if it is constructive or not. Put simply, it states the approximation capabilities but not the way to reach the desired approximation. Considering these issues, we have translated the problem into computational topology and made used of another classical result of algebraic topology called the Simplicial Approximation Theorem. It claims that given any continuous function between two simplicial complexes 10 , there exist a simplicial approximation of it. In this thesis, we have provided a new neural network using the classic multi-layer feed-forward network but whose weights are determined by a simplicial map between a triangulated representation of the spaces (see Chapter 6). This neural network is called simplicial-map neural network and can be applied to approximate continuous functions and for classification problems, providing a new version of the classical Universal Approximation Theorem using the Simplicial Approximation Theorem. 1 Introduction 3 Moreover, simplicial-map neural networks are suitable tools to face another issue of neural networks mentioned before, adversarial examples. As the problem has been translated into computational topology using simplicial complexes and simplicial maps, it is possible to understand and trace the output of a neural network and to interpret the values of the internal parameters of the neural network. Taking advantage of that, in Chapter 7, we have studied the effect of applying subdivisions to the triangulated spaces as well as refining simplicial-map neural networks to provide results about their robustness against adversarial examples, providing new insights to a long trajectory problem. In summary, we have studied neural networks from their different components and lacks. We have studied the topology of datasets, the way the size of datasets affects to neural networks, and a reinterpretation of multi-layer feed-forward neural network architecture that let us to study two fundamental problems, the approximation capabilities and the robustness issue. Besides, we have provided a bridge between two fields, neural networks and computational topology, which are the foundations for a promising new line of research. 1: An internal representation is a representation of the outside world to ourselves. In the case of neural networks, it depends on the kind of problem it is facing. For example, in image classification, it can be an internal representation of the concept of an edge, a nose or a tree. A bit of history of... 2 2.1 Neural networks . . . . . . . . 5 2.2 Computational topology . . . 6 2.3 The confluence of the two fields8 2.4 The story of this thesis . . . . 8 In this chapter, we provide a brief introduction to the main topics related to this thesis from a historical point of view to understand the shoulders of giants ∗ where we find support and motivation to face the problems we posed at the beginning of this thesis. 2.1 Neural networks The aim of machine learning is to find models that learn by themselves to solve a specific problem. Generally, the learning procedure is based on an algorithm (based on local search) to solve an optimization problem to find the optimum parameters of the model. The word model comprises all the different methods used such as support vector machines, nearest neighbors search, decision trees, neural networks... However, we will focus on neural networks. Figure 2.1: The first models of neural networks were biologically inspired. Roughly speaking, a neuron is composed of dendrites, a nucleus, an axon and terminal axon. Neurons transmit information in electric impulses by sending neurotransmitter, a chemical that travels across a synapse and reach other neurons. When a neuron receives information from other neuron or neurons, depending on a threshold, the received impulse is transferred to its adjacent neurons. The neural network concept arises by computational models of biological learning, i.e, trying to decipher and imitate the way by which a biological brain learns. In 1943, Warren McCulloch and Walter Pitts [1] discussed the first neural network based on the biological nerve cells (see Figure 2.1). The earliest models were linear, i.e, given some input values 𝑥1, . . . , 𝑥𝑛∈ℝ𝑛 , the output would be a linear combination 𝑥1·𝑤1+···+ 𝑥𝑛·𝑤𝑛 where 𝑤𝑖 are usually called weights. Then, replicating the threshold of the biological neurons while transmitting an impulse, a threshold is applied to that linear combination. However, these weights were set by the human, i.e., not trained. Later in 1949, Donald Hebb wrote the book The Organization of Behavior [2] constituting a big effort and the first work linking psychology and neural networks, and talking about networks with internal representations of the concepts they learn 1 . In 1958, the perceptron was introduced by Rosenblatt [3] and it was the first model whose weights were trained, i.e, there was some kind of learning. Modern versions of the linear learning neural network models like the one introduced by McCulloch and Pitts, or the ∗ Quoting Isaac Newton in a letter to Robert Hooke in 1675: "If I have seen further it is by standing on the shoulders of Giants". 2 A bit of history of... 6 2: The XOR problem is a simple nonlinearly-separable problem based on four points split in two classes 𝐴= {(0,0),(1,1)} and 𝐵={(0,1),(1,0)} . If we represent these four points, we can see that the two classes can not be separated with a straight line which is the output of classical linear models. 3: Intuitively, let us consider that we have a set of marbles and we want to classify them depending on two features, if they are mottled or striped, and if they are red or blue. One way to represent it is to have all the 22 possibilities,i.e., mottledred, mottled-blue, striped-red, stripedblue. However, distributed representation states that we can use one neuron to distinguish between striped and mottled marbles connected to other neuron specialized in distinguishing colors, that is just 2 neurons instead of 22. 4: Back-propagation is a widely used algorithm for training multi-layer feedforward neural networks. Roughly speaking, based on the gradient of a cost function that measures the goodness of the output, the error is spread backwards the neural network, adjusting the parameters. 5: Inreal applications suchasimagerecognition the graph of the neural network have many layers, i.e., the graph is deep. This approach of deep neural networks is usually called deep learning. 6: Training a neural network consist of the update of different parameters called weights in order to solve some kind of problem (classification, regression...). 7: This library can be found in https:// pytorch.org/ 8: This library can be found in https:// www.tensorflow.org/ 9: This library can be found in https:// keras.io/ perceptron of Rosenblatt are still widely used [4,5]. However, linear models have many limitations such as the famous XOR problem 2 . In fact, neural networks have an up and down history in terms of expectations and different waves can be established such as cybernetics (1940s-1960s, [1–3]), connectionism (1980s-1990s, [6,7]), and deep learning (2006-today, [8,9]). From the just one neuron models of the cybernetics wave and the work of Donal Hebb in the 1940s, in the 1980s emerged the connectionism, claiming that a large number of neurons networking together can achieve better results. An important concept from connectionism is distributed representation [10] which states that features can be shared by different inputs so they should be involved in the description of different inputs 3 . Another achievement of connectionism was the use of back-propagation 4 to train deep neural networks with internal representations [11]. Both, the first and the second wave of neural networks finished with disappointing as they did not fulfill the high expectations. In the case of connectionism the lack of competitive computational resources made neural networks difficult to train. Later, with the emergence of pre-trained neural networks [12] and GPUs [13], neural networks could be efficientely trained, leading to the begining of the third wave, deep learning. Nowadays, neural networks can be considered as computational graphs that are hierarchically organized in layers5. The number of layers, neurons (also called units), activation functions... configure the architecture of the neural network. This architecture is not universal in the sense that there exist plenty of possibilities and each architecture can define different kind of functions and can be trained 6 with different algorithms. Some types of deep learning neural networks are convolutional neural networks, recurrent neural networks, and generative adversarial networks. To sum up, neural networks models have evolved through time. From just one neuron that was not trained, to huge models with massive layers that are trained during days and that can classify images with high accuracy and develop very different kind of tasks. Finally,fromanimplementationpoint of view,therearedifferentpowerful libraries such as Pytorch7 and Tensorflow8 . There exist another version of the last one with a more friendly to user way of implementation called Keras9 . Some introductory reference to neural networks implementations are [14,15]. 2.2 Computational topology Prior to talking about computational topology, we want to introduce the history of different concepts from topology that are relevant to us and to the development of computational topology. For a detailed presentation of the history of topology, [16] can be consulted. The beginning of topology can be found in 1895 with the publication of Analysis Situs by Poincaré. In its origins, topology was regarded as having two main branches, a set theoretical topology that treated spaces as sets of points and combinatorial topology introduced by Dehn and Heegard in [17]. In the latter, spaces were described by combinatorial elements such as cells or simplexes. Later, Brouwer introduced new ideas to the so called homotopy theory between 1910 and 1912 such as the Simplicial Approximation Theorem proof using the Lebesgue Covering Theorem. 2 A bit of history of... 7 10: It seems that Betti groups were already mentioned by Emmy Noether in 1925 during a talk in the Göttinger Mathematische Gesellschaft. 11: There are a group of methods in computational topology to study data that are included in the subfield of topological data analysis. Persistent homology is considered one of them. 12: The Geometry Understanding in Higher Dimensions (GUDHI) library can be found in https://gudhi.inria.fr/. 13: The Giotto’s documentation can be found in https://giotto-ai.github. io/gtda-docs/0.4.0/library.html. Using Brouwer’ results, Alexander established the topological invariance of homology [18,19], that was one of the Poincaré open questions. Later, Betti groups were firstly mentioned in Vietoris’ paper [20] 10 . It is during the late twenties when algebraic topology began even if the term was not mentioned until 1936 by Lefschetz. From the thirties to the fifties, homology theory books evolved from a mixture between algebraic and geometric arguments to a standard use of chain complexes, and exact sequences appeared for the first time in 1941 in [21]. Now, let us take a 50 year leap and talk about computational topology. Computationaltopologyis arecent fieldthat, even withitsshort trajectory, has plenty of applications. Computational topology finds its origin in the need for algorithms to compute concepts from algebraic topology and was born as a combination of topics in geometry, topology, and algorithms. Therefore, it can be considered a subfield of topology that bridges computer science and algebraic topology. One of the main tools of computational topology is persistent homology which is a method to study qualitative features encoded by homology that persist across multiple scales. As fas as we know, the term “Computational Topology" wasfirstly used in [22], wherethe authors claimedin theabstractthatsuch a new research area should be referred to as “Computational Topology". However, early works appeared in the 90s independently and following different directions. Some of this works can be found in the so called size theory [23–25] that studies shapes using size functions that depend on the context. Later, Robins [26] introduced the term persistent Betti numbers and proved their stability with respect to the Hausdorff distance. Apart from its origin, we can highlight three pieces of work that have defined modern persistent homology 11 . Persistent homology measures topological features of shapes and functions. A compact representation (persistence diagrams) of these features and an effective way to compute them were introduced in [27]. In [28], the authors showed that the homology of a filtered simplicial complex is the standard homology of a graded module over the polynomial ring, introducing tools from commutative algebra. In [29], the robustness of persistence diagrams to changes in the input data in terms of the bottleneck distance was proved. Let us remark that there exist different works that are not considered the birth of computational topology, but that are highly related such as [30–32]. From an implementation point of view, there are two main libraries. The first one is the GUDHI library 12 which is an open source C++ library with a Python interface. It has got different modules for different type of data structures such as cubical complexes or simplicial complexes and a variety of topological descriptors such as the Bottleneck distance, persistence diagrams... The second one is a topological machine learning toolbox in Python called Giotto-tda [33] 13 which has the advantage of its easy pipeline implementation with other machine learning libraries such as Scikit-learn . For a detailed presentation of different libraries for Topological Data Analysis tools we recommend [34]. 2 A bit of history of... 8 14: Colah’s blog https://colah.github. io/ is mainly devoted to interpretability of neural networks. Besides, the post entitled “Neural Networks, Manifolds, and Topology" was the first motivation for our work. 2.3 The confluence of the two fields Even if these two fields seem to be far from each other, in [7], Minsky and Papert already used topological invariants to describe predicates that could be recognized by a perceptron. In this chapter, we want to highlight several works where computational topology and neural networks are involved. In the last years, the confluence of computational topology and machine learning (specifically neural networks) is wide. The first resource we bumped into was the Christopher Olah’s blog 14 . One of his posts describes that multi-layerfeed-forwardnetworks canbeconsideredascompositions of homeomorphisms letting to interpret the layers of a neural network as different transformations of the space where the input data is embedded inordertoobtainaseparablerepresentationofit. Thisis reallymeaningful and a huge step to interpretability, even if the post is just a preliminary work, we are sure it can be considered a boost to the confluence between computational topology and neural networks. Since then, computational topology has been a source to study many aspects of neural networks. The works [35,36] are examples of applications of persistent homology to characterize unknown properties of neural networks such as the number of needed neurons or the characterization of adversarial examples. There, persistent homology is directly applied defining a suitable filtration to obtain experimental results that let the authors define bounds for the number of needed neurons depending on the homology of the dataset and to distinguish instances of the datasets that are adversarial examples, respectively. Other work related to adversarial examples is [37] where the authors found by the use of persistent homology that there exist holes in the activation graphs of certain neural networks making them sensitive to adversarial examples. Persistent homology has been also used as input for neural networks, for example, in [38] where persistence diagrams were used as topological descriptors of medical image analysis and input for convolutional neural networks. Other efforts were put in improving the synergy of persistent homology outputs and neural networks. This is the case of [39] where the authors provide a new representation of persistence diagrams called persistence codebooks that are more suitable for machine learning workflows. Finally, in [40], the authors introduced topo samplers, a topology-constrained noise sample to train generative adversarial networks, and in [41] a new neural network layer for persistence diagrams called PersLay was introduced. Computational topology methods have been applied successfully in almost every aspect of neural networks, and there are many works that we do not cite here. However, in our opinion, the relationship between computational topology and neural networks is on his infancy and we can expect plenty of new fascinating results involving them in the near future. 2.4 The story of this thesis In this section, I would like to give a more personal description of the work we have developed and my experience during these three years. 2 A bit of history of... 9 15: Part of the Sistema Nacional de Garantía Juvenil y del Programa Operativo de Empleo Juvenil 2014-2020. 16: During these three years I have been attending several congresses to divulge our results and learn from experts. The first congress I attended was the “Discrete Mathematics Days 2018" and it was before starting this thesis but we already had in mind the idea of representative datasets and I gave a talk entitled “Representative datasets for neural networks". Other congress I gave a talk in my beginings was the Dragon Applied Topology meeting in Swansea. Later, our final results on this topic were presented in Chicago. There I had the opportunity to defend a poster entitled “Reducing the size of datasets". It is a trip I look back on it very fondly because this was my first long travel alone to disseminate my work. Much later, people from Learn to Forecast (L2F) enterprise were interested in working with us and I had the opportunity to visit them in Lausanne and to incorporate a module in their Giotto library that computes persistent entropy[42], a new tool of computational topology developed by our team. 17: As previously mentioned, deep learning is associated to neural networks with many layers. Having many layers mean a big amount of parameters. As the quantity of parameters to be trained increases, the training gets more difficult and more data is generally needed. 18: A dataset is considered to be unbalanced if the size of the sample of a class is much bigger than other classes. 19: Using the concept of dominating set in graph theory we can control the bottleneck distance. Then, we inferred results that relate this distance with the accuracy that is lost when reducing the size of a dataset. 20: Before that work, Rocío and I were advisors of a final master’s project about adversarial examples made by Iván de los Santos García. The code and the document can be found in https://github.com/drexpp/ Adversarial-examples-One-pixel-attack This thesis began as a result of my encounter with one of my thesis advisors, Rocío González Díaz. I applied for a one-year-and-a-half grant for a research assistant position 15 and I started working with her. I was studying a MSc in Logic, Computation and Artificial Intelligence at the University of Seville and Rocío was highly interested in merging her main field of interest, computational topology, with the field of neural networks, especially the problem of adversarial examples which is the last chapter of this thesis. As I had some background in neural networks I started to play with these two topics. Then, I contacted Miguel Ángel Gutiérrez Naranjo that was a teacher of mine at the master degree and the team of three was complete. Our first topic was representative datasets that will be explained in detail in Chapter 5 16 . The main idea was the following. In deep learning, it is known that data is valuable 17 and it is desirable to have as much data as possible to train any model. However, the drawback appears in the form of long trainingprocesses that may take days. We didn’t think that this ravenous hunger of data was fully justified, and that other problems such as the unbalanced dataset problem 18 or the training time could be minimized reducing the size of the dataset. Then, we thought that it is not a matter of having a massive dataset but to keep the right amount to have satisfactory results. We then applied persistent homology to provide bounds for the perceptron case [43,44] of how much accuracy we loose when we reduce the size of a given dataset in a certain way 19 . Another application of computational topology techniques in classification tasks using a learning model we intended in my beginning was [45]. Then, we intended another kind of application of computational topology. In this case, the model was completely based on the bottleneck distance. This is the case of [46] where we provided a distance to distinguish between different literature trends using three Spanish poets of the golden age. These two applications that are not directly related to neural networks but to the input data. The works [45, 46] are the first part of this thesis called Applying Computational Topology Techniques to the Data. Later, I wanted to work with neural networks that are my main interest. The goal was to be able to control neural networks and erase that black box idea of them. Therefore, I wanted to reinterpret them in the context of computational topology. To do so, we used algebraic topology machinery as the Simplicial Approximation Theorem. Using simplicial approximations as the kernel of our neural networks, so we can control the neural network from a combinatorial way and use all the knowledge from computational topology. The results are described in Chapter 6and in [47]. There, we proved that this new simplicial-map neural networks are universal approximators under certain conditions, but this was not the only desirable property we were looking for. In [48], we showed that simplicial-map neural networks are robust to adversarial examples 20 . This work is explained in detail in the second part of the thesis that I called Applying Computational Topology Techniques to the Model. To end this section, I would like to talk about some side works that I’ve been involved and will not be explained in detailed in this thesis but that has been part of my process of maturation as a researcher. For the first work, I contacted another teacher of mine in the Master degree, José Francisco Quesada Moreno and I assaulted him with an idea I had during his lectures. He taught me about natural language processing. 2 A bit of history of... 10 21: The code and the document of Guillermo Aguirre’s final master’s project can be found in https://github.com/Cimagroup/ AudioVisual-EmotionRecognitionUsingTDA . 22: Haskell is one of my favourites programming languages and it was a pleasure to be able to apply it. It is a purely functional programming language. During that epoch I was starting to study computational topology, so, as a kid with a new tool, I wanted to apply it to every problem I bumped into. Therefore, I talked to Rocío and José Francisco and asked them if we could apply persistent homology to emotion recognition. Soon we were on it. As a result, in [45], we developed a naive but powerful methodology to classify emotions that I had the opportunity to explain in the 7th Workshop on Computational Topology in Image Context in Málaga. Later, it has also been the topic for Guillermo Aguirre’s masters degree I supervised with Rocío. On it, Guillermo Aguirre extended the results and methodology to videos21. Other research I was involved was devoted to the simplification of combinatorial maps and the effect on 0 -dimensional homology in the lower-star filtration providing. There, we provided an algorithm for the simplification based on merging faces but controlling the Bottleneck distance between the persistence diagrams of the original surface and the simplified one [49]. Later, I helped in a paper about well-composedness [50] where I did the implementation and experimentation of the results. I did it using Haskell22. Finally, in July 2019, I assisted to the NeEDS Modelling week in Seville. There, we formed groups and we were assigned a problem to be solved. In my case, it was about oncology imaging. It was just an opportunity to meet Beatriz Rubio Serrano who was working on rational curves. She was interested in adjusting the weights of these curves and solve with them Computational Aided Geometry Design (CAGD) problems. Soon we were working about it and developed in [51] a neural network that emulated the curves she works with inheriting its good properties but with the possibility of applying gradient descent algorithms to adjust its parameters. 2 A bit of history of... 11 Jun,2018 ······• Discrete Mathematics Days, Sevilla & [43]. Sept,2018 ······• Dragon Applied Topology, Swansea. Oct,2018 ······• VII Encuentro de Jóvenes Topólog@s, Barcelona. Jan,2019 ······• 7th Workshop on Computational Topology in Image Context, Málaga & [45]. Mar,2019 ······• [44,49]. Apr,2019 ······• Visit to Giotto-L2F, Lausanne. May,2019 ······• Geometric Data Analysis, Chicago. Jul,2019 ······• NeEDS Modelling Week, Sevilla & [47]. Dec,2019 ······• [46]. Jan,2020 ······• Seminario Rubio de Francia, Zaragoza. Jul,2020 ······• [50]. Oct,2020 ······• Shaping the future of AI in Industry, Sevilla. Dec,2020 ······• [51]. Jan,2021 ······• [48]. In this timeline all the works mentioned above are listed in chronological ordertogetherwithothercongressesandseminarsIassistedanddivulged our work. Papers (JCR) Chapters in books Congresses & seminars Q1 Q2 3 1 3 10 3 Background 18 we can define the sublevel set 𝐾(𝑎)=𝑓−1(−∞, 𝑎] which satisfies that 𝐾(𝑎) ⊆ 𝐾(𝑏)when 𝑎≤𝑏. Definition 3.2.4 (filtration) Let 𝐾 be a simplicial complex and let 𝑓:𝐾→ ℝ be a non-decreasing continuous function. A filtration K of 𝐾 is a nested sequence of subcomplexes, ∅=𝐾0⊂𝐾1⊂ ··· ⊂ 𝐾𝑚=𝐾. Such that if 𝑎1<𝑎2<··· <𝑎𝑛 are the filter function values of the simplices in 𝐾and 𝑎0=−∞then 𝐾𝑖=𝐾(𝑎𝑖)for each 𝑖. As previously mentioned, for every 𝑖≤𝑗 we have the inclusion map from 𝐾(𝑎𝑖) to 𝐾(𝑎𝑗) . Therefore, we have an induced homomorphism between 𝐻𝑛(𝐾𝑖)and 𝐻𝑛(𝐾𝑗). One example of filtration is the Vietoris-Rips filtration (see [60]). Roughly speaking, a Vietoris-Rips filtration is obtained by creating open balls centered at every point of a set of points in an 𝑛 -dimensional space. The radius of the ball gets bigger along time and those vertices whose balls intersect form new simplices. Using this idea, the filtration is built. We say that a homology class born when it appears during the construction of the filtration and we say that such homology class dies when it merges with another homology class (see Figure 3.4). So, births and deaths of all homology classes are controlled along time in the filtration. Figure 3.4: Given a set of points and a filter function 𝑓 , this is an example of Vietoris- Rips filtration. In 𝐾1 and 𝐾2 there are as 0 -homology classes as points. Then, in 𝐾3 , the 0 -homology classes merge when the balls intersect. In 𝐾3 a 1 -homology class is born but dies in 𝐾4 . Finally, a 1 -homology class is born in 𝐾4. One of the common graphical representations of births vs. deaths along time is the so-called persistence diagram which is a set of points on the Cartesian plane. A point of a persistence diagram represents a hole in a concrete dimension. Since death happens only after births, all the points in a persistence diagram lie above the diagonal axis. Furthermore, those points in a persistence diagram that are far from the diagonal axis are candidates to be topologically significant since they represent holes which survive for a long time. Definition 3.2.5 (persistent homology) The corresponding sequence of 𝑛 -homology groups connected by homomorphisms obtained from a filtration K: 0=𝐻𝑛(𝐾0) → 𝐻𝑛(𝐾1) → ··· → 𝐻𝑛(𝐾𝑚)=𝐻𝑛(𝐾) is called the 𝑛-th persistent homology of K. As a next step, the persistent Betti numbers are stored as 2-dimensional points. 3 Background 19 Definition 3.2.6 (persistence diagrams) A persistence diagram is a multiset of 2-dimensional points in the extended real plane. Let 𝜇𝑖,𝑗 𝑛 be the number of 𝑛-homology classes born at 𝐾(𝑎𝑖)and dying entering 𝐾(𝑎𝑗), we have 𝜇𝑖,𝑗 𝑛=(𝛽𝑖,𝑗−1 𝑛−𝛽𝑖,𝑗 𝑛)−(𝛽𝑖−1,𝑗−1 𝑛−𝛽𝑖−1,𝑗 𝑛), for all 𝑖<𝑗 and all 𝑛 . Then, the 𝑛 -th persistence diagram of a filtration K , denoted as 𝐷𝑔𝑚𝑛(K) , is the multiset of points (𝑎𝑖, 𝑎𝑗) with multiplicity 𝜇𝑖,𝑗 𝑛 (together with the points of the diagonal with infinity multiplicity by convention). The so-called bottleneck distance can be used to compare two persistence diagrams. Definition 3.2.7 (bottleneck distance) The bottleneck distance between two persistence diagrams 𝐷𝑔𝑚 and ] 𝐷𝑔𝑚 is: 𝑑𝐵(𝐷𝑔𝑚, ] 𝐷𝑔𝑚)=inf 𝜙:𝐷𝑔𝑚→ ] 𝐷𝑔𝑚 sup 𝛼∈𝐷𝑔𝑚 ||𝛼−𝜙(𝛼)||∞ where 𝜙is any possible bijection between 𝐷𝑔𝑚 and ] 𝐷𝑔𝑚. Let us describe now an undemanding example as an illustration of these concepts. It is composed of three different datasets. The first one samples a circumference (see Figure 3.5a), the second one is a noisy version of the previous circumference (see Figure 3.5b), and the last one samples two circumferences (see Figure 3.5c). Then, Vietoris-Rips filtration was computed using the Euclidean metric to obtain the persistence diagrams shown in Figure 3.5. The coordinates of the 2-dimensional blue and orange points of the persistence diagrams correspond, respectively, to the birth and death time of the 0 - and 1 -homology classes that show up when computing the persistent homology of the corresponding filtration. In the case of Figure 3.5d, the 1-st persistent homology 𝐻1 presents just one point that corresponds to the hole of the circumference. However, in Figure 3.5e, some points appear close to the diagonal which can be considered noise because they are components that live a short period of time. Finally, the two orange points that are further to the diagonal pictured in Figure 3.5f belong to the 1-st persistent homology 𝐻1 , and correspond to the two holes, one for each circumference pictured in Figure 3.5c. 3 Background 20 (a) A two-dimensional point cloud sampling a circumference. (b) A two-dimensional point cloud sampling a noisy circumference. (c) A two-dimensional point cloud sampling two circumferences. (d) Persistence diagram of the Vietoris-Rips filtration obtained from the set of points drawn in Figure 3.5a. (e) Persistence diagram of the Vietoris-Rips filtration obtained from the set of points drawn in Figure 3.5b. (f) Persistence diagram of the Vietoris-Rips filtration obtained from the set of points drawn in Figure 3.5c. Figure 3.5: Three persistence diagrams of the Vietoris-Rips filtration obtained from a dataset of a random selection of points belonging to a circumference and from two circumferences, respectively, with the 0 - and 1 - homology classes. The blue points represent the (birth, death) of the 0 -homology classes, and the orange points are the (birth,death) of the 1 -homology classes. Observe that in Figure 3.5f there are two orange points that are far from the diagonal corresponding to the two 1-homology classes. 3.3 Neural networks In general, a neural network can be formalized as a function N 𝜔,Θ:ℝ𝑛→ ℝ𝑚 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. The number of different architectures, algorithms, and areas of application of neural networks has recently grown in many directions. A good introduction to neural networks can be found in [61]. Although there existsmanydifferenttypeof architectures,wewillfocusonthemulti-layer feed-forward neural network. Definition 3.3.1 (adapted from [55]) Given 𝑑, 𝑘 >0 , a multi-layer feedforward network defined between spaces 𝑋⊆ℝ𝑑 and 𝑌⊆ℝ𝑘 is a function N:𝑋→𝑌composed of 𝑚+1functions: N=𝑓𝑚+1◦𝑓𝑚◦···◦ 𝑓1 where the integer 𝑚>0 is the number of hidden layers and, for 𝑖∈~1, 𝑚+1 , the function 𝑓𝑖:𝑋𝑖−1→𝑋𝑖is defined as 𝑓𝑖(𝑦):=𝜙𝑖(𝑊(𝑖);𝑦;𝑏𝑖) where 𝑋0=𝑋 , 𝑋𝑚+1=𝑌 , and 𝑋𝑖⊆ℝ𝑑𝑖 for 𝑖∈~1, 𝑚 ; 𝑑0=𝑑 , 𝑑𝑚+1=𝑘 , and 𝑑𝑖>0 being an integer for 𝑖∈~1, 𝑚 (called the width of the 𝑖 -th hidden layer); 𝑊(𝑖)∈M𝑑𝑖−1×𝑑𝑖 being a real-valued 𝑑𝑖−1×𝑑𝑖 matrix (called 3 Background 21 1: A nice website with a bunch of datasets of different kind of problems is the UCI Machine Learning Repository https://archive.ics.uci. edu/ml/datasets.php. 2: For example, in a binary classification problem, we would have two labels (1,0) and (0,1). the matrix of weights of N ); 𝑏𝑖 being a point in ℝ𝑑𝑖 (called the bias term); and 𝜙𝑖being a function (called the activation function). In the literature, many other definitions of neural networks are available. The field is continuously adding new ideas and there is not a general definition which covers all the possible approaches, but many of the problems where neural networks are applied are based on the idea of finding a set of weights and bias where the remaining features of the neural network (number of hidden layers, their dimension, and activation functions),i.e.,thearchitecture,aresettledatthebeginningofthe problem. Then, as previously mentioned, the weights and bias, i.e., the parameters are adjusted using a training (also called learning) procedure. There exists different training algorithms such as gradient-based learning, algorithms with adaptive learning rates, with second-order gradient approximation methods, back-propagation... However, we will restrict to the most known which is the stochastic gradient descent algorithm that will be introduced in Section 5.3. A dataset is a set of 𝑛 -dimensional points representing knowledge in some context. An example of a dataset can be a set of images that we want to categorize into classes or a set of measures of different aspects of a flower. There exists datasets of very different nature 1 depending on the type of problem we are facing. Given a dataset, in machine learning, we try to find a model that can generalize the underline information (or structure) of the dataset to be able to successfully classify or predict new data. Definition 3.3.2 Given a set of points 𝑋⊂ℝ𝑛 and a set of labels 𝑌⊂ℕ , a dataset is the set of pairs D={(𝑥, 𝑦) ∈ ℝ𝑛×ℕ|𝑥∈𝑋, 𝑦 ∈𝑌}. Then, a classification problem is defined as follows: Definition 3.3.3 Given a labelled dataset D⊂𝑋×𝑌⊂ℝ𝑛×ℕ , a supervised classification problem consists of looking for the model that correctly classifies D . In the case that the model is a neural network, it consists of looking for the weights and bias terms such that N:𝑋→𝑌 maps the points of the dataset to their correct labels. Sometimes, the labels are described as one-hot vectors, i.e., a vector such as (0, . . . , 0,1,0, . . . , 0)determining the class2. In general, it is not possible or desirable to find the optimal solution to a classification problem because we dispose of a limited quantity of discrete data and the generalization can be untruth, this is called overfitting. Put simply, overfitting is produced when it fits too closely to a certain set of data but fail to fit additional data. In Figure 3.6, an example of this issue is shown. We usually take into account different measures to describe the performance of a model. The most commonly used is the accuracy measure which is the quotient of the data correctly classified by the model over the size of the full dataset. Next, we rewrite one of the most important theoretical results on multilayer feed-forward networks adapted to our notation. 3 Background 22 Figure 3.6: Let us consider a dataset given by the two-dimensional points displayed describing a binary classification problem, and two possible outputs for a machine learning model, the blue and the red decision boundaries. The accuracy of the red one is higher than the accuracy of the blue one. However, we can expect the blue one to be a better generalization of the binary classification problem. Theorem 3.3.1 (Universal Approximation Theorem, [55]) Let 𝐴 be any compact subset of ℝ𝑛 and let 𝐶(𝐴) be the space of real-valued continuous functions on 𝐴 . Then, given any 𝜖 > 0 and any function 𝑔∈𝐶(𝐴) , there exists a multi-layer feed-forward network N:ℝ𝑛→ℝ approximating 𝑔 , that is, ||𝑔−N|| < 𝜖. The classical proofs of this theorem are non-constructive. See [55,62, 63] where it is claimed that there exists a one-hidden-layer feed-forward network N:ℝ𝑛→ℝ , defined as N(𝑥)=𝑓2◦𝑓1(𝑥) with 𝑓1(𝑦)=𝜙1(𝑊(1); 𝑦;𝑏1) and 𝑓2(𝑦)=𝑊(2)𝑦 , approximating 𝑔 , that is, ||𝑔−N|| < 𝜖 , but no general algorithm to build Nis given. Part I: Applying Computational Topology Techniques to the Data 4 Towards a Philological Metric 4.1 Introduction . . . . . . . . . . 25 4.2 Word embedding . . . . . . . 26 4.3 Description of the methodology . . . . . . . . . . . . . . . . . . 27 4.4 Experiment . . . . . . . . . . . 28 The context: Spanish Golden Age literature . . . . . . . . . . . 28 The corpus and the preprocessing step . . . . . . . . . . . . . . . 30 Application of the word2vec algorithm . . . . . . . . . . . . . . . . 31 The Vietoris-Rips filtration and the bottleneck distance . . . . . . 31 Results . . . . . . . . . . . . . . . 31 4.1 Introduction In this chapter, we revisit [46]. Until now, most of the methods used in comparison studies in philology are essentially qualitative. The comparison among writers, periods or, in general, literary works is often based on stylistic observations that cannot be quantified. Several quantitative methods based on statistical analysis have been applied in the past (see [64]) but their use is still controversial [65]. Our approach, based on topological data analysis techniques, is completely different from previous ones. Instead of using statistical methods, whose aim is to summarize the information of the literary work in a numerical description, our procedure is based on the spatial shape of the data after its embedding in a high-dimensional metric space. Broadly speaking, we start representing a literary work as a point cloud. The process of making such representation word by word is called word embedding. Among the most popular systems for word embedding, the word2vec [66], GloVe [67] or FastText [68] systems can be cited. Along this chapter, the word2vec system with its skipgram variation will be used to obtain such multidimensional representation of literary works. The embedding techniques mentioned above try to find a representation of the literary work as a high-dimensional point cloud in such a way that the semantic proximity is kept which is one of the key points of this chapter. Another of the key points is the use of topological data analysis techniques to measure the nearness between different point clouds representing different literary works. In computer sciences, there are many different ways to measure the distance among two point clouds [69], but most of them are merely based on some kind of statistical resume of the point cloud and not on its shape. The header is a photo of the Cloud gate in Chicago. It was taken during the Geometric Data Analysis congress. 4 Towards a Philological Metric 26 In this chapter, the shape of a point cloud representing a literary work is captured by persistence diagrams (see page 19). The bottleneck distance between the persistence diagrams provides a way to quantify the nearness among two different persistence diagrams and hence, a way to quantify the nearness among two different literary works. As far as we know, very few papers are exploring similar research lines [70,71] in which the proximity between literary works is measured using topological data analysis techniques. In order to illustrate the potential of such techniques, we provide a case study on the comparison of the literary works of two poets who are representatives of the two main stylistic trends of the Spanish Golden Age: Luis de Góngora and Francisco de Quevedo. We also consider a third poet, called Lope de Vega, whose literary works belong to the same stylistic trend as those of Francisco de Quevedo. Literary experts agree that the styles of Lope de Vega and Francisco de Quevedo are close (they belong to the same literary trend, the socalled Conceptismo), but both are far from the style of Luis de Góngora, which corresponds to a different literary trend called Culteranismo [72]. The application of topological data analysis techniques to measure the nearness of such Spanish poets quantitatively confirms that the styles of Lope de Vega and Francisco de Quevedo are close to each other and yet both styles are far from the style of Luis de Góngora. As we mentioned previously, neural networks have many different kind of architectures for very different purposes. One of the possible applications is data embedding. The idea is to provide a representation of a given dataset in a different space from its current one. This representation tries to maintain the underline structure of the dataset taking into account some kind of relationship between data. In this case, we used a very special dataset, a corpus composed of the sonnets written by the three different poets from the Spanish Golden Age. We embed the corpus using a well-known neural network architecture (called Word2vec) and study the differences between the literary styles through the difference between the persistence diagrams of the Vietoris-Rips filtrations associated to the embeddings of the corpus. By this, we could make statements about the literary styles of the three poets and consider some kind of philological metric. 4.2 Word embedding Word embedding is the collective name of a set of methods for representing words from natural languages as points (or vectors) in a real-valued multi-dimensional space. The common feature of such methods is that words with similar meanings take close representation. Such representation methods are on the basis of some of the big successes of deep learning applied to natural language processing (see, for example, [73] or [74]). Next, we recall some basic definitions related to this methodology. Definition 4.2.1 (corpus) Given a finite alphabet Σ , the set of all possible words is Σ∗={𝑥1𝑥2···𝑥𝑛|𝑥𝑖∈Σ} . A corpus is a finite collection of 4 Towards a Philological Metric 27 1: The model we used is the one implemented in the python library gensim which is based on [75,76]. writings composed with these words, denoted by 𝐶 . The vocabulary, 𝑉 , of a corpus 𝐶 is the set of all the words that appear in 𝐶 . Finally, given 𝑑≥1 , a word embedding is a function 𝐸:𝑉→ℝ𝑑. The word embedding process used along this chapter is the word2vec1 , specifically its modified version called skipgram [77]. It is based on a neural network architecture with one hidden layer where the input is a corpus and the output is a probability distribution. It is trained with a corpus to detect similarities in words based on their relative distance in a writing. Such distances are the base of their representation in an 𝑛-dimensional space. The two main models of the word2vec techniques are called CBOW (Continuous Bag of Words) and skipgram . A detailed description of such models is out of the scope of this work. Roughly speaking, the neural network is trained by using a corpus, where the context of a word is considered as a window around a target word. In this way, in the skipgram model each word of the input is processed by a log-linear classifier with continuous projection layer, trying to predict the previous and the following words in a sentence. In this kind of neural network architecture, the input is a one-hot vector representing a word of the corpus. Then, the weights of the hidden layer are the high dimensional representation of the words, and the output is a prediction of the surrounding words. More specifically, it is a log-linear classifier with continuous projection layer following the architecture shown and explained in Figure 4.1. Figure 4.1: The skipgram neural network architecture. The input layer has as many neurons as the length of the one-hot vector that encodes the words of the corpus, i.e., the number of words that compose the vocabulary of the corpus, 𝑁 in this case. The size of the projection layer is equal to the dimension in which we want to embed the corpus, 𝑀 . Finally, the output layer has 𝑁·𝑆 neurons where 𝑆 is the size of the window, i.e., the number of surrounding words that the model tries to predict. This image is inspired in the image of the skipgram model in [78]. 4.3 Description of the methodology Next, we describe the methodology based on topological data analysis techniques designed to automatically compare different literary styles. Broadly speaking, given a corpus composed of writings belonging to different categories (e.g., authors, styles, trends,. . . ) a stemming process (which we call stem ) is applied to each writing where the non-informative words (also called stop-words) are deleted. Then, the skipgram word 5 Representative datasets 34 to and with a smaller number of points than the original dataset but keeping its “topological information", allowing the neural network to perform the learning process taking less time without losing accuracy. To do so, the concept of representative datasets is defined based on the Gromov-Hausdorff distance. This distance is not easy to compute. In [97], it is shown that this distance can not be approximated in polynomial time. Then, in [98], it is shown how to use persistent homology to obtain a lower bound of the Gromov-Hausdorff distance. Therefore, we could provide bounds to the optimal representative dataset and determine the loss of accuracy. However, we intended this approximation only for the perceptron case [44]. An useful result used is the following one that connects the Gromov- Hausdorffdistancebetweentwometricspacesandthebottleneckdistance between the persistence diagrams of their corresponding Vietoris-Rips filtrations. Theorem 5.1.1 ([99]) For any two subsets 𝑋 and 𝑌 of ℝ𝑛 , and for any dimension 𝑞≤𝑛 , the bottleneck distance between the persistence diagrams of the Vietoris-Rips filtration of 𝑋 and 𝑌 , denoted by 𝐷𝑔𝑚𝑞(𝑋) and 𝐷𝑔𝑚𝑞(𝑌) , is bounded by the Gromov-Hausdorff distance of 𝑋and 𝑌: 𝑑𝐵(𝐷𝑔𝑚𝑞(𝑋), 𝐷𝑔𝑚𝑞(𝑌)) ≤ 2𝑑𝐺𝐻(𝑋, 𝑌). Let us recall that the Hausdorff distance between 𝑋and 𝑌is: 𝑑𝐻(𝑋, 𝑌)=max{sup 𝑥∈𝑋 inf 𝑦∈𝑌||𝑥−𝑦||,sup 𝑦∈𝑌 inf 𝑥∈𝑋||𝑥−𝑦||}, and the Gromov-Hausdorff distance between 𝑋 and 𝑌 is defined as the infimum of the Hausdorff distance taken over all possible isometric transformations. That is, 𝑑𝐺𝐻(𝑋, 𝑌)=inf 𝑓 ,𝑔 {𝑑𝐻𝑓(𝑋), 𝑔(𝑌)}, where 𝑓:𝑋→𝑍 denotes an isometric transformation of 𝑋 into some metric space 𝑍 and 𝑔:𝑌→𝑍 an isometric transformation of 𝑌 into 𝑍 . 5.2 Representative datasets The key idea of this chapter is the formal definition of representative datasets and the proof of their usefulness to decrease the time needed to train a neural network without loosing accuracy. Proving such general result for all the neural network architectures is out of the scope and, probably, it is not possible since the definition of neural network is continuously evolving over time as we mentioned before. In spite of such difficulties, we will start by showing the usefulness of representative datasets for the perceptron case. In this section, we provide a definition of representative datasets which is general for all machine learning models. The intuition behind this definition is to keep the shape of the original dataset while reducing its number of points. 5 Representative datasets 35 Definition 5.2.1 A labelled point (˜ 𝑥, 𝑐 ˜ 𝑥) ∈ ℝ𝑛×[[0, 𝑘]] is 𝜀 -representative of (𝑥, 𝑐𝑥) ∈ ℝ𝑛× [[0, 𝑘]] if 𝑐𝑥=𝑐˜ 𝑥 and there exists 𝛿∈ℝ𝑛 such that 𝑥=˜ 𝑥+𝛿 with ||𝛿|| ≤ 𝜀 , where 𝜀∈ℝ is the representation error. We denote ˜ 𝑥≈𝜀𝑥. Then, let us define the concept of 𝜀 -representative dataset. Notice that if a dataset is correctly classified by a neural network, any isometric transformation of such dataset can be also correctly classified by the neural network. Therefore, the definition of 𝜀 -representative dataset should be independent of such transformations. Definition 5.2.2 A dataset ˜ D={(˜ 𝑥, 𝑐 ˜ 𝑥):˜ 𝑥∈˜ 𝑋⊂ℝ𝑛 and 𝑐˜ 𝑥∈ [[0, 𝑘]]} is 𝜀 -representative of D={(𝑥, 𝑐𝑥):𝑥∈𝑋⊂ℝ𝑛 and 𝑐𝑥∈ [[0, 𝑘]]} if there exists an isometric transformation 𝑓:˜ 𝑋→ℝ𝑛 , such that for any (𝑥, 𝑐𝑥) ∈ D there exists (˜ 𝑥, 𝑐 ˜ 𝑥) ∈ ˜ D satisfying that 𝑓(˜ 𝑥) ≈𝜀𝑥 . We will say that 𝜀is optimal if 𝜀=min{𝜉:˜ Dis a 𝜉-representative dataset of D}. Proposition 5.2.1 Let ˜ D be a 𝜀 -representative dataset (with set of points ˜ 𝑋 ) of a dataset D(with set of points 𝑋). Then 𝑑𝐺𝐻(𝑋, ˜ 𝑋) ≤ 𝜀. Proof. By definition of 𝜀 -representative dataset, there exists an isometric transformation from ˜ 𝑋 to ℝ𝑛 where for all 𝑥∈𝑋 there exists ˜ 𝑥∈˜ 𝑋 such that ||𝑥−𝑓(˜ 𝑥)|| ≤ 𝜀 . Therefore, 𝑑𝐻(𝑋, 𝑓 (˜ 𝑋)) ≤ 𝜀 . Then, by definition of Gromov-Hausdorff distance, 𝑑𝐺𝐻(𝑋, ˜ 𝑋) ≤ 𝑑𝐻(𝑋, 𝑓 (˜ 𝑋)) ≤ 𝜀. The definition of 𝜀 -representative datasets is not useful when 𝜀 is “big". The following result provides the optimal value for 𝜀. Remark 5.2.1 If 𝜀=𝑑𝐺𝐻(𝑋, ˜ 𝑋)then 𝜀is optimal. Therefore, one way to discern if a dataset ˜ D is “sufficently representative" of D is to compute Gromov-Hausdorff distance to 𝑋 and ˜ 𝑋 . If Gromov- Hausdorff distance is “large", we could say that the dataset ˜ D is not representative of D .However, Gromov-Hausdorffdistanceis notuseful in practice because of its high computational cost. An alternative approach to this problem is given in Section 5.4. The following concept of 𝜆 -balanced dataset will be used in Section 5.3 to ensure the maintenance of similar results when training a perceptron with a representative dataset instead of the original one. Definition 5.2.3 For 𝜆∈ℕ , a dataset ˜ D is 𝜆 -balanced 𝜀 -representative of D if ˜ D is 𝜀 -representative of D and for each (˜ 𝑥, 𝑐 ˜ 𝑥) ∈ ˜ 𝐷 , |{(𝑥, 𝑐𝑥):𝑓(𝑥) ≈𝜀 ˜ 𝑥}| =𝜆where 𝑓is a fixed isometric transformation. Finally, we introduce the definition of dominating set, which will be used in the next subsection. 5 Representative datasets 36 Definition 5.2.4 Given a graph 𝐺=(𝑋, 𝐸) , a set 𝑌⊂𝑋 is a dominating set of 𝑋 if for any 𝑥∈𝑋 , it is satisfied that 𝑥∈𝑌 or there exists 𝑦∈𝑌 adjacent to 𝑥. Proximity graph algorithm In this subsection, for a given 𝜀 , we propose a variant of the Proximity Graph Algorithm [43] to compute an 𝜀 -representative dataset ˜ D of a dataset D={(𝑥, 𝑐𝑥):𝑥∈𝑋and 𝑐𝑥∈ [[0, 𝑘]]} . It works as follows. First, a proximity graph is built over 𝑋 , establishing adjacency relations between points of 𝑋 , represented by arcs. Second, using this graph, a dominating set ˜ 𝑋⊆𝑋 is computed, obtaining a 𝜀 -representative dataset ˜ D={(˜ 𝑥, 𝑐 ˜ 𝑥):˜ 𝑥∈˜ 𝑋and (˜ 𝑥, 𝑐 ˜ 𝑥) ∈ D}. Definition 5.2.5 Given 𝑋⊂ℝ𝑛 and 𝜀∈ℝ , an 𝜀 -proximity graph of 𝑋 is a graph 𝐺𝜀(𝑋)=(𝑋, 𝐸) such that if 𝑥, 𝑦 ∈𝑋 and ||𝑥−𝑦|| ≤ 𝜀 then (𝑥, 𝑦) ∈ 𝐸. See Figure 5.1 where the proximity graph of one of the two interlaced solid torus is drawn for a fixed 𝜀. Figure 5.1: Point cloud sampling two interlaced solid torus and the proximity graph of one of them for a fixed 𝜀. The pseudo-code of the Proximity Graph Algorithm used is the following. Here, DominatingSet (𝐺𝜀(𝑋𝑐)) refers to a dominating set obtained from Algorithm 2: Proximity Graph Algorithm 1Input: A dataset D={(𝑥, 𝑐𝑥):𝑥∈𝑋⊂ℝ𝑛and 𝑐𝑥∈ [[0, 𝑘]]} 2Output: A dataset ˜ D⊆D 3for 𝑐=0to 𝑐=𝑘do 4𝑋𝑐={𝑥:(𝑥, 𝑐) ∈ D} 5˜ 𝑋𝑐=DominatingSet(𝐺𝜀(𝑋𝑐)) 6endfor 7˜ 𝑋=S𝑘 𝑐=0˜ 𝑋𝑐 8˜ D={(𝑥, 𝑐):𝑥∈˜ 𝑋and (𝑥, 𝑐) ∈ D} the proximity graph 𝐺𝜀(𝑋𝑐) . Among the existing algorithms in the literature to obtain a dominating set, we will use, in our experiments in Section 5.5, the algorithm proposed in [100] that runs in 𝑂(|𝑋| · |𝐸|) . Therefore, the complexity of Algorithm 2is 𝑂(|𝑋|2+|𝑋| · |𝐸|) because of the size of the matrix of distances between points and the complexity of the algorithm to obtain the dominating set. 5 Representative datasets 37 Lemma 5.2.2 The output, ˜ D , of Algorithm 2is a 𝜀 -representative dataset of D. Proof. Let us prove that for any (𝑥, 𝑐𝑥) ∈ D there exists (˜ 𝑥, 𝑐𝑥) ∈ ˜ D such that 𝑥≈𝜀˜ 𝑥. Two possibilities can arise: 1. If (𝑥, 𝑐𝑥) ∈ ˜ D, it is done. 2. If (𝑥, 𝑐𝑥)∉˜ D , since ˜ 𝑋𝑐𝑥⊂˜ 𝑋 is a dominating set of 𝐺𝜀(𝑋𝑐𝑥) , then there exists ˜ 𝑥∈˜ 𝑋𝑐𝑥 such that ˜ 𝑥 is adjacent to 𝑥 in 𝐺𝜀(𝑋𝑐𝑥) . Therefore, (˜ 𝑥, 𝑐𝑥) ∈ ˜ Dand 𝑥≈𝜀˜ 𝑥. 5.3 The perceptron case One of the simplest neural network architecture is the perceptron. Our goal in this section is to formally prove that training a perceptron with a representative dataset is equivalent, in terms of accuracy, to training it with the original dataset. Specifically, we provide results using the stochastic gradient descent and the gradient descent algorithms. Notice that in the case of the stochastic gradient descent, the number of updates needed to reach convergence usually increases with the size of data (see [87, Section 5.9]). For the sake of simplicity, we will restrict our interest to a binary classification problem, although our approach is valid for any classification problem. Therefore, our input is a dataset D={(𝑥, 𝑐𝑥):𝑥∈𝑋⊂ℝ𝑛and 𝑐𝑥∈ [[0,1]]}. Aperceptron, N 𝑤 , with weights 𝑤=(𝑤0, 𝑤1, . . . , 𝑤𝑛) ∈ ℝ𝑛+1 is defined as: N 𝑤(𝑥)=1 if 𝑦𝑤(𝑥) ≥ 1 2, 0otherwise; being 𝑦𝑤:ℝ𝑛→ (0,1) 𝑥↦→ 𝜎(𝑤𝑥) where, for 𝑥=(𝑥1, . . . , 𝑥𝑛) ∈ ℝ𝑛,𝑤𝑥 denotes the expression: 𝑤0+𝑤1𝑥1+···+𝑤𝑛𝑥𝑛, and 𝜎:ℝ→ (0,1), defined as 𝜎(𝑧)=1 1+𝑒−𝑧, is the sigmoid function. Let 𝜎𝑚 denotes the composition 𝜎𝑚=𝜎𝑚-times ··· 𝜎 . A useful property of the sigmoid function is the easy expression of its derivative. 5 Representative datasets 38 Lemma 5.3.1 If 𝑚∈ℕand 𝑧∈ℝthen 0<(𝜎𝑚)0(𝑧)=𝑚𝜎𝑚(𝑧)(1−𝜎(𝑧)) ≤ 𝑚 𝑚+1𝑚+1 . Proof. First, (𝜎𝑚)0(𝑧)=𝑚𝜎𝑚(𝑧)(1−𝜎(𝑧)) is greater than 0 since 0< 𝜎(𝑧)<1 for all 𝑧∈ℝ . Second, let us find the local extrema of (𝜎𝑚)0 by computing the roots of its derivative: (𝜎𝑚)00(𝑧)=𝑚𝜎𝑚(𝑧)(1−𝜎(𝑧))(𝑚−(𝑚+1)𝜎(𝑧)). Now, (𝜎𝑚)00(𝑧)=0 if and only if 𝑚− (𝑚+1)𝜎(𝑧)=0 . The last expression vanishes at 𝑧=log(𝑚) . Besides, (𝜎𝑚)00(𝑧)>0 if and only if 𝑚−(𝑚+1)𝜎(𝑧)>0 which is true for all 𝑧∈ (−∞,log(𝑚)) . Analogously, (𝜎𝑚)00(𝑧)<0 for all 𝑧∈ (log(𝑚),+∞) , concluding that 𝑧=log(𝑚) is a global maximum. Finally, (𝜎𝑚)0(log(𝑚)) =𝑚 𝑚+1𝑚+1. In the following lemma, we prove that the difference in the output of the function 𝑦𝑚 𝑤 evaluated at a point 𝑥 and at its 𝜀 -representative point ˜ 𝑥 depends on the weights 𝑤and the parameter 𝜀. Lemma 5.3.2 Let 𝑤∈ℝ𝑛+1and 𝑥,˜ 𝑥∈ℝ𝑛with ˜ 𝑥≈𝜀𝑥. Then, ||𝑦𝑚 𝑤(˜ 𝑥)− 𝑦𝑚 𝑤(𝑥)|| ≤ 𝜌𝑚||𝑤||∗𝜀, where 𝜌𝑚=𝜌(𝑤𝑥,𝑤 ˜ 𝑥,𝑚)= (𝜎𝑚)0(𝑧),if log(𝑚)<𝑧, (𝜎𝑚)0(˜ 𝑧),if ˜ 𝑧<log(𝑚), (𝜎𝑚)0(log(𝑚)),otherwise. with 𝑧=min{𝑤𝑥, 𝑤 ˜ 𝑥}and ˜ 𝑧=max{𝑤𝑥, 𝑤 ˜ 𝑥}. Proof. Let us assume, without loss of generality, that 𝑤𝑥 ≤𝑤˜ 𝑥 . Then, using Mean Value Theorem, there exists 𝛽∈ (𝑤𝑥, 𝑤 ˜ 𝑥)such that 𝑦𝑚 𝑤(˜ 𝑥)− 𝑦𝑚 𝑤(𝑥)=(𝜎𝑚)0(𝛽)(𝑤˜ 𝑥−𝑤𝑥). By Lemma 5.3.1, the maximum of (𝜎𝑚)0 in the interval [𝑧, ˜ 𝑧] is reached at log(𝑚) if 𝑧<log(𝑚)<˜ 𝑧 , at 𝑧 if log(𝑚) ≤ 𝑧 , and at ˜ 𝑧 if ˜ 𝑧≤log(𝑚) , with 𝑧=min{𝑤𝑥, 𝑤 ˜ 𝑥}and ˜ 𝑧=max{𝑤𝑥, 𝑤 ˜ 𝑥}. Consequently, ||𝑦𝑚 𝑤(𝑥)− 𝑦𝑚 𝑤(𝑥)|| ≤ 𝜌(𝑤𝑥,𝑤,˜ 𝑥,𝑚)||𝑤(˜ 𝑥−𝑥)||.(5.1) Applying now the Hölder inequality we obtain: ||𝑤(˜ 𝑥−𝑥)|| ≤ ||𝑤||∗||˜ 𝑥−𝑥|| ≤ ||𝑤||∗𝜀. Replacing ||𝑤(˜ 𝑥−𝑥)|| by ||𝑤||∗𝜀 in Eq. (5.1), we obtain the desired result. The following result is a direct consequence of Lemma 5.3.1 and Lemma 5.3.2. 5 Representative datasets 39 Corollary 5.3.3 Let 𝑤∈ℝ𝑛+1and 𝑥,˜ 𝑥∈ℝ𝑛with ˜ 𝑥≈𝜀𝑥. Then, ||𝑦𝑚 𝑤(˜ 𝑥)− 𝑦𝑚 𝑤(𝑥)|| ≤ 𝑚 𝑚+1𝑚+1||𝑤||∗𝜀. As previously anticipated, we will use stochastic gradient descent to train the perceptron, trying to minimize the following error function: 𝔼(𝑤, 𝑋)=𝔼(𝐸𝑥(𝑤)) =2 |𝑋|X 𝑥∈𝑋 𝐸𝑥(𝑤), where, for (𝑥, 𝑐𝑥) ∈ Dand 𝑤∈ℝ𝑛+1, 𝐸𝑥(𝑤)=1 2(𝑐𝑥−𝑦𝑤(𝑥))2 is the loss function considered in this chapter. Following stochastic gradient descent, for all 𝑗∈ [[0, 𝑛]] , the weights 𝑤𝑖=(𝑤𝑖 0, 𝑤𝑖 1, . . . , 𝑤𝑖 𝑛) of the 𝑖 th-state of the perceptron is updated according to the following rule: 𝑤𝑖+1 𝑗←𝑤𝑖 𝑗−𝜂𝑖 𝜕𝐸𝑥𝑖(𝑤𝑖) 𝜕𝑤𝑖 𝑗 ,(5.2) where 𝜂𝑖>0 is the learning rate. Rule (5.2) takes a random point of the dataset for every iteration 𝑖 , being able to repeat the same point in different iterations of the algorithm. Let us notice that 𝜕𝐸𝑥(𝑤) 𝜕𝑤𝑗 =(𝑐𝑥−𝑦𝑤(𝑥))𝑦0 𝑤(𝑥)𝑥𝑗,(5.3) for 𝑗∈ [[1, 𝑛]]and 𝑥=(𝑥1, . . . , 𝑥𝑛). Besides, 𝜕𝐸𝑥(𝑤) 𝜕𝑤0 =(𝑐𝑥−𝑦𝑤(𝑥))𝑦0 𝑤(𝑥). By abuse of notation we write Eq. (5.3) for all 𝑗∈ [[1, 𝑛]] , assuming that 𝑥1=1. Now, using Eq. (5.3), Rule (5.2) can be written as follows: 𝑤𝑖+1←𝑤𝑖−𝜂𝑖(𝑐𝑖−𝑦𝑤𝑖(𝑥𝑖))𝑦𝑤𝑖(𝑥𝑖)(1−𝑦𝑤𝑖(𝑥𝑖))𝑥𝑖(5.4) for (𝑥𝑖, 𝑐𝑖) ∈ D. To assure the convergence of the training process to a local minimum, it is enough that, for each iteration 𝑖 , the learning rate 𝜂𝑖 satisfies the following conditions (see [87, Section 8.3.1]): ∞ X 𝑖=1 𝜂𝑖=∞and ∞ X 𝑖=1 𝜂2 𝑖<∞. The following lemma determines when 𝜀 -representative points are classified under the same label as the points they represent. 5 Representative datasets 40 Lemma 5.3.4 Let ˜ Dbe a 𝜀-representative dataset of a dataset D. Let N 𝑤be a perceptron. Let (𝑥, 𝑐) ∈ D and (˜ 𝑥, 𝑐) ∈ ˜ D with ˜ 𝑥≈𝜀𝑥 . If 𝜀≤||𝑤𝑥|| ||𝑤|| then N 𝑤(𝑥)=N 𝑤(˜ 𝑥). Proof. First, if 𝑤𝑥 =0 then 𝜀=0 and therefore 𝑥=˜ 𝑥 . Let us then suppose, without loss of generality, that 𝑤𝑥 <0 . Then 𝑦𝑤(𝑥)<1 2 and N 𝑤(𝑥)=0 by definition of perceptron. Now, since 𝜀 < ||𝑤𝑥|| ||𝑤|| then 𝑥 and ˜ 𝑥 belong to the same semispace in which the space is divided by the hyperplane 𝑤𝑥 =0. Therefore, 𝑤˜ 𝑥<0, then 𝑦𝑤(˜ 𝑥)<1 2and finally N 𝑤(˜ 𝑥)=0. By Lemma 5.3.4, we can state that if 𝜀 is “small" enough, then D and ˜ D will produce the same accuracy on the perceptron N 𝑤. Let us define I 𝑤(𝑥)=1 if 𝑐𝑥=N 𝑤(𝑥), 0otherwise, for any (𝑥, 𝑐𝑥) ∈ D. The following result holds. Theorem 5.3.5 Let ˜ D be a 𝜆 -balanced 𝜀 -representative dataset of a dataset D. Let N 𝑤be a perceptron. If 𝜀≤min n||𝑤𝑥|| ||𝑤|| :(𝑥, 𝑐𝑥) ∈ Dothen 1 |D|X (𝑥,𝑐𝑥)∈D 𝐼𝑤(𝑥)=1 |˜ D|X (˜ 𝑥,𝑐 ˜ 𝑥)∈˜ D 𝐼𝑤(˜ 𝑥). Proof. Since ˜ D is 𝜆 -balance 𝜀 -representative of D , then |D|=𝜆·| ˜ D| and we have: 1 |D|X (𝑥,𝑐𝑥)∈D 𝐼𝑤(𝑥)− 1 |˜ D|X (˜ 𝑥,𝑐 ˜ 𝑥)∈˜ D 𝐼𝑤(˜ 𝑥)=1 |D|X (𝑥,𝑐𝑥)∈D(𝐼𝑤(𝑥)−𝜆·𝐼𝑤(˜ 𝑥)) =1 |D|X (˜ 𝑥,𝑐 ˜ 𝑥)∈˜ DX 𝑥≈𝜀˜ 𝑥(𝐼𝑤(𝑥)−𝐼𝑤(˜ 𝑥)). (5.5) Finally, 𝐼𝑤(𝑥)=𝐼𝑤(˜ 𝑥) for all 𝑥≈𝜀˜ 𝑥 and (˜ 𝑥, 𝑐 ˜ 𝑥) ∈ ˜ D by Lemma 5.3.4 since 𝜀 < ||𝑤𝑥|| ||𝑤|| for all (𝑥, 𝑐𝑥) ∈ D. Next, we compare the two errors 𝔼(𝑤, 𝑋) and 𝔼(𝑤, ˜ 𝑋) obtained when taking a dataset Dand its 𝜆-balanced 𝜀-representative dataset ˜ D. Lemma 5.3.6 Let 𝑋, ˜ 𝑋⊂ℝ𝑛 . Let 𝑤∈ℝ𝑛+1 . Let D={(𝑥, 𝑐𝑥):𝑥∈𝑋 and 𝑐𝑥∈ [[0,1]]} and ˜ D={(˜ 𝑥, 𝑐 ˜ 𝑥):˜ 𝑥∈˜ 𝑋 and 𝑐˜ 𝑥∈ [[0,1]]} . Suppose ˜ D is 𝜆-balanced 𝜀-representative of D. Then: 𝔼(𝑤, 𝑋)−𝔼(𝑤, ˜ 𝑋)≤1 |𝑋|X 𝑥∈𝑋2𝑐𝑥𝜌1+𝜌2||𝑤(𝑥−˜ 𝑥)|| where 𝜌𝑚=𝜌(𝑤𝑥,𝑤 ˜ 𝑥,𝑚)for 𝑚=1,2, and for each addend, 𝑥≈𝜀˜ 𝑥. 5 Representative datasets 41 Proof. 𝔼(𝑤, 𝑋)−𝔼(𝑤, ˜ 𝑋)=1 |𝑋|X 𝑥∈𝑋(𝑐𝑥−𝑦𝑤(𝑥))2−1 |˜ 𝑋|X ˜ 𝑥∈˜ 𝑋(𝑐˜ 𝑥−𝑦𝑤(˜ 𝑥))2 =1 |𝑋|·|˜ 𝑋||˜ 𝑋|X 𝑥∈𝑋(𝑐𝑥−𝑦𝑤(𝑥))2−|𝑋|X ˜ 𝑥∈˜ 𝑋(𝑐˜ 𝑥−𝑦𝑤(˜ 𝑥))2. Since ˜ 𝐷is 𝜆-balanced 𝜀-representative of Dthen |𝑋|=𝜆|˜ 𝑋|. Then, ||𝔼(𝑤, 𝑋)−𝔼(𝑤, ˜ 𝑋)|| =1 |𝑋|X 𝑥∈𝑋 2𝑐𝑥𝑦˜ 𝑤(˜ 𝑥)− 𝑦𝑤(𝑥)+𝑦2 𝑤(𝑥)− 𝑦2 ˜ 𝑤(˜ 𝑥) ≤1 |𝑋|X 𝑥∈𝑋 2𝑐𝑥||𝑦˜ 𝑤(˜ 𝑥)− 𝑦𝑤(𝑥)||+||𝑦2 𝑤(𝑥)− 𝑦2 ˜ 𝑤(˜ 𝑥)||, where, for each addend, ˜ 𝑥≈𝜀𝑥 . Applying Lemma 5.3.2 for 𝑚=1,2 to the last expression, we get: ||𝔼(𝑤, 𝑋)−𝔼(𝑤, ˜ 𝑋)|| ≤ 1 |𝑋|X 𝑥∈𝑋2𝑐𝑥𝜌1+𝜌2||𝑤(𝑥−˜ 𝑥)||. From this last result we can infer the following. We can always find 𝜀 “small enough" so that the difference between the errors obtained from one dataset and from another which is 𝜀 -representative of the former is “close" to zero. Theorem 5.3.7 Let 𝛿 > 0 . Let ˜ D be a 𝜆 -balanced 𝜀 -representative dataset of a dataset D . Let N 𝑤 be a perceptron. If 𝜀≤54 43||𝑤||∗𝛿 , then ||𝔼(𝑤, 𝑋)− 𝔼(𝑤, ˜ 𝑋)|| < 𝛿. Proof. First, 𝜌1≤1 4 and 𝜌2≤8 27 by Corollary 5.3.3. Second, since 𝑐𝑥∈ [[0,1]], then we have: 1 |𝑋|X 𝑥∈𝑋2𝑐𝑥𝜌1+𝜌2||𝑤(𝑥−˜ 𝑥)|| ≤ 1 |𝑋|X 𝑥∈𝑋1 2+8 27||𝑤(𝑥−˜ 𝑥)|| =43 54 1 |𝑋|X 𝑥∈𝑋||𝑤(𝑥−˜ 𝑥)||. Applying Hölder inequality to the last expression we get: 1 |𝑋|X 𝑥∈𝑋2𝑐𝑥𝜌1+𝜌2||𝑤(𝑥−˜ 𝑥)|| ≤ 43 54||𝑤||∗𝜀. Therefore, by Lemma 5.3.6, if 𝜀≤54 43||𝑤||∗𝛿 , then ||𝔼(𝑤, 𝑋)−𝔼(𝑤, ˜ 𝑋)|| < 𝛿 as stated. Summing up, in the case of stochastic gradient descent, we have proved that it is equivalent to train a perceptron with a dataset D or with its 𝜆 -balanced 𝜀 -representative dataset. This fact will be shown through experiments in Section 5.5 for the perceptron case and in Section 5.6 for a neural network with a more complex architecture. 5 Representative datasets 42 5.4 Applying persistent homology to infer the representativeness of a dataset In this section, we recall the roll of persistent homology as a tool to infer the representativeness of a dataset. First, from Theorem 5.1.1 in page 34, we can establish that the bottleneck distance between persistence diagrams is a lower bound of the representativeness of the dataset. Theorem 5.4.1 Let ˜ D be a 𝜀 -representative dataset (with set of points ˜ 𝑋 ) of a dataset D (with set of points 𝑋 ). Let Dgm(𝑋) and Dgm(˜ 𝑋) be the persistence diagrams of the Vietoris Rips filtration of 𝑋and ˜ 𝑋, respectively. Then, 𝑑𝐵Dgm(𝑋),Dgm(˜ 𝑋)≤2𝜀. Proof. Since ˜ D is 𝜀 -representative of D then 𝑑𝐺𝐻(𝑋 , ˜ 𝑋) ≤ 𝜀 by Proposition 5.2.1. Now, by Theorem 5.1.1, 1 2𝑑𝐵(Dgm𝑝(𝑋),Dgm𝑝(𝑌)) ≤ 𝑑𝐺𝐻(𝑋, 𝑌) ≤ 𝜀. As a direct consequence of Theorem 5.4.1 and the fact that the Hausdorff distance is an upper bound of the Gromov-Hausdorff distance, we have the following. Corollary 5.4.2 Let ˜ D be a 𝜀 -representative dataset of D with optimal 𝜀 . Let Dgm(𝑋) and Dgm(˜ 𝑋) be the persistence diagrams of the Vietoris-Rips filtration of 𝑋and ˜ 𝑋, respectively. Then, 1 2𝑑𝐵Dgm𝑝(𝑋),Dgm𝑝(˜ 𝑋))≤𝜀≤𝑑𝐻𝑋, ˜ 𝑋. To illustrate the usefulness of this last result, we will discuss a simple example. In Fig. 5.2a, a binary classification problem is given: Two classes corresponding, respectively, to the upper and the lower semicircumference together with a subsample of the circumference are shown. In Fig. 5.2c, we can see a subset of the original dataset given in Fig. 5.2a and a possible decision boundary. Since the decision boundaries are different, we should not consider the datasets to represent the same classification problem. However, the subset shown in Fig. 5.2b is more accurate, keeping the representativeness of the original dataset. Besides, we could say that minimizing the error function in the case of Fig. 5.2b is almost the same as minimizing the error function in the case of Fig. 5.2a. This, that is evident for the eye, can be determined computing the bottleneck distance between the two persistence diagrams and the Hausdorff distance between the two datasets (see the values shown in Table 5.1). Using Corollary 5.4.2, we can infer that 0.3≤𝜀≤0.35 for the dataset given in Fig. 5.2b and 0.425 ≤𝜀≤0.94 for the dataset given in Fig. 5.2c. 5 Representative datasets 43 Dataset 𝑏0𝑏1Hausdorff distance Representative dataset 1 (Fig. 5.2b) 0.5 0.6 0.35 Representative dataset 2 (Fig. 5.2c) 0.85 0.68 0.94 Table 5.1: The botleneck distance between the 0 - and 1 -persistence diagrams and the Hausdorff distance between the dataset given in Fig. 5.2a and, respectively, the datasets given in Fig. 5.2b and Fig. 5.2c. Therefore, the dataset given in Fig. 5.2b can be considered more representative of the dataset showed in Fig. 5.2a than the dataset pictured in Fig. 5.2c, as expected. Representative Datasets: The Perceptron case Dataset b0b1Hausdorffdistance Representative dataset 1 (Fig. 2b)0.5 0.6 0.35 Representative dataset 2 (Fig. 2c)0.85 0.68 0.94 Table 1 The 0-dimensional and 1-dimensional botleneck distances and the Hausdorffdistance between the dataset given in Fig. 2a and, respectively, the datasets given in Fig. 2b and Fig. 2c. Corollary 2. Let É Dbe a "-representative dataset of Dwith optimal ". Let Dgm(X)and Dgm(É X)be the persistence diagrams of Xand É X, respectively. Then, 1 2dBDgmp(X),Dgmp(É X))f"fdHX,É X. Toillustratetheusefulnessofthislastresult,wewilldiscussasimpleexample. InFig.2a,abinaryclassification problem is given: Two classes corresponding, respectively, to the upper and the lower semicircumference together with a subsample of the circumference are shown. In Fig. 2c, we can see a subset of the original dataset given in Fig. 2a and a possible decision boundary. Since the decision boundaries are different, we should not consider the datasetstorepresentthesameclassificationproblem. However,thesubsetshowninFig.2bismoreaccurate,keeping therepresentativenessoftheoriginaldataset. Besides,wecouldsaythatminimizingtheerrorfunctioninthecaseof Fig.2bisalmostthesameasminimizingtheerrorfunctioninthecaseofFig.2a. This,thatisevidentfortheeye,can be determined computing the bottleneck distance between the two persistence diagrams and the Hausdorffdistance betweenthetwodatasets(seethevaluesshowninTable1). UsingCorollary2,wecaninferthat0.3f"f0.35 forthedatasetgiveninFig.2band0.425 f"f0.94 forthe datasetgiveninFig.2c. Therefore,thedatasetgivenin Fig.2bcanbeconsideredmorerepresentativeof thedataset showedinFig.2athanthedatasetpicturedinFig.2c,asexpected. (a) A binary classification problem given by a sampled circumference. In this case, the classification problem tries to distinguish between the upper andthelowersemicircumference. (b)(Representative dataset 1) Asubsetofthebinaryclassificationproblem given in Fig. 2a. In this case, we can saythatitisrepresentativeoftheoriginaldataset. (c) (Representative dataset 2) A subsetofthebinaryclassificationproblem given in Fig. 2a. As we can see, it is notreallyrepresentativeoftheoriginal dataset. Figure 2: Illustration of a binary classification problem and the representative dataset concept. 6. Experimental Results: The Perceptron Case In this section, two experiments are provided in Subsection 6.1 and Subsection 6.2 for the perceptron case, to supportourresultsandillustratetheusefulnessofourmethod. In thefirstexperiment, twointerlacedsolidtorusare sampledand,inthesecondexperiment,theIrisdatasetisconsidered. Inbothexperiments,theperceptronisinitiated withthesameweightandtrainedwiththreedifferentdatasets: theoriginaldataset,adominatingdataset(whichisthe outputofAlgorithm1andisarepresentativedataset)andarandomdatasetofthesamesizeasthesizeofthedominating dataset. Theseexperimentssupportthataperceptrontrainedwithrepresentativedatasetsgivesimilaraccuracythana perceptrontrainedwiththeoriginaldataset. Besides,weshowthatthetrainingtime,inthecaseofthegradientdescent training,islowerwhenusingarepresentativedataset,andtheconvergence,inthecaseofstochasticgradientdescent, is,generally,faster. Furthermore,thecomputedbottleneckandHausdorffdistancesare,respectively,lowerandupper boundsoftheGromov-Hausdorffdistancewhichisourestimatorofrepresentativeness. R. Gonzalez-Diaz, M.A. Gutiérrez-Naranjo, E. Paluzo-Hidalgo: Preprint submitted to Elsevier Page 10 of 17 (a) A binary classification problem to distinguish between the upper and the lower semicircumference. It is given by a sampled circumference. Representative Datasets: The Perceptron case Dataset b0b1Hausdorffdistance Representative dataset 1 (Fig. 2b)0.5 0.6 0.35 Representative dataset 2 (Fig. 2c)0.85 0.68 0.94 Table 1 The 0-dimensional and 1-dimensional botleneck distances and the Hausdorffdistance between the dataset given in Fig. 2a and, respectively, the datasets given in Fig. 2b and Fig. 2c. Corollary 2. Let É Dbe a "-representative dataset of Dwith optimal ". Let Dgm(X)and Dgm(É X)be the persistence diagrams of Xand É X, respectively. Then, 1 2dBDgmp(X),Dgmp(É X))f"fdHX,É X. Toillustratetheusefulnessofthislastresult,wewilldiscussasimpleexample. InFig.2a,abinaryclassification problem is given: Two classes corresponding, respectively, to the upper and the lower semicircumference together with a subsample of the circumference are shown. In Fig. 2c, we can see a subset of the original dataset given in Fig. 2a and a possible decision boundary. Since the decision boundaries are different, we should not consider the datasetstorepresentthesameclassificationproblem. However,thesubsetshowninFig.2bismoreaccurate,keeping therepresentativenessoftheoriginaldataset. Besides,wecouldsaythatminimizingtheerrorfunctioninthecaseof Fig.2bisalmostthesameasminimizingtheerrorfunctioninthecaseofFig.2a. This,thatisevidentfortheeye,can be determined computing the bottleneck distance between the two persistence diagrams and the Hausdorffdistance betweenthetwodatasets(seethevaluesshowninTable1). UsingCorollary2,wecaninferthat0.3f"f0.35 forthedatasetgiveninFig.2band0.425 f"f0.94 forthe datasetgivenin Fig.2c. Therefore,thedatasetgivenin Fig.2bcan beconsideredmorerepresentativeof thedataset showedinFig.2athanthedatasetpicturedinFig.2c,asexpected. (a) A binary classification problem given by a sampled circumference. In this case, the classification problem tries to distinguish between the upper andthelowersemicircumference. (b)(Representative dataset 1) Asubsetofthebinaryclassificationproblem given in Fig. 2a. In this case, we can saythatitisrepresentativeoftheoriginaldataset. (c) (Representative dataset 2) A subsetofthebinaryclassificationproblem given in Fig. 2a. As we can see, it is notreallyrepresentativeoftheoriginal dataset. Figure 2: Illustration of a binary classification problem and the representative dataset concept. 6. Experimental Results: The Perceptron Case In this section, two experiments are provided in Subsection 6.1 and Subsection 6.2 for the perceptron case, to supportourresultsand illustratetheusefulnessofour method. Inthe firstexperiment,twointerlacedsolidtorusare sampledand,inthesecondexperiment,theIrisdatasetisconsidered. Inbothexperiments,theperceptronisinitiated withthesameweightandtrainedwiththreedifferentdatasets: theoriginaldataset,adominatingdataset(whichisthe outputofAlgorithm1andisarepresentativedataset)andarandomdatasetofthesamesizeasthesizeofthedominating dataset. Theseexperimentssupportthataperceptrontrainedwithrepresentativedatasetsgivesimilaraccuracythana perceptrontrainedwiththeoriginaldataset. Besides,weshowthatthetrainingtime,inthecaseofthegradientdescent training,islowerwhenusingarepresentativedataset,andtheconvergence,inthecaseofstochasticgradientdescent, is,generally,faster. Furthermore,thecomputedbottleneckandHausdorffdistancesare,respectively,lowerandupper boundsoftheGromov-Hausdorffdistancewhichisourestimatorofrepresentativeness. R. Gonzalez-Diaz, M.A. Gutiérrez-Naranjo, E. Paluzo-Hidalgo: Preprint submitted to Elsevier Page 10 of 17 (b) A subset of the binary classification problem given in Fig. 5.2a. In this case, we can say that it is representative of the original dataset. Representative Datasets: The Perceptron case Dataset b0b1Hausdorffdistance Representative dataset 1 (Fig. 2b)0.5 0.6 0.35 Representative dataset 2 (Fig. 2c)0.85 0.68 0.94 Table 1 The 0-dimensional and 1-dimensional botleneck distances and the Hausdorffdistance between the dataset given in Fig. 2a and, respectively, the datasets given in Fig. 2b and Fig. 2c. Corollary 2. Let É Dbe a "-representative dataset of Dwith optimal ". Let Dgm(X)and Dgm(É X)be the persistence diagrams of Xand É X, respectively. Then, 1 2dBDgmp(X),Dgmp(É X))f"fdHX,É X. Toillustratetheusefulnessofthislastresult,wewilldiscussasimpleexample. InFig.2a,abinaryclassification problem is given: Two classes corresponding, respectively, to the upper and the lower semicircumference together with a subsample of the circumference are shown. In Fig. 2c, we can see a subset of the original dataset given in Fig. 2a and a possible decision boundary. Since the decision boundaries are different, we should not consider the datasetstorepresentthesameclassificationproblem. However,thesubsetshowninFig.2bismoreaccurate,keeping therepresentativenessoftheoriginaldataset. Besides,wecouldsaythatminimizingtheerrorfunctioninthecaseof Fig.2bisalmostthesameasminimizingtheerrorfunctioninthecaseofFig.2a. This,thatisevidentfortheeye,can be determined computing the bottleneck distance between the two persistence diagrams and the Hausdorffdistance betweenthetwodatasets(seethevaluesshowninTable1). UsingCorollary2,wecaninferthat0.3f"f0.35 forthedatasetgiveninFig.2band0.425 f"f0.94 forthe datasetgivenin Fig.2c. Therefore,thedatasetgiveninFig.2b canbeconsideredmorerepresentativeofthedataset showedinFig.2athanthedatasetpicturedinFig.2c,asexpected. (a) A binary classification problem given by a sampled circumference. In this case, the classification problem tries to distinguish between the upper andthelowersemicircumference. (b)(Representative dataset 1) Asubsetofthebinaryclassificationproblem given in Fig. 2a. In this case, we can saythatitisrepresentativeoftheoriginaldataset. (c) (Representative dataset 2) A subsetofthebinaryclassificationproblem given in Fig. 2a. As we can see, it is notreallyrepresentativeoftheoriginal dataset. Figure 2: Illustration of a binary classification problem and the representative dataset concept. 6. Experimental Results: The Perceptron Case In this section, two experiments are provided in Subsection 6.1 and Subsection 6.2 for the perceptron case, to supportourresultsandillustratethe usefulnessofourmethod. Inthefirstexperiment, twointerlacedsolidtorusare sampledand,inthesecondexperiment,theIrisdatasetisconsidered. Inbothexperiments,theperceptronisinitiated withthesameweightandtrainedwiththreedifferentdatasets: theoriginaldataset,adominatingdataset(whichisthe outputofAlgorithm1andisarepresentativedataset)andarandomdatasetofthesamesizeasthesizeofthedominating dataset. Theseexperimentssupportthataperceptrontrainedwithrepresentativedatasetsgivesimilaraccuracythana perceptrontrainedwiththeoriginaldataset. Besides,weshowthatthetrainingtime,inthecaseofthegradientdescent training,islowerwhenusingarepresentativedataset,andtheconvergence,inthecaseofstochasticgradientdescent, is,generally,faster. Furthermore,thecomputedbottleneckandHausdorffdistancesare,respectively,lowerandupper boundsoftheGromov-Hausdorffdistancewhichisourestimatorofrepresentativeness. R. Gonzalez-Diaz, M.A. Gutiérrez-Naranjo, E. Paluzo-Hidalgo: Preprint submitted to Elsevier Page 10 of 17 (c) A subset of the binary classification problem given in Fig. 5.2a. As we can see, it is not really representative of the original dataset. Figure 5.2: Illustration of a binary classification problem and the representative dataset concept. 5.5 Experimental results: the perceptron case Two experiments are provided in Subsection 5.5 and Subsection 5.5for the perceptron case, to support our results and illustrate the usefulness of our method. In the first experiment, two interlaced solid torus are sampled and, in the second experiment, the Iris dataset is considered. In both experiments,the perceptronisinitiatedwiththesameweightsandtrained with three different datasets: the original dataset, a dominating dataset (which is the output of Algorithm 2and is a representative dataset) and a random dataset of the same size as the size of the dominating dataset. These experiments support that a perceptron trained with representative datasets gives similar accuracy than a perceptron trained with the original dataset. Besides, we show that the training time, in the case of the gradient descent training, is lower when using a representative dataset, and the convergence, in the case of stochastic gradient descent, is, generally, faster. Furthermore, the computed bottleneck and Hausdorff distances are, respectively, lower and upper bounds of the Gromov-Hausdorff distance which is our estimator of representativeness. Two interlaced solid torus dataset This experiment consists of a binary classification problem where each torus corresponds to a class. Algorithm 2was applied to obtain a representative dataset called dominating dataset smaller than the original one. A random dataset with the same number of points as the dominating dataset was also computed. In Figure 5.5a, Figure 5.5b and Figure 5.5c, the three datasets are shown: the original dataset, the dominating dataset and the random dataset. In Figure 5.9a, Figure 5.9b and Figure 5.9c, the persistence diagrams of these datasets are shown and, in Table 5.2, the Hausdorff the bottleneck distances of the 0 -persistence diagrams are provided. We can observe that the bottleneck and Hausdorff distance 6 A bridge between two theorems 6.1 Introduction . . . . . . . . . . . 51 6.2 Simplicial-map neural networks . . . . . . . . . . . . . . . . 52 6.3 Simplicial Approximation Theorem extension . . . . . . . . . . . 55 6.4 Universal Approximation Theorem extension . . . . . . . . . . . 57 6.5 Complexity of simplicial-map neural networks . . . . . . . . . . 59 6.6 Example . . . . . . . . . . . . . . 61 6.1 Introduction One of the first results in the development of neural networks is the Universal Approximation Theorem [55,63]. This classical result shows that any continuous function on a compact set in ℝ𝑛 can be approximated by a multi-layer feed-forward network with only one hidden layer and non-polynomial activation function (like the sigmoid function). It is wellknown 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 [55,63] 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 neural networks and the possibility that they act as universal approximators (see, e.g., [102–104] among many others). Undoubtedly, the use of many hidden layers is a big contribution to the success of deep learning architectures [105], but instead of exploring the power of depth, recently several studies have made interesting contributions about the power of width [106–108]. 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 neural network. In [109], 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 single-valued functions. Other interestingresearchlineontheexpressive powerofneuralnetworks follows an algebraic approach. Sum product networks are explored in [110–112], and tensor properties are studied in [113,114]. A different The header is a photo of Lausanne. It was taken during my visit to L2F. 6 A bridge between two theorems 52 perspective was introduced in [115] where "deep polynomial neural networks" (where the activation function is a polynomial exponentiation) are considered. In this chapter, we revisit [47] where 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 Universal Approximation Theorem (Theorem 3.3.1) is valid for all compact subset of ℝ𝑛 and our results presented here are valid for triangulable spaces. However, triangulable spaces are common in real-world problems. Therefore, an advantage of our approach from a practical point of view is that it can be useful to solve real-world problems that can be modeled by triangulable spaces. 6.2 Simplicial-map neural networks Inthis section,wewill show that simplicialmapscan defined a multi-layer feed-forward network that we will call simplicial-map neural network. In the following theorem, we will compute a two-hidden-layer feedforward network to model a simplicial map 𝜑𝑐:|𝐾|→|𝐿| where 𝐾 and 𝐿 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. The proof of the following Theorem provides the definition of simplicial-map neural networks that we establish in Definition 6.2.1. Theorem 6.2.1 Let us consider a simplicial map 𝜑𝑐:|𝐾| → |𝐿| between the underlying space of two finite pure simplicial complexes 𝐾 and 𝐿 . Then a two-hidden-layer feed-forward network N 𝜑 such that 𝜑𝑐(𝑥)=N 𝜑(𝑥) for all 𝑥∈ |𝐾|can be explicitly defined. Proof. Let us assume that dim(𝐾)=𝑛 and dim(𝐿)=𝑚 . Besides, let 𝜎1, . . . 𝜎𝑘 be the maximal 𝑛 -simplices of 𝐾 , where 𝜎𝑖=𝑣𝑖 0, . . . , 𝑣𝑖 𝑛 for all 𝑖 ; and let 𝜇1, . . . , 𝜇ℓ be the maximal 𝑚 -simplices of 𝐿 , where 𝜇𝑗=𝑢𝑗 0 , . . . , 𝑢𝑗 𝑚 for all 𝑗 . Let us consider a multi-layer feed-forward network N 𝜑with the following architecture: (1) an input layer composed of 𝑑0=𝑛neurons; (2) a first hidden layer composed of 𝑑1=𝑘·(𝑛+1)neurons; (3) a second hidden layer composed of 𝑑2=ℓ·(𝑚+1)neurons; and (4) an output layer with 𝑑3=𝑚neurons. Then, let N 𝜑=𝑓3◦𝑓2◦𝑓1 being 𝑓𝑖(𝑦)=𝜙𝑖(𝑊(𝑖);𝑦;𝑏𝑖) , 𝑖=1,2,3 . Now, 6 A bridge between two theorems 53 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 𝑥 in ℝ𝑛 is transformed into a 𝑘·(𝑛+1) vector. This vector can be seen as the juxtaposition of 𝑘 vectors of dimension 𝑛+1 , one for each of the 𝑘 simplices in 𝐾 . Each vector of dimension 𝑛+1 represents the barycentric coordinates of 𝑥 with respect to the corresponding simplex. The matrix 𝑊(1)∈M𝑘(𝑛+1)×𝑛 and the bias term 𝑏1 can be obtained from the barycentric coordinates relations as follows. Firstly, 𝑊(1)=©« 𝑊(1) 1 . . . 𝑊(1) 𝑘ª®®®¬ where 𝑊(1) 𝑖∈M (𝑛+1)×𝑛is: 𝑣𝑖 0··· 𝑣𝑖 𝑛 1··· 1−1 =𝑊(1) 𝑖𝐵𝑖 being {𝑣𝑖 0, . . . , 𝑣𝑛} the set of vertices of the maximal simplex 𝜎𝑖 of 𝐾 , and second, 𝑏1∈ℝ𝑘(𝑛+1)is: 𝑏1=©« 𝐵1 . . . 𝐵𝑘ª®®¬ . The function 𝜙1is then defined as: 𝜙1(𝑊(1);𝑦;𝑏1)=𝑊(1)𝑦+𝑏1. The matrix of weights 𝑊(2)∈M ℓ(𝑚+1)×𝑘(𝑛+1) between the first and the second hidden layer of N 𝜑 encodes the vertex map 𝜑 . The first hidden layer is composed of 𝑘·(𝑛+1) neurons that correspond to the vertices of the maximal simplices of 𝐾 . The second hidden layer is composed of ℓ· (𝑚+1) neurons that correspond to the vertices of the maximal simplices of 𝐿 . The matrix 𝑊(2) is composed of values zeros and ones. On the one hand, an element of 𝑊(2) has value 1 if the corresponding vertices in 𝐾 and 𝐿 are related by the vertex map 𝜑 , and, on the other hand, it has value 0 if they are not related by 𝜑. Then, 𝑊(2)=𝑊(2) 𝑠1,𝑠2 where 𝑊(2) 𝑠1,𝑠2=1if 𝜑(𝑣𝑖 𝑡)=𝑢𝑗 𝑟, 0otherwise; being 𝑠1=𝑗(𝑟+1) and 𝑠2=𝑖(𝑡+1) for 𝑖=1, . . . , 𝑘 ; 𝑗=1, . . . , ℓ ; 𝑡=0, . . . , 𝑛 ; and 𝑟=0, . . . , 𝑚 . The bias term 𝑏2 is the null vector. Then, the function 𝜙2is defined as: 𝜙2(𝑊(2);𝑦;𝑏2)=𝑊(2)𝑦. The output of the second hidden layer can be seen as the juxtaposition of ℓ vectors of dimension 𝑚+1 , one vector for each simplex in the simplicial complex 𝐿 . Each of these vectors represents the barycentric coordinates of 𝜑𝑐(𝑥) with respect to the corresponding simplex in 𝐿 . In the next step, 6 A bridge between two theorems 54 only vectors whose all coordinates are greater than or equal to zero are considered. This condition encodes the simplices of 𝐿 to which 𝜑𝑐(𝑥) belongs. Then, 𝜙3(𝑊(3);𝑦;𝑏3) maps the barycentric coordinates of 𝜑𝑐(𝑥) with respect to each maximal simplex of 𝐿 to which 𝜑𝑐(𝑥) belongs, to the Cartesian coordinates of 𝜑𝑐(𝑥). Specifically, 𝑊(3)=𝑊(3) 1··· 𝑊(3) ℓ∈M 𝑚×ℓ(𝑚+1), being 𝑊(3) 𝑗=𝑢𝑗 0··· 𝑢𝑗 𝑚 ; and 𝑏3 is the null vector. Finally, 𝜙3 is defined as: 𝜙3(𝑊(3);𝑦;𝑏3)=Pℓ 𝑗=1𝑧𝑗𝜓(𝑦𝑗) Pℓ 𝑗=1𝜓(𝑦𝑗) for 𝑦=©« 𝑦1 . . . 𝑦ℓª®®¬∈M ℓ·(𝑚+1) , with 𝑧𝑗=𝑊(3) 𝑗𝑦𝑗 and 𝜓(𝑦𝑗)=1 if all the coordinates of 𝑦𝑗 are greater than or equal to 0 and 𝜓(𝑦𝑗)=0 otherwise. Theparticularchoice of 𝜙3 and 𝜓 ismotivated bytheuse ofthebarycentric 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 6.2.1 establishes that a two-hidden-layer feedforward network can act equivalently to a simplicial map. The explicit construction of the neural network given in the proof of Theorem 6.2.1 is the main tool used in the next chapter for computing neural networks robust to adversarial attacks and it is what we call a simplicial-map neural network. Definition 6.2.1 (simplicial-map neural network) Let 𝐾 and 𝐿 be two finite pure simplicial complexes of dimension 𝑑 and 𝑘 , respectively. Let us consider the simplicial map 𝜑𝑐:|𝐾| → |𝐿| induced by a vertex map 𝜑(0):𝐾(0)→𝐿(0) . Let 𝜎1, . . . 𝜎𝑛 be the maximal simplices of 𝐾 , where 𝜎𝑠=𝑢𝑠 0, . . . , 𝑢𝑠 𝑑 and 𝑢𝑠 ℎ∈ℝ𝑑 for 𝑠∈~1, 𝑛 and ℎ∈~0, 𝑑 . Let 𝜇1, . . . , 𝜇𝑚 be the maximal simplices of 𝐿 , where 𝜇𝑗=𝑣𝑗 0, . . . , 𝑣𝑗 𝑘 and 𝑣𝑗 ℎ∈ℝ𝑘 for 𝑗∈~1, 𝑚 and ℎ∈~0, 𝑘 . The simplicial-map neural network induced by 𝜑𝑐 is a two-hidden-layer feed-forward neural network denoted by N 𝜑with the following architecture: Ian input layer composed of 𝑑0=𝑑neurons; Ia first hidden layer composed of 𝑑1=𝑛(𝑑+1)neurons; Ia second hidden layer composed of 𝑑2=𝑚(𝑘+1)neurons; and Ian output layer with 𝑑3=𝑘neurons. Then, N 𝜑=𝑓3◦𝑓2◦𝑓1being 6 A bridge between two theorems 55 𝑓𝑖(𝑦)=𝜙𝑖(𝑊(𝑖);𝑦;𝑏𝑖),for 𝑖∈~1,3. Firstly, 𝑊(1)=©« 𝑊(1) 1 . . . 𝑊(1) 𝑛ª®®®¬∈M 𝑛(𝑑+1)×𝑑being 𝑊(1) 𝑖𝐵𝑖=𝑢𝑠 0··· 𝑢𝑠 𝑑 1··· 1−1 ∈M (𝑑+1)×(𝑑+1) where 𝑊(1) 𝑖∈M (𝑑+1)×𝑑 and 𝐵𝑖∈ℝ𝑑+1 . The bias term 𝑏1∈ℝ𝑛(𝑑+1) is 𝑏1=©« 𝐵1 . . . 𝐵𝑛ª®®¬ and the function 𝜙1is then defined as: 𝜙1(𝑊(1);𝑦;𝑏1):=𝑊(1)𝑦+𝑏1. Secondly, 𝑊(2)=𝑊(2) ℎ,ℓ ∈M 𝑚(𝑘+1)×𝑛(𝑑+1)where 𝑊(2) ℎ,ℓ :=1if 𝜑(0)(𝑢𝑠 𝑡)=𝑣𝑗 𝑟, 0otherwise; being ℎ=𝑗(𝑟+1) and ℓ=𝑠(𝑡+1) for 𝑠∈~1, 𝑛 ; 𝑗∈~1, 𝑚 ; 𝑡∈~0, 𝑑 ; and 𝑟∈~0, 𝑘 . The bias term 𝑏2∈ℝ𝑚(𝑘+1) is null and the function 𝜙2 is defined as: 𝜙2(𝑊(2);𝑦;𝑏2):=𝑊(2)𝑦. Thirdly, 𝑊(3)=𝑊(3) 1··· 𝑊(3) 𝑚∈M𝑘×𝑚(𝑘+1)being 𝑊(3) 𝑗:=𝑣𝑗 0··· 𝑣𝑗 𝑘for 𝑗∈~1, 𝑚, the bias term 𝑏3is null, and 𝜙3is defined as: 𝜙3(𝑊(3);𝑦;𝑏3):=P𝑗∈~1,ℓ𝑧𝑗𝜓(𝑦𝑗) P𝑗∈~1,ℓ𝜓(𝑦𝑗) being 𝑧𝑗:=𝑊(3) 𝑗𝑦𝑗for 𝑦=©« 𝑦1 . . . 𝑦𝑚ª®®¬∈M𝑚·(𝑘+1)and 𝜓(𝑦𝑗):=1if all the coordinates of 𝑦𝑗are ≥0, 0otherwise. 6.3 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 𝑔:|𝐾|→|𝐿| between the underlying spaces of two simplicial complexes 𝐾 and 𝐿 . The first observation is that the Simplicial Approximation 6 A bridge between two theorems 56 Theorem (Theorem 3.1.2) 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. Proposition 6.3.1 Given 𝜖 > 0 and a continuous function 𝑔:|𝐾|→|𝐿| between the underlying spaces of two simplicial complexes 𝐾 and 𝐿 , there exist 𝑡1, 𝑡2>0 such that 𝜑𝑐:|Sd𝑡1𝐾|→|Sd𝑡2𝐿| is a simplicial approximation of 𝑔and ||𝑔−𝜑𝑐|| ≤ 𝜖. Proof. By Theorem 3.1.1, there exists 𝑡2 such that 𝑚(Sd𝑡2𝐿) ≤ 𝜖 . Then, by Theorem 3.1.2, there exists 𝑡1 such that 𝜑𝑐:|Sd𝑡1𝐾| → |Sd𝑡2𝐿| is a simplicial approximation of 𝑔: |𝐾| |𝐿| 𝐾 𝐿 Sd𝑡1𝐾Sd𝑡2𝐿 |Sd𝑡1𝐾| |Sd𝑡2𝐿| 𝑔 Sd Sd 𝜑𝑐 Besides, ||𝑔−𝜑𝑐|| ≤ 𝜖because 𝑚(Sd𝑡2𝐿) ≤ 𝜖. Algorithm 3: Computing a vertex map that induces a simplicial approximation Input: A continuous function 𝑔:|𝐾|→|𝐿| between the underlying spaces of two simplicial complexes 𝐾and 𝐿, and an integer 𝑡 where Sd𝑡𝑘satisfies the star condition: for each 𝑣∈Sd𝑡𝐾(0) there exists 𝑤∈𝐿(0)such that 𝑔(|𝑠𝑡(𝑣)|) ⊆ |𝑠𝑡(𝑤)|. Output: A vertex map 𝜑 that induces simplicial approximation 𝜑𝑐 of 𝑔. 1foreach vertex 𝑣∈Sd𝑡𝐾(0)do 2Choose 𝑤∈𝐿(0)such that 𝑔(|𝑠𝑡(𝑣)|) ⊆ |𝑠𝑡(𝑤)| and define 𝜑(𝑣):=𝑤. Algorithm 3is inspired in the proof of the Simplicial Approximation Theorem given in [57, p. 56] and computes a vertex map 𝜑: Sd𝑡𝐾(0)→ 𝐿(0) from which we can define the simplicial approximation 𝜑𝑐:|Sd𝑡𝐾| → |𝐿|of a continuous function 𝑔:|𝐾|→|𝐿|. Theorem 6.3.2 Given a continuous function 𝑔:|𝐾| → |𝐿| and 𝜖 > 0 , a simplicial-map neural network N such that ||𝑔−N|| ≤ 𝜖 can be explicitly defined. 6 A bridge between two theorems 57 Proof. By Proposition 6.3.1, there exists a simplicial approximation 𝜑𝑐 of 𝑔 such that ||𝑔−𝜑𝑐|| ≤ 𝜖 , that can be computed using Algorithm 3. Then, by Theorem 6.2.1 there exists N 𝜑such that 𝜑𝑐=N 𝜑. 6.4 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 SimplicialApproximationTheoremgiveninProposition 6.4.3, we provide a constructive version of the Universal Approximation Theorem that approximates any continuous function (under some specific conditions) arbitrarily close. Firstly, let us extend the definition of a mesh of a simplicial complex in the following way. Definition 6.4.1 Let 𝑋 be a triangulable metric space and (𝐾, 𝜏) a finite triangulation of 𝑋. The mesh of 𝑋induced by (𝐾, 𝜏)is defined as ˜ 𝑚(𝐾,𝜏)(𝑋)=max ˜ 𝛿(𝜎) | 𝜎∈𝐾 where ˜ 𝛿(𝜎)=max 𝑑𝑋(𝑥, 𝑦) | 𝑥=𝜏−1(𝑎), 𝑦 =𝜏−1(𝑏);𝑎, 𝑏 ∈𝜎 is the extended diameter of a simplex. Then, the following property between the mesh and its extended version can be proved. Proposition 6.4.1 Let (𝐾, 𝜏) be a finite triangulation of a metric space 𝑋 . For all 𝜖 > 0 there exists 𝑡>0 and 𝛾 > 0 such that if 𝑚(Sd𝑡𝐾) ≤ 𝛾 then ˜ 𝑚(Sd𝑡𝐾,𝜏)(𝑋) ≤ 𝜖. Proof. Let us consider 𝑎, 𝑏0∈ |𝐾| . Then, 𝑎∈𝜎0 for some maximal simplex 𝜎0∈𝐾 . If 𝑏0 belongs to 𝜎0 then ||𝑎−𝑏0|| ≤ 𝛿(𝜎0) and 𝑑𝑋(𝑥, 𝑦0) ≤ ˜ 𝛿(𝜎0) , being 𝑥=𝜏−1(𝑎) and 𝑦0=𝜏−1(𝑏0) . Otherwise, we repeat the reasoning with Sd 𝐾 . Now, 𝑎 and 𝑏0 can belong to the same simplex in Sd 𝐾 or not. If they belong to the same simplex in Sd 𝐾 , write 𝑏1=𝑏0 . If not, take a new point 𝑏1 such that 𝑎, 𝑏1∈𝜎1 and 𝜎1∈Sd 𝜎0 . Therefore, ||𝑎−𝑏1|| ≤ 𝛿(𝜎1) ≤ 𝛿(𝜎0) . Besides, 𝑑𝑋(𝑥, 𝑦1) ≤ ˜ 𝛿(𝜎1) ≤ ˜ 𝛿(𝜎0) being 𝑥=𝜏−1(𝑎) and 𝑦1=𝜏−1(𝑏1) This process can be iterated: ||𝑎−𝑏𝑡|| ≤ 𝛿(𝜎𝑡) ≤ ··· ≤ 𝛿(𝜎1) ≤ 𝛿(𝜎0) and 𝑑𝑋(𝑥, 𝑦𝑡) ≤ ˜ 𝛿(𝜎𝑡) ≤ ··· ≤ ˜ 𝛿(𝜎1) ≤ ˜ 𝛿(𝜎0) , being 𝑥=𝜏−1(𝑎) and 𝑦𝑡=𝜏−1(𝑏𝑡) . By this, we have defined a sequence {𝑏𝑖}𝑡 𝑖=0 that converges to 𝑎 . Therefore, given 𝜖 > 0 , there exists 𝑡 such that 𝑑𝑋(𝑥, 𝑦𝑡) ≤ 𝜖 , being 𝑥=𝜏−1(𝑎) and 𝑦𝑡=𝜏−1(𝑏𝑡) . Let us suppose, without loss of generality, that ˜ 𝛿(𝜎𝑡)=˜ 𝑚(Sd𝑡𝐾,𝜏)(𝑋) . Then, we can consider 𝛾=𝑚(Sd𝑡𝐾). 6 A bridge between two theorems 58 Corollary 6.4.2 Given 𝜖 > 0 and a finite triangulation (𝐾, 𝜏) of a metric space 𝑋, there exists 𝑡such that ˜ 𝑚(Sd𝑡𝐾,𝜏)(𝑋) ≤ 𝜖. Proof. By Theorem 3.1.1 there exists 𝑡0 such that 𝑚(Sd𝑡0𝐾) ≤ 𝛾 . Then, by Proposition 6.4.1, there exists 𝑡such that ˜ 𝑚(Sd𝑡𝐾,𝜏)(𝑋) ≤ 𝜖. Given two continuous function 𝑔1 and 𝑔2 between two metric spaces 𝑋 and 𝑌 , we denote sup{𝑑𝑌(𝑔1(𝑥), 𝑔2(𝑥)) | 𝑥∈𝑋} also by ||𝑔1−𝑔2|| . Now, given a continuous function 𝑔 between two finitely triangulable metric spaces 𝑋 and 𝑌 , there exists a simplicial approximation 𝜑𝑐 “arbitrarily close” to 𝑔. Proposition 6.4.3 Let 𝑋 and 𝑌 be two finitely triangulable metric spaces, 𝑔:𝑋→𝑌 a continuous function, and 𝜖 > 0 . Then, there exist two finite triangulations (𝐾, 𝜏𝐾) and (𝐿, 𝜏𝐿) of 𝑋 and 𝑌 , respectively, and a simplicial approximation 𝜑𝑐:|Sd𝑡1𝐾| → |Sd𝑡2𝐿| such that ||𝑔−˜ 𝜑𝑐|| ≤ 𝜖 being ˜ 𝜑𝑐=𝜏−1 𝐿◦𝜑𝑐◦𝜏𝐾. Proof. First, by Corollary 6.4.2, there exists 𝑡2such that ˜ 𝑚(Sd𝑡2𝐿,𝜏𝐿)(𝑌) ≤ 𝜖 . Next, by Theorem 3.1.2, there exists 𝑡1>0 and a vertex map 𝜑:(Sd𝑡1𝐾)(0)→ (Sd𝑡2𝐿)(0) such that 𝜑𝑐:|Sd𝑡1𝐾| → |Sd𝑡2𝐿| is a simplicial approximation of 𝜏𝐿◦𝑔◦𝜏−1 𝐾 . Take into account that |Sd𝑡1𝐾|=|𝐾| and |Sd𝑡2𝐿|=|𝐿| . Finally, since ˜ 𝑚(𝐿,𝜏𝐿)(𝑌) ≤ 𝜖 then ||𝑔−˜ 𝜑𝑐|| ≤ 𝜖. Below, a diagram that schematizes the proof: 𝑋 𝑌 |𝐾| |𝐿| 𝐾 𝐿 Sd𝑡1𝐾Sd𝑡2𝐿 (Sd𝑡1𝐾)(0)(Sd𝑡2𝐿)(0) 𝜏𝐾 𝑔 𝜏𝐿 𝜑𝑐 Sd Sd 𝜑 Finally, we reach the main result of this section: Given a continuous function 𝑔 between two finitely triangulable spaces 𝑋 and 𝑌 , we can obtain two finite simplicial complexes 𝐾 and 𝐿 associated to them, and a multi-layer feed-forward network between the underlying spaces of 𝐾 and 𝐿which “approximates” 𝑔. 6 A bridge between two theorems 59 Theorem 6.4.4 Given a continuous function 𝑔:𝑋→𝑌 between two finitely triangulable metric spaces 𝑋 and 𝑌 and finite triangulations (𝐾, 𝜏𝐾) and (𝐿, 𝜏𝐿) of, respectively, 𝑋 and 𝑌 , a simplicial map neural network N such that ||𝑔−˜ N|| ≤ 𝜖 , being ˜ N=𝜏−1 𝐿◦N◦𝜏𝐾 , can be explicitly defined. Proof. By Proposition 6.4.3, there exists a simplicial approximation 𝜑𝑐 such that ||𝑔−˜ 𝜑𝑐|| ≤ 𝜖 . Finally, by Theorem 6.2.1, there exists N such that N=𝜑𝑐in all the domain. Let us remark that the Universal Approximation Theorem (Theorem 3.3.1) is valid for any compact subset of ℝ𝑛 , regardless of whether they are locally contractible or not. Not all compact sets in a metric space are locally contractible (see [116, Chapter 17.7, p. 426]). Nevertheless, as far as we know, non-locally contractible spaces are very odd in ℝ𝑛 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 6.1). Figure 6.1: From left to right and from top to bottom: (1) A sphere and a loop that intersect;(2)the sphere and theloopwith a possible triangulation (the loop is covered by 2 -simplices); (3) the triangulation of the loop and the sphere. 6.5 Complexity of simplicial-map neural networks 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. Definition 6.5.1 The complexity of a neural network is the maximum of the widths of its hidden layers. 7 Robustness to adversarial examples 66 pirical margin errors was proposed, and in [126], the discriminability of deep neural networks features is enhanced via an ensemble strategy. In this chapter, we revisit [48] where we explore the idea of margin between regions associated with labels from a novel point of view. To the best of our knowledge, this is the first time where adversarial examples are studied with techniques from computational topology. Our approach can be summarized as follows. The starting point is a classification problem where the data are 𝑑 -dimensional vectors which are mapped onto a set of 𝑘 labels with a one-hot representation. From a topological point of view, such set of instances can be seen as the vertices of a simplicial complex embedded in a bounded polytope in ℝ𝑑 (details are given below), and the set of 𝑘 one-hot labels can be endowed with the structure of a 𝑘 -dimensional simplex (in fact, 𝑘+1 labels are considered since we add an unknown label to the set of one-hot labels). In this way, a simplicial map between both topological structures arises in a natural manner, since each vertex in the simplicial complex corresponds to an instance of the dataset, and it is mapped onto the vertex of the simplex that represents the corresponding label. The second step is to apply the extended Simplicial Approximation Theorem [47] (see page 56) obtaining a a neural network that classifies correctly all the instances of the dataset. As shown in Chapter 6, all the weights of such a neural network can be computed directly from the simplicial maps without any kind of training processes. Finally, by considering these ideas together with a subdivision process of the simplices, a decision boundary for the classification problem is computed to make the neural network robust to adversarial attacks of a given size, since the mesh of a simplicial complex can be bounded by the number of subdivisions and the neural network obtained is based on the simplices used in the simplicial map. Regarding other approaches to these ideas found in the literature, in [127], the authors proved the existence of a two-hidden-layer neural network which can approximate any continuous multivariable function with arbitrary precision, and, in [128], they provided a constructive method through a numerical analysis approach. Such papers can be seen as alternative constructive proofs to the Universal Approximation Theorem where no adversarial examples on classification problems were considered. A related approach that uses simplicial complexes to feed a neural network, is the concept of simplicial neural network, provided in [129], that consists of a generalization of graph neural networks with the property that compared to graph neural networks, simplicial neural networks exploit higher order relationships between the input data due to representing the data using simplicial complexes. Let us observe that, although having a similar name, our approach has a totally different goal. 7.2 Classification with simplicial-map neural networks In this section, simplicial-map neural networks are considered as tools for classification tasks and for the study of adversarial examples. As usual, the classification problem will consist of finding a set of weights adapted to a labelled dataset given a fixed architecture. 7 Robustness to adversarial examples 67 Firstly, Let us state some basic notation. Hereafter, let 𝑘>0 be an integer and let 𝑒𝑘 0:=(0, . . . , 0) be the origin of the Euclidean space ℝ𝑘 . Let a one-hot vector of length 𝑘 be denoted as 𝑒𝑘 𝑖=(0,𝑖−1 ···,0,1,0,𝑘−𝑖 ···,0) with 𝑖∈~1, 𝑘 . Let 𝔼𝑘:={𝑒𝑘 𝑖:𝑖∈~1, 𝑘} be the set of all the one-hot vectors of length 𝑘 . Let us observe that 𝔼𝑘+1={𝑒𝑘 𝑖×0 : 𝑖∈~1, 𝑘}∪{𝑒𝑘 0×1} where 𝑒𝑘 𝑖×0 :=(0,𝑖−1 ···,0,1,0,𝑘−𝑖 ···,0,0)=𝑒𝑘+1 𝑖 for 𝑖∈~1, 𝑘 and 𝑒𝑘 0×1 := (0,𝑘 ···,0,1)=𝑒𝑘+1 𝑘+1. Definition 7.2.1 Let 𝑛, 𝑑, 𝑘 >0 be integers. A labelled dataset 𝐷 is a finite set of pairs 𝐷=(𝑝𝑗, ℓ𝑗):𝑗∈~1, 𝑛, 𝑝𝑗∈ℝ𝑑, ℓ𝑗∈𝔼𝑘 where, for 𝑗, ℎ ∈~1, 𝑛 , 𝑝𝑗≠𝑝ℎ if 𝑗≠ℎ , and ℓ𝑗 represents a one-hot vector. We say that ℓ𝑗 is the label of 𝑝𝑗 or, equivalently, that 𝑝𝑗 belongs to the class ℓ𝑗 . Besides, we will denote by 𝐷𝑃the ordered set of points h𝑝𝑗i𝑗. The concept of supervised classification problem for neural networks can be defined as follows. Definition 7.2.2 Given a labelled dataset 𝐷⊂ℝ𝑑×𝔼𝑘 , an integer 𝑚>0 , and activation functions 𝜙𝑖 for 𝑖∈~1, 𝑚 , a supervised classification problem consists of looking for the weights 𝑊(𝑖) and bias terms 𝑏𝑖 for 𝑖∈~1, 𝑚 , such that the associated neural network N:𝑋→𝑌 , with 𝑋⊆ℝ𝑑 , 𝑌⊆ℝ𝑘 and 𝐷⊆𝑋×𝑌, satisfies: IN(𝑝)=ℓfor all (𝑝, ℓ) ∈ 𝐷. IN maps 𝑥∈𝑋 to a vector of scores N(𝑥)=(𝑦1, . . . , 𝑦𝑘) ∈ 𝑌 such that 𝑦𝑖∈ [0,1]for 𝑖∈~1, 𝑛and P𝑖∈~1,𝑛𝑦𝑖=1. If such a neural network N exists, we will say that N characterizes 𝐷 , or, equivalently, that Ncorrectly classifies 𝐷. Let us remark that the success of a classification model as a neural network is not usually measured on the correct classification on the input dataset, but on the correct classification of unseen examples, (that is, pairs not in 𝐷 ), collected in a test set. In this work, we chose such a restrictive definition since we are more interested in dealing with the problem of the robustness of neural networks against adversarial attacks than in the problem of overfitting. Besides, let us observe that, as usual, the scores can be interpreted as a probability distribution over the labels. Remark 7.2.1 It is known that some functions like the logistic sigmoid, the softmax or the softplus satisfy the properties of a probability distribution and they are broadly applied in deep learning models. Our function also behaves as a probability distribution which is adequate for multiclassification tasks. Next, we provide the definition of some of the main concepts in this chapter, the confidence set 𝑇N , the classified set 𝐶N , and the decision boundary ΓN of N . The intuition behind these concepts is that 𝑥 belongs to the confidence set of N if the output N(𝑥) is one of the possible one-hot vectors. If the output is a vector where the maximum is reached in exactly 7 Robustness to adversarial examples 68 one coordinate, we say that 𝑥 belongs to the classified set of N . Otherwise, the output is a vector where the maximum is reached in two or more coordinates, i.e., the instance has equal probability to belong to two or more output classes, then we say that 𝑥 belongs to the decision boundary of N. Let us observe that 𝑇N⊆𝐶Nand 𝐶NtΓN=𝑋. Definition 7.2.3 Let 𝑑, 𝑘 >0 be integers. Let 𝐷⊂ℝ𝑑×𝔼𝑘 be a labelled dataset and N:𝑋→𝑌 a neural network that characterizes 𝐷 . Let 𝑥∈𝑋 , with N(𝑥)=(𝑦1, . . . , 𝑦𝑘) ∈ 𝑌 . If there exists 𝑗∈~1, 𝑘 such that 𝑦𝑗> max{𝑦𝑖:𝑖∈~1, 𝑘, 𝑖 ≠𝑗} , then we say that 𝑥 belongs to the set 𝐶𝑗 N and it has label 𝑒𝑗∈𝔼𝑘 (with probability 𝑦𝑗 ). Moreover, we define 𝐶N to be the union of the sets 𝐶𝑗 N for 𝑗∈~0, 𝑘 . Besides, when 𝑦𝑗=1 , we say that 𝑥 belong to the confidence set 𝑇N . Finally, we say that 𝑥 belongs to the decision boundary ΓNif there exists 𝑗∈~1, 𝑛such that 𝑦𝑗=max{𝑦𝑖:𝑖∈~1, 𝑘, 𝑖 ≠𝑗}. The following is a key result to define a simplicial-map neural network that characterizes a given labelled dataset. Proposition 7.2.1 Let 𝑑, 𝑘 >0 be integers. Let 𝐿 be the simplicial complex with only one maximal 𝑘 -simplex 𝜎={𝑣0, . . . , 𝑣𝑘} with 𝑣𝑖=𝑒𝑘 𝑖×0 for 𝑖∈~1, 𝑘 and 𝑣0=𝑒𝑘 0×1 . Let 𝐷⊂ℝ𝑑×𝔼𝑘 be a labelled dataset and let 𝑉P be the vertices of a convex polytope P such that 𝐷𝑃⊂P . Let us assume that 𝐷𝑃 is in general position. Let 𝐾=D(𝐷𝑃∪𝑉P) . Then, the map 𝜑(0):𝐾(0)→𝐿(0)defined as follows is a vertex map: 𝜑(0)(𝑢):=ℓ×0if (𝑢, ℓ) ∈ 𝐷, 𝑣0if 𝑢∈𝑉P. Proof. 𝐿 is composed of a maximal simplex. Any subset of vertices of a simplex is a simplex by definition. Then, any map between vertices of 𝐾(0)to 𝐿(0)is a vertex map. Specifically, 𝜑(0)is a vertex map. Byabuse of notation,we willsaythata point 𝑦∈ℝ𝑘 with barycentric coordinates (𝑦0, . . . , 𝑦𝑘) haslabel 𝑗∈~0, 𝑘 if 𝑦𝑗>max{𝑦𝑖:𝑖∈~0, 𝑘, 𝑖 ≠𝑗} . Let us notice that an unknown label has been assigned to the vertex 𝑣0 of 𝐿. Proposition 7.2.2 Let 𝜑(0):𝐾(0)→𝐿(0) be the vertex map defined in Proposition 7.2.1. Then, the simplicial-map neural network N 𝜑:|𝐾| → |𝐿| induced by the simplicial map 𝜑𝑐characterizes 𝐷. Proof. By Theorem 6.2.1, the neural network N 𝜑 satisfies that N 𝜑(𝑥)= 𝜑𝑐(𝑥) for all 𝑥∈ |D(𝐷𝑃∪𝑉P)| . Besides, let us observe that the Cartesian coordinates of N 𝜑(𝑥) coincide with its barycentric coordinates. Moreover, for all 𝑥∈𝐷𝑃 , N 𝜑(𝑥)=𝜑(0)(𝑥) and, by definition, 𝜑(0)(𝑥)=ℓ×0 when (𝑥, ℓ) ∈ 𝐷. Then, we can conclude that N 𝜑characterizes 𝐷. Again, by abuse of notation, when N 𝜑 is a simplicial-map neural network, we will denote by 𝑇𝜑 , 𝐶𝜑 , and Γ𝜑 , its confidence set, classified set and decision boundary, respectively. 7 Robustness to adversarial examples 69 Figure 7.1: Let 𝐾=D(𝐷𝑃∪𝑉P) bethe Delaunaycomplexof 𝐷𝑃∪𝑉P where 𝐷𝑃 isthe set {𝐴, 𝐵, 𝐶} ofredandbluepoints, and 𝑉P arethe green vertices (depicted in the center). Let 𝐿 be the simplicial complex with one maximal simplex 𝜎={𝑣0=(0,0,1), 𝑣1=(0,1,0), 𝑣2=(1,0,0)} (pictured on the right). Let us consider the vertex map 𝜑(0) that sends the blue points 𝐴, 𝐵 to 𝑣1 , the red point 𝐶 to 𝑣2 , and the green points (labelled as unknown) to 𝑣0 . Then, 𝜑(0) gives rise to the simplicial map 𝜑𝑐 and the simplicial-map neural network N 𝜑 . The decision boundary of N 𝜑 is pictured on the center as the set of points in the boundary of the red, blue or green region. For example, N 𝜑(𝐷)=(1 3,1 3,1 3) , N 𝜑(𝐹)=(1 2,1 2,0) and N 𝜑(𝐺)=(0,1 2,1 2) . Let us consider now the barycenter subdivision of 𝐾 shown on the left and the simplicial map 𝜔𝑐 which relates both simplicial complexes. The decision boundary of N 𝜑◦𝜔is the gray zone on the left picture. Remark 7.2.2 Firstly, let us observe that, with the assumptions of Proposition 7.2.1, if 𝑥∈ℝ𝑑 belongs to the decision boundary Γ𝜑 then 𝑥∈ |𝜎| for some 𝜎∈𝐾 satisfying that there are at least two vertices in 𝜎 having different labels. Moreover, 𝑥∈ |𝜇| for some 𝜇∈Sd 𝐾 with all its vertices in Γ𝜑 . Secondly, if 𝜎 is a 𝑑 -simplex in Sd 𝐾 , then either all its vertices belong to the confidence set 𝑇𝜑 or 𝜎=𝜎1∪𝜎2 with 𝜎1,𝜎2∈Sd 𝐾 satisfying that |𝜎1| ⊆ Γ𝜑 and |𝜎2| ⊆ 𝑇𝜑 . Finally, if 𝜎 is a 𝑑 -simplex in Sd𝑡𝐾 for 𝑡>0 then either all its vertices belong to the classified subset 𝐶𝑗 𝜑 for some 𝑗∈~0, 𝑘 , or 𝜎=𝜎1∪𝜎2 with 𝜎1,𝜎2∈Sd𝑡𝐾satisfying that |𝜎1| ⊆ Γ𝜑and ∅≠|𝜎|\|𝜎1| ⊆ 𝐶𝑗 𝜑. As the following result states, when 𝐾=D(𝐷𝑃∪𝑉P) , we can obtain a vertex map 𝜑(0) 𝑡 from (Sd𝑡𝐾)(0) to (Sd𝑡𝐿)(0) applying the barycentric subdivision, inducing a neural network N 𝜑𝑡 that coincides with N 𝜑 for any integer 𝑡>0. Figure 7.1 illustrates these concepts. Lemma 7.2.3 Let 𝜑(0) 0:=𝜑(0) be the vertex map defined in Proposition 7.2.1. For an integer 𝑡>1 and any 𝑣∈ (Sd𝑡𝐾)(0) , there exists 𝜇∈Sd𝑡−1𝐾 such that 𝑤=bar𝜇. Then, the map 𝜑(0) 𝑡:(Sd𝑡𝐾)(0)→ (Sd𝑡𝐿)(0)defined as: 𝜑(0) 𝑡(𝑤):=bar 𝜑𝑡−1(𝜇) is a vertex map inducing a neural network N 𝜑𝑡 that coincides with N 𝜑 for any integer 𝑡≥0. Proof. Let 𝑡>0 be an integer. Let us observe that 𝜑(0) 0 is a vertex map. By induction, let us assume that 𝜑(0) 𝑡−1:(Sd𝑡−1𝐾)(0)→ (Sd𝑡−1𝐿)(0) is a vertex map. Let 𝜎∈Sd𝑡𝐾 . By definition of barycentric subdivision, we can assume that 𝜎={𝑤0, . . . , 𝑤𝑘} with 𝑤𝑖=bar𝜇𝑖 , being 𝜇𝑖 a face of 7 Robustness to adversarial examples 70 𝜇𝑗∈Sd𝑡−1𝐾for 𝑖, 𝑗 ∈~0, 𝑘and 𝑖<𝑗. Then, {𝑣∈Sd𝑡𝐿:∃𝑤∈𝜎,𝜑(0) 𝑡(𝑤)=𝑣}= ={𝜑(0) 𝑡(𝑤𝑖):𝑖∈~0, 𝑘} ={bar 𝜑𝑡−1(𝜇𝑖):𝑖∈~0, 𝑘}. Since 𝜑(0) 𝑡−1 is a simplicial map, then 𝜑𝑡−1(𝜇𝑖) is a simplex of Sd𝑡−1𝐿 and 𝜑𝑡−1(𝜇𝑖) is a face of 𝜑𝑡−1(𝜇𝑗) for all 𝑖, 𝑗 ∈~0, 𝑘 with 𝑖<𝑗 , by definition of 𝜑𝑡−1. Then, {bar 𝜑𝑡−1(𝜇𝑖):𝑖∈~0, 𝑘}is a simplex of Sd𝑡𝐿. Now, let us see that N 𝜑𝑡=N 𝜑 . By induction, let us prove that N 𝜑𝑡=N 𝜑𝑡−1 . Let 𝑥∈ |𝐾| . Then, there exist a 𝑑 -simplex 𝜇={𝑤0, . . . , 𝑤𝑛} ∈ Sd𝑡𝐾 and a 𝑑 -simplex 𝜎={𝑢0, . . . , 𝑢𝑑} ∈ Sd𝑡−1𝐾 such that 𝑥∈ |𝜇|⊂|𝜎| and 𝑤𝑖=bar{𝑢0, . . . , 𝑢𝑖}for all 𝑖∈~0, 𝑑. Then, N 𝜑𝑡(𝑥)=𝜑𝑐 𝑡(𝑥)=X 𝑖∈~0,𝑑 𝜆𝑖𝑤𝑖 being 𝜆𝑖∈ [0,1]for all 𝑖∈~0, 𝑑and P𝑖∈~0,𝑑𝜆𝑖=1. Therefore, N 𝜑𝑡(𝑥)=X 𝑖∈~0,𝑑 𝜆𝑖X 𝑗∈~0,𝑖 1 𝑖+1𝑢𝑗=X 𝑖∈~0,𝑑 𝜆0 𝑖𝑢𝑖 being 𝜆0 𝑖=P𝑗∈~𝑖,𝑑 𝜆𝑗 𝑗+1. Let us observe that X 𝑖∈~0,𝑑 𝜆0 𝑖=X 𝑖∈~0,𝑑(𝑖+1)𝜆𝑖 𝑖+1=X 𝑖∈~0,𝑑 𝜆𝑖=1. Now, let us observe that 𝜆0 𝑖=X 𝑗∈~𝑖,𝑑 𝜆𝑗 𝑗+1≥0and X 𝑗∈~𝑖,𝑑 𝜆𝑗 𝑗+1≤1 𝑖+1X 𝑗∈~𝑖,𝑑 𝜆𝑗≤1 𝑖+1≤1, for all 𝑖∈~0, 𝑑. Then, for all 𝑥∈ |𝐾|, N 𝜑𝑡(𝑥)=X 𝑖∈~0,𝑑 𝜆0 𝑖𝑢𝑖=N 𝜑𝑡−1(𝑥), with 𝜆0 𝑖∈ [0,1] for all 𝑖∈~0, 𝑑 and P𝑖∈~0,𝑑𝜆0 𝑖=1 , concluding the proof. Computing simplicial-map neural networks robust to adversarial attacks In this subsection, the main result of the chapter is provided. It states that we can always compute a neural network characterizing a given labelled dataset, and being robust to adversarial attacks of a given size. Firstly, let us define the concepts of adversarial example and robustness of neural networks against adversarial attacks. Some interesting references on these concepts are [130] and [131]. 7 Robustness to adversarial examples 71 Definition 7.2.4 Let 𝑑, 𝑘 >0 be integers. Let 𝐷⊂ℝ𝑑×𝔼𝑘 be a labelled dataset and N a neural network that characterizes 𝐷 . Let 𝐵(𝑟)={𝛼∈ℝ𝑑 : ||𝛼|| ≤ 𝑟} being ||·|| a norm on ℝ𝑑 . Let us suppose that 𝑥∈ℝ𝑑 has label ℓ . Then, an adversarial example of size 𝑟 is defined as 𝑥0=𝑥+𝛼 with 𝛼∈𝐵(𝑟) such that 𝑥0 has label ℓ0 with ℓ0≠ℓ . A neural network is called robust to adversarial attacks of size 𝑟 if no labelled point 𝑥∈ℝ𝑑 has an adversarial example of size 𝑟. Proposition 7.2.4 With the assumptions of Proposition 7.2.2, we have that N 𝜑is not robust to adversarial attacks of size 𝑟for 0<𝑟<𝑑(𝑇𝜑,Γ𝜑). Proof. By Remark 7.2.2, consider 𝜎∈𝐾 such that there exist 𝑣 and 𝑤 being two vertices of 𝜎 with different labels. Let 𝑧=bar{𝑣, 𝑤} . Then 𝑧 is in the decision boundary of |𝐾| and {𝑣, 𝑧} , {𝑧, 𝑤} are edges of Sd 𝐾 . Let 𝑥=(1−𝑎)𝑧+𝑎𝑣 where 𝑎=𝑟 2𝑑(𝑧,𝑣) . Then 𝑥 has the same label as 𝑣 and 𝑑(𝑥, 𝑧)=𝑟 2 . Let 𝑥0=(1−𝑎0)𝑧+𝑎0𝑤 where 𝑎0=𝑟 2𝑑(𝑧,𝑤) . Then 𝑥0 has the same label as 𝑤 and 𝑑(𝑧, 𝑥0)=𝑟 2 . Then, 𝑑(𝑥, 𝑥0)=𝑑(𝑥, 𝑧)+ 𝑑(𝑧, 𝑥0)=𝑟 concluding that 𝑥0 is an adversarial example of size 𝑟 and 0<𝑟< 𝑑(𝑇𝜑,Γ𝜑). Example 7.2.1 Let 𝑑=𝑘=2 . Let us consider the labelled dataset 𝐷={𝐴=(4,8),(0,1,0) , 𝐵=(8,4),(1,0,0)} and the convex polytope P with vertices {𝐶=(5,10) , 𝐷=(0,0) , 𝐸=(15,0)} . Then, 𝐾=D(𝐷𝑃∪𝑉P) is composed of five maximal 2 -simplices and 𝐿 by just one maximal 2 -simplex. This way, Sd 𝐾 and Sd 𝐿 are composed of the maximal 2 -simplices showed in Figure 7.2. Let 𝑥=(6−𝑎, 6+𝑎) ∈ |𝐾| , with 𝑎∈ (0,2] , be in the geometric realization of the segment with endpoints {(4,8),(8,4)} . Then, 𝜑𝑐(𝑥)=(𝑐, 𝑑, 0) with 0≤𝑐<1 2 and 1 2<𝑑≤1 . Therefore, 𝑥 is classified as (0,1,0) with probability 𝑑 . Take 𝑧=(6,6) . Then, 𝑧 belongs to the decision boundary since 𝜑𝑐(𝑧)=(1 2,1 2,0) . Take 𝑥0=(6+𝑎, 6−𝑎) . Then, 𝜑𝑐(𝑥)=(𝑐0, 𝑑0,0) with 1 2<𝑐0≤1 and 0≤𝑑0<1 2 . Therefore, 𝑥0 is classified as (1,0,0) with probability 𝑑0. Since 𝑑(𝑥, 𝑧)=𝑎√2=𝑑(𝑥0, 𝑧) and 𝑎∈ (0,2] , then N 𝜑 is not robust to adversarial attacks of any size 𝑟with 0<𝑟≤4√2. See Figure 7.2. Let us now introduce the main result of this chapter stating that there exists a two-hidden-layer neural network characterizing a given labelled dataset and being robust to adversarial attacks of size 𝑟>0 for 𝑟 being small enough. Inordertodefine such aneuralnetwork robusttoadversarial examples, we will construct a continuous function from |𝐾| to |𝐾| with the idea of later applying the Simplicial Approximation Theorem and the composition of simplicial maps to obtain a simplicial map from |𝐾| to |𝐿| that will give rise to a neural network robust to adversarial attacks of a given size 𝑟>0 . Let us observe that, to be able to compute such a robust neural network, the size 𝑟 should be smaller than the distance between the decision boundary and the confidence set. 7 Robustness to adversarial examples 72 Figure 7.2: An adversarial example 𝑥 for the simplicial-map neural network N 𝜑: |𝐾| → |𝐿|. Theorem 7.2.5 Let 𝑛, 𝑑, 𝑘 >0 be integers. Let 𝐷={(𝑝𝑗, ℓ𝑗) : 𝑗∈~1, 𝑛 , 𝑝𝑗∈ℝ𝑑 , ℓ𝑗∈𝔼𝑘} be a labelled dataset. Then, there exists a two-hidden-layer neural network N characterizing 𝐷 and robust to adversarial attacks of size 𝑟>0, for 𝑟being small enough. Proof. Let us consider a convex polytope P such that the points of 𝐷𝑃 are inside P . Then, we can compute the Delaunay complex D(𝐷𝑃∪𝑉P) that will be denoted simply by 𝐾 (see Figure 7.1), and a simplicial complex 𝐿 composed of just one maximal 𝑘 -simplex. As claimed in Proposition 7.2.2, a simplicial map 𝜑𝑐 can be defined between |𝐾| and |𝐿| givingrise toa neuralnetwork N 𝜑 that characterizes 𝐷 (seeTheorem 6.2.1). However, N 𝜑 is not robust to adversarial attacks (see Proposition 7.2.4). Our goal is to define a new simplicial map such that its associated simplicial-map neural network is robust to adversarial attacks. To reach that aim, we need 𝑟 to be small enough, that is, 0<𝑟<𝑑(𝑇𝜑,Γ𝜑) , where 𝑑(𝑇𝜑,Γ𝜑)=min{𝑑(𝑝, 𝑞):𝑝∈𝑇𝜑 , 𝑞∈Γ𝜑} , so adversarial attacks will be placed between the confidence set 𝑇𝜑 and the decision boundary Γ𝜑 . Then, a continuous function 𝑔:|Sd 𝐾|→|Sd 𝐾| will be defined depending on such 𝑟 , to later apply the Simplicial Approximation Theorem Extension (Proposition 6.3.1), obtaining a simplicial approximation 𝜔𝑐: Sd𝑠𝐾→ Sd𝑡𝐾 of 𝑔 as close to 𝑔 as desired. Then, 𝜑𝑐 𝑡◦𝜔𝑐:|𝐾| → |𝐿| will be a simplicial map giving rise to a simplicial-map neural network N 𝜑𝑡◦𝜔 robust to adversarial attacks of size 𝑟. Let us define now the continuous function 𝑔:|Sd 𝐾| → |Sd 𝐾| . Let 𝜎={𝑢0, . . . , 𝑢𝑑} be a 𝑑 -simplex of Sd 𝐾 . Let us observe that, by Remark 7.2.2, the vertices of 𝜎satisfy the following property: •All the vertices of 𝜎are in 𝑇𝜑. Then, |𝜎| ⊆ 𝑇𝜑. •Otherwise, 𝜎=𝜎1∪𝜎2being ∅≠|𝜎1| ⊆ Γ𝜑and ∅≠|𝜎2| ⊆ 𝑇𝜑. Let us define the continuous function 𝑔:|𝜎|→|𝜎| as follows. Without loss of generality, let us assume that 𝜎1={𝑢0, . . . , 𝑢ℎ} with ℎ∈~0, 𝑑 . Let us compute the set of points of |𝜎| at distance less than 𝑟 to |𝜎1| and let us send, by 𝑔, such points to points in |𝜎1|. Let 𝑥 be a point of |𝜎| with barycentric coordinates (𝑥0, . . . , 𝑥𝑑) with respect to 𝜎 . Let 𝜆=P𝑖∈~0,ℎ𝑥𝑖 . Let 𝑧1∈ℝ𝑑 be the projection of 𝑥 in |𝜎1|. Then, the barycentric coordinates of 𝑧1with respect to 𝜎are: (𝑧0, . . . , 𝑧ℎ,0, . . . , 0), where 𝑧𝑖=𝑥𝑖 𝜆for 𝑖∈~0, ℎ. 7 Robustness to adversarial examples 73 Let 𝑧2 bethepointin |𝜎2| withbarycentriccoordinates (0, . . . , 0, 𝑧ℎ+1, . . . , 𝑧𝑑) with respect to 𝜎, aligned with 𝑥and 𝑧1. Then, 𝑥𝑖−𝑧𝑖 𝑥𝑖=𝑥𝑗 𝑥𝑗−𝑧𝑗for 𝑖∈~0, ℎand 𝑗∈~ℎ+1, 𝑑. So, 𝑧𝑗=𝑥𝑗 1−𝜆for 𝑗∈~ℎ+1, 𝑑. Now, 𝑥=(1−𝑎)𝑧1+𝑎𝑧2 for 𝑎∈ [0,1] . Then, 𝑑(𝑥, 𝜎1) ≤ 𝑑(𝑥, 𝑧1)= 𝑎·𝑑(𝑧1, 𝑧2). Let 𝜀=𝑟 𝑑(𝑧1,𝑧2). Then, 𝑑(𝑥, 𝜎1) ≤ 𝑟if 𝑎≤𝜀. Then, 𝑔(𝑥):=(𝑧1if 𝑎∈ [0,𝜀], (1−𝑎0)𝑧1+𝑎0𝑧2if 𝑎∈ [𝜀,1]with 𝑎0=𝑎−𝜀 1−𝜀. Let us observe that 𝑎0∈ [0,1] and for 𝑎=𝜀 , we have that 𝑎0=0 so (1−𝑎0)𝑧1+𝑎0𝑧2=𝑧1 . Besides, for 𝑎=1 , we have that 𝑎0=1 so (1−𝑎0)𝑧1+𝑎0𝑧2=𝑧2. Let us prove that 𝑔 is continuous at any point 𝑥∈ |𝐾| . Let us observe that, by construction, 𝑔 is continuous in the interior of |𝜎| of every 𝑑 -simplex 𝜎∈Sd 𝐾 . Let 𝑥 be a point in |𝜎∩𝜇| for some 𝑑 -simplices 𝜎,𝜇∈Sd 𝐾 . Let 𝜎=𝜎1∪𝜎2 and 𝜇=𝜇1∪𝜇2 with |𝜎1|,|𝜇1| ⊆ Γ𝜑 and |𝜎2|,|𝜇2| ⊆ 𝑇𝜑 . Let 𝛾∈Sd 𝐾 be the simplex with lower dimension such that 𝑥∈ |𝛾| . Then, by definition of simplicial complex, 𝛾⊆𝜎∩𝜇 and the barycentric coordinates of 𝑥 with respect to 𝜎 and 𝜇 coincides. By Remark 7.2.2, we have to consider two cases: (1) All the vertices of 𝛾belong to 𝑇𝜑. Then 𝛾⊆𝜎2∩𝜇2and 𝑔(𝑥)=𝑥. (2) 𝛾=𝛾1∪𝛾2 with |𝛾1| ⊆ Γ𝜑 and |𝛾2| ⊆ 𝑇𝜑 . Then 𝛾1⊆𝜎1∩𝜇1 and 𝛾2⊆𝜎2∩𝜇2 so the definition of 𝑔(𝑥) with respect to 𝜎 and 𝜇 coincides. Now,byProposition 6.3.1,given 𝑟1>0 ,thereexist 𝑠, 𝑡 >0 anda simplicial map 𝜔𝑐:|Sd𝑠𝐾| → |Sd𝑡𝐾| such that ||𝑔−𝜔𝑐|| <𝑟1 . By Lemma 7.2.3, 𝜑(0) 𝑡:(Sd𝑡𝐾)(0)→ (Sd𝑡𝐿)(0) is a vertex map. Since the composition of simplicial maps is a simplicial map, then 𝜑𝑐 𝑡◦𝜔𝑐:|Sd𝑠𝐾| → |Sd𝑡𝐿| is a simplicial map, concluding that N 𝜑𝑡◦𝜔 is a simplicial-map neural network. Let us prove now that N 𝜑𝑡◦𝜔 is robust to adversarial attacks of size 𝑟 . First of all, the following properties holds: (0) If 𝑥∈𝐶𝑗 𝜑𝑡◦𝜔then 𝜔𝑐(𝑥) ∈ 𝐶𝑗 𝜑𝑡, being 𝑗∈~0, 𝑘. (1) Let 𝑣∈ (Sd𝑡𝐾)(0) and 𝑧∈ |st 𝑣| . If 𝑣∈𝐶𝑗 𝜑𝑡 then 𝑧∈𝐶𝑗 𝜑𝑡 , being 𝑗∈~0, 𝑘. Since 𝑧∈ |st 𝑣| then 𝑧∈ |𝜎| for a 𝑑 -simplex 𝜎∈Sd𝑡𝐾 with 𝑣∈𝜎 . Then, by Remark 7.2.2, 𝜎=𝜎1∪𝜎2 , with 𝜎1∈Γ𝜑𝑡 and 𝜎2∈𝐶𝑗 𝜑𝑡 . Besides, since 𝑣∈𝜎2then 𝑧∉|𝜎1|, therefore 𝑧∈ |𝜎|\|𝜎1⊆𝐶𝑗 𝜑𝑡. (2) If 𝑥∈𝐶𝑗 𝜑𝑡◦𝜔then 𝑔(𝑥) ∈ 𝐶𝑗 𝜑𝑡, being 𝑗∈~0, 𝑘. If 𝑥∈𝐶𝑗 𝜑𝑡◦𝜔 then there exists 𝑣∈𝐶𝑗 𝜑𝑡◦𝜔 such that 𝑥∈ |st 𝑣| . Then, 𝜔(𝑣) ∈ 𝐶𝑗 𝜑𝑡 by (0). Now, since 𝑔(|st 𝑣|) ⊆ |st 𝜔(𝑣)| , then 𝑔(𝑥) ∈ 𝐶𝑗 𝜑𝑡 by (1). (3) Let 𝑥∈ |Sd𝑠𝐾|. If 𝑔(𝑥) ∈ Γ𝜑𝑡then 𝑥∈Γ𝜑𝑡◦𝜔. By contradiction, let us assume that 𝑔(𝑥) ∈ Γ𝜑𝑡 and 𝑥∈𝐶𝑗 𝜑𝑡◦𝜔 for some 𝑗∈~0, 𝑘 . Then, 𝑔(𝑥) ∈ 𝐶𝑗 𝜑𝑡 by (2), leading to a contradiction. (4) Let 𝑥∈ |Sd𝑠𝐾| . If 𝑔(𝑥) ∈ 𝐶𝑗 𝜑𝑡 with probability 𝑦𝑗 and 𝑥∈𝐶𝑗0 𝜑𝑡◦𝜔 then 𝑗=𝑗0and |𝑦𝑗−𝑦0 𝑗|<𝑟1. 7 Robustness to adversarial examples 74 Figure 7.3: Three simplicial complexes with simplicial maps 𝜔𝑐 and 𝜑𝑐 2 between them are shown illustrating a neural network N 𝜑2◦𝜔 robust to adversarial attacks of size 𝑟. This last statement is a consequence of (2) and that ||𝑔−𝜔𝑐|| <𝑟1 . Now, let 𝑥∈𝐶𝑗 𝜑𝑡◦𝜔 being 𝑗∈~0, 𝑘 . Let 𝛼∈ℝ𝑑 with ||𝛼|| <𝑟 and let 𝑥0:=𝑥+𝛼. Let us prove that 𝑥0∈Γ𝜑𝑡◦𝜔or 𝑥0∈𝐶𝑗 𝜑𝑡◦𝜔. On one hand, if 𝑔(𝑥0) ∈ Γ𝜑𝑡 then 𝑥0∈Γ𝜑𝑡◦𝜔 by (3). On the other hand, if 𝑔(𝑥0) ∈ 𝐶𝑗 𝜑𝑡then 𝑥0∈𝐶𝑗 𝜑𝑡◦𝜔or 𝑥0∈Γ𝜑𝑡◦𝜔by (2), concluding the proof. Example 7.2.2 Let us consider a labelled dataset 𝐷={(𝑝, 1)} with 𝑝∈ℝ composed of just one point. Let P be a segment with endpoints 𝑝1 and 𝑝2 in ℝ such that 𝑝1<𝑝<𝑝2 . Let 𝑟∈ℝ such that 0<𝑟< min{|𝑝1−𝑝|,|𝑝2−𝑝|} . Let 𝐾 be the Delaunay complex of {𝑝, 𝑝1, 𝑝2} that consists of just the two maximal simplices {𝑝, 𝑝1} and {𝑝, 𝑝2} . Let 𝐿 be a simplicial complex composed of a maximal 1 -simplex with endpoints 𝑣0=(0,1) and 𝑣1=(1,0) . Then, a simplicial map 𝜑𝑐 can be defined as in Proposition 7.2.1 together with a neural network N 𝜑 as in Proposition 7.2.2. However, N 𝜑 is not robust to attacks of size 𝑟 as it has been proved in Proposition 7.2.4. Then, following the proof of Theorem 7.2.5, in Figure 7.3, we have computed barycentric subdivisions on 𝐾 until we approximate 𝑔 by the simplicial map 𝜔𝑐:|Sd3𝐾|→|Sd2𝐾| . Finally, the neural network induce by the composition 𝜑𝑐 2◦𝜔𝑐is robust to adversarial attacks of size 𝑟. Conclusions and future work During these three years, I have been studying computational topology and ways to apply it to understand and improve neural networks interpretability, approximation capabilities and robustness. The result is this thesis where the topology of data and its effect to the learning process have been studied, as well as the reinterpretation of neural networks as architectures that can be explicitly defined by simplicial maps. We have faced profound problems such as the approximation capabilities and the robustness of a new concrete family of neural networks called simplicial-map neural networks to adversarial example. Starting a new and promising research line with huge possibilities of extensions and applications. In Chapter 4, we proposed the use of topological data analysis techniques in order to compare different stylistic trends of three poets of the Spanish Golden Age. In this approach, the bottleneck distance between the persistence diagrams of the Vietoris-Rips filtration obtained form the cloud points representing the sonnets of three different writers encode the differences among their literary styles and quantifies the nearness among them. This novel approach opens a door for the interaction of topological data analysis and philological research. Topological data analysis techniques can be applied in order to give a topological description of a work, a writer or an age and go deeper into their belonging to a greater trend. In the context of the thesis, this chapter was a first attempt to study if the topological distribution of a dataset provides information. Besides, due to the satisfactory results, we started to consider persistent homology as a good descriptor of real datasets and to think about formal interpretations and effects of the datasets on neural networks, leading us to the theory developed in the next chapters. In Chapter 5, we proposed the use of representative datasets as a new approach to reduce learning time in neural networks, based on the topological structure of the dataset. We defined representative datasets using a notion of nearness that has the Gromov-Hausdorff distance as its lower bound. Nevertheless, the bottleneck distance of persistence diagrams (which is a lower bound of the Gromov-Hausdorff distance) is used to measure representativeness since it is computationally less expensive. Furthermore, the agreement between the provided theoretical results and the experiments supports that representative datasets can be a good approach to reach an efficient “summarization" of a dataset to train any neural network. First, in the case of gradient descent, the training process is faster and, second, in the case of stochastic gradient descent the convergence is usually faster when using a representative dataset. We also would like to highlight that these ideas are in line with some business needs such as providing guarantees and characterization of the input dataset for a machine learning algorithm. Besides, in words of the European Union Aviation Safety Agency (EASA), there is a need to increase the capability of making more understandable the conditions [92] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. ‘Going Deeper with Convolutions’. In: Computer Vision and Pattern Recognition (CVPR). 2015 (cited on page 33). [93] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. 2015 (cited on page 33). [94] Conrado S. Miranda and Fernando J. Von Zuben. Reducing the Training Time of Neural Networks by Partitioning. 2015 (cited on page 33). [95] Zhao You and Bo Xu. ‘Improving training time of deep neural networkwith asynchronous averaged stochastic gradient descent’. In: ISCSLP. IEEE, 2014, pp. 446–449 (cited on page 33). [96] Tong Xiao, Jingbo Zhu, Tongran Liu, and Chunliang Zhang. ‘Fast Parallel Training of Neural Language Models’. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017. 2017, pp. 4193–4199. doi: 10.24963/ijcai.2017/586 (cited on page 33). [97] Felix Schmiedl. ‘Computational Aspects of the Gromov-Hausdorff Distance and its Application in Non-rigid Shape Matching.’ In: Discret. Comput. Geom. 57.4 (2017), pp. 854–880 (cited on page 34). [98] Frédéric Chazal, Vin de Silva, and Steve Oudot. ‘Persistence stability for geometric complexes’. In: CoRR abs/1207.3885 (2012) (cited on page 34). [99] Frédéric Chazal, Vin de Silva, and Steve Oudot. ‘Persistence stability for geometric complexes’. In: Geometriae Dedicata 173.1 (Dec. 2014), pp. 193–214. doi: 10.1007/s10711- 013- 9937- z (cited on page 34). [100] David W. Matula. ‘Determining Edge Connectivity in O(nm)’. In: FOCS. IEEE Computer Society, 1987, pp. 249–251 (cited on page 36). [101] Laurens van der Maaten and Geoffrey Hinton. ‘Visualizing Data using t-SNE’. In: Journal of Machine Learning Research 9 (2008), pp. 2579–2605 (cited on page 47). [102] Shiyu Liang and R. Srikant. ‘Why Deep Neural Networks?’ In: CoRR abs/1610.04161 (2016) (cited on page 51). [103] Itay Safran and Ohad Shamir. ‘Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks’. In: Proceedings of the 34th International Conference on Machine Learning. Ed. by Doina Precup and Yee Whye Teh. Vol. 70. Proceedings of Machine Learning Research. International Convention Centre, Sydney, Australia: PMLR, June 2017, pp. 2979–2987 (cited on page 51). [104] Matus Telgarsky. ‘Benefits of depth in neural networks’. In: CoRR abs/1602.04485 (2016) (cited on page 51). [105] Shizhao Sun, Wei Chen, Liwei Wang, Xiaoguang Liu, and Tie-Yan Liu. ‘On the Depth of Deep Neural Networks: A Theoretical View’. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA. Ed. by Dale Schuurmans and Michael P. Wellman. AAAI Press, 2016, pp. 2066–2072 (cited on pages 51,65). [106] Boris Hanin and Mark Sellke. Approximating Continuous Functions by ReLU Nets of Minimal Width. 2017 (cited on page 51). [107] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. ‘The Expressive Power of Neural Networks: A View from the Width’. In: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. Ed. by Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett. 2017, pp. 6232–6240 (cited on page 51). [108] Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. ‘Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions’. In: CoRR abs/1803.00094 (2018) (cited on page 51). [109] Namig J. Guliyev and Vugar E. Ismailov. ‘On the approximation by single hidden layer feedforward neural networks with fixed weights’. In: Neural Networks 98 (2018), pp. 296–304. doi: https://doi. org/10.1016/j.neunet.2017.12.007 (cited on page 51). [110] Olivier Delalleau and Yoshua Bengio. ‘Shallow vs. Deep Sum-Product Networks’. In: Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain. Ed. by John Shawe-Taylor, Richard S. Zemel, Peter L. Bartlett, Fernando C. N. Pereira, and Kilian Q. Weinberger. 2011, pp. 666–674 (cited on page 51). [111] James Martens and Venkatesh Medabalimi. ‘On the Expressive Efficiency of Sum Product Networks.’ In: CoRR abs/1411.7717 (2014) (cited on page 51). [112] Hoifung Poon and Pedro Domingos. Sum-Product Networks: A New Deep Architecture. 2012 (cited on page 51). [113] Nadav Cohen, Or Sharir, and Amnon Shashua. ‘On the Expressive Power of Deep Learning: A Tensor Analysis’. In: Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016. Ed. by Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir. Vol. 49. JMLR Workshop and Conference Proceedings. JMLR.org, 2016, pp. 698–728 (cited on page 51). [114] Nadav Cohen and Amnon Shashua. ‘Convolutional Rectifier Networks as Generalized Tensor Decompositions’. In: Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. Ed. by Maria-Florina Balcan and Kilian Q. Weinberger. Vol. 48. JMLR Workshop and Conference Proceedings. JMLR.org, 2016, pp. 955–963 (cited on page 51). [115] Joe Kileel, Matthew Trager, and Joan Bruna. ‘On the Expressive Power of Deep Polynomial Neural Networks’. In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada. Ed. by Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett. 2019, pp. 10310–10319 (cited on page 52). [116] Ross Geoghegan. Topological Methods in Group Theory. Graduate Texts in Mathematics. Springer New York, 2010 (cited on page 59). [117] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. 2013 (cited on page 65). [118] Fezza Sid Ahmed, Yassine Bakhti, Wassim Hamidouche, and Olivier Déforges. ‘Perceptual Evaluation of Adversarial Attacks for CNN-based Image Classification’. In: 2019 Eleventh International Conference on Quality of Multimedia Experience (QoMEX). 2019, pp. 1–6. doi: 10.1109/QoMEX.2019.8743213 (cited on page 65). [119] Siddhant Garg and Goutham Ramakrishnan. BAE: BERT-based Adversarial Examples for Text Classification. 2020 (cited on page 65). [120] Fazle Karim, Somshubra Majumdar, and Houshang Darabi. ‘Adversarial Attacks on Time Series’. In: IEEE Transactions on Pattern Analysis & Machine Intelligence 01 (Apr. 2020), pp. 1–1. doi: 10.1109/TPAMI. 2020.2986319 (cited on page 65). [121] Konstantina Christakopoulou and Arindam Banerjee. ‘Adversarial Attacks on an Oblivious Recommender’. In: Proceedings of the 13th ACM Conference on Recommender Systems. Association for Computing Machinery, 2019, pp. 322–330. doi:10.1145/3298689.3347031 (cited on page 65). [122] Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K. Jain. ‘Adversarial Attacks and Defenses in Images, Graphs and Text: A Review’. In: International Journal of Automation and Computing 17 (2020), pp. 151–178. doi:10.1007/s11633-019-1211-x (cited on page 65). [123] Ziang Yan, Yiwen Guo, and Changshui Zhang. ‘Adversarial Margin Maximization Networks’. In: IEEE Transactions on Pattern Analysis and Machine Intelligence (2019), pp. 1–1. doi: 10.1109/TPAMI.2019. 2948348 (cited on page 65). [124] Corinna Cortes and Vladimir Vapnik. ‘Support Vector Networks’. In: Machine Learning 20 (1995), pp. 273–297 (cited on page 65). [125] Yichuan Tang. Deep Learning using Linear Support Vector Machines. 2013 (cited on page 65). [126] Xiaobo Wang, Shifeng Zhang, Zhen Lei, Si Liu, Xiaojie Guo, and Stan Z. Li. ‘Ensemble Soft-Margin Softmax Loss for Image Classification’. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI’18. Stockholm, Sweden: AAAI Press, 2018, pp. 992–998 (cited on page 66). [127] Vugar E. Ismailov. ‘On the approximation by neural networks with bounded number of neurons in hidden layers’. In: Journal of Mathematical Analysis and Applications 417.2 (2014), pp. 963–969. doi: https://doi.org/10.1016/j.jmaa.2014.03.092 (cited on page 66). [128] Namig J. Guliyev and Vugar E. Ismailov. ‘Approximation capability of two hidden layer feedforward neural networks with fixed weights’. In: Neurocomputing 316 (2018), pp. 262–269. doi: https://doi. org/10.1016/j.neucom.2018.07.075 (cited on page 66). [129] Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial Neural Networks. 2020 (cited on page 66). [130] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. ‘Certified Robustness to Adversarial Examples with Differential Privacy’. In: 2019 IEEE Symposium on Security and Privacy (SP). 2019, pp. 656–672. doi:10.1109/SP.2019.00044 (cited on page 70). [131] Xiaoyong Yuan, Pan He, Qile Zhu, and Xiaolin Li. ‘Adversarial Examples: Attacks and Defenses for Deep Learning’. In: IEEE Transactions on Neural Networks and Learning Systems 30.9 (2019), pp. 2805–2824. doi:10.1109/TNNLS.2018.2886017 (cited on page 70). Alphabetical Index 𝜆-balanced 𝜀-representative, 35 𝜀-proximity graph, 36 𝜀-representative, 35 Accuracy, 21 Barycentric subdivision, 14 Bottleneck distance, 19 Boundary, 17 Chain complexes, 17 Convex hull, 13 Convex polytope, 13 Corpus, 26 Cycle, 17 Dataset, 21 Deep learning, 6 Diameter, 15 Dominating set, 36 Filtration, 18 Gromov-Hausdorff distance, 34 Hausdorff distance, 34 Homology group, 17 Mesh, 15 Mesh induced by a triangulation, 57 Modulus of continuity, 60 Neural network, 20 One-hot vector, 21 Overfitting, 21 Persistence diagrams, 19 Persistent homology, 18 Representaive dataset, 35 Simplicial approximation, 16 Simplicial Approximation Theorem, 16 Simplicial complex, 14 Simplicial map, 15 Simplicial-map neural network, 54 Star, 16 Star condition, 16 Supervised classification problem, 21 Topological data analysis, 17 Triangulation, 14 Triangulation of a topological space, 15 Universal Approximation Theorem, 22 Vertex map, 15 Vietoris-Rips filtration, 18