Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An overview of the theory of overparameterized machine learning

arxiv.org

Post reply on HN
Print view View original

51–58 of 58 posts

Re: An overview of the theory of overparameterized machine learning

#51

Post by zibzab »

sdenton4 wrote: post #18
quocanh wrote: post #17

Earlier quoted context omitted.

When you say hash function, do you mean a cryptographic hash function? How on earth could the performance of that be anywhere near the simplest probabilistic algorithm on unseen examples?

No, nothing cryptographic here. All I'm saying is that you can memorize the dataset by extracting a small fingerprint of each training example and associating it with an output label: ie, learn by lookup table. Then you don't need to memorize the whole training set, you just need to find/learn the fingerprinting function. With no augmentation, you might as well use MD5... With augmentation, you do need to do some act…

Fuzzy hashing is a thing and may actually use cryptographic hashing internally.

See for example recent work on hashing for malware detection.

Re: An overview of the theory of overparameterized machine learning

#52

Post by derbOac »

yldedly wrote: post #26
derbOac wrote: post #24

I have to reread it but the model misspecification interpretation (that highly overparameterized models exhibit DD because they reduce misspecification error) is the only thing I've read in this area that makes some sense to me theoretically. I think DD is a huge issue for a number of fields and is really underappreciated a lot. Without meaning to sound disrespectful, much of this literature seems a little superficia…

DD disappears when doing Bayesian model averaging: https://arxiv.org/pdf/2002.08791.pdf It seems DD is a phenomenon specific to point estimates. >overfitting problem is really in terms of model flexibility versus data complexity, and not necessarily in terms of number of parameters per se versus sample size Yep, well put.

Thanks for the link! I hadn't thought about model averaging in this context but definitely bears on how to interpret this stuff. Interesting to think about too re: connections with model misspecification.

Re: An overview of the theory of overparameterized machine learning

#53

Post by quocanh »

sdenton4 wrote: post #18
quocanh wrote: post #17

Earlier quoted context omitted.

When you say hash function, do you mean a cryptographic hash function? How on earth could the performance of that be anywhere near the simplest probabilistic algorithm on unseen examples?

No, nothing cryptographic here. All I'm saying is that you can memorize the dataset by extracting a small fingerprint of each training example and associating it with an output label: ie, learn by lookup table. Then you don't need to memorize the whole training set, you just need to find/learn the fingerprinting function. With no augmentation, you might as well use MD5... With augmentation, you do need to do some act…

Err.. hash functions like MD5 and SHA256 are "cryptographic". That just means one with a random distribution of outputs as opposed to maybe Apple's "neural" hash function which has outputs that do the "augmentation invariant projection" you speak of.

What I'm trying to say is that neural networks are "universal approximators of continuous real functions". You can think of them as finding the curve of a function which matches the data to an expected and they get their predictive power by matching the underlying "function" of the problem.

Applying a cryptographic hash function is like completely scrambling the underlying function. The only way for a neural network to match it is if it was somehow a universal approximator of a discontinuous real function. You can either do that by getting into unexplored chaos theory or making a gigantic lookup table for every single possible bit combination. The former no human being knows how to do, and the latter is impossible for even a 64 bit combination (nevermind an entire image, audio clip, or video).

Re: An overview of the theory of overparameterized machine learning

#54

Post by sdenton4 »

quocanh wrote: post #53
sdenton4 wrote: post #18

Earlier quoted context omitted.

No, nothing cryptographic here. All I'm saying is that you can memorize the dataset by extracting a small fingerprint of each training example and associating it with an output label: ie, learn by lookup table. Then you don't need to memorize the whole training set, you just need to find/learn the fingerprinting function. With no augmentation, you might as well use MD5... With augmentation, you do need to do some act…

Err.. hash functions like MD5 and SHA256 are "cryptographic". That just means one with a random distribution of outputs as opposed to maybe Apple's "neural" hash function which has outputs that do the "augmentation invariant projection" you speak of. What I'm trying to say is that neural networks are "universal approximators of continuous real functions". You can think of them as finding the curve of a function which…

>> making a gigantic lookup table for every single possible bit combination

You don't need this to achieve zero loss on the training set, though: You only need a lookup table for the images in the train set.

We know that neural networks can do something like this (learning the lookup table) because large networks can get to zero training loss on randomly assigned labels. (I linked the paper a bit further down in the thread.) This means there's some memorization capability in the architecture, even if it's a weird emulation of some memorization strategy that we would consider easy.

