Title: ON CHARACTERIZING THE CAPACITY OF NEURAL NETWORKS USING ALGEBRAIC TOPOLOGY

Abstract: The learnability of different neural architectures can be characterized directly by computable measures of data complexity. In this paper, we reframe the problem of architecture selection as understanding how data determines the most expressive and generalizable architectures suited to that data, beyond inductive bias. After suggesting algebraic topology as a measure for data complexity, we show that the power of a network to express the topological complexity of a dataset in its decision boundary is a strictly limiting factor in its ability to generalize. We then provide the first empirical characterization of the topological capacity of neural networks. Our empirical analysis shows that at every level of dataset complexity, neural networks exhibit topological phase transitions and stratification. This observation allowed us to connect existing theory to empirically driven conjectures on the choice of architectures for a single hidden layer neural networks.

1. INTRODUCTION:

Deep learning has rapidly become one of the most pervasively applied techniques in machine learning. From computer vision (Krizhevsky et al. (2012) ) and reinforcement learning (Mnih et al. (2013) ) to natural language processing (Wu et al. (2016) ) and speech recognition (Hinton et al. (2012) ), the core principles of hierarchical representation and optimization central to deep learning have revolutionized the state of the art; see Goodfellow et al. (2016) . In each domain, a major difficulty lies in selecting the architectures of models that most optimally take advantage of structure in the data. In computer vision, for example, a large body of work (Simonyan & Zisserman (2014) , Szegedy et al. (2014) , He et al. (2015) , etc.) focuses on improving the initial architectural choices of Krizhevsky et al. (2012) by developing novel network topologies and optimization schemes specific to vision tasks. Despite the success of this approach, there are still not general principles for choosing architectures in arbitrary settings, and in order for deep learning to scale efficiently to new problems and domains without expert architecture designers, the problem of architecture selection must be better understood.

Theoretically, substantial analysis has explored how various properties of neural networks, (eg. the depth, width, and connectivity) relate to their expressivity and generalization capability (Raghu et al. (2016) , Daniely et al. (2016) , Guss (2016) ). However, the foregoing theory can only be used to determine an architecture in practice if it is understood how expressive a model need be in order to solve a problem. On the other hand, neural architecture search (NAS) views architecture selection as a compositional hyperparameter search (Saxena & Verbeek (2016) , Fernando et al. (2017) , Zoph & Le (2017) ). As a result NAS ideally yields expressive and powerful architectures, but it is often difficult to interperate the resulting architectures beyond justifying their use from their emperical optimality.

We propose a third alternative to the foregoing: data-first architecture selection. In practice, experts design architectures with some inductive bias about the data, and more generally, like any hyperparameter selection problem, the most expressive neural architectures for learning on a particular dataset are solely determined by the nature of the true data distribution. Therefore, architecture selection can be rephrased as follows: given a learning problem (some dataset), which architectures are suitably regularized and expressive enough to learn and generalize on that problem?

A natural approach to this question is to develop some objective measure of data complexity, and then characterize neural architectures by their ability to learn subject to that complexity. Then given For example, take the two datasets D 1 and D 2 given in Figure 1 (ab) and Figure 1 (cd) respectively. The first dataset, D 1 , consists of positive examples sampled from two disks and negative examples from their compliment. On the right, dataset D 2 consists of positive points sampled from two disks and two rings with hollow centers. Under some geometric measure of complexity D 2 appears more 'complicated' than D 1 because it contains more holes and clusters. As one trains single layer neural networks of increasing hidden dimension on both datasets, the minimum number of hidden units required to achieve zero testing error is ordered according to this geometric complexity. Visually in Figure 1 , regardless of initialization no single hidden layer neural network with ≤ 12 units, denoted h ≤12 , can express the two holes and clusters in D 2 . Whereas on the simpler D 1 , both h 12 and h 26 can express the decision boundary perfectly. Returning to architecture selection, one wonders if this characterization can be extrapolated; that is, is it true that for datasets with 'similar' geometric complexity to D 1 , any architecture with ≥ 12 hidden learns perfectly, and likewise for those datasets similar in complexity to D 2 , architectures with ≤ 12 hidden units can never learn to completion?

