33 ms·
Computer scientists prove why bigger neural networks do better
- feketegy 5y agoThis looks interesting, I bookmarked it. My biggest blocker is the "statistics" part of M/L, knowing what algorithms to choose for various cases.
- kache_ 5y agocheck out introduction to statistical learning
- qorrect 5y agoThis book was a big help for me and is very well written, https://xcelab.net/rm/statistical-rethinking/ https://xcelab.net/rm/statistical-rethinking/ . You can find it free online ( along with video course ). The printed version is a very nice high quality book.
- stevofolife 5y agoDo you know if there are any online classes that use this book as a reference? Or more generally, what type of courses teaches this subject?
- lariati 5y agoThanks so much. That is an amazing level of choice in the example code. I need this right now as a type of statistical strength training.
- SpaceManNabs 5y ago> Right now, we are routinely creating neural networks that have a number of parameters more than the number of training samples. This says that the books have to be rewritten. Confused by this statement. Double descent with overparameterization is exhibited in "classical settings" too and mentioned in older books. > In their new proof, the pair show that overparameterization is necessary for a network to be robust. What is important to note here is that many of papers this paper cites prove or show this result in certain network architectures. This paper adds universality. > The proof is very elementary — no heavy math, and it says something very general The most elementary part was clever use of Hoeffding's inequality. Some people are really fast readers haha. I don't even know how you pick up the fact that isoperimetry holds in manifold settings with positive curvature while also playing with all those norms and inequalities. A few years ago I mentioned on here all the maths that I knew or wanted to know to read more papers, and others critiqued that the list was too long. Well, this is why!
- aray 5y ago> Double descent with overparameterization is exhibited in "classical settings" too and mentioned in older books. I’m curious for references or citations to this. When I was going over double descent I tried to find citations like this (just in a couple places like ML/stats textbooks).
- tomrod 5y agoThere are a handful of papers in the 90s that show this, but it wasn't recognized for what it is. Double descent is REALLY crazy to me, coming from a classical background.
- pishpash 5y agoOver-parameterization for regularization is really old. The pseudoinverse min-norm solution for under-determined linear systems even has that flavor.
- tomrod 5y agoSure, but that's identification approaches in econometrics and matrix analysis contexts. Using that for neural networks is new-ish in the zeitgeist, which did not exist in the 1990s as it does today.
- moyix 5y agoHere's one that lists some older references: https://arxiv.org/abs/2004.04328 https://arxiv.org/abs/2004.04328
- throwmeawaysoon 5y ago
- carbocation 5y agoDaniela Witten has a nice twitter thread on the topic of double descent in classical settings: https://twitter.com/daniela_witten/status/1292293104855158784 https://twitter.com/daniela_witten/status/129229310485515878...
- prideout 5y ago> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- aix1 5y agoNot my area of expertise, but the quoted "fact" seems at best incompletely stated: surely for it to hold there must be some constraints on the number of points (likely as a function of the diameter)?
- Retric 5y agoIt’s just wrong as stated, there is only one point a full diameter away from each point on a high dimensional sphere. Aka (1,0,0,0,0, …) maps to (-1,0,0,0,0, …) and nothing else. Just as (1,0) maps to (-1,0) on a unit circle and (1,0,0) maps to (-1,0,0) on a unit sphere. On a high dimensional sphere they should generally be close to square root of 2 radius away from each other.
- bick_nyers 5y agoEuclidean distance calculations change based on number of dimensions, for example, in 3 dimensions it is sqrt(a^2+b^2+c^2).
- Retric 5y agoYes, that’s why it’s square root of 2. Consider the origin (0,0,0, …) to a random point on the sphere (~0, ~0, ~0, …). Distance = square root of ((X1 - X2) ^ 2 + (Y1 - Y2) ^2 + …). So D = square root of ((~0-0)^2 + (~0-0)^2 + (~0-0)^2 + … ), which is equal to 1 by definition of the unit high dimensional sphere. So distance from (1,0,0,0 …) to (~0, ~0, ~0, …) = square root of ((~0-1)^2 + (~0-0)^2 + (~0-0)^2 + … ) ~= square root of 2.
- 6gvONxR4sf7o 5y agoOff topic, but I love that they make it trivial to find a link to the original paper. I know not everyone loves quanta, but stuff like this is really refreshing.
- lordgrenville 5y agoWhat do people not like about Quanta?
- deleted 5y ago[deleted]
- stared 5y agoI am surprised that the paper does not even cite the Lottery Ticket Hypothesis (https://arxiv.org/abs/1803.03635 https://arxiv.org/abs/1803.03635, https://eng.uber.com/deconstructing-lottery-tickets/ https://eng.uber.com/deconstructing-lottery-tickets/). In the LTH paper (IMHO the most fundamental deep learning publication in the last few years), the number of tickets goes as layer_size^n_layers.
- renewiltord 5y agoConsidering the subject, it is at least somewhat amusing that you double posted this.
- gwern 5y agoI don't see how lottery tickets yield the isoperimetry result, even in a heuristic or handwavy sort of way. Yes, a larger network is more likely to have good-scoring subnetworks; sure. But that's all it says. What does that tell me about how efficiently I can construct an adversarial example? For that, I need something else, like, say a geometric argument about what sort of network will interpolate between high-dimensional datapoints with properties like "not changing much in response to small input changes"...
- paraph1n 5y agoIn the linked Uber paper, can someone explain the plots with the ellipses? It's a 2d plot of initial vs final weight, yes? But where does the ellipse shape come from and why?
- amelius 5y agoAsymptotically better? Or practically better?
- ravi-delia 5y agoWe know from reality that they get practically better, but theoretic intuition suggests you shouldn't see an effect after some point. This paper shows that this intuition is wrong if you want your networks to be robust. It doesn't guarantee large networks will be though.
- ogogmad 5y agoDoes this help against adversarial examples? The article seems to suggest so.
- zwaps 5y agoCan someone speak to the generality of assuming c-isoperimetry for the distribution of features? Without knowing anything about this in particular, this seems to be a rather pertinent restriction of the result related to things like sampling assumptions and the like.
- woopwoop 5y agoIt really depends on what we assume about "natural" data. If it looks "positively curved", e.g. the uniform measure on the boundary of a convex body, or the a gaussian, or something, this holds. But if the distribution exhibits a strong hierarchical structure that's not so good. I think it's a plausible if not obviously true assumption.
- AmericanBlarney 5y agoThis conclusion feels like saying more CPU and memory are better. Seems obvious that more moves allows matching to have more nuance, but I guess cool that someone proved it.
- nazgul17 5y agoFrom what I understand, it says that more parameters are good. This wasn't obvious before this paper: you can fit a polynomial instead of a neutral net, but adding parameters wouldn't help with robustness in that case: the polynomial would become more and more jagged.
- ska 5y ago> Seems obvious that more moves allows matching to have more nuance, This really has to be balance against overfitting. The key problem in ML is generalization, and lots of things improve training performance while making that worse.
- rackjack 5y agoSilly thought: if bigger NN's are better, shouldn't more neurons be better? Why aren't elephants smarter than us, despite having more neurons? https://en.wikipedia.org/wiki/List_of_animals_by_number_of_neurons https://en.wikipedia.org/wiki/List_of_animals_by_number_of_n... https://pubmed.ncbi.nlm.nih.gov/24971054/ https://pubmed.ncbi.nlm.nih.gov/24971054/
- kemiller 5y agoIANANS but my understanding is that neurons/body mass is more indicative. Large animals have more neurons because large bodies need more.
- salty_biscuits 5y agoThey talk about the encephalization quotient, which is to the 2/3 power https://en.wikipedia.org/wiki/Encephalization_quotient https://en.wikipedia.org/wiki/Encephalization_quotient
- cloogshicer 5y agoYou probably already know this (since you wrote "silly thought"), but real-life neurons are ridiculously more complex than simulated "neurons" in an NN. So the analogy doesn't really hold.
- pishpash 5y agoThey're more complex in biological construction and in signaling mechanism, but no proof that they are more complex in function.
- mattkrause 5y agoAn individual biological neuron can compute a variety of functions, including max and xor, that a single perceptron can't (e.g., https://www.science.org/doi/10.1126/science.aax6239 https://www.science.org/doi/10.1126/science.aax6239 ). In general, one needs a fairly elaborate ANN to approximate the behavior of a single biological neuron. OTOH, a three-layer network is a universal function approximator and RNNs are universal dynamical systems approximators, so they are sort of trivially equivalent.
- kd5bjo 5y agoIs there a corresponding result that gives the number of examples needed to provide a sufficient training set for a given physical phenomenon? I’m imagining a high-dimensional equivalent of Nyquist’s sampling theorem. Coupled with this result, we’d then have a reasonable estimator of the network size required for particular tasks before even starting the data collection.
- pishpash 5y agoVC dimension?
- samwisedum 5y agoLet's add more nodes so we can overfit even better!
- VirusNewbie 5y agoSo, the smoother the function, the easier it is to approximate using SGD? Does that mean there's a relationship between training time and parameters and beyond a certain parameter count we can discover an equivalent approximation by trading one for the other?
- yalogin 5y agoCan someone ELI5 how one increases the size of an NN? If I take the handwritten digit classifier that people use as ML 101, is it just a matter of increasing the size of the hidden layers?
- malka 5y agoYes, or add more layers
- joshvm 5y agoEfficientNet is a nice simple example of this. It's family of networks with different sizes, controlled by a single scaling parameter. That parameter controls depth, width and resolution - see here for more details, the figure is easy to understand: https://paperswithcode.com/method/efficientnet https://paperswithcode.com/method/efficientnet
- teebs 5y agoYou can just do that by adding large hidden layers or more hidden layers, up to a point. But eventually the signal that's coming from the input data is so diluted through all the neurons and layers that your models stop performing better as you add more neurons. Many of the advances in NNs come from structuring the neurons in particular ways - for example, in computer vision, convolutional neural networks. These are kind of a small neural network that looks at each part of the image and gives an output - basically, shrinking and summarizing the image - which is then fed into another small neural network that shrinks & summarizes some more, and so on until you have only one result, like "is this a cat" or something like that. Transformers, which are mostly used for natural language processing, have small neural network layers that let the network figure out which other words in a text are relevant for understanding a given word (or, token, really). These help simplify the problem for the NN so it doesn't have to sort through all the data it has at once, which is a bottleneck on scaling NNs. Not sure that explains it like you're 5, but hopefully it addresses your question
- antishatter 5y agoMore great news from the university of Texas
- mensetmanusman 5y agoSize = N x D D is the dimensionality, and they give a picture example with D = X.pixels * Y.pixels How does D change when you introduce video? (Picture arrays) E.g. can a NN recognize something more by having access to an array of approximately the same image as it sweeps through space/time?
- viraptor 5y agoYou'd expect so, because there are already projects which do sub-pixel image recovery from video frame. So putting that before recognition should be doable.
- lnyan 5y agoReviews and authors' responses of this paper: https://openreview.net/forum?id=z71OSKqTFh7 https://openreview.net/forum?id=z71OSKqTFh7
- deleted 5y ago[deleted]
- dchftcs 5y agoThe result is mildly interesting but doesn't strike me as remarkable. We've always known that overparameterization with regularization can improve performance in certain classes of problems. The comparison with using n-order polynomial to fit n points is also non-sequitur. So there's a lower bound on the number of parameters required to produce a good interpolation of a broad class of "smooth" functions, and that's larger than the data size. Ok. I'm guessing one could find an even larger lower bound to approximate a more exotic class of functions that are still "smooth" in some intuitive sense, and it wouldn't make me any more excited. The main problem is, what does it say about how well a neural network can approximate specific types of functions, compared to anything else, with the same or more parameters, with the same huge amount of data, which has always been the real mystery here? Can we analytically define a class of functions that can be fit well by neural networks with n data points, using < parameters, than any other known method, and map these functions to real world applications? Or, in other words, given a class of functions representing general real world data sets that neural networks tend to do well on (dogs and cats), can we characterize a tractable algorithm to compute nd parameters needed from the n sample points where there's high probability that it could produce a good interpolation? If not, then this paper doesn't explain anything better for neural networks than for say kernel methods with polynomial kernels or manifold reconstruction using restricted classes of spline functions. The sensationalist headline, along with the "books need to be written" rhetoric, wants to make us think the result or the techniques it presented could get us closer to answering the above questions, but it seems to me there's zero truth in that.
- 555watch 5y agoMaybe someone that knows the topic well could elaborate a little bit on how do the authors arrive to their conclusion? From what I'm gathering, by Theorem 2 they show, that with n approaching infinity, the probability that the function $f$ exists approaches zero very quickly. I understand that, for this reason, they require that the variables $d$ and $k$ also approach infinity reasonably fast (or faster than $n$) in order to bound that probability with anything other than zero. We can already stop here and question, why does an upper bound on any similar probability interest us? If we want to show that the function $f$ exists with high probability, we should also consider lower bounds, not only the upper bounds as is done in the paper (clearly, I can bound any probability by 1 and would not be wrong). But even leaving this question aside and going back to Theorem 2, they essentially show that for any sample of size $n$, they can find (and overfit) a smooth function $f$, given a sufficiently large model space $d$ and $k$. Assume I launch such a model in production, and continue generating further observations $n$. It follows from the theorem 2 that $f$ will quickly become unsuitable and require retraining on a larger training space $d$ and $k$. However, from a statistical standing point, unless the data generating process is non-differentiable at every point, we should be able to assume that there exists N_epsilon, such, that for every n > n_epsilon, we should be able to find $f$ such that the errors would be controllably small (< epsilon) against the true data generating process f + sigma. So, beyond a certain $n$, further increasing of observations should not affect the initial fit of the model. This is not at all what follows from the Theorem 2, suggesting that any such $f$ is still fitting on the errors, not necessarily the true process. What am I missing (or assuming incorrectly)? Would be very interested to discuss this paper further!
- raymondh 5y ago> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. That should be √2 × radius. Looking out from the North Pole of hypersphere, almost all points lie near the equator, not the South Pole.