<p>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 <a href="https://en.wikipedia.org/wiki/Model" rel="nofollow noreferrer">models</a> 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?</p>
<p>Any research that attempts to describe how we could use Kolmogorov  complexity in some specific field of research would also be most helpful.</p>

CC BY-SA 4.0
2020-07-31T12:56:00.350Z
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.
Martin Berger
CC BY-SA 4.0
2020-07-31T12:58:16.257Z
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](https://en.wikipedia.org/wiki/Succinct_data_structure) studies this trade-off in detail
Martin Berger
CC BY-SA 4.0
2020-07-31T13:53:23.280Z
@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)
ghosts_in_the_code
CC BY-SA 4.0
2020-07-31T13:57:36.127Z
@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.
ghosts_in_the_code
CC BY-SA 4.0
2020-07-31T17:36:27.317Z
In my experience one cannot easily get *non-trivial* upper bounds on KC by writing a program and then compressing 'by hand'.
Martin Berger
CC BY-SA 4.0
2020-07-31T17:55:30.647Z
@MartinBerger I agree but that bound could still be sufficient to prove for instance that out of say n^n n-state Turing machines that exist, your model has an accuracy greater than 1/ n^n or something (and is therefore better than picking Turing machines at random and hoping one fits). Again I could be wrong. Thanks for your time though.
ghosts_in_the_code
CC BY-SA 4.0
2020-07-31T22:46:27.173Z
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. https://dblp.org/pers/hd/c/Cilibrasi:Rudi In general, Vitanyi and colleagues have done a lot of work in this vein
Ryan Williams
<reference-request><kolmogorov-complexity>
Reference request on using Kolmogorov complexity to measure the simplicity of models
ghosts_in_the_code
# Reference request on using Kolmogorov complexity to measure the simplicity of models

(Asked by: username_0 on 2020-07-30)

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](https://en.wikipedia.org/wiki/Model) 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.

**Tags:** reference-request, kolmogorov-complexity

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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](https://en.wikipedia.org/wiki/Succinct_data_structure) studies this trade-off in detail  
> **username_0**: @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)  
> **username_0**: @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.  
> **username_1**: In my experience one cannot easily get *non-trivial* upper bounds on KC by writing a program and then compressing 'by hand'.  
> **username_0**: @MartinBerger I agree but that bound could still be sufficient to prove for instance that out of say n^n n-state Turing machines that exist, your model has an accuracy greater than 1/ n^n or something (and is therefore better than picking Turing machines at random and hoping one fits). Again I could be wrong. Thanks for your time though.  
> **username_2**: 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. https://dblp.org/pers/hd/c/Cilibrasi:Rudi In general, Vitanyi and colleagues have done a lot of work in this vein  

---

## 0 answers