1.1. OUR CONTRIBUTION:

In this paper, we formalize the above of geometric complexity in the language of algebraic topology. We show that questions of architecture selection can be answered by understanding the 'topological capacity' of different neural networks. In particular, a geometric complexity measure, called persistent homology, characterizes the capacity of neural architectures in direct relation to their ability to generalize on data. Using persistent homology, we develop a method which gives the first empirical insight into the learnability of different architectures as data complexity increases. In addition, our method allows us to generate conjectures which tighten known theoretical bounds on the expressivity of neural networks. Finally, we show that topological characterizations of architectures are possible and useful for architecture selection in practice by computing the persistent homology of CIFAR-10 and several UCI datasets.

2. BACKGROUND:



2.1. GENERAL TOPOLOGY:

In order to more formally describe notions of geometric complexity in datasets, we will turn to the language of topology. Broadly speaking, topology is a branch of mathematics that deals with characterizing shapes, spaces, and sets by their connectivity. In the context of characterizing neural networks, we will work towards defining the topological complexity of a dataset in terms of how that dataset is 'connected', and then group neural networks by their capacity to produce decision regions of the same connectivity. In topology, one understands the relationships between two different spaces of points by the continuous maps between them. Informally, we say that two topological spaces A and B are equivalent (A ∼ = B) if there is a continuous function f : A → B that has an inverse f -1 that is also continuous. When f exists, we say that A and B are homeomorphic and f is their homeomorphism; for a more detailed treatment of general topology see Bredon (2013) . Take for example, the classic example of the coffee cup and the donut in Figure 2 . They are homeomorphic because one can define a continuous deformation of one into the other which shrinks, twists, and morphs without tearing or gluing, as in Figure 2 . Note that if the donut had two holes, it would no longer be equivalent to the mug. Likewise, in an informal way, D 1 ∼ = D 2 in Figure 1 since if there were a homeomorphism f : D 1 → D 2 at least one of the clusters in D 1 would need to be split in order to produce the four different regions in D 2 .

The power of topology lies in its capacity to differentiate sets (topological spaces) in a meaningful geometric way that discards certain irrelevant properties such as rotation, translation, curvature, etc. For the purposes of defining geometric complexity, non-topological properties 1 like curvature would further fine-tune architecture selection-say if D 2 had the same regions but with squigly (differentially complex) boundaries, certain architectures might not converge-but as we will show, grouping neural networks by 'topological capacity' provides a powerful minimality condition. That is, we will show that if a certain architecture is incapable of expressing a decision region that is equivalent in topology to training data, then there is no hope of it ever generalizing to the true data.

2.2. ALGEBRAIC TOPOLOGY:

Algebraic topology provides the tools necessary to not only build the foregoing notion of topological equivalence into a measure of geometric complexity, but also to compute that measure on real data (Betti (1872 ), Dey et al. (1998) , Bredon (2013) ). At its core, algebraic topology takes topological spaces (shapes and sets with certain properties) and assigns them algebraic objects such as groups, chains, and other more exotic constructs. In doing so, two spaces can be shown to be topologically equivalent (or distinct) if the algebraic objects to which they are assigned are isomorphic (or not). Thus algebraic topology will allow us to compare the complexity of decision boundaries and datasets by the objects to which they are assigned.

Although there are many flavors of algebraic topology, a powerful and computationally realizable tool is homology.

Definition 2.1 (Informal, Bredon (2013) ). If X is a topological space, then H n (X) = Z βn is called the nth homology group of X if the power β n is the number of 'holes' of dimension n in X. Note that β 0 is the number of separate connected components. We call β n (X) the nth Betti number of X. Finally, the homology2 of X is defined as

H(X) = {H n (X)} ∞ n=0 .

