4 ms·
The theory behind this kind of approach is actually very deep. If we had a “perfect compressor” that returned the shortest non-halting prefix-free Turing machin
by Xcelerate 5y ago
The theory behind this kind of approach is actually very deep. If we had a “perfect compressor” that returned the shortest non-halting prefix-free Turing machine that, when run, output the original dataset, this would essentially be the best classifier we could create. But as the author notes, there are some heavy computational penalties to overcome for this, even to an approximation.
- thunderbird120 5y agoYeah it's an interesting concept. In the ML community recently there has been some informal chatter along similar lines. Essentially, you can prove that by modeling the probability of every element in a dataset given every other set of elements, what you are learning is the core underlying structure which defines the data you are modeling. A perfect model of this structure represents the most efficient possible representation of the information. This is kind of like how if you want to represent an arbitrarily long "game" in Conway's Game of Life you only need to give the starting position because we know exactly how the game state will look at every step because we know the rules of the game. This basically suggests that generalization in a ML model is a function of compression efficiency. ML models memorizing data isn't actually an issue. It's memorizing data INEFFICIENTLY that a problem. Models which overfit have learned inefficient representations of the underlying relationships.
- woliveirajr 5y agoKolmogovov complexity and the proofs of its incomputability are there to explain it.