Memorization is worst-case generalization. Based on MacKay's information theoretic model of supervised machine learning, this article discusses how to practically estimate the maximum size of a neural network given a training data set. First, we present four easily applicable rules to analytically determine the capacity of neural network architectures. This allows the comparison of the efficiency of different network architectures independently of a task. Second, we introduce and experimentally validate a heuristic method to estimate the neural network capacity requirement for a given dataset and labeling. This allows an estimate of the required size of a neural network for a given problem. We conclude the article with a discussion on the consequences of sizing the network wrongly, which includes both increased computation effort for training as well as reduced generalization capability.
This questions of generalization and network architecture have recently become a heated academic discussion again as deep learning surprisingly seems to outperform shallow learning. For deep learning, single perceptrons with a nonlinear and continuous gating function are concatenated in a layered fashion. Techniques like convolutional filters, drop out, early stopping, regularization, etc., are used to tune performance, leading to a variety of claims about the capabilities and limits of each of these algorithms (for example @cite_3 ). We are aware of recent questioning of the approach of discussing the memory capacity of neural networks @cite_35 @cite_3 . Occam's razor @cite_20 dictates that one should follow the path of least assumptions, as perceptrons were initially conceived as a "generalizing memory", as detailed for example, in the early works of Widrow @cite_18 . This approach has also been suggested by @cite_17 and, as mentioned earlier, later explained in depth by MacKay @cite_29 . Also, the Ising model of ferromagnetism, which is a well-known model used to explain memory storage, has already been reported to have similarities to perceptrons @cite_27 @cite_21 and also to the neurons in the retina @cite_38 .
@cite_35 @cite_18 @cite_38 @cite_29 @cite_21 @cite_3 @cite_27 @cite_20 @cite_17
2682189153 2290730379 2165363188 2030450972 2950220847 2080531309 2070902649 2131497475
We examine the role of memorization in deep learning, drawing connections to capacity, generalization, and adversarial robustness. While deep networks are capable of memorizing noise data, our results suggest that they tend to prioritize learning simple patterns first. In our experiments, we expose qualitative differences in gradient-based optimization of deep neural networks (DNNs) on noise vs. real data. We also demonstrate that for appropriately tuned explicit regularization (e.g., dropout) we can degrade DNN training performance on noise datasets without compromising generalization on real data. Our analysis suggests that the notions of effective capacity which are dataset independent are unlikely to explain the generalization performance of deep networks when trained with gradient based methods because training data itself plays an important role in determining the degree of memorization. Fun and exciting textbook on the mathematics underpinning the most dynamic areas of modern science and engineering. The typical fraction of the space of interactions between each pair of N Ising spins which solve the problem of storing a given set of p random patterns as N-bit spin configurations is considered. The volume is calculated explicitly as a function of the storage ratio, alpha =p N, of the value kappa (>0) of the product of the spin and the magnetic field at each site and of the magnetisation, m. Here m may vary between 0 (no correlation) and 1 (completely correlated). The capacity increases with the correlation between patterns from alpha =2 for correlated patterns with kappa =0 and tends to infinity as m tends to 1. The calculations use a saddle-point method and the order parameters at the saddle point are assumed to be replica symmetric. This solution is shown to be locally stable. A local iterative learning algorithm for updating the interactions is given which will converge to a solution of given kappa provided such solutions exist. Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance. Conventional wisdom attributes small generalization error either to properties of the model family, or to the regularization techniques used during training. Through extensive systematic experiments, we show how these traditional approaches fail to explain why large neural networks generalize well in practice. Specifically, our experiments establish that state-of-the-art convolutional networks for image classification trained with stochastic gradient methods easily fit a random labeling of the training data. This phenomenon is qualitatively unaffected by explicit regularization, and occurs even if we replace the true images by completely unstructured random noise. We corroborate these experimental findings with a theoretical construction showing that simple depth two neural networks already have perfect finite sample expressivity as soon as the number of parameters exceeds the number of data points as it usually does in practice. We interpret our experimental findings by comparison with traditional models. The upper storage capacity of a neural network for patterns of fixed magnetization m is calculated. The optimal capacity increases with the correlation m2 between the patterns. Abstract We show that a polynomial learning algorithm, as defined by Valiant (1984), is obtained whenever there exists a polynomial-time method of producing, for any sequence of observations, a nearly minimum hypothesis that is consistent with these observations. Some of the main results in the mathematical evaluation of neural networks as information processing systems are discussed. The basic operation of feedback and feed-forward neural networks is described. Their memory capacity and computing power are considered. The concept of learning by example as it applies to neural networks is examined. >