Immediately homology brings us closer to defining the complexity of D 1 and D 2 . If we assume that D 1 is not actually a collection of N datapoints, but really the union of 2 solid balls, and likewise that D 2 is the union of 2 solid balls and 2 rings, then we can compute the homology directly. In this case H 0 (D 1 ) = Z 2 since there are two connected components3 ; H 1 (D 1 ) = {0} since there are no circles (one-dimensional holes); and clearly, H n (D 1 ) = {0} for n ≥ 2. Performing the same computation in the second case, we get H 0 (D 2 ) = Z 4 and H 1 (D 2 ) = Z 2 as there are 4 seperate clusters and 2 rings/holes. With respect to any reasonable ordering on homology, D 2 is more complex than D 1 . The measure yields non-trivial differentiation of spaces in higher dimension. For example, the homology of a hollow donut is

{Z 1 , Z 2 , Z 1 , 0, . . . }.

Surprisingly, the homology of a space contains a great deal of information about its topological complexity 1 . The following theorem suggests the absolute power of homology to group topologically similar spaces, and therefore neural networks with topologically similar decision regions.

Theorem 2.2 (Informal). Let X and Y be topological spaces.

If X ∼ = Y then H(X) = H(Y ). 4

Intuitively, Theorem 2.2 states that number of 'holes' (and in the case of H 0 (X), connected components) are topologically invariant, and can be used to show that two shapes (or decision regions) are different.

2.3. COMPUTATIONAL METHODS FOR HOMOLOGICAL COMPLEXITY:

In order to compute the homology of both D 1 and D 2 we needed to assume that they were actually the geometric shapes from which they were sampled. Without such assumptions, for any dataset D a H(D) = {Z N , 0, . . . } where N is the number of data points. This is because, at small enough scales each data point can be isolated as its own connected component; that is, as sets each pair of different positive points d 1 , d 2 ∈ D are disjoint. To properly utilize homological complexity in better understanding architecture selection, we need to be able to compute the homology of the data directly and still capture meaningful topological information. Persistent homology, introduced in Zomorodian & Carlsson (2005) , avoids the trivialization of computation of dataset homology by providing an algorithm to calculate the homology of a filtration of a space. Specifically, a filtration is a topological space X equipped with a sequence of subspaces

X 0 ⊂ X 1 ⊂ • • • ⊂ X.

In Figure 3 one such particular filtration is given by growing balls of size centered at each point, and then letting X be the resulting subspace in the filtration. Define β n (X) to be the nth Betti number of the homology H(X ) of X . Then for example at = 1.5, β 0 (X ) = 19 and β 1 (X ) = 0 as every ball is disjoint. At = 5.0 some connected components merge and β 0 (X ) = 12 and β 1 (X ) = 0. Finally at = 7, the union of the balls forms a hole towards the center of the dataset and β 1 (X ) > 0 with β 0 (X ) = 4.

All together the change in homology and therefore Betti numbers for X as changes can be summarized succinctly in the persistence barcode diagram given in Figure 3 . Each bar in the section β n (X) denotes a 'hole' of dimension n. The left endpoint of the bar is the point at which homology detects that particular component, and the right endpoint is when that component becomes indistinguishable in the filtration. When calculating the persistent homology of datasets we will frequently use these diagrams.

With the foregoing algorithms established, we are now equipped with the tools to study the capacity of neural networks in the language of algebraic topology.

3. HOMOLOGICAL CHARACTERIZATION OF NEURAL ARCHITECTURES:

In the forthcoming section, we will apply persistent homology to emperically characterize the power of certain neural architectures. To understand why homological complexity is a powerful measure for differentiating architectures, we present the following principle.

Suppose that D is some dataset drawn from a joint distribution F with continuous CDF on some topological space X × {0, 1}. Let X + denote the support of the distribution of points with positive labels, and X -denote that of the points with negative labels. Then let

H S (f ) := H[f -1 ((0, ∞))]

denote the support homology of some function f : X → {0, 1}. Essentially H S (f ) is homology of the set of x such that f (x) > 0. For a binary classifier, f , H S (f ) is roughly a characterization of how many 'holes' are in the positive decision region of f . We will sometimes use β n (f ) to denote the nth Betti number of this support homology. Finally let F = {f : X → {0, 1}} be some family of binary classifiers on X.

Theorem 3.1 (The Homological Principle of Generalization). If X = X -X + and for all f ∈ F with H S (f ) = H(X + ), then for all f ∈ F there exists A ⊂ X + so f misclassifies every x ∈ A.

