5 ms·

I tend to think this is a result of classification's information density being too low. You can 'learn' a classification problem in the same way with a hash fun

I tend to think this is a result of classification's information density being too low. You can 'learn' a classification problem in the same way with a hash function: take a hash of each image, and memorize the hash and label. Then you only need to 'learn' a very tiny amount of data relative to the size of the dataset to get zero loss. A series of random projections can also function as a crude hash function, and this is likely how NN memorization works. Generative models, on the other hand, don't allow this kind of data reduction trick. If you need to predict (say) every sample of an audio stream conditioned on the previous audio samples, you really do need to memorize the whole dataset (not just a hash of each item) to get to zero loss, because the information density of the output is still very high. And then you've got BERT, which is basically a generative model for language, used for downstream tasks. The information-dense task probably helps with the memorization 'problem' so good features are learned that adapt nicely to other tasks. (and as others have said, memorization may not be a problem in practice. Sometimes it's actually the right thing to do.)

DavidSJ 6y ago
The thing is, despite the fact that deep neural networks can effectively learn the hash function you describe (i.e. they have the capacity to do so, and they will do so if "forced" to with random labels), they "prefer" not to. They learn a generalizable pattern in the data. That's the mystery this paper points to.
- sdenton4 6y ago
  Yeah, I've also done a bunch of work on hard classification problems where generalization pretty much fails. I think they're /probably/ doing the right thing in the infinite training data regime. And they're definitely doing interesting things in the generative case. But ultimately they look for a convenient 'nearby' solution: that's the nature of stochastic gradient descent. If you have two solutions and one of them is the hash function, it would be helpful to /know/ that the hash function is harder to get to than the 'correct' solution.
  - anonymousDan 6y ago
    But isn't that shown by the fact it takes training longer to converge in their experiments with random labels vs real labels?
    - sdenton4 6y ago
      Yeah, not a bad idea; for any given problem, just scramble the labels and compare training time... For my pet problem, there's quite different performance across classes. It would be tougher to do the comparison for a subset of classes, but could still probably design some kind of experiment.
- joe_the_user 6y ago
  The paper says that: "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" What is a generalization of a random labeling? Does the network become psychic? Is this saying "garbage works fine by these measures"?
  - visarga 6y ago
    The network learns how to map data into an intermediate representation, then learns a hash output for each of these intermediate values. So it learns two things compared to when the intermediate values correspond to the task.
  - DavidSJ 6y ago
    Random labeling can’t generalize. But in the usual case, the labels are nonrandom and the learned map generalizes.
- joe_the_user 6y ago
  That's the mystery this paper points to I'm still honestly confused here. Yes, the success of neural networks generally shows they more than memorize. Some of the experiments here show they can just memorize too. I guess some describe something in-between. But all this seems obvious. Is there something that's being quantified here?
  - DavidSJ 6y ago
    You can measure the generalization gap: the difference between training and test performance. With good generalization that gap will be small. When fitting random labels the gap will be large. Classical statistical learning theory (from Vapnik and Chervonenkis, among others), predicts that low capacity models will generalize (have small generalization gaps). It makes no promises for large capacity models, i.e. those which can fit random labels. Yet here we are.
