I keep feeling like there's a set of fundamental assumptions that can be optimized for, or relaxed and optimized for, in order to get at what a better method might be.
For example, stability of dithering under rotation and or some type of shear translation. What about stability under scaling?
There's been some other methods that essentially create a dither texture on the surface itself but, to me at least, this has a different quality than the "screen space" dithering that Obra Dinn employs.
Does anyone have any ideas on how to make this idea more rigorous? Or is the set of assumption fundamentally contradictory?
One of the biggest issues with dithering stability in screen space is attributable to perspective projection. The division operation is what screws everything up. It introduces a nonlinearity. An orthographic or isometric projection is much more stable.
If sums of independent identically distributed random variables converge to a distribution, they converge to a Levy stable distribution [0]. Tails of the Levy stable distribution are power law, which makes them not Gaussian.
Yes but really what our brains do is use Gaussian Mixture model to cut up those distributions into more granular bell curves which we then call “normal”. Because we find what we are tuned to find.
Eg we find bell curves because we look for bell curves. And given infinite resolution we can find them at some granularity.
The fact the article said that is a gross error. You've identified the issue head on.
The sum of independent identically distributed random variables, if they converge at all, converge to a Levy stable distribution (aka fat-tailed, heavy tailed, power law). In this sense, Levy stable distributions are more "normal" than the normal distribution. They also show up with regular frequency all over nature.
As you point out, infinite variance might be dismissed but, in practice, this just ends up getting larger and larger "outliers" as one keeps drawing from the distribution. Infinities are, in effect, a "verb" and so an infinite variance, in this context, just means the distributions spits out larger and larger numbers the more you sample from it.
Say I have N independent and identically distributed random variables with finite mean. Assuming the sum converges to a distribution, what is the distribution they converge to?
If I had made the extra condition that the random variables had finite variance, you'd be correct. Without the finite variance condition, the distribution is Levy stable.
Levy stable distributions can have finite mean but infinite variance. They can also have infinite mean and infinite variance. Only in the finite mean and finite variance case does it imply a Gaussian.
Levy stable distributions are also called "fat-tailed", "heavy-tailed" or "power law" distributions. In some sense, Levy stable distributions are more normal than the normal distribution. It might be tempting to dismiss the infinite variance condition but, practically, this just means you get larger and larger numbers as you draw from the distribution.
This was one of Mandelbrot's main positions, that power laws were much more common than previously thought and should be adopted much more readily.
As an aside, if you do ever get asked this in an interview, don't expect to get the job if you answer correctly.
Sorry, does the article actually give reasons why the bell curve is "everywhere"?
For simplicity, take N identically distributed random variables that are uniform on the interval from [-1/2,1/2], so the probability distribution function, f(x), on the interval from [-1/2,1/2] is 1.
The Fourier transform of f(x), F(w), is essentially sin(w)/w. Taking only the first few terms of the Taylor expansion, ignoring constants, gives (1-w^2).
Convolution is multiplication in Fourier space, so you get (1-w^2)^n. Squinting, (1-w^2)^n ~ (1-n w^2 / n)^n ~ exp(-n w^2). The Fourier transform of a Gaussian is a Gaussian, so the result holds.
Unfortunately I haven't worked it out myself but I've been told if you fiddle with the exponent of 2 (presumably choosing it to be in the range of (0,2]), this gives the motivation for Levy stable distributions, which is another way to see why fat-tailed/Levy stable distributions are so ubiquitous.
There's a paragraph on discovery that multinomial distributions are normal in the limit. The turn from there to CLT is not great, but that's a standard way to introduce normal distributions and explains a myriad of statistics.
It's not super hard to prove the central limit theorem, and you gave the flavor of one such proof, but it's still a bit much for the likely audience of this article, who can't be assumed to have the math background needed to appreciate the argument. And I think you're on the right track with the comment about stable distributions.
The Fourier transform of a uniform distribution is the sinc function which looks like a quadratic locally around 0. Convolution to multiplication is how the quadratic goes from downstairs to upstairs, giving the Gaussian.
Widths of different uniform distributions along with different centers all still have a quadratic center, so the above argument only needs to be minimally changed.
The added bonus is that if the (1-w^2)^n is replaced by (1-w^a)^n, you can sort of see how to get at the Levy stable distribution (see the characteristic function definition [0]).
The point is that this gives a simple, high-level motivation as to why it's so common. Aside from seeing this flavor of proof in "An Invitation to Modern Number Theory" [1], I haven't really seen it elsewhere (though, to be fair, I'm not a mathematician). I also have never heard the connection of this method to the Levy stable distributions but for someone communicating it to me personally.
I disagree about the audience for Quanta. They tend to be exposed to higher level concepts even if they don't have a lot of in depth experience with them.
Anubis is one such answer [0]. Cryptocurrency and micro transactions are another.
In the last few decades, spam was a problem because the marginal transaction costs of information exchange were orders of magnitude lower than they had been. Note that physical mail spam was, and still, is an issue. Focusing on perceptual or fuzzy computation as the limiting factor, through captchas and other 'human tests', allowed for most spam to be effectively mitigated.
Now that intelligence is becoming orders of magnitude cheaper, perceptual computation challenges no longer work, but we can still do computation challenges in the form of proof of work or proxies thereof. Spam will never wholly go away but we can at least cause more friction by charging bot networks to execute in the form of energy or money.
I don't see how Anubis solves anything. If a human lets the bot control a completely vanilla computer (which there is now a lot of tooling for), then how is it going to stop that?
You're right. My proposed solution only addressed AI at scale (web crawlers, mass spam campaigns, etc.) and doesn't address low bandwidth, "high friction" events like PRs, code reviews, blog posts, etc.
I don't want to dismiss the concerns outright and I'm not sure I have a concise response but my feeling is that, in some sense, it doesn't really matter. If AI is used to create a high quality output, then it should be accepted. If AI is creating low quality output, then it should be easy to verify, maybe with better (AI) tooling.
In other words, the bot problem cannot be solved, in that we might never know whether the source is from human or machine, but it won't matter as that's not the core of the problem, quality content is.
My opinion is that DIT is overstated and, where it isn't, we'll see much better technology evolve to separate the signal from the noise. As an analogy, in the late 1990s, internet search engines were abysmal, raking by document keyword searches and so were easily game-able by content that had nothing to do with the search intent. Google came along with page rank and, almost overnight, made the internet usable. From the bad Yahoo search results, one might be tempted to think that the entirety of the internet looked like what Yahoo was serving, but this was the wrong impression as there were plenty of interesting things on the internet, it just took page rank to provide the necessary filter to make the internet usable.
At most, PoW makes it a bit annoying to scale: you need to add some form of RPC that delegates solving to a beefy+cheap Hetzner server. If you're really scaling and it's getting expensive, you can rent a GPU to do batch solves.
This is awesome. I think I've heard of other research that's similar to try and speed up Navier-Stokes or other water/smoke/etc. simulation.
But this isn't actually recreating murmurations, is it? This is a neural network that's using the Reynolds criteria as a loss function, with Cavagna's topological neighbors?
As far as I know, there's no good research that reproduces the murmations seen in starling flocks. This seems like it would be a good use case for neural networks but I don't know of any publicly available 3d data of actual starling flocks, aside from some random YouTube videos floating around.
For example, stability of dithering under rotation and or some type of shear translation. What about stability under scaling?
There's been some other methods that essentially create a dither texture on the surface itself but, to me at least, this has a different quality than the "screen space" dithering that Obra Dinn employs.
Does anyone have any ideas on how to make this idea more rigorous? Or is the set of assumption fundamentally contradictory?
reply