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. Deep learning has rapidly become one of the most pervasively applied techniques in machine learning. From computer vision BID15 ) and reinforcement learning BID18 ) to natural language processing BID27 ) and speech recognition ), the core principles of hierarchical representation and optimization central to deep learning have revolutionized the state of the art; see BID10 . 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 BID24 , BID25 , BID12 , etc. ) focuses on improving the initial architectural choices of BID15 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 , BID6 , BID11 ). 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 BID23 , BID9 , BID31 ). 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 some new dataset, the problem of architecture selection is distilled to computing the data complexity and chosing the appropriate architecture.For example, take the two datasets D 1 and D 2 given in FIG0 (ab) and FIG0 (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 FIG0 , 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? 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.
We show that the learnability of different neural architectures can be characterized directly by computable measures of data complexity.
{"src": "scitldr-AIC_train", "paper_id": "H11lAfbCW"}