HNHacker News
TopNewBestAskShowJobs

extremelearning

146 karma · joined June 17, 2018

Martin Roberts web: www.extremelearning.com.au email: martin (@) robertsanalytics.com Twitter: @Techsparx LinkedIn: https://www.linkedin.com/in/martinroberts/
submissionscomments
extremelearning··on The Unreasonable Effectiveness of Quasirandom Sequences
Absolutely! This is actually the original reason I began exploration into quasirandom numbers. I wanted to see if I could replace some of the stochastic process in current machine learning architectures with quasirandom processes.

In principle, the curse of dimensionality kicks in after a dozen or so dimensions, as convergence is O( log(N)^D / N). But in practice I have found that in a surprising number of applications and circumstances, quasirandom sequences can have offer a substantial improvement even when the number of dimensions are in the hundreds or even thousands. (Some authors have suggested this works because the solution space is of low dimensions but embedded in a much higher dimensional space...)

However, to get the full benefit I needed to find a low discrepancy quasirandom sequence that did not suffer the many of the parameter degeneracy problems that many of the conventional ones exhibit for very large D. For me, the new R-sequence nicely solves this parameter selection problem by not having any parameters to optimize!

extremelearning··on The Unreasonable Effectiveness of Quasirandom Sequences
I somewhat stumbled on this during my efforts to improve some machine learning architecture I was working on, so unfortunately no formal proofs as yet. This is one reason why I went down the route of technical blog post rather than more academic routes which would no doubt require more rigour and precise language.

Although in many cases I have reason to strongly believe that it is not possible for other sequences to have similar properties, until such proofs are established, I agree that in a technical paper it would be prudent for me to preface most of the quotes with “only known...”

extremelearning··on The Unreasonable Effectiveness of Quasirandom Sequences
Author here. OMG! Someone submitted my post here and it's got to the front page!! Happy to try to answer any questions that people have. Enjoy!
extremelearning··on Show HN: I'm 12, learning JS, and wrote Wolfram's cellular automaton in Node
Hi Jacob, I never got to thank you for doing the observableHQ notebook for my quasirandom sequencing. For your information, I have linked to it on many occasions which includes in my post "Unreasonable Effectiveness of Quasirandom Sequences" which is on front page of HN right now! :) https://news.ycombinator.com
extremelearning··on Evenly distributing points on a sphere
Interesting question... I just calculated that for the modified Fibonacci sequence (last method): 2.95 < d_N < 3.12.

Technically d* does not exist, because as N-> infinity, d* alternates between 3.03 and 3.07 (depending on if k is odd or even).

Compare this to the canonical fibonacci sequence gives a value of d_N = 3.07 for all values of N, and so d* = 3.07

extremelearning··on Evenly distributing points on a sphere
One of the reasons why this field is still so active is because different measures and methods often result in slightly different optimal configurations. In the case of this post, I focused on direct construction methods; and measures relating to minimum distance or convex hulls.

For an excellent commentary on the latest for optimal Riesz energy (which includes Coulomb potentials) configurations can be found in the first paper that I reference: "A comparison of popular point configurations on S2", by Hardin, Michaels and Saff.

extremelearning··on Evenly distributing points on a sphere
The values for the tetrahedron, cube, octahedron, dodecahedron and icosahedron are:3.27, 3.27, 3.46,3.19 and 3.64, resp.

These produce the largest d for N=4,8,6,12 and 20 resp. Thus, it is presumed by almost everyone that d=3.64 is the global upper bound.

Unfortunately, I believe it is still an open problem to to prove this or to describe a general upper bound for specific N not equal to any of these five values.

extremelearning··on Evenly distributing points on a sphere
Hi I included about a dozen references at the end of my post for overall material on this topic. I specifically chose these ones as they are very readable. My favourite paper is defintiely the first one, "A comparison of popular point configurations on S2". It is very comprehensive in breadth as well as historical developments and includes copious references.

One of my other references is "Distributing many points on a sphere" as it is written by E.B. Saff who is basically a legend in this field. Hope that helps! Martin

extremelearning··on Evenly distributing points on a sphere
Thanks for the kind words. I’m glad you found it interesting and useful.

I think one of the advantages of writing blog posts rather than academic articles is that they are often more readable to a wider audience as the authors can be a little less formal in tone, expand on things (including copious illustrations), without worrying about space constraints.

extremelearning··on Evenly distributing points on a sphere
Author here. So amazed to find that my blog post got featured on Hacker news. Happy to answer any questions that I can! :)
extremelearning··on World Airports Voronoi (2014)
I also love using Voronoi diagrams as well as Delaunay diagrams (via Mathematica).

My most recent exploration with them was to understand and visualize the different structures and characteristics of various low discrepancy quasirandom point distributions in two dimensions.

http://extremelearning.com.au/unreasonable-effectiveness-of-...

Also interesting to compare them with @burfog's comment about the Voronoi / Delaunay diagrams of Penrose Tilings.

extremelearning··on Fibonacci Hashing: The Optimization That the World Forgot
As @twic and the OP discussed, the equal distribution of numbers within a defined range is naturally achieved through low discrepancy sequences (eg recurrence,Halton, Sobol, etc..) Furthermore, in ultra high-speed / low-level computing situations the additive recurrence methods are often preferred due to the incredibly fast and simple method of calculating the each successive term simply by adding (modulo) a constant value to the previous term.

For the one-dimensional case, it is well known, and relatively easily proven that the the additive recurrence method based on the golden ratio offers the optimal 'evenness' [low discrepancy] in distribution [1]. For higher dimensions, it is still an open research question as to how to create provably optimal methods. However, one of my recent blog posts [2] explores the idea that a generalization of the golden ratio, produces results that are possibly optimal, and better than existing contemporary low discrepancy sequences. In the one dimensional case, the critical additive constant is of course, the golden ratio. In the two dimensional case, the additive constant is based on integral powers of the plastic number. The generalization to even higher dimensions follows other Pisot numbers.

[1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Addit...

[2] http://www.extremelearning.com.au/unreasonable-effectiveness...

← PreviousPage 3 of 3