Essential Theorem 3.1 says that if an architecture (a family of models F) is incapable of producing a certain homological complexity, then for any model using that architecture there will always be a set A of true data points on which the model will fail. Note that the above principle holds regardless of how f ∈ F is attained, learned or otherwise. However, the principle does imply that no matter how well some F learns to correctly classify D there will always be a counter examples in the true data.

In the context of architecture selection, the foregoing minimality condition significantly reduces the size of the search space by eliminating smaller architectures which cannot even express the 'holes' (persistent homology) of the data H(D). This allows us to return to our original question of finding suitably expressive and generalizeable architectures but in the very computable language of homological complexity: Let F A the set of all neural networks with 'architecture' A, then Given a dataset D, for which architectures A does there exist a neural network f ∈ F A such that H S (f ) = H(D)? We will resurface a contemporary theoretical view on this question, and thereafter make the first steps towards an emperical characterization of the capacity of neural architectures in the view of topology.

3.1. THEORETICAL BASIS FOR NEURAL HOMOLOGY:

Theoretically, the homological complexity of neural network can be framed in terms of the sum of the number of holes expressible by certain architectures. In particular, Bianchini et al. (2014) gives an analysis of how the maximum sum of Betti numbers grows as F A changes. The results, summarized in Table 1 , show that the width, depth, and activation of a fully connected architecture effect its topological expressivity to varying polynomial and exponential degrees. What is unclear from this analysis is how these bounds describe expressivity in terms of individual Betti numbers. For example, with a tanh activation function, n inputs, layers, and h hidden units, there is no description of what the number of connected components max f ∈F A β 0 (f ) or 1-dimensional holes max f ∈F A β 1 (f ) actually is. With regards to tighter bounds Bianchini et al. (2014) stipulate that improvements to their results are deeply tied to several unsolved problems in algebraic topology.

Table 1 : Upper bounds on homological expressivity of neural architectures (Bianchini et al. (2014) .)

Architecture A max f ∈F A n k=1 β k (f ) Inputs Layers Units Activation n 3 h threshold O(h n ) n 3 h arctan O((n + h) n+2 ) n 3 h polynomial, deg. r 1 2 (2 + r)(1 + r) n-1 1 3 h arctan h n h arctan 2 h(2h-1) O((n + n) n+2h ) n h tanh 2 h(h-1)/2 O((n + n) n+h ) n h polynomial, deg. r 1 2 (2 + r)(1 + r) n-1 )

Figure 4 : Topological phase transitions in low dimensional neural networks as the homological complexity of the data increases. The upper right corner of each plot is a dataset on which the neural networks of increasing hidden dimension are trained.

3.2. EMPIRICAL RESULTS:

To understand how the homology of data determines expressive architectures we turn to an empirical characterization of neural networks. In this setting, we can tighten the bounds given in Table 1 by training different architectures on datasets with known homologies and then recording the decision regions observed over the course of training.

3.2.1. HOMOLOGICAL CAPACITY OF HIDDEN UNITS.:

In the most basic case, one is interested in studying how the number of hidden units in a single hidden layer neural network affect its homological capacity. Restricting5 our analysis to the case of two inputs, n = 2, we characterize the capacities of architectures with an increasing number of hidden units to learn on datasets with homological complexities ranging from {Z 1 , 0} to {Z 20 , Z 20 }. In our experiment, we generate datasets of each particular homological complexity by sampling different combinations of balls, rings, and scaling, twisting, and gluing them at random. After generating the foregoing datasets with N ≈ 90000 samples we train 100 randomly (truncated normal) initialized single hidden layer architectures with hidden units h ∈ {1, . . . , 255} and tanh activation functions for 10 6 minibatches of size 128. During training, every 2500 batches we sample the decision boundary of each neural network over a grid of 500 × 500 samples, producing 1.02 × 10 6 recorded decision boundaries. Using the resulting data, we not only characterize different architectures but observed interesting topological phenomena during learning. First, neural networks exhibit a statistically significant topological phase transition in their convergence which depends directly on the homological complexity of the data. For any dataset in the experiment and any random homeomorphism applied thereto, the best test error of architectures with h hidden units is strictly ordered in magnitude and convergence time for h < h phase where h phase is a number of hidden units required to express the homology of the data. In Figure 4 we plot the best performing test error of architectures h ∈ {1, . . . , 15} on some example datasets D 0 , D 1 , and D 2 with H(D 0 ) ≈ {Z 2 , 0}, H(D 1 ) ≈ {Z 3 , 0}, H(D 2 ) ≈ {Z 3 , Z 2 }. In this example h phase (D 0 ) = 4, h phase (D 1 ) = 6, and h phase (D 2 ) = 10. Surprisingly, leading up to the phase transition point, each different architecture falls into its own band of optimal convergence. This suggests that additional hidden units do in fact add to the topological capacity of an architecture in a consistent way.

