4 ms·

Actually RNNs/LSTMs are surprisingly good at memorizing in addition to generalization. Have a look at the famous blog post "The Unreasonable Effectiveness of Re

by ma2rten 10y ago

Actually RNNs/LSTMs are surprisingly good at memorizing in addition to generalization. Have a look at the famous blog post "The Unreasonable Effectiveness of Recurrent Neural Networks" [1] for instance and notice how many words it's able to generate from characters. However, your second point is valid. [1] http://karpathy.github.io/2015/05/21/rnn-effectiveness/ http://karpathy.github.io/2015/05/21/rnn-effectiveness/

gwern 10y ago
That's not 'surprisingly' good, that's effective only on a small corpus. You can see for yourself that if you try to feed it multiple corpuses with many vocabulary words or proper names, which a Markov chain wouldn't break a sweat on memorizing them all, the RNN has limited memorization ability and what tends to happen is that the less common ones get overwritten in favor of the general grammar of English and the vocabulary of the largest corpus: https://www.gwern.net/RNN%20metadata https://www.gwern.net/RNN%20metadata
- ma2rten 10y ago
  If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. This paper shows a large LSTM outperform n-gram models: "In this paper we have shown that RNN LMs can be trained on large amounts of data, and outperform competing models including carefully tuned N-grams. [...] Unlike previous work, we do not require to interpolate both the RNN LM and the N-gram, and the gains of doing so are rather marginal." https://arxiv.org/abs/1602.02410 https://arxiv.org/abs/1602.02410
  - gwern 10y ago
    > If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. No. Words have nothing to do with it. (An RNN over words would be useless for password guessing.) Anyway, your link doesn't demonstrate what you think it demonstrates. It's not on a password corpus but a much smaller natural language one, there is no attempt to equate runtime or model size, and the log-likelihood is an irrelevant measure of performance to passwords/s.
    - ma2rten 10y ago
      If words have nothing to do with it then I am not sure how your link shows that Markov Chains are better at memorizing, because a Markov Chain over characters would do a much worse job at generating coherent text. But I actually acknowledged your second point, so I never said that RNNs are useful for password guessing, unless maybe you have a very expensive hash function. However, they are good at memorizing sequences and log-likelihood is not an irrelevant measure of performance on passwords. It measures ability of the model to generalize to unseen data. In this case that means generating realistic passwords that are not in the training data. That is important because otherwise you might as well just use a dictionary attack.
      - gwern 10y ago
        > If words have nothing to do with it then I am not sure how your link shows that Markov Chains are better at memorizing, because a Markov Chain over characters would do a much worse job at generating coherent text. Over n-grams, it would not, as some of the responses to Karpathy's post noted, by posting Markov chain text which is of high quality. The char-RNN shows its greatest ability in matching syntax and recusive structures and in modeling the subtler aspects of English grammar, syntax, and semantics... which are all useless in password guessing. (For example, I could only tell the difference between the Markov chain and char-RNN C source, because the char-RNN understood the nesting of syntax, but not between the Shakespeare.) > However, they are good at memorizing sequences and log-likelihood is not an irrelevant measure of performance on passwords. It measures ability of the model to generalize to unseen data. No, it measures a particular loss function proportional to the mean log probability. In password guessing, the loss function is zero-one: you care only about guessing a single exactly right password. You get zero points for generating a realistic password which is one character off. Being able to model the distribution of 'e's slightly better is irrelevant compared to being able to memorize common birthday suffixes and guess a few more passwords per second. Having a better log likelihood on a natural English language corpus is measuring the wrong thing on the wrong data. > you might as well just use a dictionary attack. Exactly. This is how the best password crackers work: mix-and-match memorized literals, prefixes, and suffixes extracted from dumps of billions of passwords. A Markov chain is a souped-up dictionary attack demonstrating 'The unreasonable effectiveness of big data'.

by ma2rten 10y ago

gwern 10y ago

That's not 'surprisingly' good, that's effective only on a small corpus. You can see for yourself that if you try to feed it multiple corpuses with many vocabulary words or proper names, which a Markov chain wouldn't break a sweat on memorizing them all, the RNN has limited memorization ability and what tends to happen is that the less common ones get overwritten in favor of the general grammar of English and the vocabulary of the largest corpus: https://www.gwern.net/RNN%20metadata https://www.gwern.net/RNN%20metadata

ma2rten 10y ago
If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. This paper shows a large LSTM outperform n-gram models: "In this paper we have shown that RNN LMs can be trained on large amounts of data, and outperform competing models including carefully tuned N-grams. [...] Unlike previous work, we do not require to interpolate both the RNN LM and the N-gram, and the gains of doing so are rather marginal." https://arxiv.org/abs/1602.02410 https://arxiv.org/abs/1602.02410
- gwern 10y ago
  > If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. No. Words have nothing to do with it. (An RNN over words would be useless for password guessing.) Anyway, your link doesn't demonstrate what you think it demonstrates. It's not on a password corpus but a much smaller natural language one, there is no attempt to equate runtime or model size, and the log-likelihood is an irrelevant measure of performance to passwords/s.
  - ma2rten 10y ago
    If words have nothing to do with it then I am not sure how your link shows that Markov Chains are better at memorizing, because a Markov Chain over characters would do a much worse job at generating coherent text. But I actually acknowledged your second point, so I never said that RNNs are useful for password guessing, unless maybe you have a very expensive hash function. However, they are good at memorizing sequences and log-likelihood is not an irrelevant measure of performance on passwords. It measures ability of the model to generalize to unseen data. In this case that means generating realistic passwords that are not in the training data. That is important because otherwise you might as well just use a dictionary attack.
    - gwern 10y ago
      > If words have nothing to do with it then I am not sure how your link shows that Markov Chains are better at memorizing, because a Markov Chain over characters would do a much worse job at generating coherent text. Over n-grams, it would not, as some of the responses to Karpathy's post noted, by posting Markov chain text which is of high quality. The char-RNN shows its greatest ability in matching syntax and recusive structures and in modeling the subtler aspects of English grammar, syntax, and semantics... which are all useless in password guessing. (For example, I could only tell the difference between the Markov chain and char-RNN C source, because the char-RNN understood the nesting of syntax, but not between the Shakespeare.) > However, they are good at memorizing sequences and log-likelihood is not an irrelevant measure of performance on passwords. It measures ability of the model to generalize to unseen data. No, it measures a particular loss function proportional to the mean log probability. In password guessing, the loss function is zero-one: you care only about guessing a single exactly right password. You get zero points for generating a realistic password which is one character off. Being able to model the distribution of 'e's slightly better is irrelevant compared to being able to memorize common birthday suffixes and guess a few more passwords per second. Having a better log likelihood on a natural English language corpus is measuring the wrong thing on the wrong data. > you might as well just use a dictionary attack. Exactly. This is how the best password crackers work: mix-and-match memorized literals, prefixes, and suffixes extracted from dumps of billions of passwords. A Markov chain is a souped-up dictionary attack demonstrating 'The unreasonable effectiveness of big data'.