4 ms·
What they are doing is essentially encoding the binary circuit of the xorshift128 PRNG as a neutal network. The fact that you can encode abritrary binary circui
by _hl_ 5y ago
What they are doing is essentially encoding the binary circuit of the xorshift128 PRNG as a neutal network. The fact that you can encode abritrary binary circuits as neural networks is well-known, so it's not surprising that it is possible to do this.
The interesting and perhaps surprising result is the demonstration that it is possible to train this network using standard gradient methods, when choosing the proper loss function for the problem and designing the network with the required domain-knowledge of the algorithm it is supposed to model. In other words, this can be seen as an example of how well-educated network design and choice of loss function massively impacts the performance of your fancy ML model.
For more "real-world" problems, it is often very difficult to come up with a network design that encodes the implicit constraints of the problem, mostly because these constraints are not even known (that's why we use ML!), but results like the recent AlphaFold show that even for these problems, thoughtful design of the model architecture goes a very long way.
- SeanLuke 5y ago> What they are doing is essentially encoding the binary circuit of the xorshift128 PRNG as a neutal network. The fact that you can encode abritrary binary circuits as neural networks is well-known, so it's not surprising that it is possible to do this. Mcullough-Pitts aside, I think this is unfair. What's interesting to me is that they can predict a recurrent algorithm with internal state using with a trivial NON-recurrent feedforward network without any internal state.
- gus_massa 5y agoThey can see the last 4 results, not only the last result. That's somewhat equivalent of partially seeing the secret internal state. As a bad metaphor: Let's suppose that you enter a lifter and a NN without internal state must predict which button you will press, but now consider the case where the NN can see a video of everything you have done during the last year. Do you think it's possible?
- _hl_ 5y ago> That's somewhat equivalent of partially seeing the secret internal state Not just partially, xorshift128 is designed such that the output depends only on the last 4 results. So this is "just" learning the output function of xorshift as a neural network.
- SeanLuke 5y agoPerhaps you might consider how big that output function ideally is, then compare to the capacity of the neural network they used and the number of samples provided.
- _hl_ 5y agoMy reading of it is that it's essentially one-to-one (up to minor constant factors), they took the binary circuit for xorshift128 and replace the xor gates by functionally equivalent NN blocks, and then trained the weights.
- SeanLuke 5y agoThat's only ~365 values. XORshift32 has a period of 2^32-1, a good portion of that (I'd imagine) unique. If XORshift had really good randomness properties, at the extreme we'd expect that the NN would have to special case all of them. What this implies is that XORshift has easily cracked, nonrandom, repeatable patterns (which we suspect of course since it fails certain tests) and that the NN has identified them.
- rurban 5y agoWe knew that before the two ML attempts. You just need to look at the source. There are several other trivial PRNG's with the exact same properties. Never use a trivial PRNG for security or seeding.
- jameshart 5y agoIt looks like this specific algorithm can easily be deterministically reversed - the XORs and bitwise shifts mean that, given four output numbers, you can completely determine what state it was in before the numbers were generated - and, in fact, that there is probably a simple series of bit shifts and XORs you can perform on the last four outputs that produces the next number. Bit shifts and XORs are very much the kind of pattern neural networks should excel at learning - they mean that each output bit is a simple linear function of the input bits. Actually doing it is still a good demonstration! But the fact that the function in question is used as a PRNG doesn’t imply that other PRNGs would be susceptible to a similar approach.
- 317070 5y agoXOR is not linear in the inputs. I mention this, because Minsky's paper used that fact to show that perceptrons could never work as AI. This pretty much started the first AI winter in 1973. It's an interesting story: https://towardsdatascience.com/history-of-the-first-ai-winter-6f8c2186f80b https://towardsdatascience.com/history-of-the-first-ai-winte...
- ajb 5y agoLinearity is actually relative to the algebra you are using. Xor is not linear in real arithmetic but it is in GF(2). This is useful because some of the algorithms work across many algebras, and are useful for different problems. Eg, the tropical algebra. But you are quite correct about the AI winter.
- cookiengineer 5y agoThis whole project reads as a beginner's guide to ML and what it can do. I mean, it's nice and all but at some point I would've expected at least a mention that this all was solvable with a quantized neural network with low bit precision as well. Most of the article was about LSTMs and the recurrent design of those is just a very inefficient way to solve the problem at hand. I would've expected an LSTM try for something like a seed based randomizer like MT19937 and that the unfolding layers are trained on the seed itself with the idea that they learn how to predict the seed's state for the next iteration. Something like this would be really important research, especially in times where time based one time passwords are used everywhere, and their cryptographic security of how seeds are generated is important.
- sillysaurusx 5y ago> I mean, it's nice and all but at some point I would've expected at least a mention that this all was solvable with a quantized neural network with low bit precision as well. This doesn't matter, so I'm not sure why you were expecting it. I'm struggling to be diplomatic, so I'll leave it at that.
- nsonha 5y agothe rest of their comment sounds insightful
- More-nitors 5y agohm can this be applied to AES?
- bawolff 5y agoI'm pretty sure it can't
- downandout 5y agoSo would this model be able to predict any imperfect PRNG with some degree of accuracy, or just xorshift128? For the purposes I'm thinking, even 1% accuracy above purely random would suffice.
- IAmGraydon 5y agoFinancial market prediction is where my mind went too.
- danbmil99 5y agoGood luck with that. Financial markets are not pRNG's -- they are more like an adversary you are playing poker with. Think game theory, rather than pattern matching.
- downandout 5y agoI was actually considering something known to be a relatively weak pRNG....card shuffling in a casino setting.
- tatersolid 5y agoManual or modern automated shuffles in a casino are NOT weak. Casino owners and employees aren’t dumb. They actually understand the math involved quite well.
- downandout 5y agoCasino owners and employees aren’t dumb Having met a few casino owners, and many more game supervisors actually charged with understanding the math of the games to avoid exploitation, I can tell you this is patently false.