Using topological phase transitions we now return to the original question of existence of expressive architectures. In Figure 5 , we accumulate the probabilities that neural networks of varying hidden dimension train to zero-error on datasets of different homological complexities. The table gives different views into how expressive an architecture need be in order to converge, and therefore we are able to conjecture tighter bounds on the capacity of hidden units. Extrapolating from the first view, if H 0 (D) = Z m then there exists a single hidden layer neural network with h = m + 2 that converges to zero error on D. Likewise we claim that if H 0 (D) = Z m and H 1 (D) = 1 then the same holds with h ≥ 3m -1. Further empirical analysis of convergence probabilities yields additional conjectures. However, claiming converse conjectures about a failure to generalize in the view of Theorem 3.1 requires exhaustive computation of decision boundary homologies.

By applying persistent homology to the decision boundaries of certain networks during training, we observe that given sufficient data, neural networks exhibit topological stratification. For example, consider the homologies of different architecture decision regions as training progresses in Figure 6(a) . At the beginning of training every model captures the global topological information of the dataset and is homologically correlated with one another. However as training continues, the architectures stratify into two groups with homological complexities ordered by the capacities of the models. In this example, h 3 , h 4 , and h 5 are unable to express as many holes as the other architectures and so never specialize to more complex and local topological properties of the data. Figure 6(b ) depicts topological stratification in terms of the correlation between Betti numbers. Topologically speaking, networks with less than 6 hidden units are distinct from those with more for most of training. Furthermore, this correlative view shows that stratification is consistent with topological phase transition; that is, across all decision boundary homologies recorded during the experiment stratification occurs just when the number of hidden units is slightly less than h phase .

4. THE TOPOLOGY OF REAL DATA:

We have thus far demonstrated the discriminatory power of homological complexity in determining the expressivity of architectures. However, for homological complexity to have any practical use in architecture selection, it must be computable on real data, and more generally real data must have non-trivial homology; if all data were topologically simple our characterization would have no predictive power. In the following section we will compute the persistent homologies up to dimension 2 of different real world datasets. CIFAR-10. We compute the persistent homology of several classes of CIFAR-10 using the Python library Dionysus. Currently algorithms for persistent homology do not deal well with high dimensional data, so we embed the entire dataset in R 3 using local linear embedding (LLE; Saul & Roweis (2000)) with K = 120 neighbors. After embedding the dataset, we take a sample of 1000 points from example class 'car' and build a persistent filtration by constructing a Vietoris-Rips complex on the data. The resulting complex has 20833750 simplices and took 4.3 min. to generate. Finally, computation of the persistence diagram shown in Figure 7 took 8.4 min. locked to a single thread on a Intel Core i7 processor. The one-time cost of computing persistent homology could easily augment any neural architecture search.

Although we only give an analysis of dimension 2 topological features-and there is certainly higher dimensional homological information in CIFAR-10-the persistence barcode diagram is rich with different components in both H 0 (D) and H 1 (D). Intuitively, CIFAR contains pictures of cars rotated accross a range of different orientations and this is exhibited in the homology. In particular, several holes are born and die in the range ∈ [0.15, 0.375] and one large loop from ∈ [0.625, 0.82].

