4 ms·
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
by woliveirajr 7y ago
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.
- mherrmann 7y agoWhat's a pigeon problem? Googling for this term only tells me what to do if I have too many pigeons flying around my house.
- FridgeSeal 7y agoProbably referring to the Pigeonhole principle: https://en.m.wikipedia.org/wiki/Pigeonhole_principle https://en.m.wikipedia.org/wiki/Pigeonhole_principle
- stevesimmons 7y agoThe 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!
- tromp 7y agoIn 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}.