rubatuga 6y ago
But BERT isn't a generative model? Unless you mean it's trained similar to a generative model by predicting the missing tokens? Also an interesting paper about hybrid energy based models: https://arxiv.org/pdf/1912.03263.pdf https://arxiv.org/pdf/1912.03263.pdf It's possible to have a model be both a classifier + generative, and the performance is comparable (although lower) to the SOTA of single-purpose models.
medlyyy 6y ago
Why exactly is it a problem that powerful models can memorise training data with random labels, if they generalise well on non-memorisation problems? I also think that a lot of progress is being made seemingly in parallel on this "understanding NN [generalisation]" topic, and the different threads don't necessarily seem to be aware of each other. This article seems to have failed to mention most of this recent progress. Possibly this is an artifact of the time it takes to produce and publish a completed article, but it presents a picture that we are more clueless than we actually are. The most promising, IMO, is outlined in these blog posts: https://towardsdatascience.com/neural-networks-are-fundamentally-bayesian-bee9a172fad8 https://towardsdatascience.com/neural-networks-are-fundament... and https://towardsdatascience.com/deep-neural-networks-are-biased-at-initialisation-towards-simple-functions-a63487edcb99 https://towardsdatascience.com/deep-neural-networks-are-bias... which summarise 3 research papers. The basic idea is that because NN outputs are usually thresholded to produce a prediction/classification, there is not always a change in the output if a parameter changes. This gives space for there to be a non-uniform distribution over output functions, if weights are initialised randomly. The authors investigate this empirically (with some theoretical justification) and find that this bias is toward "simple" functions, which often generalise well, due to "simple" properties mostly being what we care about in real data. Then generalisation can be explained by SGD simply being more likely to find parameters which cause the NN to express a function that is simpler, out of all functions that perfectly match the training data. There is also some interesting investigations into infinite-width limits - the most well known being the result that NNs are equivalent to Gaussian Processes at initialisation, then Neural Tangent Kernels [1] showing a way to view them through the lens of kernel methods throughout training as well. But then there is Feature Learning in Infinite-Width Neural Networks [2] which seems to be at odds with the kernel approach (due to kernels not learning features) - this paper provides a different method for parametrisation to admit feature learning. So there is progress both in understanding generalisation and understanding when feature learning does & does not occur. (And this is hardly a comprehensive sampling.) [1]: https://arxiv.org/abs/1806.07572 https://arxiv.org/abs/1806.07572 [2]: https://arxiv.org/abs/2011.14522 https://arxiv.org/abs/2011.14522
- sdenton4 6y ago
  I've recently been doing some work on a model that mixes a big convolutional model with a second piece that we can actually analyze with the signal processing toolkit. What I see in the signal-processing side was a mix of really interesting good behavior (including one cool trick I hadn't seen before), right along side a bunch of obviously-dumb pathological behavior. (Basically, glaring discontinuities which induce the model to introduce /other/ discontinuities to course-correct... with really bad impacts on output quality.) I found some nice tweaks that get rid of /most/ of the pathological behavior in the sig-proc side, and produce some really nice results. But for the main black-box network? No such visibility. It is undoubtedly doing all kinds of stupid shit that I have no insight into. And I would /love/ to be able to sort it out and get rid of the dumb parts, because I a) want tiny models that run hella fast on slow-ass phones, and b) would love to eliminate sources of spurious correlations to provide better predictions. Getting rid of the dumb parts means more compute to do the smart things. The high-level theory answers maaaybe tell me about convergence but not whether the NN converges to anything reasonable. Giant models provide a huge amount of flexibility, which help the model find answers, but the answers may not be any good, and we really don't have robust ways to know. (eg, aggregates over big eval datasets may tell me something could be better, but not what or why.)

DavidSJ 6y ago

The thing is, despite the fact that deep neural networks can effectively learn the hash function you describe (i.e. they have the capacity to do so, and they will do so if "forced" to with random labels), they "prefer" not to. They learn a generalizable pattern in the data. That's the mystery this paper points to.

sdenton4 6y ago
Yeah, I've also done a bunch of work on hard classification problems where generalization pretty much fails. I think they're /probably/ doing the right thing in the infinite training data regime. And they're definitely doing interesting things in the generative case. But ultimately they look for a convenient 'nearby' solution: that's the nature of stochastic gradient descent. If you have two solutions and one of them is the hash function, it would be helpful to /know/ that the hash function is harder to get to than the 'correct' solution.
- anonymousDan 6y ago
  But isn't that shown by the fact it takes training longer to converge in their experiments with random labels vs real labels?
  - sdenton4 6y ago
    Yeah, not a bad idea; for any given problem, just scramble the labels and compare training time... For my pet problem, there's quite different performance across classes. It would be tougher to do the comparison for a subset of classes, but could still probably design some kind of experiment.
joe_the_user 6y ago
The paper says that: "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" What is a generalization of a random labeling? Does the network become psychic? Is this saying "garbage works fine by these measures"?
- visarga 6y ago
  The network learns how to map data into an intermediate representation, then learns a hash output for each of these intermediate values. So it learns two things compared to when the intermediate values correspond to the task.
- DavidSJ 6y ago
  Random labeling can’t generalize. But in the usual case, the labels are nonrandom and the learned map generalizes.