UCI Datasets. We further compute the homology of three low dimensional UCI datasets and attempt to assert the of non-trivial , h phase . Specifically, we compute the persistent homology of the majority classes in the Yeast Protein Localization Sites, UCI Ecoli Protein Localization Sites, and HTRU2 datasets. For these datasets no dimensionality reduction was used. In Figure 7 (left), the persistence barcode exhibits two seperate significant loops (holes) at ∈ [0.19, 0.31] and ∈ [0.76, 0.85], as well as two major connected components in β 0 (D). The Other persistence diagrams are relegated to the appendix.

Existing Data. Outside of the primary machine learning literature, topological data analysis yields non-trivial computations in wide variety of fields and datasets. Of particular interest is the work of Carlsson et al. (2008) , which computes the homological complexity of collections of n × n patches of natural images. Even in these simple collections of images, the authors found topologies of Klein Bottles (H(•) = {Z, Z 2 /2Z, 0 . . . }) and other exotic topological objects. Other authors have calculated non-trivial dataset homologies in biological (Topaz et al. (2015) ), natural language (Michel et al. (2017) ), and other domains (Wu et al. (2017) , Xia & Wei (2014) ).

5. RELATED WORK:

We will place this work in the context of deep learning theory as it relates to expressivity. Since the seminal work of Cybenko (1989) which established standard universal approximation results for neural networks, many theorists have endeavored to understand the expressivity of certain neural architectures. Pascanu et al. (2013) and MacKay (2003) provided the first analysis relating the depth and width of architectures to the complexitity of the sublevel sets they can express. Motivated therefrom, Bianchini et al. (2014) expressed this theme in the language of Pfefferian functions, thereby bounding the sum of Betti numbers expressed by sublevel sets. Finally Guss (2016) gave an account of how topological assumptions on the input data lead to optimally expressive architectures. In parallel, Eldan & Shamir (2016) presented the first analytical minimality result in expressivity theory; that is, the authors show that there are simple functions that cannot be expressed by two layer neural networks with out exponential dependence on input dimension. This work spurred the work ofPoole et al. ( 2016), Raghu et al. (2016) which reframed expressivity in a differential geometric lense.

Our work presents the first method to derive expressivity results empirically. Our topological viewpoint sits dually with its differential geometric counterpart, and in conjunction with the work of Poole et al. (2016) and Bianchini et al. (2014) , this duallity implies that when topological expression is not possible, exponential differential expressivity allows networks to bypass homological constaints at the cost of adversarial sets. Furthermore, our work opens a practical connectio nbetween the foregoing theory on neural expressivity and architecture selection, with the potential to drastically improve neural architecture search (Zoph & Le (2017) ) by directly computing the capacities of different architectures.

6. CONCLUSION:

Architectural power is deeply related to the algebraic topology of decision boundaries. In this work we distilled neural network expressivity into an empirical question of the generalization capabilities of architectures with respect to the homological complexity of learning problems. This view allowed us to provide an empirical method for developing tighter characterizations on the the capacity of different architectures in addition to a principled approach to guiding architecture selection by computation of persistent homology on real data.

There are several potential avenues of future research in using homological complexity to better understand neural architectures. First, a full characterization of neural networks with many layers or convolutional linearities is a crucial next step. Our empirical results suggest that the their are exact formulas describing the of power of neural networks to express decision boundaries with certain properties. Future theoretical work in determining these forms would significantly increase the efficiency and power of neural architecture search, constraining the search space by the persistent homology of the data. Additionally, we intend on studying how the topological complexity of data changes as it is propagated through deeper architectures.

A PROOFS, CONJECTURES, AND FORMAL DEFINITIONS:

A.1 HOMOLOGY Homology is naturally described using the language of category theory. Let T op 2 denote the category of topological spaces and Ab the category of abelian groups.

Definition A.1 (Homology Theory, Bredon (2013) ). A homology theory on the on T op 2 is a function H : T op 2 → Ab assigning to each pair (X, A) of spaces a graded (abelian) group {H p (X, A)}, and to each map f : (X, A) → (Y, B), homomorphisms f * : H p (X, A) → H p (Y, B), together with a natural transformation of functors ∂ * : H p (X, A) → H p-1 (X, A), called the connecting homomorphism (where we use H * (A) to denote H * (A, ∅)) such that the following five axioms are satisfied.

