Extreme Learning

I am a statistician / data scientist who blogs about nifty sampling methods, which are frequently used in rendering computer graphics such as: ray-tracing (via Quasi-Monte Carlo methods), object placement, dithering, etc... http://www.extremelearning.com.au All these methods try to find the most efficient sampling techniques that minimize various undesirable effects such as aliasing. Techniques and topics include: blue noise distributions; low discrepancy quasirandom sequences; orthogonal grid-based sampling; and even-sampling on the surface of n-spheres. My most favourite articles (two of which have previously been featured on HN) include: * "The unreasonable effectiveness of quasirandom sequences" http://extremelearning.com.au/unreasonable-effectiveness-of-quasirando… * "A new method to construct isotropic blue noise with uniform projections" http://extremelearning.com.au/isotropic-blue-noise-point-sets/ * "Evenly distributing points on a sphere" http://extremelearning.com.au/evenly-distributing-points-on-a-sphere/ I hope that someone finds some of these useful and interesting. ;)

After implementing a number of dithering approaches, including blue noise and the three line approach used in modern games, I’ve found that quasi random sequences give the best results. Have you tried them out? https://extremelearning.com.au/unreasonable-effectiveness-of-quasirand…

See [1] [2] and there is a great treatment of the topic in this book [3]. I don't know exactly what's he doing, but if I was doing some kind of monte carlo integration (like the family of energy surfaces in 6-dimensional space that I plotted the volume of as a function of energy for my PhD thesis) I'd be really concerned about the "uniform" part. [1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence [2] https://extremelearning.com.au/unreasonable-effectiveness-of-quasirand… [3] https://numerical.recipes/

This article was written before this one: https://extremelearning.com.au/unreasonable-effectiveness-of-quasirand… You should definitely read that one instead. It's such a great method (and article) that I'll even forgive their use of "unreasonable effectiveness".

For sampling points on a plane (or other geometries), there is an even better algorithm: http://extremelearning.com.au/unreasonable-effectiveness-of-quasirando… (Yes, no https - I promise the visualizations are worth it!)

The fibonacci hashing mentioned here looks to be just Kronecker low-discrepancy sequences https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Additive_recurr… which is used for dithering too (see eg https://extremelearning.com.au/unreasonable-effectiveness-of-quasirand… It's quite likely already what Spotify were obliquely referring to. But I think the author missed a trick: tracks by an artist occur close together if your collection is already arranged by artist/album. Picking tracks far apart from the globally sorted list is what this sequence will do, and do you don't need to do anything at all to split by artist/album/category etc: 1. for the Kth track in a sorted collection of N with seed S in [0,1), pick track number floor(N((K(phi-1)+S)%1)). 2. There is no step 2. Since Spotify suggest their algorithm is only a couple of lines, I'd guess this is what they did. edited to add: the above would get pretty boring because songs would always follow one another in sequence, no matter what the seed was. But since the chance of picking an irrational number at random in a real interval is a near certainty (because rationals are countable and reals are uncountable) you can just pick any new random number as the stepsize in the sequence when you start to shuffle play and it should be good enough; picking in [.25, .75) avoids steps that take you back too close to the same artist.

I would say very close to the top is the amazing depth of sampling methods, in particular Quasi-Monte Carlo (QMC) methods. I'll try to give a small sample of that. Basically what you're doing in MC is estimating expected values (and thereby integrals: average height times base width equals area under the graph) using random numbers, to be roughly thought of as a rnd() function which gives you back a float in [0,1). However, using actual proper random number generators has a very slow convergence rate, as the random numbers chosen will tend to clump; on the other hand, if you just use a perfectly uniform distribution, you'll suffer from correlation problems. Consider a 1-D numerical integration problem, and instead of using rnd() to pick points in your integrand range, you start with some seed value in [0,1), and each time you need a new random number, you add phi-1 to the existing number and mod with 1.0 to get the new number. If you plot this sequence on a [0,1) number line, you'll see that it divides up the interval into finer pieces really nicely, magically keeping a good distance from all the previous values, without even knowing them! Why does this work? Well, there's a lot of beautiful theory about phi (also relating to biology and nature, e.g. seashells and the distribution of sunflower seeds), in particular how it is in some sense (continued fraction) the "most irrational" number. Does it work well for other numbers, and can it be extended to higher dimensions?…

Yes: http://extremelearning.com.au/unreasonable-effectiveness-of-quasirando… Sibling comments are completely correct. Graphics simulations often require quasirandom sequences; the particular sequence is not important, but any correlations in the sequence will be visible in the output as artifacts, so we want a decorrelated sequence. If this is not enough of a real-world example for you, then Monte Carlo methods also show up in weather modeling, financial planning, and election forecasting. In those predictive systems, there is extreme uncertainty and dependence on initial conditions, which we model with quasirandom sequences and seed numbers respectively. By running many simulations with different random sequences and then examining all of the results statistically, we can get good estimates of future behavior. Edit: Oh, you're not in good faith. Okay, cool story. Best of luck with whatever imaginary idea of "unpredictability" you're trying to define, but you might want to return to actual maths at some point.

https://extremelearning.com.au/unreasonable-effectiveness-of-quasirand… (Unreasonable Effectiveness of Quasirandom Sequences) has a section dedicated to spheres. TL;DR: Generate two orthogonal sequences, map with sin/cos. I think this method is currently state of the art. It provably doesn't clump in higher dimensions. Also, it is blue enough for Monte Carlo.

I needed something related, n roughly evenly distributed points on the surface of a sphere. Ended up using a Fibonacci spiral. https://extremelearning.com.au/how-to-evenly-distribute-points-on-a-sp…

See also this method based on optimizing nearest-neighbor distances after initializing with fibonacci spiral: https://extremelearning.com.au/how-to-evenly-distribute-points-on-a-sp…

Related: https://extremelearning.com.au/unreasonable-effectiveness-of-quasirand… Also related is the occurrence of the golden ratio in nature: https://www.wolframscience.com/nks/p411--growth-of-plants-and-animals/

For more methods to uniformly generate points on an n-dimensional sphere and inside an n-dimensional ball: http://extremelearning.com.au/how-to-generate-uniformly-random-points-… I quite like the normalized Gaussian method.

For those interested in this problem, a while back I wrote a blog post listing all the well-known ways of correctly generating random points on the surface (or inside) of a d-dimensional sphere. It includes all the frequently used ones as well as some lesser know elegant methods. http://extremelearning.com.au/how-to-generate-uniformly-random-points-…

Try http://extremelearning.com.au/unreasonable-effectiveness-of-quasirando…

Here’s a more mathematical description of the “sunflower pattern” on the sphere, a spherical Fibonacci lattice: http://extremelearning.com.au/evenly-distributing-points-on-a-sphere/ As a live notebook: https://observablehq.com/@mbostock/spherical-fibonacci-lattice