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

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

theorangeduck.com

Post reply on HN
Print view View original

11–20 of 23 posts

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

#11

Post by FridgeSeal »

mherrmann wrote: post #7
woliveirajr wrote: post #3

When I first learned about Kolmogorov complexity I understood it as the amount of symbols you have to use, from some specific vocabulary, to represent something. It walks side-by-side with compression (and pigeon problems). Using Kolmogorov to improve ML in those physical examples means that the solution will be better to the specific case, not that there'll come a one-in-all solution to any kind of clothes animation…

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.

Probably referring to the Pigeonhole principle: https://en.m.wikipedia.org/wiki/Pigeonhole_principle

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

#12

Post by [deleted] »

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.

[deleted]

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

#13

Post by stevesimmons »

mherrmann wrote: post #7
woliveirajr wrote: post #3

When I first learned about Kolmogorov complexity I understood it as the amount of symbols you have to use, from some specific vocabulary, to represent something. It walks side-by-side with compression (and pigeon problems). Using Kolmogorov to improve ML in those physical examples means that the solution will be better to the specific case, not that there'll come a one-in-all solution to any kind of clothes animation…

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!

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

#14

Post by keenmaster »

ThePhysicist wrote: post #6
keenmaster wrote: post #2

Key quote from the conclusion: "Neural Networks are not just good for things we don't know how to solve, they can provide massive performance gains on problems we already know how to solve." That quote is in reference to tasks such as physics simulation. There is an incredible GIF in the OP which shows a digital mannequin being manipulated, with its dress flowing in a hyper-realistic manner due to ML physics simulati…

I don’t think the cloth simulation is based on ML, this looks like a normal physics-based solver. If I understand the article correctly the author just uses this as an example of complex behavior that could be learned using ML, but he/she doesn’t indicate that this was actually done using ML. I know some papers that try to improve physics simulations with deep learning and I think it’s definitely possible, not sure t…

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 simulation quality right?

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

#15

Post by jcims »

New concepts to me coming from outside the field. Kolmogorov complexity was discussed just recently on Lex Fridman's podcast with Marcus Hutter - https://www.youtube.com/watch?v=E1AxVXt2Gv4&t=905

I don't know enough to say how accurate Hutter's explanation is but it made sense to me.

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

#16

Post by svantana »

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.

Overfitting shouldn't be an issue for approximation of a known function, where you can generate an arbitrary amount of "training data". Of course you may not have the resources to do so, but that's a whole different tradeoff.

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

#17

Post by ThePhysicist »

keenmaster wrote: post #14
ThePhysicist wrote: post #6

Earlier quoted context omitted.

I don’t think the cloth simulation is based on ML, this looks like a normal physics-based solver. If I understand the article correctly the author just uses this as an example of complex behavior that could be learned using ML, but he/she doesn’t indicate that this was actually done using ML. I know some papers that try to improve physics simulations with deep learning and I think it’s definitely possible, not sure t…

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 the update algorithm only needs to do some simple arithmetic operations for each point. Often there's another step afterwards that ensures the constraints are met. All this can be executed really efficiently on a GPU already. Here's an example of an electrodynamics simulation I wrote: https://github.com/adewes/fdtd-ml

To achieve a 300-500 speedup of this seems impossible because for a single grid point we only do a few numerical operations to update it, so it's hard to see how one could reduce that much further as even an ML-based model will need to update each grid point to maintain the level of detail.

I think there are definitely other areas where ML can speed up things, but IMO cloth simulation is just a really bad example because it's a problem that can be solved using a nearest-neighbors approach with rather simple equations. Problems where you have non-local interactions or more complex dynamics might profit more from ML, but most physics problems can be solved faster with much simpler approaches, I think.

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

#19

Post by Schiphol »

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…

> perhaps there is, or should be defined, a signal/noise Kolmogorov Complexity measure

This is studied in so-called algorithmic rate-distortion theory:

Rooij, S. de, & Vitanyi, P. (2012). Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising. IEEE Transactions on Computers, 61(3), 395–407. https://doi.org/10.1109/TC.2011.25

Vereshchagin, N., & Vitányi, P. (2006). On Algorithmic Rate-Distortion Function. Information Theory, 2006 IEEE International Symposium On, 798–802.

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

#20

Post by bitforger »

svantana wrote: post #16
davidwihl wrote: post #10

Earlier quoted context omitted.

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.

Overfitting shouldn't be an issue for approximation of a known function, where you can generate an arbitrary amount of "training data". Of course you may not have the resources to do so, but that's a whole different tradeoff.

Even then, it might not really be an issue.

https://youtu.be/5-Kqb80h9rk

Post reply on HN