1. If f g : (X, A) → (Y, B) then f * = g * : H * (X, A) → H * (Y, B).

2. For the inclusions i : A → X and j : X → (X, A) the sequence sequence of inclusions and connecting homomorphisms are exact.

3. Given the pair (X, A) and an open set U ⊂ X such that cl(U ) ⊂ int(A) then the inclusion k : (X -U, A -U ) → (X, A) induces an isomorphism k * : H * (X -U, A -U ) → H * (X, A)

4. For a one point space P, H i (P ) = 0 for all i = 0.

5. For a topological sum X = + α X α the homomorphism

(i α ) * : H n (X α ) → H n (X)

is an isomorphism, where i α : X α → X is the inclusion.

For related definitions and requisite notions we refer the reader to Bredon (2013) .

A.2 PROOF OF THEOREM 3.1

Theorem A.2. Let X be a topological space and X + be some open subspace. If F ⊂ 2 X such that f ∈ F implies H S (f ) = H(X + ), then for all f ∈ F there exists A ⊂ X so that f (A ∩ X + ) = {0} and f (A ∩ (X \ X + )) = {1}.

Proof. Suppose the for the sake of contraiction that for all f ∈ F, H S (f ) = H(X + ) and yet there exists an f such that for all A ⊂ X, there exists an x ∈ A such that f (x) = 1. Then take A = {x} x∈X , and note that f maps each singleton into its proper partition on X. We have that for any open subset of V ⊂ X + , f (V ) = {1}, and for any closed subset W ⊂ X \ X + , f (W ) = {0}. Therefore X + = A∈τ X + ∩X A ⊂ supp(f ) as the subspace topology τ X + ∩X = τ X + ∩ τ X where τ X + = {A ∈ τ X | A ⊂ X + } and τ X denotes the topology of X. Likewise, int(X -) ⊂ X \supp(F ) under the same logic. Therefore supp(f ) has the exact same topology as X + and so by Theorem 2.2 H(X + ) = H(supp(f )) but this is a contradiction. This completes the proof.

A.3 THE NEURAL HOMOLOGY PRINCIPLE:

Conjecture A.3. If N is some neural network with layers and h hidden units, and H S (N ) = H(X + ) then E[L(N, D)] > c for some fixed c( , h) > 0. 

E EXAMPLE SAMPLED DATASETS:



:

A topological property or invariant is one that is preserved by a homeomorphism. For example, the number of holes and regions which are disjoint from one another are topological properties, whereas curvature is not.

This definition of homology makes many assumptions on X and the base field of computation, but for introductory purposes, this informality is edifying.

Informally, a connected component is a set which is not contained in another connected set except for itself.

Equality of H(X) and H(Y ) should be interpreted as isomorphism between each individual Hi(X) and Hi(Y ).

Analysis of greater input dimension was not given due to space constraints (decision boundary samples alone accounted for 18.55 TB), but in future work Monte Carlo samples of the decision boundary suffice to perform the forthcoming analysis; seeChazal et al. (2015).

Figures and Tables:

Figure 1: The positive label outptus of single hidden layer neural networks, h 12 and h 26 , of 2 inputs with 12 and 26 hidden units respectively after training on datasets D 1 and D 2 with positive examples in red. Highlighted regions of the output constitute the positive decision region.

Figure 2: A continuous deformation of a coffee cup into a donut, showing that both are topologically equivalent (Kato et al. (2014)).

Figure 3: Left: The local disconnectedness of datasets prevents direct computation of their homology. Right: An illustration of computing persistent homology on a collection of points (Topaz et al. (2015))

The results of Bianchini et al. (2014) say for certain activation functions we should expect a polynomial dependence on the sum of Betti numbers β n , but is this true of individual numbers? Having an individual characterization would allow for architecture selection by computing the homology of the dataset, and then finding which architectures meet the minimal criterion for each Betti number β n .

