Have there been any serious attempts to use the notion of Kolmogorov complexity to measure the simplicity of models outside of theoretical CS? I mean models in the english sense - any logical set of rules that attempts to predict a specific domain of reality. Or any attempts to balance this measure of complexity against the accuracy of the model (how will it predicts reality / a dataset) and conclude that the results are better than chance?

Any research that attempts to describe how we could use Kolmogorov complexity in some specific field of research would also be most helpful.

  • $\begingroup$ Just to be on the safe side: you are aware that Kolmogorov complexity is not computable (and it appears to be hard to approximate with reasonable precision in practise)? That makes KC difficult a metric to use. $\endgroup$ – Martin Berger Jul 31 at 12:56
  • $\begingroup$ Another issue is that Kolmogorov complexity talks about program size only. Why is that an interesting criterion in your use-case? In practise you want to do something with a model, and it looks like there are hard trade-offs between model size and speed of using a model, the field of succinct data structures studies this trade-off in detail $\endgroup$ – Martin Berger Jul 31 at 12:58
  • $\begingroup$ @MartinBerger Thanks I will look that up. Yes I'm aware KC is not computable, so but one can determine an upper bound (by writing the program themselves and trying to compress it). I hoped that this upper bound should still be enough to prove that a model works better than chance? (when compared to all other models of size less than or equal to) $\endgroup$ – ghosts_in_the_code Jul 31 at 13:53
  • $\begingroup$ @MartinBerger Also yeah I think time taken to run the program can be excluded right? If I have two programs that produce (provably) identical results - one being small but slow and the other being large but fast, I can use the large one in practice but for theory I'll use the size of the small one as a measure of the "simplicity" of my algorithm/model. $\endgroup$ – ghosts_in_the_code Jul 31 at 13:57
  • 2
    $\begingroup$ Have you seen the work by Cilibrasi and Vitanyi? They have several papers on using Kolmogorov-complexity-like notions to do clustering and other tasks. dblp.org/pers/hd/c/Cilibrasi:Rudi In general, Vitanyi and colleagues have done a lot of work in this vein $\endgroup$ – Ryan Williams Jul 31 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.