Hacker News Reader

Comment by SeanLuke | Hacker News Reader

> 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.

View on HN

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.

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-winte...

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.

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?

> 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.

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.

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.

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.

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.

Reply on news.ycombinator.com