Figure 5: Several different views of the probability of converging to zero-error for single hidden layer neural networks on datasets with different homological complexities.

Figure 6: An example of topological stratification for single hidden layer networks. (a) The number of connected components in the decision regions during training. (b) Correlation of Betti numbers.

Figure 7: The persistent homology barcodes of classes in the CIFAR-10 and UCI Protein Localization Datasets. Left: The bardcode for dimension 0 and 1 of the 'CYT' class along side its local linear embedding into R 2 . Right: The barcode for the dimensions 0 and 1 for the 'cars' class along side different samples thereof in CIFAR-10. Note how different orientations are shown.

Figure 10: Topological phase transitions for datasets with β(D) ∈ {(4, 3), (5, 0)}

Figure 11: Topological stratification for {h 3 , . . . , h 15 } on a random dataset D with β 0 (D) = 25, β 1 (D) = 16.

Figure 12: Topological stratification for {h 1 , . . . , h 5 } on a random dataset D with β 0 (D) = 3, β 1 (D) = 0.

Figure 13: Topological stratification for {h 3 , . . . , h 7 } on a random dataset D with β 0 (D) = 3, β 1 (D) = 0. D ADDITIONAL TOPOLOGY OF REAL DATA

Peer review (iclr2018):
 Paper Summary: This paper looks at empirically measuring neural network architecture expressivity by examining performance on a variety of complex datasets, measuring dataset complexity with algebraic topology. The paper first introduces the notion of topological equivalence for datasets -- a desirable measure to use as it is invariant to superficial differences such as rotation, translation and curvature. The definition of homology from algebraic topology can then be used as a robust measure of the "complexity" of a dataset. This notion of difficulty focuses roughly on determining the number of holes of dimension n (for varying n) there are in the dataset, with more holes roughly leading to a more complex connectivity pattern to learn. They provide a demonstration of this on two synthetic toy datasets in Figure 1, training two (very small -- 12 and 26 neuron) single hidden layer networks on these two datasets, where the smaller of the two networks is unable to learn the data distribution of the second dataset. These synthetic datasets have a well defined data distribution, and for an empirical sample of N points, a (standard) method of determining connectivity by growing epsilon balls around each datapoint in section 2.3. The authors give a theoretical result on the importance of homology: if a binary classifier has support homology not equal to the homology of the underlying dataset, then there is at least one point that is misclassified by the classifier. Experiments are then performed with single hidden layer networks on synthetic datasets, and a phase transition is observed: if h_phase is the number of hidden units where the phase transition happens, and h* < h < h_phase, h* has higher error and takes longer to converge than h. Finally, the authors touch on computing homology of real datasets, albeit with a low dimensional projection (e.g. down to 3 dimensions for CIFAR-10). Main Comments The motivation to consider algebraic topology and dataset difficulty is interesting, but I think this method is ultimately ill suited and unable to be adapted to more complex and interesting settings. In particular, the majority of experiments and justification of this method comes from use on a low dimensional manifold with either known data distribution, or with a densely sampled manifold. (The authors look at using CIFAR-10, but project this down to 3 dimensions -- as current methods for persistent homology cannot scale -- which somewhat invalidates the goal of testing this out on real data.) This is an important and serious drawback because it seems unlikely that the method described in Figure 3 of determining the connectivity patterns of a dataset are likely to yield insightful results in a high dimensional space with very few datapoints (in comparison to 2^{dimension}), where distance between datapoints is unlikely to have any nice class related correspondence. Furthermore, while part of the motivation of this paper is to use dataset complexity measured with topology to help select architectures, experiments demonstrating that this might be useful are very rudimentary. All experiments only look at single hidden layers, and the toy task in Figure 1 and in section 3.2.1 and Figure 5 use extremely small networks (hidden size 12-26). It*s hard to be convinced that these results necessarily generalize even to other larger hidden layer models. On real datasets, exploring architectures does not seem to be done at all (Section 4). Minor Comments Some kind of typo in Thm 1? (for all f repeated twice) Small typos (missing spaces) in related work and conclusion How is h_phase determined? Empirically? (Or is there a construction?) Review Summary: This paper is not ready to be accepted.