Topology-based representative datasets to reduce neural network training resources

ORIGINAL ARTICLE Topology-based representative datasets to reduce neural network training resources Rocio Gonzalez-Diaz 1 •Miguel A. Gutie ´rrez-Naranjo 2 •Eduardo Paluzo-Hidalgo 1 Received: 5 October 2021 / Accepted: 29 March 2022 The Author(s) 2022 Abstract One of the main drawbacks of the practical use of neural networks is the long time required in the training process. Such a training process consists of an iterative change of parameters trying to minimize a loss function. These changes are driven by a dataset, which can be seen as a set of labeled points in an n-dimensional space. In this paper, we explore the concept of arepresentative dataset which is a dataset smaller than the original one, satisfying a nearness condition independent of isometric transformations. Representativeness is measured using persistence diagrams (a computational topology tool) due to its computational efficiency. We theoretically prove that the accuracy of a perceptron evaluated on the original dataset coincides with the accuracy of the neural network evaluated on the representative dataset when the neural network architecture is a perceptron, the loss function is the mean squared error, and certain conditions on the representativeness of the dataset are imposed. These theoretical results accompanied by experimentation open a door to reducing the size of the dataset to gain time in the training process of any neural network. Keywords Data reduction Neural networks Representative datasets Computational topology 1 Introduction The success of the different architectures used in the framework of neural networks is doubtless [1]. The achievements made in areas such as video imaging [2], recognition [3], or language models [4] show the surprising potential of such architectures. In spite of such success, they still have some shortcomings. One of their main drawbacks is the long time needed in the training process. Such a long training time is usually associated with two factors: first, the large amount of weights to be adjusted in the current architectures and second, the huge datasets used to train neural networks. In general, the time needed to train a complex neural network from the scratch is so long that many researchers use pretrained neural networks as, for example, Oxford VGG models [5], Google Inception Model [6], or Microsoft ResNet Model [7]. Other attempts to reduce the training time are, for example, to partition the training task in multiple training subtasks with submodels, which can be performed independently and in parallel [8], to use asynchronous averaged stochastic gradient descent [9], and to reduce data transmission through a samplingbased approach [10]. Besides, in [11], the authors studied how the elimination of ‘‘unfavorable’’ samples improve generalization accuracy for convolutional neural networks. Finally, in [12], an unweighted influence data subsampling method is proposed. Roughly speaking, a training process consists of searching for a local minimum of a loss function in an abstract space where the states are sets of weights. Each of the training sample batches provides an extremely small change in weights according to the training rules. The aim of such changes is to find the ‘‘best’’ set of weights that minimizes the loss function. If we consider a R. Gonzalez-Diaz, M. A. Gutie ´rrez-Naranjo and E. Paluzo- Hidalgo have contributed equally to this work. &Eduardo Paluzo-Hidalgo [email protected] Rocio Gonzalez-Diaz [email protected] Miguel A. Gutie ´rrez-Naranjo [email protected] 1 Dept. of Applied Mathematics I, Universidad de Sevilla, 41012 Sevilla, Spain 2 Dept. of Computer Science and Artificial Intelligence, Universidad de Sevilla, 41012 Sevilla, Spain 123 Neural Computing and Applications https://doi.org/10.1007/s00521-022-07252-y(0123456789().,-volV)(0123456789().,-volV) ‘‘geometrical’’ interpretation of the learning process, such changes can be seen as tiny steps in a multi-dimensional metric space of parameters that follow the direction settled by the gradient of the loss function. In some sense, one may think that two ‘‘close’’ points of the dataset with the same label provide ‘‘similar’’ information to the learning process since the gradient of the loss function on such points is similar. Such a viewpoint leads us to look for a representative dataset, ‘‘close’’ 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. Proving such a general result for any neural network architecture is out of the scope of this paper and, probably, it is not possible since the definition of neural network is continuously evolving over time. Due to such difficulties, we will begin in this paper by proving the usefulness of representative datasets in the perceptron case; that is, we formally prove, for the perceptron case, that the accuracy of a neural network evaluated on the representative dataset is similar to the accuracy of the neural network evaluated on the original dataset under some constraints on the representativeness of the dataset. Besides, experimental evidence indicates that neural networks trained on representative datasets perform similar to neural networks trained on the original datasets in the case of multi-layer neural networks. Moreover, in order to ‘‘keep the shape’’ of the original dataset, the concept of representative datasets is associated with a notion of nearness independent of isometric transformations. As a first approach, the Gromov–Hausdorff distance is used to measure the representativeness of the dataset. Nonetheless, as the Gromov–Hausdorff distance complexity is an open problem 1 , the bottleneck distance between persistence diagrams [14] is used instead as a lower bound to the Gromov–Hausdorff distance since its time complexity is cubic on the size of the dataset (see [15]). The paper is organized as follows. In Sect. 2, basic definitions and results from neural networks and computational topology are given. The notion of representative datasets is introduced in Sect. 3. Persistence diagrams are used in Sect. 4to measure the representativeness of a dataset. In Sect. 5, the perceptron architecture is studied to theoretically prove that the accuracy of a perceptron evaluated on original and representative datasets coincide under some constraint. In Sect. 6.1, experimental results are provided for the perceptron case showing the good performance of representative datasets, compared to random datasets. In Sect. 6.2, we illustrate experimentally the same fact for multi-layer neural networks. Finally, some conclusions and future work are provided in Sect. 7. 2 Background Next, we recall some basic definitions and notations used throughout the paper. 2.1 Neural networks The research field of neural networks is extremely vivid and new architectures are continuously being presented (see, e.g., CapsNets [7], Bidirectional Feature Pyramid Networks [16] or new variants of the Gated Recurrent Units [17,18]), so the current notion of neural network is far from the classic multi-layer perceptron or radial basis function networks [19]. As a general setting, a neural network is a mapping Nw;U:Rn!s0;kt(where s0;kt¼f0;1;...;kg) that depends on a set of weights wand a set of parameters U which involve the description of the synapses between neurons, layers, activation functions and whatever consideration in its architecture. To train the neural network Nw;U, we use a dataset which is a finite set of pairs D¼ ðx;cxÞwhere point xlies in XRnand label cxlies in s0;kt, for a fixed integer k2N. Observe that it should be satisfied that a point cannot have different labels. The sets Xand s0;ktare called, respectively, the set of points and the set of labels in D. To perform the learning process, we use: (1) a loss function which measures the difference between the output of the network (obtained with the current weights) and the desired output; and (2) a loss-driven training method to iteratively update the weights. Finally, let us introduce the concept of accuracy as a measure to evaluate the performance of a neural network. Definition 1 The accuracy of a neural network Nw;U evaluated on a dataset D¼ðx;cxÞ:x2XRnand cx2s0;kt, is defined as: AðD;NwÞ¼ 1 jXjX x2X IwðxÞ; where, for any x2X, IwðxÞ¼ 1if cx¼Nw;UðxÞ; 0otherwise:  1 It seems to be intractable in practice [13]. Neural Computing and Applications 123 2.2 Persistent homology In this paper, the representativeness of a dataset will be measured using methods from the recent developed area called computational topology whose main tool is persistent homology. A detailed presentation of this field can be found in [14]. Homology provides mathematical formalism to count holes where holes refer to connected components, tunnels, cavities, and so on, being the q-dimensional homology group the mathematical representation for the q-dimen- sional holes in a given space. Persistent homology is usually computed when the homology cannot be determined. An example of the latter appears when a surface is sampled by a point cloud. Persistent homology is based on the concept of filtration, which is an increasing sequence of simplicial complexes. The building blocks of a simplicial complex are q-sim- plices, being a 0-simplex a point, a 1-simplex a line segment, a 2-simplex a triangle, a 3-simplex a tetrahedron, and so on. An example of filtration is the Vietoris–Rips filtration (see [20]) that is built by successively increasing the radius of the balls centered at the points of a given set in an n-dimensional space and joining those vertices (points) whose balls intersect forming new simplices. We say that a q-dimensional hole is born when it appears at a specific time along the filtration and it dies when it merges with another q-dimensional hole at a specific time along the filtration. One of the common graphical representations of births and deaths of the q-di- mensional holes over time is the so-called (q-dimensional) persistence diagram which consists of a set of points on the Cartesian plane. This way, a point of a persistence diagram represents the birth and the death of a hole. Since deaths happen 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 that survive for a long time. The so-called bottleneck distance can be used to compare two persistence diagrams. Definition 2 The (q-dimensional) bottleneck distance between two (q-dimensional) persistence diagrams Dgm and g Dgm is: dBðDgm;g DgmÞ¼inf /sup a ka/ðaÞk1 where a2Dgm and /is any possible bijection between Dgm [Dand g Dgm [D, being Dthe set of points in the diagonal axis. An useful result used in this paper is the following one that connects the Gromov–Hausdorff distance between two metric spaces and the bottleneck distance between the persistence diagrams obtained from their corresponding Vietoris–Rips filtrations. For the sake of brevity, the (qdimensional) persistence diagram obtained from the Vietoris–Rips filtration computed from a subset Xof Rn, with qn, will be simply called the (q-dimensional) persistence diagram of Xand denoted by DgmqðXÞ. Theorem 1 [21,Theorem 5.2] For any two subsets X and YofRn,and for any dimension q n,the bottleneck distance between the persistence diagrams of X and Y is bounded by the Gromov–Hausdorff distance of X and Y: dBðDgmqðXÞ;DgmqðYÞÞ  2dGH ðX;YÞ: Let us recall that dGH ðX;YÞ¼1 2inff;gdHðfðXÞ; gðYÞÞ ;where dHðX;YÞ¼max supx2Xinfy2Ykxyk; supy2Yinfx2Xkxyk;and f:X!Z(resp. g:Y!Z) denotes an isometric transformation of X(resp. Y) into some metric space Z. Summing up, we can conclude that 1 2dBðDgmqðXÞ;DgmqðYÞÞ  dGHðX;YÞdHðX;YÞ: 3 Representative datasets In this section, we provide the definition of representative datasets which is independent of the neural network architecture considered. The intuition behind this definition is to keep the ‘‘shape’’ of the original dataset while reducing its number of points. Firstly, let us introduce the notion of e-representative point. Definition 3 A labeled point ð~ x;c~ xÞ2Rns0;ktis erepresentative of ðx;cxÞ2Rns0;ktif cx¼c~ xand kx~ xke, where e2Ris the representation error. We denote ~ xex. Neural Computing and Applications 123 The next step is to define the concept of e-representative dataset. Notice that if a dataset can be correctly classified by a neural network, any isometric transformation of such dataset can also be correctly classified by the neural network (after adjusting the weights). Therefore, the definition of e-representative dataset should be independent of such transformations. The concept of k-balanced e-representa- tive datasets is also introduced and it will be used in Sect. 5 to ensure that similar accuracy results are obtained when a trained perceptron is evaluated on a representative dataset rather than on the original dataset. Definition 4 A dataset ~ D¼ð~ x;c~ xÞ:~ x2~ XRnand c~ x2s0;ktis e-representative of D¼ðx;cxÞ:x2X Rnand cx2s0;ktif there exists an isometric transformation f:~ X!Rn, such that for any ðx;cxÞ2Dthere exists ð~ x;c~ xÞ2 ~ Dsatisfying that fð~ xÞ ex. The minimum of all those possible efor which an isometric transformation exists is called to be optimal. Finally, the dataset ~ Dis said to be k-balanced if for each ð~ x;c~ xÞ2 ~ D, the set fðx;cxÞ:fð~ xÞ exgcontains kpoints and for each ðx;cxÞ2 Dthere exists only one ð~ x;c~ xÞ2 ~ Dsuch that fð~ xÞ ex. Remark 1 Let us point out that k-balanced datasets cannot be computed for most datasets when they are required to be subsets of the datasets. Even if it is too restrictive, in Sect. 5, we will provide several theoretical results using that assumption. Nevertheless, we will prove experimentally in Sect. 6that, without that assumption, e-represen- tative datasets still perform well. Proposition 1 Let ~ Dbe an e-representative dataset (with set of points ~ XRn) of a dataset D(with set of points XRn). Then, dGHðX;~ XÞe: Proof By definition of e-representative datasets, there exists an isometric transformation from ~ Xto Rnwhere for all x2Xthere exists ~ x2~ Xsuch that kxfð~ xÞk  e. Therefore, dHðX;fð~ XÞÞ  e. Then, by the definition of the Gromov–Hausdorff distance, dGH ðX;~ XÞdHðX;fð~ XÞÞ  e. h Notice that the definition of e-representative datasets is not useful when eis ‘‘big.’’ The following result, which is a consequence of Proposition 1, provides the optimal value for e. Corollary 1 The parameter eis optimal if and only if e¼dGHðX;~ XÞ. Therefore, one way to discern if a dataset ~ Dis ‘‘representative enough’’ of Dis to compute the Gromov–Hausdorff distance between Xand ~ X. If the Gromov–Hausdorff distance is ‘‘big,’’ we could say that the dataset ~ Dis not representative of D. However, the Gromov–Hausdorff distance is not useful in practice because of its high computational cost. An alternative approach to this problem is given in Sect. 4. 3.1 Proximity graph algorithm In this section, for a given e[0, we propose a variant of the proximity graph algorithm [22] to compute an e-rep- resentative dataset ~ Dof a dataset D¼ðx;cxÞ:x2X Rnand cx2s0;kt. Firstly, a proximity graph is built over X, establishing adjacency relations between the points of X, represented by edges. Definition 5 Given e[0, an e-proximity graph of Xis a graph GeðXÞ¼ðX;EÞsuch that if x;y2Xand kxyke then ðx;yÞ2E. See Fig. 1in which the proximity graph of one of the two interlaced solid torus is drawn for a fixed e. Secondly, from an e-proximity graph of X, a dominating dataset (also known as a vertex cover) ~ XXis computed satisfying that if x2Xthen x2~ Xor there exists y2~ X adjacent to x. We then obtain an e-representative dataset ~ D¼fð ~ x;c~ xÞ:~ x2~ Xand ð~ x;c~ xÞ2Dgalso called dominating dataset of D. Algorithm 1 shows the pseudo-code used in this paper to compute a dominating dataset of D. Fig. 1 A point cloud sampling two interlaced solid torus and the eproximity graph of one of them for a fixed e. Neural Computing and Applications 123 Here, DominatingSetðGeðXcÞÞ refers to a dominating set obtained from the proximity graph GeðXcÞ. Among the existing algorithms in the literature to obtain a dominating set, we will use, in our experiments in Sect. 6, the algorithm proposed in [23] that runs in OðjXjjEjÞ. Therefore, the complexity of Algorithm 1 is OðjXj2þjXjjEjÞ because of the size of the matrix of distances between points and the complexity of the algorithm to obtain the dominating set. Let us observe that the algorithm proposed in this paper is just an example to show how we can compute representative datasets. Other more efficient algorithms to compute representative datasets are left for future work in Sect. 7. Lemma 1 The dominating dataset ~ Dobtained by running Algorithm 1is an e-representative dataset of D. Proof Let us prove that for any ðx;cxÞ2Dthere exists ð~ x;cxÞ2 ~ Dsuch that xe~ x. Two possibilities arise: 1. If ðx;cxÞ2 ~ D, it is done. 2. If ðx;cxÞ 62 ~ D, since ~ Xcxis a dominating dataset of GeðXcxÞ, then there exists ~ x2~ Xcxsuch that ~ xis adjacent to xin GeðXcxÞ. Therefore, ð~ x;cxÞ2 ~ Dand xe~ x. h 4 Persistent homology to Infer the representativeness of a dataset In this section, we show the role of persistent homology as a tool to infer the representativeness of a dataset. Firstly, from Theorem 1in page 5, we will establish that the bottleneck distance between persistence diagrams is a lower bound of the representativeness of the dataset. Lemma 2 Let ~ Dbe an e-representative dataset (with set of points ~ XRn)of a dataset D(with set of points X Rn). Let DgmqðXÞand Dgmqð~ XÞbe the q-dimensional persistence diagrams of X and ~ X,respectively. Then,for qn, 1 2dBDgmqðXÞ;Dgmqð~ XÞe: Proof Since ~ Dis an e-representative dataset of Dthen dGHðX,~ XÞeby Proposition 1. Now, by Theorem 1, 1 2dBðDgmqðXÞ;DgmqðYÞÞ  dGH ðX;YÞe.h As a direct consequence of Lemma 2and the fact that the Hausdorff distance is an upper bound of the Gromov– Hausdorff distance, we have the following result. Corollary 2 Let ~ Dbe an e-representative dataset (with set of points ~ XRn)of a dataset D(with set of points XRn)where the parameter eis optimal. Let DgmqðXÞ and Dgmqð~ XÞbe the q-dimensional persistence diagrams of X and ~ X,respectively. Then, 1 2dBDgmqðXÞ;Dgmqð~ XÞÞedHX;~ X: In order to illustrate the usefulness of this last result, we will discuss a simple example. In Fig. 2a, we can see a subsample of a circumference (the original dataset) together with two classes corresponding, respectively, to the upper and lower part of the circumference. In Fig. 2c, we can see a subset of the original dataset and a decision boundary ‘‘very’’ different to the one given in Fig. 2a. Then, we could say that the dataset shown in Fig. 2c does not ‘‘represent’’ the same classification problem than the original dataset. However, the dataset shown in Fig. 2b could be considered a representative dataset of the original one since both decision boundaries are ‘‘similar.’’ This can be determined by computing the Hausdorff distance between the original and the other datasets, and the bottleneck distance between the persistence diagrams of the corresponding datasets (see the values shown in Table 1). Using Corollary 2, we can infer that 0:08 e10:18 for Neural Computing and Applications 123 the dataset given in Fig. 2b and 0:13 e20:3 for the dataset given in Fig. 2c. Therefore, the dataset given in Fig. 2b can be considered ‘‘more’’ representative of the dataset shown in Fig. 2a than the dataset given in Fig. 2c, as expected. In Table 2, we show the output of Algorithm 1 applied to the dataset pictured in Fig. 2a and different values of e, in order to obtain different dominating datasets. Let us observe that, depending on the value of the parameter e, the size of the resulting dominating dataset is different. Finally, let us remark that the values of the parameter used in Algorithm 1 does not correspond, in general, to the optimal e(see Definition 4). 5 Theoretical results on the perceptron case One of the simplest neural network architecture is the perceptron. Our goal in this section is to formally prove that the accuracy of a perceptron evaluated on the original dataset and on its representative dataset are equivalent when we impose certain conditions on the representativeness. For the sake of simplicity, in this section, we will restrict our interest to a binary classification problem, although our approach is valid for any classification problem. Therefore, our input is a binary dataset D¼ðx;cxÞ:x2XRnand cx2f0;1g. Besides, we will assume in this section that the training process tries to minimize the following error function: Eðw;DÞ¼ 2 jXjX x2X ExðwÞ; where, for ðx;cxÞ2Dand w2Rnþ1, ExðwÞ¼1 2ðcxywðxÞÞ2 is the loss function considered, called the mean squared error (MSE). An example of such a training process is the gradient descent training algorithm. First, let us introduce the definition of a perceptron. (a) A binary classification problem given by a sampled circumference. In this case, the classification problem tries to distinguish between the upper and the lower part of the circumference. (b) (ε1-Representative dataset) A subset of the sampled circumference given in Fig. 2a. Let us observe that the decision boundary obtained is similar to the one showed in Fig. 2a. (c) (ε2-Representative dataset) A subset of the sampled circumference given in Fig. 2a. Let us observe that the decision boundary obtained is quite different to the one showed in Fig. 2a. Fig. 2 Illustration of a binary classification problem and the representative dataset concept Table 1 The 0-dimensional bottleneck distance (dB0), the 1-dimensional bottleneck distance (dB1), and the Hausdorff distance (dH) between the persistence diagrams of the dataset given in Fig. 2a and the datasets given in Fig. 2b and c, respectively Datasets 1 2dB01 2dB1dH Original (Fig. 2a) and e1-representative (Fig. 2b) 0.07 0.08 0.18 Original (Fig. 2a) and e2-representative (Fig. 2c) 0.13 0.08 0.3 Table 2 The 0-dimensional bottleneck distance (dB0) and the Hausdorff distance (dH) between the persistence diagrams of the dataset (D) given in Fig. 2a, composed of 22 points, and the dominating datasets ( ~ D) obtained applying Algorithm 1 for different values of e, and a random dataset (R) of the same size than the corresponding dominating dataset e(Alg. 1) j~ Dj1 2dB0ðD;~ DÞ1 2dB0ðD;RÞdHðD;~ DÞdHðD;RÞ 0.6 8 0.22 0.29 0.39 0.83 0.3 14 0.13 0.16 0.23 0.7 0.2 18 0.05 0.15 0.19 0.71 Neural Computing and Applications 123 Definition 6 Aperceptron Nw:Rn!f0;1g, with weights w¼ðw0;w1;...;wnÞ2Rnþ1, is defined as: NwðxÞ¼ 1if ywðxÞ 1 2; 0otherwise; 8 < : being yw:Rn!ð0;1Þdefined as ywðxÞ¼rðwxÞ where, for x¼ðx1;...;xnÞ2Rn, wx ¼w0þw1x1þ...þwnxn; and r:R!ð0;1Þ, defined as rðzÞ¼ 1 1þez; is the sigmoid function. Remark 2 In the previous definition, let us point out that the condition ywðxÞ 1 2is the same as the condition wx 0 that usually appears in the definition of perceptron. A useful property of the sigmoid function is the easy expression of its derivative. Let rmdenote the composition rm¼r mtimesr. Lemma 3 If m 2Nand z 2Rthen 0\ðrmÞ0ðzÞ¼mrmðzÞð1rðzÞÞ  m mþ1  mþ1 : Proof Firstly, let us observe that ðrmÞ0ðzÞ¼mrmðzÞð1 rðzÞÞ [0 since 0\rðzÞ\1 for all z2R. Secondly, let us find the local extrema of ðrmÞ0by computing the roots of its derivative: ðrmÞ00ðzÞ¼mrmðzÞð1rðzÞÞðmðmþ1ÞrðzÞÞ: Now, ðrmÞ00ðzÞ¼0 if and only if mðmþ1ÞrðzÞ¼0. The last expression vanishes at z¼logðmÞ. Besides, ðrmÞ00ðzÞ[0 if and only if mðmþ1ÞrðzÞ[0 which is true for all z2 ð1;logðmÞÞ. Analogously, ðrmÞ00ðzÞ\0 for all z2ðlogðmÞ;þ1Þ, concluding that z¼logðmÞis a global maximum. Finally, ðrmÞ0ðlogðmÞÞ ¼ m mþ1  mþ1 concluding the proof. h From now on, we will consider that the associated isometric transformation fby which the dataset is e-repre- sentative is applied to the representative dataset. Therefore, by abuse of notation, ~ xwill mean fð~ xÞ. Analogously, ~ Xwill mean fð~ XÞand ~ Dwill mean fð~ DÞ. In the following lemma, we prove that the difference between the outputs of the function ym wevaluated at a point xand at its e-representative point ~ xdepends on the weights wand the parameter e. Lemma 4 Let w 2Rnþ1and x,~ x2Rnwith ~ xex. Then, kym wð~ xÞym wðxÞk  qmkwke; where qm¼qðwx;w~ x;mÞ¼ ðrmÞ0ðzÞ;if logðmÞ\z; ðrmÞ0ð~zÞ;if ~z\logðmÞ; ðrmÞ0ðlogðmÞÞ;otherwise. 8 > < > : with z ¼minfwx;w~ xgand ~z¼maxfwx;w~ xg. Proof Let us assume, without loss of generality, that wx w~ x. Then, using the mean value theorem, there exists b2ðwx;w~ xÞsuch that ym wð~ xÞym wðxÞ¼ðrmÞ0ðbÞðw~ xwxÞ: By Lemma 3, the maximum of ðrmÞ0in the interval ½z;~zis reached at logðmÞif z\logðmÞ\~z,atzif logðmÞz, and at ~zif ~zlogðmÞ, with z¼minfwx;w~ xgand ~z¼maxfwx;w~ xg. Consequently, kym wðxÞym wðxÞk  qmkwð~ xxÞk:ð1Þ Applying now the Ho ¨lder inequality we obtain: kwð~ xxÞk  kwkk~ xxkkwke: Replacing kwð~ xxÞk by kwkein Eq. (1), we obtain the desired result. h The following result is a direct consequence of Lemma 3and Lemma 4. Corollary 3 Let w 2Rnþ1and x,~ x2Rnwith ~ xex. Then, kym wð~ xÞym wðxÞk  m mþ1  mþ1 kwke: The next result establishes under which conditions erepresentative points are classified under the same label as the points they represent. Lemma 5 Let ~ Dbe an e-representative dataset of the binary dataset D. Let Nwbe a perceptron with weights w2Rnþ1.Letðx;cÞ2Dand ð~ x;cÞ2 ~ Dwith ~ xex. If ekwxk kwkthen NwðxÞ¼Nwð~ xÞ: Proof First, if wx ¼0, then e¼0, therefore x¼~ xand then NwðxÞ¼Nwð~ xÞ. Now, let us suppose that wx\0. Then, ywðxÞ\1 2and NwðxÞ¼0 by the definition of Neural Computing and Applications 123 perceptron. Since e\kwxk kwkthen xand ~ xbelong to the same semispace in which the space is divided by the hyperplane wx ¼0. Therefore, w~ x\0, then ywð~ xÞ\1 2and finally Nwð~ xÞ¼0. Similarly, if wx [0, then NwðxÞ¼1¼Nwð~ xÞ, concluding the proof. h By Lemma 5, we can state that if eis ‘‘small enough’’ then the perceptron Nwevaluated on Dand ~ Dwill coincide. In the following results, we will restrict ourselves to kbalance datasets as a theoretical convenience. The next result relies on the accuracy (see Definition 1) of a perceptron evaluated on the original dataset and its representative dataset. Theorem 2 Let ~ Dbe a k-balanced e-representative dataset of the binary dataset D. Let Nwbe a perceptron with weights w 2Rnþ1.Ifemin nkwxk kwk:ðx;cxÞ2Dothen AðD;NwÞ¼Að~ D;NwÞ: Proof Since ~ Dis k-balance e-representative of D, then jXj¼kj~ Xjand we have: AðD;NwÞAð~ D;NwÞ¼ 1 jXjX x2X IwðxÞ 1 j~ XjX ~ x2~ X Iwð~ xÞ ¼1 jXjX x2X IwðxÞkIwð~ xÞðÞ ¼1 jXjX ~ x2~ XX xe~ x IwðxÞIwð~ xÞðÞ: Finally, IwðxÞ¼Iwð~ xÞfor all xe~ xand ð~ x;c~xÞ2 ~ Dby Lemma 5since e\kwxk kwkfor all ðx;cxÞ2D.h Next, let us compare the two errors Eðw;DÞand Eðw;~ DÞ obtained when considering the binary dataset Dand its kbalanced e-representative dataset ~ D. Theorem 3 Let ~ Dbe a k-balanced e-representative dataset of the binary dataset D. Then: kEðw;DÞEðw;~ DÞk  1 jXjX x2X2cxq1þq2kwðx~ xÞk where qm(being m ¼1;2) was defined in Lemma 4,and for each addend,xe~ x. Proof First, let us observe that: Eðw;DÞEðw;~ DÞ ¼1 jXjX x2X ðcxywðxÞÞ21 j~ XjX ~ x2~ X ðc~ xywð~ xÞÞ2 ¼1 jXjj~ Xjj~ XjX x2X ðcxywðxÞÞ2jXjX ~x2~ X ðc~xywð~ xÞÞ2: Now, since ~ Dis k-balanced e-representative of Dthen jXj¼kj~ Xj. Therefore, kEðw;DÞEðw;DÞk ¼1 jXjkX x2X 2cxy~ wð~ xÞywðxÞþy2 wðxÞy2 ~ wð~ xÞk 1 jXjX x2X 2cxky~ wð~ xÞywðxÞk þ ky2 wðxÞy2 ~ wð~ xÞk; where, for each addend, ~ xex. Applying Lemma 4for m¼1;2 to the last expression, we get: kEðw;DÞEðw;~ DÞk  1 jXjX x2X2cxq1þq2kwðx~ xÞk: h From this last result, we can infer the following: We can always fix the parameter e‘‘small enough’’ so that the difference between the error obtained when considering the dataset Dand its e-representative dataset is ‘‘close’’ to zero. Fig. 3aims to provide intuition for this result. Theorem 4 Let d[0. Let ~ Dbe a k-balanced e-repre- sentative dataset of the binary dataset D. Let Nwbe a perceptron with weights w 2Rnþ1.Ife54 43kwkd,then kEðw;DÞEðw;~ DÞk  d: Fig. 3 Intuition for Theorem 4. The error function can be understood as an error surface. For a fixed set of weights w, the difference between the error computed on the original dataset, E¼Eðw;DÞ, and on its k-balanced e-representative dataset, ~ E¼Eðw;~ DÞ, is bounded Neural Computing and Applications 123 Proof First, q11 4and q28 27 by Corollary 3. Second, since cx2f0;1g, we have: 1 jXjX x2X2cxq1þq2kwðx~ xÞk 1 jXjX x2X1 2þ8 27 kwðx~ xÞk ¼43 54 1 jXjX x2X kwðx~ xÞk: Applying Ho ¨lder inequality to the last expression, we get: 1 jXjX x2X2cxq1þq2kwðx~ xÞk  43 54 kwke: Therefore, by Theorem 3,ife54 43kwkd, then kEðw;XÞ Eðw;~ XÞk\das stated. h Summing up, we have proved that the accuracy and error of a perceptron evaluated on the binary dataset Dor on its k-balanced e-representative dataset, are equivalent. This fact will be highlighted in Sect. 6.1 for the perceptron case and in Sect. 6.2 for neural networks with more complex architectures. 6 Experimental results In this section, we experimentally prove that the accuracy of a neural network trained on the original dataset and on a dominating dataset is correlated with the parameter e. Besides, we also show that the accuracy is worse if we train the neural network on a random dataset. Evaluation metrics will be computed to show the performance of the trained neural network using different datasets. Specifically, MSE is the mean squared error, Recall is the ratio of positive identifications correctly classified over all positive identifications. Precision is the ratio of positive identifications correctly classified over all those classified positive. AUC is the area under the ROC curve. The ROC curve plots true positive rates vs. false positive rates at different classification thresholds. 6.1 The perceptron case In this section, two experiments are provided to support our theoretical results for the perceptron case and to illustrate the usefulness of our method. In the first experiment (Sect. 6.1.1), several synthetic datasets are presented showing different distributions. Random weight initialization is considered, and the holdout procedure is applied (i.e., the datasets were split into training dataset and test set) to test the generalization capabilities. In the second experiment (Sect. 6.1.2), the Iris dataset is considered. The perceptron is initiated with random weights and trained on three different datasets: the original dataset, a representative dataset (being the output of Algorithm 1) and a random dataset of the same size as the size of the representative dataset. Now, the trained perceptron is evaluated on the original dataset. This experiment supports that a perceptron trained on representative datasets get similar accuracy to a perceptron trained on 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 that representative datasets ensure good performance, while the random dataset provides no guarantees. 6.1.1 Synthetic datasets In this experiment, different datasets were generated using a Scikit-learn Python package implementation. 2 Roughly speaking, it creates clusters of normally distributed points in an hypercube and adds some noise. Specifically, we considered three different situations: (1) distribution without overlapping; (2) distribution with overlapping; and (3) a dataset with a ‘‘thin’’ class and a high e. In the last experiment, we wanted to show that the choice of eis important, and that there are cases where representative datasets are not so useful. In all three cases, the perceptron was trained using the stochastic gradient descent algorithm and the mean squared error as the loss function. The methodology followed in the experiments performed in this section is outlined in Fig. 4and summarized in the following steps. •Input: A dataset D¼ðx;cxÞ:x2XR2and cx2 f0;1gand a parameter e[0. •Divide the dataset Din a training dataset Sand a test set T. •Compute a dominating dataset ~ Sof Susing Algorithm 1. •Compute a random dataset Rof S. •Train the perceptron Nwon X, for X2fS;~ S;Rg. •Evaluate the trained perceptron on T. The aim of the second step in the methodology is to compute an e-representative dataset using Algorithm 1 (see Lemma 1of Sect. 3.1). Nevertheless, using Algorithm 1 is not mandatory, and we could replace it by any other 2 It can be found in https://scikit-learn.org/stable/modules/generated/ sklearn.datasets.make_classification.html. Neural Computing and Applications 123 in [27], where the redundancy of several datasets is empirically shown. In this paper, we propose the use of representative datasets as a new approach to reduce learning time in neural networks based on the topological structure of the input dataset. Specifically, we have defined representative datasets using a notion of nearness that has the Gromov– Hausdorff distance as the lower bound. Nevertheless, the bottleneck distance of persistence diagrams (which is a lower bound of the Gromov–Hausdorff distance) is used to measure the representativeness of the dataset since it is computationally less expensive. Besides, we have theoretically proved that the accuracy of a perceptron evaluated on the original dataset coincides with the accuracy of the neural network evaluated on its representative dataset when the neural network architecture is a perceptron, the loss function is the mean square error and certain conditions on the representativeness of the dataset are imposed. 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 a neural network. Planned future work is to provide more experiments using high-dimensional real data and different reduction algorithms. Furthermore, we plan to formally prove that the proposed approach can be extended to other neural network architectures and training algorithms using milder constraints. Let us observe that in the case that the dataset is already small, and then, it will not make sense to compute a representative dataset. The sparsity of the dataset may be a feature to be considered as a future work. Finally, we plan to investigate more efficient ways of computing dominating datasets in particular and representative datasets in general, since the algorithm proposed is just an example and, in general, will not compute the smallest possible representative dataset nor is it the fastest possible. Acknowledgements This work was partly supported by the Agencia Estatal de Investigacio ´n/10.13039/501100011033 under grant PID2019-107339GB-100 and the Agencia Andaluza del Conocimiento under grant P20-01145. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Declarations Conflict of interest The authors declare that there is no conflict of interest. Code availability The implementation of the methodology followed and the experimentation carried out can be consulted online in https:// github.com/Cimagroup/Experiments-Representative-datasets. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this Fig. 10 (Digits) Example of an image of each class of the digits dataset. They are 32 32 arrays in gray scale Table 9 Mean accuracy values after 5 repetitions of the neural network trained on the dominating dataset and evaluated on both the dominating dataset and the original dataset for the Digits classification problem eSize Accuracy on the original dataset Accuracy on the dominating dataset 0.1 1363 0.95 0.95 0.15 531 0.91 0.98 0.18 283 0.82 0.99 Neural Computing and Applications 123 article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons. org/licenses/by/4.0/. References 1. Goodfellow I, Bengio Y, Courville A (2016) Deep Learning. MIT Press, MA. http://www.deeplearningbook.org 2. Mohammadi B, Fathy M, Sabokrou M (2021) Image/video deep anomaly detection: a survey. arXiv:2103.01739 3. Biswas R, Blanco-Medina P (2021) State of the art: face recognition. arXiv:2108.11821 4. Brown TB, Mann B, Ryder N, Subbiah M et al (2020) Language models are few-shot learners. In: Advances in neural information processing systems, vol. 33, pp. 1877–1901. https://proceedings. neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a- Paper.pdf 5. Simonyan K, Zisserman A (2015) Very deep convolutional networks for large-scale image recognition. In: Bengio Y, LeCun Y (eds.) 3rd International Conference on Learning Representations, ICLR 2015. arXiv:1409.1556 6. Szegedy C, Liu W, Jia Y, Sermanet P, Reed S, Anguelov D, Erhan D, Vanhoucke V, Rabinovich A (2015) Going deeper with convolutions. In: 2015 IEEE conference on computer vision and pattern recognition (CVPR), pp 1–9. https://doi.org/10.1109/ CVPR.2015.7298594 7. He K, Zhang X, Ren S, Sun J (2016) Deep residual learning for image recognition. In: 2016 IEEE conference on computer vision and pattern recognition (CVPR), pp 770–778. https://doi.org/10. 1109/CVPR.2016.90 8. Miranda CS, Zuben FJV (2015) Reducing the training time of neural networks by partitioning. arXiv:1511.02954 9. You Z, Xu B (2014) Improving training time of deep neural networkwith asynchronous averaged stochastic gradient descent. In: The 9th international symposium on chinese spoken language processing, pp 446–449. https://doi.org/10.1109/ISCSLP.2014. 6936596 10. Xiao T, Zhu J, Liu T, Zhang C (2017) 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, pp 4193–4199. https://doi.org/10.24963/ijcai.2017/586 11. Wang T, Huan J, Li B (2018) Data dropout: optimizing training data for convolutional neural networks. In: 2018 IEEE 30th international conference on tools with artificial intelligence (ICTAI), pp 39–46. https://doi.org/10.1109/ICTAI.2018.00017 12. Wang Z, Zhu H, Dong Z, He X, Huang S-L (2020) Less is better: unweighted data subsampling via influence function. Proc AAAI Conf Artif Intell 34(04):6340–6347. https://doi.org/10.1609/aaai. v34i04.6103 13. Schmiedl F (2017) Computational aspects of the gromov-haus- dorff distance and its application in non-rigid shape matching. Discrete Comput Geom 57(4):854–880. https://doi.org/10.1007/ s00454-017-9889-4 14. Edelsbrunner H, Harer JL (2010) Computational topology, an introduction. American Mathematical Society, Providence 15. Chazal F, Cohen-Steiner D, Guibas LJ, Me ´moli F, Oudot SY (2009) Gromov-Hausdorff stable signatures for shapes using persistence. Computer Graphics Forum (proc. SGP 2009), 1393–1403 16. Tan M, Pang R, Le QV (2020) Efficientdet: scalable and efficient object detection. In: 2020 IEEE/CVF conference on computer vision and pattern recognition (CVPR), pp 10778–10787.https:// doi.org/10.1109/CVPR42600.2020.01079 17. Dey R, Salem FM (2017) Gate-variants of gated recurrent unit (gru) neural networks. In: 2017 IEEE 60th international midwest symposium on circuits and systems (MWSCAS), pp 1597–1600. https://doi.org/10.1109/MWSCAS.2017.8053243 18. Heck JC, Salem FM (2017) Simplified minimal gated unit variations for recurrent neural networks. In: 2017 IEEE 60th International Midwest Symposium on Circuits and Systems (MWSCAS), pp 1593–1596. https://doi.org/10.1109/MWSCAS. 2017.8053242 19. Haykin SS (2009) Neural networks and learning machines, 3rd edn. Pearson Education, Upper Saddle River 20. Hausmann J-C (2016) In: Quinn, F. (ed.) On the Vietoris-Rips complexes and a Cohomology Theory for metric spaces, pp 175–188. Princeton University Press, NJ. https://doi.org/10. 1515/9781400882588-013 21. Chazal F, de Silva V, Oudot S (2014) Persistence stability for geometric complexes. Geometriae Dedicata 173(1):193–214. https://doi.org/10.1007/s10711-013-9937-z 22. Gonzalez-Diaz R, Paluzo-Hidalgo E, Gutierrez-Naranjo MA (2018) Representative datasets for neural networks. Electron Notes Discrete Math 68:89–94. https://doi.org/10.1016/j.endm. 2018.06.016 (Discrete Mathematics Days 2018) 23. Matula DW (1987) Determining edge connectivity in 0(nm). In: 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp. 249–251. https://doi.org/10.1109/SFCS.1987.19 24. Gu J, Liu H, Zhou Y, Wang X (2017) DeepProf: performance analysis for deep learning applications via mining GPU execution patterns. arXiv:1707.03750 25. Jouppi NP, Young C, Patil N, Patterson D, et al (2017) In-data- center performance analysis of a tensor processing unit. In: Proceedings of the 44th annual international symposium on computer architecture. ISCA ’17, pp 1–12.https://doi.org/10. 1145/3079856.3080246 26. Yuan X, He P, Zhu Q, Li X (2019) Adversarial examples: attacks and defenses for deep learning. IEEE Trans Neural Netw Learn Syst 30(9):2805–2824. https://doi.org/10.1109/TNNLS.2018. 2886017 27. Toneva M, Sordoni A, Combes RTd, Trischler A, Bengio Y, Gordon GJ (2019) An empirical study of example forgetting during deep neural network learning. In: ICLR. https://openre view.net/forum?id=BJlxm30cKm Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Neural Computing and Applications 123