Suppose we wanted to set up a system which maps any such sample to its minimal-description-length representation; i. e., to a well-structured world-model that takes advantage of its abstract regularities. How would it work? What are the algorithms that implement search for such representations?
I’m not in the field, but doesn’t algorithmic information theory forbid finding a general algorithm that could discover the minimal description of anything (Kolmogorov complexity)? If I remember correctly, that algorithm is undecidable. There may exist heuristics to asymptotically approach such a solution, but if it’s like approaching Chaitin’s Omega, it would require more computation than any other kind of algorithm (I believe a theorem also proves this).
Perhaps, but we’re not aiming for an algorithm able to discover the minimal description of “anything”. We’re working with an object of a very specific type, that has a very specific structure which could be exploited (perhaps the way these posts sketch out) to find that minimal representation.
I think this is a general problem with these kinds of fundamental impossibility theorems (see also: no-free-lunch theorems, the data-processing inequality, Legg’s minimial-complexity theorem). They’re usually inapplicable to practical cases, because they talk about highly generic objects which are missing all the structures that make those problems solvable in practice. This is a good post on the topic.
I’m not in the field, but doesn’t algorithmic information theory forbid finding a general algorithm that could discover the minimal description of anything (Kolmogorov complexity)? If I remember correctly, that algorithm is undecidable. There may exist heuristics to asymptotically approach such a solution, but if it’s like approaching Chaitin’s Omega, it would require more computation than any other kind of algorithm (I believe a theorem also proves this).
Perhaps, but we’re not aiming for an algorithm able to discover the minimal description of “anything”. We’re working with an object of a very specific type, that has a very specific structure which could be exploited (perhaps the way these posts sketch out) to find that minimal representation.
I think this is a general problem with these kinds of fundamental impossibility theorems (see also: no-free-lunch theorems, the data-processing inequality, Legg’s minimial-complexity theorem). They’re usually inapplicable to practical cases, because they talk about highly generic objects which are missing all the structures that make those problems solvable in practice. This is a good post on the topic.
That’s a fair observation. I will look at this post. Thank you.