Machine Learning, Kolmogorov Complexity, and Squishy Bunnies (2019) • Hacker News Board

Re: Machine Learning, Kolmogorov Complexity, and Squishy Bunnies (2019)

#21

Post by tromp » Thu, Feb 27, 2020, 2:01 PM UTC

stevesimmons wrote: post #13

mherrmann wrote: post #7

Earlier quoted context omitted.

What's a pigeon problem? Googling for this term only tells me what to do if I have too many pigeons flying around my house.

The pigeon-hole principle. If you have N+1 things and N pigeonholes to put them in, at least one pigeonhole must have more than 1 thing!

In particular, since the number of binary strings of length n exceeds the number of shorter strings, there must be a string of length n that's not described by a shorter program, i.e. that's incompressible.

More generally, the fraction of strings of length n that can be compressed by k or more bits is less than 2^{-k}.

Re: Machine Learning, Kolmogorov Complexity, and Squishy Bunnies (2019)

#22

Post by petermcneeley » Thu, Feb 27, 2020, 3:11 PM UTC

ThePhysicist wrote: post #17

keenmaster wrote: post #14

Earlier quoted context omitted.

A “300-5000x” gain in simulation speed for low-complexity simulations would be impressive. If a blade of grass is low complexity, then I assume that would free up resources from basic environmental rendering for more complex objects, and greater complexity in those objects (which themselves might benefit from ML, but with <300x gains). Until everyone has near infinite computing power, that’s a de facto improvement in…

How would you reach such a gain though? Most physics-based simulations are really efficient already. For example, cloth simulations usually work using a grid of points (finite element approach) that are evolved using a differential equation and a constraint solver (not an expert in this particular area but I wrote e.g. electrodynamic simulations). Each point is usually only connected to its immediate neighbors, so th…

They used low inertia cloth and solids because these are the kinds of scenarios that this technique can best approximate.

Once you buy into the concept that your simulation can be represented by a very limited number of parameters it's not hard to suggest that this small state vector can be mutated from state to state using ML.

The issue with this technique is PCA not ML.

I can certainly see this technique being used in place of some existing simulation or animation based secondary motion in video games.

Note that adding up the contributions of 256 basis vectors might be more expensive than a per vertex cloth simulation.

I am experienced in these areas and have done grad computational physics and work on game engines for a living.

Re: Machine Learning, Kolmogorov Complexity, and Squishy Bunnies (2019)

#23

Post by superpermutat0r » Thu, Feb 27, 2020, 6:50 PM UTC

davidwihl wrote: post #10

manthideaal wrote: post #8

Using Kolmogorov Complexity and then using PCA is not valid since you are approximating a solution and Kolmogorov Complexity is for exact solutions. Anyway perhaps there is, or should be defined, a signal/noise Kolmogorov Complexity measure, that is the shortest length of a program that computes an approximate solution within an epsilon distance of the true solution. Also since PCA is discussed, why not use SVD? Edit…

Well stated. The author also misses two other critical points: (1) accuracy is a poor measure of quality for non-numeric, classification type problems, (2) increasing model complexity has an asymptote in order to prevent overfitting. You can’t arbitrarily increase the number of weights and expect that the NN will continue to improve.

The thing about NN is that increasing the weights does improve the performance. The standard way to get good performance and see if your architecture works is just get the network huge (wide). After you see it works you get it small.

The "common wisdom" of "too many parameters will make you overfit" is most definitely not that important for the way modern NN training works.