5 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 circ

> 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 ago
They 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 ago
    Perhaps 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 ago
      My 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 ago
  That'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 ago
    We 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 ago
It 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 ago
  XOR 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 ago
    Linearity 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.

gus_massa 5y ago

They 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 ago
  Perhaps 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 ago
    My 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 ago
That'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 ago
  We 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 ago

It 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 ago
XOR 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 ago
  Linearity 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.