joe_the_user 6y ago
That's the mystery this paper points to I'm still honestly confused here. Yes, the success of neural networks generally shows they more than memorize. Some of the experiments here show they can just memorize too. I guess some describe something in-between. But all this seems obvious. Is there something that's being quantified here?
- DavidSJ 6y ago
  You can measure the generalization gap: the difference between training and test performance. With good generalization that gap will be small. When fitting random labels the gap will be large. Classical statistical learning theory (from Vapnik and Chervonenkis, among others), predicts that low capacity models will generalize (have small generalization gaps). It makes no promises for large capacity models, i.e. those which can fit random labels. Yet here we are.

rubatuga 6y ago

But BERT isn't a generative model? Unless you mean it's trained similar to a generative model by predicting the missing tokens? Also an interesting paper about hybrid energy based models: https://arxiv.org/pdf/1912.03263.pdf https://arxiv.org/pdf/1912.03263.pdf It's possible to have a model be both a classifier + generative, and the performance is comparable (although lower) to the SOTA of single-purpose models.

medlyyy 6y ago

Why exactly is it a problem that powerful models can memorise training data with random labels, if they generalise well on non-memorisation problems? I also think that a lot of progress is being made seemingly in parallel on this "understanding NN [generalisation]" topic, and the different threads don't necessarily seem to be aware of each other. This article seems to have failed to mention most of this recent progress. Possibly this is an artifact of the time it takes to produce and publish a completed article, but it presents a picture that we are more clueless than we actually are. The most promising, IMO, is outlined in these blog posts: https://towardsdatascience.com/neural-networks-are-fundamentally-bayesian-bee9a172fad8 https://towardsdatascience.com/neural-networks-are-fundament... and https://towardsdatascience.com/deep-neural-networks-are-biased-at-initialisation-towards-simple-functions-a63487edcb99 https://towardsdatascience.com/deep-neural-networks-are-bias... which summarise 3 research papers. The basic idea is that because NN outputs are usually thresholded to produce a prediction/classification, there is not always a change in the output if a parameter changes. This gives space for there to be a non-uniform distribution over output functions, if weights are initialised randomly. The authors investigate this empirically (with some theoretical justification) and find that this bias is toward "simple" functions, which often generalise well, due to "simple" properties mostly being what we care about in real data. Then generalisation can be explained by SGD simply being more likely to find parameters which cause the NN to express a function that is simpler, out of all functions that perfectly match the training data. There is also some interesting investigations into infinite-width limits - the most well known being the result that NNs are equivalent to Gaussian Processes at initialisation, then Neural Tangent Kernels [1] showing a way to view them through the lens of kernel methods throughout training as well. But then there is Feature Learning in Infinite-Width Neural Networks [2] which seems to be at odds with the kernel approach (due to kernels not learning features) - this paper provides a different method for parametrisation to admit feature learning. So there is progress both in understanding generalisation and understanding when feature learning does & does not occur. (And this is hardly a comprehensive sampling.) [1]: https://arxiv.org/abs/1806.07572 https://arxiv.org/abs/1806.07572 [2]: https://arxiv.org/abs/2011.14522 https://arxiv.org/abs/2011.14522

sdenton4 6y ago
I've recently been doing some work on a model that mixes a big convolutional model with a second piece that we can actually analyze with the signal processing toolkit. What I see in the signal-processing side was a mix of really interesting good behavior (including one cool trick I hadn't seen before), right along side a bunch of obviously-dumb pathological behavior. (Basically, glaring discontinuities which induce the model to introduce /other/ discontinuities to course-correct... with really bad impacts on output quality.) I found some nice tweaks that get rid of /most/ of the pathological behavior in the sig-proc side, and produce some really nice results. But for the main black-box network? No such visibility. It is undoubtedly doing all kinds of stupid shit that I have no insight into. And I would /love/ to be able to sort it out and get rid of the dumb parts, because I a) want tiny models that run hella fast on slow-ass phones, and b) would love to eliminate sources of spurious correlations to provide better predictions. Getting rid of the dumb parts means more compute to do the smart things. The high-level theory answers maaaybe tell me about convergence but not whether the NN converges to anything reasonable. Giant models provide a huge amount of flexibility, which help the model find answers, but the answers may not be any good, and we really don't have robust ways to know. (eg, aggregates over big eval datasets may tell me something could be better, but not what or why.)