The actual mechanism here is probably closer to random projection + nearest neighbor; NNs are not obviously learning crypto functions. But they /are/ learning some kind of lookup mechanism. There's some indication (see Sara Hooker's work) that in practice they use a mixture of 'reasonable' strategies and memorization for long-tail training examples. We don't know /how much/ the leading networks trained on real labels rely on memorization because we don't have any real insight into the learned structures.

(as an aside, we train neural networks for discontinuous functions all the time: Classification is discontinuous, by the nature of the labels. We turn it into a continuous+trainable problem by choosing a probabilistic framing.)

Re: An overview of the theory of overparameterized machine learning

#55

Post by quocanh »

sdenton4 wrote: post #54
quocanh wrote: post #53

Earlier quoted context omitted.

Err.. hash functions like MD5 and SHA256 are "cryptographic". That just means one with a random distribution of outputs as opposed to maybe Apple's "neural" hash function which has outputs that do the "augmentation invariant projection" you speak of. What I'm trying to say is that neural networks are "universal approximators of continuous real functions". You can think of them as finding the curve of a function which…

>> making a gigantic lookup table for every single possible bit combination You don't need this to achieve zero loss on the training set, though: You only need a lookup table for the images in the train set. We know that neural networks can do something like this (learning the lookup table) because large networks can get to zero training loss on randomly assigned labels. (I linked the paper a bit further down in the…

Okay but that would only work for examples with which you already have. All interesting cases of neural networks are applying it to unseen inputs. How does your technique work with unseen inputs?

And while we interpret the result of a classification as a 1 or 0, the underlying result is a continuous probability. Even in reality, our training examples are labeled with too much confidence - some labels are vague even for humans. If it approximates a discontinuous function, then it does so by approximating a continuous function. You can read here for more information: https://www.sciencedirect.com/science/article/abs/pii/089360...

Re: An overview of the theory of overparameterized machine learning

#56

Post by sdenton4 »

quocanh wrote: post #55
sdenton4 wrote: post #54

Earlier quoted context omitted.

>> making a gigantic lookup table for every single possible bit combination You don't need this to achieve zero loss on the training set, though: You only need a lookup table for the images in the train set. We know that neural networks can do something like this (learning the lookup table) because large networks can get to zero training loss on randomly assigned labels. (I linked the paper a bit further down in the…

Okay but that would only work for examples with which you already have. All interesting cases of neural networks are applying it to unseen inputs. How does your technique work with unseen inputs? And while we interpret the result of a classification as a 1 or 0, the underlying result is a continuous probability. Even in reality, our training examples are labeled with too much confidence - some labels are vague even f…

Yes, this is the point: When we train a neural network, especially on a classification problem, it has multiple avenues to solve the problem. We know they are capable of ineffectual memorization, as well as some other less ridiculous things. When we train, it's not clear what mix we're getting of 'neural hashing' vs learning abstracted features.

My point up above is that classification problems are too weak, exactly because these kinds of shortcuts are readily available. The leading edge of ML research is over-focused on ImageNet classification in particular.

Re: An overview of the theory of overparameterized machine learning

#57

Post by quocanh »

sdenton4 wrote: post #56
quocanh wrote: post #55

Earlier quoted context omitted.

Okay but that would only work for examples with which you already have. All interesting cases of neural networks are applying it to unseen inputs. How does your technique work with unseen inputs? And while we interpret the result of a classification as a 1 or 0, the underlying result is a continuous probability. Even in reality, our training examples are labeled with too much confidence - some labels are vague even f…

Yes, this is the point: When we train a neural network, especially on a classification problem, it has multiple avenues to solve the problem. We know they are capable of ineffectual memorization, as well as some other less ridiculous things. When we train, it's not clear what mix we're getting of 'neural hashing' vs learning abstracted features. My point up above is that classification problems are too weak, exactly…

Ok so according to your theory, we could make this hypothesis: if we applied a neural network to an unseen example (for example, a validation dataset), then we would get accuracy that is equivalent to randomly picking a random label. Well surprise, surprise - we obviously don't get that. So there is clearly more going on than "neural hashing".

You're not answering this problem with unseen data so it's really hard for me to follow your reasoning here.

Re: An overview of the theory of overparameterized machine learning

#58

Post by r-zip »

sdenton4 wrote: post #33
r-zip wrote: post #21

Earlier quoted context omitted.

Has this been implemented? What kinds of hashing functions are you talking about? How would you guarantee the same hash for all the augmentations? It seems like the approach you describe just moves the complexity of the task solved by neural networks into the hashing function.

https://openreview.net/forum?id=Sy8gdB9xx "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."

What's your point? It's not clear at all from this post.
Post reply on HN