Computer scientists prove why bigger neural networks do better
quantamagazine.org
quantamagazine.org
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!
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).
Can you call this learning?
I also believe that this statement is weird. I have a very shallow knowledge of ML, but I can imagine that in a convolutional neural network a training sample interacts with lots of parameters. This 'one training sample <-> one parameter' correspondence seems wrong to me.
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.
https://en.wikipedia.org/wiki/List_of_animals_by_number_of_n...
An analogy: what's the difference between a supercomputer, and the same number of CPUs scattered across a few datacenters? It's that in a supercomputer, those CPUs are packed physically as close as possible with expensive interconnects to allow them to communicate as fast as possible. (For many applications, the supercomputer will finish long before the spread out nodes ever finish communicating and idling.) But you need to improve both or else your new super-fast CPUs will spend all their time waiting on Infiniband to chug through, or your fancy new Infiniband will be underutilized and you should've bought more CPUs.
Case in point: https://openai.com/blog/block-sparse-gpu-kernels/
Plenty of animals recognise themselves in the mirror, for instance.
That said even ants pass the test, i.e. they were recently(2015) tested.
But the whole thing can be characterized as: "Let me make up a random test, according to my personal opinion of what defines cognition and then see if a random animal I choose passes it".
Every couple of years we have requests of slews of psychology papers requested to be invalidated because they're unreproducible.
But of course! How do we know that humans are, indeed, the smartest? What if we've been failing every single test that mice have been throwing at us over the past millennia, and they wonder why we are so dumb?
(This is a reference to The Hitchhiker's Guide to the Galaxy in case you're wondering if I've gone mad. Not that one wouldn't presuppose the other :)
Dogs pass the scent-based mirror test for example, their eyes are just simply not the primary way of interacting with the world.
Dolphins and elephants are famous examples, most primates as well. Even many birds show levels of self awareness and theory of mind (they know the difference between what they know and what others know)
This means birds have to keep track of who can and can't see them cheat, who knows and who doesn't. There's even evidence that they rat each other out (2nd degree info) if they think there's a reward to be had. All of this requires immense intelligence, which happens to prove useful in other contexts.
There's also a bird species who does this with food caches. Easier to steal from others than to build their own so a plethora of deceptive tactics developed to ensure others can't see where you're storing those delicious nuts. Complete with fake caches, lying, and espionage.
[1] I learned about it in The Genius of Birds
https://www.labroots.com/trending/plants-and-animals/15629/s...
This is exactly the question the field is about, and I find it fascinating to read about
Most cats and dogs I've seen correctly recognise themselves in the mirror after the novelty of seeing one for the first time wears off.
Bigger animals may require more neurons to handle moving larger and/or more complicated muscle groups.
Interesting related point there is the encephalization quotient which is related to the predicted ratio of brain size to body mass. On the wikipedia page [0] they list the EQ for various animals. Humans are the highest but dolphins and ravens are not far behind.
https://www.newscientist.com/article/dn12301-man-with-tiny-b...
Exactly. Most of the newer research on this topic suggests that it's neural connection complexity, and specifically frontal lobe volume, rather than overall brain size that determines intelligence or brain power.
https://neuroscience.stanford.edu/news/ask-neuroscientist-do...
>Luckily, there is much more to a brain when you look at it under a microscope, and most neuroscientists now believe that the complexity of cellular and molecular organization of neural connections, or synapses, is what truly determines a brain’s computational capacity. This view is supported by findings that intelligence is more correlated with frontal lobe volume and volume of gray matter, which is dense in neural cell bodies and synapses, than sheer brain size. Other research comparing proteins at synapses between different species suggests that what makes up synapses at the molecular level has had a huge impact on intelligence throughout evolutionary history. So, although having a big brain is somewhat predictive of having big smarts, intelligence probably depends much more on how efficiently different parts of your brain communicate with each other.
This thread has links to a copy, plus a bunch of related studies in humans and animals. https://twitter.com/markdhumphries/status/107105276276554137...
The whole nail part is basically a single sentence in the paper.
For example, decorticate rats are unable to escape narrow alleyways because they can not turn around due to their tonsils touching the walls and them being unable to ignore that feeling.
Another example is that they take a few seconds vs (!) 5 minutes to groom themselves on average.
FWIW, the nail thing is a bit of a neuroscience meme. I heard--and stole--this quip from multiple people in several different situations. There's also a really striking figure in that chapter (p. 7 or 8).
No argument that the rats' behaviors are affected. I suppose whether you find the slowness of their grooming expected (because of brain damage) or impressive (because it happens at all) is a matter of taste. Glass^W Skull half-empty or half-full, if you will.
They are not slow, they just stop grooming themselves well enough.
I don't think he released them into the wild (would be a tough experiment with 80s tech), but there are a bunch of studies of their interactions with conspecifics. They can mate[0], though less successfully than controls, but playfight a bit better than they do[1].
[0] https://psycnet.apa.org/record/1983-29790-001 [1] https://doi.org/10.1159/000114124
> “If something happens very slowly over quite some time, maybe over decades, the different parts of the brain take up functions that would normally be done by the part that is pushed to the side,” adds Muenke, who was not involved in the case.
OTOH, a three-layer network is a universal function approximator and RNNs are universal dynamical systems approximators, so they are sort of trivially equivalent.
I think we read too much into the complexity of biological neurons. Remember they need to do much more than compute signals. They need to self assemble, self replicate and pass through various stages of growth. They need to function for 80-100 years. Many of those neurons and synapses exist only for redundancy and other biological constraints.
A digital neuron doesn't care about its physical substrate and can be millions of times faster. They can be copied identically for no cost and cheaply fine-tuned for new tasks. Their architecture and data can evolve much faster than ours, and the physical implementation can remain the same during this process.
https://www.scientificamerican.com/article/elephants-never-f...
If so, then your memory is unusually good. I know that this is well beyond my capabilities. Nor do I have the ability to visit a place that I lived 40 years earlier and find my way around.
I recently found myself in a hotel that I stayed in as a 7-8 year old in the 80s for a particularly memorable vacation with my extended family. It was funny that I still remembered the I unusual aspects of the layout and could spot many of the changes that had been made over the years.
But if you asked me to describe someone I met for a few days in a business context in 2020, I’d have a hard time remembering detail.
There also, AFAIK, isn’t evidence they remember _all_ other elephants they’ve shared time with for at least few weeks (I certainly do not rule that out, either, given the low number they likely will meet in their life)
Yeah? Maybe not if they were a kid 20 years ago or their appearance had otherwise changed significantly, but otherwise I don't see why not.
It's like how just getting a bigger faster computer can help with your problem, but its less powerful than a new more efficient algorithm on the same computer.
Also, you're working under the assumption that they are equivalent between mammals which as far as we can tell it's not the case (https://www.medicalnewstoday.com/articles/why-are-human-neur...).
So my guess is that the comparison is much more complex than just number of neurons.
[0]: https://en.wikipedia.org/wiki/Brain_size#:~:text=In%20men%20....
We have very good problem solving ability of course, but a superpowered ability to ask others how they solved the problem. If we wanted to somehow define a kind of 'brain horsepower' type intelligence, it seems to me that the former is closer to it than the latter, and it doesn't seem obvious to me that humans would necessarily take the top spot. Or that there's a reasonable/ethical way to test it -- let's take a human, elephant, crow, and dolphin, raise them in total isolation from the any community to get a measure of their untrained intelligence... we might get some interesting results on intelligence, but mostly we will learn something about ballistics as some ethics review board launches us unto the Sun.
I suspect the question really doesn't make sense if that is true.
We just have this bias/mind projection fallacy that intelligence is a general physical property of the brain that can be measured. I just suspect this is not true.
Like athletic ability doesn't generalize well. Of course, someone not athletic at all is never going to be a great athlete in anything but it makes no sense to compare Lance Armstrong to Patrick Mahomes in some general athletic context. Putting a number on a general athletic ability index between the two would just be total nonsense.
I imagine it's 100% dependent on the cardinal rule of neural networks:
"Choice of training data is 10 times more important than the actual model."
What we have over elephants are opposable thumbs, excellent eyes, and vocal cords. And crucially, we're generally speaking pretty slow, weak and useless.
Except for our elaborate methods of I/O.
Our entire success is based on a feedback loop. "If human uses their IO this way, human will get more food."
Thus, we become ever more sophisticated at this. We are nothing if not a vehicle for using our high dexterity, low gross force, opposable thumbs in inventive ways to get food.
Plus, we have a biological imperative to pass these techniques on as knowledge.
A baby elephant can probably feed itself by eating green stuff at 1 year old (I know nothing about elephants).
A human child realistically cannot independently scrounge up enough solid food to sustain themselves, until they're what, twelve? Twenty-two? Certainly no younger than eight.
We have, almost certainly, the most useless progeny in the animal kingdom.
Hence we invest an enormous amount of time and energy in education to make them able to feed themselves.
So the tl;dr is
1) Human brains are pretty similar to the animal kingdom's. 2) Human opposable thumbs are world class. Pretty close to as good as it gets. Sight is also top notch, many animals have useless eyeballs. 3) Most human food is obtained by doing creative things with thumbs. This is very complex, and takes a lot of practice. 4) Human birth the most useless children in the entire animal kingdom. These children take decades to fully grow, hence we invest an enormous amount of time educating them in opposable thumbs. 5) Over time our education system gets better and better, and our list of clever things we can do with opposable thumbs get longer and longer.
Essentially what we have over the other animals isn't neurons.
What we have over the other animals is a data collection/cleaning/utilization cycle.
Elephants have bodies built like a tank (and used as such by Hannibal), but humans have better I/O ports.
{reading, writing, listening, speaking, singing, typing, doing, going}
Without opposable thumbs, an elephant is probably quite envious of human writing & typing. Let's use the privilege wisely to encourage one another, teach and learn from each other, from Donald Tusk, and give a helping hand.
I did, and still do, believe this to be true. Would love to befriend a bird
What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
[1] https://en.wikipedia.org/wiki/Curse_of_dimensionality
[2] http://kops.uni-konstanz.de/bitstream/handle/123456789/5715/...
Even though almost every all pairs of points are almost a full diameter away from each other, they are also almost all almost orthogonal (i.e. the angle they make with the center of the sphere is very close to 90 degrees).
The M-Tree is one of my favorite indexes. It works with data that's embedded in infinite dimensional spaces (sometimes; it's bumping up against an impossibility result that's sketched in a sibling comment).
What I have just thought about though, is what points would be exactly diameter/2 distance away from that point? If you have a circle, you might think it would be the points that form a 90 degree triangle, but that is not the case, those points would be sqrt(2)*radius distance away.
So while it is obvious to me that it is not diameter/2, it is not obvious to me why it would be diameter either, or how larger n converges it closer to the diameter or some other fixed number.
x1^2 + x2^2 + … + xn^2 = 1.
D = (x1-1)^2 + x2^2 + … + xn^2
x1^2 = 1 - x2^2 - x3^2 - … - xn^2
But we can be more mathematical about it. Our (very reasonable) assumption is that the volume of a n-dimensional disk is proportional to the nth power of its radius. The third equation shows that x1 is going to be big (meaning the distance to the chosen point above is not so close to the diameter) if a corresponding[1] point on the n-disk is close to the middle. But the distance from the origin, R, of a random point in the n-disk is distributed with pdf proportional to p(r) = r^n for r in [0,1]. So the cdf is just r^(n+1) and E[x1^2] = 1 - E[R] = 1 - (n+1)/(n+2), which tends to 0 as n grows.
Therefore we get E[D] = E[(1-x1)^2] + 1 - E[x1^2] which tends to 2 as n grows large.
[1] the correspondence is that if I give you a point on a disk, you can turn it into a point on a sphere by flipping a coin to decide if it goes in the upper or lower hemisphere and then projecting up or down perpendicular to the disk from the point onto the sphere. But thinking a little more, I’m not sure this preserves the metric as it favours points on the sphere that correspond to the middle parts of the disk. So I think the actual expected value of x1 should be smaller.
D = (x₁-1)² + (x₂² + … + xₙ²)
Since we know that ∑xₙ²=1, and that x₁² is almost 0, then we also know that ∑xₙ² - x₁² is almost 1, which is the 2nd half of the above expression for D. So the average distance converges to "almost 1 + almost 1", which "almost 2", which is the diameter.
So exactly 1 gives a distance of 1, but almost 1 + almost 1 gives a distance of almost square root of 2.
I'm not sure it will. x1 is chosen randomly in the -1..1 interval. I dont see how the million other dimensions would force it to stick to 0. Those N other dimensions shrink the stddev(xi) by sqrt(N), though.
D^2 = (1 - x1)^2 + (1 - x1^2) = 2 - 2x1
We know that x1 is 0 on average, but its distribution is restricted by the fact that we choose a random point on the n-sphere. So what's the probability of that random point falling into a thin stripe where abs(x1) < eps? And how does this probability behave for large n?
This eps-stripe is basically the (n-1)-sphere of width eps, so the stripe's area A(n)=eps•S(n-1), and so our probability p=eps•S(n-1)/S(n).
The "magical" property of n-spheres is that their area grows at first, reaches maximum in 7 dimensions and then falls off rapidly to zero. Using formulas from wikipedia, I get: p = eps•(n/4)^(n/2) for large n.
In other words, the distribution of x1 approaches the look of the delta function at the n^n pace and for all practical matters, D=sqrt(2) with high precision for n > 10.
Where
On a high dimensional sphere they should generally be close to square root of 2 radius away from each other.
Consider the origin (0,0,0, …) to a random point on the sphere (~0, ~0, ~0, …). So Distance from origin = square root of ((~0-0)^2 + (~0-0)^2 + (~0-0)^2 + … ), which sums to 1 by definition of the unit high dimensional sphere.
Then plug in 1 vs 0 in the first place because we care about (1,0,0,0 …) and you get the correct answer = square root of ((~0-1)^2 + (~0-0)^2 + (~0-0)^2 + … ) ~= square root of 2.
Edited to fix typo and add clarity.
d(x,y) = 0 if x == y; 1 otherwise
Then all points are distance one apart. It's been proven that, as dimensionality increases, normal euclidian distance over uniform point clouds rapidly converges to have the same behavior as the equality metric.
The proof relies on the information gained by performing pairwise distance calculations.
In the example distance function I gave, there is zero information gained if you plug in two points that are known to be non-equal.
The information gained from evaluating the Euclidian distance function converges to zero as the dimensionality of the data set increases.
(Note: This does not hold for low dimensional data that's been embedded in a higher dimensional space.)
Edit: Misread your comment. Yes, everything ends up being the same distance apart. More precisely, the ratio of mean distance / stddev distance tends to infinity. The intrinsic dimensionality of the data is monotonic w.r.t. that ratio.
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.
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.
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!
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.
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.
Not sure that explains it like you're 5, but hopefully it addresses your question
That should be √2 × radius.
Looking out from the North Pole of hypersphere, almost all points lie near the equator, not the South Pole.
My biggest blocker is the "statistics" part of M/L, knowing what algorithms to choose for various cases.
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?
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.