Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When good pseudorandom numbers go bad

blog.djnavarro.net

Post reply on HN
Print view View original

11–20 of 39 posts

Re: When good pseudorandom numbers go bad

#11

Post by AlotOfReading »

craigacp wrote: post #4
AlotOfReading wrote: post #2

Most people don't really care about numerical stability or correctness. What they usually want is reproducibility, but they go down a rabbit hole with those other topics as a way to get it, at least in part because everyone thinks reproducibility is too slow. It was 20 years ago, but that's not the case today. The vast majority of hardware today implements 754 reproducibly if you're willing to stick to a few basic pr…

The same operations in the same order is a tough constraint in an environment where core count is increasing and clock speeds/IPC are not. It's hard to rewrite some of these algorithms to use a parallel decomposition that's the same as the serial one. I've done a lot of work on reproducibility in machine learning systems, and its really, really hard. Even the JVM got me by changing some functions in `java.lang.Math`…

Many systems I've worked on can be written as embarrassingly parallel with synchronized checkpoints for a relatively small cost if they're not serial, but yeah, the middle ground is hard. That's the nature of the beast though. Imagine trying to rearrange the instructions in your program the same way. You're going to get all sorts of wacky behavior unless you invest an enormous amount of effort into avoiding problems the way superscalar CPUs do.

Relatively few programs truly need to operate that way though and they're usually written by people who know the cost of their choices.

Re: When good pseudorandom numbers go bad

#12

Post by coolcase »

mattb314 wrote: post #6
coolcase wrote: post #5

I don't grok this but if you had to describe it in a nutshell, is this because of a race condition? Differences in HW? Floating point ops have some randomness built in?

Super rough summary of the first half: in order to pick out random vectors with a given shape (where the "shape" is determined by the covariance matrix), MASS::mvrnorm() computes some eigenvectors, and eigenvectors are only well defined up to a sign flip. This means tiny floating differences between machines can result in one machine choosing v_1, v_2, v_3,... as eigenvectors, while another machine chooses -v_1, v_3,…

Thanks! So machine differences in their FP units drives the entropy, and the code doesn't handle that when picking eigenvectors?

Re: When good pseudorandom numbers go bad

#13

Post by jdougan »

mjcohen wrote: post #3

I found this an enjoyable read. I also have Wilkinson, both text and Algol book, which I used many years ago to write a fortran eigenvalue/vector routine. Worked very nicely. Done in VAX fortran and showed me that having subscript checking on added 30% to the run time.

I wonder what the bounds-check overhead looks like on a modern machine for that code?

Re: When good pseudorandom numbers go bad

#14

Post by thaumasiotes »

AlotOfReading wrote: post #10
thaumasiotes wrote: post #8

Earlier quoted context omitted.

I don't actually understand why you'd want reproducibility in a statistical simulation. If you fix the output, what are you learning? The point of the simulation is to produce different random numbers so you can see what the outcomes are like... right? Let's say I write a paper that says "in this statistical model, with random seed 1495268404, I get Important Result Y", and you criticize me on the grounds that when y…

The point is that if you run the simulation with seed X, you'll get the same results I do. This means that all you need to reproduce my results is the code and any inputs like the seed, rather than the entire execution history. If you want to provide different inputs and get the same result, that's another matter entirely (where numerical stability will be much more important).

But what is the value of reproducing your results that way? Those results only mean anything if they're similar to what happens with other seeds.

Re: When good pseudorandom numbers go bad

#16

Post by saagarjha »

craigacp wrote: post #4
AlotOfReading wrote: post #2

Most people don't really care about numerical stability or correctness. What they usually want is reproducibility, but they go down a rabbit hole with those other topics as a way to get it, at least in part because everyone thinks reproducibility is too slow. It was 20 years ago, but that's not the case today. The vast majority of hardware today implements 754 reproducibly if you're willing to stick to a few basic pr…

The same operations in the same order is a tough constraint in an environment where core count is increasing and clock speeds/IPC are not. It's hard to rewrite some of these algorithms to use a parallel decomposition that's the same as the serial one. I've done a lot of work on reproducibility in machine learning systems, and its really, really hard. Even the JVM got me by changing some functions in `java.lang.Math`…

You can definitely do operations in a reproducible way (assuming you do the reductions in a defined order) but, yeah, you might lose some performance. Unfortunately the ML people seem to pick better performance over correctness basically every time :(

Re: When good pseudorandom numbers go bad

#17

Post by saagarjha »

thaumasiotes wrote: post #14
AlotOfReading wrote: post #10

Earlier quoted context omitted.

The point is that if you run the simulation with seed X, you'll get the same results I do. This means that all you need to reproduce my results is the code and any inputs like the seed, rather than the entire execution history. If you want to provide different inputs and get the same result, that's another matter entirely (where numerical stability will be much more important).

But what is the value of reproducing your results that way? Those results only mean anything if they're similar to what happens with other seeds.

If something fails, I can reproduce the failure with your seed.

Re: When good pseudorandom numbers go bad

#18

Post by saagarjha »

coolcase wrote: post #12
mattb314 wrote: post #6

Earlier quoted context omitted.

Super rough summary of the first half: in order to pick out random vectors with a given shape (where the "shape" is determined by the covariance matrix), MASS::mvrnorm() computes some eigenvectors, and eigenvectors are only well defined up to a sign flip. This means tiny floating differences between machines can result in one machine choosing v_1, v_2, v_3,... as eigenvectors, while another machine chooses -v_1, v_3,…

Thanks! So machine differences in their FP units drives the entropy, and the code doesn't handle that when picking eigenvectors?

It doesn't have to be their FP units; it could be that they run the operations in different orders, or that some different modes were set. I don't think the blog post goes into detail as to why but it does explain how this "cascades" into very different results coming out of the actual operation being performed.

Re: When good pseudorandom numbers go bad

#19

Post by somat »

This is a perpetual problem in computer science, people want a hash function, then decide that the random function very nearly does what they want. then use the random function as a hash function and are dumbfounded that it turns out there is no hard specification for how it works internally. The random function has no guarantee of result across versions, system, time. Hell I would even be harsh enough to say that any reproducibility in random is an accident of implementation. random should always be considered the non-deterministic function, hash is the deterministic function.

Re: When good pseudorandom numbers go bad

#20

Post by Dylan16807 »

craigacp wrote: post #4
AlotOfReading wrote: post #2

Most people don't really care about numerical stability or correctness. What they usually want is reproducibility, but they go down a rabbit hole with those other topics as a way to get it, at least in part because everyone thinks reproducibility is too slow. It was 20 years ago, but that's not the case today. The vast majority of hardware today implements 754 reproducibly if you're willing to stick to a few basic pr…

The same operations in the same order is a tough constraint in an environment where core count is increasing and clock speeds/IPC are not. It's hard to rewrite some of these algorithms to use a parallel decomposition that's the same as the serial one. I've done a lot of work on reproducibility in machine learning systems, and its really, really hard. Even the JVM got me by changing some functions in `java.lang.Math`…

Most people aren't spreading single calculations across multiple cores, and the ones that do are already deep enough into the technical weeds to handle deterministic chunking and combining.

"parallel decomposition that's the same as the serial one" would be difficult in many ways, but only needed when you can't afford a one-time change.

Post reply on HN