Re:Are deep neural networks dramatically overfitted? (2019)
by logicchains on Monday April 05, 2021 @06:26AM
(#26697238)
>Relative to a device to perform the understanding.
It uses Kolmogorov complexity, which is defined as the length of a shortest computer program in a predetermined programming language that produces the object as output. Note that this measure is relative to a programming language, not a program, and the exact choice of language doesn't matter too much. Compression means creating a smaller program that produces the same output, and to produce the same output with less code necessarily requires more understanding.
As a concrete example, imagine the output is [1,2,fizz,4,buzz,fizz,7,8,fizz,buzz,11,fizz,13,14,fizzbuzz..1000). The longest program to output this would just hard-code it in the source code (much as a very inexperienced programmer might solve the problem, or a large neural net). Someone with a better understanding would write a program using iteration and the modulus operator, which would be shorter.
It uses Kolmogorov complexity, which is defined as the length of a shortest computer program in a predetermined programming language that produces the object as output. Note that this measure is relative to a programming language, not a program, and the exact choice of language doesn't matter too much. Compression means creating a smaller program that produces the same output, and to produce the same output with less code necessarily requires more understanding.
As a concrete example, imagine the output is [1,2,fizz,4,buzz,fizz,7,8,fizz,buzz,11,fizz,13,14,fizzbuzz..1000). The longest program to output this would just hard-code it in the source code (much as a very inexperienced programmer might solve the problem, or a large neural net). Someone with a better understanding would write a program using iteration and the modulus operator, which would be shorter.